Namespaces

Classes

Interfaces

1: <?php declare(strict_types = 1);
2:
3: namespace PHPStan\Type;
4:
5: use PHPStan\Type\Accessory\AccessoryArrayListType;
6: use PHPStan\Type\Accessory\AccessoryNonEmptyStringType;
7: use PHPStan\Type\Accessory\AccessoryType;
8: use PHPStan\Type\Accessory\HasOffsetType;
9: use PHPStan\Type\Accessory\HasOffsetValueType;
10: use PHPStan\Type\Accessory\HasPropertyType;
11: use PHPStan\Type\Accessory\NonEmptyArrayType;
12: use PHPStan\Type\Accessory\OversizedArrayType;
13: use PHPStan\Type\Constant\ConstantArrayType;
14: use PHPStan\Type\Constant\ConstantArrayTypeBuilder;
15: use PHPStan\Type\Constant\ConstantBooleanType;
16: use PHPStan\Type\Constant\ConstantFloatType;
17: use PHPStan\Type\Constant\ConstantIntegerType;
18: use PHPStan\Type\Constant\ConstantStringType;
19: use PHPStan\Type\Generic\GenericClassStringType;
20: use PHPStan\Type\Generic\TemplateArrayType;
21: use PHPStan\Type\Generic\TemplateBenevolentUnionType;
22: use PHPStan\Type\Generic\TemplateType;
23: use PHPStan\Type\Generic\TemplateTypeFactory;
24: use PHPStan\Type\Generic\TemplateUnionType;
25: use function array_key_exists;
26: use function array_key_first;
27: use function array_map;
28: use function array_merge;
29: use function array_slice;
30: use function array_splice;
31: use function array_values;
32: use function count;
33: use function get_class;
34: use function is_int;
35: use function md5;
36: use function sprintf;
37: use function usort;
38:
39: /** @api */
40: class TypeCombinator
41: {
42:
43: public static function addNull(Type $type): Type
44: {
45: $nullType = new NullType();
46:
47: if ($nullType->isSuperTypeOf($type)->no()) {
48: return self::union($type, $nullType);
49: }
50:
51: return $type;
52: }
53:
54: public static function remove(Type $fromType, Type $typeToRemove): Type
55: {
56: if ($typeToRemove instanceof UnionType) {
57: foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
58: $fromType = self::remove($fromType, $unionTypeToRemove);
59: }
60: return $fromType;
61: }
62:
63: $isSuperType = $typeToRemove->isSuperTypeOf($fromType);
64: if ($isSuperType->yes()) {
65: return new NeverType();
66: }
67: if ($isSuperType->no()) {
68: return $fromType;
69: }
70:
71: if ($typeToRemove instanceof MixedType) {
72: $typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
73: if ($typeToRemoveSubtractedType !== null) {
74: return self::intersect($fromType, $typeToRemoveSubtractedType);
75: }
76: }
77:
78: $removed = $fromType->tryRemove($typeToRemove);
79: if ($removed !== null) {
80: return $removed;
81: }
82:
83: $fromFiniteTypes = $fromType->getFiniteTypes();
84: if (count($fromFiniteTypes) > 0) {
85: $finiteTypesToRemove = $typeToRemove->getFiniteTypes();
86: if (count($finiteTypesToRemove) === 1) {
87: $result = [];
88: foreach ($fromFiniteTypes as $finiteType) {
89: if ($finiteType->equals($finiteTypesToRemove[0])) {
90: continue;
91: }
92:
93: $result[] = $finiteType;
94: }
95:
96: if (count($result) === count($fromFiniteTypes)) {
97: return $fromType;
98: }
99:
100: if (count($result) === 0) {
101: return new NeverType();
102: }
103:
104: if (count($result) === 1) {
105: return $result[0];
106: }
107:
108: return new UnionType($result);
109: }
110: }
111:
112: return $fromType;
113: }
114:
115: public static function removeNull(Type $type): Type
116: {
117: if (self::containsNull($type)) {
118: return self::remove($type, new NullType());
119: }
120:
121: return $type;
122: }
123:
124: public static function containsNull(Type $type): bool
125: {
126: if ($type instanceof UnionType) {
127: foreach ($type->getTypes() as $innerType) {
128: if ($innerType instanceof NullType) {
129: return true;
130: }
131: }
132:
133: return false;
134: }
135:
136: return $type instanceof NullType;
137: }
138:
139: public static function union(Type ...$types): Type
140: {
141: $typesCount = count($types);
142: if ($typesCount === 0) {
143: return new NeverType();
144: }
145:
146: $benevolentTypes = [];
147: $benevolentUnionObject = null;
148: // transform A | (B | C) to A | B | C
149: for ($i = 0; $i < $typesCount; $i++) {
150: if ($types[$i] instanceof BenevolentUnionType) {
151: if ($types[$i] instanceof TemplateBenevolentUnionType && $benevolentUnionObject === null) {
152: $benevolentUnionObject = $types[$i];
153: }
154: $benevolentTypesCount = 0;
155: $typesInner = $types[$i]->getTypes();
156: foreach ($typesInner as $benevolentInnerType) {
157: $benevolentTypesCount++;
158: $benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
159: }
160: array_splice($types, $i, 1, $typesInner);
161: $typesCount += $benevolentTypesCount - 1;
162: continue;
163: }
164: if (!($types[$i] instanceof UnionType)) {
165: continue;
166: }
167: if ($types[$i] instanceof TemplateType) {
168: continue;
169: }
170:
171: $typesInner = $types[$i]->getTypes();
172: array_splice($types, $i, 1, $typesInner);
173: $typesCount += count($typesInner) - 1;
174: }
175:
176: if ($typesCount === 1) {
177: return $types[0];
178: }
179:
180: $arrayTypes = [];
181: $scalarTypes = [];
182: $hasGenericScalarTypes = [];
183: $enumCaseTypes = [];
184: for ($i = 0; $i < $typesCount; $i++) {
185: if ($types[$i] instanceof ConstantScalarType) {
186: $type = $types[$i];
187: $scalarTypes[get_class($type)][md5($type->describe(VerbosityLevel::cache()))] = $type;
188: unset($types[$i]);
189: continue;
190: }
191: if ($types[$i] instanceof BooleanType) {
192: $hasGenericScalarTypes[ConstantBooleanType::class] = true;
193: }
194: if ($types[$i] instanceof FloatType) {
195: $hasGenericScalarTypes[ConstantFloatType::class] = true;
196: }
197: if ($types[$i] instanceof IntegerType && !$types[$i] instanceof IntegerRangeType) {
198: $hasGenericScalarTypes[ConstantIntegerType::class] = true;
199: }
200: if ($types[$i] instanceof StringType && !$types[$i] instanceof ClassStringType) {
201: $hasGenericScalarTypes[ConstantStringType::class] = true;
202: }
203: $enumCases = $types[$i]->getEnumCases();
204: if (count($enumCases) === 1) {
205: $enumCaseTypes[$types[$i]->describe(VerbosityLevel::cache())] = $types[$i];
206:
207: unset($types[$i]);
208: continue;
209: }
210:
211: if (!$types[$i]->isArray()->yes()) {
212: continue;
213: }
214:
215: $arrayTypes[] = $types[$i];
216: unset($types[$i]);
217: }
218:
219: foreach ($scalarTypes as $classType => $scalarTypeItems) {
220: $scalarTypes[$classType] = array_values($scalarTypeItems);
221: }
222:
223: $enumCaseTypes = array_values($enumCaseTypes);
224: $types = array_values($types);
225: $typesCount = count($types);
226:
227: foreach ($scalarTypes as $classType => $scalarTypeItems) {
228: if (isset($hasGenericScalarTypes[$classType])) {
229: unset($scalarTypes[$classType]);
230: continue;
231: }
232: if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
233: $types[] = new BooleanType();
234: $typesCount++;
235: unset($scalarTypes[$classType]);
236: continue;
237: }
238:
239: $scalarTypeItemsCount = count($scalarTypeItems);
240: for ($i = 0; $i < $typesCount; $i++) {
241: for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
242: $compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
243: if ($compareResult === null) {
244: continue;
245: }
246:
247: [$a, $b] = $compareResult;
248: if ($a !== null) {
249: $types[$i] = $a;
250: array_splice($scalarTypeItems, $j--, 1);
251: $scalarTypeItemsCount--;
252: continue 1;
253: }
254: if ($b !== null) {
255: $scalarTypeItems[$j] = $b;
256: array_splice($types, $i--, 1);
257: $typesCount--;
258: continue 2;
259: }
260: }
261: }
262:
263: $scalarTypes[$classType] = $scalarTypeItems;
264: }
265:
266: if (count($types) > 16) {
267: $newTypes = [];
268: foreach ($types as $type) {
269: $newTypes[$type->describe(VerbosityLevel::cache())] = $type;
270: }
271: $types = array_values($newTypes);
272: }
273:
274: $types = array_merge(
275: $types,
276: self::processArrayTypes($arrayTypes),
277: );
278: $typesCount = count($types);
279:
280: // transform A | A to A
281: // transform A | never to A
282: for ($i = 0; $i < $typesCount; $i++) {
283: for ($j = $i + 1; $j < $typesCount; $j++) {
284: $compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
285: if ($compareResult === null) {
286: continue;
287: }
288:
289: [$a, $b] = $compareResult;
290: if ($a !== null) {
291: $types[$i] = $a;
292: array_splice($types, $j--, 1);
293: $typesCount--;
294: continue 1;
295: }
296: if ($b !== null) {
297: $types[$j] = $b;
298: array_splice($types, $i--, 1);
299: $typesCount--;
300: continue 2;
301: }
302: }
303: }
304:
305: $enumCasesCount = count($enumCaseTypes);
306: for ($i = 0; $i < $typesCount; $i++) {
307: for ($j = 0; $j < $enumCasesCount; $j++) {
308: $compareResult = self::compareTypesInUnion($types[$i], $enumCaseTypes[$j]);
309: if ($compareResult === null) {
310: continue;
311: }
312:
313: [$a, $b] = $compareResult;
314: if ($a !== null) {
315: $types[$i] = $a;
316: array_splice($enumCaseTypes, $j--, 1);
317: $enumCasesCount--;
318: continue 1;
319: }
320: if ($b !== null) {
321: $enumCaseTypes[$j] = $b;
322: array_splice($types, $i--, 1);
323: $typesCount--;
324: continue 2;
325: }
326: }
327: }
328:
329: foreach ($enumCaseTypes as $enumCaseType) {
330: $types[] = $enumCaseType;
331: $typesCount++;
332: }
333:
334: foreach ($scalarTypes as $scalarTypeItems) {
335: foreach ($scalarTypeItems as $scalarType) {
336: $types[] = $scalarType;
337: $typesCount++;
338: }
339: }
340:
341: if ($typesCount === 0) {
342: return new NeverType();
343: }
344: if ($typesCount === 1) {
345: return $types[0];
346: }
347:
348: if ($benevolentTypes !== []) {
349: $tempTypes = $types;
350: foreach ($tempTypes as $i => $type) {
351: if (!isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
352: break;
353: }
354:
355: unset($tempTypes[$i]);
356: }
357:
358: if ($tempTypes === []) {
359: if ($benevolentUnionObject instanceof TemplateBenevolentUnionType) {
360: return $benevolentUnionObject->withTypes($types);
361: }
362:
363: return new BenevolentUnionType($types);
364: }
365: }
366:
367: return new UnionType($types, true);
368: }
369:
370: /**
371: * @return array{Type, null}|array{null, Type}|null
372: */
373: private static function compareTypesInUnion(Type $a, Type $b): ?array
374: {
375: if ($a instanceof IntegerRangeType) {
376: $type = $a->tryUnion($b);
377: if ($type !== null) {
378: $a = $type;
379: return [$a, null];
380: }
381: }
382: if ($b instanceof IntegerRangeType) {
383: $type = $b->tryUnion($a);
384: if ($type !== null) {
385: $b = $type;
386: return [null, $b];
387: }
388: }
389: if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
390: return null;
391: }
392: if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
393: if ($a->getOffsetType()->equals($b->getOffsetType())) {
394: return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
395: }
396: }
397: if ($a->isConstantArray()->yes() && $b->isConstantArray()->yes()) {
398: return null;
399: }
400:
401: // simplify string[] | int[] to (string|int)[]
402: if ($a instanceof IterableType && $b instanceof IterableType) {
403: return [
404: new IterableType(
405: self::union($a->getIterableKeyType(), $b->getIterableKeyType()),
406: self::union($a->getIterableValueType(), $b->getIterableValueType()),
407: ),
408: null,
409: ];
410: }
411:
412: if ($a instanceof SubtractableType) {
413: $typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
414: if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
415: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
416: } else {
417: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
418: }
419: if ($isSuperType->yes()) {
420: $a = self::intersectWithSubtractedType($a, $b);
421: return [$a, null];
422: }
423: }
424:
425: if ($b instanceof SubtractableType) {
426: $typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
427: if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
428: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
429: } else {
430: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
431: }
432: if ($isSuperType->yes()) {
433: $b = self::intersectWithSubtractedType($b, $a);
434: return [null, $b];
435: }
436: }
437:
438: if ($b->isSuperTypeOf($a)->yes()) {
439: return [null, $b];
440: }
441:
442: if ($a->isSuperTypeOf($b)->yes()) {
443: return [$a, null];
444: }
445:
446: if (
447: $a instanceof ConstantStringType
448: && $a->getValue() === ''
449: && ($b->describe(VerbosityLevel::value()) === 'non-empty-string'
450: || $b->describe(VerbosityLevel::value()) === 'non-falsy-string')
451: ) {
452: return [null, new StringType()];
453: }
454:
455: if (
456: $b instanceof ConstantStringType
457: && $b->getValue() === ''
458: && ($a->describe(VerbosityLevel::value()) === 'non-empty-string'
459: || $a->describe(VerbosityLevel::value()) === 'non-falsy-string')
460: ) {
461: return [new StringType(), null];
462: }
463:
464: if (
465: $a instanceof ConstantStringType
466: && $a->getValue() === '0'
467: && $b->describe(VerbosityLevel::value()) === 'non-falsy-string'
468: ) {
469: return [null, new IntersectionType([
470: new StringType(),
471: new AccessoryNonEmptyStringType(),
472: ])];
473: }
474:
475: if (
476: $b instanceof ConstantStringType
477: && $b->getValue() === '0'
478: && $a->describe(VerbosityLevel::value()) === 'non-falsy-string'
479: ) {
480: return [new IntersectionType([
481: new StringType(),
482: new AccessoryNonEmptyStringType(),
483: ]), null];
484: }
485:
486: return null;
487: }
488:
489: private static function unionWithSubtractedType(
490: Type $type,
491: ?Type $subtractedType,
492: ): Type
493: {
494: if ($subtractedType === null) {
495: return $type;
496: }
497:
498: if ($type instanceof SubtractableType) {
499: $subtractedType = $type->getSubtractedType() === null
500: ? $subtractedType
501: : self::union($type->getSubtractedType(), $subtractedType);
502: if ($subtractedType instanceof NeverType) {
503: $subtractedType = null;
504: }
505:
506: return $type->changeSubtractedType($subtractedType);
507: }
508:
509: if ($subtractedType->isSuperTypeOf($type)->yes()) {
510: return new NeverType();
511: }
512:
513: return self::remove($type, $subtractedType);
514: }
515:
516: private static function intersectWithSubtractedType(
517: SubtractableType $a,
518: Type $b,
519: ): Type
520: {
521: if ($a->getSubtractedType() === null) {
522: return $a;
523: }
524:
525: if ($b instanceof IntersectionType) {
526: $subtractableTypes = [];
527: foreach ($b->getTypes() as $innerType) {
528: if (!$innerType instanceof SubtractableType) {
529: continue;
530: }
531:
532: $subtractableTypes[] = $innerType;
533: }
534:
535: if (count($subtractableTypes) === 0) {
536: return $a->getTypeWithoutSubtractedType();
537: }
538:
539: $subtractedTypes = [];
540: foreach ($subtractableTypes as $subtractableType) {
541: if ($subtractableType->getSubtractedType() === null) {
542: continue;
543: }
544:
545: $subtractedTypes[] = $subtractableType->getSubtractedType();
546: }
547:
548: if (count($subtractedTypes) === 0) {
549: return $a->getTypeWithoutSubtractedType();
550:
551: }
552:
553: $subtractedType = self::union(...$subtractedTypes);
554: } elseif ($b instanceof SubtractableType) {
555: $subtractedType = $b->getSubtractedType();
556: if ($subtractedType === null) {
557: return $a->getTypeWithoutSubtractedType();
558: }
559: } else {
560: $subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
561: if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
562: return $a->getTypeWithoutSubtractedType();
563: }
564: $subtractedType = new MixedType(false, $b);
565: }
566:
567: $subtractedType = self::intersect(
568: $a->getSubtractedType(),
569: $subtractedType,
570: );
571: if ($subtractedType instanceof NeverType) {
572: $subtractedType = null;
573: }
574:
575: return $a->changeSubtractedType($subtractedType);
576: }
577:
578: /**
579: * @param Type[] $arrayTypes
580: * @return Type[]
581: */
582: private static function processArrayAccessoryTypes(array $arrayTypes): array
583: {
584: $accessoryTypes = [];
585: foreach ($arrayTypes as $i => $arrayType) {
586: if ($arrayType instanceof IntersectionType) {
587: foreach ($arrayType->getTypes() as $innerType) {
588: if ($innerType instanceof TemplateType) {
589: break;
590: }
591: if (!($innerType instanceof AccessoryType) && !($innerType instanceof CallableType)) {
592: continue;
593: }
594: if ($innerType instanceof HasOffsetValueType) {
595: $accessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][$i] = $innerType;
596: continue;
597: }
598:
599: $accessoryTypes[$innerType->describe(VerbosityLevel::cache())][$i] = $innerType;
600: }
601: }
602:
603: if (!$arrayType->isConstantArray()->yes()) {
604: continue;
605: }
606: $constantArrays = $arrayType->getConstantArrays();
607:
608: foreach ($constantArrays as $constantArray) {
609: if ($constantArray->isList()->yes() && AccessoryArrayListType::isListTypeEnabled()) {
610: $list = new AccessoryArrayListType();
611: $accessoryTypes[$list->describe(VerbosityLevel::cache())][$i] = $list;
612: }
613:
614: if (!$constantArray->isIterableAtLeastOnce()->yes()) {
615: continue;
616: }
617:
618: $nonEmpty = new NonEmptyArrayType();
619: $accessoryTypes[$nonEmpty->describe(VerbosityLevel::cache())][$i] = $nonEmpty;
620: }
621: }
622:
623: $commonAccessoryTypes = [];
624: $arrayTypeCount = count($arrayTypes);
625: foreach ($accessoryTypes as $accessoryType) {
626: if (count($accessoryType) !== $arrayTypeCount) {
627: $firstKey = array_key_first($accessoryType);
628: if ($accessoryType[$firstKey] instanceof OversizedArrayType) {
629: $commonAccessoryTypes[] = $accessoryType[$firstKey];
630: }
631: continue;
632: }
633:
634: if ($accessoryType[0] instanceof HasOffsetValueType) {
635: $commonAccessoryTypes[] = self::union(...$accessoryType);
636: continue;
637: }
638:
639: $commonAccessoryTypes[] = $accessoryType[0];
640: }
641:
642: return $commonAccessoryTypes;
643: }
644:
645: /**
646: * @param list<Type> $arrayTypes
647: * @return Type[]
648: */
649: private static function processArrayTypes(array $arrayTypes): array
650: {
651: if ($arrayTypes === []) {
652: return [];
653: }
654:
655: $accessoryTypes = self::processArrayAccessoryTypes($arrayTypes);
656:
657: if (count($arrayTypes) === 1) {
658: return [
659: self::intersect(...$arrayTypes, ...$accessoryTypes),
660: ];
661: }
662:
663: $keyTypesForGeneralArray = [];
664: $valueTypesForGeneralArray = [];
665: $generalArrayOccurred = false;
666: $constantKeyTypesNumbered = [];
667: $filledArrays = 0;
668: $overflowed = false;
669:
670: /** @var int|float $nextConstantKeyTypeIndex */
671: $nextConstantKeyTypeIndex = 1;
672: $constantArraysMap = array_map(
673: static fn (Type $t) => $t->getConstantArrays(),
674: $arrayTypes,
675: );
676:
677: foreach ($arrayTypes as $arrayIdx => $arrayType) {
678: $constantArrays = $constantArraysMap[$arrayIdx];
679: $isConstantArray = $constantArrays !== [];
680: if (!$isConstantArray || !$arrayType->isIterableAtLeastOnce()->no()) {
681: $filledArrays++;
682: }
683:
684: if ($generalArrayOccurred || !$isConstantArray) {
685: foreach ($arrayType->getArrays() as $type) {
686: $keyTypesForGeneralArray[] = $type->getIterableKeyType();
687: $valueTypesForGeneralArray[] = $type->getItemType();
688: $generalArrayOccurred = true;
689: }
690: continue;
691: }
692:
693: $constantArrays = $arrayType->getConstantArrays();
694: foreach ($constantArrays as $constantArray) {
695: foreach ($constantArray->getKeyTypes() as $i => $keyType) {
696: $keyTypesForGeneralArray[] = $keyType;
697: $valueTypesForGeneralArray[] = $constantArray->getValueTypes()[$i];
698:
699: $keyTypeValue = $keyType->getValue();
700: if (array_key_exists($keyTypeValue, $constantKeyTypesNumbered)) {
701: continue;
702: }
703:
704: $constantKeyTypesNumbered[$keyTypeValue] = $nextConstantKeyTypeIndex;
705: $nextConstantKeyTypeIndex *= 2;
706: if (!is_int($nextConstantKeyTypeIndex)) {
707: $generalArrayOccurred = true;
708: $overflowed = true;
709: continue 2;
710: }
711: }
712: }
713: }
714:
715: if ($generalArrayOccurred && (!$overflowed || $filledArrays > 1)) {
716: $reducedArrayTypes = self::reduceArrays($arrayTypes, false);
717: if (count($reducedArrayTypes) === 1) {
718: return [self::intersect($reducedArrayTypes[0], ...$accessoryTypes)];
719: }
720: $scopes = [];
721: $useTemplateArray = true;
722: foreach ($arrayTypes as $arrayType) {
723: if (!$arrayType instanceof TemplateArrayType) {
724: $useTemplateArray = false;
725: break;
726: }
727:
728: $scopes[$arrayType->getScope()->describe()] = $arrayType;
729: }
730:
731: $arrayType = new ArrayType(
732: self::union(...$keyTypesForGeneralArray),
733: self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
734: );
735:
736: if ($useTemplateArray && count($scopes) === 1) {
737: $templateArray = array_values($scopes)[0];
738: $arrayType = new TemplateArrayType(
739: $templateArray->getScope(),
740: $templateArray->getStrategy(),
741: $templateArray->getVariance(),
742: $templateArray->getName(),
743: $arrayType,
744: );
745: }
746:
747: return [
748: self::intersect($arrayType, ...$accessoryTypes),
749: ];
750: }
751:
752: $reducedArrayTypes = self::reduceArrays($arrayTypes, true);
753:
754: return array_map(
755: static fn (Type $arrayType) => self::intersect($arrayType, ...$accessoryTypes),
756: self::optimizeConstantArrays($reducedArrayTypes),
757: );
758: }
759:
760: /**
761: * @param Type[] $types
762: * @return Type[]
763: */
764: private static function optimizeConstantArrays(array $types): array
765: {
766: $constantArrayValuesCount = self::countConstantArrayValueTypes($types);
767:
768: if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
769: return $types;
770: }
771:
772: $results = [];
773: foreach ($types as $type) {
774: $results[] = TypeTraverser::map($type, static function (Type $type, callable $traverse): Type {
775: if (!$type instanceof ConstantArrayType) {
776: return $traverse($type);
777: }
778:
779: if ($type->isIterableAtLeastOnce()->no()) {
780: return $type;
781: }
782:
783: $isList = true;
784: $valueTypes = [];
785: $keyTypes = [];
786: $nextAutoIndex = 0;
787: foreach ($type->getKeyTypes() as $i => $innerKeyType) {
788: if (!$innerKeyType instanceof ConstantIntegerType) {
789: $isList = false;
790: } elseif ($innerKeyType->getValue() !== $nextAutoIndex) {
791: $isList = false;
792: $nextAutoIndex = $innerKeyType->getValue() + 1;
793: } else {
794: $nextAutoIndex++;
795: }
796:
797: $generalizedKeyType = $innerKeyType->generalize(GeneralizePrecision::moreSpecific());
798: $keyTypes[$generalizedKeyType->describe(VerbosityLevel::precise())] = $generalizedKeyType;
799:
800: $innerValueType = $type->getValueTypes()[$i];
801: $generalizedValueType = TypeTraverser::map($innerValueType, static function (Type $type, callable $innerTraverse) use ($traverse): Type {
802: if ($type instanceof ArrayType) {
803: return TypeCombinator::intersect($type, new OversizedArrayType());
804: }
805:
806: return $traverse($type);
807: });
808: $valueTypes[$generalizedValueType->describe(VerbosityLevel::precise())] = $generalizedValueType;
809: }
810:
811: $keyType = TypeCombinator::union(...array_values($keyTypes));
812: $valueType = TypeCombinator::union(...array_values($valueTypes));
813:
814: $arrayType = new ArrayType($keyType, $valueType);
815: if ($isList) {
816: $arrayType = AccessoryArrayListType::intersectWith($arrayType);
817: }
818:
819: return TypeCombinator::intersect($arrayType, new NonEmptyArrayType(), new OversizedArrayType());
820: });
821: }
822:
823: return $results;
824: }
825:
826: /**
827: * @param Type[] $types
828: */
829: private static function countConstantArrayValueTypes(array $types): int
830: {
831: $constantArrayValuesCount = 0;
832: foreach ($types as $type) {
833: TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$constantArrayValuesCount): Type {
834: if ($type instanceof ConstantArrayType) {
835: $constantArrayValuesCount += count($type->getValueTypes());
836: }
837:
838: return $traverse($type);
839: });
840: }
841: return $constantArrayValuesCount;
842: }
843:
844: /**
845: * @param list<Type> $constantArrays
846: * @return list<Type>
847: */
848: private static function reduceArrays(array $constantArrays, bool $preserveTaggedUnions): array
849: {
850: $newArrays = [];
851: $arraysToProcess = [];
852: $emptyArray = null;
853: foreach ($constantArrays as $constantArray) {
854: if (!$constantArray->isConstantArray()->yes()) {
855: // This is an optimization for current use-case of $preserveTaggedUnions=false, where we need
856: // one constant array as a result, or we generalize the $constantArrays.
857: if (!$preserveTaggedUnions) {
858: return $constantArrays;
859: }
860: $newArrays[] = $constantArray;
861: continue;
862: }
863:
864: if ($constantArray->isIterableAtLeastOnce()->no()) {
865: $emptyArray = $constantArray;
866: continue;
867: }
868:
869: $arraysToProcess = array_merge($arraysToProcess, $constantArray->getConstantArrays());
870: }
871:
872: if ($emptyArray !== null) {
873: $newArrays[] = $emptyArray;
874: }
875:
876: $arraysToProcessPerKey = [];
877: foreach ($arraysToProcess as $i => $arrayToProcess) {
878: foreach ($arrayToProcess->getKeyTypes() as $keyType) {
879: $arraysToProcessPerKey[$keyType->getValue()][] = $i;
880: }
881: }
882:
883: $eligibleCombinations = [];
884:
885: foreach ($arraysToProcessPerKey as $arrays) {
886: for ($i = 0, $arraysCount = count($arrays); $i < $arraysCount - 1; $i++) {
887: for ($j = $i + 1; $j < $arraysCount; $j++) {
888: $eligibleCombinations[$arrays[$i]][$arrays[$j]] ??= 0;
889: $eligibleCombinations[$arrays[$i]][$arrays[$j]]++;
890: }
891: }
892: }
893:
894: foreach ($eligibleCombinations as $i => $other) {
895: if (!array_key_exists($i, $arraysToProcess)) {
896: continue;
897: }
898:
899: foreach ($other as $j => $overlappingKeysCount) {
900: if (!array_key_exists($j, $arraysToProcess)) {
901: continue;
902: }
903:
904: if (
905: $preserveTaggedUnions
906: && $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
907: && $arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])
908: ) {
909: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
910: unset($arraysToProcess[$i]);
911: continue 2;
912: }
913:
914: if (
915: $preserveTaggedUnions
916: && $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
917: && $arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])
918: ) {
919: $arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
920: unset($arraysToProcess[$j]);
921: continue 1;
922: }
923:
924: if (
925: !$preserveTaggedUnions
926: // both arrays have same keys
927: && $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
928: && $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
929: ) {
930: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
931: unset($arraysToProcess[$i]);
932: continue 2;
933: }
934: }
935: }
936:
937: return array_merge($newArrays, $arraysToProcess);
938: }
939:
940: public static function intersect(Type ...$types): Type
941: {
942: $types = array_values($types);
943:
944: $typesCount = count($types);
945: if ($typesCount === 0) {
946: return new NeverType();
947: }
948: if ($typesCount === 1) {
949: return $types[0];
950: }
951:
952: $sortTypes = static function (Type $a, Type $b): int {
953: if (!$a instanceof UnionType || !$b instanceof UnionType) {
954: return 0;
955: }
956:
957: if ($a instanceof TemplateType) {
958: return -1;
959: }
960: if ($b instanceof TemplateType) {
961: return 1;
962: }
963:
964: if ($a instanceof BenevolentUnionType) {
965: return -1;
966: }
967: if ($b instanceof BenevolentUnionType) {
968: return 1;
969: }
970:
971: return 0;
972: };
973: usort($types, $sortTypes);
974: // transform A & (B | C) to (A & B) | (A & C)
975: foreach ($types as $i => $type) {
976: if (!$type instanceof UnionType) {
977: continue;
978: }
979:
980: $topLevelUnionSubTypes = [];
981: $innerTypes = $type->getTypes();
982: usort($innerTypes, $sortTypes);
983: $slice1 = array_slice($types, 0, $i);
984: $slice2 = array_slice($types, $i + 1);
985: foreach ($innerTypes as $innerUnionSubType) {
986: $topLevelUnionSubTypes[] = self::intersect(
987: $innerUnionSubType,
988: ...$slice1,
989: ...$slice2,
990: );
991: }
992:
993: $union = self::union(...$topLevelUnionSubTypes);
994: if ($union instanceof NeverType) {
995: return $union;
996: }
997:
998: if ($type instanceof BenevolentUnionType) {
999: $union = TypeUtils::toBenevolentUnion($union);
1000: }
1001:
1002: if ($type instanceof TemplateUnionType || $type instanceof TemplateBenevolentUnionType) {
1003: $union = TemplateTypeFactory::create(
1004: $type->getScope(),
1005: $type->getName(),
1006: $union,
1007: $type->getVariance(),
1008: $type->getStrategy(),
1009: );
1010: }
1011:
1012: return $union;
1013: }
1014: $typesCount = count($types);
1015:
1016: // transform A & (B & C) to A & B & C
1017: for ($i = 0; $i < $typesCount; $i++) {
1018: $type = $types[$i];
1019:
1020: if (!($type instanceof IntersectionType)) {
1021: continue;
1022: }
1023:
1024: array_splice($types, $i--, 1, $type->getTypes());
1025: $typesCount = count($types);
1026: }
1027:
1028: $hasOffsetValueTypeCount = 0;
1029: $newTypes = [];
1030: foreach ($types as $type) {
1031: if (!$type instanceof HasOffsetValueType) {
1032: $newTypes[] = $type;
1033: continue;
1034: }
1035:
1036: $hasOffsetValueTypeCount++;
1037: }
1038:
1039: if ($hasOffsetValueTypeCount > 32) {
1040: $newTypes[] = new OversizedArrayType();
1041: $types = $newTypes;
1042: $typesCount = count($types);
1043: }
1044:
1045: usort($types, static function (Type $a, Type $b): int {
1046: // move subtractables with subtracts before those without to avoid loosing them in the union logic
1047: if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
1048: return -1;
1049: }
1050: if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
1051: return 1;
1052: }
1053:
1054: if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
1055: return -1;
1056: }
1057: if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
1058: return 1;
1059: }
1060:
1061: return 0;
1062: });
1063:
1064: // transform IntegerType & ConstantIntegerType to ConstantIntegerType
1065: // transform Child & Parent to Child
1066: // transform Object & ~null to Object
1067: // transform A & A to A
1068: // transform int[] & string to never
1069: // transform callable & int to never
1070: // transform A & ~A to never
1071: // transform int & string to never
1072: for ($i = 0; $i < $typesCount; $i++) {
1073: for ($j = $i + 1; $j < $typesCount; $j++) {
1074: if ($types[$j] instanceof SubtractableType) {
1075: $typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
1076:
1077: if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
1078: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
1079: } else {
1080: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
1081: }
1082: if ($isSuperTypeSubtractableA->yes()) {
1083: $types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
1084: array_splice($types, $j--, 1);
1085: $typesCount--;
1086: continue 1;
1087: }
1088: }
1089:
1090: if ($types[$i] instanceof SubtractableType) {
1091: $typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
1092:
1093: if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
1094: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
1095: } else {
1096: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
1097: }
1098: if ($isSuperTypeSubtractableB->yes()) {
1099: $types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
1100: array_splice($types, $i--, 1);
1101: $typesCount--;
1102: continue 2;
1103: }
1104: }
1105:
1106: if ($types[$i] instanceof IntegerRangeType) {
1107: $intersectionType = $types[$i]->tryIntersect($types[$j]);
1108: if ($intersectionType !== null) {
1109: $types[$j] = $intersectionType;
1110: array_splice($types, $i--, 1);
1111: $typesCount--;
1112: continue 2;
1113: }
1114: }
1115:
1116: if ($types[$j] instanceof IterableType) {
1117: $isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
1118: } else {
1119: $isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
1120: }
1121:
1122: if ($isSuperTypeA->yes()) {
1123: array_splice($types, $j--, 1);
1124: $typesCount--;
1125: continue;
1126: }
1127:
1128: if ($types[$i] instanceof IterableType) {
1129: $isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
1130: } else {
1131: $isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
1132: }
1133:
1134: if ($isSuperTypeB->maybe()) {
1135: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
1136: $types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
1137: array_splice($types, $j--, 1);
1138: $typesCount--;
1139: continue;
1140: }
1141:
1142: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
1143: $types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
1144: array_splice($types, $i--, 1);
1145: $typesCount--;
1146: continue 2;
1147: }
1148:
1149: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
1150: $offsetType = $types[$j]->getOffsetType();
1151: $valueType = $types[$j]->getValueType();
1152: $newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
1153: if ($newValueType instanceof NeverType) {
1154: return $newValueType;
1155: }
1156: $types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
1157: array_splice($types, $j--, 1);
1158: $typesCount--;
1159: continue;
1160: }
1161:
1162: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
1163: $offsetType = $types[$i]->getOffsetType();
1164: $valueType = $types[$i]->getValueType();
1165: $newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
1166: if ($newValueType instanceof NeverType) {
1167: return $newValueType;
1168: }
1169:
1170: $types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
1171: array_splice($types, $i--, 1);
1172: $typesCount--;
1173: continue 2;
1174: }
1175:
1176: if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
1177: array_splice($types, $j--, 1);
1178: $typesCount--;
1179: continue;
1180: }
1181:
1182: if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
1183: array_splice($types, $i--, 1);
1184: $typesCount--;
1185: continue 2;
1186: }
1187:
1188: if ($types[$i] instanceof ObjectShapeType && $types[$j] instanceof HasPropertyType) {
1189: $types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
1190: array_splice($types, $j--, 1);
1191: $typesCount--;
1192: continue;
1193: }
1194:
1195: if ($types[$j] instanceof ObjectShapeType && $types[$i] instanceof HasPropertyType) {
1196: $types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
1197: array_splice($types, $i--, 1);
1198: $typesCount--;
1199: continue 2;
1200: }
1201:
1202: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof ArrayType) {
1203: $newArray = ConstantArrayTypeBuilder::createEmpty();
1204: $valueTypes = $types[$i]->getValueTypes();
1205: foreach ($types[$i]->getKeyTypes() as $k => $keyType) {
1206: $newArray->setOffsetValueType(
1207: self::intersect($keyType, $types[$j]->getIterableKeyType()),
1208: self::intersect($valueTypes[$k], $types[$j]->getIterableValueType()),
1209: $types[$i]->isOptionalKey($k) && !$types[$j]->hasOffsetValueType($keyType)->yes(),
1210: );
1211: }
1212: $types[$i] = $newArray->getArray();
1213: array_splice($types, $j--, 1);
1214: $typesCount--;
1215: continue 2;
1216: }
1217:
1218: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof ArrayType) {
1219: $newArray = ConstantArrayTypeBuilder::createEmpty();
1220: $valueTypes = $types[$j]->getValueTypes();
1221: foreach ($types[$j]->getKeyTypes() as $k => $keyType) {
1222: $newArray->setOffsetValueType(
1223: self::intersect($keyType, $types[$i]->getIterableKeyType()),
1224: self::intersect($valueTypes[$k], $types[$i]->getIterableValueType()),
1225: $types[$j]->isOptionalKey($k) && !$types[$i]->hasOffsetValueType($keyType)->yes(),
1226: );
1227: }
1228: $types[$j] = $newArray->getArray();
1229: array_splice($types, $i--, 1);
1230: $typesCount--;
1231: continue 2;
1232: }
1233:
1234: if (
1235: ($types[$i] instanceof ArrayType || $types[$i] instanceof IterableType) &&
1236: ($types[$j] instanceof ArrayType || $types[$j] instanceof IterableType)
1237: ) {
1238: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
1239: $itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
1240: if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
1241: $types[$j] = new IterableType($keyType, $itemType);
1242: } else {
1243: $types[$j] = new ArrayType($keyType, $itemType);
1244: }
1245: array_splice($types, $i--, 1);
1246: $typesCount--;
1247: continue 2;
1248: }
1249:
1250: if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
1251: $genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
1252: $types[$i] = new GenericClassStringType($genericType);
1253: array_splice($types, $j--, 1);
1254: $typesCount--;
1255: continue;
1256: }
1257:
1258: if (
1259: $types[$i] instanceof ArrayType
1260: && get_class($types[$i]) === ArrayType::class
1261: && $types[$j] instanceof AccessoryArrayListType
1262: && !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
1263: ) {
1264: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
1265: if ($keyType instanceof NeverType) {
1266: return $keyType;
1267: }
1268: $types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
1269: continue;
1270: }
1271:
1272: continue;
1273: }
1274:
1275: if ($isSuperTypeB->yes()) {
1276: array_splice($types, $i--, 1);
1277: $typesCount--;
1278: continue 2;
1279: }
1280:
1281: if ($isSuperTypeA->no()) {
1282: return new NeverType();
1283: }
1284: }
1285: }
1286:
1287: if ($typesCount === 1) {
1288: return $types[0];
1289: }
1290:
1291: return new IntersectionType($types);
1292: }
1293:
1294: public static function removeFalsey(Type $type): Type
1295: {
1296: return self::remove($type, StaticTypeFactory::falsey());
1297: }
1298:
1299: }
1300:
PHPStan API documentation generated by ApiGen dev-master