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