File src/Type/TypeCombinator.php

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:	*/
42:	final class TypeCombinator
43:	{
44:
45:	public static function addNull(Type $type): Type
46:	{
47:	$nullType = new NullType();
48:
49:	if ($nullType->isSuperTypeOf($type)->no()) {
50:	return self::union($type, $nullType);
51:	}
52:
53:	return $type;
54:	}
55:
56:	public static function remove(Type $fromType, Type $typeToRemove): Type
57:	{
58:	if ($typeToRemove instanceof UnionType) {
59:	foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
60:	$fromType = self::remove($fromType, $unionTypeToRemove);
61:	}
62:	return $fromType;
63:	}
64:
65:	$isSuperType = $typeToRemove->isSuperTypeOf($fromType);
66:	if ($isSuperType->yes()) {
67:	return new NeverType();
68:	}
69:	if ($isSuperType->no()) {
70:	return $fromType;
71:	}
72:
73:	if ($typeToRemove instanceof MixedType) {
74:	$typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
75:	if ($typeToRemoveSubtractedType !== null) {
76:	return self::intersect($fromType, $typeToRemoveSubtractedType);
77:	}
78:	}
79:
80:	$removed = $fromType->tryRemove($typeToRemove);
81:	if ($removed !== null) {
82:	return $removed;
83:	}
84:
85:	$fromFiniteTypes = $fromType->getFiniteTypes();
86:	if (count($fromFiniteTypes) > 0) {
87:	$finiteTypesToRemove = $typeToRemove->getFiniteTypes();
88:	if (count($finiteTypesToRemove) === 1) {
89:	$result = [];
90:	foreach ($fromFiniteTypes as $finiteType) {
91:	if ($finiteType->equals($finiteTypesToRemove[0])) {
92:	continue;
93:	}
94:
95:	$result[] = $finiteType;
96:	}
97:
98:	if (count($result) === count($fromFiniteTypes)) {
99:	return $fromType;
100:	}
101:
102:	if (count($result) === 0) {
103:	return new NeverType();
104:	}
105:
106:	if (count($result) === 1) {
107:	return $result[0];
108:	}
109:
110:	return new UnionType($result);
111:	}
112:	}
113:
114:	return $fromType;
115:	}
116:
117:	public static function removeNull(Type $type): Type
118:	{
119:	if (self::containsNull($type)) {
120:	return self::remove($type, new NullType());
121:	}
122:
123:	return $type;
124:	}
125:
126:	public static function containsNull(Type $type): bool
127:	{
128:	if ($type instanceof UnionType) {
129:	foreach ($type->getTypes() as $innerType) {
130:	if ($innerType instanceof NullType) {
131:	return true;
132:	}
133:	}
134:
135:	return false;
136:	}
137:
138:	return $type instanceof NullType;
139:	}
140:
141:	public static function union(Type ...$types): Type
142:	{
143:	$typesCount = count($types);
144:	if ($typesCount === 0) {
145:	return new NeverType();
146:	}
147:
148:	$benevolentTypes = [];
149:	$benevolentUnionObject = null;
150:	// transform A \| (B \| C) to A \| B \| C
151:	for ($i = 0; $i < $typesCount; $i++) {
152:	if ($types[$i] instanceof BenevolentUnionType) {
153:	if ($types[$i] instanceof TemplateBenevolentUnionType && $benevolentUnionObject === null) {
154:	$benevolentUnionObject = $types[$i];
155:	}
156:	$benevolentTypesCount = 0;
157:	$typesInner = $types[$i]->getTypes();
158:	foreach ($typesInner as $benevolentInnerType) {
159:	$benevolentTypesCount++;
160:	$benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
161:	}
162:	array_splice($types, $i, 1, $typesInner);
163:	$typesCount += $benevolentTypesCount - 1;
164:	continue;
165:	}
166:	if (!($types[$i] instanceof UnionType)) {
167:	continue;
168:	}
169:	if ($types[$i] instanceof TemplateType) {
170:	continue;
171:	}
172:
173:	$typesInner = $types[$i]->getTypes();
174:	array_splice($types, $i, 1, $typesInner);
175:	$typesCount += count($typesInner) - 1;
176:	}
177:
178:	if ($typesCount === 1) {
179:	return $types[0];
180:	}
181:
182:	$arrayTypes = [];
183:	$scalarTypes = [];
184:	$hasGenericScalarTypes = [];
185:	$enumCaseTypes = [];
186:	for ($i = 0; $i < $typesCount; $i++) {
187:	if ($types[$i] instanceof ConstantScalarType) {
188:	$type = $types[$i];
189:	$scalarTypes[get_class($type)][md5($type->describe(VerbosityLevel::cache()))] = $type;
190:	unset($types[$i]);
191:	continue;
192:	}
193:	if ($types[$i] instanceof BooleanType) {
194:	$hasGenericScalarTypes[ConstantBooleanType::class] = true;
195:	}
196:	if ($types[$i] instanceof FloatType) {
197:	$hasGenericScalarTypes[ConstantFloatType::class] = true;
198:	}
199:	if ($types[$i] instanceof IntegerType && !$types[$i] instanceof IntegerRangeType) {
200:	$hasGenericScalarTypes[ConstantIntegerType::class] = true;
201:	}
202:	if ($types[$i] instanceof StringType && !$types[$i] instanceof ClassStringType) {
203:	$hasGenericScalarTypes[ConstantStringType::class] = true;
204:	}
205:	$enumCases = $types[$i]->getEnumCases();
206:	if (count($enumCases) === 1) {
207:	$enumCaseTypes[$types[$i]->describe(VerbosityLevel::cache())] = $types[$i];
208:
209:	unset($types[$i]);
210:	continue;
211:	}
212:
213:	if (!$types[$i]->isArray()->yes()) {
214:	continue;
215:	}
216:
217:	$arrayTypes[] = $types[$i];
218:	unset($types[$i]);
219:	}
220:
221:	foreach ($scalarTypes as $classType => $scalarTypeItems) {
222:	$scalarTypes[$classType] = array_values($scalarTypeItems);
223:	}
224:
225:	$enumCaseTypes = array_values($enumCaseTypes);
226:	$types = array_values($types);
227:	$typesCount = count($types);
228:
229:	foreach ($scalarTypes as $classType => $scalarTypeItems) {
230:	if (isset($hasGenericScalarTypes[$classType])) {
231:	unset($scalarTypes[$classType]);
232:	continue;
233:	}
234:	if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
235:	$types[] = new BooleanType();
236:	$typesCount++;
237:	unset($scalarTypes[$classType]);
238:	continue;
239:	}
240:
241:	$scalarTypeItemsCount = count($scalarTypeItems);
242:	for ($i = 0; $i < $typesCount; $i++) {
243:	for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
244:	$compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
245:	if ($compareResult === null) {
246:	continue;
247:	}
248:
249:	[$a, $b] = $compareResult;
250:	if ($a !== null) {
251:	$types[$i] = $a;
252:	array_splice($scalarTypeItems, $j--, 1);
253:	$scalarTypeItemsCount--;
254:	continue 1;
255:	}
256:	if ($b !== null) {
257:	$scalarTypeItems[$j] = $b;
258:	array_splice($types, $i--, 1);
259:	$typesCount--;
260:	continue 2;
261:	}
262:	}
263:	}
264:
265:	$scalarTypes[$classType] = $scalarTypeItems;
266:	}
267:
268:	if (count($types) > 16) {
269:	$newTypes = [];
270:	foreach ($types as $type) {
271:	$newTypes[$type->describe(VerbosityLevel::cache())] = $type;
272:	}
273:	$types = array_values($newTypes);
274:	}
275:
276:	$types = array_merge(
277:	$types,
278:	self::processArrayTypes($arrayTypes),
279:	);
280:	$typesCount = count($types);
281:
282:	// transform A \| A to A
283:	// transform A \| never to A
284:	for ($i = 0; $i < $typesCount; $i++) {
285:	for ($j = $i + 1; $j < $typesCount; $j++) {
286:	$compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
287:	if ($compareResult === null) {
288:	continue;
289:	}
290:
291:	[$a, $b] = $compareResult;
292:	if ($a !== null) {
293:	$types[$i] = $a;
294:	array_splice($types, $j--, 1);
295:	$typesCount--;
296:	continue 1;
297:	}
298:	if ($b !== null) {
299:	$types[$j] = $b;
300:	array_splice($types, $i--, 1);
301:	$typesCount--;
302:	continue 2;
303:	}
304:	}
305:	}
306:
307:	$enumCasesCount = count($enumCaseTypes);
308:	for ($i = 0; $i < $typesCount; $i++) {
309:	for ($j = 0; $j < $enumCasesCount; $j++) {
310:	$compareResult = self::compareTypesInUnion($types[$i], $enumCaseTypes[$j]);
311:	if ($compareResult === null) {
312:	continue;
313:	}
314:
315:	[$a, $b] = $compareResult;
316:	if ($a !== null) {
317:	$types[$i] = $a;
318:	array_splice($enumCaseTypes, $j--, 1);
319:	$enumCasesCount--;
320:	continue 1;
321:	}
322:	if ($b !== null) {
323:	$enumCaseTypes[$j] = $b;
324:	array_splice($types, $i--, 1);
325:	$typesCount--;
326:	continue 2;
327:	}
328:	}
329:	}
330:
331:	foreach ($enumCaseTypes as $enumCaseType) {
332:	$types[] = $enumCaseType;
333:	$typesCount++;
334:	}
335:
336:	foreach ($scalarTypes as $scalarTypeItems) {
337:	foreach ($scalarTypeItems as $scalarType) {
338:	$types[] = $scalarType;
339:	$typesCount++;
340:	}
341:	}
342:
343:	if ($typesCount === 0) {
344:	return new NeverType();
345:	}
346:	if ($typesCount === 1) {
347:	return $types[0];
348:	}
349:
350:	if ($benevolentTypes !== []) {
351:	$tempTypes = $types;
352:	foreach ($tempTypes as $i => $type) {
353:	if (!isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
354:	break;
355:	}
356:
357:	unset($tempTypes[$i]);
358:	}
359:
360:	if ($tempTypes === []) {
361:	if ($benevolentUnionObject instanceof TemplateBenevolentUnionType) {
362:	return $benevolentUnionObject->withTypes($types);
363:	}
364:
365:	return new BenevolentUnionType($types, true);
366:	}
367:	}
368:
369:	return new UnionType($types, true);
370:	}
371:
372:	/**
373:	* @return array{Type, null}\|array{null, Type}\|null
374:	*/
375:	private static function compareTypesInUnion(Type $a, Type $b): ?array
376:	{
377:	if ($a instanceof IntegerRangeType) {
378:	$type = $a->tryUnion($b);
379:	if ($type !== null) {
380:	$a = $type;
381:	return [$a, null];
382:	}
383:	}
384:	if ($b instanceof IntegerRangeType) {
385:	$type = $b->tryUnion($a);
386:	if ($type !== null) {
387:	$b = $type;
388:	return [null, $b];
389:	}
390:	}
391:	if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
392:	return null;
393:	}
394:	if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
395:	if ($a->getOffsetType()->equals($b->getOffsetType())) {
396:	return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
397:	}
398:	}
399:	if ($a->isConstantArray()->yes() && $b->isConstantArray()->yes()) {
400:	return null;
401:	}
402:
403:	// simplify string[] \| int[] to (string\|int)[]
404:	if ($a instanceof IterableType && $b instanceof IterableType) {
405:	return [
406:	new IterableType(
407:	self::union($a->getIterableKeyType(), $b->getIterableKeyType()),
408:	self::union($a->getIterableValueType(), $b->getIterableValueType()),
409:	),
410:	null,
411:	];
412:	}
413:
414:	if ($a instanceof SubtractableType) {
415:	$typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
416:	if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
417:	$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
418:	} else {
419:	$isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
420:	}
421:	if ($isSuperType->yes()) {
422:	$a = self::intersectWithSubtractedType($a, $b);
423:	return [$a, null];
424:	}
425:	}
426:
427:	if ($b instanceof SubtractableType) {
428:	$typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
429:	if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
430:	$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
431:	} else {
432:	$isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
433:	}
434:	if ($isSuperType->yes()) {
435:	$b = self::intersectWithSubtractedType($b, $a);
436:	return [null, $b];
437:	}
438:	}
439:
440:	if ($b->isSuperTypeOf($a)->yes()) {
441:	return [null, $b];
442:	}
443:
444:	if ($a->isSuperTypeOf($b)->yes()) {
445:	return [$a, null];
446:	}
447:
448:	if (
449:	$a instanceof ConstantStringType
450:	&& $a->getValue() === ''
451:	&& ($b->describe(VerbosityLevel::value()) === 'non-empty-string'
452:	\|\| $b->describe(VerbosityLevel::value()) === 'non-falsy-string')
453:	) {
454:	return [null, new StringType()];
455:	}
456:
457:	if (
458:	$b instanceof ConstantStringType
459:	&& $b->getValue() === ''
460:	&& ($a->describe(VerbosityLevel::value()) === 'non-empty-string'
461:	\|\| $a->describe(VerbosityLevel::value()) === 'non-falsy-string')
462:	) {
463:	return [new StringType(), null];
464:	}
465:
466:	if (
467:	$a instanceof ConstantStringType
468:	&& $a->getValue() === '0'
469:	&& $b->describe(VerbosityLevel::value()) === 'non-falsy-string'
470:	) {
471:	return [null, new IntersectionType([
472:	new StringType(),
473:	new AccessoryNonEmptyStringType(),
474:	])];
475:	}
476:
477:	if (
478:	$b instanceof ConstantStringType
479:	&& $b->getValue() === '0'
480:	&& $a->describe(VerbosityLevel::value()) === 'non-falsy-string'
481:	) {
482:	return [new IntersectionType([
483:	new StringType(),
484:	new AccessoryNonEmptyStringType(),
485:	]), null];
486:	}
487:
488:	return null;
489:	}
490:
491:	private static function unionWithSubtractedType(
492:	Type $type,
493:	?Type $subtractedType,
494:	): Type
495:	{
496:	if ($subtractedType === null) {
497:	return $type;
498:	}
499:
500:	if ($type instanceof SubtractableType) {
501:	$subtractedType = $type->getSubtractedType() === null
502:	? $subtractedType
503:	: self::union($type->getSubtractedType(), $subtractedType);
504:	if ($subtractedType instanceof NeverType) {
505:	$subtractedType = null;
506:	}
507:
508:	return $type->changeSubtractedType($subtractedType);
509:	}
510:
511:	if ($subtractedType->isSuperTypeOf($type)->yes()) {
512:	return new NeverType();
513:	}
514:
515:	return self::remove($type, $subtractedType);
516:	}
517:
518:	private static function intersectWithSubtractedType(
519:	SubtractableType $a,
520:	Type $b,
521:	): Type
522:	{
523:	if ($a->getSubtractedType() === null) {
524:	return $a;
525:	}
526:
527:	if ($b instanceof IntersectionType) {
528:	$subtractableTypes = [];
529:	foreach ($b->getTypes() as $innerType) {
530:	if (!$innerType instanceof SubtractableType) {
531:	continue;
532:	}
533:
534:	$subtractableTypes[] = $innerType;
535:	}
536:
537:	if (count($subtractableTypes) === 0) {
538:	return $a->getTypeWithoutSubtractedType();
539:	}
540:
541:	$subtractedTypes = [];
542:	foreach ($subtractableTypes as $subtractableType) {
543:	if ($subtractableType->getSubtractedType() === null) {
544:	continue;
545:	}
546:
547:	$subtractedTypes[] = $subtractableType->getSubtractedType();
548:	}
549:
550:	if (count($subtractedTypes) === 0) {
551:	return $a->getTypeWithoutSubtractedType();
552:
553:	}
554:
555:	$subtractedType = self::union(...$subtractedTypes);
556:	} elseif ($b instanceof SubtractableType) {
557:	$subtractedType = $b->getSubtractedType();
558:	if ($subtractedType === null) {
559:	return $a->getTypeWithoutSubtractedType();
560:	}
561:	} else {
562:	$subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
563:	if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
564:	return $a->getTypeWithoutSubtractedType();
565:	}
566:	$subtractedType = new MixedType(false, $b);
567:	}
568:
569:	$subtractedType = self::intersect(
570:	$a->getSubtractedType(),
571:	$subtractedType,
572:	);
573:	if ($subtractedType instanceof NeverType) {
574:	$subtractedType = null;
575:	}
576:
577:	return $a->changeSubtractedType($subtractedType);
578:	}
579:
580:	/**
581:	* @param Type[] $arrayTypes
582:	* @return Type[]
583:	*/
584:	private static function processArrayAccessoryTypes(array $arrayTypes): array
585:	{
586:	$accessoryTypes = [];
587:	foreach ($arrayTypes as $i => $arrayType) {
588:	if ($arrayType instanceof IntersectionType) {
589:	foreach ($arrayType->getTypes() as $innerType) {
590:	if ($innerType instanceof TemplateType) {
591:	break;
592:	}
593:	if (!($innerType instanceof AccessoryType) && !($innerType instanceof CallableType)) {
594:	continue;
595:	}
596:	if ($innerType instanceof HasOffsetType) {
597:	$offset = $innerType->getOffsetType();
598:	if ($offset instanceof ConstantStringType \|\| $offset instanceof ConstantIntegerType) {
599:	$innerType = new HasOffsetValueType($offset, $arrayType->getIterableValueType());
600:	}
601:	}
602:	if ($innerType instanceof HasOffsetValueType) {
603:	$accessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][$i] = $innerType;
604:	continue;
605:	}
606:
607:	$accessoryTypes[$innerType->describe(VerbosityLevel::cache())][$i] = $innerType;
608:	}
609:	}
610:
611:	if (!$arrayType->isConstantArray()->yes()) {
612:	continue;
613:	}
614:	$constantArrays = $arrayType->getConstantArrays();
615:
616:	foreach ($constantArrays as $constantArray) {
617:	if ($constantArray->isList()->yes()) {
618:	$list = new AccessoryArrayListType();
619:	$accessoryTypes[$list->describe(VerbosityLevel::cache())][$i] = $list;
620:	}
621:
622:	if (!$constantArray->isIterableAtLeastOnce()->yes()) {
623:	continue;
624:	}
625:
626:	$nonEmpty = new NonEmptyArrayType();
627:	$accessoryTypes[$nonEmpty->describe(VerbosityLevel::cache())][$i] = $nonEmpty;
628:	}
629:	}
630:
631:	$commonAccessoryTypes = [];
632:	$arrayTypeCount = count($arrayTypes);
633:	foreach ($accessoryTypes as $accessoryType) {
634:	if (count($accessoryType) !== $arrayTypeCount) {
635:	$firstKey = array_key_first($accessoryType);
636:	if ($accessoryType[$firstKey] instanceof OversizedArrayType) {
637:	$commonAccessoryTypes[] = $accessoryType[$firstKey];
638:	}
639:	continue;
640:	}
641:
642:	if ($accessoryType[0] instanceof HasOffsetValueType) {
643:	$commonAccessoryTypes[] = self::union(...$accessoryType);
644:	continue;
645:	}
646:
647:	$commonAccessoryTypes[] = $accessoryType[0];
648:	}
649:
650:	return $commonAccessoryTypes;
651:	}
652:
653:	/**
654:	* @param list<Type> $arrayTypes
655:	* @return Type[]
656:	*/
657:	private static function processArrayTypes(array $arrayTypes): array
658:	{
659:	if ($arrayTypes === []) {
660:	return [];
661:	}
662:
663:	$accessoryTypes = self::processArrayAccessoryTypes($arrayTypes);
664:
665:	if (count($arrayTypes) === 1) {
666:	return [
667:	self::intersect(...$arrayTypes, ...$accessoryTypes),
668:	];
669:	}
670:
671:	$keyTypesForGeneralArray = [];
672:	$valueTypesForGeneralArray = [];
673:	$generalArrayOccurred = false;
674:	$constantKeyTypesNumbered = [];
675:	$filledArrays = 0;
676:	$overflowed = false;
677:
678:	/** @var int\|float $nextConstantKeyTypeIndex */
679:	$nextConstantKeyTypeIndex = 1;
680:	$constantArraysMap = array_map(
681:	static fn (Type $t) => $t->getConstantArrays(),
682:	$arrayTypes,
683:	);
684:
685:	foreach ($arrayTypes as $arrayIdx => $arrayType) {
686:	$constantArrays = $constantArraysMap[$arrayIdx];
687:	$isConstantArray = $constantArrays !== [];
688:	if (!$isConstantArray \|\| !$arrayType->isIterableAtLeastOnce()->no()) {
689:	$filledArrays++;
690:	}
691:
692:	if ($generalArrayOccurred \|\| !$isConstantArray) {
693:	foreach ($arrayType->getArrays() as $type) {
694:	$keyTypesForGeneralArray[] = $type->getIterableKeyType();
695:	$valueTypesForGeneralArray[] = $type->getItemType();
696:	$generalArrayOccurred = true;
697:	}
698:	continue;
699:	}
700:
701:	$constantArrays = $arrayType->getConstantArrays();
702:	foreach ($constantArrays as $constantArray) {
703:	foreach ($constantArray->getKeyTypes() as $i => $keyType) {
704:	$keyTypesForGeneralArray[] = $keyType;
705:	$valueTypesForGeneralArray[] = $constantArray->getValueTypes()[$i];
706:
707:	$keyTypeValue = $keyType->getValue();
708:	if (array_key_exists($keyTypeValue, $constantKeyTypesNumbered)) {
709:	continue;
710:	}
711:
712:	$constantKeyTypesNumbered[$keyTypeValue] = $nextConstantKeyTypeIndex;
713:	$nextConstantKeyTypeIndex *= 2;
714:	if (!is_int($nextConstantKeyTypeIndex)) {
715:	$generalArrayOccurred = true;
716:	$overflowed = true;
717:	continue 2;
718:	}
719:	}
720:	}
721:	}
722:
723:	if ($generalArrayOccurred && (!$overflowed \|\| $filledArrays > 1)) {
724:	$reducedArrayTypes = self::reduceArrays($arrayTypes, false);
725:	if (count($reducedArrayTypes) === 1) {
726:	return [self::intersect($reducedArrayTypes[0], ...$accessoryTypes)];
727:	}
728:	$scopes = [];
729:	$useTemplateArray = true;
730:	foreach ($arrayTypes as $arrayType) {
731:	if (!$arrayType instanceof TemplateArrayType) {
732:	$useTemplateArray = false;
733:	break;
734:	}
735:
736:	$scopes[$arrayType->getScope()->describe()] = $arrayType;
737:	}
738:
739:	$arrayType = new ArrayType(
740:	self::union(...$keyTypesForGeneralArray),
741:	self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
742:	);
743:
744:	if ($useTemplateArray && count($scopes) === 1) {
745:	$templateArray = array_values($scopes)[0];
746:	$arrayType = new TemplateArrayType(
747:	$templateArray->getScope(),
748:	$templateArray->getStrategy(),
749:	$templateArray->getVariance(),
750:	$templateArray->getName(),
751:	$arrayType,
752:	$templateArray->getDefault(),
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 \|\| $type instanceof ConstantArrayType) {
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 = TypeCombinator::intersect($arrayType, new AccessoryArrayListType());
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:	$type->getDefault(),
1019:	);
1020:	}
1021:
1022:	return $union;
1023:	}
1024:	$typesCount = count($types);
1025:
1026:	// transform A & (B & C) to A & B & C
1027:	for ($i = 0; $i < $typesCount; $i++) {
1028:	$type = $types[$i];
1029:
1030:	if (!($type instanceof IntersectionType)) {
1031:	continue;
1032:	}
1033:
1034:	array_splice($types, $i--, 1, $type->getTypes());
1035:	$typesCount = count($types);
1036:	}
1037:
1038:	$hasOffsetValueTypeCount = 0;
1039:	$newTypes = [];
1040:	foreach ($types as $type) {
1041:	if (!$type instanceof HasOffsetValueType) {
1042:	$newTypes[] = $type;
1043:	continue;
1044:	}
1045:
1046:	$hasOffsetValueTypeCount++;
1047:	}
1048:
1049:	if ($hasOffsetValueTypeCount > 32) {
1050:	$newTypes[] = new OversizedArrayType();
1051:	$types = $newTypes;
1052:	$typesCount = count($types);
1053:	}
1054:
1055:	usort($types, static function (Type $a, Type $b): int {
1056:	// move subtractables with subtracts before those without to avoid loosing them in the union logic
1057:	if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
1058:	return -1;
1059:	}
1060:	if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
1061:	return 1;
1062:	}
1063:
1064:	if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
1065:	return -1;
1066:	}
1067:	if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
1068:	return 1;
1069:	}
1070:
1071:	return 0;
1072:	});
1073:
1074:	// transform IntegerType & ConstantIntegerType to ConstantIntegerType
1075:	// transform Child & Parent to Child
1076:	// transform Object & ~null to Object
1077:	// transform A & A to A
1078:	// transform int[] & string to never
1079:	// transform callable & int to never
1080:	// transform A & ~A to never
1081:	// transform int & string to never
1082:	for ($i = 0; $i < $typesCount; $i++) {
1083:	for ($j = $i + 1; $j < $typesCount; $j++) {
1084:	if ($types[$j] instanceof SubtractableType) {
1085:	$typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
1086:
1087:	if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
1088:	$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
1089:	} else {
1090:	$isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
1091:	}
1092:	if ($isSuperTypeSubtractableA->yes()) {
1093:	$types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
1094:	array_splice($types, $j--, 1);
1095:	$typesCount--;
1096:	continue 1;
1097:	}
1098:	}
1099:
1100:	if ($types[$i] instanceof SubtractableType) {
1101:	$typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
1102:
1103:	if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
1104:	$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
1105:	} else {
1106:	$isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
1107:	}
1108:	if ($isSuperTypeSubtractableB->yes()) {
1109:	$types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
1110:	array_splice($types, $i--, 1);
1111:	$typesCount--;
1112:	continue 2;
1113:	}
1114:	}
1115:
1116:	if ($types[$i] instanceof IntegerRangeType) {
1117:	$intersectionType = $types[$i]->tryIntersect($types[$j]);
1118:	if ($intersectionType !== null) {
1119:	$types[$j] = $intersectionType;
1120:	array_splice($types, $i--, 1);
1121:	$typesCount--;
1122:	continue 2;
1123:	}
1124:	}
1125:
1126:	if ($types[$j] instanceof IterableType) {
1127:	$isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
1128:	} else {
1129:	$isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
1130:	}
1131:
1132:	if ($isSuperTypeA->yes()) {
1133:	array_splice($types, $j--, 1);
1134:	$typesCount--;
1135:	continue;
1136:	}
1137:
1138:	if ($types[$i] instanceof IterableType) {
1139:	$isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
1140:	} else {
1141:	$isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
1142:	}
1143:
1144:	if ($isSuperTypeB->maybe()) {
1145:	if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
1146:	$types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
1147:	array_splice($types, $j--, 1);
1148:	$typesCount--;
1149:	continue;
1150:	}
1151:
1152:	if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
1153:	$types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
1154:	array_splice($types, $i--, 1);
1155:	$typesCount--;
1156:	continue 2;
1157:	}
1158:
1159:	if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
1160:	$offsetType = $types[$j]->getOffsetType();
1161:	$valueType = $types[$j]->getValueType();
1162:	$newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
1163:	if ($newValueType instanceof NeverType) {
1164:	return $newValueType;
1165:	}
1166:	$types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
1167:	array_splice($types, $j--, 1);
1168:	$typesCount--;
1169:	continue;
1170:	}
1171:
1172:	if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
1173:	$offsetType = $types[$i]->getOffsetType();
1174:	$valueType = $types[$i]->getValueType();
1175:	$newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
1176:	if ($newValueType instanceof NeverType) {
1177:	return $newValueType;
1178:	}
1179:
1180:	$types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
1181:	array_splice($types, $i--, 1);
1182:	$typesCount--;
1183:	continue 2;
1184:	}
1185:
1186:	if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
1187:	array_splice($types, $j--, 1);
1188:	$typesCount--;
1189:	continue;
1190:	}
1191:
1192:	if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
1193:	array_splice($types, $i--, 1);
1194:	$typesCount--;
1195:	continue 2;
1196:	}
1197:
1198:	if ($types[$i] instanceof ObjectShapeType && $types[$j] instanceof HasPropertyType) {
1199:	$types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
1200:	array_splice($types, $j--, 1);
1201:	$typesCount--;
1202:	continue;
1203:	}
1204:
1205:	if ($types[$j] instanceof ObjectShapeType && $types[$i] instanceof HasPropertyType) {
1206:	$types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
1207:	array_splice($types, $i--, 1);
1208:	$typesCount--;
1209:	continue 2;
1210:	}
1211:
1212:	if ($types[$i] instanceof ConstantArrayType && ($types[$j] instanceof ArrayType \|\| $types[$j] instanceof ConstantArrayType)) {
1213:	$newArray = ConstantArrayTypeBuilder::createEmpty();
1214:	$valueTypes = $types[$i]->getValueTypes();
1215:	foreach ($types[$i]->getKeyTypes() as $k => $keyType) {
1216:	$newArray->setOffsetValueType(
1217:	self::intersect($keyType, $types[$j]->getIterableKeyType()),
1218:	self::intersect($valueTypes[$k], $types[$j]->getIterableValueType()),
1219:	$types[$i]->isOptionalKey($k) && !$types[$j]->hasOffsetValueType($keyType)->yes(),
1220:	);
1221:	}
1222:	$types[$i] = $newArray->getArray();
1223:	array_splice($types, $j--, 1);
1224:	$typesCount--;
1225:	continue 2;
1226:	}
1227:
1228:	if ($types[$j] instanceof ConstantArrayType && ($types[$i] instanceof ArrayType \|\| $types[$i] instanceof ConstantArrayType)) {
1229:	$newArray = ConstantArrayTypeBuilder::createEmpty();
1230:	$valueTypes = $types[$j]->getValueTypes();
1231:	foreach ($types[$j]->getKeyTypes() as $k => $keyType) {
1232:	$newArray->setOffsetValueType(
1233:	self::intersect($keyType, $types[$i]->getIterableKeyType()),
1234:	self::intersect($valueTypes[$k], $types[$i]->getIterableValueType()),
1235:	$types[$j]->isOptionalKey($k) && !$types[$i]->hasOffsetValueType($keyType)->yes(),
1236:	);
1237:	}
1238:	$types[$j] = $newArray->getArray();
1239:	array_splice($types, $i--, 1);
1240:	$typesCount--;
1241:	continue 2;
1242:	}
1243:
1244:	if (
1245:	($types[$i] instanceof ArrayType \|\| $types[$i] instanceof ConstantArrayType \|\| $types[$i] instanceof IterableType) &&
1246:	($types[$j] instanceof ArrayType \|\| $types[$j] instanceof ConstantArrayType \|\| $types[$j] instanceof IterableType)
1247:	) {
1248:	$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
1249:	$itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
1250:	if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
1251:	$types[$j] = new IterableType($keyType, $itemType);
1252:	} else {
1253:	$types[$j] = new ArrayType($keyType, $itemType);
1254:	}
1255:	array_splice($types, $i--, 1);
1256:	$typesCount--;
1257:	continue 2;
1258:	}
1259:
1260:	if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
1261:	$genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
1262:	$types[$i] = new GenericClassStringType($genericType);
1263:	array_splice($types, $j--, 1);
1264:	$typesCount--;
1265:	continue;
1266:	}
1267:
1268:	if (
1269:	$types[$i] instanceof ArrayType
1270:	&& get_class($types[$i]) === ArrayType::class
1271:	&& $types[$j] instanceof AccessoryArrayListType
1272:	&& !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
1273:	) {
1274:	$keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
1275:	if ($keyType instanceof NeverType) {
1276:	return $keyType;
1277:	}
1278:	$types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
1279:	continue;
1280:	}
1281:
1282:	continue;
1283:	}
1284:
1285:	if ($isSuperTypeB->yes()) {
1286:	array_splice($types, $i--, 1);
1287:	$typesCount--;
1288:	continue 2;
1289:	}
1290:
1291:	if ($isSuperTypeA->no()) {
1292:	return new NeverType();
1293:	}
1294:	}
1295:	}
1296:
1297:	if ($typesCount === 1) {
1298:	return $types[0];
1299:	}
1300:
1301:	return new IntersectionType($types);
1302:	}
1303:
1304:	public static function removeFalsey(Type $type): Type
1305:	{
1306:	return self::remove($type, StaticTypeFactory::falsey());
1307:	}
1308:
1309:	}
1310:

Namespaces

Classes

Interfaces