File src/Type/TypeCombinator.php

1:	<?php declare(strict_types = 1);
2:
3:	namespace PHPStan\Type;
4:
5:	use PHPStan\TrinaryLogic;
6:	use PHPStan\Turbo\ShadowedByTurboExtension;
7:	use PHPStan\Turbo\TurboExtensionEnabler;
8:	use PHPStan\Type\Accessory\AccessoryArrayListType;
9:	use PHPStan\Type\Accessory\AccessoryDecimalIntegerStringType;
10:	use PHPStan\Type\Accessory\AccessoryLowercaseStringType;
11:	use PHPStan\Type\Accessory\AccessoryNonEmptyStringType;
12:	use PHPStan\Type\Accessory\AccessoryNonFalsyStringType;
13:	use PHPStan\Type\Accessory\AccessoryType;
14:	use PHPStan\Type\Accessory\AccessoryUppercaseStringType;
15:	use PHPStan\Type\Accessory\HasOffsetType;
16:	use PHPStan\Type\Accessory\HasOffsetValueType;
17:	use PHPStan\Type\Accessory\HasPropertyType;
18:	use PHPStan\Type\Accessory\NonEmptyArrayType;
19:	use PHPStan\Type\Accessory\OversizedArrayType;
20:	use PHPStan\Type\Constant\ConstantArrayType;
21:	use PHPStan\Type\Constant\ConstantArrayTypeBuilder;
22:	use PHPStan\Type\Constant\ConstantBooleanType;
23:	use PHPStan\Type\Constant\ConstantFloatType;
24:	use PHPStan\Type\Constant\ConstantIntegerType;
25:	use PHPStan\Type\Constant\ConstantStringType;
26:	use PHPStan\Type\Generic\GenericClassStringType;
27:	use PHPStan\Type\Generic\TemplateArrayType;
28:	use PHPStan\Type\Generic\TemplateBenevolentUnionType;
29:	use PHPStan\Type\Generic\TemplateMixedType;
30:	use PHPStan\Type\Generic\TemplateType;
31:	use PHPStan\Type\Generic\TemplateTypeFactory;
32:	use PHPStan\Type\Generic\TemplateUnionType;
33:	use PHPStan\Type\Generic\UnresolvedTemplateArgumentType;
34:	use function array_fill;
35:	use function array_filter;
36:	use function array_key_exists;
37:	use function array_key_first;
38:	use function array_keys;
39:	use function array_merge;
40:	use function array_slice;
41:	use function array_splice;
42:	use function array_values;
43:	use function count;
44:	use function get_class;
45:	use function implode;
46:	use function in_array;
47:	use function spl_object_id;
48:	use function sprintf;
49:	use function usort;
50:	use const PHP_INT_MAX;
51:	use const PHP_INT_MIN;
52:
53:	/**
54:	* @api
55:	*/
56:	#[ShadowedByTurboExtension(implementation: __DIR__ . '/../../turbo-ext/src/TypeCombinator.cpp')]
57:	final class TypeCombinator
58:	{
59:
60:	/**
61:	* Turned on by TurboExtensionEnabler when the native extension is active, so that
62:	* union(), intersect() and remove() route through the memoizing TypeCombinatorCache.
63:	* Without the extension the operations run exactly as they always have — the flag
64:	* costs a property read, and nothing else changes.
65:	*/
66:	private static ?bool $cacheEnabled = null;
67:
68:	/**
69:	* Memoization hands back shared Type instances, and a Type lazily resolves a
70:	* ClassReflection belonging to the container that created it — so the cache must
71:	* not outlive its container.
72:	*/
73:	public static function clearCache(): void
74:	{
75:	if ((self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) === false) {
76:	return;
77:	}
78:
79:	TypeCombinatorCache::clearCache();
80:	}
81:
82:	public static function addNull(Type $type): Type
83:	{
84:	// asking the type itself is both cheaper than NullType::isSuperTypeOf()
85:	// (UnionType memoizes isNull(), isSubTypeOf() recomputes) and right for
86:	// `never`, of which null is a supertype without never containing it.
87:	if ($type->isNull()->no()) {
88:	return self::union($type, new NullType());
89:	}
90:
91:	return $type;
92:	}
93:
94:	public static function remove(Type $fromType, Type $typeToRemove): Type
95:	{
96:	if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
97:	return TypeCombinatorCache::remove($fromType, $typeToRemove);
98:	}
99:
100:	return self::doRemove($fromType, $typeToRemove);
101:	}
102:
103:	/**
104:	* Whether removing the union's members all at once gives what removing them
105:	* one at a time would: true when the subtraction is a set difference, so no
106:	* order of removals can sharpen the result.
107:	*
108:	* Everywhere else the members have to come off one at a time - removing one
109:	* can narrow the type so that removing the next achieves more.
110:	*/
111:	private static function canRemoveUnionAtOnce(Type $fromType): bool
112:	{
113:	// A sealed hierarchy - an enum, or a hierarchy an
114:	// AllowedSubTypesClassReflectionExtension seals - subtracts by dropping
115:	// allowed subtypes, and which ones are dropped does not depend on order.
116:	$classReflections = $fromType->getObjectClassReflections();
117:	if (count($classReflections) === 1 && $classReflections[0]->getAllowedSubTypes() !== null) {
118:	return true;
119:	}
120:
121:	// A union removes the whole thing from each of its members, and each of
122:	// those removals weighs this same question again - so a member that needs
123:	// the removals one at a time still gets them that way.
124:	return $fromType instanceof UnionType;
125:	}
126:
127:	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
128:	public static function doRemove(Type $fromType, Type $typeToRemove): Type
129:	{
130:	if ($typeToRemove instanceof UnionType) {
131:	// Removing the members one at a time is what keeps the result precise:
132:	// removing one can narrow the type so that removing the next achieves
133:	// more. A sealed hierarchy is the exception - there the subtraction is
134:	// a set difference over the allowed subtypes, so the order the members
135:	// come off cannot matter, and peeling them would rebuild the whole
136:	// subtraction once per member (removing an enum from its own type then
137:	// costs O(cases^2)).
138:	if (self::canRemoveUnionAtOnce($fromType)) {
139:	$removed = $fromType->tryRemove($typeToRemove);
140:	if ($removed !== null) {
141:	return $removed;
142:	}
143:	}
144:
145:	foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
146:	$fromType = self::remove($fromType, $unionTypeToRemove);
147:	if ($fromType instanceof NeverType) {
148:	// there is nothing left to remove from
149:	break;
150:	}
151:	}
152:	return $fromType;
153:	}
154:
155:	$isSuperType = $typeToRemove->isSuperTypeOf($fromType);
156:	if ($isSuperType->yes()) {
157:	return new NeverType();
158:	}
159:	if ($isSuperType->no()) {
160:	return $fromType;
161:	}
162:
163:	if ($typeToRemove instanceof MixedType) {
164:	$typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
165:	if ($typeToRemoveSubtractedType !== null) {
166:	return self::intersect($fromType, $typeToRemoveSubtractedType);
167:	}
168:	}
169:
170:	$removed = $fromType->tryRemove($typeToRemove);
171:	if ($removed !== null) {
172:	return $removed;
173:	}
174:
175:	$fromFiniteTypes = $fromType->getFiniteTypes();
176:	if (count($fromFiniteTypes) > 0) {
177:	$finiteTypesToRemove = $typeToRemove->getFiniteTypes();
178:	if (count($finiteTypesToRemove) > 0) {
179:	$result = [];
180:	foreach ($fromFiniteTypes as $finiteType) {
181:	foreach ($finiteTypesToRemove as $finiteTypeToRemove) {
182:	if ($finiteType->equals($finiteTypeToRemove)) {
183:	continue 2;
184:	}
185:	}
186:
187:	$result[] = $finiteType;
188:	}
189:
190:	if (count($result) === count($fromFiniteTypes)) {
191:	return $fromType;
192:	}
193:
194:	if (count($result) === 0) {
195:	return new NeverType();
196:	}
197:
198:	if (count($result) === 1) {
199:	return $result[0];
200:	}
201:
202:	return new UnionType($result);
203:	}
204:	}
205:
206:	return $fromType;
207:	}
208:
209:	public static function removeNull(Type $type): Type
210:	{
211:	if (self::containsNull($type)) {
212:	return self::remove($type, new NullType());
213:	}
214:
215:	return $type;
216:	}
217:
218:	public static function containsNull(Type $type): bool
219:	{
220:	if ($type instanceof UnionType) {
221:	foreach ($type->getTypes() as $innerType) {
222:	if ($innerType->isNull()->yes()) {
223:	return true;
224:	}
225:	}
226:
227:	return false;
228:	}
229:
230:	return $type instanceof NullType;
231:	}
232:
233:	public static function union(Type ...$types): Type
234:	{
235:	if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
236:	return TypeCombinatorCache::union(...$types);
237:	}
238:
239:	return self::doUnion(...$types);
240:	}
241:
242:	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
243:	public static function doUnion(Type ...$types): Type
244:	{
245:	$typesCount = count($types);
246:	if ($typesCount === 0) {
247:	return new NeverType();
248:	}
249:
250:	// Fast path for single non-union type
251:	if ($typesCount === 1) {
252:	$singleType = $types[0];
253:	if (!$singleType instanceof UnionType && !$singleType->isArray()->yes()) {
254:	return $singleType;
255:	}
256:	}
257:
258:	// Fast path for common 2-type cases
259:	if ($typesCount === 2) {
260:	$a = $types[0];
261:	$b = $types[1];
262:
263:	// union(never, X) = X and union(X, never) = X
264:	if ($a instanceof NeverType && !$a->isExplicit()) {
265:	return $b;
266:	}
267:	if ($b instanceof NeverType && !$b->isExplicit()) {
268:	return $a;
269:	}
270:
271:	// union(mixed, X) = mixed (non-explicit, non-template, no subtracted)
272:	if ($a instanceof MixedType && !$a->isExplicitMixed() && !$a instanceof TemplateMixedType && $a->getSubtractedType() === null) {
273:	return $a;
274:	}
275:	if ($b instanceof MixedType && !$b->isExplicitMixed() && !$b instanceof TemplateMixedType && $b->getSubtractedType() === null) {
276:	return $b;
277:	}
278:
279:	// union(X, X) = X — for equal array operands, not just identical
280:	// ones. For arrays the general path below is not a no-op on a pair
281:	// that already denotes a single type: it rebuilds them from
282:	// ArrayType::getIterableKeyType(), which coerces a subtracted key
283:	// type down to the plain array-key union, so `array<mixed~'User',
284:	// mixed>` unioned with an equal instance came back as plain
285:	// `array`. Whether the two operands happen to be the same object
286:	// must not decide the result.
287:	//
288:	// Non-array operands keep taking the general path. It is lossless
289:	// for them, and it has to stay in charge because `equals()` is
290:	// weaker than interchangeability for some types: a benevolent
291:	// `(int\|string)` equals a plain `int\|string` and `Foo=final` equals
292:	// `Foo`, and there the general path deliberately yields the wider
293:	// operand rather than whichever one was passed first.
294:	if ($a === $b \|\| ($a->equals($b) && $a->isArray()->yes())) {
295:	return $a;
296:	}
297:	}
298:
299:	// A member passed more than once contributes nothing; dropping the
300:	// repeats up front keeps the pairwise comparison below from paying for
301:	// them (array_values() of a shape unions the same value type per slot).
302:	if ($typesCount > 2) {
303:	$seenTypes = [];
304:	$uniqueTypes = [];
305:	foreach ($types as $type) {
306:	$typeId = spl_object_id($type);
307:	if (isset($seenTypes[$typeId])) {
308:	continue;
309:	}
310:	$seenTypes[$typeId] = true;
311:	$uniqueTypes[] = $type;
312:	}
313:	if (count($uniqueTypes) === 1) {
314:	return $uniqueTypes[0];
315:	}
316:	if (count($uniqueTypes) === 2) {
317:	return self::union($uniqueTypes[0], $uniqueTypes[1]);
318:	}
319:	$types = $uniqueTypes;
320:	}
321:
322:	$alreadyNormalized = [];
323:	$alreadyNormalizedCounter = 0;
324:
325:	$benevolentTypes = [];
326:	$neverCount = 0;
327:	$markers = [];
328:	// transform A \| (B \| C) to A \| B \| C - in one pass, a union's members are
329:	// never unions, implicit never or implicit mixed themselves
330:	$flattenedTypes = [];
331:	foreach ($types as $type) {
332:	if (
333:	$type instanceof MixedType
334:	&& !$type->isExplicitMixed()
335:	&& !$type instanceof TemplateMixedType
336:	&& $type->getSubtractedType() === null
337:	) {
338:	return $type;
339:	}
340:	if ($type instanceof UnresolvedTemplateArgumentType && !$type->isClosureSignature()) {
341:	$markers = self::addMarker($markers, $type);
342:	continue;
343:	}
344:	if ($type instanceof NeverType && !$type->isExplicit()) {
345:	$neverCount++;
346:	$flattenedTypes[] = $type;
347:	continue;
348:	}
349:	if ($type instanceof BenevolentUnionType) {
350:	if ($type instanceof TemplateType) {
351:	$flattenedTypes[] = $type;
352:	continue;
353:	}
354:	foreach ($type->getTypes() as $benevolentInnerType) {
355:	$benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
356:	$flattenedTypes[] = $benevolentInnerType;
357:	}
358:	continue;
359:	}
360:	if (!($type instanceof UnionType) \|\| $type instanceof TemplateType) {
361:	$flattenedTypes[] = $type;
362:	continue;
363:	}
364:
365:	$typesInner = $type->getTypes();
366:	$alreadyNormalized[$alreadyNormalizedCounter] = $typesInner;
367:	$alreadyNormalizedCounter++;
368:	foreach ($typesInner as $innerType) {
369:	if ($innerType instanceof UnresolvedTemplateArgumentType && !$innerType->isClosureSignature()) {
370:	$markers = self::addMarker($markers, $innerType);
371:	continue;
372:	}
373:	$flattenedTypes[] = $innerType;
374:	}
375:	}
376:	if ($markers !== []) {
377:	return self::unionWithMarkers(self::union(...$flattenedTypes), $markers);
378:	}
379:	$types = $flattenedTypes;
380:	$typesCount = count($types);
381:
382:	// Bulk-remove implicit NeverTypes (skipped during the loop above)
383:	if ($neverCount > 0) {
384:	if ($neverCount === $typesCount) {
385:	return new NeverType();
386:	}
387:
388:	$filtered = [];
389:	for ($i = 0; $i < $typesCount; $i++) {
390:	if ($types[$i] instanceof NeverType && !$types[$i]->isExplicit()) {
391:	continue;
392:	}
393:	$filtered[] = $types[$i];
394:	}
395:	$types = $filtered;
396:	$typesCount = count($types);
397:
398:	if ($typesCount === 0) {
399:	return new NeverType();
400:	}
401:	if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
402:	return $types[0];
403:	}
404:	if ($typesCount === 2) {
405:	return self::union($types[0], $types[1]);
406:	}
407:	}
408:
409:	if ($typesCount === 0) {
410:	return new NeverType();
411:	}
412:
413:	if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
414:	return $types[0];
415:	}
416:
417:	$arrayTypes = [];
418:	$scalarTypes = [];
419:	$hasGenericScalarTypes = [];
420:	$enumCaseTypes = [];
421:	$integerRangeTypes = [];
422:	for ($i = 0; $i < $typesCount; $i++) {
423:	if ($types[$i]->isConstantScalarValue()->yes()) {
424:	$type = $types[$i];
425:	$scalarTypes[get_class($type)][$type->describe(VerbosityLevel::cache())] = $type;
426:	unset($types[$i]);
427:	continue;
428:	}
429:
430:	// only a type containing every value of the scalar (not T of int, 1&T)
431:	// absorbs all the constants of that scalar
432:	if ($types[$i]->isBoolean()->yes()) {
433:	if ($types[$i]->isSuperTypeOf(new BooleanType())->yes()) {
434:	$hasGenericScalarTypes[ConstantBooleanType::class] = true;
435:	}
436:	} elseif ($types[$i]->isFloat()->yes()) {
437:	if ($types[$i]->isSuperTypeOf(new FloatType())->yes()) {
438:	$hasGenericScalarTypes[ConstantFloatType::class] = true;
439:	}
440:	} elseif ($types[$i]->isInteger()->yes() && !$types[$i] instanceof IntegerRangeType) {
441:	if ($types[$i]->isSuperTypeOf(new IntegerType())->yes()) {
442:	$hasGenericScalarTypes[ConstantIntegerType::class] = true;
443:	}
444:	} elseif ($types[$i]->isString()->yes() && $types[$i]->isClassString()->no() && TypeUtils::getAccessoryTypes($types[$i]) === []) {
445:	$hasGenericScalarTypes[ConstantStringType::class] = true;
446:	} else {
447:	$enumCase = $types[$i]->getEnumCaseObject();
448:	if ($enumCase !== null) {
449:	$enumCaseTypes[$types[$i]->describe(VerbosityLevel::cache())] = $types[$i];
450:
451:	unset($types[$i]);
452:	continue;
453:	}
454:	}
455:
456:	if ($types[$i] instanceof IntegerRangeType) {
457:	$integerRangeTypes[] = $types[$i];
458:	unset($types[$i]);
459:
460:	continue;
461:	}
462:
463:	if (!$types[$i]->isArray()->yes()) {
464:	continue;
465:	}
466:
467:	$arrayTypes[] = $types[$i];
468:	unset($types[$i]);
469:	}
470:
471:	$enumCaseTypes = array_values($enumCaseTypes);
472:	usort(
473:	$integerRangeTypes,
474:	static fn (IntegerRangeType $a, IntegerRangeType $b): int => ($a->getMin() ?? PHP_INT_MIN) <=> ($b->getMin() ?? PHP_INT_MIN)
475:	?: ($a->getMax() ?? PHP_INT_MAX) <=> ($b->getMax() ?? PHP_INT_MAX),
476:	);
477:	// array_merge() hands the first array back as it is when the second one
478:	// is empty, so the keys the bucketing above unset must be renumbered here
479:	$types = array_merge(array_values($types), $integerRangeTypes);
480:	$typesCount = count($types);
481:
482:	if (isset($scalarTypes[IntersectionType::class])) {
483:	$scalarTypes[IntersectionType::class] = self::reduceRefinedConstantScalars($scalarTypes[IntersectionType::class], $scalarTypes);
484:	}
485:
486:	foreach ($scalarTypes as $classType => $scalarTypeItems) {
487:	if (isset($hasGenericScalarTypes[$classType])) {
488:	unset($scalarTypes[$classType]);
489:	continue;
490:	}
491:	if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
492:	$types[] = new BooleanType();
493:	$typesCount++;
494:	unset($scalarTypes[$classType]);
495:	continue;
496:	}
497:
498:	$scalarTypeItems = array_values($scalarTypeItems);
499:	$scalarTypeItemsCount = count($scalarTypeItems);
500:	for ($i = 0; $i < $typesCount; $i++) {
501:	for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
502:	$compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
503:	if ($compareResult === null) {
504:	continue;
505:	}
506:
507:	[$a, $b] = $compareResult;
508:	if ($a !== null) {
509:	$types[$i] = $a;
510:	array_splice($scalarTypeItems, $j, 1);
511:	$scalarTypeItemsCount--;
512:	$j = -1;
513:	continue 1;
514:	}
515:	if ($b !== null) {
516:	$scalarTypeItems[$j] = $b;
517:	array_splice($types, $i--, 1);
518:	$typesCount--;
519:	continue 2;
520:	}
521:	}
522:	}
523:
524:	$scalarTypes[$classType] = $scalarTypeItems;
525:	}
526:
527:	if (count($types) > 16) {
528:	$newTypes = [];
529:	foreach ($types as $type) {
530:	$newTypes[$type->describe(VerbosityLevel::cache())] = $type;
531:	}
532:	$types = array_values($newTypes);
533:	}
534:
535:	$types = array_merge(
536:	$types,
537:	self::processArrayTypes($arrayTypes),
538:	);
539:	$typesCount = count($types);
540:
541:	// transform A \| A to A
542:	// transform A \| never to A
543:	for ($i = 0; $i < $typesCount; $i++) {
544:	for ($j = $i + 1; $j < $typesCount; $j++) {
545:	if (self::isAlreadyNormalized($alreadyNormalized, $types[$i], $types[$j])) {
546:	continue;
547:	}
548:	$compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
549:	if ($compareResult === null) {
550:	continue;
551:	}
552:
553:	[$a, $b] = $compareResult;
554:	if ($a !== null) {
555:	$types[$i] = $a;
556:	array_splice($types, $j--, 1);
557:	$typesCount--;
558:	continue 1;
559:	}
560:	if ($b !== null) {
561:	$types[$j] = $b;
562:	array_splice($types, $i--, 1);
563:	$typesCount--;
564:	continue 2;
565:	}
566:	}
567:	}
568:
569:	$enumCasesCount = count($enumCaseTypes);
570:	for ($i = 0; $i < $typesCount; $i++) {
571:	for ($j = 0; $j < $enumCasesCount; $j++) {
572:	$compareResult = self::compareTypesInUnion($types[$i], $enumCaseTypes[$j]);
573:	if ($compareResult === null) {
574:	continue;
575:	}
576:
577:	[$a, $b] = $compareResult;
578:	if ($a !== null) {
579:	$types[$i] = $a;
580:	array_splice($enumCaseTypes, $j--, 1);
581:	$enumCasesCount--;
582:	continue 1;
583:	}
584:	if ($b !== null) {
585:	$enumCaseTypes[$j] = $b;
586:	array_splice($types, $i--, 1);
587:	$typesCount--;
588:	continue 2;
589:	}
590:	}
591:	}
592:
593:	foreach ($enumCaseTypes as $enumCaseType) {
594:	$types[] = $enumCaseType;
595:	$typesCount++;
596:	}
597:
598:	foreach ($scalarTypes as $scalarTypeItems) {
599:	foreach ($scalarTypeItems as $scalarType) {
600:	$types[] = $scalarType;
601:	$typesCount++;
602:	}
603:	}
604:
605:	if ($typesCount === 0) {
606:	return new NeverType();
607:	}
608:	if ($typesCount === 1) {
609:	return $types[0];
610:	}
611:
612:	if ($benevolentTypes !== []) {
613:	$tempTypes = $types;
614:	foreach ($tempTypes as $i => $type) {
615:	if (!isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
616:	break;
617:	}
618:
619:	unset($tempTypes[$i]);
620:	}
621:
622:	if ($tempTypes === []) {
623:	return new BenevolentUnionType(array_values($types), true);
624:	}
625:	}
626:
627:	return new UnionType(array_values($types), true);
628:	}
629:
630:	/**
631:	* An unresolved template argument is a variable of its site, not the type it
632:	* currently stands for: unresolved(int) from two different sites are two
633:	* variables, and neither int nor the other variable absorbs it. Only the same
634:	* variable merges - into the wider of the two inferred types.
635:	*
636:	* @param array<string, UnresolvedTemplateArgumentType> $markers
637:	* @return array<string, UnresolvedTemplateArgumentType>
638:	*/
639:	private static function addMarker(array $markers, UnresolvedTemplateArgumentType $marker): array
640:	{
641:	$key = spl_object_id($marker->getSite()) . '#' . $marker->getTemplateName();
642:	$existing = $markers[$key] ?? null;
643:	if ($existing === null \|\| $existing === $marker) {
644:	$markers[$key] = $marker;
645:	return $markers;
646:	}
647:
648:	$existingInitial = $existing->getInitialType();
649:	$initial = $marker->getInitialType();
650:	if ($existingInitial === null \|\| $initial === null) {
651:	// nothing inferred stands for the template's default or bound
652:	$markers[$key] = $existingInitial === null ? $existing : $marker;
653:	return $markers;
654:	}
655:
656:	$markers[$key] = $existing->withInitialType(self::union($existingInitial, $initial));
657:
658:	return $markers;
659:	}
660:
661:	/**
662:	* @param array<string, UnresolvedTemplateArgumentType> $markers
663:	*/
664:	private static function unionWithMarkers(Type $rest, array $markers): Type
665:	{
666:	if ($rest instanceof MixedType && !$rest instanceof TemplateMixedType && $rest->getSubtractedType() === null) {
667:	return $rest;
668:	}
669:
670:	if ($rest instanceof NeverType) {
671:	$members = [];
672:	} elseif ($rest instanceof UnionType && !$rest instanceof TemplateType) {
673:	$members = $rest->getTypes();
674:	} else {
675:	$members = [$rest];
676:	}
677:	foreach ($markers as $marker) {
678:	$members[] = $marker;
679:	}
680:	if (count($members) === 1) {
681:	return $members[0];
682:	}
683:	if ($rest instanceof BenevolentUnionType && !$rest instanceof TemplateType) {
684:	return new BenevolentUnionType($members, true);
685:	}
686:
687:	return new UnionType($members, true);
688:	}
689:
690:	/**
691:	* @param array<int, Type[]> $alreadyNormalized
692:	*/
693:	private static function isAlreadyNormalized(array $alreadyNormalized, Type $a, Type $b): bool
694:	{
695:	foreach ($alreadyNormalized as $normalizedTypes) {
696:	foreach ($normalizedTypes as $i => $normalizedType) {
697:	if ($normalizedType !== $a) {
698:	continue;
699:	}
700:
701:	foreach ($normalizedTypes as $j => $anotherNormalizedType) {
702:	if ($i === $j) {
703:	continue;
704:	}
705:	if ($anotherNormalizedType === $b) {
706:	return true;
707:	}
708:	}
709:	}
710:	}
711:
712:	return false;
713:	}
714:
715:	/**
716:	* Scalar buckets are compared only against the non-scalar union members, which
717:	* is correct for plain constants (distinct values are disjoint) but not for
718:	* constants refined by another type ('Foo'&hasMethod(bar)). Those are absorbed
719:	* here by the plain constant of the same value, or by a less refined
720:	* intersection of the same value. Values never need to be compared across.
721:	*
722:	* @param array<string, Type> $intersections
723:	* @param array<string, array<string, Type>> $scalarTypes
724:	* @return array<string, Type>
725:	*/
726:	private static function reduceRefinedConstantScalars(array $intersections, array $scalarTypes): array
727:	{
728:	$byValue = [];
729:	foreach ($intersections as $key => $intersection) {
730:	$constants = $intersection->getConstantScalarTypes();
731:	if (count($constants) !== 1) {
732:	continue;
733:	}
734:	$valueKey = $constants[0]->describe(VerbosityLevel::cache());
735:	$plain = $scalarTypes[get_class($constants[0])][$valueKey] ?? null;
736:	if ($plain !== null && $plain->isSuperTypeOf($intersection)->yes()) {
737:	unset($intersections[$key]);
738:	continue;
739:	}
740:	$byValue[get_class($constants[0])][$valueKey][] = $key;
741:	}
742:
743:	foreach ($byValue as $valueKeys) {
744:	foreach ($valueKeys as $keys) {
745:	$keysCount = count($keys);
746:	for ($i = 0; $i < $keysCount; $i++) {
747:	for ($j = 0; $j < $keysCount; $j++) {
748:	if ($i === $j \|\| !isset($intersections[$keys[$i]], $intersections[$keys[$j]])) {
749:	continue;
750:	}
751:	if (!$intersections[$keys[$i]]->isSuperTypeOf($intersections[$keys[$j]])->yes()) {
752:	continue;
753:	}
754:	unset($intersections[$keys[$j]]);
755:	}
756:	}
757:	}
758:	}
759:
760:	return $intersections;
761:	}
762:
763:	/**
764:	* @return array{Type, null}\|array{null, Type}\|null
765:	*/
766:	private static function compareTypesInUnion(Type $a, Type $b): ?array
767:	{
768:	if ($a instanceof IntegerRangeType) {
769:	$type = $a->tryUnion($b);
770:	if ($type !== null) {
771:	$a = $type;
772:	return [$a, null];
773:	}
774:	}
775:	if ($b instanceof IntegerRangeType) {
776:	$type = $b->tryUnion($a);
777:	if ($type !== null) {
778:	$b = $type;
779:	return [null, $b];
780:	}
781:	}
782:	if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
783:	return null;
784:	}
785:	if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
786:	if ($a->getOffsetType()->equals($b->getOffsetType())) {
787:	return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
788:	}
789:	}
790:	if ($a instanceof IntersectionType && $b instanceof IntersectionType) {
791:	$merged = self::mergeIntersectionsForUnion($a, $b);
792:	if ($merged !== null) {
793:	return [$merged, null];
794:	}
795:	}
796:	if ($a->isConstantArray()->yes() && $b->isConstantArray()->yes()) {
797:	return null;
798:	}
799:
800:	// simplify string[] \| int[] to (string\|int)[]
801:	if ($a instanceof IterableType && $b instanceof IterableType) {
802:	return [
803:	new IterableType(
804:	self::union($a->getIterableKeyType(), $b->getIterableKeyType()),
805:	self::union($a->getIterableValueType(), $b->getIterableValueType()),
806:	),
807:	null,
808:	];
809:	}
810:
811:	if ($a instanceof SubtractableType) {
812:	$typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
813:	if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
814:	$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
815:	} else {
816:	$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
817:	}
818:	if ($isSuperType->yes()) {
819:	$a = self::intersectWithSubtractedType($a, $b);
820:	return [$a, null];
821:	}
822:	}
823:
824:	if ($b instanceof SubtractableType) {
825:	$typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
826:	if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
827:	$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
828:	} else {
829:	$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
830:	}
831:	if ($isSuperType->yes()) {
832:	$b = self::intersectWithSubtractedType($b, $a);
833:	return [null, $b];
834:	}
835:	}
836:
837:	if ($b->isSuperTypeOf($a)->yes()) {
838:	return [null, $b];
839:	}
840:
841:	if ($a->isSuperTypeOf($b)->yes()) {
842:	return [$a, null];
843:	}
844:
845:	if (
846:	$a instanceof ConstantStringType
847:	) {
848:	if ($a->getValue() === '') {
849:	$description = $b->describe(VerbosityLevel::value());
850:	if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
851:	return [null, self::intersect(
852:	new StringType(),
853:	...self::getAccessoryCaseStringTypes($b),
854:	)];
855:	}
856:	}
857:
858:	if ($a->getValue() === '0') {
859:	$nonEmpty = self::downgradeNonFalsyStringToNonEmpty($b);
860:	if ($nonEmpty !== null) {
861:	return [null, $nonEmpty];
862:	}
863:	}
864:	}
865:
866:	if (
867:	$b instanceof ConstantStringType
868:	) {
869:	if ($b->getValue() === '') {
870:	$description = $a->describe(VerbosityLevel::value());
871:	if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
872:	return [self::intersect(
873:	new StringType(),
874:	...self::getAccessoryCaseStringTypes($a),
875:	), null];
876:	}
877:	}
878:
879:	if ($b->getValue() === '0') {
880:	$nonEmpty = self::downgradeNonFalsyStringToNonEmpty($a);
881:	if ($nonEmpty !== null) {
882:	return [$nonEmpty, null];
883:	}
884:	}
885:	}
886:
887:	// numeric-string \| non-decimal-int-string → string (preserving common accessories)
888:	// Works because decimal-int-string ⊂ numeric-string, so together they cover all strings
889:	if ($a->isString()->yes() && $b->isString()->yes()) {
890:	$decimalIntString = new IntersectionType([new StringType(), new AccessoryDecimalIntegerStringType()]);
891:	if ($b->isDecimalIntegerString()->no()) {
892:	$bBase = self::removeDecimalIntStringAccessory($b);
893:	if ($bBase->isSuperTypeOf($a)->yes() && $a->isSuperTypeOf($decimalIntString)->yes()) {
894:	return [null, $bBase];
895:	}
896:	}
897:	if ($a->isDecimalIntegerString()->no()) {
898:	$aBase = self::removeDecimalIntStringAccessory($a);
899:	if ($aBase->isSuperTypeOf($b)->yes() && $b->isSuperTypeOf($decimalIntString)->yes()) {
900:	return [$aBase, null];
901:	}
902:	}
903:	}
904:
905:	return null;
906:	}
907:
908:	/**
909:	* @return list<Type>
910:	*/
911:	private static function getAccessoryCaseStringTypes(Type $type): array
912:	{
913:	$accessory = [];
914:	if ($type->isLowercaseString()->yes()) {
915:	$accessory[] = new AccessoryLowercaseStringType();
916:	}
917:	if ($type->isUppercaseString()->yes()) {
918:	$accessory[] = new AccessoryUppercaseStringType();
919:	}
920:
921:	return $accessory;
922:	}
923:
924:	/**
925:	* Turns a non-falsy-string type into its non-empty-string counterpart by
926:	* downgrading the non-falsy accessory while preserving every other accessory
927:	* (numeric-string, decimal-int-string, lowercase-string, …). Used to simplify
928:	* `'0' \| non-falsy-string-X` back to `non-empty-string-X`, since `"0"` is the
929:	* only value that separates the two. Returns null when $type is not a
930:	* non-constant non-falsy-string built from an intersection.
931:	*/
932:	private static function downgradeNonFalsyStringToNonEmpty(Type $type): ?Type
933:	{
934:	if (!$type instanceof IntersectionType \|\| $type->isNonFalsyString()->no()) {
935:	return null;
936:	}
937:
938:	$newTypes = [];
939:	$found = false;
940:	foreach ($type->getTypes() as $innerType) {
941:	if ($innerType instanceof AccessoryNonFalsyStringType) {
942:	$found = true;
943:	continue;
944:	}
945:
946:	$newTypes[] = $innerType;
947:	}
948:
949:	if (!$found) {
950:	return null;
951:	}
952:
953:	$withoutNonFalsy = self::intersect(...$newTypes);
954:	if ($withoutNonFalsy->isNonEmptyString()->yes()) {
955:	return $withoutNonFalsy;
956:	}
957:
958:	return self::intersect($withoutNonFalsy, new AccessoryNonEmptyStringType());
959:	}
960:
961:	private static function removeDecimalIntStringAccessory(Type $type): Type
962:	{
963:	if (!$type instanceof IntersectionType) {
964:	return $type;
965:	}
966:
967:	return self::intersect(...array_filter(
968:	$type->getTypes(),
969:	static fn (Type $t): bool => !$t instanceof AccessoryDecimalIntegerStringType,
970:	));
971:	}
972:
973:	private static function unionWithSubtractedType(
974:	Type $type,
975:	?Type $subtractedType,
976:	): Type
977:	{
978:	if ($subtractedType === null) {
979:	return $type;
980:	}
981:
982:	if ($subtractedType instanceof SubtractableType) {
983:	$withoutSubtracted = $subtractedType->getTypeWithoutSubtractedType();
984:	if ($withoutSubtracted->isSuperTypeOf($type)->yes()) {
985:	$subtractedSubtractedType = $subtractedType->getSubtractedType();
986:	if ($subtractedSubtractedType === null) {
987:	return new NeverType();
988:	}
989:
990:	return self::intersect($type, $subtractedSubtractedType);
991:	}
992:	}
993:
994:	if ($type instanceof SubtractableType) {
995:	$subtractedType = $type->getSubtractedType() === null
996:	? $subtractedType
997:	: self::union($type->getSubtractedType(), $subtractedType);
998:
999:	$subtractedType = self::intersect(
1000:	$type->getTypeWithoutSubtractedType(),
1001:	$subtractedType,
1002:	);
1003:	if ($subtractedType instanceof NeverType) {
1004:	$subtractedType = null;
1005:	}
1006:
1007:	return $type->changeSubtractedType($subtractedType);
1008:	}
1009:
1010:	if ($subtractedType->isSuperTypeOf($type)->yes()) {
1011:	return new NeverType();
1012:	}
1013:
1014:	return self::remove($type, $subtractedType);
1015:	}
1016:
1017:	private static function intersectWithSubtractedType(
1018:	SubtractableType $a,
1019:	Type $b,
1020:	): Type
1021:	{
1022:	if ($a->getSubtractedType() === null \|\| $b instanceof NeverType) {
1023:	return $a;
1024:	}
1025:
1026:	if ($b instanceof IntersectionType) {
1027:	$subtractableTypes = [];
1028:	foreach ($b->getTypes() as $innerType) {
1029:	if (!$innerType instanceof SubtractableType) {
1030:	continue;
1031:	}
1032:
1033:	$subtractableTypes[] = $innerType;
1034:	}
1035:
1036:	if (count($subtractableTypes) === 0) {
1037:	return $a->getTypeWithoutSubtractedType();
1038:	}
1039:
1040:	$subtractedTypes = [];
1041:	foreach ($subtractableTypes as $subtractableType) {
1042:	if ($subtractableType->getSubtractedType() === null) {
1043:	continue;
1044:	}
1045:
1046:	$subtractedTypes[] = $subtractableType->getSubtractedType();
1047:	}
1048:
1049:	if (count($subtractedTypes) === 0) {
1050:	return $a->getTypeWithoutSubtractedType();
1051:
1052:	}
1053:
1054:	$subtractedType = self::union(...$subtractedTypes);
1055:	} else {
1056:	$isBAlreadySubtracted = $a->getSubtractedType()->isSuperTypeOf($b);
1057:
1058:	if ($isBAlreadySubtracted->no()) {
1059:	return $a;
1060:	} elseif ($isBAlreadySubtracted->yes()) {
1061:	$subtractedType = self::remove($a->getSubtractedType(), $b);
1062:
1063:	if (
1064:	$subtractedType instanceof NeverType
1065:	\|\| !$subtractedType->isSuperTypeOf($b)->no()
1066:	) {
1067:	$subtractedType = null;
1068:	}
1069:
1070:	return $a->changeSubtractedType($subtractedType);
1071:	} elseif ($b instanceof SubtractableType) {
1072:	$subtractedType = $b->getSubtractedType();
1073:	if ($subtractedType === null) {
1074:	return $a->getTypeWithoutSubtractedType();
1075:	}
1076:	} else {
1077:	$subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
1078:	if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
1079:	return $a->getTypeWithoutSubtractedType();
1080:	}
1081:	$subtractedType = new MixedType(subtractedType: $b);
1082:	}
1083:	}
1084:
1085:	$subtractedType = self::intersect(
1086:	$a->getSubtractedType(),
1087:	$subtractedType,
1088:	);
1089:	if ($subtractedType instanceof NeverType) {
1090:	$subtractedType = null;
1091:	}
1092:
1093:	return $a->changeSubtractedType($subtractedType);
1094:	}
1095:
1096:	/**
1097:	* @param Type[] $arrayTypes
1098:	* @return list<Type>
1099:	*/
1100:	private static function processArrayAccessoryTypes(array $arrayTypes): array
1101:	{
1102:	$isIterableAtLeastOnce = [];
1103:	$accessoryTypes = [];
1104:	foreach ($arrayTypes as $i => $arrayType) {
1105:	$isIterableAtLeastOnce[] = $arrayType->isIterableAtLeastOnce();
1106:
1107:	if ($arrayType instanceof IntersectionType) {
1108:	foreach ($arrayType->getTypes() as $innerType) {
1109:	if ($innerType instanceof TemplateType) {
1110:	break;
1111:	}
1112:	if (!($innerType instanceof AccessoryType) && !($innerType instanceof CallableType)) {
1113:	continue;
1114:	}
1115:	if ($innerType instanceof HasOffsetType) {
1116:	$innerType = new HasOffsetValueType($innerType->getOffsetType(), $arrayType->getIterableValueType());
1117:	}
1118:	if ($innerType instanceof HasOffsetValueType) {
1119:	$accessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][$i] = $innerType;
1120:	continue;
1121:	}
1122:
1123:	$accessoryTypes[$innerType->describe(VerbosityLevel::cache())][$i] = $innerType;
1124:	}
1125:	}
1126:
1127:	if (!$arrayType->isConstantArray()->yes()) {
1128:	continue;
1129:	}
1130:	$constantArrays = $arrayType->getConstantArrays();
1131:
1132:	foreach ($constantArrays as $constantArray) {
1133:	if ($constantArray->isList()->yes()) {
1134:	$list = new AccessoryArrayListType();
1135:	$accessoryTypes[$list->describe(VerbosityLevel::cache())][$i] = $list;
1136:	}
1137:
1138:	if (!$constantArray->isIterableAtLeastOnce()->yes()) {
1139:	continue;
1140:	}
1141:
1142:	$nonEmpty = new NonEmptyArrayType();
1143:	$accessoryTypes[$nonEmpty->describe(VerbosityLevel::cache())][$i] = $nonEmpty;
1144:	}
1145:	}
1146:
1147:	$commonAccessoryTypes = [];
1148:	$arrayTypeCount = count($arrayTypes);
1149:	foreach ($accessoryTypes as $accessoryType) {
1150:	if (count($accessoryType) !== $arrayTypeCount) {
1151:	$firstKey = array_key_first($accessoryType);
1152:	if ($accessoryType[$firstKey] instanceof OversizedArrayType) {
1153:	$commonAccessoryTypes[] = $accessoryType[$firstKey];
1154:	}
1155:	continue;
1156:	}
1157:
1158:	if ($accessoryType[0] instanceof HasOffsetValueType) {
1159:	$commonAccessoryTypes[] = self::union(...$accessoryType);
1160:	continue;
1161:	}
1162:
1163:	$commonAccessoryTypes[] = $accessoryType[0];
1164:	}
1165:
1166:	if (TrinaryLogic::createYes()->and(...$isIterableAtLeastOnce)->yes()) {
1167:	$commonAccessoryTypes[] = new NonEmptyArrayType();
1168:	}
1169:
1170:	return $commonAccessoryTypes;
1171:	}
1172:
1173:	/**
1174:	* @param Type[] $arrayTypes
1175:	*/
1176:	private static function findEmptyArrayNextToOversizedArray(array $arrayTypes): ?Type
1177:	{
1178:	if (count($arrayTypes) < 2) {
1179:	return null;
1180:	}
1181:
1182:	$emptyArray = null;
1183:	$hasOversizedArray = false;
1184:	foreach ($arrayTypes as $arrayType) {
1185:	if ($arrayType->isOversizedArray()->yes()) {
1186:	$hasOversizedArray = true;
1187:	} elseif ($emptyArray === null && $arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
1188:	$emptyArray = $arrayType;
1189:	}
1190:	}
1191:
1192:	return $hasOversizedArray ? $emptyArray : null;
1193:	}
1194:
1195:	/**
1196:	* @param list<Type> $arrayTypes
1197:	* @return Type[]
1198:	*/
1199:	private static function processArrayTypes(array $arrayTypes): array
1200:	{
1201:	if ($arrayTypes === []) {
1202:	return [];
1203:	}
1204:
1205:	$emptyArray = self::findEmptyArrayNextToOversizedArray($arrayTypes);
1206:	if ($emptyArray !== null) {
1207:	// like reduceArrays() does when it generalizes to an oversized array:
1208:	// folded into it, the empty array would be lost to the oversized
1209:	// accessory, which accepts only arrays that hold something
1210:	$otherArrayTypes = [];
1211:	foreach ($arrayTypes as $arrayType) {
1212:	if ($arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
1213:	continue;
1214:	}
1215:	$otherArrayTypes[] = $arrayType;
1216:	}
1217:
1218:	return [$emptyArray, ...self::processArrayTypes($otherArrayTypes)];
1219:	}
1220:
1221:	$accessoryTypes = self::processArrayAccessoryTypes($arrayTypes);
1222:
1223:	if (count($arrayTypes) === 1) {
1224:	return [
1225:	self::intersect(...$arrayTypes, ...$accessoryTypes),
1226:	];
1227:	}
1228:
1229:	$keyTypesForGeneralArray = [];
1230:	$valueTypesForGeneralArray = [];
1231:	$generalArrayOccurred = false;
1232:	$seenConstantKeyTypes = [];
1233:
1234:	foreach ($arrayTypes as $arrayType) {
1235:	$constantArrays = $arrayType->getConstantArrays();
1236:	$isConstantArray = $constantArrays !== [];
1237:
1238:	if (!$isConstantArray) {
1239:	foreach ($arrayType->getArrays() as $type) {
1240:	$keyTypesForGeneralArray[] = $type->getIterableKeyType();
1241:	$valueTypesForGeneralArray[] = $type->getItemType();
1242:	$generalArrayOccurred = true;
1243:	}
1244:	continue;
1245:	}
1246:
1247:	foreach ($constantArrays as $constantArray) {
1248:	$valueTypes = $constantArray->getValueTypes();
1249:	foreach ($constantArray->getKeyTypes() as $i => $keyType) {
1250:	$valueTypesForGeneralArray[] = $valueTypes[$i];
1251:
1252:	$keyTypeValue = $keyType->getValue();
1253:	if (array_key_exists($keyTypeValue, $seenConstantKeyTypes)) {
1254:	continue;
1255:	}
1256:	$seenConstantKeyTypes[$keyTypeValue] = true;
1257:	$keyTypesForGeneralArray[] = $keyType;
1258:	}
1259:	}
1260:	}
1261:
1262:	if ($generalArrayOccurred) {
1263:	$reducedArrayTypes = self::reduceArrays($arrayTypes, false);
1264:	if (count($reducedArrayTypes) === 1) {
1265:	return [self::intersect($reducedArrayTypes[0], ...$accessoryTypes)];
1266:	}
1267:
1268:	$templateArrayType = null;
1269:	foreach ($arrayTypes as $arrayType) {
1270:	if (!$arrayType instanceof TemplateArrayType) {
1271:	$templateArrayType = null;
1272:	break;
1273:	}
1274:
1275:	if ($templateArrayType !== null) {
1276:	continue;
1277:	}
1278:
1279:	$templateArrayType = $arrayType;
1280:	}
1281:
1282:	$arrayType = new ArrayType(
1283:	self::union(...$keyTypesForGeneralArray),
1284:	self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
1285:	);
1286:
1287:	if ($templateArrayType !== null) {
1288:	$arrayType = new TemplateArrayType(
1289:	$templateArrayType->getScope(),
1290:	$templateArrayType->getStrategy(),
1291:	$templateArrayType->getVariance(),
1292:	$templateArrayType->getName(),
1293:	$arrayType,
1294:	$templateArrayType->getDefault(),
1295:	);
1296:	}
1297:
1298:	return [
1299:	self::intersect($arrayType, ...$accessoryTypes),
1300:	];
1301:	}
1302:
1303:	$reducedArrayTypes = self::optimizeConstantArrays(self::reduceArrays($arrayTypes, true));
1304:	foreach ($reducedArrayTypes as $idx => $reducedArray) {
1305:	$applied = $accessoryTypes;
1306:	if ($reducedArray->isIterableAtLeastOnce()->no()) {
1307:	// Empty arrays cannot satisfy non-empty / oversized constraints —
1308:	// applying those accessories would produce a contradictory intersection
1309:	// (e.g. `array{}&oversized-array`) that rejects the very value it
1310:	// represents, breaking the super-type contract of the union.
1311:	$applied = array_values(array_filter(
1312:	$applied,
1313:	static fn (Type $t): bool => !($t instanceof OversizedArrayType) && !($t instanceof NonEmptyArrayType),
1314:	));
1315:	}
1316:	$reducedArrayTypes[$idx] = self::intersect($reducedArray, ...$applied);
1317:	}
1318:	return $reducedArrayTypes;
1319:	}
1320:
1321:	/**
1322:	* @param Type[] $types
1323:	* @return Type[]
1324:	*/
1325:	private static function optimizeConstantArrays(array $types): array
1326:	{
1327:	$constantArrayValuesCount = self::countConstantArrayValueTypes($types);
1328:
1329:	if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1330:	return $types;
1331:	}
1332:
1333:	// Stage 1: collapse same-key-set ConstantArrayType variants per-position
1334:	// before the (lossy) generalization below kicks in. Variants with the
1335:	// same key signature mergeWith losslessly into a single shape whose
1336:	// values at each position are the union of the variants' values, which
1337:	// drops the count while keeping the per-position structure. Without
1338:	// this, a list of N similarly-shaped records (e.g. bug-7963) hits the
1339:	// limit and the generalization decomposes every nested constant array
1340:	// into a flat `non-empty-list<unionOfAllPositionValues>`, losing the
1341:	// shape entirely.
1342:	$signatureGroups = [];
1343:	$nonConstantTypes = [];
1344:	foreach ($types as $idx => $type) {
1345:	if (!$type instanceof ConstantArrayType) {
1346:	$nonConstantTypes[$idx] = $type;
1347:	continue;
1348:	}
1349:	$signatureParts = [];
1350:	$signatureParts[] = $type->isList()->yes() ? 'L' : 'A';
1351:	foreach ($type->getKeyTypes() as $i => $keyType) {
1352:	$signatureParts[] = ($type->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
1353:	}
1354:	$signatureGroups[implode(',', $signatureParts)][] = $type;
1355:	}
1356:	if ($signatureGroups !== []) {
1357:	$collapsed = $nonConstantTypes;
1358:	$anyMerged = false;
1359:	foreach ($signatureGroups as $group) {
1360:	if (count($group) === 1) {
1361:	$collapsed[] = $group[0];
1362:	continue;
1363:	}
1364:	$merged = $group[0];
1365:	for ($i = 1, $count = count($group); $i < $count; $i++) {
1366:	$merged = $merged->mergeWith($group[$i]);
1367:	}
1368:	$collapsed[] = $merged;
1369:	$anyMerged = true;
1370:	}
1371:	if ($anyMerged) {
1372:	$types = array_values($collapsed);
1373:	$constantArrayValuesCount = self::countConstantArrayValueTypes($types);
1374:	if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1375:	return $types;
1376:	}
1377:	}
1378:	}
1379:
1380:	$results = [];
1381:	$emptyArrays = [];
1382:	$eachIsOversized = true;
1383:	foreach ($types as $type) {
1384:	if ($type->isConstantArray()->yes() && $type->isIterableAtLeastOnce()->no()) {
1385:	$emptyArrays[] = $type;
1386:	continue;
1387:	}
1388:
1389:	$isOversized = false;
1390:	$result = TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$isOversized): Type {
1391:	if (!$type instanceof ConstantArrayType) {
1392:	return $traverse($type);
1393:	}
1394:
1395:	if ($type->isIterableAtLeastOnce()->no()) {
1396:	return $type;
1397:	}
1398:
1399:	$isOversized = true;
1400:
1401:	$isList = true;
1402:	$valueTypes = [];
1403:	$keyTypes = [];
1404:	$nextAutoIndex = 0;
1405:	$innerValueTypes = $type->getValueTypes();
1406:	foreach ($type->getKeyTypes() as $i => $innerKeyType) {
1407:	if (!$innerKeyType instanceof ConstantIntegerType) {
1408:	$isList = false;
1409:	} elseif ($innerKeyType->getValue() !== $nextAutoIndex) {
1410:	$isList = false;
1411:	$nextAutoIndex = $innerKeyType->getValue() + 1;
1412:	} else {
1413:	$nextAutoIndex++;
1414:	}
1415:
1416:	$generalizedKeyType = $innerKeyType->generalize(GeneralizePrecision::moreSpecific());
1417:	$keyTypes[$generalizedKeyType->describe(VerbosityLevel::precise())] = $generalizedKeyType;
1418:
1419:	// Inner traversal of the value position. Two subtleties, both
1420:	// of which produced types that failed to be super-types of
1421:	// their contributors:
1422:	// - Empty constant arrays must be left alone; wrapping them
1423:	// builds a contradictory `array{}&oversized-array`.
1424:	// - Fall through via `$innerTraverse`, not the outer
1425:	// `$traverse`. The outer callback fully generalizes a
1426:	// sealed `ConstantArrayType` into `array<intKey, V>&...`,
1427:	// which is correct at the top level but wrong inside a
1428:	// value position: it would treat a sealed `array{a: 1}`
1429:	// reached via `array{}\|array{a: 1}` differently from one
1430:	// reached directly, leaving `processArrayTypes` with a
1431:	// mix of shapes it cannot unify cleanly.
1432:	$generalizedValueType = TypeTraverser::map($innerValueTypes[$i], static function (Type $type, callable $innerTraverse): Type {
1433:	if ($type instanceof ConstantArrayType && $type->isIterableAtLeastOnce()->no()) {
1434:	return $type;
1435:	}
1436:
1437:	if ($type instanceof ArrayType \|\| $type instanceof ConstantArrayType) {
1438:	return new IntersectionType([$type, new OversizedArrayType()]);
1439:	}
1440:
1441:	if ($type instanceof ConstantScalarType) {
1442:	return $type->generalize(GeneralizePrecision::moreSpecific());
1443:	}
1444:
1445:	return $innerTraverse($type);
1446:	});
1447:	$valueTypes[$generalizedValueType->describe(VerbosityLevel::precise())] = $generalizedValueType;
1448:	}
1449:
1450:	$keyType = TypeCombinator::union(...array_values($keyTypes));
1451:	$valueType = TypeCombinator::union(...array_values($valueTypes));
1452:
1453:	$accessories = [];
1454:	if ($isList) {
1455:	$accessories[] = new AccessoryArrayListType();
1456:	}
1457:	$accessories[] = new NonEmptyArrayType();
1458:	$accessories[] = new OversizedArrayType();
1459:
1460:	return self::intersect(new ArrayType($keyType, $valueType), ...$accessories);
1461:	});
1462:
1463:	if (!$isOversized) {
1464:	$eachIsOversized = false;
1465:	}
1466:
1467:	$results[] = $result;
1468:	}
1469:
1470:	if ($eachIsOversized && $results !== []) {
1471:	$eachIsList = true;
1472:	$keyTypes = [];
1473:	$valueTypes = [];
1474:	foreach ($results as $result) {
1475:	$keyTypes[] = $result->getIterableKeyType();
1476:	$valueTypes[] = $result->getIterableValueType();
1477:	if ($result->isList()->yes()) {
1478:	continue;
1479:	}
1480:	$eachIsList = false;
1481:	}
1482:
1483:	$keyType = self::union(...$keyTypes);
1484:	$valueType = self::union(...$valueTypes);
1485:
1486:	if ($valueType instanceof UnionType && count($valueType->getTypes()) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1487:	$valueType = $valueType->generalize(GeneralizePrecision::lessSpecific());
1488:	}
1489:
1490:	$accessories = [];
1491:	if ($eachIsList) {
1492:	$accessories[] = new AccessoryArrayListType();
1493:	}
1494:	$accessories[] = new NonEmptyArrayType();
1495:	$accessories[] = new OversizedArrayType();
1496:
1497:	return [...$emptyArrays, self::intersect(new ArrayType($keyType, $valueType), ...$accessories)];
1498:	}
1499:
1500:	return [...$emptyArrays, ...$results];
1501:	}
1502:
1503:	/**
1504:	* @param Type[] $types
1505:	*/
1506:	public static function countConstantArrayValueTypes(array $types): int
1507:	{
1508:	$constantArrayValuesCount = 0;
1509:	foreach ($types as $type) {
1510:	TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$constantArrayValuesCount): Type {
1511:	if ($type instanceof ConstantArrayType) {
1512:	$constantArrayValuesCount += count($type->getValueTypes());
1513:	}
1514:
1515:	return $traverse($type);
1516:	});
1517:	}
1518:	return $constantArrayValuesCount;
1519:	}
1520:
1521:	/**
1522:	* The value at each key of the array that is a single constant scalar, null
1523:	* when the array has real unsealed extras - its keys-supersets are then not
1524:	* decided by the known keys alone.
1525:	*
1526:	* @return array<int\|string, scalar\|null>\|null
1527:	*/
1528:	private static function getConstantScalarValuesByKey(ConstantArrayType $array): ?array
1529:	{
1530:	$unsealed = $array->getUnsealedTypes();
1531:	if ($unsealed !== null && !($unsealed[0] instanceof NeverType && $unsealed[0]->isExplicit())) {
1532:	return null;
1533:	}
1534:
1535:	$values = [];
1536:	$valueTypes = $array->getValueTypes();
1537:	foreach ($array->getKeyTypes() as $i => $keyType) {
1538:	if (!$valueTypes[$i]->isConstantScalarValue()->yes()) {
1539:	continue;
1540:	}
1541:	$constantScalarValues = $valueTypes[$i]->getConstantScalarValues();
1542:	if (count($constantScalarValues) !== 1) {
1543:	continue;
1544:	}
1545:	$values[$keyType->getValue()] = $constantScalarValues[0];
1546:	}
1547:
1548:	return $values;
1549:	}
1550:
1551:	/**
1552:	* Whether two arrays differ in enough keys holding different single constant
1553:	* scalars that neither can be a keys-superset of the other: each such key
1554:	* pairs two disjoint values, and ConstantArrayType::isKeysSupersetOf() lets
1555:	* at most one key's values be unrelated - only when both arrays have the
1556:	* same number of keys, two or more.
1557:	*
1558:	* @param array<int\|string, scalar\|null>\|null $a
1559:	* @param array<int\|string, scalar\|null>\|null $b
1560:	*/
1561:	private static function haveDisjointConstantScalarValues(?array $a, ?array $b, bool $oneUnrelatedKeyAllowed): bool
1562:	{
1563:	if ($a === null \|\| $b === null) {
1564:	return false;
1565:	}
1566:	if (count($a) > count($b)) {
1567:	[$a, $b] = [$b, $a];
1568:	}
1569:
1570:	$differing = 0;
1571:	foreach ($a as $key => $value) {
1572:	if (!array_key_exists($key, $b) \|\| $b[$key] === $value) {
1573:	continue;
1574:	}
1575:	$differing++;
1576:	if ($differing >= 2 \|\| !$oneUnrelatedKeyAllowed) {
1577:	return true;
1578:	}
1579:	}
1580:
1581:	return false;
1582:	}
1583:
1584:	/**
1585:	* @param list<Type> $constantArrays
1586:	* @return list<Type>
1587:	*/
1588:	private static function reduceArrays(array $constantArrays, bool $preserveTaggedUnions): array
1589:	{
1590:	$newArrays = [];
1591:	$arraysToProcess = [];
1592:	$emptyArray = null;
1593:	foreach ($constantArrays as $constantArray) {
1594:	if (!$constantArray->isConstantArray()->yes()) {
1595:	// This is an optimization for current use-case of $preserveTaggedUnions=false, where we need
1596:	// one constant array as a result, or we generalize the $constantArrays.
1597:	if (!$preserveTaggedUnions) {
1598:	return $constantArrays;
1599:	}
1600:	$newArrays[] = $constantArray;
1601:	continue;
1602:	}
1603:
1604:	if ($constantArray->isIterableAtLeastOnce()->no()) {
1605:	$emptyArray = $constantArray;
1606:	continue;
1607:	}
1608:
1609:	$arraysToProcess = array_merge($arraysToProcess, $constantArray->getConstantArrays());
1610:	}
1611:
1612:	if ($emptyArray !== null) {
1613:	if ($preserveTaggedUnions && $emptyArray instanceof ConstantArrayType) {
1614:	// Let the empty array participate in merging — the passes below will absorb
1615:	// it into any array that already accepts [] (all-optional keys, compatible
1616:	// unsealed extras). If no such array exists, it remains as-is in the result.
1617:	$arraysToProcess[] = $emptyArray;
1618:	} else {
1619:	$newArrays[] = $emptyArray;
1620:	}
1621:	}
1622:
1623:	$arraysToProcessPerKey = [];
1624:	foreach ($arraysToProcess as $i => $arrayToProcess) {
1625:	foreach ($arrayToProcess->getKeyTypes() as $keyType) {
1626:	$arraysToProcessPerKey[$keyType->getValue()][] = $i;
1627:	}
1628:	}
1629:
1630:	// the single constant scalar value at each key of the arrays without
1631:	// real unsealed extras (whose supersets the key/value shape decides)
1632:	$constantScalarValues = [];
1633:	if ($preserveTaggedUnions) {
1634:	foreach ($arraysToProcess as $i => $arrayToProcess) {
1635:	$constantScalarValues[$i] = self::getConstantScalarValuesByKey($arrayToProcess);
1636:	}
1637:	}
1638:
1639:	$eligibleCombinations = [];
1640:
1641:	foreach ($arraysToProcessPerKey as $arrays) {
1642:	for ($i = 0, $arraysCount = count($arrays); $i < $arraysCount - 1; $i++) {
1643:	for ($j = $i + 1; $j < $arraysCount; $j++) {
1644:	$eligibleCombinations[$arrays[$i]][$arrays[$j]] ??= 0;
1645:	$eligibleCombinations[$arrays[$i]][$arrays[$j]]++;
1646:	}
1647:	}
1648:	}
1649:
1650:	foreach ($eligibleCombinations as $i => $other) {
1651:	if (!array_key_exists($i, $arraysToProcess)) {
1652:	continue;
1653:	}
1654:
1655:	foreach ($other as $j => $overlappingKeysCount) {
1656:	if (!array_key_exists($j, $arraysToProcess)) {
1657:	continue;
1658:	}
1659:
1660:	// Merge two single-key arrays sharing the same key when their value
1661:	// types union into a single type (not a UnionType). This is lossless
1662:	// and prevents exponential union growth when narrowing nested
1663:	// ArrayDimFetch expressions on a ConstantArrayType parent (see
1664:	// phpstan/phpstan#14462).
1665:	if (
1666:	$preserveTaggedUnions
1667:	&& $overlappingKeysCount === 1
1668:	&& count($arraysToProcess[$i]->getKeyTypes()) === 1
1669:	&& count($arraysToProcess[$j]->getKeyTypes()) === 1
1670:	) {
1671:	$iValueType = $arraysToProcess[$i]->getValueTypes()[0];
1672:	$jValueType = $arraysToProcess[$j]->getValueTypes()[0];
1673:	$unionValueType = self::union($iValueType, $jValueType);
1674:	if (!$unionValueType instanceof UnionType) {
1675:	$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
1676:	$constantScalarValues[$j] = null;
1677:	unset($arraysToProcess[$i]);
1678:	continue 2;
1679:	}
1680:	}
1681:
1682:	if (
1683:	$preserveTaggedUnions
1684:	&& self::haveDisjointConstantScalarValues(
1685:	$constantScalarValues[$i] ?? null,
1686:	$constantScalarValues[$j] ?? null,
1687:	count($arraysToProcess[$i]->getKeyTypes()) === count($arraysToProcess[$j]->getKeyTypes())
1688:	&& count($arraysToProcess[$i]->getKeyTypes()) >= 2,
1689:	)
1690:	) {
1691:	// neither array is a keys-superset of the other
1692:	continue;
1693:	}
1694:
1695:	if (
1696:	$preserveTaggedUnions
1697:	&& $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
1698:	&& $arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])
1699:	) {
1700:	$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
1701:	$constantScalarValues[$j] = null;
1702:	unset($arraysToProcess[$i]);
1703:	continue 2;
1704:	}
1705:
1706:	if (
1707:	$preserveTaggedUnions
1708:	&& $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
1709:	&& $arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])
1710:	) {
1711:	$arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
1712:	$constantScalarValues[$i] = null;
1713:	unset($arraysToProcess[$j]);
1714:	continue 1;
1715:	}
1716:
1717:	if (
1718:	!$preserveTaggedUnions
1719:	// both arrays have same keys
1720:	&& $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
1721:	&& $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
1722:	) {
1723:	$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
1724:	unset($arraysToProcess[$i]);
1725:	continue 2;
1726:	}
1727:	}
1728:	}
1729:
1730:	// Second pass: merge pairs that the eligibleCombinations loop above couldn't touch.
1731:	// That loop only considers pairs sharing at least one known key, so it never fires
1732:	// for e.g. `array{}` ∪ `array{a?: 1}` (disjoint, one empty) or for two
1733:	// unsealed-extras arrays with disjoint required keys. Both collapse losslessly if
1734:	// one side's extras or optional-key shape can absorb the other side's content.
1735:	//
1736:	// Performance: two sealed, non-empty, no-extras arrays with disjoint keys cannot
1737:	// merge losslessly (legacyIsKeysSupersetOf returns false immediately on the first
1738:	// missing key). Skip those pairs via a candidate flag to avoid an O(n²) scan that
1739:	// dominated analyse time on files accumulating many sealed ConstantArrayType
1740:	// variants (bug-7581 / bug-8146a). A pair is worth checking only if at least one
1741:	// side is (a) empty, or (b) has real unsealed extras, or (c) has optional keys —
1742:	// the last case covers the narrowing shape used by e.g. array_key_exists checks
1743:	// over large optional-key shapes (bug-14032).
1744:	$indices = array_keys($arraysToProcess);
1745:	$indicesCount = count($indices);
1746:	if ($indicesCount > 1) {
1747:	$candidateFlags = [];
1748:	foreach ($indices as $idx) {
1749:	$arr = $arraysToProcess[$idx];
1750:	$unsealed = $arr->getUnsealedTypes();
1751:	if ($unsealed === null) {
1752:	$candidateFlags[$idx] = false;
1753:	continue;
1754:	}
1755:	[$unsealedKey] = $unsealed;
1756:	$hasRealExtras = !($unsealedKey instanceof NeverType && $unsealedKey->isExplicit());
1757:	if ($hasRealExtras) {
1758:	$candidateFlags[$idx] = true;
1759:	continue;
1760:	}
1761:	$keyTypesCount = count($arr->getKeyTypes());
1762:	if ($keyTypesCount === 0) {
1763:	$candidateFlags[$idx] = true;
1764:	continue;
1765:	}
1766:	$hasOptional = count($arr->getOptionalKeys()) > 0;
1767:	$candidateFlags[$idx] = $hasOptional;
1768:	}
1769:
1770:	for ($ii = 0; $ii < $indicesCount - 1; $ii++) {
1771:	$i = $indices[$ii];
1772:	if (!array_key_exists($i, $arraysToProcess)) {
1773:	continue;
1774:	}
1775:	if ($arraysToProcess[$i]->getUnsealedTypes() === null) {
1776:	continue;
1777:	}
1778:	for ($jj = $ii + 1; $jj < $indicesCount; $jj++) {
1779:	$j = $indices[$jj];
1780:	if (!array_key_exists($j, $arraysToProcess)) {
1781:	continue;
1782:	}
1783:	if (!$candidateFlags[$i] && !$candidateFlags[$j]) {
1784:	continue;
1785:	}
1786:	if ($arraysToProcess[$j]->getUnsealedTypes() === null) {
1787:	continue;
1788:	}
1789:	if ($arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])) {
1790:	$arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
1791:	unset($arraysToProcess[$i]);
1792:	continue 2;
1793:	}
1794:	if (!$arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])) {
1795:	continue;
1796:	}
1797:
1798:	$arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
1799:	unset($arraysToProcess[$j]);
1800:	}
1801:	}
1802:	}
1803:
1804:	// Final pass: if merging left us with a ConstantArrayType that has no known keys
1805:	// but has real unsealed extras, collapse it to a plain ArrayType (mirrors the same
1806:	// logic in ConstantArrayTypeBuilder::getArray — but applies to results produced by
1807:	// ConstantArrayType::mergeWith, which doesn't go through the builder).
1808:	foreach ($arraysToProcess as $idx => $arr) {
1809:	if (count($arr->getKeyTypes()) !== 0) {
1810:	continue;
1811:	}
1812:	$unsealed = $arr->getUnsealedTypes();
1813:	if ($unsealed === null) {
1814:	continue;
1815:	}
1816:	[$unsealedKey, $unsealedValue] = $unsealed;
1817:	if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
1818:	continue;
1819:	}
1820:	$newArrays[] = new ArrayType($unsealedKey, $unsealedValue);
1821:	unset($arraysToProcess[$idx]);
1822:	}
1823:
1824:	// Final pass: collapse the loop-accumulator pattern where each iteration
1825:	// produced a longer non-empty list variant. When several non-empty list
1826:	// ConstantArrayTypes survive earlier merging and together push the
1827:	// constant-array value count past the limit, fold them into a single
1828:	// non-empty-list<unionValueType> so the result stays bounded without
1829:	// going through the lossier optimizeConstantArrays generalization.
1830:	// Skip when every list variant shares one key signature — those collapse
1831:	// losslessly via the stage 1 same-key-set merge in optimizeConstantArrays
1832:	// (each position keeps its own value union), which is strictly more
1833:	// precise than this flat fold.
1834:	if ($preserveTaggedUnions && count($arraysToProcess) > 1) {
1835:	$listVariantIndices = [];
1836:	$listValueTypes = [];
1837:	$listVariants = [];
1838:	$listVariantSignatures = [];
1839:	foreach ($arraysToProcess as $idx => $arr) {
1840:	if (!$arr->isList()->yes() \|\| !$arr->isIterableAtLeastOnce()->yes()) {
1841:	continue;
1842:	}
1843:	$listVariantIndices[] = $idx;
1844:	$listValueTypes[] = $arr->getIterableValueType();
1845:	$listVariants[] = $arr;
1846:	$signatureParts = [];
1847:	foreach ($arr->getKeyTypes() as $i => $keyType) {
1848:	$signatureParts[] = ($arr->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
1849:	}
1850:	$listVariantSignatures[implode(',', $signatureParts)] = true;
1851:	}
1852:	if (
1853:	count($listVariantIndices) >= 2
1854:	&& count($listVariantSignatures) >= 2
1855:	&& self::countConstantArrayValueTypes($listVariants) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT
1856:	) {
1857:	$mergedValueType = self::union(...$listValueTypes);
1858:	$merged = self::intersect(
1859:	new ArrayType(new IntegerType(), $mergedValueType),
1860:	new NonEmptyArrayType(),
1861:	new AccessoryArrayListType(),
1862:	);
1863:	$newArrays[] = $merged;
1864:	foreach ($listVariantIndices as $idx) {
1865:	unset($arraysToProcess[$idx]);
1866:	}
1867:	}
1868:	}
1869:
1870:	return array_merge($newArrays, $arraysToProcess);
1871:	}
1872:
1873:	/**
1874:	* Fast path for intersect(): the intersection of two unions whose members are all
1875:	* finite, mutually-disjoint values (constant scalars and/or enum cases) is their
1876:	* identity-keyed set intersection. Returns null when either union has a member that is
1877:	* not such a value, in which case the caller falls back to the general A & (B\|C)
1878:	* distribution.
1879:	*/
1880:	/** @phpstan-assert-if-true UnionType $type */
1881:	private static function isPlainOrBenevolentUnion(Type $type): bool
1882:	{
1883:	$class = get_class($type);
1884:
1885:	return $class === UnionType::class \|\| $class === BenevolentUnionType::class;
1886:	}
1887:
1888:	private static function intersectFiniteUnions(UnionType $a, UnionType $b): ?Type
1889:	{
1890:	$membersA = self::finiteUnionMembers($a);
1891:	if ($membersA === null) {
1892:	return null;
1893:	}
1894:
1895:	$membersB = self::finiteUnionMembers($b);
1896:	if ($membersB === null) {
1897:	return null;
1898:	}
1899:
1900:	$common = [];
1901:	foreach ($membersA as $key => $member) {
1902:	if (!array_key_exists($key, $membersB)) {
1903:	continue;
1904:	}
1905:
1906:	$common[] = $member;
1907:	}
1908:
1909:	if ($common === []) {
1910:	return new NeverType();
1911:	}
1912:
1913:	return self::union(...$common);
1914:	}
1915:
1916:	/**
1917:	* The union's members keyed by identity, or null when the fast path does not apply.
1918:	*
1919:	* FiniteTypeSet does the keying and the union caches it; on top of that, intersect()
1920:	* hands one of the two members back instead of only comparing them, so a constant string
1921:	* that is also a class-string is not interchangeable with a same-valued one that is not -
1922:	* the class-string flag would be lost. Such unions go the slow way.
1923:	*
1924:	* @return array<string, Type>\|null
1925:	*/
1926:	private static function finiteUnionMembers(UnionType $union): ?array
1927:	{
1928:	$finiteTypeSet = $union->getFiniteTypeSet();
1929:	if ($finiteTypeSet === null \|\| !$finiteTypeSet->isComplete()) {
1930:	return null;
1931:	}
1932:
1933:	return $finiteTypeSet->getMembers();
1934:	}
1935:
1936:	public static function intersect(Type ...$types): Type
1937:	{
1938:	if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
1939:	return TypeCombinatorCache::intersect(...$types);
1940:	}
1941:
1942:	return self::doIntersect(...$types);
1943:	}
1944:
1945:	/** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
1946:	public static function doIntersect(Type ...$types): Type
1947:	{
1948:	$typesCount = count($types);
1949:	if ($typesCount === 0) {
1950:	return new NeverType();
1951:	}
1952:
1953:	$types = array_values($types);
1954:	if ($typesCount === 1) {
1955:	return $types[0];
1956:	}
1957:
1958:	// The comparator only orders UnionTypes relative to each other, so sorting is
1959:	// a no-op unless there are at least two of them. Skip it in the common case.
1960:	$unionTypesCount = 0;
1961:	foreach ($types as $type) {
1962:	if ($type instanceof NeverType && !$type->isExplicit()) {
1963:	return $type;
1964:	}
1965:	if (!$type instanceof UnionType) {
1966:	continue;
1967:	}
1968:	$unionTypesCount++;
1969:	}
1970:
1971:	// Fast path: the intersection of two unions whose members are all finite,
1972:	// mutually-disjoint values (constant scalars and/or enum cases) is their
1973:	// identity-keyed set intersection (O(n)), avoiding the O(n*m) `A & (B\|C)`
1974:	// distribution + union rebuild below. A benevolent union is the one the
1975:	// distribution walks first and the benevolence it gives the result is kept;
1976:	// the template union types keep their dedicated handling.
1977:	if (
1978:	$typesCount === 2
1979:	&& self::isPlainOrBenevolentUnion($types[0])
1980:	&& self::isPlainOrBenevolentUnion($types[1])
1981:	) {
1982:	[$a, $b] = $types;
1983:	if ($b instanceof BenevolentUnionType && !$a instanceof BenevolentUnionType) {
1984:	[$a, $b] = [$b, $a];
1985:	}
1986:	$finiteIntersection = self::intersectFiniteUnions($a, $b);
1987:	if ($finiteIntersection !== null) {
1988:	return $a instanceof BenevolentUnionType ? TypeUtils::toBenevolentUnion($finiteIntersection) : $finiteIntersection;
1989:	}
1990:	}
1991:
1992:	$sortTypes = static function (Type $a, Type $b): int {
1993:	if (!$a instanceof UnionType \|\| !$b instanceof UnionType) {
1994:	return 0;
1995:	}
1996:
1997:	if ($a instanceof TemplateType) {
1998:	return -1;
1999:	}
2000:	if ($b instanceof TemplateType) {
2001:	return 1;
2002:	}
2003:
2004:	if ($a instanceof BenevolentUnionType) {
2005:	return -1;
2006:	}
2007:	if ($b instanceof BenevolentUnionType) {
2008:	return 1;
2009:	}
2010:
2011:	return 0;
2012:	};
2013:	if ($unionTypesCount >= 2) {
2014:	usort($types, $sortTypes);
2015:	}
2016:	// transform A & (B \| C) to (A & B) \| (A & C)
2017:	foreach ($types as $i => $type) {
2018:	if (!$type instanceof UnionType) {
2019:	continue;
2020:	}
2021:
2022:	$topLevelUnionSubTypes = [];
2023:	$innerTypes = $type->getTypes();
2024:	$innerUnionTypesCount = 0;
2025:	foreach ($innerTypes as $innerType) {
2026:	if (!$innerType instanceof UnionType) {
2027:	continue;
2028:	}
2029:	$innerUnionTypesCount++;
2030:	if ($innerUnionTypesCount >= 2) {
2031:	break;
2032:	}
2033:	}
2034:	if ($innerUnionTypesCount >= 2) {
2035:	usort($innerTypes, $sortTypes);
2036:	}
2037:	$slice1 = array_slice($types, 0, $i);
2038:	$slice2 = array_slice($types, $i + 1);
2039:	foreach ($innerTypes as $innerUnionSubType) {
2040:	$topLevelUnionSubTypes[] = self::intersect(
2041:	$innerUnionSubType,
2042:	...$slice1,
2043:	...$slice2,
2044:	);
2045:	}
2046:
2047:	$union = self::union(...$topLevelUnionSubTypes);
2048:	if ($union instanceof NeverType) {
2049:	return $union;
2050:	}
2051:
2052:	if ($type instanceof BenevolentUnionType) {
2053:	$union = TypeUtils::toBenevolentUnion($union);
2054:	}
2055:
2056:	if ($type instanceof TemplateUnionType \|\| $type instanceof TemplateBenevolentUnionType) {
2057:	$union = TemplateTypeFactory::create(
2058:	$type->getScope(),
2059:	$type->getName(),
2060:	$union,
2061:	$type->getVariance(),
2062:	$type->getStrategy(),
2063:	$type->getDefault(),
2064:	);
2065:	}
2066:
2067:	return $union;
2068:	}
2069:
2070:	$newTypes = [];
2071:	$hasOffsetValueTypeCount = 0;
2072:	$typesCount = count($types);
2073:	$typesNeedSorting = false;
2074:	$hasPropertyType = false;
2075:	for ($i = 0; $i < $typesCount; $i++) {
2076:	$type = $types[$i];
2077:
2078:	if ($type instanceof SubtractableType \|\| $type instanceof ConstantArrayType) {
2079:	$typesNeedSorting = true;
2080:	}
2081:
2082:	if ($type instanceof HasPropertyType) {
2083:	$hasPropertyType = true;
2084:	}
2085:
2086:	if ($type instanceof IntersectionType && !$type instanceof TemplateType) {
2087:	// transform A & (B & C) to A & B & C
2088:	array_splice($types, $i--, 1, $type->getTypes());
2089:	$typesCount = count($types);
2090:	} elseif ($type instanceof HasOffsetValueType) {
2091:	$hasOffsetValueTypeCount++;
2092:	} else {
2093:	$newTypes[] = $type;
2094:	}
2095:	}
2096:
2097:	if ($hasOffsetValueTypeCount > 32) {
2098:	$newTypes[] = new OversizedArrayType();
2099:	$types = $newTypes;
2100:	$typesCount = count($types);
2101:	}
2102:
2103:	if ($typesNeedSorting) {
2104:	usort($types, static function (Type $a, Type $b): int {
2105:	// move subtractables with subtracts before those without to avoid losing them in the union logic
2106:	if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
2107:	return -1;
2108:	}
2109:	if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
2110:	return 1;
2111:	}
2112:
2113:	if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
2114:	return -1;
2115:	}
2116:	if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
2117:	return 1;
2118:	}
2119:
2120:	return 0;
2121:	});
2122:	}
2123:
2124:	// Resolve object-shape optional keys that a HasPropertyType asserts are present before the
2125:	// reduction loop below. In that loop the generic supertype dedup can drop a HasPropertyType
2126:	// as redundant against a dynamic-property class such as stdClass (which reports every
2127:	// property as present) before it is ever paired with the object shape. Which of the two
2128:	// fires first depends on the member order, so the collapse runs here, where order does not
2129:	// change the result of what is meant to be an order-independent value. Gated on the presence
2130:	// of a HasPropertyType so the common intersection pays only the flag check set above.
2131:	if ($hasPropertyType) {
2132:	for ($i = 0; $i < $typesCount; $i++) {
2133:	for ($j = $i + 1; $j < $typesCount; $j++) {
2134:	if (
2135:	$types[$i] instanceof ObjectShapeType
2136:	&& $types[$j] instanceof HasPropertyType
2137:	&& !$types[$i]->hasInstanceProperty($types[$j]->getPropertyName())->no()
2138:	) {
2139:	$types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
2140:	array_splice($types, $j--, 1);
2141:	$typesCount--;
2142:	continue;
2143:	}
2144:
2145:	if (
2146:	$types[$j] instanceof ObjectShapeType
2147:	&& $types[$i] instanceof HasPropertyType
2148:	&& !$types[$j]->hasInstanceProperty($types[$i]->getPropertyName())->no()
2149:	) {
2150:	$types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
2151:	array_splice($types, $i--, 1);
2152:	$typesCount--;
2153:	continue 2;
2154:	}
2155:	}
2156:	}
2157:	}
2158:
2159:	// transform IntegerType & ConstantIntegerType to ConstantIntegerType
2160:	// transform Child & Parent to Child
2161:	// transform Object & ~null to Object
2162:	// transform A & A to A
2163:	// transform int[] & string to never
2164:	// transform callable & int to never
2165:	// transform A & ~A to never
2166:	// transform int & string to never
2167:	for ($i = 0; $i < $typesCount; $i++) {
2168:	for ($j = $i + 1; $j < $typesCount; $j++) {
2169:	if ($types[$j] instanceof SubtractableType) {
2170:	$typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
2171:
2172:	if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
2173:	$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
2174:	} else {
2175:	$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
2176:	}
2177:	if ($isSuperTypeSubtractableA->yes()) {
2178:	$types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
2179:	array_splice($types, $j--, 1);
2180:	$typesCount--;
2181:	continue 1;
2182:	}
2183:	}
2184:
2185:	if ($types[$i] instanceof SubtractableType) {
2186:	$typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
2187:
2188:	if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
2189:	$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
2190:	} else {
2191:	$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
2192:	}
2193:	if ($isSuperTypeSubtractableB->yes()) {
2194:	$types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
2195:	array_splice($types, $i--, 1);
2196:	$typesCount--;
2197:	continue 2;
2198:	}
2199:	}
2200:
2201:	if ($types[$i] instanceof IntegerRangeType) {
2202:	$intersectionType = $types[$i]->tryIntersect($types[$j]);
2203:	if ($intersectionType !== null) {
2204:	$types[$j] = $intersectionType;
2205:	array_splice($types, $i--, 1);
2206:	$typesCount--;
2207:	continue 2;
2208:	}
2209:	}
2210:
2211:	if ($types[$j] instanceof IterableType) {
2212:	$isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
2213:	} else {
2214:	$isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
2215:	}
2216:
2217:	if ($isSuperTypeA->yes()) {
2218:	array_splice($types, $j--, 1);
2219:	$typesCount--;
2220:	continue;
2221:	}
2222:
2223:	if ($types[$i] instanceof IterableType) {
2224:	$isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
2225:	} else {
2226:	$isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
2227:	}
2228:
2229:	if ($isSuperTypeB->maybe()) {
2230:	if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
2231:	$types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
2232:	array_splice($types, $j--, 1);
2233:	$typesCount--;
2234:	continue;
2235:	}
2236:
2237:	if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
2238:	$types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
2239:	array_splice($types, $i--, 1);
2240:	$typesCount--;
2241:	continue 2;
2242:	}
2243:
2244:	if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof AccessoryArrayListType) {
2245:	$types[$i] = $types[$i]->makeList();
2246:	array_splice($types, $j--, 1);
2247:	$typesCount--;
2248:	continue;
2249:	}
2250:
2251:	if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof AccessoryArrayListType) {
2252:	$types[$j] = $types[$j]->makeList();
2253:	array_splice($types, $i--, 1);
2254:	$typesCount--;
2255:	continue 2;
2256:	}
2257:
2258:	if (
2259:	$types[$i] instanceof ConstantArrayType
2260:	&& $types[$j] instanceof NonEmptyArrayType
2261:	&& (count($types[$i]->getKeyTypes()) === 1 \|\| $types[$i]->isList()->yes())
2262:	&& $types[$i]->isOptionalKey(0)
2263:	&& !$types[$i]->isUnsealed()->yes()
2264:	) {
2265:	$types[$i] = $types[$i]->makeOffsetRequired($types[$i]->getKeyTypes()[0]);
2266:	array_splice($types, $j--, 1);
2267:	$typesCount--;
2268:	continue;
2269:	}
2270:
2271:	if (
2272:	$types[$j] instanceof ConstantArrayType
2273:	&& $types[$i] instanceof NonEmptyArrayType
2274:	&& (count($types[$j]->getKeyTypes()) === 1 \|\| $types[$j]->isList()->yes())
2275:	&& $types[$j]->isOptionalKey(0)
2276:	&& !$types[$j]->isUnsealed()->yes()
2277:	) {
2278:	$types[$j] = $types[$j]->makeOffsetRequired($types[$j]->getKeyTypes()[0]);
2279:	array_splice($types, $i--, 1);
2280:	$typesCount--;
2281:	continue 2;
2282:	}
2283:
2284:	if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
2285:	$offsetType = $types[$j]->getOffsetType();
2286:	$valueType = $types[$j]->getValueType();
2287:	$newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
2288:	if ($newValueType instanceof NeverType) {
2289:	return $newValueType;
2290:	}
2291:	$types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
2292:	array_splice($types, $j--, 1);
2293:	$typesCount--;
2294:	continue;
2295:	}
2296:
2297:	if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
2298:	$offsetType = $types[$i]->getOffsetType();
2299:	$valueType = $types[$i]->getValueType();
2300:	$newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
2301:	if ($newValueType instanceof NeverType) {
2302:	return $newValueType;
2303:	}
2304:
2305:	$types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
2306:	array_splice($types, $i--, 1);
2307:	$typesCount--;
2308:	continue 2;
2309:	}
2310:
2311:	if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
2312:	array_splice($types, $j--, 1);
2313:	$typesCount--;
2314:	continue;
2315:	}
2316:
2317:	if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
2318:	array_splice($types, $i--, 1);
2319:	$typesCount--;
2320:	continue 2;
2321:	}
2322:
2323:	$constArrayIsI = $types[$i] instanceof ConstantArrayType && ($types[$j] instanceof ArrayType \|\| $types[$j] instanceof ConstantArrayType);
2324:	$constArrayIsJ = $types[$j] instanceof ConstantArrayType && ($types[$i] instanceof ArrayType \|\| $types[$i] instanceof ConstantArrayType);
2325:	if ($constArrayIsI \|\| $constArrayIsJ) {
2326:	$constArray = $constArrayIsI ? $types[$i] : $types[$j];
2327:	$otherArray = $constArrayIsI ? $types[$j] : $types[$i];
2328:
2329:	if (
2330:	$otherArray instanceof ConstantArrayType
2331:	&& !$constArray->isUnsealed()->maybe()
2332:	&& !$otherArray->isUnsealed()->maybe()
2333:	) {
2334:	$merged = self::intersectDefiniteConstantArrays($constArray, $otherArray);
2335:	if ($merged instanceof NeverType) {
2336:	if ($merged->getReason() === null) {
2337:	$reasons = array_merge($isSuperTypeA->getReasons(), $isSuperTypeB->getReasons());
2338:	if ($reasons !== []) {
2339:	return new NeverType(reason: $reasons[0]);
2340:	}
2341:	}
2342:	return $merged;
2343:	}
2344:	$newArrayType = $merged;
2345:	} else {
2346:	$newArray = ConstantArrayTypeBuilder::createEmpty();
2347:	// Preserve unsealed extras from the source shape so the
2348:	// rebuild doesn't silently turn `array{k: int, ...} & X`
2349:	// into a sealed `array{k: int}` — intersect with the other
2350:	// side's iterable key/value so the open part keeps both
2351:	// sides' refinements.
2352:	$constUnsealed = $constArray->getUnsealedTypes();
2353:	if ($constUnsealed !== null && $constArray->isUnsealed()->yes()) {
2354:	$newUnsealedKey = self::intersect($constUnsealed[0], $otherArray->getIterableKeyType());
2355:	$newUnsealedValue = self::intersect($constUnsealed[1], $otherArray->getIterableValueType());
2356:	if (!$newUnsealedKey instanceof NeverType && !$newUnsealedValue instanceof NeverType) {
2357:	$newArray->makeUnsealed($newUnsealedKey, $newUnsealedValue);
2358:	}
2359:	}
2360:	$valueTypes = $constArray->getValueTypes();
2361:	foreach ($constArray->getKeyTypes() as $k => $keyType) {
2362:	$hasOffset = $otherArray->hasOffsetValueType($keyType);
2363:	if ($hasOffset->no()) {
2364:	continue;
2365:	}
2366:	$newArray->setOffsetValueType(
2367:	self::intersect($keyType, $otherArray->getIterableKeyType()),
2368:	self::intersect($valueTypes[$k], $otherArray->getOffsetValueType($keyType)),
2369:	$constArray->isOptionalKey($k) && !$hasOffset->yes(),
2370:	);
2371:	}
2372:	$newArrayType = $newArray->getArray();
2373:	if ($constArray->isList()->yes()) {
2374:	$newArrayType = self::intersect($newArrayType, new AccessoryArrayListType());
2375:	}
2376:	}
2377:
2378:	if ($constArrayIsI) {
2379:	$types[$i] = $newArrayType;
2380:	array_splice($types, $j, 1);
2381:	} else {
2382:	$types[$j] = $newArrayType;
2383:	array_splice($types, $i--, 1);
2384:	}
2385:	$typesCount--;
2386:	continue 2;
2387:	}
2388:
2389:	if (
2390:	($types[$i] instanceof ArrayType \|\| $types[$i] instanceof ConstantArrayType \|\| $types[$i] instanceof IterableType) &&
2391:	($types[$j] instanceof ArrayType \|\| $types[$j] instanceof ConstantArrayType \|\| $types[$j] instanceof IterableType)
2392:	) {
2393:	$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
2394:	$itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
2395:	if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
2396:	$types[$j] = new IterableType($keyType, $itemType);
2397:	} else {
2398:	$types[$j] = new ArrayType($keyType, $itemType);
2399:	}
2400:	array_splice($types, $i--, 1);
2401:	$typesCount--;
2402:	continue 2;
2403:	}
2404:
2405:	if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
2406:	$genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
2407:	$types[$i] = new GenericClassStringType($genericType);
2408:	array_splice($types, $j--, 1);
2409:	$typesCount--;
2410:	continue;
2411:	}
2412:
2413:	if (
2414:	$types[$i] instanceof ArrayType
2415:	&& get_class($types[$i]) === ArrayType::class
2416:	&& $types[$j] instanceof AccessoryArrayListType
2417:	&& !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
2418:	) {
2419:	$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
2420:	if ($keyType instanceof NeverType) {
2421:	return $keyType;
2422:	}
2423:	$types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
2424:	continue;
2425:	}
2426:
2427:	continue;
2428:	}
2429:
2430:	if ($isSuperTypeB->yes()) {
2431:	array_splice($types, $i--, 1);
2432:	$typesCount--;
2433:	continue 2;
2434:	}
2435:
2436:	if ($isSuperTypeA->no()) {
2437:	return new NeverType(reason: $isSuperTypeA->getReasons()[0] ?? null);
2438:	}
2439:	}
2440:	}
2441:
2442:	if ($typesCount === 1) {
2443:	return $types[0];
2444:	}
2445:
2446:	$accessoryBaseTypes = [];
2447:	foreach ($types as $type) {
2448:	if (!$type instanceof AccessoryType) {
2449:	$accessoryBaseTypes = null;
2450:	break;
2451:	}
2452:	// Accessory types share their default base type: every string accessory
2453:	// returns `string`, hasOffset() and hasOffsetValue() both return
2454:	// `array\|ArrayAccess`. Adding the same base type again narrows nothing -
2455:	// intersection is idempotent - but the intersect() below distributes
2456:	// `A & (B \| C)` one union at a time, so n copies of `array\|ArrayAccess`
2457:	// would cost 2^n recursive calls before the duplicates are recognized at
2458:	// the leaves. That is why isset() with many offsets used to grow
2459:	// exponentially: each offset contributes one hasOffset().
2460:	$baseType = $type->getDefaultBaseType();
2461:	foreach ($accessoryBaseTypes as $addedBaseType) {
2462:	if ($addedBaseType->equals($baseType)) {
2463:	continue 2;
2464:	}
2465:	}
2466:	$accessoryBaseTypes[] = $baseType;
2467:	}
2468:	if ($accessoryBaseTypes !== null) {
2469:	// Accessory types never stand alone — supply the base type they refine.
2470:	return self::intersect(self::intersect(...$accessoryBaseTypes), ...$types);
2471:	}
2472:
2473:	return new IntersectionType($types);
2474:	}
2475:
2476:	private static function intersectDefiniteConstantArrays(ConstantArrayType $a, ConstantArrayType $b): Type
2477:	{
2478:	$aSealed = $a->isUnsealed()->no();
2479:	$bSealed = $b->isUnsealed()->no();
2480:	$bothUnsealed = !$aSealed && !$bSealed && $a->getUnsealedTypes() !== null && $b->getUnsealedTypes() !== null;
2481:
2482:	$aKeyByValue = [];
2483:	foreach ($a->getKeyTypes() as $k => $keyType) {
2484:	$aKeyByValue[$keyType->getValue()] = $k;
2485:	}
2486:	$bKeyByValue = [];
2487:	foreach ($b->getKeyTypes() as $k => $keyType) {
2488:	$bKeyByValue[$keyType->getValue()] = $k;
2489:	}
2490:
2491:	if ($aSealed && $bSealed) {
2492:	foreach ($aKeyByValue as $keyValue => $k) {
2493:	if (!$a->isOptionalKey($k) && !array_key_exists($keyValue, $bKeyByValue)) {
2494:	return new NeverType();
2495:	}
2496:	}
2497:	foreach ($bKeyByValue as $keyValue => $k) {
2498:	if (!$b->isOptionalKey($k) && !array_key_exists($keyValue, $aKeyByValue)) {
2499:	return new NeverType();
2500:	}
2501:	}
2502:	}
2503:
2504:	$newArray = ConstantArrayTypeBuilder::createEmpty();
2505:
2506:	if ($bothUnsealed) {
2507:	$aUnsealed = $a->getUnsealedTypes();
2508:	$bUnsealed = $b->getUnsealedTypes();
2509:	$unsealedKey = self::intersect($aUnsealed[0], $bUnsealed[0]);
2510:	$unsealedValue = self::intersect($aUnsealed[1], $bUnsealed[1]);
2511:	if ($unsealedKey instanceof NeverType \|\| $unsealedValue instanceof NeverType) {
2512:	return new NeverType();
2513:	}
2514:	$newArray->makeUnsealed($unsealedKey, $unsealedValue);
2515:	} else {
2516:	$never = new NeverType(true);
2517:	$newArray->makeUnsealed($never, $never);
2518:	}
2519:
2520:	$resolveOtherValue = static function (ConstantArrayType $other, Type $keyType): ?Type {
2521:	if ($other->hasOffsetValueType($keyType)->yes()) {
2522:	return $other->getOffsetValueType($keyType);
2523:	}
2524:	$otherUnsealed = $other->getUnsealedTypes();
2525:	if ($otherUnsealed === null) {
2526:	return null;
2527:	}
2528:	[$unsealedKey, $unsealedValue] = $otherUnsealed;
2529:	if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
2530:	return null;
2531:	}
2532:	if ($unsealedKey->isSuperTypeOf($keyType)->no()) {
2533:	return null;
2534:	}
2535:	return $unsealedValue;
2536:	};
2537:
2538:	$keysToProcess = [];
2539:	foreach ($aKeyByValue as $keyValue => $k) {
2540:	$keysToProcess[$keyValue] = [$k, $bKeyByValue[$keyValue] ?? null];
2541:	}
2542:	foreach ($bKeyByValue as $keyValue => $k) {
2543:	if (array_key_exists($keyValue, $keysToProcess)) {
2544:	continue;
2545:	}
2546:
2547:	$keysToProcess[$keyValue] = [null, $k];
2548:	}
2549:
2550:	foreach ($keysToProcess as [$aIdx, $bIdx]) {
2551:	if ($aIdx !== null && $bIdx !== null) {
2552:	$keyType = $a->getKeyTypes()[$aIdx];
2553:	$value = self::intersect($a->getValueTypes()[$aIdx], $b->getValueTypes()[$bIdx]);
2554:	$optional = $a->isOptionalKey($aIdx) && $b->isOptionalKey($bIdx);
2555:	} elseif ($aIdx !== null) {
2556:	$keyType = $a->getKeyTypes()[$aIdx];
2557:	$aValue = $a->getValueTypes()[$aIdx];
2558:	$bValue = $resolveOtherValue($b, $keyType);
2559:	if ($bValue === null) {
2560:	if ($a->isOptionalKey($aIdx)) {
2561:	continue;
2562:	}
2563:	return new NeverType();
2564:	}
2565:	$value = self::intersect($aValue, $bValue);
2566:	$optional = $a->isOptionalKey($aIdx);
2567:	} else {
2568:	/** @var int<0, max> $bIdx */
2569:	$keyType = $b->getKeyTypes()[$bIdx];
2570:	$bValue = $b->getValueTypes()[$bIdx];
2571:	$aValue = $resolveOtherValue($a, $keyType);
2572:	if ($aValue === null) {
2573:	if ($b->isOptionalKey($bIdx)) {
2574:	continue;
2575:	}
2576:	return new NeverType();
2577:	}
2578:	$value = self::intersect($aValue, $bValue);
2579:	$optional = $b->isOptionalKey($bIdx);
2580:	}
2581:
2582:	if ($value instanceof NeverType) {
2583:	if ($optional) {
2584:	continue;
2585:	}
2586:	return new NeverType();
2587:	}
2588:	$newArray->setOffsetValueType($keyType, $value, $optional);
2589:	}
2590:
2591:	return $newArray->getArray();
2592:	}
2593:
2594:	/**
2595:	* Merge two IntersectionTypes that have the same structure but differ
2596:	* in HasOffsetValueType value types (matched by offset key).
2597:	*
2598:	* E.g. (A & hasOV('k', X)) \| (A & hasOV('k', Y)) → (A & hasOV('k', X\|Y))
2599:	*/
2600:	private static function mergeIntersectionsForUnion(IntersectionType $a, IntersectionType $b): ?Type
2601:	{
2602:	$aTypes = $a->getTypes();
2603:	$bTypes = $b->getTypes();
2604:
2605:	if (count($aTypes) !== count($bTypes)) {
2606:	return null;
2607:	}
2608:
2609:	$mergedTypes = [];
2610:	$hasDifference = false;
2611:	$bUsed = array_fill(0, count($bTypes), false);
2612:
2613:	foreach ($aTypes as $aType) {
2614:	$matched = false;
2615:	foreach ($bTypes as $bIdx => $bType) {
2616:	if ($bUsed[$bIdx]) {
2617:	continue;
2618:	}
2619:
2620:	if ($aType->equals($bType)) {
2621:	$mergedTypes[] = $aType;
2622:	$bUsed[$bIdx] = true;
2623:	$matched = true;
2624:	break;
2625:	}
2626:
2627:	// HasOffsetValueType: merge value types when offset keys match
2628:	if ($aType instanceof HasOffsetValueType && $bType instanceof HasOffsetValueType
2629:	&& $aType->getOffsetType()->equals($bType->getOffsetType())) {
2630:	$mergedTypes[] = new HasOffsetValueType(
2631:	$aType->getOffsetType(),
2632:	self::union($aType->getValueType(), $bType->getValueType()),
2633:	);
2634:	$hasDifference = true;
2635:	$bUsed[$bIdx] = true;
2636:	$matched = true;
2637:	break;
2638:	}
2639:
2640:	// HasOffsetType, HasMethodType, HasPropertyType: only equal values match (no merging possible)
2641:	}
2642:	if (!$matched) {
2643:	return null;
2644:	}
2645:	}
2646:
2647:	if (!$hasDifference) {
2648:	return null;
2649:	}
2650:
2651:	$result = $mergedTypes[0];
2652:	for ($i = 1, $count = count($mergedTypes); $i < $count; $i++) {
2653:	$result = self::intersect($result, $mergedTypes[$i]);
2654:	}
2655:	return $result;
2656:	}
2657:
2658:	public static function removeFalsey(Type $type): Type
2659:	{
2660:	return self::remove($type, StaticTypeFactory::falsey());
2661:	}
2662:
2663:	public static function removeTruthy(Type $type): Type
2664:	{
2665:	return self::remove($type, StaticTypeFactory::truthy());
2666:	}
2667:
2668:	}
2669:

Namespaces

Classes

Interfaces