import type {ApplyDefaultOptions} from './apply-default-options.d.ts';
import type {IsEqualOrExtend} from './internal/array.d.ts';
import type {IsAnyOrNever} from './internal/type.d.ts';
import type {Not} from './not.d.ts';
import type {UnknownArray} from './unknown-array.d.ts';
import type {IsNever} from './is-never.d.ts';

/**
{@link Includes `Includes`} Options.
*/
export type IncludesOptions = {
	/**
	Compare the item and the elements member by member, by assignability, instead of comparing them exactly.

	With it, `Includes<[1 | 2], 1, {distributeItem: true}>` is `boolean`, because the element may be `1`, and `Includes<[1, 2], 1 | 2, {distributeItem: true}>` is `true`, because both members are included.

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

	type T1 = Includes<[1, 2, 3], 1 | 4, {distributeItem: false}>;
	//=> false

	type T2 = Includes<[1, 2, 3], 1 | 4, {distributeItem: true}>;
	//=> boolean

	type T3 = Includes<[1 | 2, 3], 1, {distributeItem: false}>;
	//=> false

	type T4 = Includes<[1 | 2, 3], 1, {distributeItem: true}>;
	//=> boolean

	type T5 = Includes<[1, 2, 3], 1 | 2, {distributeItem: true}>;
	//=> true

	type T6 = Includes<[1, 2, 3], number, {distributeItem: true}>;
	//=> boolean

	type T7 = Includes<[string, 1], 'a', {distributeItem: true}>;
	//=> boolean
	```

	@default false
	*/
	distributeItem?: boolean;
};

type DefaultIncludesOptions = {
	distributeItem: false;
};

/**
Returns a boolean for whether the given array includes the given item.

This can be useful if another type wants to make a decision based on whether the array includes that item.

Distributes over unions of arrays. Returns `false` when the array itself is `any` or `never`.

Elements are compared exactly, so `Includes<[boolean], true>` is `false`. Use the `distributeItem` option to compare by assignability.

The result describes every array of the given type: `true` if each one includes the item, `boolean` if only some do, and `false` otherwise. Only some do when the item is only matched by an optional element, or by the element type of an array of unknown length, which can be empty. Use `true extends Includes<…>` to check whether the item may be included.

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

type T1 = Includes<[1, 2, ...Array<3>], 2>;
//=> true

type T2 = Includes<[1, 2, ...Array<3>], 0>;
//=> false

type T3 = Includes<[1, 2, ...Array<3>], 3>;
//=> boolean

type T4 = Includes<[1, 2, 3?], 3>;
//=> boolean

type T5 = Includes<[1, 3, 3?], 3>;
//=> true

type T6 = Includes<string[], string>;
//=> boolean

type T7 = Includes<[1, 2, 3], 1 | 4, {distributeItem: true}>;
//=> boolean

type T8 = Includes<[string, number], 'a', {distributeItem: true}>;
//=> boolean
```

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

@see {@link IncludesOptions `IncludesOptions`}
@category Array
*/
// An item that is only possibly present gives `boolean`, not `true`. This is intentional, so do not change it to count an optional element or an array of unknown length as including the item: `true` must mean that every array of the type includes the item, otherwise `Includes<…> extends true` would accept an array that does not. `true extends Includes<…>` covers the "may include" case. See https://github.com/sindresorhus/type-fest/pull/1252.
export type Includes<
	Array_ extends UnknownArray, Item,
	Options extends IncludesOptions = {},
> =
	IsAnyOrNever<Array_> extends true ? false // An `any` or `never` array is not known to include the item
		// Keep inferred options so a constrained exact-comparison mode remains exact.
		: ApplyDefaultOptions<
			IncludesOptions,
			DefaultIncludesOptions,
			Options
		> extends infer ResolvedOptions extends Required<IncludesOptions>
			? (ResolvedOptions['distributeItem'] extends true ? Not<IsNever<Item>> : false) extends true
				? Item extends unknown // Distribute item
					? IncludesEach<Array_, Item, ResolvedOptions>
					: never
				: IncludesEach<Array_, Item, ResolvedOptions>
			: never;

