TypeCombinator.php

<?php declare(strict_types = 1);

namespace PHPStan\Type;

use PHPStan\TrinaryLogic;
use PHPStan\Turbo\ShadowedByTurboExtension;
use PHPStan\Turbo\TurboExtensionEnabler;
use PHPStan\Type\Accessory\AccessoryArrayListType;
use PHPStan\Type\Accessory\AccessoryDecimalIntegerStringType;
use PHPStan\Type\Accessory\AccessoryLowercaseStringType;
use PHPStan\Type\Accessory\AccessoryNonEmptyStringType;
use PHPStan\Type\Accessory\AccessoryNonFalsyStringType;
use PHPStan\Type\Accessory\AccessoryType;
use PHPStan\Type\Accessory\AccessoryUppercaseStringType;
use PHPStan\Type\Accessory\HasOffsetType;
use PHPStan\Type\Accessory\HasOffsetValueType;
use PHPStan\Type\Accessory\HasPropertyType;
use PHPStan\Type\Accessory\NonEmptyArrayType;
use PHPStan\Type\Accessory\OversizedArrayType;
use PHPStan\Type\Constant\ConstantArrayType;
use PHPStan\Type\Constant\ConstantArrayTypeBuilder;
use PHPStan\Type\Constant\ConstantBooleanType;
use PHPStan\Type\Constant\ConstantFloatType;
use PHPStan\Type\Constant\ConstantIntegerType;
use PHPStan\Type\Constant\ConstantStringType;
use PHPStan\Type\Generic\GenericClassStringType;
use PHPStan\Type\Generic\TemplateArrayType;
use PHPStan\Type\Generic\TemplateBenevolentUnionType;
use PHPStan\Type\Generic\TemplateMixedType;
use PHPStan\Type\Generic\TemplateType;
use PHPStan\Type\Generic\TemplateTypeFactory;
use PHPStan\Type\Generic\TemplateUnionType;
use PHPStan\Type\Generic\UnresolvedTemplateArgumentType;
use function array_fill;
use function array_filter;
use function array_key_exists;
use function array_key_first;
use function array_keys;
use function array_merge;
use function array_slice;
use function array_splice;
use function array_values;
use function count;
use function get_class;
use function implode;
use function in_array;
use function spl_object_id;
use function sprintf;
use function usort;
use const PHP_INT_MAX;
use const PHP_INT_MIN;

/**
 * @api
 */
#[ShadowedByTurboExtension(implementation: __DIR__ . '/../../turbo-ext/src/TypeCombinator.cpp')]
final class TypeCombinator
{

	private const KEEP_SEPARATE_ARRAYS_LIMIT = 4;

	/**
	 * Turned on by TurboExtensionEnabler when the native extension is active, so that
	 * union(), intersect() and remove() route through the memoizing TypeCombinatorCache.
	 * Without the extension the operations run exactly as they always have — the flag
	 * costs a property read, and nothing else changes.
	 */
	private static ?bool $cacheEnabled = null;

	/**
	 * Memoization hands back shared Type instances, and a Type lazily resolves a
	 * ClassReflection belonging to the container that created it — so the cache must
	 * not outlive its container.
	 */
	public static function clearCache(): void
	{
		if ((self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) === false) {
			return;
		}

		TypeCombinatorCache::clearCache();
	}

	public static function addNull(Type $type): Type
	{
		// asking the type itself is both cheaper than NullType::isSuperTypeOf()
		// (UnionType memoizes isNull(), isSubTypeOf() recomputes) and right for
		// `never`, of which null is a supertype without never containing it.
		if ($type->isNull()->no()) {
			return self::union($type, new NullType());
		}

		return $type;
	}

	public static function remove(Type $fromType, Type $typeToRemove): Type
	{
		if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
			return TypeCombinatorCache::remove($fromType, $typeToRemove);
		}

