1: <?php declare(strict_types = 1);
2:
3: namespace PHPStan\Type;
4:
5: use PHPStan\Type\Accessory\AccessoryNonEmptyStringType;
6: use PHPStan\Type\Accessory\AccessoryType;
7: use PHPStan\Type\Accessory\HasOffsetType;
8: use PHPStan\Type\Accessory\HasOffsetValueType;
9: use PHPStan\Type\Accessory\NonEmptyArrayType;
10: use PHPStan\Type\Accessory\OversizedArrayType;
11: use PHPStan\Type\Constant\ConstantArrayType;
12: use PHPStan\Type\Constant\ConstantArrayTypeBuilder;
13: use PHPStan\Type\Constant\ConstantBooleanType;
14: use PHPStan\Type\Constant\ConstantFloatType;
15: use PHPStan\Type\Constant\ConstantIntegerType;
16: use PHPStan\Type\Constant\ConstantStringType;
17: use PHPStan\Type\Generic\GenericClassStringType;
18: use PHPStan\Type\Generic\TemplateBenevolentUnionType;
19: use PHPStan\Type\Generic\TemplateType;
20: use PHPStan\Type\Generic\TemplateTypeFactory;
21: use PHPStan\Type\Generic\TemplateUnionType;
22: use function array_intersect_key;
23: use function array_key_exists;
24: use function array_keys;
25: use function array_map;
26: use function array_merge;
27: use function array_slice;
28: use function array_splice;
29: use function array_values;
30: use function count;
31: use function get_class;
32: use function is_int;
33: use function md5;
34: use function sprintf;
35: use function usort;
36:
37: /** @api */
38: class TypeCombinator
39: {
40:
41: public static function addNull(Type $type): Type
42: {
43: if ((new NullType())->isSuperTypeOf($type)->no()) {
44: return self::union($type, new NullType());
45: }
46:
47: return $type;
48: }
49:
50: public static function remove(Type $fromType, Type $typeToRemove): Type
51: {
52: if ($typeToRemove instanceof UnionType) {
53: foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
54: $fromType = self::remove($fromType, $unionTypeToRemove);
55: }
56: return $fromType;
57: }
58:
59: $isSuperType = $typeToRemove->isSuperTypeOf($fromType);
60: if ($isSuperType->yes()) {
61: return new NeverType();
62: }
63: if ($isSuperType->no()) {
64: return $fromType;
65: }
66:
67: if ($typeToRemove instanceof MixedType) {
68: $typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
69: if ($typeToRemoveSubtractedType !== null) {
70: return self::intersect($fromType, $typeToRemoveSubtractedType);
71: }
72: }
73:
74: return $fromType->tryRemove($typeToRemove) ?? $fromType;
75: }
76:
77: public static function removeNull(Type $type): Type
78: {
79: if (self::containsNull($type)) {
80: return self::remove($type, new NullType());
81: }
82:
83: return $type;
84: }
85:
86: public static function containsNull(Type $type): bool
87: {
88: if ($type instanceof UnionType) {
89: foreach ($type->getTypes() as $innerType) {
90: if ($innerType instanceof NullType) {
91: return true;
92: }
93: }
94:
95: return false;
96: }
97:
98: return $type instanceof NullType;
99: }
100:
101: public static function union(Type ...$types): Type
102: {
103: $typesCount = count($types);
104: if ($typesCount === 0) {
105: return new NeverType();
106: }
107:
108: $benevolentTypes = [];
109: $benevolentUnionObject = null;
110: // transform A | (B | C) to A | B | C
111: for ($i = 0; $i < $typesCount; $i++) {
112: if ($types[$i] instanceof BenevolentUnionType) {
113: if ($types[$i] instanceof TemplateBenevolentUnionType && $benevolentUnionObject === null) {
114: $benevolentUnionObject = $types[$i];
115: }
116: $benevolentTypesCount = 0;
117: $typesInner = $types[$i]->getTypes();
118: foreach ($typesInner as $benevolentInnerType) {
119: $benevolentTypesCount++;
120: $benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
121: }
122: array_splice($types, $i, 1, $typesInner);
123: $typesCount += $benevolentTypesCount - 1;
124: continue;
125: }
126: if (!($types[$i] instanceof UnionType)) {
127: continue;
128: }
129: if ($types[$i] instanceof TemplateType) {
130: continue;
131: }
132:
133: $typesInner = $types[$i]->getTypes();
134: array_splice($types, $i, 1, $typesInner);
135: $typesCount += count($typesInner) - 1;
136: }
137:
138: if ($typesCount === 1) {
139: return $types[0];
140: }
141:
142: $arrayTypes = [];
143: $arrayAccessoryTypes = [];
144: $scalarTypes = [];
145: $hasGenericScalarTypes = [];
146: for ($i = 0; $i < $typesCount; $i++) {
147: if ($types[$i] instanceof ConstantScalarType) {
148: $type = $types[$i];
149: $scalarTypes[get_class($type)][md5($type->describe(VerbosityLevel::cache()))] = $type;
150: unset($types[$i]);
151: continue;
152: }
153: if ($types[$i] instanceof BooleanType) {
154: $hasGenericScalarTypes[ConstantBooleanType::class] = true;
155: }
156: if ($types[$i] instanceof FloatType) {
157: $hasGenericScalarTypes[ConstantFloatType::class] = true;
158: }
159: if ($types[$i] instanceof IntegerType && !$types[$i] instanceof IntegerRangeType) {
160: $hasGenericScalarTypes[ConstantIntegerType::class] = true;
161: }
162: if ($types[$i] instanceof StringType && !$types[$i] instanceof ClassStringType) {
163: $hasGenericScalarTypes[ConstantStringType::class] = true;
164: }
165: if ($types[$i] instanceof IntersectionType) {
166: $intermediateArrayType = null;
167: $intermediateAccessoryTypes = [];
168: foreach ($types[$i]->getTypes() as $innerType) {
169: if ($innerType instanceof TemplateType) {
170: continue 2;
171: }
172: if ($innerType instanceof ArrayType) {
173: $intermediateArrayType = $innerType;
174: continue;
175: }
176: if ($innerType instanceof AccessoryType || $innerType instanceof CallableType) {
177: if ($innerType instanceof HasOffsetValueType) {
178: $intermediateAccessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][] = $innerType;
179: continue;
180: }
181:
182: $intermediateAccessoryTypes[$innerType->describe(VerbosityLevel::cache())][] = $innerType;
183: continue;
184: }
185: }
186:
187: if ($intermediateArrayType !== null) {
188: $arrayTypes[] = $intermediateArrayType;
189: $arrayAccessoryTypes[] = $intermediateAccessoryTypes;
190: unset($types[$i]);
191: continue;
192: }
193: }
194: if (!$types[$i] instanceof ArrayType) {
195: continue;
196: }
197:
198: $arrayTypes[] = $types[$i];
199:
200: if ($types[$i]->isIterableAtLeastOnce()->yes()) {
201: $nonEmpty = new NonEmptyArrayType();
202: $arrayAccessoryTypes[] = [$nonEmpty->describe(VerbosityLevel::cache()) => [$nonEmpty]];
203: } else {
204: $arrayAccessoryTypes[] = [];
205: }
206: unset($types[$i]);
207: }
208:
209: foreach ($scalarTypes as $classType => $scalarTypeItems) {
210: $scalarTypes[$classType] = array_values($scalarTypeItems);
211: }
212:
213: /** @var ArrayType[] $arrayTypes */
214: $arrayTypes = $arrayTypes;
215:
216: $commonArrayAccessoryTypesKeys = [];
217: if (count($arrayAccessoryTypes) > 1) {
218: $commonArrayAccessoryTypesKeys = array_keys(array_intersect_key(...$arrayAccessoryTypes));
219: } elseif (count($arrayAccessoryTypes) > 0) {
220: $commonArrayAccessoryTypesKeys = array_keys($arrayAccessoryTypes[0]);
221: }
222:
223: $arrayAccessoryTypesToProcess = [];
224: foreach ($commonArrayAccessoryTypesKeys as $commonKey) {
225: $typesToUnion = [];
226: foreach ($arrayAccessoryTypes as $array) {
227: foreach ($array[$commonKey] as $arrayAccessoryType) {
228: $typesToUnion[] = $arrayAccessoryType;
229: }
230: }
231: $arrayAccessoryTypesToProcess[] = self::union(...$typesToUnion);
232: }
233:
234: $types = array_values(
235: array_merge(
236: $types,
237: self::processArrayTypes($arrayTypes, $arrayAccessoryTypesToProcess),
238: ),
239: );
240: $typesCount = count($types);
241:
242: // simplify string[] | int[] to (string|int)[]
243: for ($i = 0; $i < $typesCount; $i++) {
244: for ($j = $i + 1; $j < $typesCount; $j++) {
245: if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
246: $types[$i] = new IterableType(
247: self::union($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType()),
248: self::union($types[$i]->getIterableValueType(), $types[$j]->getIterableValueType()),
249: );
250: array_splice($types, $j, 1);
251: $typesCount--;
252: continue 2;
253: }
254: }
255: }
256:
257: foreach ($scalarTypes as $classType => $scalarTypeItems) {
258: if (isset($hasGenericScalarTypes[$classType])) {
259: unset($scalarTypes[$classType]);
260: continue;
261: }
262: if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
263: $types[] = new BooleanType();
264: $typesCount++;
265: unset($scalarTypes[$classType]);
266: continue;
267: }
268:
269: $scalarTypeItemsCount = count($scalarTypeItems);
270: for ($i = 0; $i < $typesCount; $i++) {
271: for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
272: $compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
273: if ($compareResult === null) {
274: continue;
275: }
276:
277: [$a, $b] = $compareResult;
278: if ($a !== null) {
279: $types[$i] = $a;
280: array_splice($scalarTypeItems, $j--, 1);
281: $scalarTypeItemsCount--;
282: continue 1;
283: }
284: if ($b !== null) {
285: $scalarTypeItems[$j] = $b;
286: array_splice($types, $i--, 1);
287: $typesCount--;
288: continue 2;
289: }
290: }
291: }
292:
293: $scalarTypes[$classType] = $scalarTypeItems;
294: }
295:
296: if (count($types) > 16) {
297: $newTypes = [];
298: foreach ($types as $type) {
299: $newTypes[$type->describe(VerbosityLevel::cache())] = $type;
300: }
301: $types = array_values($newTypes);
302: $typesCount = count($types);
303: }
304:
305: // transform A | A to A
306: // transform A | never to A
307: for ($i = 0; $i < $typesCount; $i++) {
308: for ($j = $i + 1; $j < $typesCount; $j++) {
309: $compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
310: if ($compareResult === null) {
311: continue;
312: }
313:
314: [$a, $b] = $compareResult;
315: if ($a !== null) {
316: $types[$i] = $a;
317: array_splice($types, $j--, 1);
318: $typesCount--;
319: continue 1;
320: }
321: if ($b !== null) {
322: $types[$j] = $b;
323: array_splice($types, $i--, 1);
324: $typesCount--;
325: continue 2;
326: }
327: }
328: }
329:
330: foreach ($scalarTypes as $scalarTypeItems) {
331: foreach ($scalarTypeItems as $scalarType) {
332: $types[] = $scalarType;
333: $typesCount++;
334: }
335: }
336:
337: if ($typesCount === 0) {
338: return new NeverType();
339: }
340: if ($typesCount === 1) {
341: return $types[0];
342: }
343:
344: if ($benevolentTypes !== []) {
345: $tempTypes = $types;
346: foreach ($tempTypes as $i => $type) {
347: if (!isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
348: break;
349: }
350:
351: unset($tempTypes[$i]);
352: }
353:
354: if ($tempTypes === []) {
355: if ($benevolentUnionObject instanceof TemplateBenevolentUnionType) {
356: return $benevolentUnionObject->withTypes($types);
357: }
358:
359: return new BenevolentUnionType($types);
360: }
361: }
362:
363: return new UnionType($types);
364: }
365:
366: /**
367: * @return array{Type, null}|array{null, Type}|null
368: */
369: private static function compareTypesInUnion(Type $a, Type $b): ?array
370: {
371: if ($a instanceof IntegerRangeType) {
372: $type = $a->tryUnion($b);
373: if ($type !== null) {
374: $a = $type;
375: return [$a, null];
376: }
377: }
378: if ($b instanceof IntegerRangeType) {
379: $type = $b->tryUnion($a);
380: if ($type !== null) {
381: $b = $type;
382: return [null, $b];
383: }
384: }
385: if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
386: return null;
387: }
388: if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
389: if ($a->getOffsetType()->equals($b->getOffsetType())) {
390: return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
391: }
392: }
393: if ($a instanceof ConstantArrayType && $b instanceof ConstantArrayType) {
394: return null;
395: }
396:
397: if ($a instanceof SubtractableType) {
398: $typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
399: if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
400: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
401: } else {
402: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
403: }
404: if ($isSuperType->yes()) {
405: $a = self::intersectWithSubtractedType($a, $b);
406: return [$a, null];
407: }
408: }
409:
410: if ($b instanceof SubtractableType) {
411: $typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
412: if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
413: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
414: } else {
415: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
416: }
417: if ($isSuperType->yes()) {
418: $b = self::intersectWithSubtractedType($b, $a);
419: return [null, $b];
420: }
421: }
422:
423: if ($b->isSuperTypeOf($a)->yes()) {
424: return [null, $b];
425: }
426:
427: if ($a->isSuperTypeOf($b)->yes()) {
428: return [$a, null];
429: }
430:
431: if (
432: $a instanceof ConstantStringType
433: && $a->getValue() === ''
434: && ($b->describe(VerbosityLevel::value()) === 'non-empty-string'
435: || $b->describe(VerbosityLevel::value()) === 'non-falsy-string')
436: ) {
437: return [null, new StringType()];
438: }
439:
440: if (
441: $b instanceof ConstantStringType
442: && $b->getValue() === ''
443: && ($a->describe(VerbosityLevel::value()) === 'non-empty-string'
444: || $a->describe(VerbosityLevel::value()) === 'non-falsy-string')
445: ) {
446: return [new StringType(), null];
447: }
448:
449: if (
450: $a instanceof ConstantStringType
451: && $a->getValue() === '0'
452: && $b->describe(VerbosityLevel::value()) === 'non-falsy-string'
453: ) {
454: return [null, new IntersectionType([
455: new StringType(),
456: new AccessoryNonEmptyStringType(),
457: ])];
458: }
459:
460: if (
461: $b instanceof ConstantStringType
462: && $b->getValue() === '0'
463: && $a->describe(VerbosityLevel::value()) === 'non-falsy-string'
464: ) {
465: return [new IntersectionType([
466: new StringType(),
467: new AccessoryNonEmptyStringType(),
468: ]), null];
469: }
470:
471: return null;
472: }
473:
474: private static function unionWithSubtractedType(
475: Type $type,
476: ?Type $subtractedType,
477: ): Type
478: {
479: if ($subtractedType === null) {
480: return $type;
481: }
482:
483: if ($type instanceof SubtractableType) {
484: if ($type->getSubtractedType() === null) {
485: return $type;
486: }
487:
488: $subtractedType = self::union(
489: $type->getSubtractedType(),
490: $subtractedType,
491: );
492: if ($subtractedType instanceof NeverType) {
493: $subtractedType = null;
494: }
495:
496: return $type->changeSubtractedType($subtractedType);
497: }
498:
499: if ($subtractedType->isSuperTypeOf($type)->yes()) {
500: return new NeverType();
501: }
502:
503: return self::remove($type, $subtractedType);
504: }
505:
506: private static function intersectWithSubtractedType(
507: SubtractableType $a,
508: Type $b,
509: ): Type
510: {
511: if ($a->getSubtractedType() === null) {
512: return $a;
513: }
514:
515: if ($b instanceof IntersectionType) {
516: $subtractableTypes = [];
517: foreach ($b->getTypes() as $innerType) {
518: if (!$innerType instanceof SubtractableType) {
519: continue;
520: }
521:
522: $subtractableTypes[] = $innerType;
523: }
524:
525: if (count($subtractableTypes) === 0) {
526: return $a->getTypeWithoutSubtractedType();
527: }
528:
529: $subtractedTypes = [];
530: foreach ($subtractableTypes as $subtractableType) {
531: if ($subtractableType->getSubtractedType() === null) {
532: continue;
533: }
534:
535: $subtractedTypes[] = $subtractableType->getSubtractedType();
536: }
537:
538: if (count($subtractedTypes) === 0) {
539: return $a->getTypeWithoutSubtractedType();
540:
541: }
542:
543: $subtractedType = self::union(...$subtractedTypes);
544: } elseif ($b instanceof SubtractableType) {
545: $subtractedType = $b->getSubtractedType();
546: if ($subtractedType === null) {
547: return $a->getTypeWithoutSubtractedType();
548: }
549: } else {
550: $subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
551: if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
552: return $a->getTypeWithoutSubtractedType();
553: }
554: $subtractedType = new MixedType(false, $b);
555: }
556:
557: $subtractedType = self::intersect(
558: $a->getSubtractedType(),
559: $subtractedType,
560: );
561: if ($subtractedType instanceof NeverType) {
562: $subtractedType = null;
563: }
564:
565: return $a->changeSubtractedType($subtractedType);
566: }
567:
568: /**
569: * @param ArrayType[] $arrayTypes
570: * @param Type[] $accessoryTypes
571: * @return Type[]
572: */
573: private static function processArrayTypes(array $arrayTypes, array $accessoryTypes): array
574: {
575: foreach ($arrayTypes as $arrayType) {
576: if (!$arrayType instanceof ConstantArrayType) {
577: continue;
578: }
579: if (count($arrayType->getKeyTypes()) > 0) {
580: continue;
581: }
582:
583: foreach ($accessoryTypes as $i => $accessoryType) {
584: if (!$accessoryType instanceof NonEmptyArrayType) {
585: continue;
586: }
587:
588: unset($accessoryTypes[$i]);
589: break 2;
590: }
591: }
592:
593: if ($arrayTypes === []) {
594: return [];
595: }
596: if (count($arrayTypes) === 1) {
597: return [
598: self::intersect(...$arrayTypes, ...$accessoryTypes),
599: ];
600: }
601:
602: $keyTypesForGeneralArray = [];
603: $valueTypesForGeneralArray = [];
604: $generalArrayOccurred = false;
605: $constantKeyTypesNumbered = [];
606:
607: /** @var int|float $nextConstantKeyTypeIndex */
608: $nextConstantKeyTypeIndex = 1;
609:
610: foreach ($arrayTypes as $arrayType) {
611: if (!$arrayType instanceof ConstantArrayType || $generalArrayOccurred) {
612: $keyTypesForGeneralArray[] = $arrayType->getKeyType();
613: $valueTypesForGeneralArray[] = $arrayType->getItemType();
614: $generalArrayOccurred = true;
615: continue;
616: }
617:
618: foreach ($arrayType->getKeyTypes() as $i => $keyType) {
619: $keyTypesForGeneralArray[] = $keyType;
620: $valueTypesForGeneralArray[] = $arrayType->getValueTypes()[$i];
621:
622: $keyTypeValue = $keyType->getValue();
623: if (array_key_exists($keyTypeValue, $constantKeyTypesNumbered)) {
624: continue;
625: }
626:
627: $constantKeyTypesNumbered[$keyTypeValue] = $nextConstantKeyTypeIndex;
628: $nextConstantKeyTypeIndex *= 2;
629: if (!is_int($nextConstantKeyTypeIndex)) {
630: $generalArrayOccurred = true;
631: continue;
632: }
633: }
634: }
635:
636: if ($generalArrayOccurred) {
637: return [
638: self::intersect(new ArrayType(
639: self::union(...$keyTypesForGeneralArray),
640: self::union(...$valueTypesForGeneralArray),
641: ), ...$accessoryTypes),
642: ];
643: }
644:
645: return array_map(
646: static fn (Type $arrayType) => self::intersect($arrayType, ...$accessoryTypes),
647: self::reduceArrays($arrayTypes),
648: );
649: }
650:
651: /**
652: * @param Type[] $constantArrays
653: * @return Type[]
654: */
655: private static function reduceArrays(array $constantArrays): array
656: {
657: $newArrays = [];
658: $arraysToProcess = [];
659: $emptyArray = null;
660: foreach ($constantArrays as $constantArray) {
661: if (!$constantArray instanceof ConstantArrayType) {
662: $newArrays[] = $constantArray;
663: continue;
664: }
665:
666: if ($constantArray->isEmpty()) {
667: $emptyArray = $constantArray;
668: continue;
669: }
670:
671: $arraysToProcess[] = $constantArray;
672: }
673:
674: if ($emptyArray !== null) {
675: $newArrays[] = $emptyArray;
676: }
677:
678: $arraysToProcessPerKey = [];
679: foreach ($arraysToProcess as $i => $arrayToProcess) {
680: foreach ($arrayToProcess->getKeyTypes() as $keyType) {
681: $arraysToProcessPerKey[$keyType->getValue()][] = $i;
682: }
683: }
684:
685: $eligibleCombinations = [];
686:
687: foreach ($arraysToProcessPerKey as $arrays) {
688: for ($i = 0, $arraysCount = count($arrays); $i < $arraysCount - 1; $i++) {
689: for ($j = $i + 1; $j < $arraysCount; $j++) {
690: $eligibleCombinations[$arrays[$i]][$arrays[$j]] = $arrays[$j];
691: }
692: }
693: }
694:
695: foreach ($eligibleCombinations as $i => $other) {
696: if (!array_key_exists($i, $arraysToProcess)) {
697: continue;
698: }
699:
700: foreach ($other as $j) {
701: if (!array_key_exists($j, $arraysToProcess)) {
702: continue;
703: }
704:
705: if ($arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])) {
706: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
707: unset($arraysToProcess[$i]);
708: continue 2;
709:
710: } elseif ($arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])) {
711: $arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
712: unset($arraysToProcess[$j]);
713: continue 1;
714: }
715: }
716: }
717:
718: return array_merge($newArrays, $arraysToProcess);
719: }
720:
721: public static function intersect(Type ...$types): Type
722: {
723: $types = array_values($types);
724:
725: $sortTypes = static function (Type $a, Type $b): int {
726: if (!$a instanceof UnionType || !$b instanceof UnionType) {
727: return 0;
728: }
729:
730: if ($a instanceof TemplateType) {
731: return -1;
732: }
733: if ($b instanceof TemplateType) {
734: return 1;
735: }
736:
737: if ($a instanceof BenevolentUnionType) {
738: return -1;
739: }
740: if ($b instanceof BenevolentUnionType) {
741: return 1;
742: }
743:
744: return 0;
745: };
746: usort($types, $sortTypes);
747: // transform A & (B | C) to (A & B) | (A & C)
748: foreach ($types as $i => $type) {
749: if (!$type instanceof UnionType) {
750: continue;
751: }
752:
753: $topLevelUnionSubTypes = [];
754: $innerTypes = $type->getTypes();
755: usort($innerTypes, $sortTypes);
756: $slice1 = array_slice($types, 0, $i);
757: $slice2 = array_slice($types, $i + 1);
758: foreach ($innerTypes as $innerUnionSubType) {
759: $topLevelUnionSubTypes[] = self::intersect(
760: $innerUnionSubType,
761: ...$slice1,
762: ...$slice2,
763: );
764: }
765:
766: $union = self::union(...$topLevelUnionSubTypes);
767: if ($union instanceof NeverType) {
768: return $union;
769: }
770:
771: if ($type instanceof BenevolentUnionType) {
772: $union = TypeUtils::toBenevolentUnion($union);
773: }
774:
775: if ($type instanceof TemplateUnionType || $type instanceof TemplateBenevolentUnionType) {
776: $union = TemplateTypeFactory::create(
777: $type->getScope(),
778: $type->getName(),
779: $union,
780: $type->getVariance(),
781: $type->getStrategy(),
782: );
783: }
784:
785: return $union;
786: }
787: $typesCount = count($types);
788:
789: // transform A & (B & C) to A & B & C
790: for ($i = 0; $i < $typesCount; $i++) {
791: $type = $types[$i];
792:
793: if (!($type instanceof IntersectionType)) {
794: continue;
795: }
796:
797: array_splice($types, $i--, 1, $type->getTypes());
798: $typesCount = count($types);
799: }
800:
801: $hasOffsetValueTypeCount = 0;
802: $newTypes = [];
803: foreach ($types as $type) {
804: if (!$type instanceof HasOffsetValueType) {
805: $newTypes[] = $type;
806: continue;
807: }
808:
809: $hasOffsetValueTypeCount++;
810: }
811:
812: if ($hasOffsetValueTypeCount > 32) {
813: $newTypes[] = new OversizedArrayType();
814: $types = array_values($newTypes);
815: $typesCount = count($types);
816: }
817:
818: usort($types, static function (Type $a, Type $b): int {
819: // move subtractables with subtracts before those without to avoid loosing them in the union logic
820: if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
821: return -1;
822: }
823: if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
824: return 1;
825: }
826:
827: if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
828: return -1;
829: }
830: if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
831: return 1;
832: }
833:
834: return 0;
835: });
836:
837: // transform IntegerType & ConstantIntegerType to ConstantIntegerType
838: // transform Child & Parent to Child
839: // transform Object & ~null to Object
840: // transform A & A to A
841: // transform int[] & string to never
842: // transform callable & int to never
843: // transform A & ~A to never
844: // transform int & string to never
845: for ($i = 0; $i < $typesCount; $i++) {
846: for ($j = $i + 1; $j < $typesCount; $j++) {
847: if ($types[$j] instanceof SubtractableType) {
848: $typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
849:
850: if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
851: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
852: } else {
853: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
854: }
855: if ($isSuperTypeSubtractableA->yes()) {
856: $types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
857: array_splice($types, $j--, 1);
858: $typesCount--;
859: continue 1;
860: }
861: }
862:
863: if ($types[$i] instanceof SubtractableType) {
864: $typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
865:
866: if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
867: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
868: } else {
869: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
870: }
871: if ($isSuperTypeSubtractableB->yes()) {
872: $types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
873: array_splice($types, $i--, 1);
874: $typesCount--;
875: continue 2;
876: }
877: }
878:
879: if ($types[$i] instanceof IntegerRangeType) {
880: $intersectionType = $types[$i]->tryIntersect($types[$j]);
881: if ($intersectionType !== null) {
882: $types[$j] = $intersectionType;
883: array_splice($types, $i--, 1);
884: $typesCount--;
885: continue 2;
886: }
887: }
888:
889: if ($types[$j] instanceof IterableType) {
890: $isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
891: } else {
892: $isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
893: }
894:
895: if ($isSuperTypeA->yes()) {
896: array_splice($types, $j--, 1);
897: $typesCount--;
898: continue;
899: }
900:
901: if ($types[$i] instanceof IterableType) {
902: $isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
903: } else {
904: $isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
905: }
906:
907: if ($isSuperTypeB->maybe()) {
908: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
909: $types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
910: array_splice($types, $j--, 1);
911: $typesCount--;
912: continue;
913: }
914:
915: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
916: $types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
917: array_splice($types, $i--, 1);
918: $typesCount--;
919: continue 2;
920: }
921:
922: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
923: $offsetType = $types[$j]->getOffsetType();
924: $valueType = $types[$j]->getValueType();
925: $newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
926: if ($newValueType instanceof NeverType) {
927: return new NeverType();
928: }
929: $types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
930: array_splice($types, $j--, 1);
931: $typesCount--;
932: continue;
933: }
934:
935: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
936: $offsetType = $types[$i]->getOffsetType();
937: $valueType = $types[$i]->getValueType();
938: $newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
939: if ($newValueType instanceof NeverType) {
940: return new NeverType();
941: }
942:
943: $types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
944: array_splice($types, $i--, 1);
945: $typesCount--;
946: continue 2;
947: }
948:
949: if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
950: array_splice($types, $j--, 1);
951: $typesCount--;
952: continue;
953: }
954:
955: if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
956: array_splice($types, $i--, 1);
957: $typesCount--;
958: continue 2;
959: }
960:
961: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof ArrayType && !$types[$j] instanceof ConstantArrayType) {
962: $newArray = ConstantArrayTypeBuilder::createEmpty();
963: $valueTypes = $types[$i]->getValueTypes();
964: foreach ($types[$i]->getKeyTypes() as $k => $keyType) {
965: $newArray->setOffsetValueType(
966: self::intersect($keyType, $types[$j]->getIterableKeyType()),
967: self::intersect($valueTypes[$k], $types[$j]->getIterableValueType()),
968: $types[$i]->isOptionalKey($k),
969: );
970: }
971: $types[$i] = $newArray->getArray();
972: array_splice($types, $j--, 1);
973: $typesCount--;
974: continue 2;
975: }
976:
977: if (
978: ($types[$i] instanceof ArrayType || $types[$i] instanceof IterableType) &&
979: ($types[$j] instanceof ArrayType || $types[$j] instanceof IterableType)
980: ) {
981: $keyType = self::intersect($types[$i]->getKeyType(), $types[$j]->getKeyType());
982: $itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
983: if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
984: $types[$j] = new IterableType($keyType, $itemType);
985: } else {
986: $types[$j] = new ArrayType($keyType, $itemType);
987: }
988: array_splice($types, $i--, 1);
989: $typesCount--;
990: continue 2;
991: }
992:
993: if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
994: $genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
995: $types[$i] = new GenericClassStringType($genericType);
996: array_splice($types, $j--, 1);
997: $typesCount--;
998: continue;
999: }
1000:
1001: continue;
1002: }
1003:
1004: if ($isSuperTypeB->yes()) {
1005: array_splice($types, $i--, 1);
1006: $typesCount--;
1007: continue 2;
1008: }
1009:
1010: if ($isSuperTypeA->no()) {
1011: return new NeverType();
1012: }
1013: }
1014: }
1015:
1016: if ($typesCount === 1) {
1017: return $types[0];
1018: }
1019:
1020: return new IntersectionType($types);
1021: }
1022:
1023: }
1024: