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\Enum\EnumCaseObjectType;
20: use PHPStan\Type\Generic\GenericClassStringType;
21: use PHPStan\Type\Generic\TemplateArrayType;
22: use PHPStan\Type\Generic\TemplateBenevolentUnionType;
23: use PHPStan\Type\Generic\TemplateType;
24: use PHPStan\Type\Generic\TemplateTypeFactory;
25: use PHPStan\Type\Generic\TemplateUnionType;
26: use function array_key_exists;
27: use function array_key_first;
28: use function array_map;
29: use function array_merge;
30: use function array_slice;
31: use function array_splice;
32: use function array_values;
33: use function count;
34: use function get_class;
35: use function is_int;
36: use function md5;
37: use function sprintf;
38: use function usort;
39:
40: /** @api */
41: class TypeCombinator
42: {
43:
44: public static function addNull(Type $type): Type
45: {
46: $nullType = new NullType();
47:
48: if ($nullType->isSuperTypeOf($type)->no()) {
49: return self::union($type, $nullType);
50: }
51:
52: return $type;
53: }
54:
55: public static function remove(Type $fromType, Type $typeToRemove): Type
56: {
57: if ($typeToRemove instanceof UnionType) {
58: foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
59: $fromType = self::remove($fromType, $unionTypeToRemove);
60: }
61: return $fromType;
62: }
63:
64: $isSuperType = $typeToRemove->isSuperTypeOf($fromType);
65: if ($isSuperType->yes()) {
66: return new NeverType();
67: }
68: if ($isSuperType->no()) {
69: return $fromType;
70: }
71:
72: if ($typeToRemove instanceof MixedType) {
73: $typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
74: if ($typeToRemoveSubtractedType !== null) {
75: return self::intersect($fromType, $typeToRemoveSubtractedType);
76: }
77: }
78:
79: $removed = $fromType->tryRemove($typeToRemove);
80: if ($removed !== null) {
81: return $removed;
82: }
83:
84: $fromFiniteTypes = $fromType->getFiniteTypes();
85: if (count($fromFiniteTypes) > 0) {
86: $finiteTypesToRemove = $typeToRemove->getFiniteTypes();
87: if (count($finiteTypesToRemove) === 1) {
88: $result = [];
89: foreach ($fromFiniteTypes as $finiteType) {
90: if ($finiteType->equals($finiteTypesToRemove[0])) {
91: continue;
92: }
93:
94: $result[] = $finiteType;
95: }
96:
97: if (count($result) === count($fromFiniteTypes)) {
98: return $fromType;
99: }
100:
101: if (count($result) === 0) {
102: return new NeverType();
103: }
104:
105: if (count($result) === 1) {
106: return $result[0];
107: }
108:
109: return new UnionType($result);
110: }
111: }
112:
113: return $fromType;
114: }
115:
116: public static function removeNull(Type $type): Type
117: {
118: if (self::containsNull($type)) {
119: return self::remove($type, new NullType());
120: }
121:
122: return $type;
123: }
124:
125: public static function containsNull(Type $type): bool
126: {
127: if ($type instanceof UnionType) {
128: foreach ($type->getTypes() as $innerType) {
129: if ($innerType instanceof NullType) {
130: return true;
131: }
132: }
133:
134: return false;
135: }
136:
137: return $type instanceof NullType;
138: }
139:
140: public static function union(Type ...$types): Type
141: {
142: $typesCount = count($types);
143: if ($typesCount === 0) {
144: return new NeverType();
145: }
146:
147: $benevolentTypes = [];
148: $benevolentUnionObject = null;
149: // transform A | (B | C) to A | B | C
150: for ($i = 0; $i < $typesCount; $i++) {
151: if ($types[$i] instanceof BenevolentUnionType) {
152: if ($types[$i] instanceof TemplateBenevolentUnionType && $benevolentUnionObject === null) {
153: $benevolentUnionObject = $types[$i];
154: }
155: $benevolentTypesCount = 0;
156: $typesInner = $types[$i]->getTypes();
157: foreach ($typesInner as $benevolentInnerType) {
158: $benevolentTypesCount++;
159: $benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
160: }
161: array_splice($types, $i, 1, $typesInner);
162: $typesCount += $benevolentTypesCount - 1;
163: continue;
164: }
165: if (!($types[$i] instanceof UnionType)) {
166: continue;
167: }
168: if ($types[$i] instanceof TemplateType) {
169: continue;
170: }
171:
172: $typesInner = $types[$i]->getTypes();
173: array_splice($types, $i, 1, $typesInner);
174: $typesCount += count($typesInner) - 1;
175: }
176:
177: if ($typesCount === 1) {
178: return $types[0];
179: }
180:
181: $arrayTypes = [];
182: $scalarTypes = [];
183: $hasGenericScalarTypes = [];
184: $enumCaseTypes = [];
185: for ($i = 0; $i < $typesCount; $i++) {
186: if ($types[$i] instanceof ConstantScalarType) {
187: $type = $types[$i];
188: $scalarTypes[get_class($type)][md5($type->describe(VerbosityLevel::cache()))] = $type;
189: unset($types[$i]);
190: continue;
191: }
192: if ($types[$i] instanceof BooleanType) {
193: $hasGenericScalarTypes[ConstantBooleanType::class] = true;
194: }
195: if ($types[$i] instanceof FloatType) {
196: $hasGenericScalarTypes[ConstantFloatType::class] = true;
197: }
198: if ($types[$i] instanceof IntegerType && !$types[$i] instanceof IntegerRangeType) {
199: $hasGenericScalarTypes[ConstantIntegerType::class] = true;
200: }
201: if ($types[$i] instanceof StringType && !$types[$i] instanceof ClassStringType) {
202: $hasGenericScalarTypes[ConstantStringType::class] = true;
203: }
204: if ($types[$i] instanceof EnumCaseObjectType) {
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 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:
673: foreach ($arrayTypes as $arrayType) {
674: $isConstantArray = $arrayType->isConstantArray()->yes();
675: if (!$isConstantArray || !$arrayType->isIterableAtLeastOnce()->no()) {
676: $filledArrays++;
677: }
678:
679: if ($generalArrayOccurred || !$isConstantArray) {
680: foreach ($arrayType->getArrays() as $type) {
681: $keyTypesForGeneralArray[] = $type->getIterableKeyType();
682: $valueTypesForGeneralArray[] = $type->getItemType();
683: $generalArrayOccurred = true;
684: }
685: continue;
686: }
687:
688: $constantArrays = $arrayType->getConstantArrays();
689: foreach ($constantArrays as $constantArray) {
690: foreach ($constantArray->getKeyTypes() as $i => $keyType) {
691: $keyTypesForGeneralArray[] = $keyType;
692: $valueTypesForGeneralArray[] = $constantArray->getValueTypes()[$i];
693:
694: $keyTypeValue = $keyType->getValue();
695: if (array_key_exists($keyTypeValue, $constantKeyTypesNumbered)) {
696: continue;
697: }
698:
699: $constantKeyTypesNumbered[$keyTypeValue] = $nextConstantKeyTypeIndex;
700: $nextConstantKeyTypeIndex *= 2;
701: if (!is_int($nextConstantKeyTypeIndex)) {
702: $generalArrayOccurred = true;
703: $overflowed = true;
704: continue 2;
705: }
706: }
707: }
708: }
709:
710: if ($generalArrayOccurred && (!$overflowed || $filledArrays > 1)) {
711: $scopes = [];
712: $useTemplateArray = true;
713: foreach ($arrayTypes as $arrayType) {
714: if (!$arrayType instanceof TemplateArrayType) {
715: $useTemplateArray = false;
716: break;
717: }
718:
719: $scopes[$arrayType->getScope()->describe()] = $arrayType;
720: }
721:
722: $arrayType = new ArrayType(
723: self::union(...$keyTypesForGeneralArray),
724: self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
725: );
726:
727: if ($useTemplateArray && count($scopes) === 1) {
728: $templateArray = array_values($scopes)[0];
729: $arrayType = new TemplateArrayType(
730: $templateArray->getScope(),
731: $templateArray->getStrategy(),
732: $templateArray->getVariance(),
733: $templateArray->getName(),
734: $arrayType,
735: );
736: }
737:
738: return [
739: self::intersect($arrayType, ...$accessoryTypes),
740: ];
741: }
742:
743: $reducedArrayTypes = self::reduceArrays($arrayTypes);
744:
745: return array_map(
746: static fn (Type $arrayType) => self::intersect($arrayType, ...$accessoryTypes),
747: self::optimizeConstantArrays($reducedArrayTypes),
748: );
749: }
750:
751: /**
752: * @param Type[] $types
753: * @return Type[]
754: */
755: private static function optimizeConstantArrays(array $types): array
756: {
757: $constantArrayValuesCount = self::countConstantArrayValueTypes($types);
758:
759: if ($constantArrayValuesCount > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
760: $results = [];
761: foreach ($types as $type) {
762: $results[] = TypeTraverser::map($type, static function (Type $type, callable $traverse): Type {
763: if ($type instanceof ConstantArrayType) {
764: if ($type->isIterableAtLeastOnce()->no()) {
765: return $type;
766: }
767:
768: $isList = true;
769: $valueTypes = [];
770: $keyTypes = [];
771: $nextAutoIndex = 0;
772: foreach ($type->getKeyTypes() as $i => $innerKeyType) {
773: if (!$innerKeyType instanceof ConstantIntegerType) {
774: $isList = false;
775: } elseif ($innerKeyType->getValue() !== $nextAutoIndex) {
776: $isList = false;
777: $nextAutoIndex = $innerKeyType->getValue() + 1;
778: } else {
779: $nextAutoIndex++;
780: }
781:
782: $generalizedKeyType = $innerKeyType->generalize(GeneralizePrecision::moreSpecific());
783: $keyTypes[$generalizedKeyType->describe(VerbosityLevel::precise())] = $generalizedKeyType;
784:
785: $innerValueType = $type->getValueTypes()[$i];
786: $generalizedValueType = TypeTraverser::map($innerValueType, static function (Type $type, callable $innerTraverse) use ($traverse): Type {
787: if ($type instanceof ArrayType) {
788: return TypeCombinator::intersect($type, new OversizedArrayType());
789: }
790:
791: return $traverse($type);
792: });
793: $valueTypes[$generalizedValueType->describe(VerbosityLevel::precise())] = $generalizedValueType;
794: }
795:
796: $keyType = TypeCombinator::union(...array_values($keyTypes));
797: $valueType = TypeCombinator::union(...array_values($valueTypes));
798:
799: $arrayType = new ArrayType($keyType, $valueType);
800: if ($isList) {
801: $arrayType = AccessoryArrayListType::intersectWith($arrayType);
802: }
803:
804: return TypeCombinator::intersect($arrayType, new NonEmptyArrayType(), new OversizedArrayType());
805: }
806:
807: return $traverse($type);
808: });
809: }
810:
811: return $results;
812: }
813:
814: return $types;
815: }
816:
817: /**
818: * @param Type[] $types
819: */
820: private static function countConstantArrayValueTypes(array $types): int
821: {
822: $constantArrayValuesCount = 0;
823: foreach ($types as $type) {
824: TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$constantArrayValuesCount): Type {
825: if ($type instanceof ConstantArrayType) {
826: $constantArrayValuesCount += count($type->getValueTypes());
827: }
828:
829: return $traverse($type);
830: });
831: }
832: return $constantArrayValuesCount;
833: }
834:
835: /**
836: * @param Type[] $constantArrays
837: * @return Type[]
838: */
839: private static function reduceArrays(array $constantArrays): array
840: {
841: $newArrays = [];
842: $arraysToProcess = [];
843: $emptyArray = null;
844: foreach ($constantArrays as $constantArray) {
845: if (!$constantArray->isConstantArray()->yes()) {
846: $newArrays[] = $constantArray;
847: continue;
848: }
849:
850: if ($constantArray->isIterableAtLeastOnce()->no()) {
851: $emptyArray = $constantArray;
852: continue;
853: }
854:
855: $arraysToProcess = array_merge($arraysToProcess, $constantArray->getConstantArrays());
856: }
857:
858: if ($emptyArray !== null) {
859: $newArrays[] = $emptyArray;
860: }
861:
862: $arraysToProcessPerKey = [];
863: foreach ($arraysToProcess as $i => $arrayToProcess) {
864: foreach ($arrayToProcess->getKeyTypes() as $keyType) {
865: $arraysToProcessPerKey[$keyType->getValue()][] = $i;
866: }
867: }
868:
869: $eligibleCombinations = [];
870:
871: foreach ($arraysToProcessPerKey as $arrays) {
872: for ($i = 0, $arraysCount = count($arrays); $i < $arraysCount - 1; $i++) {
873: for ($j = $i + 1; $j < $arraysCount; $j++) {
874: $eligibleCombinations[$arrays[$i]][$arrays[$j]] ??= 0;
875: $eligibleCombinations[$arrays[$i]][$arrays[$j]]++;
876: }
877: }
878: }
879:
880: foreach ($eligibleCombinations as $i => $other) {
881: if (!array_key_exists($i, $arraysToProcess)) {
882: continue;
883: }
884:
885: foreach ($other as $j => $overlappingKeysCount) {
886: if (!array_key_exists($j, $arraysToProcess)) {
887: continue;
888: }
889:
890: if (
891: $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
892: && $arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])
893: ) {
894: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
895: unset($arraysToProcess[$i]);
896: continue 2;
897: }
898:
899: if (
900: $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
901: && $arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])
902: ) {
903: $arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
904: unset($arraysToProcess[$j]);
905: continue 1;
906: }
907: }
908: }
909:
910: return array_merge($newArrays, $arraysToProcess);
911: }
912:
913: public static function intersect(Type ...$types): Type
914: {
915: $types = array_values($types);
916:
917: $typesCount = count($types);
918: if ($typesCount === 0) {
919: return new NeverType();
920: }
921: if ($typesCount === 1) {
922: return $types[0];
923: }
924:
925: $sortTypes = static function (Type $a, Type $b): int {
926: if (!$a instanceof UnionType || !$b instanceof UnionType) {
927: return 0;
928: }
929:
930: if ($a instanceof TemplateType) {
931: return -1;
932: }
933: if ($b instanceof TemplateType) {
934: return 1;
935: }
936:
937: if ($a instanceof BenevolentUnionType) {
938: return -1;
939: }
940: if ($b instanceof BenevolentUnionType) {
941: return 1;
942: }
943:
944: return 0;
945: };
946: usort($types, $sortTypes);
947: // transform A & (B | C) to (A & B) | (A & C)
948: foreach ($types as $i => $type) {
949: if (!$type instanceof UnionType) {
950: continue;
951: }
952:
953: $topLevelUnionSubTypes = [];
954: $innerTypes = $type->getTypes();
955: usort($innerTypes, $sortTypes);
956: $slice1 = array_slice($types, 0, $i);
957: $slice2 = array_slice($types, $i + 1);
958: foreach ($innerTypes as $innerUnionSubType) {
959: $topLevelUnionSubTypes[] = self::intersect(
960: $innerUnionSubType,
961: ...$slice1,
962: ...$slice2,
963: );
964: }
965:
966: $union = self::union(...$topLevelUnionSubTypes);
967: if ($union instanceof NeverType) {
968: return $union;
969: }
970:
971: if ($type instanceof BenevolentUnionType) {
972: $union = TypeUtils::toBenevolentUnion($union);
973: }
974:
975: if ($type instanceof TemplateUnionType || $type instanceof TemplateBenevolentUnionType) {
976: $union = TemplateTypeFactory::create(
977: $type->getScope(),
978: $type->getName(),
979: $union,
980: $type->getVariance(),
981: $type->getStrategy(),
982: );
983: }
984:
985: return $union;
986: }
987: $typesCount = count($types);
988:
989: // transform A & (B & C) to A & B & C
990: for ($i = 0; $i < $typesCount; $i++) {
991: $type = $types[$i];
992:
993: if (!($type instanceof IntersectionType)) {
994: continue;
995: }
996:
997: array_splice($types, $i--, 1, $type->getTypes());
998: $typesCount = count($types);
999: }
1000:
1001: $hasOffsetValueTypeCount = 0;
1002: $newTypes = [];
1003: foreach ($types as $type) {
1004: if (!$type instanceof HasOffsetValueType) {
1005: $newTypes[] = $type;
1006: continue;
1007: }
1008:
1009: $hasOffsetValueTypeCount++;
1010: }
1011:
1012: if ($hasOffsetValueTypeCount > 32) {
1013: $newTypes[] = new OversizedArrayType();
1014: $types = $newTypes;
1015: $typesCount = count($types);
1016: }
1017:
1018: usort($types, static function (Type $a, Type $b): int {
1019: // move subtractables with subtracts before those without to avoid loosing them in the union logic
1020: if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
1021: return -1;
1022: }
1023: if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
1024: return 1;
1025: }
1026:
1027: if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
1028: return -1;
1029: }
1030: if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
1031: return 1;
1032: }
1033:
1034: return 0;
1035: });
1036:
1037: // transform IntegerType & ConstantIntegerType to ConstantIntegerType
1038: // transform Child & Parent to Child
1039: // transform Object & ~null to Object
1040: // transform A & A to A
1041: // transform int[] & string to never
1042: // transform callable & int to never
1043: // transform A & ~A to never
1044: // transform int & string to never
1045: for ($i = 0; $i < $typesCount; $i++) {
1046: for ($j = $i + 1; $j < $typesCount; $j++) {
1047: if ($types[$j] instanceof SubtractableType) {
1048: $typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
1049:
1050: if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
1051: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
1052: } else {
1053: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
1054: }
1055: if ($isSuperTypeSubtractableA->yes()) {
1056: $types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
1057: array_splice($types, $j--, 1);
1058: $typesCount--;
1059: continue 1;
1060: }
1061: }
1062:
1063: if ($types[$i] instanceof SubtractableType) {
1064: $typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
1065:
1066: if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
1067: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
1068: } else {
1069: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
1070: }
1071: if ($isSuperTypeSubtractableB->yes()) {
1072: $types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
1073: array_splice($types, $i--, 1);
1074: $typesCount--;
1075: continue 2;
1076: }
1077: }
1078:
1079: if ($types[$i] instanceof IntegerRangeType) {
1080: $intersectionType = $types[$i]->tryIntersect($types[$j]);
1081: if ($intersectionType !== null) {
1082: $types[$j] = $intersectionType;
1083: array_splice($types, $i--, 1);
1084: $typesCount--;
1085: continue 2;
1086: }
1087: }
1088:
1089: if ($types[$j] instanceof IterableType) {
1090: $isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
1091: } else {
1092: $isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
1093: }
1094:
1095: if ($isSuperTypeA->yes()) {
1096: array_splice($types, $j--, 1);
1097: $typesCount--;
1098: continue;
1099: }
1100:
1101: if ($types[$i] instanceof IterableType) {
1102: $isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
1103: } else {
1104: $isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
1105: }
1106:
1107: if ($isSuperTypeB->maybe()) {
1108: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
1109: $types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
1110: array_splice($types, $j--, 1);
1111: $typesCount--;
1112: continue;
1113: }
1114:
1115: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
1116: $types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
1117: array_splice($types, $i--, 1);
1118: $typesCount--;
1119: continue 2;
1120: }
1121:
1122: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
1123: $offsetType = $types[$j]->getOffsetType();
1124: $valueType = $types[$j]->getValueType();
1125: $newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
1126: if ($newValueType instanceof NeverType) {
1127: return $newValueType;
1128: }
1129: $types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
1130: array_splice($types, $j--, 1);
1131: $typesCount--;
1132: continue;
1133: }
1134:
1135: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
1136: $offsetType = $types[$i]->getOffsetType();
1137: $valueType = $types[$i]->getValueType();
1138: $newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
1139: if ($newValueType instanceof NeverType) {
1140: return $newValueType;
1141: }
1142:
1143: $types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
1144: array_splice($types, $i--, 1);
1145: $typesCount--;
1146: continue 2;
1147: }
1148:
1149: if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
1150: array_splice($types, $j--, 1);
1151: $typesCount--;
1152: continue;
1153: }
1154:
1155: if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
1156: array_splice($types, $i--, 1);
1157: $typesCount--;
1158: continue 2;
1159: }
1160:
1161: if ($types[$i] instanceof ObjectShapeType && $types[$j] instanceof HasPropertyType) {
1162: $types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
1163: array_splice($types, $j--, 1);
1164: $typesCount--;
1165: continue;
1166: }
1167:
1168: if ($types[$j] instanceof ObjectShapeType && $types[$i] instanceof HasPropertyType) {
1169: $types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
1170: array_splice($types, $i--, 1);
1171: $typesCount--;
1172: continue 2;
1173: }
1174:
1175: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof ArrayType) {
1176: $newArray = ConstantArrayTypeBuilder::createEmpty();
1177: $valueTypes = $types[$i]->getValueTypes();
1178: foreach ($types[$i]->getKeyTypes() as $k => $keyType) {
1179: $newArray->setOffsetValueType(
1180: self::intersect($keyType, $types[$j]->getIterableKeyType()),
1181: self::intersect($valueTypes[$k], $types[$j]->getIterableValueType()),
1182: $types[$i]->isOptionalKey($k) && !$types[$j]->hasOffsetValueType($keyType)->yes(),
1183: );
1184: }
1185: $types[$i] = $newArray->getArray();
1186: array_splice($types, $j--, 1);
1187: $typesCount--;
1188: continue 2;
1189: }
1190:
1191: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof ArrayType) {
1192: $newArray = ConstantArrayTypeBuilder::createEmpty();
1193: $valueTypes = $types[$j]->getValueTypes();
1194: foreach ($types[$j]->getKeyTypes() as $k => $keyType) {
1195: $newArray->setOffsetValueType(
1196: self::intersect($keyType, $types[$i]->getIterableKeyType()),
1197: self::intersect($valueTypes[$k], $types[$i]->getIterableValueType()),
1198: $types[$j]->isOptionalKey($k) && !$types[$i]->hasOffsetValueType($keyType)->yes(),
1199: );
1200: }
1201: $types[$j] = $newArray->getArray();
1202: array_splice($types, $i--, 1);
1203: $typesCount--;
1204: continue 2;
1205: }
1206:
1207: if (
1208: ($types[$i] instanceof ArrayType || $types[$i] instanceof IterableType) &&
1209: ($types[$j] instanceof ArrayType || $types[$j] instanceof IterableType)
1210: ) {
1211: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
1212: $itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
1213: if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
1214: $types[$j] = new IterableType($keyType, $itemType);
1215: } else {
1216: $types[$j] = new ArrayType($keyType, $itemType);
1217: }
1218: array_splice($types, $i--, 1);
1219: $typesCount--;
1220: continue 2;
1221: }
1222:
1223: if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
1224: $genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
1225: $types[$i] = new GenericClassStringType($genericType);
1226: array_splice($types, $j--, 1);
1227: $typesCount--;
1228: continue;
1229: }
1230:
1231: if (
1232: $types[$i] instanceof ArrayType
1233: && get_class($types[$i]) === ArrayType::class
1234: && $types[$j] instanceof AccessoryArrayListType
1235: && !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
1236: ) {
1237: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
1238: if ($keyType instanceof NeverType) {
1239: return $keyType;
1240: }
1241: $types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
1242: continue;
1243: }
1244:
1245: continue;
1246: }
1247:
1248: if ($isSuperTypeB->yes()) {
1249: array_splice($types, $i--, 1);
1250: $typesCount--;
1251: continue 2;
1252: }
1253:
1254: if ($isSuperTypeA->no()) {
1255: return new NeverType();
1256: }
1257: }
1258: }
1259:
1260: if ($typesCount === 1) {
1261: return $types[0];
1262: }
1263:
1264: return new IntersectionType($types);
1265: }
1266:
1267: public static function removeFalsey(Type $type): Type
1268: {
1269: return self::remove($type, StaticTypeFactory::falsey());
1270: }
1271:
1272: }
1273:
PHPStan API documentation generated by ApiGen dev-master