/**
Checks each member of a union of arrays on its own, using indexed checks for fixed tuples and traversal for arrays with a rest element.
*/
type IncludesEach<Array_ extends UnknownArray, Item, Options extends Required<IncludesOptions>> =
	Array_ extends unknown // For distributing `Array_`
		? number extends [...Array_]['length']
			? _Includes<Array_, Item, Options>
			: IncludesFixedTuple<Array_, Item, Options>
		: never; // Should never happen

/**
Check fixed positions independently, using the existing matcher on one-element tuples to preserve required and optional element inference. Keep possible matches separate from definite matches so a later definite match still decides the result.
*/
type IncludesFixedTuple<Array_ extends UnknownArray, Item, Options extends Required<IncludesOptions>> =
	true extends IncludesFixedTupleMatches<Array_, Item, Options>[number]
		? true
		: 'possible' extends IncludesFixedTupleMatches<Array_, Item, Options>[number] ? boolean : false;

/**
Keep each position's match state in a tuple, so a known match can decide the result even while other positions remain generic.
*/
type IncludesFixedTupleMatches<Array_ extends UnknownArray, Item, Options extends Required<IncludesOptions>> = {
	[Key in keyof Array_]-?: _Includes<
		{} extends Pick<Array_, Key>
			? Pick<Array_, Key> extends {[Position in Key]?: infer Element} ? [Element?] : never
			: [Array_[Key]],
		Item,
		Options
	> extends infer Matches
		? [Matches] extends [true]
			? true
			: true extends Matches ? 'possible' : false
		: never;
};

/**
`Found` is `boolean` once an element may be the item, so a possible match is remembered while the search continues for a certain one. Carrying it along, instead of returning `true | <rest of the search>`, keeps the recursion in tail position, so long tuples do not hit the instantiation depth limit.
*/
type _Includes<
	Array_ extends UnknownArray, Item,
	Options extends Required<IncludesOptions>,
	Found extends boolean = false,
> =
	keyof Array_ & '0' extends never
		// The array starts with a rest element, or has no elements, so its fixed elements are searched from the end.
		? Array_ extends readonly [...infer Rest, infer Last]
			? IsEqualOrExtend<Last, Item, Options['distributeItem']> extends infer Result
				? [Result] extends [true]
					? true
					: _Includes<Rest, Item, Options, Found | (true extends Result ? boolean : false)>
				: never // Should never happen
			// Only the rest element is left, which can hold any number of elements, including none, so a match is only possible.
			: Array_ extends readonly []
				? Found // No certain match, so only a remembered possible match is left
				: Found | (true extends IsEqualOrExtend<Array_[number], Item, Options['distributeItem']> ? boolean : false)
		// The array starts with a fixed element, which can be optional, so the elements are searched from the start.
		: Array_ extends readonly [(infer First)?, ...infer Rest]
			// Optional inference preserves explicitly declared `undefined` without adding the missing-position value. A required element is read with `Array_[0]`, because inference from a tuple intersection, such as a tuple with metadata, widens `First` to every element. An indexed value without `undefined` can only be a required element, so the property check, which is slow for long tuples, is only needed when it includes `undefined`.
			? IsEqualOrExtend<undefined extends Array_[0] ? Array_ extends {0: unknown} ? Array_[0] : First : Array_[0], Item, Options['distributeItem']> extends infer Result
				? [Result] extends [true]
					// An optional element can be absent, so it is only a possible match. Its value excludes implicit `undefined`, so `Includes<[1?], undefined>` is `false`.
					// Check the property directly because an intersection can make an optional tuple position required.
					? Array_ extends {0: unknown}
						? true
						: _Includes<Rest, Item, Options, boolean>
					: _Includes<Rest, Item, Options, Found | (true extends Result ? boolean : false)>
				: never // Should never happen
			: never; // Should never happen

export {};
