import type {UnknownCollection} from './unknown-collection.d.ts';
import type {NonRecursiveType, KeyToString, CountExactInArray} from './internal/index.d.ts';
import type {IsNumberLike} from './is-number-like.d.ts';
import type {ApplyDefaultOptions} from './apply-default-options.d.ts';
import type {IsAny} from './is-any.d.ts';
import type {UnknownArray} from './unknown-array.d.ts';
import type {GreaterThan} from './greater-than.d.ts';
import type {IsNever} from './is-never.d.ts';
import type {ExtendsStrict} from './extends-strict.d.ts';
import type {Sum} from './sum.d.ts';
import type {And} from './and.d.ts';
import type {OptionalKeysOf} from './optional-keys-of.d.ts';
import type {OptionalPaths} from './optional-paths.d.ts'; // For `@link`
import type {NonNullableDeep} from './non-nullable-deep.d.ts'; // For `@link`
import type {ConditionalKeys} from './conditional-keys.d.ts'; // For `@link`

/**
Options for the `Paths` type.

@see {@link Paths}
*/
export type PathsOptions = {
	/**
	The maximum depth to recurse when searching for paths. Range: 0 ~ 10.

	@default 5
	*/
	maxRecursionDepth?: number;

	/**
	The maximum number of times to recurse into a circular reference, like a `parent` property that points back to its own type.

	Use it to limit large self-referencing types without lowering {@link PathsOptions.maxRecursionDepth | `maxRecursionDepth`} for the rest of the type. With `0`, the circular property is included, but `Paths` does not go into it. `maxRecursionDepth` still applies.

	When {@link PathsOptions.leavesOnly | `leavesOnly`} is `true`, a path that stops at this limit counts as a leaf.

	@default number

	@example
	```
	import type {Paths} from 'type-fest';

	type Node = {
		value: string;
		parent: Node;
	};

	type A = Paths<Node, {maxCircularDepth: 0}>;
	//=> 'value' | 'parent'

	type B = Paths<Node, {maxCircularDepth: 1}>;
	//=> 'value' | 'parent' | 'parent.value' | 'parent.parent'
	```
	*/
	maxCircularDepth?: number;

	/**
	Use bracket notation for array indices and numeric object keys.

	@default false

	@example
	```
	import type {Paths} from 'type-fest';

	type ArrayExample = {
		array: ['foo'];
	};

	type A = Paths<ArrayExample, {bracketNotation: false}>;
	//=> 'array' | 'array.0'

	type B = Paths<ArrayExample, {bracketNotation: true}>;
	//=> 'array' | 'array[0]'
	```

	@example
	```
	import type {Paths} from 'type-fest';

	type NumberKeyExample = {
		1: ['foo'];
	};

	type A = Paths<NumberKeyExample, {bracketNotation: false}>;
	//=> 1 | '1' | '1.0'

	type B = Paths<NumberKeyExample, {bracketNotation: true}>;
	//=> '[1]' | '[1][0]'
	```
	*/
	bracketNotation?: boolean;

	/**
	Only include leaf paths in the output.

	A path whose value can be `null` or `undefined` is also a leaf, even if the value can be an object too. An optional property (`?`) is not a leaf because of its implicit `undefined`, but explicitly including `undefined` in the property type makes it a leaf. To leave out such paths, remove `null` and `undefined` first with {@link NonNullableDeep}.

	@default false

	@example
	```
	import type {Paths} from 'type-fest';

	type Post = {
		id: number;
		author: {
			id: number;
			name: {
				first: string;
				last: string;
			};
		};
	};

	type AllPaths = Paths<Post, {leavesOnly: false}>;
	//=> 'id' | 'author' | 'author.id' | 'author.name' | 'author.name.first' | 'author.name.last'

	type LeafPaths = Paths<Post, {leavesOnly: true}>;
	//=> 'id' | 'author.id' | 'author.name.first' | 'author.name.last'
	```

	@example
	```
	import type {Paths} from 'type-fest';

	type ArrayExample = {
		array: Array<{foo: string}>;
		tuple: [string, {bar: string}];
	};

	type AllPaths = Paths<ArrayExample, {leavesOnly: false}>;
	//=> 'array' | 'tuple' | `array.${number}` | `array.${number}.foo` | 'tuple.0' | 'tuple.1' | 'tuple.1.bar'

	type LeafPaths = Paths<ArrayExample, {leavesOnly: true}>;
	//=> `array.${number}.foo` | 'tuple.0' | 'tuple.1.bar'
	```

	@example
	```
	import type {NonNullableDeep, Paths} from 'type-fest';

	type User = {
		name: string;
		address: {city: string} | null;
	};

	type LeafPaths = Paths<User, {leavesOnly: true}>;
	//=> 'name' | 'address' | 'address.city'

	type NonNullableLeafPaths = Paths<NonNullableDeep<User>, {leavesOnly: true}>;
	//=> 'name' | 'address.city'
	```
	*/
	leavesOnly?: boolean;

	/**
	Only include paths at the specified depth. By default all paths up to {@link PathsOptions.maxRecursionDepth | `maxRecursionDepth`} are included.

	Note: Depth starts at `0` for root properties.

	@default number

	@example
	```
	import type {Paths} from 'type-fest';

	type Post = {
		id: number;
		author: {
			id: number;
			name: {
				first: string;
				last: string;
			};
		};
	};

	type DepthZero = Paths<Post, {depth: 0}>;
	//=> 'id' | 'author'

	type DepthOne = Paths<Post, {depth: 1}>;
	//=> 'author.id' | 'author.name'

	type DepthTwo = Paths<Post, {depth: 2}>;
	//=> 'author.name.first' | 'author.name.last'

	type LeavesAtDepthOne = Paths<Post, {leavesOnly: true; depth: 1}>;
	//=> 'author.id'
	```
	*/
	depth?: number;

	/**
	Include paths to the elements of arrays and tuples.

	When `false`, the path to an array or tuple is still included, but the paths to its elements are not. With {@link PathsOptions.leavesOnly | `leavesOnly`}, the path to an array or tuple then counts as a leaf. If the given type is itself an array or tuple, the result is `never`.

	Use-case: The paths are used with an API that cannot address array elements, like Firestore field paths.

	@default true

	@example
	```
	import type {Paths} from 'type-fest';

	type Project = {
		filename: string;
		listA: string[];
		listB: [{filename: string}];
		folder: {
			name: string;
		};
	};

	type AllPaths = Paths<Project, {recurseIntoArrays: true}>;
	//=> 'filename' | 'listA' | 'listB' | 'folder' | `listA.${number}` | 'listB.0' | 'listB.0.filename' | 'folder.name'

	type WithoutArrayPaths = Paths<Project, {recurseIntoArrays: false}>;
	//=> 'filename' | 'listA' | 'listB' | 'folder' | 'folder.name'

	type LeafPaths = Paths<Project, {recurseIntoArrays: false; leavesOnly: true}>;
	//=> 'filename' | 'listA' | 'listB' | 'folder.name'
	```
	*/
	recurseIntoArrays?: boolean;

	/**
	Only include paths that do not go through an optional key.

	A key is optional when it has the `?` modifier, so a required key whose type includes `undefined` is still included. Index signatures are not optional, and neither is the `number` index of an array or of a tuple with a rest element. For a union, each member is checked separately, so a key that is optional in one member but required in another is included. With {@link PathsOptions.leavesOnly | `leavesOnly`}, an object whose keys are all optional, or a tuple whose elements are all optional, counts as a leaf, like an empty object.

	Use-case: Get the paths to the properties that must be present, like the required fields of a config. To get the paths to optional keys instead, use {@link OptionalPaths}.

	@default false

	@example
	```
	import type {Paths} from 'type-fest';

	type Project = {
		filename: string;
		size?: number;
		options: {
			timeout?: number;
		};
		folder: {
			name: string;
			subfolder?: {
				filename: string;
			};
		};
	};

	type RequiredPaths = Paths<Project, {requiredOnly: true}>;
	//=> 'filename' | 'options' | 'folder' | 'folder.name'

	type RequiredLeafPaths = Paths<Project, {requiredOnly: true; leavesOnly: true}>;
	//=> 'filename' | 'options' | 'folder.name'
	```
	*/
	requiredOnly?: boolean;

	/**
	Only include paths whose value type is assignable to this type.

	The checked value is what reading the path gives, so an optional property includes `undefined`: `{name?: string}` matches `string | undefined`, not `string`. A union value is checked as a whole, so `{a: string | number}` does not match `string`. For a single object, these are the matching rules of {@link ConditionalKeys}.

	Only the value at the end of the path is checked, so a path can still go through an optional property. Add {@link PathsOptions.requiredOnly | `requiredOnly`} to leave those out.

	Use-case: You want a type-safe way to refer only to the paths that hold a specific kind of value, like every `string` path in a translation object.

	The default, `unknown`, includes every path.

	@default unknown

	@example
	```
	import type {Paths} from 'type-fest';

	type Project = {
		id: number;
		title: string;
		tags: string[];
		scores: [number, number];
		owner: {
			name: string;
			age: number;
		};
	};

	type StringPaths = Paths<Project, {valueType: string}>;
	//=> 'title' | `tags.${number}` | 'owner.name'

	type NumberPaths = Paths<Project, {valueType: number}>;
	//=> 'id' | 'scores.0' | 'scores.1' | 'owner.age'
	```

	@example
	```
	import type {Paths} from 'type-fest';

	// Reading an optional property can give `undefined`, so the matcher needs it.
	type A = Paths<{name?: string; age: number}, {valueType: string}>;
	//=> never

	type B = Paths<{name?: string; age: number}, {valueType: string | undefined}>;
	//=> 'name'

	// A union value is checked as a whole.
	type C = Paths<{value: string | number; name: string}, {valueType: string}>;
	//=> 'name'
	```
	*/
	valueType?: unknown;
};

