Namespaces

Classes

Interfaces

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