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

Namespaces

Classes

Interfaces