type DefaultPathsOptions = {
	maxRecursionDepth: 5;
	maxCircularDepth: number;
	bracketNotation: false;
	leavesOnly: false;
	depth: number;
	recurseIntoArrays: true;
	requiredOnly: false;
	valueType: unknown;
};

/**
The types that `Paths` does not recurse into.
*/
type NonRecursivePathsType<Options extends Required<PathsOptions>> =
	| NonRecursiveType
	| Exclude<UnknownCollection, UnknownArray>
	| (Options['recurseIntoArrays'] extends false ? UnknownArray : never);

/**
The optional keys of the given object, which `Paths` leaves out with `requiredOnly`.
*/
type KeysToSkip<T extends object, Options extends Required<PathsOptions>> = Options['requiredOnly'] extends true ? OptionalKeysOf<T> : never;

/**
Whether every key of the given object, or every element of the given tuple, is optional. Symbol keys are ignored, because `Paths` leaves them out.
*/
type HasOnlyOptionalKeys<Value> = Value extends UnknownArray
	? number extends Value['length'] // A non-tuple array or a tuple with a rest element has an index that is not optional.
		? false
		: [] extends Value
			? true
			: false
	: Value extends object
		? IsNever<Exclude<keyof Value & (string | number), OptionalKeysOf<Value>>>
		: false;

