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