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