/**
Generate a union of all possible paths to properties in the given object.

It also works with arrays.

Use-case: You want a type-safe way to access deeply nested properties in an object.

Note: With a `string` index signature at the top level, the result is `string`, because TypeScript merges the other paths, like `` `${string}.a` ``, into `string`. Use {@link PathsOptions.leavesOnly | `leavesOnly`} or {@link PathsOptions.depth | `depth`} to get the nested paths.

Note: A key that contains a dot gives a path that reads like a nested path, because every `.` separates two keys. `Paths<{'a.b': {c: number}}>` includes `'a.b.c'`, which `Get`, `PickDeep`, and the other path types read as `a` → `b` → `c`. To read such a key, use the array form of `Get`: `Get<{'a.b': {c: number}}, ['a.b', 'c']>` is `number`.

Note: In a generic function, use concrete option values before relying on bracket notation. While any option is generic, TypeScript can read the result as if the default options were used.

@example
```
import type {Paths} from 'type-fest';

type Project = {
	filename: string;
	listA: string[];
	listB: [{filename: string}];
	folder: {
		subfolder: {
			filename: string;
		};
	};
};

type ProjectPaths = Paths<Project>;
//=> 'filename' | 'listA' | 'listB' | 'folder' | `listA.${number}` | 'listB.0' | 'listB.0.filename' | 'folder.subfolder' | 'folder.subfolder.filename'

declare function open<Path extends ProjectPaths>(path: Path): void;

open('filename'); // Pass
open('folder.subfolder'); // Pass
open('folder.subfolder.filename'); // Pass
// @ts-expect-error
open('foo'); // TypeError

// Also works with arrays
open('listA.1'); // Pass
open('listB.0'); // Pass
// @ts-expect-error
open('listB.1'); // TypeError. Because listB only has one element.
```

@example
```
import type {Paths} from 'type-fest';

type Users = Record<string, {name: string}>;

type AllPaths = Paths<Users>;
//=> string

type LeafPaths = Paths<Users, {leavesOnly: true}>;
//=> `${string}.name`
```

@category Object
@category Array
*/
export type Paths<T, Options extends PathsOptions = {}> =
	// Resolving the options in a conditional type defers it for generic options, so declaration emit keeps this alias instead of expanding the result.
	ApplyDefaultOptions<PathsOptions, DefaultPathsOptions, Options> extends infer ResolvedOptions extends Required<PathsOptions>
		? _Paths<T, ResolvedOptions>
		: never;

