File src/Type/TypeCombinator.php

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

Namespaces

Classes

Interfaces