		return self::doRemove($fromType, $typeToRemove);
	}

	/**
	 * Whether removing the union's members all at once gives what removing them
	 * one at a time would: true when the subtraction is a set difference, so no
	 * order of removals can sharpen the result.
	 *
	 * Everywhere else the members have to come off one at a time - removing one
	 * can narrow the type so that removing the next achieves more.
	 */
	private static function canRemoveUnionAtOnce(Type $fromType): bool
	{
		// A sealed hierarchy - an enum, or a hierarchy an
		// AllowedSubTypesClassReflectionExtension seals - subtracts by dropping
		// allowed subtypes, and which ones are dropped does not depend on order.
		$classReflections = $fromType->getObjectClassReflections();
		if (count($classReflections) === 1 && $classReflections[0]->getAllowedSubTypes() !== null) {
			return true;
		}

		// A union removes the whole thing from each of its members, and each of
		// those removals weighs this same question again - so a member that needs
		// the removals one at a time still gets them that way.
		return $fromType instanceof UnionType;
	}

	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
	public static function doRemove(Type $fromType, Type $typeToRemove): Type
	{
		if ($typeToRemove instanceof UnionType) {
			// Removing the members one at a time is what keeps the result precise:
			// removing one can narrow the type so that removing the next achieves
			// more. A sealed hierarchy is the exception - there the subtraction is
			// a set difference over the allowed subtypes, so the order the members
			// come off cannot matter, and peeling them would rebuild the whole
			// subtraction once per member (removing an enum from its own type then
			// costs O(cases^2)).
			if (self::canRemoveUnionAtOnce($fromType)) {
				$removed = $fromType->tryRemove($typeToRemove);
				if ($removed !== null) {
					return $removed;
				}
			}

			foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
				$fromType = self::remove($fromType, $unionTypeToRemove);
				if ($fromType instanceof NeverType) {
					// there is nothing left to remove from
					break;
				}
			}
			return $fromType;
		}

		$isSuperType = $typeToRemove->isSuperTypeOf($fromType);
		if ($isSuperType->yes()) {
			return new NeverType();
		}
		if ($isSuperType->no()) {
			return $fromType;
		}

		if ($typeToRemove instanceof MixedType) {
			$typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
			if ($typeToRemoveSubtractedType !== null) {
				return self::intersect($fromType, $typeToRemoveSubtractedType);
			}
		}

		$removed = $fromType->tryRemove($typeToRemove);
		if ($removed !== null) {
			return $removed;
		}

		$fromFiniteTypes = $fromType->getFiniteTypes();
		if (count($fromFiniteTypes) > 0) {
			$finiteTypesToRemove = $typeToRemove->getFiniteTypes();
			if (count($finiteTypesToRemove) > 0) {
				$result = [];
				foreach ($fromFiniteTypes as $finiteType) {
					foreach ($finiteTypesToRemove as $finiteTypeToRemove) {
						if ($finiteType->equals($finiteTypeToRemove)) {
							continue 2;
						}
					}

					$result[] = $finiteType;
				}

				if (count($result) === count($fromFiniteTypes)) {
					return $fromType;
				}

				if (count($result) === 0) {
					return new NeverType();
				}

				if (count($result) === 1) {
					return $result[0];
				}

				return new UnionType($result);
			}
		}

		return $fromType;
	}

	public static function removeNull(Type $type): Type
	{
		if (self::containsNull($type)) {
			return self::remove($type, new NullType());
		}

		return $type;
	}

	public static function containsNull(Type $type): bool
	{
		if ($type instanceof UnionType) {
			foreach ($type->getTypes() as $innerType) {
				if ($innerType->isNull()->yes()) {
					return true;
				}
			}

			return false;
		}

		return $type instanceof NullType;
	}

	public static function union(Type ...$types): Type
	{
		if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
			return TypeCombinatorCache::union(...$types);
		}

		return self::doUnion(...$types);
	}

	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
	public static function doUnion(Type ...$types): Type
	{
		$typesCount = count($types);
		if ($typesCount === 0) {
			return new NeverType();
		}

		// Fast path for single non-union type
		if ($typesCount === 1) {
			$singleType = $types[0];
			if (!$singleType instanceof UnionType && !$singleType->isArray()->yes()) {
				return $singleType;
			}
		}

		// Fast path for common 2-type cases
		if ($typesCount === 2) {
			$a = $types[0];
			$b = $types[1];

			// union(never, X) = X and union(X, never) = X
			if ($a instanceof NeverType && !$a->isExplicit()) {
				return $b;
			}
			if ($b instanceof NeverType && !$b->isExplicit()) {
				return $a;
			}

			// union(mixed, X) = mixed (non-explicit, non-template, no subtracted)
			if ($a instanceof MixedType && !$a->isExplicitMixed() && !$a instanceof TemplateMixedType && $a->getSubtractedType() === null) {
				return $a;
			}
			if ($b instanceof MixedType && !$b->isExplicitMixed() && !$b instanceof TemplateMixedType && $b->getSubtractedType() === null) {
				return $b;
			}

			// union(X, X) = X — for equal array operands, not just identical
			// ones. For arrays the general path below is not a no-op on a pair
			// that already denotes a single type: it rebuilds them from
			// ArrayType::getIterableKeyType(), which coerces a subtracted key
			// type down to the plain array-key union, so `array<mixed~'User',
			// mixed>` unioned with an equal instance came back as plain
			// `array`. Whether the two operands happen to be the same object
			// must not decide the result.
			//
			// Non-array operands keep taking the general path. It is lossless
			// for them, and it has to stay in charge because `equals()` is
			// weaker than interchangeability for some types: a benevolent
			// `(int|string)` equals a plain `int|string` and `Foo=final` equals
			// `Foo`, and there the general path deliberately yields the wider
			// operand rather than whichever one was passed first.
			if ($a === $b || ($a->equals($b) && $a->isArray()->yes())) {
				return $a;
			}
		}

		// A member passed more than once contributes nothing; dropping the
		// repeats up front keeps the pairwise comparison below from paying for
		// them (array_values() of a shape unions the same value type per slot).
		if ($typesCount > 2) {
			$seenTypes = [];
			$uniqueTypes = [];
			foreach ($types as $type) {
				$typeId = spl_object_id($type);
				if (isset($seenTypes[$typeId])) {
					continue;
				}
				$seenTypes[$typeId] = true;
				$uniqueTypes[] = $type;
			}
			if (count($uniqueTypes) === 1) {
				return $uniqueTypes[0];
			}
			if (count($uniqueTypes) === 2) {
				return self::union($uniqueTypes[0], $uniqueTypes[1]);
			}
			$types = $uniqueTypes;
		}

		$alreadyNormalized = [];
		$alreadyNormalizedCounter = 0;

		$benevolentTypes = [];
		$neverCount = 0;
		$markers = [];
		// transform A | (B | C) to A | B | C - in one pass, a union's members are
		// never unions, implicit never or implicit mixed themselves
		$flattenedTypes = [];
		foreach ($types as $type) {
			if (
				$type instanceof MixedType
				&& !$type->isExplicitMixed()
				&& !$type instanceof TemplateMixedType
				&& $type->getSubtractedType() === null
			) {
				return $type;
			}
			if ($type instanceof UnresolvedTemplateArgumentType && !$type->isClosureSignature()) {
				$markers = self::addMarker($markers, $type);
				continue;
			}
			if ($type instanceof NeverType && !$type->isExplicit()) {
				$neverCount++;
				$flattenedTypes[] = $type;
				continue;
			}
			if ($type instanceof BenevolentUnionType) {
				if ($type instanceof TemplateType) {
					$flattenedTypes[] = $type;
					continue;
				}
				foreach ($type->getTypes() as $benevolentInnerType) {
					$benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
					$flattenedTypes[] = $benevolentInnerType;
				}
				continue;
			}
			if (!($type instanceof UnionType) || $type instanceof TemplateType) {
				$flattenedTypes[] = $type;
				continue;
			}

			$typesInner = $type->getTypes();
			$alreadyNormalized[$alreadyNormalizedCounter] = $typesInner;
			$alreadyNormalizedCounter++;
			foreach ($typesInner as $innerType) {
				if ($innerType instanceof UnresolvedTemplateArgumentType && !$innerType->isClosureSignature()) {
					$markers = self::addMarker($markers, $innerType);
					continue;
				}
				$flattenedTypes[] = $innerType;
			}
		}
		if ($markers !== []) {
			return self::unionWithMarkers(self::union(...$flattenedTypes), $markers);
		}
		$types = $flattenedTypes;
		$typesCount = count($types);

		// Bulk-remove implicit NeverTypes (skipped during the loop above)
		if ($neverCount > 0) {
			if ($neverCount === $typesCount) {
				return new NeverType();
			}

			$filtered = [];
			for ($i = 0; $i < $typesCount; $i++) {
				if ($types[$i] instanceof NeverType && !$types[$i]->isExplicit()) {
					continue;
				}
				$filtered[] = $types[$i];
			}
			$types = $filtered;
			$typesCount = count($types);

			if ($typesCount === 0) {
				return new NeverType();
			}
			if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
				return $types[0];
			}
			if ($typesCount === 2) {
				return self::union($types[0], $types[1]);
			}
		}

		if ($typesCount === 0) {
			return new NeverType();
		}

		if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
			return $types[0];
		}

		$arrayTypes = [];
		$scalarTypes = [];
		$hasGenericScalarTypes = [];
		$enumCaseTypes = [];
		$integerRangeTypes = [];
		for ($i = 0; $i < $typesCount; $i++) {
			if ($types[$i]->isConstantScalarValue()->yes()) {
				$type = $types[$i];
				$scalarTypes[get_class($type)][$type->describe(VerbosityLevel::cache())] = $type;
				unset($types[$i]);
				continue;
			}

			// only a type containing every value of the scalar (not T of int, 1&T)
			// absorbs all the constants of that scalar
			if ($types[$i]->isBoolean()->yes()) {
				if ($types[$i]->isSuperTypeOf(new BooleanType())->yes()) {
					$hasGenericScalarTypes[ConstantBooleanType::class] = true;
				}
			} elseif ($types[$i]->isFloat()->yes()) {
				if ($types[$i]->isSuperTypeOf(new FloatType())->yes()) {
					$hasGenericScalarTypes[ConstantFloatType::class] = true;
				}
			} elseif ($types[$i]->isInteger()->yes() && !$types[$i] instanceof IntegerRangeType) {
				if ($types[$i]->isSuperTypeOf(new IntegerType())->yes()) {
					$hasGenericScalarTypes[ConstantIntegerType::class] = true;
				}
			} elseif ($types[$i]->isString()->yes() && $types[$i]->isClassString()->no() && TypeUtils::getAccessoryTypes($types[$i]) === []) {
				$hasGenericScalarTypes[ConstantStringType::class] = true;
			} else {
				$enumCase = $types[$i]->getEnumCaseObject();
				if ($enumCase !== null) {
					$enumCaseTypes[$types[$i]->describe(VerbosityLevel::cache())] = $types[$i];

					unset($types[$i]);
					continue;
				}
			}

			if ($types[$i] instanceof IntegerRangeType) {
				$integerRangeTypes[] = $types[$i];
				unset($types[$i]);

				continue;
			}

			if (!$types[$i]->isArray()->yes()) {
				continue;
			}

			$arrayTypes[] = $types[$i];
			unset($types[$i]);
		}

		$enumCaseTypes = array_values($enumCaseTypes);
		usort(
			$integerRangeTypes,
			static fn (IntegerRangeType $a, IntegerRangeType $b): int => ($a->getMin() ?? PHP_INT_MIN) <=> ($b->getMin() ?? PHP_INT_MIN)
				?: ($a->getMax() ?? PHP_INT_MAX) <=> ($b->getMax() ?? PHP_INT_MAX),
		);
		// array_merge() hands the first array back as it is when the second one
		// is empty, so the keys the bucketing above unset must be renumbered here
		$types = array_merge(array_values($types), $integerRangeTypes);
		$typesCount = count($types);

		if (isset($scalarTypes[IntersectionType::class])) {
			$scalarTypes[IntersectionType::class] = self::reduceRefinedConstantScalars($scalarTypes[IntersectionType::class], $scalarTypes);
		}

		foreach ($scalarTypes as $classType => $scalarTypeItems) {
			if (isset($hasGenericScalarTypes[$classType])) {
				unset($scalarTypes[$classType]);
				continue;
			}
			if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
				$types[] = new BooleanType();
				$typesCount++;
				unset($scalarTypes[$classType]);
				continue;
			}

			$scalarTypeItems = array_values($scalarTypeItems);
			$scalarTypeItemsCount = count($scalarTypeItems);
			for ($i = 0; $i < $typesCount; $i++) {
				for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
					$compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
					if ($compareResult === null) {
						continue;
					}

					[$a, $b] = $compareResult;
					if ($a !== null) {
						$types[$i] = $a;
						array_splice($scalarTypeItems, $j, 1);
						$scalarTypeItemsCount--;
						$j = -1;
						continue 1;
					}
					if ($b !== null) {
						$scalarTypeItems[$j] = $b;
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}
				}
			}

			$scalarTypes[$classType] = $scalarTypeItems;
		}

		if (count($types) > 16) {
			$newTypes = [];
			foreach ($types as $type) {
				$newTypes[$type->describe(VerbosityLevel::cache())] = $type;
			}
			$types = array_values($newTypes);
		}

		$types = array_merge(
			$types,
			self::processArrayTypes($arrayTypes),
		);
		$typesCount = count($types);

		// transform A | A to A
		// transform A | never to A
		for ($i = 0; $i < $typesCount; $i++) {
			for ($j = $i + 1; $j < $typesCount; $j++) {
				if (self::isAlreadyNormalized($alreadyNormalized, $types[$i], $types[$j])) {
					continue;
				}
				$compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
				if ($compareResult === null) {
					continue;
				}

				[$a, $b] = $compareResult;
				if ($a !== null) {
					$types[$i] = $a;
					array_splice($types, $j--, 1);
					$typesCount--;
					continue 1;
				}
				if ($b !== null) {
					$types[$j] = $b;
					array_splice($types, $i--, 1);
					$typesCount--;
					continue 2;
				}
			}
		}

		$enumCasesCount = count($enumCaseTypes);
		for ($i = 0; $i < $typesCount; $i++) {
			for ($j = 0; $j < $enumCasesCount; $j++) {
				$compareResult = self::compareTypesInUnion($types[$i], $enumCaseTypes[$j]);
				if ($compareResult === null) {
					continue;
				}

				[$a, $b] = $compareResult;
				if ($a !== null) {
					$types[$i] = $a;
					array_splice($enumCaseTypes, $j--, 1);
					$enumCasesCount--;
					continue 1;
				}
				if ($b !== null) {
					$enumCaseTypes[$j] = $b;
					array_splice($types, $i--, 1);
					$typesCount--;
					continue 2;
				}
			}
		}

		foreach ($enumCaseTypes as $enumCaseType) {
			$types[] = $enumCaseType;
			$typesCount++;
		}

		foreach ($scalarTypes as $scalarTypeItems) {
			foreach ($scalarTypeItems as $scalarType) {
				$types[] = $scalarType;
				$typesCount++;
			}
		}

		if ($typesCount === 0) {
			return new NeverType();
		}
		if ($typesCount === 1) {
			return $types[0];
		}

		if ($benevolentTypes !== []) {
			$tempTypes = $types;
			foreach ($tempTypes as $i => $type) {
				if (!isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
					break;
				}

				unset($tempTypes[$i]);
			}

			if ($tempTypes === []) {
				return new BenevolentUnionType(array_values($types), true);
			}
		}

		return new UnionType(array_values($types), true);
	}

	/**
	 * An unresolved template argument is a variable of its site, not the type it
	 * currently stands for: unresolved(int) from two different sites are two
	 * variables, and neither int nor the other variable absorbs it. Only the same
	 * variable merges - into the wider of the two inferred types.
	 *
	 * @param array<string, UnresolvedTemplateArgumentType> $markers
	 * @return array<string, UnresolvedTemplateArgumentType>
	 */
	private static function addMarker(array $markers, UnresolvedTemplateArgumentType $marker): array
	{
		$key = spl_object_id($marker->getSite()) . '#' . $marker->getTemplateName();
		$existing = $markers[$key] ?? null;
		if ($existing === null || $existing === $marker) {
			$markers[$key] = $marker;
			return $markers;
		}

		$existingInitial = $existing->getInitialType();
		$initial = $marker->getInitialType();
		if ($existingInitial === null || $initial === null) {
			// nothing inferred stands for the template's default or bound
			$markers[$key] = $existingInitial === null ? $existing : $marker;
			return $markers;
		}

		$markers[$key] = $existing->withInitialType(self::union($existingInitial, $initial));

		return $markers;
	}

	/**
	 * @param array<string, UnresolvedTemplateArgumentType> $markers
	 */
	private static function unionWithMarkers(Type $rest, array $markers): Type
	{
		if ($rest instanceof MixedType && !$rest instanceof TemplateMixedType && $rest->getSubtractedType() === null) {
			return $rest;
		}

		if ($rest instanceof NeverType) {
			$members = [];
		} elseif ($rest instanceof UnionType && !$rest instanceof TemplateType) {
			$members = $rest->getTypes();
		} else {
			$members = [$rest];
		}
		foreach ($markers as $marker) {
			$members[] = $marker;
		}
		if (count($members) === 1) {
			return $members[0];
		}
		if ($rest instanceof BenevolentUnionType && !$rest instanceof TemplateType) {
			return new BenevolentUnionType($members, true);
		}

		return new UnionType($members, true);
	}

	/**
	 * @param array<int, Type[]> $alreadyNormalized
	 */
	private static function isAlreadyNormalized(array $alreadyNormalized, Type $a, Type $b): bool
	{
		foreach ($alreadyNormalized as $normalizedTypes) {
			foreach ($normalizedTypes as $i => $normalizedType) {
				if ($normalizedType !== $a) {
					continue;
				}

				foreach ($normalizedTypes as $j => $anotherNormalizedType) {
					if ($i === $j) {
						continue;
					}
					if ($anotherNormalizedType === $b) {
						return true;
					}
				}
			}
		}

		return false;
	}

	/**
	 * Scalar buckets are compared only against the non-scalar union members, which
	 * is correct for plain constants (distinct values are disjoint) but not for
	 * constants refined by another type ('Foo'&hasMethod(bar)). Those are absorbed
	 * here by the plain constant of the same value, or by a less refined
	 * intersection of the same value. Values never need to be compared across.
	 *
	 * @param array<string, Type> $intersections
	 * @param array<string, array<string, Type>> $scalarTypes
	 * @return array<string, Type>
	 */
	private static function reduceRefinedConstantScalars(array $intersections, array $scalarTypes): array
	{
		$byValue = [];
		foreach ($intersections as $key => $intersection) {
			$constants = $intersection->getConstantScalarTypes();
			if (count($constants) !== 1) {
				continue;
			}
			$valueKey = $constants[0]->describe(VerbosityLevel::cache());
			$plain = $scalarTypes[get_class($constants[0])][$valueKey] ?? null;
			if ($plain !== null && $plain->isSuperTypeOf($intersection)->yes()) {
				unset($intersections[$key]);
				continue;
			}
			$byValue[get_class($constants[0])][$valueKey][] = $key;
		}

		foreach ($byValue as $valueKeys) {
			foreach ($valueKeys as $keys) {
				$keysCount = count($keys);
				for ($i = 0; $i < $keysCount; $i++) {
					for ($j = 0; $j < $keysCount; $j++) {
						if ($i === $j || !isset($intersections[$keys[$i]], $intersections[$keys[$j]])) {
							continue;
						}
						if (!$intersections[$keys[$i]]->isSuperTypeOf($intersections[$keys[$j]])->yes()) {
							continue;
						}
						unset($intersections[$keys[$j]]);
					}
				}
			}
		}

		return $intersections;
	}

	/**
	 * @return array{Type, null}|array{null, Type}|null
	 */
	private static function compareTypesInUnion(Type $a, Type $b): ?array
	{
		if ($a instanceof IntegerRangeType) {
			$type = $a->tryUnion($b);
			if ($type !== null) {
				$a = $type;
				return [$a, null];
			}
		}
		if ($b instanceof IntegerRangeType) {
			$type = $b->tryUnion($a);
			if ($type !== null) {
				$b = $type;
				return [null, $b];
			}
		}
		if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
			return null;
		}
		if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
			if ($a->getOffsetType()->equals($b->getOffsetType())) {
				return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
			}
		}
		if ($a instanceof IntersectionType && $b instanceof IntersectionType) {
			$merged = self::mergeIntersectionsForUnion($a, $b);
			if ($merged !== null) {
				return [$merged, null];
			}
		}
		if ($a->isConstantArray()->yes() && $b->isConstantArray()->yes()) {
			return null;
		}

		// simplify string[] | int[] to (string|int)[]
		if ($a instanceof IterableType && $b instanceof IterableType) {
			return [
				new IterableType(
					self::union($a->getIterableKeyType(), $b->getIterableKeyType()),
					self::union($a->getIterableValueType(), $b->getIterableValueType()),
				),
				null,
			];
		}

		if ($a instanceof SubtractableType) {
			$typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
			if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
				$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
			} else {
				$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
			}
			if ($isSuperType->yes()) {
				$a = self::intersectWithSubtractedType($a, $b);
				return [$a, null];
			}
		}

		if ($b instanceof SubtractableType) {
			$typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
			if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
				$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
			} else {
				$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
			}
			if ($isSuperType->yes()) {
				$b = self::intersectWithSubtractedType($b, $a);
				return [null, $b];
			}
		}

		if ($b->isSuperTypeOf($a)->yes()) {
			return [null, $b];
		}

		if ($a->isSuperTypeOf($b)->yes()) {
			return [$a, null];
		}

		if (
			$a instanceof ConstantStringType
		) {
			if ($a->getValue() === '') {
				$description = $b->describe(VerbosityLevel::value());
				if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
					return [null, self::intersect(
						new StringType(),
						...self::getAccessoryCaseStringTypes($b),
					)];
				}
			}

			if ($a->getValue() === '0') {
				$nonEmpty = self::downgradeNonFalsyStringToNonEmpty($b);
				if ($nonEmpty !== null) {
					return [null, $nonEmpty];
				}
			}
		}

		if (
			$b instanceof ConstantStringType
		) {
			if ($b->getValue() === '') {
				$description = $a->describe(VerbosityLevel::value());
				if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
					return [self::intersect(
						new StringType(),
						...self::getAccessoryCaseStringTypes($a),
					), null];
				}
			}

			if ($b->getValue() === '0') {
				$nonEmpty = self::downgradeNonFalsyStringToNonEmpty($a);
				if ($nonEmpty !== null) {
					return [$nonEmpty, null];
				}
			}
		}

		// numeric-string | non-decimal-int-string → string (preserving common accessories)
		// Works because decimal-int-string ⊂ numeric-string, so together they cover all strings
		if ($a->isString()->yes() && $b->isString()->yes()) {
			$decimalIntString = new IntersectionType([new StringType(), new AccessoryDecimalIntegerStringType()]);
			if ($b->isDecimalIntegerString()->no()) {
				$bBase = self::removeDecimalIntStringAccessory($b);
				if ($bBase->isSuperTypeOf($a)->yes() && $a->isSuperTypeOf($decimalIntString)->yes()) {
					return [null, $bBase];
				}
			}
			if ($a->isDecimalIntegerString()->no()) {
				$aBase = self::removeDecimalIntStringAccessory($a);
				if ($aBase->isSuperTypeOf($b)->yes() && $b->isSuperTypeOf($decimalIntString)->yes()) {
					return [$aBase, null];
				}
			}
		}

		return null;
	}

	/**
	 * @return list<Type>
	 */
	private static function getAccessoryCaseStringTypes(Type $type): array
	{
		$accessory = [];
		if ($type->isLowercaseString()->yes()) {
			$accessory[] = new AccessoryLowercaseStringType();
		}
		if ($type->isUppercaseString()->yes()) {
			$accessory[] = new AccessoryUppercaseStringType();
		}

		return $accessory;
	}

	/**
	 * Turns a non-falsy-string type into its non-empty-string counterpart by
	 * downgrading the non-falsy accessory while preserving every other accessory
	 * (numeric-string, decimal-int-string, lowercase-string, …). Used to simplify
	 * `'0' | non-falsy-string-X` back to `non-empty-string-X`, since `"0"` is the
	 * only value that separates the two. Returns null when $type is not a
	 * non-constant non-falsy-string built from an intersection.
	 */
	private static function downgradeNonFalsyStringToNonEmpty(Type $type): ?Type
	{
		if (!$type instanceof IntersectionType || $type->isNonFalsyString()->no()) {
			return null;
		}

		$newTypes = [];
		$found = false;
		foreach ($type->getTypes() as $innerType) {
			if ($innerType instanceof AccessoryNonFalsyStringType) {
				$found = true;
				continue;
			}

			$newTypes[] = $innerType;
		}

		if (!$found) {
			return null;
		}

		$withoutNonFalsy = self::intersect(...$newTypes);
		if ($withoutNonFalsy->isNonEmptyString()->yes()) {
			return $withoutNonFalsy;
		}

		return self::intersect($withoutNonFalsy, new AccessoryNonEmptyStringType());
	}

	private static function removeDecimalIntStringAccessory(Type $type): Type
	{
		if (!$type instanceof IntersectionType) {
			return $type;
		}

		return self::intersect(...array_filter(
			$type->getTypes(),
			static fn (Type $t): bool => !$t instanceof AccessoryDecimalIntegerStringType,
		));
	}

	private static function unionWithSubtractedType(
		Type $type,
		?Type $subtractedType,
	): Type
	{
		if ($subtractedType === null) {
			return $type;
		}

		if ($subtractedType instanceof SubtractableType) {
			$withoutSubtracted = $subtractedType->getTypeWithoutSubtractedType();
			if ($withoutSubtracted->isSuperTypeOf($type)->yes()) {
				$subtractedSubtractedType = $subtractedType->getSubtractedType();
				if ($subtractedSubtractedType === null) {
					return new NeverType();
				}

				return self::intersect($type, $subtractedSubtractedType);
			}
		}

		if ($type instanceof SubtractableType) {
			$subtractedType = $type->getSubtractedType() === null
				? $subtractedType
				: self::union($type->getSubtractedType(), $subtractedType);

			$subtractedType = self::intersect(
				$type->getTypeWithoutSubtractedType(),
				$subtractedType,
			);
			if ($subtractedType instanceof NeverType) {
				$subtractedType = null;
			}

			return $type->changeSubtractedType($subtractedType);
		}

		if ($subtractedType->isSuperTypeOf($type)->yes()) {
			return new NeverType();
		}

		return self::remove($type, $subtractedType);
	}

	private static function intersectWithSubtractedType(
		SubtractableType $a,
		Type $b,
	): Type
	{
		if ($a->getSubtractedType() === null || $b instanceof NeverType) {
			return $a;
		}

		if ($b instanceof IntersectionType) {
			$subtractableTypes = [];
			foreach ($b->getTypes() as $innerType) {
				if (!$innerType instanceof SubtractableType) {
					continue;
				}

				$subtractableTypes[] = $innerType;
			}

			if (count($subtractableTypes) === 0) {
				return $a->getTypeWithoutSubtractedType();
			}

			$subtractedTypes = [];
			foreach ($subtractableTypes as $subtractableType) {
				if ($subtractableType->getSubtractedType() === null) {
					continue;
				}

				$subtractedTypes[] = $subtractableType->getSubtractedType();
			}

			if (count($subtractedTypes) === 0) {
				return $a->getTypeWithoutSubtractedType();

			}

			$subtractedType = self::union(...$subtractedTypes);
		} else {
			$isBAlreadySubtracted = $a->getSubtractedType()->isSuperTypeOf($b);

			if ($isBAlreadySubtracted->no()) {
				return $a;
			} elseif ($isBAlreadySubtracted->yes()) {
				$subtractedType = self::remove($a->getSubtractedType(), $b);

				if (
					$subtractedType instanceof NeverType
					|| !$subtractedType->isSuperTypeOf($b)->no()
				) {
					$subtractedType = null;
				}

				return $a->changeSubtractedType($subtractedType);
			} elseif ($b instanceof SubtractableType) {
				$subtractedType = $b->getSubtractedType();
				if ($subtractedType === null) {
					return $a->getTypeWithoutSubtractedType();
				}
			} else {
				$subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
				if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
					return $a->getTypeWithoutSubtractedType();
				}
				$subtractedType = new MixedType(subtractedType: $b);
			}
		}

		$subtractedType = self::intersect(
			$a->getSubtractedType(),
			$subtractedType,
		);
		if ($subtractedType instanceof NeverType) {
			$subtractedType = null;
		}

		return $a->changeSubtractedType($subtractedType);
	}

	/**
	 * @param list<Type> $arrayTypes
	 * @return array{list<Type>, list<Type>} tuple of [arrays with accessory wrappers stripped, common accessory types]
	 */
	private static function processArrayAccessoryTypes(array $arrayTypes): array
	{
		$isIterableAtLeastOnce = [];
		$accessoryTypes = [];
		$strippedArrays = [];
		foreach ($arrayTypes as $i => $arrayType) {
			$isIterableAtLeastOnce[] = $arrayType->isIterableAtLeastOnce();

			if ($arrayType instanceof IntersectionType) {
				$nonAccessoryInner = [];
				$skipStrip = false;
				foreach ($arrayType->getTypes() as $innerType) {
					if ($innerType instanceof TemplateType) {
						$skipStrip = true;
						break;
					}
					if (!($innerType instanceof AccessoryType) && !($innerType instanceof CallableType)) {
						$nonAccessoryInner[] = $innerType;
						continue;
					}
					if ($innerType instanceof HasOffsetType) {
						$innerType = new HasOffsetValueType($innerType->getOffsetType(), $arrayType->getIterableValueType());
					}
					if ($innerType instanceof HasOffsetValueType) {
						$accessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][$i] = $innerType;
						continue;
					}

					$accessoryTypes[$innerType->describe(VerbosityLevel::cache())][$i] = $innerType;
				}
				$strippedArrays[] = $skipStrip || count($nonAccessoryInner) !== 1 ? $arrayType : $nonAccessoryInner[0];
			} else {
				$strippedArrays[] = $arrayType;
			}

			if (!$arrayType->isConstantArray()->yes()) {
				continue;
			}
			$constantArrays = $arrayType->getConstantArrays();

			foreach ($constantArrays as $constantArray) {
				if ($constantArray->isList()->yes()) {
					$list = new AccessoryArrayListType();
					$accessoryTypes[$list->describe(VerbosityLevel::cache())][$i] = $list;
				}

				if (!$constantArray->isIterableAtLeastOnce()->yes()) {
					continue;
				}

				$nonEmpty = new NonEmptyArrayType();
				$accessoryTypes[$nonEmpty->describe(VerbosityLevel::cache())][$i] = $nonEmpty;
			}
		}

		$commonAccessoryTypes = [];
		$arrayTypeCount = count($arrayTypes);
		foreach ($accessoryTypes as $accessoryType) {
			if (count($accessoryType) !== $arrayTypeCount) {
				$firstKey = array_key_first($accessoryType);
				if ($accessoryType[$firstKey] instanceof OversizedArrayType) {
					$commonAccessoryTypes[] = $accessoryType[$firstKey];
				}
				continue;
			}

			if ($accessoryType[0] instanceof HasOffsetValueType) {
				$commonAccessoryTypes[] = self::union(...$accessoryType);
				continue;
			}

			$commonAccessoryTypes[] = $accessoryType[0];
		}

		if (TrinaryLogic::createYes()->and(...$isIterableAtLeastOnce)->yes()) {
			$commonAccessoryTypes[] = new NonEmptyArrayType();
		}

		return [$strippedArrays, $commonAccessoryTypes];
	}

	/**
	 * @param Type[] $arrayTypes
	 */
	private static function findEmptyArrayNextToOversizedArray(array $arrayTypes): ?Type
	{
		if (count($arrayTypes) < 2) {
			return null;
		}

		$emptyArray = null;
		$hasOversizedArray = false;
		foreach ($arrayTypes as $arrayType) {
			if ($arrayType->isOversizedArray()->yes()) {
				$hasOversizedArray = true;
			} elseif ($emptyArray === null && $arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
				$emptyArray = $arrayType;
			}
		}

		return $hasOversizedArray ? $emptyArray : null;
	}

	/**
	 * @param list<Type> $arrayTypes
	 * @return Type[]
	 */
	private static function processArrayTypes(array $arrayTypes): array
	{
		if ($arrayTypes === []) {
			return [];
		}

		$emptyArray = self::findEmptyArrayNextToOversizedArray($arrayTypes);
		if ($emptyArray !== null) {
			// like reduceArrays() does when it generalizes to an oversized array:
			// folded into it, the empty array would be lost to the oversized
			// accessory, which accepts only arrays that hold something
			$otherArrayTypes = [];
			foreach ($arrayTypes as $arrayType) {
				if ($arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
					continue;
				}
				$otherArrayTypes[] = $arrayType;
			}

			return [$emptyArray, ...self::processArrayTypes($otherArrayTypes)];
		}

		[$strippedArrays, $accessoryTypes] = self::processArrayAccessoryTypes($arrayTypes);

		if (count($arrayTypes) === 1) {
			return [
				self::intersect(...$arrayTypes, ...$accessoryTypes),
			];
		}

		$keyTypesForGeneralArray = [];
		$valueTypesForGeneralArray = [];
		$generalArrayOccurred = false;
		$seenConstantKeyTypes = [];

		foreach ($arrayTypes as $arrayType) {
			$constantArrays = $arrayType->getConstantArrays();
			$isConstantArray = $constantArrays !== [];

			if (!$isConstantArray) {
				foreach ($arrayType->getArrays() as $type) {
					$keyTypesForGeneralArray[] = $type->getIterableKeyType();
					$valueTypesForGeneralArray[] = $type->getItemType();
					$generalArrayOccurred = true;
				}
				continue;
			}

			foreach ($constantArrays as $constantArray) {
				$valueTypes = $constantArray->getValueTypes();
				foreach ($constantArray->getKeyTypes() as $i => $keyType) {
					$valueTypesForGeneralArray[] = $valueTypes[$i];

					$keyTypeValue = $keyType->getValue();
					if (array_key_exists($keyTypeValue, $seenConstantKeyTypes)) {
						continue;
					}
					$seenConstantKeyTypes[$keyTypeValue] = true;
					$keyTypesForGeneralArray[] = $keyType;
				}
			}
		}

		if ($generalArrayOccurred) {
			$reducedArrayTypes = self::reduceArrays($arrayTypes, false);
			if (count($reducedArrayTypes) === 1) {
				return [self::intersect($reducedArrayTypes[0], ...$accessoryTypes)];
			}

			$hasEmptyConstantArray = false;
			foreach ($arrayTypes as $arrayType) {
				if ($arrayType->isIterableAtLeastOnce()->no() && $arrayType->isConstantArray()->yes()) {
					$hasEmptyConstantArray = true;
					break;
				}
			}

			// TMP WIP: run for everyone, not just bleedingEdge, so CI exercises the new path
			// Keep distinct array shapes (e.g. `list<int>|list<string>` rather than
			// `list<int|string>`), but reduce the result before returning so analysis-
			// emergent intermediate state (foreach over mixed[], deeply nested
			// ArrayDimFetch writes, sequential `if ($x !== null) $arr['x'] = $x;`) does
			// not blow up. `array{} | non-empty-array<X>` -> `array<X>` still goes to
			// the old collapse path.
			if (!$hasEmptyConstantArray) {
				// Dedupe using the stripped (accessory-free) describe as the key, but
				// keep the original (with accessories) as the value. This collapses
				// members that share an underlying shape but differ only in stacked
				// per-element accessories like hasOffsetValue (cf. the optional-
				// properties repro: 4 same-shape members differing only in stacked
				// hasOffsetValue accessories), while preserving per-member accessories
				// like list / non-empty when only one original has the shape. Two
				// originals of one shape that differ in their accessories collapse to
				// the stripped shape: keeping either of them would drop values of the
				// other, and the accessories they share are added back below.
				$deduped = [];
				foreach ($strippedArrays as $i => $stripped) {
					$key = $stripped->describe(VerbosityLevel::cache());
					if (!array_key_exists($key, $deduped)) {
						$deduped[$key] = $arrayTypes[$i];
						continue;
					}
					if ($deduped[$key]->equals($arrayTypes[$i])) {
						continue;
					}

					$deduped[$key] = $stripped;
				}
				$deduped = array_values($deduped);

				// Budget: when more distinct shapes remain than a small union would have,
				// they are almost certainly analysis-emergent rather than user-written;
				// fall through to the old collapse path to keep downstream tractable.
				// Mirrors optimizeConstantArrays() which generalizes once a similar
				// budget (256 constant value types) is exceeded.
				if (count($deduped) <= self::KEEP_SEPARATE_ARRAYS_LIMIT) {
					$results = [];
					foreach ($deduped as $arrayType) {
						$results[] = $accessoryTypes === []
							? $arrayType
							: self::intersect($arrayType, ...$accessoryTypes);
					}
					return $results;
				}
			}

			$templateArrayType = null;
			foreach ($arrayTypes as $arrayType) {
				if (!$arrayType instanceof TemplateArrayType) {
					$templateArrayType = null;
					break;
				}

				if ($templateArrayType !== null) {
					continue;
				}

				$templateArrayType = $arrayType;
			}

			$arrayType = new ArrayType(
				self::union(...$keyTypesForGeneralArray),
				self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
			);

			if ($templateArrayType !== null) {
				$arrayType = new TemplateArrayType(
					$templateArrayType->getScope(),
					$templateArrayType->getStrategy(),
					$templateArrayType->getVariance(),
					$templateArrayType->getName(),
					$arrayType,
					$templateArrayType->getDefault(),
				);
			}

			return [
				self::intersect($arrayType, ...$accessoryTypes),
			];
		}

		$reducedArrayTypes = self::optimizeConstantArrays(self::reduceArrays($arrayTypes, true));
		foreach ($reducedArrayTypes as $idx => $reducedArray) {
			$applied = $accessoryTypes;
			if ($reducedArray->isIterableAtLeastOnce()->no()) {
				// Empty arrays cannot satisfy non-empty / oversized constraints —
				// applying those accessories would produce a contradictory intersection
				// (e.g. `array{}&oversized-array`) that rejects the very value it
				// represents, breaking the super-type contract of the union.
				$applied = array_values(array_filter(
					$applied,
					static fn (Type $t): bool => !($t instanceof OversizedArrayType) && !($t instanceof NonEmptyArrayType),
				));
			}
			$reducedArrayTypes[$idx] = self::intersect($reducedArray, ...$applied);
		}
		return $reducedArrayTypes;
	}

	/**
	 * @param Type[] $types
	 * @return Type[]
	 */
	private static function optimizeConstantArrays(array $types): array
	{
		$constantArrayValuesCount = self::countConstantArrayValueTypes($types);

		if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
			return $types;
		}

		// Stage 1: collapse same-key-set ConstantArrayType variants per-position
		// before the (lossy) generalization below kicks in. Variants with the
		// same key signature mergeWith losslessly into a single shape whose
		// values at each position are the union of the variants' values, which
		// drops the count while keeping the per-position structure. Without
		// this, a list of N similarly-shaped records (e.g. bug-7963) hits the
		// limit and the generalization decomposes every nested constant array
		// into a flat `non-empty-list<unionOfAllPositionValues>`, losing the
		// shape entirely.
		$signatureGroups = [];
		$nonConstantTypes = [];
		foreach ($types as $idx => $type) {
			if (!$type instanceof ConstantArrayType) {
				$nonConstantTypes[$idx] = $type;
				continue;
			}
			$signatureParts = [];
			$signatureParts[] = $type->isList()->yes() ? 'L' : 'A';
			foreach ($type->getKeyTypes() as $i => $keyType) {
				$signatureParts[] = ($type->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
			}
			$signatureGroups[implode(',', $signatureParts)][] = $type;
		}
		if ($signatureGroups !== []) {
			$collapsed = $nonConstantTypes;
			$anyMerged = false;
			foreach ($signatureGroups as $group) {
				if (count($group) === 1) {
					$collapsed[] = $group[0];
					continue;
				}
				$merged = $group[0];
				for ($i = 1, $count = count($group); $i < $count; $i++) {
					$merged = $merged->mergeWith($group[$i]);
				}
				$collapsed[] = $merged;
				$anyMerged = true;
			}
			if ($anyMerged) {
				$types = array_values($collapsed);
				$constantArrayValuesCount = self::countConstantArrayValueTypes($types);
				if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
					return $types;
				}
			}
		}

		$results = [];
		$emptyArrays = [];
		$eachIsOversized = true;
		foreach ($types as $type) {
			if ($type->isConstantArray()->yes() && $type->isIterableAtLeastOnce()->no()) {
				$emptyArrays[] = $type;
				continue;
			}

			$isOversized = false;
			$result = TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$isOversized): Type {
				if (!$type instanceof ConstantArrayType) {
					return $traverse($type);
				}

				if ($type->isIterableAtLeastOnce()->no()) {
					return $type;
				}

				$isOversized = true;

				$isList = true;
				$valueTypes = [];
				$keyTypes = [];
				$nextAutoIndex = 0;
				$innerValueTypes = $type->getValueTypes();
				foreach ($type->getKeyTypes() as $i => $innerKeyType) {
					if (!$innerKeyType instanceof ConstantIntegerType) {
						$isList = false;
					} elseif ($innerKeyType->getValue() !== $nextAutoIndex) {
						$isList = false;
						$nextAutoIndex = $innerKeyType->getValue() + 1;
					} else {
						$nextAutoIndex++;
					}

					$generalizedKeyType = $innerKeyType->generalize(GeneralizePrecision::moreSpecific());
					$keyTypes[$generalizedKeyType->describe(VerbosityLevel::precise())] = $generalizedKeyType;

					// Inner traversal of the value position. Two subtleties, both
					// of which produced types that failed to be super-types of
					// their contributors:
					// - Empty constant arrays must be left alone; wrapping them
					//   builds a contradictory `array{}&oversized-array`.
					// - Fall through via `$innerTraverse`, not the outer
					//   `$traverse`. The outer callback fully generalizes a
					//   sealed `ConstantArrayType` into `array<intKey, V>&...`,
					//   which is correct at the top level but wrong inside a
					//   value position: it would treat a sealed `array{a: 1}`
					//   reached via `array{}|array{a: 1}` differently from one
					//   reached directly, leaving `processArrayTypes` with a
					//   mix of shapes it cannot unify cleanly.
					$generalizedValueType = TypeTraverser::map($innerValueTypes[$i], static function (Type $type, callable $innerTraverse): Type {
						if ($type instanceof ConstantArrayType && $type->isIterableAtLeastOnce()->no()) {
							return $type;
						}

						if ($type instanceof ArrayType || $type instanceof ConstantArrayType) {
							return new IntersectionType([$type, new OversizedArrayType()]);
						}

						if ($type instanceof ConstantScalarType) {
							return $type->generalize(GeneralizePrecision::moreSpecific());
						}

						return $innerTraverse($type);
					});
					$valueTypes[$generalizedValueType->describe(VerbosityLevel::precise())] = $generalizedValueType;
				}

				$keyType = TypeCombinator::union(...array_values($keyTypes));
				$valueType = TypeCombinator::union(...array_values($valueTypes));

				$accessories = [];
				if ($isList) {
					$accessories[] = new AccessoryArrayListType();
				}
				$accessories[] = new NonEmptyArrayType();
				$accessories[] = new OversizedArrayType();

				return self::intersect(new ArrayType($keyType, $valueType), ...$accessories);
			});

			if (!$isOversized) {
				$eachIsOversized = false;
			}

			$results[] = $result;
		}

		if ($eachIsOversized && $results !== []) {
			$eachIsList = true;
			$keyTypes = [];
			$valueTypes = [];
			foreach ($results as $result) {
				$keyTypes[] = $result->getIterableKeyType();
				$valueTypes[] = $result->getIterableValueType();
				if ($result->isList()->yes()) {
					continue;
				}
				$eachIsList = false;
			}

			$keyType = self::union(...$keyTypes);
			$valueType = self::union(...$valueTypes);

			if ($valueType instanceof UnionType && count($valueType->getTypes()) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
				$valueType = $valueType->generalize(GeneralizePrecision::lessSpecific());
			}

			$accessories = [];
			if ($eachIsList) {
				$accessories[] = new AccessoryArrayListType();
			}
			$accessories[] = new NonEmptyArrayType();
			$accessories[] = new OversizedArrayType();

			return [...$emptyArrays, self::intersect(new ArrayType($keyType, $valueType), ...$accessories)];
		}

		return [...$emptyArrays, ...$results];
	}

	/**
	 * @param Type[] $types
	 */
	public static function countConstantArrayValueTypes(array $types): int
	{
		$constantArrayValuesCount = 0;
		foreach ($types as $type) {
			TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$constantArrayValuesCount): Type {
				if ($type instanceof ConstantArrayType) {
					$constantArrayValuesCount += count($type->getValueTypes());
				}

				return $traverse($type);
			});
		}
		return $constantArrayValuesCount;
	}

	/**
	 * The value at each key of the array that is a single constant scalar, null
	 * when the array has real unsealed extras - its keys-supersets are then not
	 * decided by the known keys alone.
	 *
	 * @return array<int|string, scalar|null>|null
	 */
	private static function getConstantScalarValuesByKey(ConstantArrayType $array): ?array
	{
		$unsealed = $array->getUnsealedTypes();
		if ($unsealed !== null && !($unsealed[0] instanceof NeverType && $unsealed[0]->isExplicit())) {
			return null;
		}

		$values = [];
		$valueTypes = $array->getValueTypes();
		foreach ($array->getKeyTypes() as $i => $keyType) {
			if (!$valueTypes[$i]->isConstantScalarValue()->yes()) {
				continue;
			}
			$constantScalarValues = $valueTypes[$i]->getConstantScalarValues();
			if (count($constantScalarValues) !== 1) {
				continue;
			}
			$values[$keyType->getValue()] = $constantScalarValues[0];
		}

		return $values;
	}

	/**
	 * Whether two arrays differ in enough keys holding different single constant
	 * scalars that neither can be a keys-superset of the other: each such key
	 * pairs two disjoint values, and ConstantArrayType::isKeysSupersetOf() lets
	 * at most one key's values be unrelated - only when both arrays have the
	 * same number of keys, two or more.
	 *
	 * @param array<int|string, scalar|null>|null $a
	 * @param array<int|string, scalar|null>|null $b
	 */
	private static function haveDisjointConstantScalarValues(?array $a, ?array $b, bool $oneUnrelatedKeyAllowed): bool
	{
		if ($a === null || $b === null) {
			return false;
		}
		if (count($a) > count($b)) {
			[$a, $b] = [$b, $a];
		}

		$differing = 0;
		foreach ($a as $key => $value) {
			if (!array_key_exists($key, $b) || $b[$key] === $value) {
				continue;
			}
			$differing++;
			if ($differing >= 2 || !$oneUnrelatedKeyAllowed) {
				return true;
			}
		}

		return false;
	}

	/**
	 * @param list<Type> $constantArrays
	 * @return list<Type>
	 */
	private static function reduceArrays(array $constantArrays, bool $preserveTaggedUnions): array
	{
		$newArrays = [];
		$arraysToProcess = [];
		$emptyArray = null;
		foreach ($constantArrays as $constantArray) {
			if (!$constantArray->isConstantArray()->yes()) {
				// This is an optimization for current use-case of $preserveTaggedUnions=false, where we need
				// one constant array as a result, or we generalize the $constantArrays.
				if (!$preserveTaggedUnions) {
					return $constantArrays;
				}
				$newArrays[] = $constantArray;
				continue;
			}

			if ($constantArray->isIterableAtLeastOnce()->no()) {
				$emptyArray = $constantArray;
				continue;
			}

			$arraysToProcess = array_merge($arraysToProcess, $constantArray->getConstantArrays());
		}

		if ($emptyArray !== null) {
			if ($preserveTaggedUnions && $emptyArray instanceof ConstantArrayType) {
				// Let the empty array participate in merging — the passes below will absorb
				// it into any array that already accepts [] (all-optional keys, compatible
				// unsealed extras). If no such array exists, it remains as-is in the result.
				$arraysToProcess[] = $emptyArray;
			} else {
				$newArrays[] = $emptyArray;
			}
		}

		$arraysToProcessPerKey = [];
		foreach ($arraysToProcess as $i => $arrayToProcess) {
			foreach ($arrayToProcess->getKeyTypes() as $keyType) {
				$arraysToProcessPerKey[$keyType->getValue()][] = $i;
			}
		}

		// the single constant scalar value at each key of the arrays without
		// real unsealed extras (whose supersets the key/value shape decides)
		$constantScalarValues = [];
		if ($preserveTaggedUnions) {
			foreach ($arraysToProcess as $i => $arrayToProcess) {
				$constantScalarValues[$i] = self::getConstantScalarValuesByKey($arrayToProcess);
			}
		}

		$eligibleCombinations = [];

		foreach ($arraysToProcessPerKey as $arrays) {
			for ($i = 0, $arraysCount = count($arrays); $i < $arraysCount - 1; $i++) {
				for ($j = $i + 1; $j < $arraysCount; $j++) {
					$eligibleCombinations[$arrays[$i]][$arrays[$j]] ??= 0;
					$eligibleCombinations[$arrays[$i]][$arrays[$j]]++;
				}
			}
		}

		foreach ($eligibleCombinations as $i => $other) {
			if (!array_key_exists($i, $arraysToProcess)) {
				continue;
			}

			foreach ($other as $j => $overlappingKeysCount) {
				if (!array_key_exists($j, $arraysToProcess)) {
					continue;
				}

				// Merge two single-key arrays sharing the same key when their value
				// types union into a single type (not a UnionType). This is lossless
				// and prevents exponential union growth when narrowing nested
				// ArrayDimFetch expressions on a ConstantArrayType parent (see
				// phpstan/phpstan#14462).
				if (
					$preserveTaggedUnions
					&& $overlappingKeysCount === 1
					&& count($arraysToProcess[$i]->getKeyTypes()) === 1
					&& count($arraysToProcess[$j]->getKeyTypes()) === 1
				) {
					$iValueType = $arraysToProcess[$i]->getValueTypes()[0];
					$jValueType = $arraysToProcess[$j]->getValueTypes()[0];
					$unionValueType = self::union($iValueType, $jValueType);
					if (!$unionValueType instanceof UnionType) {
						$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
						$constantScalarValues[$j] = null;
						unset($arraysToProcess[$i]);
						continue 2;
					}
				}

				if (
					$preserveTaggedUnions
					&& self::haveDisjointConstantScalarValues(
						$constantScalarValues[$i] ?? null,
						$constantScalarValues[$j] ?? null,
						count($arraysToProcess[$i]->getKeyTypes()) === count($arraysToProcess[$j]->getKeyTypes())
							&& count($arraysToProcess[$i]->getKeyTypes()) >= 2,
					)
				) {
					// neither array is a keys-superset of the other
					continue;
				}

				if (
					$preserveTaggedUnions
					&& $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
					&& $arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])
				) {
					$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
					$constantScalarValues[$j] = null;
					unset($arraysToProcess[$i]);
					continue 2;
				}

				if (
					$preserveTaggedUnions
					&& $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
					&& $arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])
				) {
					$arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
					$constantScalarValues[$i] = null;
					unset($arraysToProcess[$j]);
					continue 1;
				}

				if (
					!$preserveTaggedUnions
					// both arrays have same keys
					&& $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
					&& $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
				) {
					$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
					unset($arraysToProcess[$i]);
					continue 2;
				}
			}
		}

		// Second pass: merge pairs that the eligibleCombinations loop above couldn't touch.
		// That loop only considers pairs sharing at least one known key, so it never fires
		// for e.g. `array{}` ∪ `array{a?: 1}` (disjoint, one empty) or for two
		// unsealed-extras arrays with disjoint required keys. Both collapse losslessly if
		// one side's extras or optional-key shape can absorb the other side's content.
		//
		// Performance: two sealed, non-empty, no-extras arrays with disjoint keys cannot
		// merge losslessly (legacyIsKeysSupersetOf returns false immediately on the first
		// missing key). Skip those pairs via a candidate flag to avoid an O(n²) scan that
		// dominated analyse time on files accumulating many sealed ConstantArrayType
		// variants (bug-7581 / bug-8146a). A pair is worth checking only if at least one
		// side is (a) empty, or (b) has real unsealed extras, or (c) has optional keys —
		// the last case covers the narrowing shape used by e.g. array_key_exists checks
		// over large optional-key shapes (bug-14032).
		$indices = array_keys($arraysToProcess);
		$indicesCount = count($indices);
		if ($indicesCount > 1) {
			$candidateFlags = [];
			foreach ($indices as $idx) {
				$arr = $arraysToProcess[$idx];
				$unsealed = $arr->getUnsealedTypes();
				if ($unsealed === null) {
					$candidateFlags[$idx] = false;
					continue;
				}
				[$unsealedKey] = $unsealed;
				$hasRealExtras = !($unsealedKey instanceof NeverType && $unsealedKey->isExplicit());
				if ($hasRealExtras) {
					$candidateFlags[$idx] = true;
					continue;
				}
				$keyTypesCount = count($arr->getKeyTypes());
				if ($keyTypesCount === 0) {
					$candidateFlags[$idx] = true;
					continue;
				}
				$hasOptional = count($arr->getOptionalKeys()) > 0;
				$candidateFlags[$idx] = $hasOptional;
			}

			for ($ii = 0; $ii < $indicesCount - 1; $ii++) {
				$i = $indices[$ii];
				if (!array_key_exists($i, $arraysToProcess)) {
					continue;
				}
				if ($arraysToProcess[$i]->getUnsealedTypes() === null) {
					continue;
				}
				for ($jj = $ii + 1; $jj < $indicesCount; $jj++) {
					$j = $indices[$jj];
					if (!array_key_exists($j, $arraysToProcess)) {
						continue;
					}
					if (!$candidateFlags[$i] && !$candidateFlags[$j]) {
						continue;
					}
					if ($arraysToProcess[$j]->getUnsealedTypes() === null) {
						continue;
					}
					if ($arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])) {
						$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
						unset($arraysToProcess[$i]);
						continue 2;
					}
					if (!$arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])) {
						continue;
					}

					$arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
					unset($arraysToProcess[$j]);
				}
			}
		}

		// Final pass: if merging left us with a ConstantArrayType that has no known keys
		// but has real unsealed extras, collapse it to a plain ArrayType (mirrors the same
		// logic in ConstantArrayTypeBuilder::getArray — but applies to results produced by
		// ConstantArrayType::mergeWith, which doesn't go through the builder).
		foreach ($arraysToProcess as $idx => $arr) {
			if (count($arr->getKeyTypes()) !== 0) {
				continue;
			}
			$unsealed = $arr->getUnsealedTypes();
			if ($unsealed === null) {
				continue;
			}
			[$unsealedKey, $unsealedValue] = $unsealed;
			if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
				continue;
			}
			$newArrays[] = new ArrayType($unsealedKey, $unsealedValue);
			unset($arraysToProcess[$idx]);
		}

		// Final pass: collapse the loop-accumulator pattern where each iteration
		// produced a longer non-empty list variant. When several non-empty list
		// ConstantArrayTypes survive earlier merging and together push the
		// constant-array value count past the limit, fold them into a single
		// non-empty-list<unionValueType> so the result stays bounded without
		// going through the lossier optimizeConstantArrays generalization.
		// Skip when every list variant shares one key signature — those collapse
		// losslessly via the stage 1 same-key-set merge in optimizeConstantArrays
		// (each position keeps its own value union), which is strictly more
		// precise than this flat fold.
		if ($preserveTaggedUnions && count($arraysToProcess) > 1) {
			$listVariantIndices = [];
			$listValueTypes = [];
			$listVariants = [];
			$listVariantSignatures = [];
			foreach ($arraysToProcess as $idx => $arr) {
				if (!$arr->isList()->yes() || !$arr->isIterableAtLeastOnce()->yes()) {
					continue;
				}
				$listVariantIndices[] = $idx;
				$listValueTypes[] = $arr->getIterableValueType();
				$listVariants[] = $arr;
				$signatureParts = [];
				foreach ($arr->getKeyTypes() as $i => $keyType) {
					$signatureParts[] = ($arr->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
				}
				$listVariantSignatures[implode(',', $signatureParts)] = true;
			}
			if (
				count($listVariantIndices) >= 2
				&& count($listVariantSignatures) >= 2
				&& self::countConstantArrayValueTypes($listVariants) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT
			) {
				$mergedValueType = self::union(...$listValueTypes);
				$merged = self::intersect(
					new ArrayType(new IntegerType(), $mergedValueType),
					new NonEmptyArrayType(),
					new AccessoryArrayListType(),
				);
				$newArrays[] = $merged;
				foreach ($listVariantIndices as $idx) {
					unset($arraysToProcess[$idx]);
				}
			}
		}

		return array_merge($newArrays, $arraysToProcess);
	}

	/**
	 * Fast path for intersect(): the intersection of two unions whose members are all
	 * finite, mutually-disjoint values (constant scalars and/or enum cases) is their
	 * identity-keyed set intersection. Returns null when either union has a member that is
	 * not such a value, in which case the caller falls back to the general A & (B|C)
	 * distribution.
	 */
	/** @phpstan-assert-if-true UnionType $type */
	private static function isPlainOrBenevolentUnion(Type $type): bool
	{
		$class = get_class($type);

		return $class === UnionType::class || $class === BenevolentUnionType::class;
	}

	private static function intersectFiniteUnions(UnionType $a, UnionType $b): ?Type
	{
		$membersA = self::finiteUnionMembers($a);
		if ($membersA === null) {
			return null;
		}

		$membersB = self::finiteUnionMembers($b);
		if ($membersB === null) {
			return null;
		}

		$common = [];
		foreach ($membersA as $key => $member) {
			if (!array_key_exists($key, $membersB)) {
				continue;
			}

			$common[] = $member;
		}

		if ($common === []) {
			return new NeverType();
		}

		return self::union(...$common);
	}

	/**
	 * The union's members keyed by identity, or null when the fast path does not apply.
	 *
	 * FiniteTypeSet does the keying and the union caches it; on top of that, intersect()
	 * hands one of the two members back instead of only comparing them, so a constant string
	 * that is also a class-string is not interchangeable with a same-valued one that is not -
	 * the class-string flag would be lost. Such unions go the slow way.
	 *
	 * @return array<string, Type>|null
	 */
	private static function finiteUnionMembers(UnionType $union): ?array
	{
		$finiteTypeSet = $union->getFiniteTypeSet();
		if ($finiteTypeSet === null || !$finiteTypeSet->isComplete()) {
			return null;
		}

		return $finiteTypeSet->getMembers();
	}

	public static function intersect(Type ...$types): Type
	{
		if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
			return TypeCombinatorCache::intersect(...$types);
		}

		return self::doIntersect(...$types);
	}

	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
	public static function doIntersect(Type ...$types): Type
	{
		$typesCount = count($types);
		if ($typesCount === 0) {
			return new NeverType();
		}

		$types = array_values($types);
		if ($typesCount === 1) {
			return $types[0];
		}

		// The comparator only orders UnionTypes relative to each other, so sorting is
		// a no-op unless there are at least two of them. Skip it in the common case.
		$unionTypesCount = 0;
		foreach ($types as $type) {
			if ($type instanceof NeverType && !$type->isExplicit()) {
				return $type;
			}
			if (!$type instanceof UnionType) {
				continue;
			}
			$unionTypesCount++;
		}

		// Fast path: the intersection of two unions whose members are all finite,
		// mutually-disjoint values (constant scalars and/or enum cases) is their
		// identity-keyed set intersection (O(n)), avoiding the O(n*m) `A & (B|C)`
		// distribution + union rebuild below. A benevolent union is the one the
		// distribution walks first and the benevolence it gives the result is kept;
		// the template union types keep their dedicated handling.
		if (
			$typesCount === 2
			&& self::isPlainOrBenevolentUnion($types[0])
			&& self::isPlainOrBenevolentUnion($types[1])
		) {
			[$a, $b] = $types;
			if ($b instanceof BenevolentUnionType && !$a instanceof BenevolentUnionType) {
				[$a, $b] = [$b, $a];
			}
			$finiteIntersection = self::intersectFiniteUnions($a, $b);
			if ($finiteIntersection !== null) {
				return $a instanceof BenevolentUnionType ? TypeUtils::toBenevolentUnion($finiteIntersection) : $finiteIntersection;
			}
		}

		$sortTypes = static function (Type $a, Type $b): int {
			if (!$a instanceof UnionType || !$b instanceof UnionType) {
				return 0;
			}

			if ($a instanceof TemplateType) {
				return -1;
			}
			if ($b instanceof TemplateType) {
				return 1;
			}

			if ($a instanceof BenevolentUnionType) {
				return -1;
			}
			if ($b instanceof BenevolentUnionType) {
				return 1;
			}

			return 0;
		};
		if ($unionTypesCount >= 2) {
			usort($types, $sortTypes);
		}
		// transform A & (B | C) to (A & B) | (A & C)
		foreach ($types as $i => $type) {
			if (!$type instanceof UnionType) {
				continue;
			}

			$topLevelUnionSubTypes = [];
			$innerTypes = $type->getTypes();
			$innerUnionTypesCount = 0;
			foreach ($innerTypes as $innerType) {
				if (!$innerType instanceof UnionType) {
					continue;
				}
				$innerUnionTypesCount++;
				if ($innerUnionTypesCount >= 2) {
					break;
				}
			}
			if ($innerUnionTypesCount >= 2) {
				usort($innerTypes, $sortTypes);
			}
			$slice1 = array_slice($types, 0, $i);
			$slice2 = array_slice($types, $i + 1);
			foreach ($innerTypes as $innerUnionSubType) {
				$topLevelUnionSubTypes[] = self::intersect(
					$innerUnionSubType,
					...$slice1,
					...$slice2,
				);
			}

			$union = self::union(...$topLevelUnionSubTypes);
			if ($union instanceof NeverType) {
				return $union;
			}

			if ($type instanceof BenevolentUnionType) {
				$union = TypeUtils::toBenevolentUnion($union);
			}

			if ($type instanceof TemplateUnionType || $type instanceof TemplateBenevolentUnionType) {
				$union = TemplateTypeFactory::create(
					$type->getScope(),
					$type->getName(),
					$union,
					$type->getVariance(),
					$type->getStrategy(),
					$type->getDefault(),
				);
			}

			return $union;
		}

		$newTypes = [];
		$hasOffsetValueTypeCount = 0;
		$typesCount = count($types);
		$typesNeedSorting = false;
		$hasPropertyType = false;
		for ($i = 0; $i < $typesCount; $i++) {
			$type = $types[$i];

			if ($type instanceof SubtractableType || $type instanceof ConstantArrayType) {
				$typesNeedSorting = true;
			}

			if ($type instanceof HasPropertyType) {
				$hasPropertyType = true;
			}

			if ($type instanceof IntersectionType && !$type instanceof TemplateType) {
				// transform A & (B & C) to A & B & C
				array_splice($types, $i--, 1, $type->getTypes());
				$typesCount = count($types);
			} elseif ($type instanceof HasOffsetValueType) {
				$hasOffsetValueTypeCount++;
			} else {
				$newTypes[] = $type;
			}
		}

		if ($hasOffsetValueTypeCount > 32) {
			$newTypes[] = new OversizedArrayType();
			$types = $newTypes;
			$typesCount = count($types);
		}

		if ($typesNeedSorting) {
			usort($types, static function (Type $a, Type $b): int {
				// move subtractables with subtracts before those without to avoid losing them in the union logic
				if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
					return -1;
				}
				if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
					return 1;
				}

				if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
					return -1;
				}
				if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
					return 1;
				}

				return 0;
			});
		}

		// Resolve object-shape optional keys that a HasPropertyType asserts are present before the
		// reduction loop below. In that loop the generic supertype dedup can drop a HasPropertyType
		// as redundant against a dynamic-property class such as stdClass (which reports every
		// property as present) before it is ever paired with the object shape. Which of the two
		// fires first depends on the member order, so the collapse runs here, where order does not
		// change the result of what is meant to be an order-independent value. Gated on the presence
		// of a HasPropertyType so the common intersection pays only the flag check set above.
		if ($hasPropertyType) {
			for ($i = 0; $i < $typesCount; $i++) {
				for ($j = $i + 1; $j < $typesCount; $j++) {
					if (
						$types[$i] instanceof ObjectShapeType
						&& $types[$j] instanceof HasPropertyType
						&& !$types[$i]->hasInstanceProperty($types[$j]->getPropertyName())->no()
					) {
						$types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if (
						$types[$j] instanceof ObjectShapeType
						&& $types[$i] instanceof HasPropertyType
						&& !$types[$j]->hasInstanceProperty($types[$i]->getPropertyName())->no()
					) {
						$types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}
				}
			}
		}

		// transform IntegerType & ConstantIntegerType to ConstantIntegerType
		// transform Child & Parent to Child
		// transform Object & ~null to Object
		// transform A & A to A
		// transform int[] & string to never
		// transform callable & int to never
		// transform A & ~A to never
		// transform int & string to never
		for ($i = 0; $i < $typesCount; $i++) {
			for ($j = $i + 1; $j < $typesCount; $j++) {
				if ($types[$j] instanceof SubtractableType) {
					$typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();

					if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
						$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
					} else {
						$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
					}
					if ($isSuperTypeSubtractableA->yes()) {
						$types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
						array_splice($types, $j--, 1);
						$typesCount--;
						continue 1;
					}
				}

				if ($types[$i] instanceof SubtractableType) {
					$typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();

					if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
						$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
					} else {
						$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
					}
					if ($isSuperTypeSubtractableB->yes()) {
						$types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}
				}

				if ($types[$i] instanceof IntegerRangeType) {
					$intersectionType = $types[$i]->tryIntersect($types[$j]);
					if ($intersectionType !== null) {
						$types[$j] = $intersectionType;
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}
				}

				if ($types[$j] instanceof IterableType) {
					$isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
				} else {
					$isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
				}

				if ($isSuperTypeA->yes()) {
					array_splice($types, $j--, 1);
					$typesCount--;
					continue;
				}

				if ($types[$i] instanceof IterableType) {
					$isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
				} else {
					$isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
				}

				if ($isSuperTypeB->maybe()) {
					if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
						$types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
						$types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof AccessoryArrayListType) {
						$types[$i] = $types[$i]->makeList();
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof AccessoryArrayListType) {
						$types[$j] = $types[$j]->makeList();
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					if (
						$types[$i] instanceof ConstantArrayType
						&& $types[$j] instanceof NonEmptyArrayType
						&& (count($types[$i]->getKeyTypes()) === 1 || $types[$i]->isList()->yes())
						&& $types[$i]->isOptionalKey(0)
						&& !$types[$i]->isUnsealed()->yes()
					) {
						$types[$i] = $types[$i]->makeOffsetRequired($types[$i]->getKeyTypes()[0]);
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if (
						$types[$j] instanceof ConstantArrayType
						&& $types[$i] instanceof NonEmptyArrayType
						&& (count($types[$j]->getKeyTypes()) === 1 || $types[$j]->isList()->yes())
						&& $types[$j]->isOptionalKey(0)
						&& !$types[$j]->isUnsealed()->yes()
					) {
						$types[$j] = $types[$j]->makeOffsetRequired($types[$j]->getKeyTypes()[0]);
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
						$offsetType = $types[$j]->getOffsetType();
						$valueType = $types[$j]->getValueType();
						$newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
						if ($newValueType instanceof NeverType) {
							return $newValueType;
						}
						$types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
						$offsetType = $types[$i]->getOffsetType();
						$valueType = $types[$i]->getValueType();
						$newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
						if ($newValueType instanceof NeverType) {
							return $newValueType;
						}

						$types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					$constArrayIsI = $types[$i] instanceof ConstantArrayType && ($types[$j] instanceof ArrayType || $types[$j] instanceof ConstantArrayType);
					$constArrayIsJ = $types[$j] instanceof ConstantArrayType && ($types[$i] instanceof ArrayType || $types[$i] instanceof ConstantArrayType);
					if ($constArrayIsI || $constArrayIsJ) {
						$constArray = $constArrayIsI ? $types[$i] : $types[$j];
						$otherArray = $constArrayIsI ? $types[$j] : $types[$i];

						if (
							$otherArray instanceof ConstantArrayType
							&& !$constArray->isUnsealed()->maybe()
							&& !$otherArray->isUnsealed()->maybe()
						) {
							$merged = self::intersectDefiniteConstantArrays($constArray, $otherArray);
							if ($merged instanceof NeverType) {
								if ($merged->getReason() === null) {
									$reasons = array_merge($isSuperTypeA->getReasons(), $isSuperTypeB->getReasons());
									if ($reasons !== []) {
										return new NeverType(reason: $reasons[0]);
									}
								}
								return $merged;
							}
							$newArrayType = $merged;
						} else {
							$newArray = ConstantArrayTypeBuilder::createEmpty();
							// Preserve unsealed extras from the source shape so the
							// rebuild doesn't silently turn `array{k: int, ...} & X`
							// into a sealed `array{k: int}` — intersect with the other
							// side's iterable key/value so the open part keeps both
							// sides' refinements.
							$constUnsealed = $constArray->getUnsealedTypes();
							if ($constUnsealed !== null && $constArray->isUnsealed()->yes()) {
								$newUnsealedKey = self::intersect($constUnsealed[0], $otherArray->getIterableKeyType());
								$newUnsealedValue = self::intersect($constUnsealed[1], $otherArray->getIterableValueType());
								if (!$newUnsealedKey instanceof NeverType && !$newUnsealedValue instanceof NeverType) {
									$newArray->makeUnsealed($newUnsealedKey, $newUnsealedValue);
								}
							}
							$valueTypes = $constArray->getValueTypes();
							foreach ($constArray->getKeyTypes() as $k => $keyType) {
								$hasOffset = $otherArray->hasOffsetValueType($keyType);
								if ($hasOffset->no()) {
									continue;
								}
								$newArray->setOffsetValueType(
									self::intersect($keyType, $otherArray->getIterableKeyType()),
									self::intersect($valueTypes[$k], $otherArray->getOffsetValueType($keyType)),
									$constArray->isOptionalKey($k) && !$hasOffset->yes(),
								);
							}
							$newArrayType = $newArray->getArray();
							if ($constArray->isList()->yes()) {
								$newArrayType = self::intersect($newArrayType, new AccessoryArrayListType());
							}
						}

						if ($constArrayIsI) {
							$types[$i] = $newArrayType;
							array_splice($types, $j, 1);
						} else {
							$types[$j] = $newArrayType;
							array_splice($types, $i--, 1);
						}
						$typesCount--;
						continue 2;
					}

					if (
						($types[$i] instanceof ArrayType || $types[$i] instanceof ConstantArrayType || $types[$i] instanceof IterableType) &&
						($types[$j] instanceof ArrayType || $types[$j] instanceof ConstantArrayType || $types[$j] instanceof IterableType)
					) {
						$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
						$itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
						if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
							$types[$j] = new IterableType($keyType, $itemType);
						} else {
							$types[$j] = new ArrayType($keyType, $itemType);
						}
						array_splice($types, $i--, 1);
						$typesCount--;
						continue 2;
					}

					if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
						$genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
						$types[$i] = new GenericClassStringType($genericType);
						array_splice($types, $j--, 1);
						$typesCount--;
						continue;
					}

					if (
						$types[$i] instanceof ArrayType
						&& get_class($types[$i]) === ArrayType::class
						&& $types[$j] instanceof AccessoryArrayListType
						&& !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
					) {
						$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
						if ($keyType instanceof NeverType) {
							return $keyType;
						}
						$types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
						continue;
					}

					continue;
				}

				if ($isSuperTypeB->yes()) {
					array_splice($types, $i--, 1);
					$typesCount--;
					continue 2;
				}

				if ($isSuperTypeA->no()) {
					return new NeverType(reason: $isSuperTypeA->getReasons()[0] ?? null);
				}
			}
		}

		if ($typesCount === 1) {
			return $types[0];
		}

		$accessoryBaseTypes = [];
		foreach ($types as $type) {
			if (!$type instanceof AccessoryType) {
				$accessoryBaseTypes = null;
				break;
			}
			// Accessory types share their default base type: every string accessory
			// returns `string`, hasOffset() and hasOffsetValue() both return
			// `array|ArrayAccess`. Adding the same base type again narrows nothing -
			// intersection is idempotent - but the intersect() below distributes
			// `A & (B | C)` one union at a time, so n copies of `array|ArrayAccess`
			// would cost 2^n recursive calls before the duplicates are recognized at
			// the leaves. That is why isset() with many offsets used to grow
			// exponentially: each offset contributes one hasOffset().
			$baseType = $type->getDefaultBaseType();
			foreach ($accessoryBaseTypes as $addedBaseType) {
				if ($addedBaseType->equals($baseType)) {
					continue 2;
				}
			}
			$accessoryBaseTypes[] = $baseType;
		}
		if ($accessoryBaseTypes !== null) {
			// Accessory types never stand alone — supply the base type they refine.
			return self::intersect(self::intersect(...$accessoryBaseTypes), ...$types);
		}

		return new IntersectionType($types);
	}

	private static function intersectDefiniteConstantArrays(ConstantArrayType $a, ConstantArrayType $b): Type
	{
		$aSealed = $a->isUnsealed()->no();
		$bSealed = $b->isUnsealed()->no();
		$bothUnsealed = !$aSealed && !$bSealed && $a->getUnsealedTypes() !== null && $b->getUnsealedTypes() !== null;

		$aKeyByValue = [];
		foreach ($a->getKeyTypes() as $k => $keyType) {
			$aKeyByValue[$keyType->getValue()] = $k;
		}
		$bKeyByValue = [];
		foreach ($b->getKeyTypes() as $k => $keyType) {
			$bKeyByValue[$keyType->getValue()] = $k;
		}

		if ($aSealed && $bSealed) {
			foreach ($aKeyByValue as $keyValue => $k) {
				if (!$a->isOptionalKey($k) && !array_key_exists($keyValue, $bKeyByValue)) {
					return new NeverType();
				}
			}
			foreach ($bKeyByValue as $keyValue => $k) {
				if (!$b->isOptionalKey($k) && !array_key_exists($keyValue, $aKeyByValue)) {
					return new NeverType();
				}
			}
		}

		$newArray = ConstantArrayTypeBuilder::createEmpty();

		if ($bothUnsealed) {
			$aUnsealed = $a->getUnsealedTypes();
			$bUnsealed = $b->getUnsealedTypes();
			$unsealedKey = self::intersect($aUnsealed[0], $bUnsealed[0]);
			$unsealedValue = self::intersect($aUnsealed[1], $bUnsealed[1]);
			if ($unsealedKey instanceof NeverType || $unsealedValue instanceof NeverType) {
				return new NeverType();
			}
			$newArray->makeUnsealed($unsealedKey, $unsealedValue);
		} else {
			$never = new NeverType(true);
			$newArray->makeUnsealed($never, $never);
		}

		$resolveOtherValue = static function (ConstantArrayType $other, Type $keyType): ?Type {
			if ($other->hasOffsetValueType($keyType)->yes()) {
				return $other->getOffsetValueType($keyType);
			}
			$otherUnsealed = $other->getUnsealedTypes();
			if ($otherUnsealed === null) {
				return null;
			}
			[$unsealedKey, $unsealedValue] = $otherUnsealed;
			if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
				return null;
			}
			if ($unsealedKey->isSuperTypeOf($keyType)->no()) {
				return null;
			}
			return $unsealedValue;
		};

		$keysToProcess = [];
		foreach ($aKeyByValue as $keyValue => $k) {
			$keysToProcess[$keyValue] = [$k, $bKeyByValue[$keyValue] ?? null];
		}
		foreach ($bKeyByValue as $keyValue => $k) {
			if (array_key_exists($keyValue, $keysToProcess)) {
				continue;
			}

			$keysToProcess[$keyValue] = [null, $k];
		}

		foreach ($keysToProcess as [$aIdx, $bIdx]) {
			if ($aIdx !== null && $bIdx !== null) {
				$keyType = $a->getKeyTypes()[$aIdx];
				$value = self::intersect($a->getValueTypes()[$aIdx], $b->getValueTypes()[$bIdx]);
				$optional = $a->isOptionalKey($aIdx) && $b->isOptionalKey($bIdx);
			} elseif ($aIdx !== null) {
				$keyType = $a->getKeyTypes()[$aIdx];
				$aValue = $a->getValueTypes()[$aIdx];
				$bValue = $resolveOtherValue($b, $keyType);
				if ($bValue === null) {
					if ($a->isOptionalKey($aIdx)) {
						continue;
					}
					return new NeverType();
				}
				$value = self::intersect($aValue, $bValue);
				$optional = $a->isOptionalKey($aIdx);
			} else {
				/** @var int<0, max> $bIdx */
				$keyType = $b->getKeyTypes()[$bIdx];
				$bValue = $b->getValueTypes()[$bIdx];
				$aValue = $resolveOtherValue($a, $keyType);
				if ($aValue === null) {
					if ($b->isOptionalKey($bIdx)) {
						continue;
					}
					return new NeverType();
				}
				$value = self::intersect($aValue, $bValue);
				$optional = $b->isOptionalKey($bIdx);
			}

			if ($value instanceof NeverType) {
				if ($optional) {
					continue;
				}
				return new NeverType();
			}
			$newArray->setOffsetValueType($keyType, $value, $optional);
		}

		return $newArray->getArray();
	}

	/**
	 * Merge two IntersectionTypes that have the same structure but differ
	 * in HasOffsetValueType value types (matched by offset key).
	 *
	 * E.g. (A & hasOV('k', X)) | (A & hasOV('k', Y)) → (A & hasOV('k', X|Y))
	 */
	private static function mergeIntersectionsForUnion(IntersectionType $a, IntersectionType $b): ?Type
	{
		$aTypes = $a->getTypes();
		$bTypes = $b->getTypes();

		if (count($aTypes) !== count($bTypes)) {
			return null;
		}

		$mergedTypes = [];
		$hasDifference = false;
		$bUsed = array_fill(0, count($bTypes), false);

		foreach ($aTypes as $aType) {
			$matched = false;
			foreach ($bTypes as $bIdx => $bType) {
				if ($bUsed[$bIdx]) {
					continue;
				}

				if ($aType->equals($bType)) {
					$mergedTypes[] = $aType;
					$bUsed[$bIdx] = true;
					$matched = true;
					break;
				}

				// HasOffsetValueType: merge value types when offset keys match
				if ($aType instanceof HasOffsetValueType && $bType instanceof HasOffsetValueType
					&& $aType->getOffsetType()->equals($bType->getOffsetType())) {
					$mergedTypes[] = new HasOffsetValueType(
						$aType->getOffsetType(),
						self::union($aType->getValueType(), $bType->getValueType()),
					);
					$hasDifference = true;
					$bUsed[$bIdx] = true;
					$matched = true;
					break;
				}

				// HasOffsetType, HasMethodType, HasPropertyType: only equal values match (no merging possible)
			}
			if (!$matched) {
				return null;
			}
		}

		if (!$hasDifference) {
			return null;
		}

		$result = $mergedTypes[0];
		for ($i = 1, $count = count($mergedTypes); $i < $count; $i++) {
			$result = self::intersect($result, $mergedTypes[$i]);
		}
		return $result;
	}

	public static function removeFalsey(Type $type): Type
	{
		return self::remove($type, StaticTypeFactory::falsey());
	}

	public static function removeTruthy(Type $type): Type
	{
		return self::remove($type, StaticTypeFactory::truthy());
	}

}