Namespaces

Classes

Interfaces

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