type _Paths<T, Options extends Required<PathsOptions>, CurrentDepth extends number = 0, Seen extends unknown[] = []> =
	T extends NonRecursivePathsType<Options>
		? never
		: IsAny<T> extends true
			? never
			: T extends object
				// Numeric enum members also accept `number`, so compare printed values to recognize finite limits.
				? `${number}` extends `${Options['maxCircularDepth']}`
					// No limit, so skip tracking the seen types, which would prevent TypeScript from reusing instantiations
					? InternalPaths<T, Options, CurrentDepth, Seen, KeysToSkip<T, Options>>
					: GreaterThan<CountExactInArray<Seen, T>, Options['maxCircularDepth']> extends true // Limit the depth of circular references
						? never
						: InternalPaths<T, Options, CurrentDepth, [...Seen, T], KeysToSkip<T, Options>>
				: never;

// The key map removes optional modifiers from the generated paths, while each value is read from its own required property.
type InternalPaths<T, Options extends Required<PathsOptions>, CurrentDepth extends number, Seen extends unknown[], SkippedKey> =
	{[Key in keyof T]-?: Key extends SkippedKey ? never : Key extends string | number // Leave out the keys in `SkippedKey`, and limit `Key` to `string | number`
		? (
			And<Options['bracketNotation'], IsNumberLike<Key>> extends true
				? `[${Key}]`
				: CurrentDepth extends 0
					// Return both `Key` and `KeyToString<Key>` because for number keys, like `1`, both `1` and `'1'` are valid keys.
					? Key | KeyToString<Key>
					: `.${Key}`
		) extends infer TransformedKey extends string | number
			? ((Options['leavesOnly'] extends true
				? Options['maxRecursionDepth'] extends CurrentDepth
					? TransformedKey
					: IsNever<PathValue<T, Key>> extends true
						? TransformedKey
						: PathValue<T, Key> extends infer Value // For distributing the declared property value
							? (Value extends readonly [] | NonRecursivePathsType<Options>
								? TransformedKey
								: IsNever<keyof Value & (string | number)> extends true // Check for empty object & `unknown`, because `keyof unknown` is `never`. Symbol keys are ignored, because they have no paths.
									? TransformedKey
									: (Options['requiredOnly'] extends true ? HasOnlyOptionalKeys<Value> : false) extends true // With `requiredOnly`, a value whose keys are all optional has no paths, so it counts as a leaf like an empty object.
										? TransformedKey
										// Like `_Paths`, skip circular checks when there is no limit and `Seen` is not tracked.
										: `${number}` extends `${Options['maxCircularDepth']}`
											? never
											: GreaterThan<CountExactInArray<Seen, Value>, Options['maxCircularDepth']> extends true // The path terminates at the circular reference limit, just like it does at `maxRecursionDepth`.
												? TransformedKey
												: never)
							: never // Should never happen
				: TransformedKey
			) extends infer _TransformedKey
				// If `depth` is provided, the condition becomes truthy only when it matches `CurrentDepth`.
				// Otherwise, since `depth` defaults to `number`, the condition is always truthy, returning paths at all depths.
				? CurrentDepth extends Options['depth']
					// The value is read as a property, so an optional key carries its `undefined`, like `ConditionalKeys`.
					// The default matcher accepts every value. This branch is required, not just faster: reading `T[Key]` for a generic `T` makes the result irreducible, which breaks constraints like `ParsePath<Paths<T>>`.
					? unknown extends Options['valueType']
						? _TransformedKey
						// An `any` value matches every matcher, like with `ConditionalKeys`.
						: ExtendsStrict<T[Key], Options['valueType'], {strictAny: false}> extends true
							? _TransformedKey
							: never
					: never
				: never)
			// Recursively generate paths for the current key
			| (GreaterThan<Options['maxRecursionDepth'], CurrentDepth> extends true // Limit the depth to prevent infinite recursion
				? `${TransformedKey}${_Paths<PathValue<T, Key>, Options, Sum<CurrentDepth, 1>, Seen> & (string | number)}`
				: never)
			: never
		: never
	}[keyof T & (T extends UnknownArray ? number : unknown)];

// Reading one required property removes implicit absence without transforming array elements.
type PathValue<Type, Key extends keyof Type> = Required<Pick<Type, Key>>[Key];

export {};
