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

Namespaces

Classes

Interfaces