1: <?php declare(strict_types = 1);
2:
3: namespace PHPStan\Type;
4:
5: use PHPStan\TrinaryLogic;
6: use PHPStan\Turbo\ShadowedByTurboExtension;
7: use PHPStan\Turbo\TurboExtensionEnabler;
8: use PHPStan\Type\Accessory\AccessoryArrayListType;
9: use PHPStan\Type\Accessory\AccessoryDecimalIntegerStringType;
10: use PHPStan\Type\Accessory\AccessoryLowercaseStringType;
11: use PHPStan\Type\Accessory\AccessoryNonEmptyStringType;
12: use PHPStan\Type\Accessory\AccessoryNonFalsyStringType;
13: use PHPStan\Type\Accessory\AccessoryType;
14: use PHPStan\Type\Accessory\AccessoryUppercaseStringType;
15: use PHPStan\Type\Accessory\HasOffsetType;
16: use PHPStan\Type\Accessory\HasOffsetValueType;
17: use PHPStan\Type\Accessory\HasPropertyType;
18: use PHPStan\Type\Accessory\NonEmptyArrayType;
19: use PHPStan\Type\Accessory\OversizedArrayType;
20: use PHPStan\Type\Constant\ConstantArrayType;
21: use PHPStan\Type\Constant\ConstantArrayTypeBuilder;
22: use PHPStan\Type\Constant\ConstantBooleanType;
23: use PHPStan\Type\Constant\ConstantFloatType;
24: use PHPStan\Type\Constant\ConstantIntegerType;
25: use PHPStan\Type\Constant\ConstantStringType;
26: use PHPStan\Type\Generic\GenericClassStringType;
27: use PHPStan\Type\Generic\TemplateArrayType;
28: use PHPStan\Type\Generic\TemplateBenevolentUnionType;
29: use PHPStan\Type\Generic\TemplateMixedType;
30: use PHPStan\Type\Generic\TemplateType;
31: use PHPStan\Type\Generic\TemplateTypeFactory;
32: use PHPStan\Type\Generic\TemplateUnionType;
33: use PHPStan\Type\Generic\UnresolvedTemplateArgumentType;
34: use function array_fill;
35: use function array_filter;
36: use function array_flip;
37: use function array_intersect_key;
38: use function array_key_exists;
39: use function array_key_first;
40: use function array_keys;
41: use function array_merge;
42: use function array_search;
43: use function array_slice;
44: use function array_splice;
45: use function array_values;
46: use function count;
47: use function get_class;
48: use function implode;
49: use function in_array;
50: use function ksort;
51: use function serialize;
52: use function sort;
53: use function spl_object_id;
54: use function sprintf;
55: use function usort;
56: use const PHP_INT_MAX;
57: use const PHP_INT_MIN;
58:
59: /**
60: * @api
61: */
62: #[ShadowedByTurboExtension(implementation: __DIR__ . '/../../turbo-ext/src/TypeCombinator.cpp')]
63: final class TypeCombinator
64: {
65:
66: /**
67: * Up to this many members of the one union doUnion() flattens, finding out whether two of
68: * them were already compared by scanning it costs less than indexing it.
69: */
70: private const ALREADY_NORMALIZED_SCAN_LIMIT = 4;
71:
72: /**
73: * Turned on by TurboExtensionEnabler when the native extension is active, so that
74: * union(), intersect() and remove() route through the memoizing TypeCombinatorCache.
75: * Without the extension the operations run exactly as they always have — the flag
76: * costs a property read, and nothing else changes.
77: */
78: private static ?bool $cacheEnabled = null;
79:
80: /**
81: * Memoization hands back shared Type instances, and a Type lazily resolves a
82: * ClassReflection belonging to the container that created it — so the cache must
83: * not outlive its container.
84: */
85: public static function clearCache(): void
86: {
87: if ((self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) === false) {
88: return;
89: }
90:
91: TypeCombinatorCache::clearCache();
92: }
93:
94: public static function addNull(Type $type): Type
95: {
96: // asking the type itself is both cheaper than NullType::isSuperTypeOf()
97: // (UnionType memoizes isNull(), isSubTypeOf() recomputes) and right for
98: // `never`, of which null is a supertype without never containing it.
99: if ($type->isNull()->no()) {
100: return self::union($type, new NullType());
101: }
102:
103: return $type;
104: }
105:
106: public static function remove(Type $fromType, Type $typeToRemove): Type
107: {
108: if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
109: return TypeCombinatorCache::remove($fromType, $typeToRemove);
110: }
111:
112: return self::doRemove($fromType, $typeToRemove);
113: }
114:
115: /**
116: * Whether removing the union's members all at once gives what removing them
117: * one at a time would: true when the subtraction is a set difference, so no
118: * order of removals can sharpen the result.
119: *
120: * Everywhere else the members have to come off one at a time - removing one
121: * can narrow the type so that removing the next achieves more.
122: */
123: private static function canRemoveUnionAtOnce(Type $fromType): bool
124: {
125: // A sealed hierarchy - an enum, or a hierarchy an
126: // AllowedSubTypesClassReflectionExtension seals - subtracts by dropping
127: // allowed subtypes, and which ones are dropped does not depend on order.
128: $classReflections = $fromType->getObjectClassReflections();
129: if (count($classReflections) === 1 && $classReflections[0]->getAllowedSubTypes() !== null) {
130: return true;
131: }
132:
133: // A union removes the whole thing from each of its members, and each of
134: // those removals weighs this same question again - so a member that needs
135: // the removals one at a time still gets them that way.
136: return $fromType instanceof UnionType;
137: }
138:
139: /** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
140: public static function doRemove(Type $fromType, Type $typeToRemove): Type
141: {
142: if ($typeToRemove instanceof UnionType) {
143: // Removing the members one at a time is what keeps the result precise:
144: // removing one can narrow the type so that removing the next achieves
145: // more. A sealed hierarchy is the exception - there the subtraction is
146: // a set difference over the allowed subtypes, so the order the members
147: // come off cannot matter, and peeling them would rebuild the whole
148: // subtraction once per member (removing an enum from its own type then
149: // costs O(cases^2)).
150: if (self::canRemoveUnionAtOnce($fromType)) {
151: $removed = $fromType->tryRemove($typeToRemove);
152: if ($removed !== null) {
153: return $removed;
154: }
155:
156: // a union removed the whole union from each of its members and none
157: // of them changed - removing the members of it one at a time cannot
158: // change one either, peeling would only repeat that work
159: if ($fromType instanceof UnionType) {
160: return $fromType;
161: }
162: }
163:
164: // mixed is the top type, so removing a union from it is exactly
165: // subtracting the members it does not subtract already, all of them at
166: // once. Peeling them one at a time would ask each member about the mixed
167: // the earlier members left, which walks everything they subtracted.
168: if ($fromType instanceof MixedType && !$fromType instanceof TemplateType) {
169: $subtractedType = $fromType->getSubtractedType();
170: $remainingTypes = [];
171: foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
172: if ($subtractedType !== null && $subtractedType->isSuperTypeOf($unionTypeToRemove)->yes()) {
173: continue;
174: }
175: $remainingTypes[] = $unionTypeToRemove;
176: }
177:
178: if ($remainingTypes === []) {
179: return $fromType;
180: }
181:
182: return $fromType->subtract(count($remainingTypes) === 1 ? $remainingTypes[0] : new UnionType($remainingTypes));
183: }
184:
185: // a value none of the union's keyed members stands for overlaps none
186: // of them - one lookup instead of a removal per member
187: $fromTypeKey = FiniteTypeSet::key($fromType);
188: if ($fromTypeKey !== null) {
189: $finiteTypeSet = $typeToRemove->getFiniteTypeSet();
190: if ($finiteTypeSet !== null && $finiteTypeSet->isComplete() && !$finiteTypeSet->has($fromTypeKey)) {
191: return $fromType;
192: }
193: }
194:
195: foreach ($typeToRemove->getTypes() as $unionTypeToRemove) {
196: $fromType = self::remove($fromType, $unionTypeToRemove);
197: if ($fromType instanceof NeverType) {
198: // there is nothing left to remove from
199: break;
200: }
201: }
202: return $fromType;
203: }
204:
205: $isSuperType = $typeToRemove->isSuperTypeOf($fromType);
206: if ($isSuperType->yes()) {
207: return new NeverType();
208: }
209: if ($isSuperType->no()) {
210: return $fromType;
211: }
212:
213: if ($typeToRemove instanceof MixedType) {
214: $typeToRemoveSubtractedType = $typeToRemove->getSubtractedType();
215: if ($typeToRemoveSubtractedType !== null) {
216: return self::intersect($fromType, $typeToRemoveSubtractedType);
217: }
218: }
219:
220: $removed = $fromType->tryRemove($typeToRemove);
221: if ($removed !== null) {
222: return $removed;
223: }
224:
225: $fromFiniteTypes = $fromType->getFiniteTypes();
226: if (count($fromFiniteTypes) > 0) {
227: $finiteTypesToRemove = $typeToRemove->getFiniteTypes();
228: if (count($finiteTypesToRemove) > 0) {
229: $result = [];
230: foreach ($fromFiniteTypes as $finiteType) {
231: foreach ($finiteTypesToRemove as $finiteTypeToRemove) {
232: if ($finiteType->equals($finiteTypeToRemove)) {
233: continue 2;
234: }
235: }
236:
237: $result[] = $finiteType;
238: }
239:
240: if (count($result) === count($fromFiniteTypes)) {
241: return $fromType;
242: }
243:
244: if (count($result) === 0) {
245: return new NeverType();
246: }
247:
248: if (count($result) === 1) {
249: return $result[0];
250: }
251:
252: return new UnionType($result);
253: }
254: }
255:
256: return $fromType;
257: }
258:
259: public static function removeNull(Type $type): Type
260: {
261: if (self::containsNull($type)) {
262: return self::remove($type, new NullType());
263: }
264:
265: return $type;
266: }
267:
268: public static function containsNull(Type $type): bool
269: {
270: if ($type instanceof UnionType) {
271: foreach ($type->getTypes() as $innerType) {
272: if ($innerType->isNull()->yes()) {
273: return true;
274: }
275: }
276:
277: return false;
278: }
279:
280: return $type instanceof NullType;
281: }
282:
283: public static function union(Type ...$types): Type
284: {
285: if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
286: return TypeCombinatorCache::union(...$types);
287: }
288:
289: return self::doUnion(...$types);
290: }
291:
292: /** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
293: public static function doUnion(Type ...$types): Type
294: {
295: $typesCount = count($types);
296: if ($typesCount === 0) {
297: return new NeverType();
298: }
299:
300: // Fast path for single non-union type
301: if ($typesCount === 1) {
302: $singleType = $types[0];
303: if (!$singleType instanceof UnionType && !$singleType->isArray()->yes()) {
304: return $singleType;
305: }
306: }
307:
308: // Fast path for common 2-type cases
309: if ($typesCount === 2) {
310: $a = $types[0];
311: $b = $types[1];
312:
313: // union(never, X) = X and union(X, never) = X
314: if ($a instanceof NeverType && !$a->isExplicit()) {
315: return $b;
316: }
317: if ($b instanceof NeverType && !$b->isExplicit()) {
318: return $a;
319: }
320:
321: // union(mixed, X) = mixed (non-explicit, non-template, no subtracted)
322: if ($a instanceof MixedType && !$a->isExplicitMixed() && !$a instanceof TemplateMixedType && $a->getSubtractedType() === null) {
323: return $a;
324: }
325: if ($b instanceof MixedType && !$b->isExplicitMixed() && !$b instanceof TemplateMixedType && $b->getSubtractedType() === null) {
326: return $b;
327: }
328:
329: // union(X, X) = X — for equal array operands, not just identical
330: // ones. For arrays the general path below is not a no-op on a pair
331: // that already denotes a single type: it rebuilds them from
332: // ArrayType::getIterableKeyType(), which coerces a subtracted key
333: // type down to the plain array-key union, so `array<mixed~'User',
334: // mixed>` unioned with an equal instance came back as plain
335: // `array`. Whether the two operands happen to be the same object
336: // must not decide the result.
337: //
338: // Non-array operands keep taking the general path. It is lossless
339: // for them, and it has to stay in charge because `equals()` is
340: // weaker than interchangeability for some types: a benevolent
341: // `(int|string)` equals a plain `int|string` and `Foo=final` equals
342: // `Foo`, and there the general path deliberately yields the wider
343: // operand rather than whichever one was passed first.
344: if ($a === $b || ($a->equals($b) && $a->isArray()->yes())) {
345: return $a;
346: }
347: }
348:
349: // A member passed more than once contributes nothing; dropping the
350: // repeats up front keeps the pairwise comparison below from paying for
351: // them (array_values() of a shape unions the same value type per slot).
352: if ($typesCount > 2) {
353: $seenTypes = [];
354: $uniqueTypes = [];
355: foreach ($types as $type) {
356: $typeId = spl_object_id($type);
357: if (isset($seenTypes[$typeId])) {
358: continue;
359: }
360: $seenTypes[$typeId] = true;
361: $uniqueTypes[] = $type;
362: }
363: if (count($uniqueTypes) === 1) {
364: return $uniqueTypes[0];
365: }
366: if (count($uniqueTypes) === 2) {
367: return self::union($uniqueTypes[0], $uniqueTypes[1]);
368: }
369: $types = $uniqueTypes;
370: }
371:
372: $alreadyNormalized = [];
373: $alreadyNormalizedCounter = 0;
374:
375: $benevolentTypes = [];
376: $neverCount = 0;
377: $markers = [];
378: // transform A | (B | C) to A | B | C - in one pass, a union's members are
379: // never unions, implicit never or implicit mixed themselves
380: $flattenedTypes = [];
381: foreach ($types as $type) {
382: if (
383: $type instanceof MixedType
384: && !$type->isExplicitMixed()
385: && !$type instanceof TemplateMixedType
386: && $type->getSubtractedType() === null
387: ) {
388: return $type;
389: }
390: if ($type instanceof UnresolvedTemplateArgumentType && !$type->isClosureSignature()) {
391: $markers = self::addMarker($markers, $type);
392: continue;
393: }
394: if ($type instanceof NeverType && !$type->isExplicit()) {
395: $neverCount++;
396: $flattenedTypes[] = $type;
397: continue;
398: }
399: if ($type instanceof BenevolentUnionType) {
400: if ($type instanceof TemplateType) {
401: $flattenedTypes[] = $type;
402: continue;
403: }
404: foreach ($type->getTypes() as $benevolentInnerType) {
405: $benevolentTypes[$benevolentInnerType->describe(VerbosityLevel::value())] = $benevolentInnerType;
406: $flattenedTypes[] = $benevolentInnerType;
407: }
408: continue;
409: }
410: if (!($type instanceof UnionType) || $type instanceof TemplateType) {
411: $flattenedTypes[] = $type;
412: continue;
413: }
414:
415: $typesInner = $type->getTypes();
416: $alreadyNormalized[$alreadyNormalizedCounter] = $typesInner;
417: $alreadyNormalizedCounter++;
418: foreach ($typesInner as $innerType) {
419: if ($innerType instanceof UnresolvedTemplateArgumentType && !$innerType->isClosureSignature()) {
420: $markers = self::addMarker($markers, $innerType);
421: continue;
422: }
423: $flattenedTypes[] = $innerType;
424: }
425: }
426: if ($markers !== []) {
427: return self::unionWithMarkers(self::union(...$flattenedTypes), $markers);
428: }
429: $types = $flattenedTypes;
430: $typesCount = count($types);
431:
432: // Bulk-remove implicit NeverTypes (skipped during the loop above)
433: if ($neverCount > 0) {
434: if ($neverCount === $typesCount) {
435: return new NeverType();
436: }
437:
438: $filtered = [];
439: for ($i = 0; $i < $typesCount; $i++) {
440: if ($types[$i] instanceof NeverType && !$types[$i]->isExplicit()) {
441: continue;
442: }
443: $filtered[] = $types[$i];
444: }
445: $types = $filtered;
446: $typesCount = count($types);
447:
448: if ($typesCount === 0) {
449: return new NeverType();
450: }
451: if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
452: return $types[0];
453: }
454: if ($typesCount === 2) {
455: return self::union($types[0], $types[1]);
456: }
457: }
458:
459: if ($typesCount === 0) {
460: return new NeverType();
461: }
462:
463: if ($typesCount === 1 && !$types[0]->isArray()->yes()) {
464: return $types[0];
465: }
466:
467: $arrayTypes = [];
468: $scalarTypes = [];
469: $hasGenericScalarTypes = [];
470: $enumCaseTypes = [];
471: $integerRangeTypes = [];
472: $floatRangeTypes = [];
473: for ($i = 0; $i < $typesCount; $i++) {
474: if ($types[$i]->isConstantScalarValue()->yes()) {
475: $type = $types[$i];
476: $scalarTypes[get_class($type)][$type->describe(VerbosityLevel::cache())] = $type;
477: unset($types[$i]);
478: continue;
479: }
480:
481: // only a type containing every value of the scalar (not T of int, 1&T)
482: // absorbs all the constants of that scalar
483: if ($types[$i]->isBoolean()->yes()) {
484: if (!isset($hasGenericScalarTypes[ConstantBooleanType::class]) && $types[$i]->isSuperTypeOf(new BooleanType())->yes()) {
485: $hasGenericScalarTypes[ConstantBooleanType::class] = true;
486: }
487: } elseif ($types[$i]->isFloat()->yes()) {
488: if (!isset($hasGenericScalarTypes[ConstantFloatType::class]) && $types[$i]->isSuperTypeOf(new FloatType())->yes()) {
489: $hasGenericScalarTypes[ConstantFloatType::class] = true;
490: }
491: } elseif ($types[$i]->isInteger()->yes() && !$types[$i] instanceof IntegerRangeType) {
492: if (!isset($hasGenericScalarTypes[ConstantIntegerType::class]) && $types[$i]->isSuperTypeOf(new IntegerType())->yes()) {
493: $hasGenericScalarTypes[ConstantIntegerType::class] = true;
494: }
495: } elseif ($types[$i]->isString()->yes() && $types[$i]->isClassString()->no() && TypeUtils::getAccessoryTypes($types[$i]) === []) {
496: $hasGenericScalarTypes[ConstantStringType::class] = true;
497: } else {
498: $enumCase = $types[$i]->getEnumCaseObject();
499: if ($enumCase !== null) {
500: $enumCaseTypes[$types[$i]->describe(VerbosityLevel::cache())] = $types[$i];
501:
502: unset($types[$i]);
503: continue;
504: }
505: }
506:
507: if ($types[$i] instanceof IntegerRangeType) {
508: $integerRangeTypes[] = $types[$i];
509: unset($types[$i]);
510:
511: continue;
512: }
513:
514: if ($types[$i] instanceof FloatRangeType) {
515: $floatRangeTypes[] = $types[$i];
516: unset($types[$i]);
517:
518: continue;
519: }
520:
521: // a late-resolvable type, such as a conditional type, stays as it is until it resolves:
522: // merged with the other arrays, it would lose its condition and its accessory types
523: if (!$types[$i]->isArray()->yes() || $types[$i] instanceof LateResolvableType) {
524: continue;
525: }
526:
527: $arrayTypes[] = $types[$i];
528: unset($types[$i]);
529: }
530:
531: $enumCaseTypes = array_values($enumCaseTypes);
532: usort(
533: $integerRangeTypes,
534: static fn (IntegerRangeType $a, IntegerRangeType $b): int => ($a->getMin() ?? PHP_INT_MIN) <=> ($b->getMin() ?? PHP_INT_MIN)
535: ?: ($a->getMax() ?? PHP_INT_MAX) <=> ($b->getMax() ?? PHP_INT_MAX),
536: );
537: // array_merge() hands the first array back as it is when the second one
538: // is empty, so the keys the bucketing above unset must be renumbered here
539: if ($floatRangeTypes === []) {
540: // most unions have no float range, and sorting an empty list still creates the closure
541: $types = array_merge(array_values($types), $integerRangeTypes);
542: } else {
543: usort(
544: $floatRangeTypes,
545: static fn (FloatRangeType $a, FloatRangeType $b): int => $a->getMin() <=> $b->getMin() ?: $a->getMax() <=> $b->getMax(),
546: );
547: // sorted by min, touching float ranges are neighbours: merging them now lets a
548: // constant meet the merged range (float<min, max> and NAN are float)
549: $mergedFloatRangeTypes = [];
550: foreach ($floatRangeTypes as $floatRangeType) {
551: $last = count($mergedFloatRangeTypes) - 1;
552: if ($last >= 0) {
553: $merged = $mergedFloatRangeTypes[$last]->tryUnion($floatRangeType);
554: if ($merged instanceof FloatRangeType) {
555: $mergedFloatRangeTypes[$last] = $merged;
556: continue;
557: }
558: }
559: $mergedFloatRangeTypes[] = $floatRangeType;
560: }
561: $types = array_merge(array_values($types), $integerRangeTypes, $mergedFloatRangeTypes);
562: }
563: $typesCount = count($types);
564:
565: if (isset($scalarTypes[IntersectionType::class])) {
566: $scalarTypes[IntersectionType::class] = self::reduceRefinedConstantScalars($scalarTypes[IntersectionType::class], $scalarTypes);
567: }
568:
569: foreach ($scalarTypes as $classType => $scalarTypeItems) {
570: if (isset($hasGenericScalarTypes[$classType])) {
571: unset($scalarTypes[$classType]);
572: continue;
573: }
574: if ($classType === ConstantBooleanType::class && count($scalarTypeItems) === 2) {
575: $types[] = new BooleanType();
576: $typesCount++;
577: unset($scalarTypes[$classType]);
578: continue;
579: }
580:
581: $scalarTypeItems = array_values($scalarTypeItems);
582: $scalarTypeItemsCount = count($scalarTypeItems);
583: for ($i = 0; $i < $typesCount; $i++) {
584: for ($j = 0; $j < $scalarTypeItemsCount; $j++) {
585: $compareResult = self::compareTypesInUnion($types[$i], $scalarTypeItems[$j]);
586: if ($compareResult === null) {
587: continue;
588: }
589:
590: [$a, $b] = $compareResult;
591: if ($a !== null) {
592: $types[$i] = $a;
593: array_splice($scalarTypeItems, $j, 1);
594: $scalarTypeItemsCount--;
595: $j = -1;
596: continue 1;
597: }
598: if ($b !== null) {
599: $scalarTypeItems[$j] = $b;
600: array_splice($types, $i--, 1);
601: $typesCount--;
602: continue 2;
603: }
604: }
605: }
606:
607: $scalarTypes[$classType] = $scalarTypeItems;
608: }
609:
610: if (count($types) > 16) {
611: $newTypes = [];
612: foreach ($types as $type) {
613: $newTypes[$type->describe(VerbosityLevel::cache())] = $type;
614: }
615: $types = array_values($newTypes);
616: }
617:
618: // compareTypesInUnion() leaves a pair of constant arrays as it is unless
619: // both are intersections, so such pairs are skipped without calling it. A
620: // bare ConstantArrayType is the only type whose getConstantArrays() is
621: // itself. Every array went to processArrayTypes(), so only its results
622: // can be such.
623: $processedArrayTypes = self::processArrayTypes($arrayTypes);
624: $isPlainConstantArray = null;
625: if (count($processedArrayTypes) > 1) {
626: $isPlainConstantArray = array_fill(0, count($types), false);
627: foreach ($processedArrayTypes as $processedArrayType) {
628: $isPlainConstantArray[] = $processedArrayType->getConstantArrays() === [$processedArrayType];
629: }
630: }
631: $types = array_merge(
632: $types,
633: $processedArrayTypes,
634: );
635: $typesCount = count($types);
636:
637: // $alreadyNormalized keeps the members alive, so their object ids stay
638: // unique while this lookup refers to them
639: $normalizedGroupsByType = [];
640: $normalizedTwice = [];
641: // a single flattened union of a few members, as in most unions, is cheaper to scan - without
642: // new local variables, which every call of this method initializes
643: $scanAlreadyNormalized = $alreadyNormalizedCounter === 1 && count($alreadyNormalized[0]) <= self::ALREADY_NORMALIZED_SCAN_LIMIT;
644: if ($typesCount > 1 && !$scanAlreadyNormalized) {
645: foreach ($alreadyNormalized as $group => $normalizedTypes) {
646: foreach ($normalizedTypes as $normalizedType) {
647: $normalizedTypeId = spl_object_id($normalizedType);
648: if (isset($normalizedGroupsByType[$normalizedTypeId][$group])) {
649: $normalizedTwice[$normalizedTypeId] = true;
650: continue;
651: }
652: $normalizedGroupsByType[$normalizedTypeId][$group] = $group;
653: }
654: }
655: }
656:
657: // transform A | A to A
658: // transform A | never to A
659: for ($i = 0; $i < $typesCount; $i++) {
660: if ($scanAlreadyNormalized) {
661: // null for a type not in the flattened union, which skips the scan of its pairs below
662: $iGroups = in_array($types[$i], $alreadyNormalized[0], true) ? [] : null;
663: } else {
664: $iGroups = $normalizedGroupsByType[spl_object_id($types[$i])] ?? null;
665: }
666: for ($j = $i + 1; $j < $typesCount; $j++) {
667: if ($isPlainConstantArray !== null && $isPlainConstantArray[$i] && $isPlainConstantArray[$j]) {
668: continue;
669: }
670: if ($iGroups !== null) {
671: if ($scanAlreadyNormalized) {
672: // what isAlreadyNormalized() answers: $types[$j] is another member of
673: // the flattened union, which holds $types[$i]
674: $normalizedTypes = $alreadyNormalized[0];
675: if (
676: $types[$i] !== $types[$j]
677: ? in_array($types[$j], $normalizedTypes, true)
678: : count(array_keys($normalizedTypes, $types[$j], true)) > 1
679: ) {
680: continue;
681: }
682: } elseif (self::isAlreadyNormalized($iGroups, $normalizedGroupsByType, $normalizedTwice, $types[$i], $types[$j])) {
683: continue;
684: }
685: }
686: $compareResult = self::compareTypesInUnion($types[$i], $types[$j]);
687: if ($compareResult === null) {
688: continue;
689: }
690:
691: [$a, $b] = $compareResult;
692: if ($a !== null) {
693: $types[$i] = $a;
694: $iGroups = $scanAlreadyNormalized
695: ? (in_array($a, $alreadyNormalized[0], true) ? [] : null)
696: : ($normalizedGroupsByType[spl_object_id($a)] ?? null);
697: if ($isPlainConstantArray !== null) {
698: $isPlainConstantArray[$i] = $a->getConstantArrays() === [$a];
699: array_splice($isPlainConstantArray, $j, 1);
700: }
701: array_splice($types, $j--, 1);
702: $typesCount--;
703: continue 1;
704: }
705: if ($b === null) {
706: continue;
707: }
708:
709: $types[$j] = $b;
710: if ($isPlainConstantArray !== null) {
711: $isPlainConstantArray[$j] = $b->getConstantArrays() === [$b];
712: array_splice($isPlainConstantArray, $i, 1);
713: }
714: array_splice($types, $i--, 1);
715: $typesCount--;
716: continue 2;
717: }
718: }
719:
720: $enumCasesCount = count($enumCaseTypes);
721: for ($i = 0; $i < $typesCount; $i++) {
722: for ($j = 0; $j < $enumCasesCount; $j++) {
723: $compareResult = self::compareTypesInUnion($types[$i], $enumCaseTypes[$j]);
724: if ($compareResult === null) {
725: continue;
726: }
727:
728: [$a, $b] = $compareResult;
729: if ($a !== null) {
730: $types[$i] = $a;
731: array_splice($enumCaseTypes, $j--, 1);
732: $enumCasesCount--;
733: continue 1;
734: }
735: if ($b !== null) {
736: $enumCaseTypes[$j] = $b;
737: array_splice($types, $i--, 1);
738: $typesCount--;
739: continue 2;
740: }
741: }
742: }
743:
744: foreach ($enumCaseTypes as $enumCaseType) {
745: $types[] = $enumCaseType;
746: $typesCount++;
747: }
748:
749: foreach ($scalarTypes as $scalarTypeItems) {
750: foreach ($scalarTypeItems as $scalarType) {
751: $types[] = $scalarType;
752: $typesCount++;
753: }
754: }
755:
756: if ($typesCount === 0) {
757: return new NeverType();
758: }
759: if ($typesCount === 1) {
760: return $types[0];
761: }
762:
763: if ($benevolentTypes !== []) {
764: $allBenevolent = true;
765: foreach ($types as $type) {
766: if (isset($benevolentTypes[$type->describe(VerbosityLevel::value())])) {
767: continue;
768: }
769:
770: // a member that absorbed a benevolent member stays benevolent,
771: // like int absorbing int<1, max> from (int<1, max>|string) and 0
772: foreach ($benevolentTypes as $benevolentType) {
773: if ($type->isSuperTypeOf($benevolentType)->yes()) {
774: continue 2;
775: }
776: }
777:
778: $allBenevolent = false;
779: break;
780: }
781:
782: if ($allBenevolent) {
783: return new BenevolentUnionType(array_values($types), true);
784: }
785: }
786:
787: return new UnionType(array_values($types), true);
788: }
789:
790: /**
791: * An unresolved template argument is a variable of its site, not the type it
792: * currently stands for: unresolved(int) from two different sites are two
793: * variables, and neither int nor the other variable absorbs it. Only the same
794: * variable merges - into the wider of the two inferred types.
795: *
796: * @param array<string, UnresolvedTemplateArgumentType> $markers
797: * @return array<string, UnresolvedTemplateArgumentType>
798: */
799: private static function addMarker(array $markers, UnresolvedTemplateArgumentType $marker): array
800: {
801: $key = spl_object_id($marker->getSite()) . '#' . $marker->getTemplateName();
802: $existing = $markers[$key] ?? null;
803: if ($existing === null || $existing === $marker) {
804: $markers[$key] = $marker;
805: return $markers;
806: }
807:
808: $existingInitial = $existing->getInitialType();
809: $initial = $marker->getInitialType();
810: if ($existingInitial === null || $initial === null) {
811: // nothing inferred stands for the template's default or bound
812: $markers[$key] = $existingInitial === null ? $existing : $marker;
813: return $markers;
814: }
815:
816: $markers[$key] = $existing->withInitialType(self::union($existingInitial, $initial));
817:
818: return $markers;
819: }
820:
821: /**
822: * @param array<string, UnresolvedTemplateArgumentType> $markers
823: */
824: private static function unionWithMarkers(Type $rest, array $markers): Type
825: {
826: if ($rest instanceof MixedType && !$rest instanceof TemplateMixedType && $rest->getSubtractedType() === null) {
827: return $rest;
828: }
829:
830: if ($rest instanceof NeverType) {
831: $members = [];
832: } elseif ($rest instanceof UnionType && !$rest instanceof TemplateType) {
833: $members = $rest->getTypes();
834: } else {
835: $members = [$rest];
836: }
837: foreach ($markers as $marker) {
838: $members[] = $marker;
839: }
840: if (count($members) === 1) {
841: return $members[0];
842: }
843: if ($rest instanceof BenevolentUnionType && !$rest instanceof TemplateType) {
844: return new BenevolentUnionType($members, true);
845: }
846:
847: return new UnionType($members, true);
848: }
849:
850: /**
851: * Whether $a and $b are members of one union that was flattened into this
852: * one - such members were already compared against each other.
853: *
854: * @param array<int, int> $aGroups the groups of $a in $normalizedGroupsByType
855: * @param array<int, array<int, int>> $normalizedGroupsByType member object id => (index of a flattened union holding it => the same index)
856: * @param array<int, true> $normalizedTwice member object ids a flattened union held twice
857: */
858: private static function isAlreadyNormalized(array $aGroups, array $normalizedGroupsByType, array $normalizedTwice, Type $a, Type $b): bool
859: {
860: if ($a === $b) {
861: return isset($normalizedTwice[spl_object_id($a)]);
862: }
863:
864: $bGroups = $normalizedGroupsByType[spl_object_id($b)] ?? null;
865: if ($bGroups === null) {
866: return false;
867: }
868:
869: foreach ($aGroups as $group) {
870: if (isset($bGroups[$group])) {
871: return true;
872: }
873: }
874:
875: return false;
876: }
877:
878: /**
879: * Scalar buckets are compared only against the non-scalar union members, which
880: * is correct for plain constants (distinct values are disjoint) but not for
881: * constants refined by another type ('Foo'&hasMethod(bar)). Those are absorbed
882: * here by the plain constant of the same value, or by a less refined
883: * intersection of the same value. Values never need to be compared across.
884: *
885: * @param array<string, Type> $intersections
886: * @param array<string, array<string, Type>> $scalarTypes
887: * @return array<string, Type>
888: */
889: private static function reduceRefinedConstantScalars(array $intersections, array $scalarTypes): array
890: {
891: $byValue = [];
892: foreach ($intersections as $key => $intersection) {
893: $constants = $intersection->getConstantScalarTypes();
894: if (count($constants) !== 1) {
895: continue;
896: }
897: $valueKey = $constants[0]->describe(VerbosityLevel::cache());
898: $plain = $scalarTypes[get_class($constants[0])][$valueKey] ?? null;
899: if ($plain !== null && $plain->isSuperTypeOf($intersection)->yes()) {
900: unset($intersections[$key]);
901: continue;
902: }
903: $byValue[get_class($constants[0])][$valueKey][] = $key;
904: }
905:
906: foreach ($byValue as $valueKeys) {
907: foreach ($valueKeys as $keys) {
908: $keysCount = count($keys);
909: for ($i = 0; $i < $keysCount; $i++) {
910: for ($j = 0; $j < $keysCount; $j++) {
911: if ($i === $j || !isset($intersections[$keys[$i]], $intersections[$keys[$j]])) {
912: continue;
913: }
914: if (!$intersections[$keys[$i]]->isSuperTypeOf($intersections[$keys[$j]])->yes()) {
915: continue;
916: }
917: unset($intersections[$keys[$j]]);
918: }
919: }
920: }
921: }
922:
923: return $intersections;
924: }
925:
926: /**
927: * @return array{Type, null}|array{null, Type}|null
928: */
929: private static function compareTypesInUnion(Type $a, Type $b): ?array
930: {
931: if ($a instanceof IntegerRangeType) {
932: $type = $a->tryUnion($b);
933: if ($type !== null) {
934: $a = $type;
935: return [$a, null];
936: }
937: }
938: if ($b instanceof IntegerRangeType) {
939: $type = $b->tryUnion($a);
940: if ($type !== null) {
941: $b = $type;
942: return [null, $b];
943: }
944: }
945: if ($a instanceof IntegerRangeType && $b instanceof IntegerRangeType) {
946: return null;
947: }
948: if ($a instanceof FloatRangeType) {
949: $type = $a->tryUnion($b);
950: if ($type !== null) {
951: return [$type, null];
952: }
953: }
954: if ($b instanceof FloatRangeType) {
955: $type = $b->tryUnion($a);
956: if ($type !== null) {
957: return [null, $type];
958: }
959: }
960: if ($a instanceof FloatRangeType && $b instanceof FloatRangeType) {
961: return null;
962: }
963: if ($a instanceof HasOffsetValueType && $b instanceof HasOffsetValueType) {
964: if ($a->getOffsetType()->equals($b->getOffsetType())) {
965: return [new HasOffsetValueType($a->getOffsetType(), self::union($a->getValueType(), $b->getValueType())), null];
966: }
967: }
968: if ($a instanceof IntersectionType && $b instanceof IntersectionType) {
969: $merged = self::mergeIntersectionsForUnion($a, $b);
970: if ($merged !== null) {
971: return [$merged, null];
972: }
973: }
974: if ($a->isConstantArray()->yes() && $b->isConstantArray()->yes()) {
975: return null;
976: }
977:
978: // simplify string[] | int[] to (string|int)[]
979: if ($a instanceof IterableType && $b instanceof IterableType) {
980: return [
981: new IterableType(
982: self::union($a->getIterableKeyType(), $b->getIterableKeyType()),
983: self::union($a->getIterableValueType(), $b->getIterableValueType()),
984: ),
985: null,
986: ];
987: }
988:
989: if ($a instanceof SubtractableType) {
990: $typeWithoutSubtractedTypeA = $a->getTypeWithoutSubtractedType();
991: if ($typeWithoutSubtractedTypeA instanceof MixedType && $b instanceof MixedType) {
992: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($b);
993: } else {
994: $isSuperType = $typeWithoutSubtractedTypeA->isSuperTypeOf($b);
995: }
996: if ($isSuperType->yes()) {
997: $a = self::intersectWithSubtractedType($a, $b);
998: return [$a, null];
999: }
1000: }
1001:
1002: if ($b instanceof SubtractableType) {
1003: $typeWithoutSubtractedTypeB = $b->getTypeWithoutSubtractedType();
1004: if ($typeWithoutSubtractedTypeB instanceof MixedType && $a instanceof MixedType) {
1005: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($a);
1006: } else {
1007: $isSuperType = $typeWithoutSubtractedTypeB->isSuperTypeOf($a);
1008: }
1009: if ($isSuperType->yes()) {
1010: $b = self::intersectWithSubtractedType($b, $a);
1011: return [null, $b];
1012: }
1013: }
1014:
1015: if ($b->isSuperTypeOf($a)->yes()) {
1016: return [null, $b];
1017: }
1018:
1019: if ($a->isSuperTypeOf($b)->yes()) {
1020: return [$a, null];
1021: }
1022:
1023: if (
1024: $a instanceof ConstantStringType
1025: ) {
1026: if ($a->getValue() === '') {
1027: $description = $b->describe(VerbosityLevel::value());
1028: if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
1029: return [null, self::intersect(
1030: new StringType(),
1031: ...self::getAccessoryCaseStringTypes($b),
1032: )];
1033: }
1034: }
1035:
1036: if ($a->getValue() === '0') {
1037: $nonEmpty = self::downgradeNonFalsyStringToNonEmpty($b);
1038: if ($nonEmpty !== null) {
1039: return [null, $nonEmpty];
1040: }
1041: }
1042: }
1043:
1044: if (
1045: $b instanceof ConstantStringType
1046: ) {
1047: if ($b->getValue() === '') {
1048: $description = $a->describe(VerbosityLevel::value());
1049: if (in_array($description, ['non-empty-string', 'non-falsy-string'], true)) {
1050: return [self::intersect(
1051: new StringType(),
1052: ...self::getAccessoryCaseStringTypes($a),
1053: ), null];
1054: }
1055: }
1056:
1057: if ($b->getValue() === '0') {
1058: $nonEmpty = self::downgradeNonFalsyStringToNonEmpty($a);
1059: if ($nonEmpty !== null) {
1060: return [$nonEmpty, null];
1061: }
1062: }
1063: }
1064:
1065: // numeric-string | non-decimal-int-string → string (preserving common accessories)
1066: // Works because decimal-int-string ⊂ numeric-string, so together they cover all strings
1067: // A base that is the type itself was compared with the other one above.
1068: if ($a->isString()->yes() && $b->isString()->yes()) {
1069: if ($b->isDecimalIntegerString()->no()) {
1070: $bBase = self::removeDecimalIntStringAccessory($b);
1071: if ($bBase !== $b && $bBase->isSuperTypeOf($a)->yes() && $a->isSuperTypeOf(new IntersectionType([new StringType(), new AccessoryDecimalIntegerStringType()]))->yes()) {
1072: return [null, $bBase];
1073: }
1074: }
1075: if ($a->isDecimalIntegerString()->no()) {
1076: $aBase = self::removeDecimalIntStringAccessory($a);
1077: if ($aBase !== $a && $aBase->isSuperTypeOf($b)->yes() && $b->isSuperTypeOf(new IntersectionType([new StringType(), new AccessoryDecimalIntegerStringType()]))->yes()) {
1078: return [$aBase, null];
1079: }
1080: }
1081: }
1082:
1083: return null;
1084: }
1085:
1086: /**
1087: * @return list<Type>
1088: */
1089: private static function getAccessoryCaseStringTypes(Type $type): array
1090: {
1091: $accessory = [];
1092: if ($type->isLowercaseString()->yes()) {
1093: $accessory[] = new AccessoryLowercaseStringType();
1094: }
1095: if ($type->isUppercaseString()->yes()) {
1096: $accessory[] = new AccessoryUppercaseStringType();
1097: }
1098:
1099: return $accessory;
1100: }
1101:
1102: /**
1103: * Turns a non-falsy-string type into its non-empty-string counterpart by
1104: * downgrading the non-falsy accessory while preserving every other accessory
1105: * (numeric-string, decimal-int-string, lowercase-string, …). Used to simplify
1106: * `'0' | non-falsy-string-X` back to `non-empty-string-X`, since `"0"` is the
1107: * only value that separates the two. Returns null when $type is not a
1108: * non-constant non-falsy-string built from an intersection.
1109: */
1110: private static function downgradeNonFalsyStringToNonEmpty(Type $type): ?Type
1111: {
1112: if (!$type instanceof IntersectionType || $type->isNonFalsyString()->no()) {
1113: return null;
1114: }
1115:
1116: $newTypes = [];
1117: $found = false;
1118: foreach ($type->getTypes() as $innerType) {
1119: if ($innerType instanceof AccessoryNonFalsyStringType) {
1120: $found = true;
1121: continue;
1122: }
1123:
1124: $newTypes[] = $innerType;
1125: }
1126:
1127: if (!$found) {
1128: return null;
1129: }
1130:
1131: $withoutNonFalsy = self::intersect(...$newTypes);
1132: if ($withoutNonFalsy->isNonEmptyString()->yes()) {
1133: return $withoutNonFalsy;
1134: }
1135:
1136: return self::intersect($withoutNonFalsy, new AccessoryNonEmptyStringType());
1137: }
1138:
1139: private static function removeDecimalIntStringAccessory(Type $type): Type
1140: {
1141: if (!$type instanceof IntersectionType) {
1142: return $type;
1143: }
1144:
1145: return self::intersect(...array_filter(
1146: $type->getTypes(),
1147: static fn (Type $t): bool => !$t instanceof AccessoryDecimalIntegerStringType,
1148: ));
1149: }
1150:
1151: private static function unionWithSubtractedType(
1152: Type $type,
1153: ?Type $subtractedType,
1154: ): Type
1155: {
1156: if ($subtractedType === null) {
1157: return $type;
1158: }
1159:
1160: if ($subtractedType instanceof SubtractableType) {
1161: $withoutSubtracted = $subtractedType->getTypeWithoutSubtractedType();
1162: if ($withoutSubtracted->isSuperTypeOf($type)->yes()) {
1163: $subtractedSubtractedType = $subtractedType->getSubtractedType();
1164: if ($subtractedSubtractedType === null) {
1165: return new NeverType();
1166: }
1167:
1168: return self::intersect($type, $subtractedSubtractedType);
1169: }
1170: }
1171:
1172: if ($type instanceof SubtractableType) {
1173: $subtractedType = $type->getSubtractedType() === null
1174: ? $subtractedType
1175: : self::union($type->getSubtractedType(), $subtractedType);
1176:
1177: $subtractedType = self::intersect(
1178: $type->getTypeWithoutSubtractedType(),
1179: $subtractedType,
1180: );
1181: if ($subtractedType instanceof NeverType) {
1182: $subtractedType = null;
1183: }
1184:
1185: return $type->changeSubtractedType($subtractedType);
1186: }
1187:
1188: if ($subtractedType->isSuperTypeOf($type)->yes()) {
1189: return new NeverType();
1190: }
1191:
1192: return self::remove($type, $subtractedType);
1193: }
1194:
1195: private static function intersectWithSubtractedType(
1196: SubtractableType $a,
1197: Type $b,
1198: ): Type
1199: {
1200: if ($a->getSubtractedType() === null || $b instanceof NeverType) {
1201: return $a;
1202: }
1203:
1204: if ($b instanceof IntersectionType) {
1205: $subtractableTypes = [];
1206: foreach ($b->getTypes() as $innerType) {
1207: if (!$innerType instanceof SubtractableType) {
1208: continue;
1209: }
1210:
1211: $subtractableTypes[] = $innerType;
1212: }
1213:
1214: if (count($subtractableTypes) === 0) {
1215: return $a->getTypeWithoutSubtractedType();
1216: }
1217:
1218: $subtractedTypes = [];
1219: foreach ($subtractableTypes as $subtractableType) {
1220: if ($subtractableType->getSubtractedType() === null) {
1221: continue;
1222: }
1223:
1224: $subtractedTypes[] = $subtractableType->getSubtractedType();
1225: }
1226:
1227: if (count($subtractedTypes) === 0) {
1228: return $a->getTypeWithoutSubtractedType();
1229:
1230: }
1231:
1232: $subtractedType = self::union(...$subtractedTypes);
1233: } else {
1234: $isBAlreadySubtracted = $a->getSubtractedType()->isSuperTypeOf($b);
1235:
1236: if ($isBAlreadySubtracted->no()) {
1237: return $a;
1238: } elseif ($isBAlreadySubtracted->yes()) {
1239: $subtractedType = self::remove($a->getSubtractedType(), $b);
1240:
1241: if (
1242: $subtractedType instanceof NeverType
1243: || !$subtractedType->isSuperTypeOf($b)->no()
1244: ) {
1245: $subtractedType = null;
1246: }
1247:
1248: return $a->changeSubtractedType($subtractedType);
1249: } elseif ($b instanceof SubtractableType) {
1250: $subtractedType = $b->getSubtractedType();
1251: if ($subtractedType === null) {
1252: return $a->getTypeWithoutSubtractedType();
1253: }
1254: } else {
1255: $subtractedTypeTmp = self::intersect($a->getTypeWithoutSubtractedType(), $a->getSubtractedType());
1256: if ($b->isSuperTypeOf($subtractedTypeTmp)->yes()) {
1257: return $a->getTypeWithoutSubtractedType();
1258: }
1259: $subtractedType = new MixedType(subtractedType: $b);
1260: }
1261: }
1262:
1263: $subtractedType = self::intersect(
1264: $a->getSubtractedType(),
1265: $subtractedType,
1266: );
1267: if ($subtractedType instanceof NeverType) {
1268: $subtractedType = null;
1269: }
1270:
1271: return $a->changeSubtractedType($subtractedType);
1272: }
1273:
1274: /**
1275: * @param Type[] $arrayTypes
1276: * @return list<Type>
1277: */
1278: private static function processArrayAccessoryTypes(array $arrayTypes): array
1279: {
1280: $isIterableAtLeastOnce = [];
1281: $accessoryTypes = [];
1282: foreach ($arrayTypes as $i => $arrayType) {
1283: $isIterableAtLeastOnce[] = $arrayType->isIterableAtLeastOnce();
1284:
1285: if ($arrayType instanceof IntersectionType) {
1286: // asked once: the same for every hasOffset() member, and an
1287: // intersection computes it from all of its members
1288: $iterableValueType = null;
1289: foreach ($arrayType->getTypes() as $innerType) {
1290: if ($innerType instanceof TemplateType) {
1291: break;
1292: }
1293: if (!($innerType instanceof AccessoryType) && !($innerType instanceof CallableType)) {
1294: continue;
1295: }
1296: if ($innerType instanceof HasOffsetType) {
1297: $iterableValueType ??= $arrayType->getIterableValueType();
1298: $innerType = new HasOffsetValueType($innerType->getOffsetType(), $iterableValueType);
1299: }
1300: if ($innerType instanceof HasOffsetValueType) {
1301: $accessoryTypes[sprintf('hasOffsetValue(%s)', $innerType->getOffsetType()->describe(VerbosityLevel::cache()))][$i] = $innerType;
1302: continue;
1303: }
1304:
1305: $accessoryTypes[$innerType->describe(VerbosityLevel::cache())][$i] = $innerType;
1306: }
1307: }
1308:
1309: if (!$arrayType->isConstantArray()->yes()) {
1310: continue;
1311: }
1312: $constantArrays = $arrayType->getConstantArrays();
1313:
1314: foreach ($constantArrays as $constantArray) {
1315: if ($constantArray->isList()->yes()) {
1316: $list = new AccessoryArrayListType();
1317: $accessoryTypes[$list->describe(VerbosityLevel::cache())][$i] = $list;
1318: }
1319:
1320: if (!$constantArray->isIterableAtLeastOnce()->yes()) {
1321: continue;
1322: }
1323:
1324: $nonEmpty = new NonEmptyArrayType();
1325: $accessoryTypes[$nonEmpty->describe(VerbosityLevel::cache())][$i] = $nonEmpty;
1326: }
1327: }
1328:
1329: $commonAccessoryTypes = [];
1330: $arrayTypeCount = count($arrayTypes);
1331: foreach ($accessoryTypes as $accessoryType) {
1332: if (count($accessoryType) !== $arrayTypeCount) {
1333: $firstKey = array_key_first($accessoryType);
1334: if ($accessoryType[$firstKey] instanceof OversizedArrayType) {
1335: $commonAccessoryTypes[] = $accessoryType[$firstKey];
1336: }
1337: continue;
1338: }
1339:
1340: if ($accessoryType[0] instanceof HasOffsetValueType) {
1341: $commonAccessoryTypes[] = self::union(...$accessoryType);
1342: continue;
1343: }
1344:
1345: $commonAccessoryTypes[] = $accessoryType[0];
1346: }
1347:
1348: if (TrinaryLogic::createYes()->and(...$isIterableAtLeastOnce)->yes()) {
1349: $commonAccessoryTypes[] = new NonEmptyArrayType();
1350: }
1351:
1352: return $commonAccessoryTypes;
1353: }
1354:
1355: /**
1356: * @param Type[] $arrayTypes
1357: */
1358: private static function findEmptyArrayNextToOversizedArray(array $arrayTypes): ?Type
1359: {
1360: if (count($arrayTypes) < 2) {
1361: return null;
1362: }
1363:
1364: $emptyArray = null;
1365: $hasOversizedArray = false;
1366: foreach ($arrayTypes as $arrayType) {
1367: if ($arrayType->isOversizedArray()->yes()) {
1368: $hasOversizedArray = true;
1369: } elseif ($emptyArray === null && $arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
1370: $emptyArray = $arrayType;
1371: }
1372: }
1373:
1374: return $hasOversizedArray ? $emptyArray : null;
1375: }
1376:
1377: /**
1378: * @param list<Type> $arrayTypes
1379: * @return Type[]
1380: */
1381: private static function processArrayTypes(array $arrayTypes): array
1382: {
1383: if ($arrayTypes === []) {
1384: return [];
1385: }
1386:
1387: $emptyArray = self::findEmptyArrayNextToOversizedArray($arrayTypes);
1388: if ($emptyArray !== null) {
1389: // like reduceArrays() does when it generalizes to an oversized array:
1390: // folded into it, the empty array would be lost to the oversized
1391: // accessory, which accepts only arrays that hold something
1392: $otherArrayTypes = [];
1393: foreach ($arrayTypes as $arrayType) {
1394: if ($arrayType->isConstantArray()->yes() && $arrayType->isIterableAtLeastOnce()->no()) {
1395: continue;
1396: }
1397: $otherArrayTypes[] = $arrayType;
1398: }
1399:
1400: return [$emptyArray, ...self::processArrayTypes($otherArrayTypes)];
1401: }
1402:
1403: $accessoryTypes = self::processArrayAccessoryTypes($arrayTypes);
1404:
1405: if (count($arrayTypes) === 1) {
1406: return [
1407: self::intersect(...$arrayTypes, ...$accessoryTypes),
1408: ];
1409: }
1410:
1411: $keyTypesForGeneralArray = [];
1412: $valueTypesForGeneralArray = [];
1413: $generalArrayOccurred = false;
1414: $seenConstantKeyTypes = [];
1415:
1416: foreach ($arrayTypes as $arrayType) {
1417: $constantArrays = $arrayType->getConstantArrays();
1418: $isConstantArray = $constantArrays !== [];
1419:
1420: if (!$isConstantArray) {
1421: foreach ($arrayType->getArrays() as $type) {
1422: $keyTypesForGeneralArray[] = $type->getIterableKeyType();
1423: $valueTypesForGeneralArray[] = $type->getItemType();
1424: $generalArrayOccurred = true;
1425: }
1426: continue;
1427: }
1428:
1429: foreach ($constantArrays as $constantArray) {
1430: $valueTypes = $constantArray->getValueTypes();
1431: foreach ($constantArray->getKeyTypes() as $i => $keyType) {
1432: $valueTypesForGeneralArray[] = $valueTypes[$i];
1433:
1434: $keyTypeValue = $keyType->getValue();
1435: if (array_key_exists($keyTypeValue, $seenConstantKeyTypes)) {
1436: continue;
1437: }
1438: $seenConstantKeyTypes[$keyTypeValue] = true;
1439: $keyTypesForGeneralArray[] = $keyType;
1440: }
1441: }
1442: }
1443:
1444: if ($generalArrayOccurred) {
1445: $reducedArrayTypes = self::reduceArrays($arrayTypes, false);
1446: if (count($reducedArrayTypes) === 1) {
1447: return [self::intersect($reducedArrayTypes[0], ...$accessoryTypes)];
1448: }
1449:
1450: $templateArrayType = null;
1451: foreach ($arrayTypes as $arrayType) {
1452: if (!$arrayType instanceof TemplateArrayType) {
1453: $templateArrayType = null;
1454: break;
1455: }
1456:
1457: if ($templateArrayType !== null) {
1458: continue;
1459: }
1460:
1461: $templateArrayType = $arrayType;
1462: }
1463:
1464: $arrayType = new ArrayType(
1465: self::union(...$keyTypesForGeneralArray),
1466: self::union(...self::optimizeConstantArrays($valueTypesForGeneralArray)),
1467: );
1468:
1469: if ($templateArrayType !== null) {
1470: $arrayType = new TemplateArrayType(
1471: $templateArrayType->getScope(),
1472: $templateArrayType->getStrategy(),
1473: $templateArrayType->getVariance(),
1474: $templateArrayType->getName(),
1475: $arrayType,
1476: $templateArrayType->getDefault(),
1477: );
1478: }
1479:
1480: return [
1481: self::intersect($arrayType, ...$accessoryTypes),
1482: ];
1483: }
1484:
1485: $reducedArrayTypes = self::optimizeConstantArrays(self::reduceArrays($arrayTypes, true));
1486: foreach ($reducedArrayTypes as $idx => $reducedArray) {
1487: $applied = $accessoryTypes;
1488: if ($reducedArray->isIterableAtLeastOnce()->no()) {
1489: // Empty arrays cannot satisfy non-empty / oversized constraints —
1490: // applying those accessories would produce a contradictory intersection
1491: // (e.g. `array{}&oversized-array`) that rejects the very value it
1492: // represents, breaking the super-type contract of the union.
1493: $applied = array_values(array_filter(
1494: $applied,
1495: static fn (Type $t): bool => !($t instanceof OversizedArrayType) && !($t instanceof NonEmptyArrayType),
1496: ));
1497: }
1498: $reducedArrayTypes[$idx] = self::intersect($reducedArray, ...$applied);
1499: }
1500: return $reducedArrayTypes;
1501: }
1502:
1503: /**
1504: * Merges the arrays like a chain of mergeWith() calls. They have the same
1505: * keys in the same order, so the chain unions the values at each key. At a
1506: * key where every array holds only constant scalars, one union of all the
1507: * values is the same as the chain of unions, which was quadratic in the size
1508: * of its growing result - the chain only merges the rest of the shape, with a
1509: * placeholder at that key.
1510: *
1511: * @param non-empty-list<ConstantArrayType> $arrays
1512: */
1513: private static function mergeConstantArraysWithSameKeys(array $arrays): ConstantArrayType
1514: {
1515: $constantScalarValueTypes = [];
1516: if (!$arrays[0] instanceof TemplateType) {
1517: foreach (array_keys($arrays[0]->getValueTypes()) as $i) {
1518: $constantScalarValueTypes[$i] = [];
1519: }
1520: }
1521: foreach ($arrays as $array) {
1522: foreach ($array->getValueTypes() as $i => $valueType) {
1523: if (!array_key_exists($i, $constantScalarValueTypes)) {
1524: continue;
1525: }
1526: // the classes whose union is a plain concatenation of their
1527: // members, deduplicated - not ones merely holding a constant scalar
1528: $members = $valueType instanceof UnionType && !$valueType instanceof BenevolentUnionType && !$valueType instanceof TemplateType
1529: ? $valueType->getTypes()
1530: : [$valueType];
1531: foreach ($members as $member) {
1532: if (!$member instanceof ConstantScalarType || $member instanceof TemplateType) { // @phpstan-ignore phpstanApi.instanceofType
1533: unset($constantScalarValueTypes[$i]);
1534: continue 2;
1535: }
1536: }
1537: $constantScalarValueTypes[$i][] = $valueType;
1538: }
1539: }
1540:
1541: $placeholder = new NeverType(true);
1542: $merged = null;
1543: foreach ($arrays as $array) {
1544: if ($constantScalarValueTypes !== []) {
1545: $valueTypes = $array->getValueTypes();
1546: foreach (array_keys($constantScalarValueTypes) as $i) {
1547: $valueTypes[$i] = $placeholder;
1548: }
1549: $array = new ConstantArrayType($array->getKeyTypes(), $valueTypes, $array->getNextAutoIndexes(), $array->getOptionalKeys(), $array->isList(), $array->getUnsealedTypes());
1550: }
1551: $merged = $merged === null ? $array : $merged->mergeWith($array);
1552: }
1553:
1554: if ($constantScalarValueTypes === []) {
1555: return $merged;
1556: }
1557:
1558: $valueTypes = $merged->getValueTypes();
1559: foreach ($constantScalarValueTypes as $i => $types) {
1560: $valueTypes[$i] = self::union(...$types);
1561: }
1562:
1563: return new ConstantArrayType($merged->getKeyTypes(), $valueTypes, $merged->getNextAutoIndexes(), $merged->getOptionalKeys(), $merged->isList(), $merged->getUnsealedTypes());
1564: }
1565:
1566: /**
1567: * @param Type[] $types
1568: * @return Type[]
1569: */
1570: private static function optimizeConstantArrays(array $types): array
1571: {
1572: $constantArrayValuesCount = self::countConstantArrayValueTypes($types);
1573:
1574: if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1575: return $types;
1576: }
1577:
1578: // Stage 1: collapse same-key-set ConstantArrayType variants per-position
1579: // before the (lossy) generalization below kicks in. Variants with the
1580: // same key signature mergeWith losslessly into a single shape whose
1581: // values at each position are the union of the variants' values, which
1582: // drops the count while keeping the per-position structure. Without
1583: // this, a list of N similarly-shaped records (e.g. bug-7963) hits the
1584: // limit and the generalization decomposes every nested constant array
1585: // into a flat `non-empty-list<unionOfAllPositionValues>`, losing the
1586: // shape entirely.
1587: $signatureGroups = [];
1588: $nonConstantTypes = [];
1589: foreach ($types as $idx => $type) {
1590: if (!$type instanceof ConstantArrayType) {
1591: $nonConstantTypes[$idx] = $type;
1592: continue;
1593: }
1594: $signatureParts = [];
1595: $signatureParts[] = $type->isList()->yes() ? 'L' : 'A';
1596: foreach ($type->getKeyTypes() as $i => $keyType) {
1597: $signatureParts[] = ($type->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
1598: }
1599: $signatureGroups[implode(',', $signatureParts)][] = $type;
1600: }
1601: if ($signatureGroups !== []) {
1602: $collapsed = $nonConstantTypes;
1603: $anyMerged = false;
1604: foreach ($signatureGroups as $group) {
1605: if (count($group) === 1) {
1606: $collapsed[] = $group[0];
1607: continue;
1608: }
1609: $collapsed[] = self::mergeConstantArraysWithSameKeys($group);
1610: $anyMerged = true;
1611: }
1612: if ($anyMerged) {
1613: $types = array_values($collapsed);
1614: $constantArrayValuesCount = self::countConstantArrayValueTypes($types);
1615: if ($constantArrayValuesCount <= ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1616: return $types;
1617: }
1618: }
1619: }
1620:
1621: $results = [];
1622: $emptyArrays = [];
1623: $eachIsOversized = true;
1624: foreach ($types as $type) {
1625: if ($type->isConstantArray()->yes() && $type->isIterableAtLeastOnce()->no()) {
1626: $emptyArrays[] = $type;
1627: continue;
1628: }
1629:
1630: $isOversized = false;
1631: $result = TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$isOversized): Type {
1632: if (!$type instanceof ConstantArrayType) {
1633: return $traverse($type);
1634: }
1635:
1636: if ($type->isIterableAtLeastOnce()->no()) {
1637: return $type;
1638: }
1639:
1640: $isOversized = true;
1641:
1642: $isList = true;
1643: $valueTypes = [];
1644: $keyTypes = [];
1645: $nextAutoIndex = 0;
1646: $innerValueTypes = $type->getValueTypes();
1647: foreach ($type->getKeyTypes() as $i => $innerKeyType) {
1648: if (!$innerKeyType instanceof ConstantIntegerType) {
1649: $isList = false;
1650: } elseif ($innerKeyType->getValue() !== $nextAutoIndex) {
1651: $isList = false;
1652: $nextAutoIndex = $innerKeyType->getValue() + 1;
1653: } else {
1654: $nextAutoIndex++;
1655: }
1656:
1657: $generalizedKeyType = $innerKeyType->generalize(GeneralizePrecision::moreSpecific());
1658: $keyTypes[$generalizedKeyType->describe(VerbosityLevel::precise())] = $generalizedKeyType;
1659:
1660: // Inner traversal of the value position. Two subtleties, both
1661: // of which produced types that failed to be super-types of
1662: // their contributors:
1663: // - Empty constant arrays must be left alone; wrapping them
1664: // builds a contradictory `array{}&oversized-array`.
1665: // - Fall through via `$innerTraverse`, not the outer
1666: // `$traverse`. The outer callback fully generalizes a
1667: // sealed `ConstantArrayType` into `array<intKey, V>&...`,
1668: // which is correct at the top level but wrong inside a
1669: // value position: it would treat a sealed `array{a: 1}`
1670: // reached via `array{}|array{a: 1}` differently from one
1671: // reached directly, leaving `processArrayTypes` with a
1672: // mix of shapes it cannot unify cleanly.
1673: $generalizedValueType = TypeTraverser::map($innerValueTypes[$i], static function (Type $type, callable $innerTraverse): Type {
1674: if ($type instanceof ConstantArrayType && $type->isIterableAtLeastOnce()->no()) {
1675: return $type;
1676: }
1677:
1678: if ($type instanceof ArrayType || $type instanceof ConstantArrayType) {
1679: return new IntersectionType([$type, new OversizedArrayType()]);
1680: }
1681:
1682: if ($type instanceof ConstantScalarType) {
1683: return $type->generalize(GeneralizePrecision::moreSpecific());
1684: }
1685:
1686: return $innerTraverse($type);
1687: });
1688: $valueTypes[$generalizedValueType->describe(VerbosityLevel::precise())] = $generalizedValueType;
1689: }
1690:
1691: $keyType = TypeCombinator::union(...array_values($keyTypes));
1692: $valueType = TypeCombinator::union(...array_values($valueTypes));
1693:
1694: $accessories = [];
1695: if ($isList) {
1696: $accessories[] = new AccessoryArrayListType();
1697: }
1698: $accessories[] = new NonEmptyArrayType();
1699: $accessories[] = new OversizedArrayType();
1700:
1701: return self::intersect(new ArrayType($keyType, $valueType), ...$accessories);
1702: });
1703:
1704: if (!$isOversized) {
1705: $eachIsOversized = false;
1706: }
1707:
1708: $results[] = $result;
1709: }
1710:
1711: if ($eachIsOversized && $results !== []) {
1712: $eachIsList = true;
1713: $keyTypes = [];
1714: $valueTypes = [];
1715: foreach ($results as $result) {
1716: $keyTypes[] = $result->getIterableKeyType();
1717: $valueTypes[] = $result->getIterableValueType();
1718: if ($result->isList()->yes()) {
1719: continue;
1720: }
1721: $eachIsList = false;
1722: }
1723:
1724: $keyType = self::union(...$keyTypes);
1725: $valueType = self::union(...$valueTypes);
1726:
1727: if ($valueType instanceof UnionType && count($valueType->getTypes()) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT) {
1728: $valueType = $valueType->generalize(GeneralizePrecision::lessSpecific());
1729: }
1730:
1731: $accessories = [];
1732: if ($eachIsList) {
1733: $accessories[] = new AccessoryArrayListType();
1734: }
1735: $accessories[] = new NonEmptyArrayType();
1736: $accessories[] = new OversizedArrayType();
1737:
1738: return [...$emptyArrays, self::intersect(new ArrayType($keyType, $valueType), ...$accessories)];
1739: }
1740:
1741: return [...$emptyArrays, ...$results];
1742: }
1743:
1744: /**
1745: * @param Type[] $types
1746: */
1747: public static function countConstantArrayValueTypes(array $types): int
1748: {
1749: $constantArrayValuesCount = 0;
1750: // A type shared by several positions (array shape keys written
1751: // through a union offset all hold the same value type) is counted
1752: // once per position, but traversed only once. The entries keep the
1753: // visited types alive so that their object ids are not reused.
1754: $countsByType = [];
1755: foreach ($types as $type) {
1756: TypeTraverser::map($type, static function (Type $type, callable $traverse) use (&$constantArrayValuesCount, &$countsByType): Type {
1757: $id = spl_object_id($type);
1758: if (array_key_exists($id, $countsByType)) {
1759: $constantArrayValuesCount += $countsByType[$id][1];
1760: return $type;
1761: }
1762:
1763: $countBefore = $constantArrayValuesCount;
1764: if ($type instanceof ConstantArrayType) {
1765: $constantArrayValuesCount += count($type->getValueTypes());
1766: }
1767:
1768: $result = $traverse($type);
1769: $countsByType[$id] = [$type, $constantArrayValuesCount - $countBefore];
1770:
1771: return $result;
1772: });
1773: }
1774: return $constantArrayValuesCount;
1775: }
1776:
1777: /**
1778: * The value at each key of the array that is a single constant scalar, null
1779: * when the array has real unsealed extras - its keys-supersets are then not
1780: * decided by the known keys alone.
1781: *
1782: * @return array<int|string, scalar|null>|null
1783: */
1784: private static function getConstantScalarValuesByKey(ConstantArrayType $array): ?array
1785: {
1786: $unsealed = $array->getUnsealedTypes();
1787: if ($unsealed !== null && !($unsealed[0] instanceof NeverType && $unsealed[0]->isExplicit())) {
1788: return null;
1789: }
1790:
1791: $values = [];
1792: $valueTypes = $array->getValueTypes();
1793: // keys written through a union offset share one value type - inspect it once
1794: $singleValues = [];
1795: foreach ($array->getKeyTypes() as $i => $keyType) {
1796: $id = spl_object_id($valueTypes[$i]);
1797: if (array_key_exists($id, $singleValues)) {
1798: if ($singleValues[$id] !== null) {
1799: $values[$keyType->getValue()] = $singleValues[$id][0];
1800: }
1801: continue;
1802: }
1803: $singleValues[$id] = null;
1804: if (!$valueTypes[$i]->isConstantScalarValue()->yes()) {
1805: continue;
1806: }
1807: $constantScalarValues = $valueTypes[$i]->getConstantScalarValues();
1808: if (count($constantScalarValues) !== 1) {
1809: continue;
1810: }
1811: $singleValues[$id] = [$constantScalarValues[0]];
1812: $values[$keyType->getValue()] = $constantScalarValues[0];
1813: }
1814:
1815: return $values;
1816: }
1817:
1818: /**
1819: * Whether two arrays differ in enough keys holding different single constant
1820: * scalars that neither can be a keys-superset of the other: each such key
1821: * pairs two disjoint values, and ConstantArrayType::isKeysSupersetOf() lets
1822: * at most one key's values be unrelated - only when both arrays have the
1823: * same number of keys, two or more.
1824: *
1825: * @param array<int|string, scalar|null>|null $a
1826: * @param array<int|string, scalar|null>|null $b
1827: */
1828: private static function haveDisjointConstantScalarValues(?array $a, ?array $b, bool $oneUnrelatedKeyAllowed): bool
1829: {
1830: if ($a === null || $b === null) {
1831: return false;
1832: }
1833: if (count($a) > count($b)) {
1834: [$a, $b] = [$b, $a];
1835: }
1836:
1837: $differing = 0;
1838: foreach ($a as $key => $value) {
1839: if (!array_key_exists($key, $b) || $b[$key] === $value) {
1840: continue;
1841: }
1842: $differing++;
1843: if ($differing >= 2 || !$oneUnrelatedKeyAllowed) {
1844: return true;
1845: }
1846: }
1847:
1848: return false;
1849: }
1850:
1851: /**
1852: * The arrays after $i sharing a key with it, by the first key they share
1853: * in $arraysToProcessPerKey's order, then by their indexes.
1854: *
1855: * @param array<int, list<int|string>> $keysByRank
1856: * @param array<int|string, list<int>> $arraysToProcessPerKey
1857: * @return list<int>
1858: */
1859: private static function getReduceArraysPartners(int $i, array $keysByRank, array $arraysToProcessPerKey): array
1860: {
1861: $partners = [];
1862: foreach ($keysByRank[$i] as $key) {
1863: foreach ($arraysToProcessPerKey[$key] as $j) {
1864: if ($j <= $i || isset($partners[$j])) {
1865: continue;
1866: }
1867: $partners[$j] = $j;
1868: }
1869: }
1870:
1871: return array_values($partners);
1872: }
1873:
1874: /**
1875: * @param list<Type> $constantArrays
1876: * @return list<Type>
1877: */
1878: private static function reduceArrays(array $constantArrays, bool $preserveTaggedUnions): array
1879: {
1880: $newArrays = [];
1881: $arraysToProcess = [];
1882: $emptyArray = null;
1883: foreach ($constantArrays as $constantArray) {
1884: if (!$constantArray->isConstantArray()->yes()) {
1885: // This is an optimization for current use-case of $preserveTaggedUnions=false, where we need
1886: // one constant array as a result, or we generalize the $constantArrays.
1887: if (!$preserveTaggedUnions) {
1888: return $constantArrays;
1889: }
1890: $newArrays[] = $constantArray;
1891: continue;
1892: }
1893:
1894: if ($constantArray->isIterableAtLeastOnce()->no()) {
1895: $emptyArray = $constantArray;
1896: continue;
1897: }
1898:
1899: $arraysToProcess = array_merge($arraysToProcess, $constantArray->getConstantArrays());
1900: }
1901:
1902: if ($emptyArray !== null) {
1903: if ($preserveTaggedUnions && $emptyArray instanceof ConstantArrayType) {
1904: // Let the empty array participate in merging — the passes below will absorb
1905: // it into any array that already accepts [] (all-optional keys, compatible
1906: // unsealed extras). If no such array exists, it remains as-is in the result.
1907: $arraysToProcess[] = $emptyArray;
1908: } else {
1909: $newArrays[] = $emptyArray;
1910: }
1911: }
1912:
1913: $arraysToProcessPerKey = [];
1914: foreach ($arraysToProcess as $i => $arrayToProcess) {
1915: foreach ($arrayToProcess->getKeyTypes() as $keyType) {
1916: $arraysToProcessPerKey[$keyType->getValue()][] = $i;
1917: }
1918: }
1919:
1920: // the single constant scalar value at each key of the arrays without
1921: // real unsealed extras (whose supersets the key/value shape decides)
1922: $constantScalarValues = [];
1923: if ($preserveTaggedUnions) {
1924: foreach ($arraysToProcess as $i => $arrayToProcess) {
1925: $constantScalarValues[$i] = self::getConstantScalarValuesByKey($arrayToProcess);
1926: }
1927: }
1928:
1929: // The loop below visits the pairs of arrays sharing a key: by the first
1930: // key they share in $arraysToProcessPerKey's order, then by their
1931: // indexes. It skips the pairs whose single constant scalar values rule out
1932: // a keys-superset (haveDisjointConstantScalarValues()). For arrays with the
1933: // same number of keys (two or more) and the same keys holding a single
1934: // constant scalar, those are the pairs differing in two or more of them, so
1935: // only the pairs sharing a bucket of the values with one key left out are
1936: // visited - enumerating all pairs is quadratic in the number of arrays,
1937: // which dominated unions of many same-shaped arrays (bug-12671).
1938: $keyRanks = array_flip(array_keys($arraysToProcessPerKey));
1939: $keySets = [];
1940: $keysByRank = [];
1941: foreach ($arraysToProcess as $i => $arrayToProcess) {
1942: $keys = [];
1943: foreach ($arrayToProcess->getKeyTypes() as $keyType) {
1944: $keys[$keyRanks[$keyType->getValue()]] = $keyType->getValue();
1945: }
1946: ksort($keys);
1947: $keysByRank[$i] = array_values($keys);
1948: $keySets[$i] = array_flip($keys);
1949: }
1950:
1951: $bucketGroups = [];
1952: $bucketPartners = [];
1953: $arraysPerKeyAndGroup = [];
1954: if ($preserveTaggedUnions) {
1955: $buckets = [];
1956: foreach ($constantScalarValues as $i => $values) {
1957: if ($values === null || $values === [] || count($keysByRank[$i]) < 2) {
1958: continue;
1959: }
1960:
1961: $sortedValues = [];
1962: foreach ($values as $key => $value) {
1963: // -0.0 === 0.0
1964: $sortedValues[$keyRanks[$key]] = $value === 0.0 ? 0.0 : $value;
1965: }
1966: ksort($sortedValues);
1967: $group = count($keysByRank[$i]) . ':' . implode(',', array_keys($sortedValues));
1968: $bucketGroups[$i] = $group;
1969: $sortedValues = array_values($sortedValues);
1970: foreach (array_keys($sortedValues) as $leftOut) {
1971: $projection = $sortedValues;
1972: unset($projection[$leftOut]);
1973: $buckets[$group . "\0" . $leftOut . "\0" . serialize($projection)][] = $i;
1974: }
1975: }
1976: foreach ($buckets as $bucket) {
1977: for ($a = 0, $bucketCount = count($bucket); $a < $bucketCount - 1; $a++) {
1978: for ($b = $a + 1; $b < $bucketCount; $b++) {
1979: $bucketPartners[$bucket[$a]][$bucket[$b]] = true;
1980: }
1981: }
1982: }
1983: foreach ($keysByRank as $i => $keys) {
1984: foreach ($keys as $key) {
1985: $arraysPerKeyAndGroup[$key][$bucketGroups[$i] ?? ''][] = $i;
1986: }
1987: }
1988: }
1989:
1990: $visitOrder = [];
1991: foreach ($keysByRank as $i => $keys) {
1992: foreach ($keys as $key) {
1993: $arrays = $arraysToProcessPerKey[$key];
1994: if ($arrays[count($arrays) - 1] !== $i) {
1995: $visitOrder[$keyRanks[$key]][] = $i;
1996: break;
1997: }
1998: }
1999: }
2000: ksort($visitOrder);
2001:
2002: $nullifiedConstantScalarValues = [];
2003: foreach ($visitOrder as $arraysOfRank) {
2004: foreach ($arraysOfRank as $i) {
2005: if (!array_key_exists($i, $arraysToProcess)) {
2006: continue;
2007: }
2008:
2009: $allPartnersVisited = !isset($bucketGroups[$i]) || $constantScalarValues[$i] === null;
2010: if ($allPartnersVisited) {
2011: $partners = self::getReduceArraysPartners($i, $keysByRank, $arraysToProcessPerKey);
2012: } else {
2013: // the bucket partners, the arrays not in $i's group and the
2014: // arrays that lost their single constant scalar values
2015: $partners = $bucketPartners[$i] ?? [];
2016: foreach ($keysByRank[$i] as $key) {
2017: foreach ($arraysPerKeyAndGroup[$key] as $group => $arrays) {
2018: if ($group === $bucketGroups[$i]) {
2019: continue;
2020: }
2021: foreach ($arrays as $j) {
2022: if ($j <= $i) {
2023: continue;
2024: }
2025: $partners[$j] = true;
2026: }
2027: }
2028: }
2029: foreach (array_keys($nullifiedConstantScalarValues) as $j) {
2030: if ($j <= $i || array_intersect_key($keySets[$i], $keySets[$j]) === []) {
2031: continue;
2032: }
2033: $partners[$j] = true;
2034: }
2035:
2036: $partnersByRank = [];
2037: foreach (array_keys($partners) as $j) {
2038: foreach ($keysByRank[$i] as $key) {
2039: if (isset($keySets[$j][$key])) {
2040: $partnersByRank[$keyRanks[$key]][] = $j;
2041: break;
2042: }
2043: }
2044: }
2045: ksort($partnersByRank);
2046: $partners = [];
2047: foreach ($partnersByRank as $partnersOfRank) {
2048: sort($partnersOfRank);
2049: foreach ($partnersOfRank as $j) {
2050: $partners[] = $j;
2051: }
2052: }
2053: }
2054:
2055: for ($p = 0; $p < count($partners); $p++) {
2056: $j = $partners[$p];
2057: if (!array_key_exists($j, $arraysToProcess)) {
2058: continue;
2059: }
2060:
2061: $overlappingKeysCount = count(array_intersect_key($keySets[$i], $keySets[$j]));
2062:
2063: // Merge two single-key arrays sharing the same key when their value
2064: // types union into a single type (not a UnionType). This is lossless
2065: // and prevents exponential union growth when narrowing nested
2066: // ArrayDimFetch expressions on a ConstantArrayType parent (see
2067: // phpstan/phpstan#14462).
2068: // mergeWith() unions the two values, so its result answers the
2069: // question, and a keys-superset merge of the same pair below
2070: // reuses it: unioning the values once more there made nested
2071: // single-key arrays (`$x = [$x]` in nested loops) exponential
2072: // in their depth.
2073: $singleKeyMerge = null;
2074: if (
2075: $preserveTaggedUnions
2076: && $overlappingKeysCount === 1
2077: && count($arraysToProcess[$i]->getKeyTypes()) === 1
2078: && count($arraysToProcess[$j]->getKeyTypes()) === 1
2079: ) {
2080: $singleKeyMerge = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
2081: if (!$singleKeyMerge->getValueTypes()[0] instanceof UnionType) {
2082: $arraysToProcess[$j] = $singleKeyMerge;
2083: $constantScalarValues[$j] = null;
2084: $nullifiedConstantScalarValues[$j] = true;
2085: unset($arraysToProcess[$i]);
2086: continue 2;
2087: }
2088: }
2089:
2090: if (
2091: $preserveTaggedUnions
2092: && self::haveDisjointConstantScalarValues(
2093: $constantScalarValues[$i] ?? null,
2094: $constantScalarValues[$j] ?? null,
2095: count($arraysToProcess[$i]->getKeyTypes()) === count($arraysToProcess[$j]->getKeyTypes())
2096: && count($arraysToProcess[$i]->getKeyTypes()) >= 2,
2097: )
2098: ) {
2099: // neither array is a keys-superset of the other
2100: continue;
2101: }
2102:
2103: if (
2104: $preserveTaggedUnions
2105: && $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
2106: && $arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])
2107: ) {
2108: $arraysToProcess[$j] = $singleKeyMerge ?? $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
2109: $constantScalarValues[$j] = null;
2110: $nullifiedConstantScalarValues[$j] = true;
2111: unset($arraysToProcess[$i]);
2112: continue 2;
2113: }
2114:
2115: if (
2116: $preserveTaggedUnions
2117: && $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
2118: && $arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])
2119: ) {
2120: $arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
2121: $constantScalarValues[$i] = null;
2122: $nullifiedConstantScalarValues[$i] = true;
2123: unset($arraysToProcess[$j]);
2124: if (!$allPartnersVisited) {
2125: // from now on visited with every array after $j
2126: $allPartners = self::getReduceArraysPartners($i, $keysByRank, $arraysToProcessPerKey);
2127: $partners = array_slice($allPartners, (int) array_search($j, $allPartners, true) + 1);
2128: $p = -1;
2129: $allPartnersVisited = true;
2130: }
2131: continue 1;
2132: }
2133:
2134: if (
2135: !$preserveTaggedUnions
2136: // both arrays have same keys
2137: && $overlappingKeysCount === count($arraysToProcess[$i]->getKeyTypes())
2138: && $overlappingKeysCount === count($arraysToProcess[$j]->getKeyTypes())
2139: ) {
2140: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
2141: unset($arraysToProcess[$i]);
2142: continue 2;
2143: }
2144: }
2145: }
2146: }
2147:
2148: // Second pass: merge pairs that the eligibleCombinations loop above couldn't touch.
2149: // That loop only considers pairs sharing at least one known key, so it never fires
2150: // for e.g. `array{}` ∪ `array{a?: 1}` (disjoint, one empty) or for two
2151: // unsealed-extras arrays with disjoint required keys. Both collapse losslessly if
2152: // one side's extras or optional-key shape can absorb the other side's content.
2153: //
2154: // Performance: two sealed, non-empty, no-extras arrays with disjoint keys cannot
2155: // merge losslessly (legacyIsKeysSupersetOf returns false immediately on the first
2156: // missing key). Skip those pairs via a candidate flag to avoid an O(n²) scan that
2157: // dominated analyse time on files accumulating many sealed ConstantArrayType
2158: // variants (bug-7581 / bug-8146a). A pair is worth checking only if at least one
2159: // side is (a) empty, or (b) has real unsealed extras, or (c) has optional keys —
2160: // the last case covers the narrowing shape used by e.g. array_key_exists checks
2161: // over large optional-key shapes (bug-14032).
2162: $indices = array_keys($arraysToProcess);
2163: $indicesCount = count($indices);
2164: if ($indicesCount > 1) {
2165: $candidateFlags = [];
2166: foreach ($indices as $idx) {
2167: $arr = $arraysToProcess[$idx];
2168: $unsealed = $arr->getUnsealedTypes();
2169: if ($unsealed === null) {
2170: $candidateFlags[$idx] = false;
2171: continue;
2172: }
2173: [$unsealedKey] = $unsealed;
2174: $hasRealExtras = !($unsealedKey instanceof NeverType && $unsealedKey->isExplicit());
2175: if ($hasRealExtras) {
2176: $candidateFlags[$idx] = true;
2177: continue;
2178: }
2179: $keyTypesCount = count($arr->getKeyTypes());
2180: if ($keyTypesCount === 0) {
2181: $candidateFlags[$idx] = true;
2182: continue;
2183: }
2184: $hasOptional = count($arr->getOptionalKeys()) > 0;
2185: $candidateFlags[$idx] = $hasOptional;
2186: }
2187:
2188: for ($ii = 0; $ii < $indicesCount - 1; $ii++) {
2189: $i = $indices[$ii];
2190: if (!array_key_exists($i, $arraysToProcess)) {
2191: continue;
2192: }
2193: if ($arraysToProcess[$i]->getUnsealedTypes() === null) {
2194: continue;
2195: }
2196: for ($jj = $ii + 1; $jj < $indicesCount; $jj++) {
2197: $j = $indices[$jj];
2198: if (!array_key_exists($j, $arraysToProcess)) {
2199: continue;
2200: }
2201: if (!$candidateFlags[$i] && !$candidateFlags[$j]) {
2202: continue;
2203: }
2204: if ($arraysToProcess[$j]->getUnsealedTypes() === null) {
2205: continue;
2206: }
2207: if ($arraysToProcess[$j]->isKeysSupersetOf($arraysToProcess[$i])) {
2208: $arraysToProcess[$j] = $arraysToProcess[$j]->mergeWith($arraysToProcess[$i]);
2209: unset($arraysToProcess[$i]);
2210: continue 2;
2211: }
2212: if (!$arraysToProcess[$i]->isKeysSupersetOf($arraysToProcess[$j])) {
2213: continue;
2214: }
2215:
2216: $arraysToProcess[$i] = $arraysToProcess[$i]->mergeWith($arraysToProcess[$j]);
2217: unset($arraysToProcess[$j]);
2218: }
2219: }
2220: }
2221:
2222: // Final pass: if merging left us with a ConstantArrayType that has no known keys
2223: // but has real unsealed extras, collapse it to a plain ArrayType (mirrors the same
2224: // logic in ConstantArrayTypeBuilder::getArray — but applies to results produced by
2225: // ConstantArrayType::mergeWith, which doesn't go through the builder).
2226: foreach ($arraysToProcess as $idx => $arr) {
2227: if (count($arr->getKeyTypes()) !== 0) {
2228: continue;
2229: }
2230: $unsealed = $arr->getUnsealedTypes();
2231: if ($unsealed === null) {
2232: continue;
2233: }
2234: [$unsealedKey, $unsealedValue] = $unsealed;
2235: if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
2236: continue;
2237: }
2238: $newArrays[] = new ArrayType($unsealedKey, $unsealedValue);
2239: unset($arraysToProcess[$idx]);
2240: }
2241:
2242: // Final pass: collapse the loop-accumulator pattern where each iteration
2243: // produced a longer non-empty list variant. When several non-empty list
2244: // ConstantArrayTypes survive earlier merging and together push the
2245: // constant-array value count past the limit, fold them into a single
2246: // non-empty-list<unionValueType> so the result stays bounded without
2247: // going through the lossier optimizeConstantArrays generalization.
2248: // Skip when every list variant shares one key signature — those collapse
2249: // losslessly via the stage 1 same-key-set merge in optimizeConstantArrays
2250: // (each position keeps its own value union), which is strictly more
2251: // precise than this flat fold.
2252: if ($preserveTaggedUnions && count($arraysToProcess) > 1) {
2253: $listVariantIndices = [];
2254: $listValueTypes = [];
2255: $listVariants = [];
2256: $listVariantSignatures = [];
2257: foreach ($arraysToProcess as $idx => $arr) {
2258: if (!$arr->isList()->yes() || !$arr->isIterableAtLeastOnce()->yes()) {
2259: continue;
2260: }
2261: $listVariantIndices[] = $idx;
2262: $listValueTypes[] = $arr->getIterableValueType();
2263: $listVariants[] = $arr;
2264: $signatureParts = [];
2265: foreach ($arr->getKeyTypes() as $i => $keyType) {
2266: $signatureParts[] = ($arr->isOptionalKey($i) ? '?' : '!') . ($keyType instanceof ConstantIntegerType ? 'i' : 's') . $keyType->getValue();
2267: }
2268: $listVariantSignatures[implode(',', $signatureParts)] = true;
2269: }
2270: if (
2271: count($listVariantIndices) >= 2
2272: && count($listVariantSignatures) >= 2
2273: && self::countConstantArrayValueTypes($listVariants) > ConstantArrayTypeBuilder::ARRAY_COUNT_LIMIT
2274: ) {
2275: $mergedValueType = self::union(...$listValueTypes);
2276: $merged = self::intersect(
2277: new ArrayType(new IntegerType(), $mergedValueType),
2278: new NonEmptyArrayType(),
2279: new AccessoryArrayListType(),
2280: );
2281: $newArrays[] = $merged;
2282: foreach ($listVariantIndices as $idx) {
2283: unset($arraysToProcess[$idx]);
2284: }
2285: }
2286: }
2287:
2288: return array_merge($newArrays, $arraysToProcess);
2289: }
2290:
2291: /**
2292: * Fast path for intersect(): the intersection of two unions whose members are all
2293: * finite, mutually-disjoint values (constant scalars and/or enum cases) is their
2294: * identity-keyed set intersection. Returns null when either union has a member that is
2295: * not such a value, in which case the caller falls back to the general A & (B|C)
2296: * distribution.
2297: */
2298: /** @phpstan-assert-if-true UnionType $type */
2299: private static function isPlainOrBenevolentUnion(Type $type): bool
2300: {
2301: $class = get_class($type);
2302:
2303: return $class === UnionType::class || $class === BenevolentUnionType::class;
2304: }
2305:
2306: private static function intersectFiniteUnions(UnionType $a, UnionType $b): ?Type
2307: {
2308: $membersA = self::finiteUnionMembers($a);
2309: if ($membersA === null) {
2310: return null;
2311: }
2312:
2313: $membersB = self::finiteUnionMembers($b);
2314: if ($membersB === null) {
2315: return null;
2316: }
2317:
2318: $common = [];
2319: foreach ($membersA as $key => $member) {
2320: if (!array_key_exists($key, $membersB)) {
2321: continue;
2322: }
2323:
2324: $common[] = $member;
2325: }
2326:
2327: if ($common === []) {
2328: return new NeverType();
2329: }
2330:
2331: return self::union(...$common);
2332: }
2333:
2334: /**
2335: * The union's members keyed by identity, or null when the fast path does not apply.
2336: *
2337: * FiniteTypeSet does the keying and the union caches it; on top of that, intersect()
2338: * hands one of the two members back instead of only comparing them, so a constant string
2339: * that is also a class-string is not interchangeable with a same-valued one that is not -
2340: * the class-string flag would be lost. Such unions go the slow way.
2341: *
2342: * @return array<string, Type>|null
2343: */
2344: private static function finiteUnionMembers(UnionType $union): ?array
2345: {
2346: $finiteTypeSet = $union->getFiniteTypeSet();
2347: if ($finiteTypeSet === null || !$finiteTypeSet->isComplete()) {
2348: return null;
2349: }
2350:
2351: return $finiteTypeSet->getMembers();
2352: }
2353:
2354: public static function intersect(Type ...$types): Type
2355: {
2356: if (self::$cacheEnabled ??= TurboExtensionEnabler::isTypeCombinatorCacheEnabled()) {
2357: return TypeCombinatorCache::intersect(...$types);
2358: }
2359:
2360: return self::doIntersect(...$types);
2361: }
2362:
2363: /** @internal Delegated to from TypeCombinatorCache, which the native extension shadows to memoize it. */
2364: public static function doIntersect(Type ...$types): Type
2365: {
2366: $typesCount = count($types);
2367: if ($typesCount === 0) {
2368: return new NeverType();
2369: }
2370:
2371: $types = array_values($types);
2372: if ($typesCount === 1) {
2373: return $types[0];
2374: }
2375:
2376: // The comparator only orders UnionTypes relative to each other, so sorting is
2377: // a no-op unless there are at least two of them. Skip it in the common case.
2378: $unionTypesCount = 0;
2379: foreach ($types as $type) {
2380: if ($type instanceof NeverType && !$type->isExplicit()) {
2381: return $type;
2382: }
2383: if (!$type instanceof UnionType) {
2384: continue;
2385: }
2386: $unionTypesCount++;
2387: }
2388:
2389: // Fast path: the intersection of two unions whose members are all finite,
2390: // mutually-disjoint values (constant scalars and/or enum cases) is their
2391: // identity-keyed set intersection (O(n)), avoiding the O(n*m) `A & (B|C)`
2392: // distribution + union rebuild below. A benevolent union is the one the
2393: // distribution walks first and the benevolence it gives the result is kept;
2394: // the template union types keep their dedicated handling.
2395: if (
2396: $typesCount === 2
2397: && self::isPlainOrBenevolentUnion($types[0])
2398: && self::isPlainOrBenevolentUnion($types[1])
2399: ) {
2400: [$a, $b] = $types;
2401: if ($b instanceof BenevolentUnionType && !$a instanceof BenevolentUnionType) {
2402: [$a, $b] = [$b, $a];
2403: }
2404: $finiteIntersection = self::intersectFiniteUnions($a, $b);
2405: if ($finiteIntersection !== null) {
2406: return $a instanceof BenevolentUnionType ? TypeUtils::toBenevolentUnion($finiteIntersection) : $finiteIntersection;
2407: }
2408: }
2409:
2410: $sortTypes = static function (Type $a, Type $b): int {
2411: if (!$a instanceof UnionType || !$b instanceof UnionType) {
2412: return 0;
2413: }
2414:
2415: if ($a instanceof TemplateType) {
2416: return -1;
2417: }
2418: if ($b instanceof TemplateType) {
2419: return 1;
2420: }
2421:
2422: if ($a instanceof BenevolentUnionType) {
2423: return -1;
2424: }
2425: if ($b instanceof BenevolentUnionType) {
2426: return 1;
2427: }
2428:
2429: return 0;
2430: };
2431: if ($unionTypesCount >= 2) {
2432: usort($types, $sortTypes);
2433: }
2434: // transform A & (B | C) to (A & B) | (A & C)
2435: foreach ($types as $i => $type) {
2436: if (!$type instanceof UnionType) {
2437: continue;
2438: }
2439:
2440: $topLevelUnionSubTypes = [];
2441: $innerTypes = $type->getTypes();
2442: $innerUnionTypesCount = 0;
2443: foreach ($innerTypes as $innerType) {
2444: if (!$innerType instanceof UnionType) {
2445: continue;
2446: }
2447: $innerUnionTypesCount++;
2448: if ($innerUnionTypesCount >= 2) {
2449: break;
2450: }
2451: }
2452: if ($innerUnionTypesCount >= 2) {
2453: usort($innerTypes, $sortTypes);
2454: }
2455: $slice1 = array_slice($types, 0, $i);
2456: $slice2 = array_slice($types, $i + 1);
2457: foreach ($innerTypes as $innerUnionSubType) {
2458: $topLevelUnionSubTypes[] = self::intersect(
2459: $innerUnionSubType,
2460: ...$slice1,
2461: ...$slice2,
2462: );
2463: }
2464:
2465: $union = self::union(...$topLevelUnionSubTypes);
2466: if ($union instanceof NeverType) {
2467: return $union;
2468: }
2469:
2470: if ($type instanceof BenevolentUnionType) {
2471: $union = TypeUtils::toBenevolentUnion($union);
2472: }
2473:
2474: if ($type instanceof TemplateUnionType || $type instanceof TemplateBenevolentUnionType) {
2475: $union = TemplateTypeFactory::create(
2476: $type->getScope(),
2477: $type->getName(),
2478: $union,
2479: $type->getVariance(),
2480: $type->getStrategy(),
2481: $type->getDefault(),
2482: );
2483: }
2484:
2485: return $union;
2486: }
2487:
2488: $newTypes = [];
2489: $hasOffsetValueTypeCount = 0;
2490: $typesCount = count($types);
2491: $typesNeedSorting = false;
2492: $hasPropertyType = false;
2493: for ($i = 0; $i < $typesCount; $i++) {
2494: $type = $types[$i];
2495:
2496: if ($type instanceof SubtractableType || $type instanceof ConstantArrayType) {
2497: $typesNeedSorting = true;
2498: }
2499:
2500: if ($type instanceof HasPropertyType) {
2501: $hasPropertyType = true;
2502: }
2503:
2504: if ($type instanceof IntersectionType && !$type instanceof TemplateType) {
2505: // transform A & (B & C) to A & B & C
2506: array_splice($types, $i--, 1, $type->getTypes());
2507: $typesCount = count($types);
2508: } elseif ($type instanceof HasOffsetValueType) {
2509: $hasOffsetValueTypeCount++;
2510: } else {
2511: $newTypes[] = $type;
2512: }
2513: }
2514:
2515: if ($hasOffsetValueTypeCount > 32) {
2516: $newTypes[] = new OversizedArrayType();
2517: $types = $newTypes;
2518: $typesCount = count($types);
2519: }
2520:
2521: if ($typesNeedSorting) {
2522: usort($types, static function (Type $a, Type $b): int {
2523: // move subtractables with subtracts before those without to avoid losing them in the union logic
2524: if ($a instanceof SubtractableType && $a->getSubtractedType() !== null) {
2525: return -1;
2526: }
2527: if ($b instanceof SubtractableType && $b->getSubtractedType() !== null) {
2528: return 1;
2529: }
2530:
2531: if ($a instanceof ConstantArrayType && !$b instanceof ConstantArrayType) {
2532: return -1;
2533: }
2534: if ($b instanceof ConstantArrayType && !$a instanceof ConstantArrayType) {
2535: return 1;
2536: }
2537:
2538: return 0;
2539: });
2540: }
2541:
2542: // Resolve object-shape optional keys that a HasPropertyType asserts are present before the
2543: // reduction loop below. In that loop the generic supertype dedup can drop a HasPropertyType
2544: // as redundant against a dynamic-property class such as stdClass (which reports every
2545: // property as present) before it is ever paired with the object shape. Which of the two
2546: // fires first depends on the member order, so the collapse runs here, where order does not
2547: // change the result of what is meant to be an order-independent value. Gated on the presence
2548: // of a HasPropertyType so the common intersection pays only the flag check set above.
2549: if ($hasPropertyType) {
2550: for ($i = 0; $i < $typesCount; $i++) {
2551: for ($j = $i + 1; $j < $typesCount; $j++) {
2552: if (
2553: $types[$i] instanceof ObjectShapeType
2554: && $types[$j] instanceof HasPropertyType
2555: && !$types[$i]->hasInstanceProperty($types[$j]->getPropertyName())->no()
2556: ) {
2557: $types[$i] = $types[$i]->makePropertyRequired($types[$j]->getPropertyName());
2558: array_splice($types, $j--, 1);
2559: $typesCount--;
2560: continue;
2561: }
2562:
2563: if (
2564: $types[$j] instanceof ObjectShapeType
2565: && $types[$i] instanceof HasPropertyType
2566: && !$types[$j]->hasInstanceProperty($types[$i]->getPropertyName())->no()
2567: ) {
2568: $types[$j] = $types[$j]->makePropertyRequired($types[$i]->getPropertyName());
2569: array_splice($types, $i--, 1);
2570: $typesCount--;
2571: continue 2;
2572: }
2573: }
2574: }
2575: }
2576:
2577: // transform IntegerType & ConstantIntegerType to ConstantIntegerType
2578: // transform Child & Parent to Child
2579: // transform Object & ~null to Object
2580: // transform A & A to A
2581: // transform int[] & string to never
2582: // transform callable & int to never
2583: // transform A & ~A to never
2584: // transform int & string to never
2585: for ($i = 0; $i < $typesCount; $i++) {
2586: for ($j = $i + 1; $j < $typesCount; $j++) {
2587: if ($types[$j] instanceof SubtractableType) {
2588: $typeWithoutSubtractedTypeA = $types[$j]->getTypeWithoutSubtractedType();
2589:
2590: if ($typeWithoutSubtractedTypeA instanceof MixedType && $types[$i] instanceof MixedType) {
2591: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOfMixed($types[$i]);
2592: } else {
2593: $isSuperTypeSubtractableA = $typeWithoutSubtractedTypeA->isSuperTypeOf($types[$i]);
2594: }
2595: if ($isSuperTypeSubtractableA->yes()) {
2596: $types[$i] = self::unionWithSubtractedType($types[$i], $types[$j]->getSubtractedType());
2597: array_splice($types, $j--, 1);
2598: $typesCount--;
2599: continue 1;
2600: }
2601: }
2602:
2603: if ($types[$i] instanceof SubtractableType) {
2604: $typeWithoutSubtractedTypeB = $types[$i]->getTypeWithoutSubtractedType();
2605:
2606: if ($typeWithoutSubtractedTypeB instanceof MixedType && $types[$j] instanceof MixedType) {
2607: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOfMixed($types[$j]);
2608: } else {
2609: $isSuperTypeSubtractableB = $typeWithoutSubtractedTypeB->isSuperTypeOf($types[$j]);
2610: }
2611: if ($isSuperTypeSubtractableB->yes()) {
2612: $types[$j] = self::unionWithSubtractedType($types[$j], $types[$i]->getSubtractedType());
2613: array_splice($types, $i--, 1);
2614: $typesCount--;
2615: continue 2;
2616: }
2617: }
2618:
2619: if ($types[$i] instanceof IntegerRangeType || $types[$i] instanceof FloatRangeType) {
2620: $intersectionType = $types[$i]->tryIntersect($types[$j]);
2621: if ($intersectionType !== null) {
2622: $types[$j] = $intersectionType;
2623: array_splice($types, $i--, 1);
2624: $typesCount--;
2625: continue 2;
2626: }
2627: }
2628:
2629: if ($types[$j] instanceof IterableType) {
2630: $isSuperTypeA = $types[$j]->isSuperTypeOfMixed($types[$i]);
2631: } else {
2632: $isSuperTypeA = $types[$j]->isSuperTypeOf($types[$i]);
2633: }
2634:
2635: if ($isSuperTypeA->yes()) {
2636: array_splice($types, $j--, 1);
2637: $typesCount--;
2638: continue;
2639: }
2640:
2641: if ($types[$i] instanceof IterableType) {
2642: $isSuperTypeB = $types[$i]->isSuperTypeOfMixed($types[$j]);
2643: } else {
2644: $isSuperTypeB = $types[$i]->isSuperTypeOf($types[$j]);
2645: }
2646:
2647: if ($isSuperTypeB->maybe()) {
2648: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetType) {
2649: $types[$i] = $types[$i]->makeOffsetRequired($types[$j]->getOffsetType());
2650: array_splice($types, $j--, 1);
2651: $typesCount--;
2652: continue;
2653: }
2654:
2655: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetType) {
2656: $types[$j] = $types[$j]->makeOffsetRequired($types[$i]->getOffsetType());
2657: array_splice($types, $i--, 1);
2658: $typesCount--;
2659: continue 2;
2660: }
2661:
2662: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof AccessoryArrayListType) {
2663: $types[$i] = $types[$i]->makeList();
2664: array_splice($types, $j--, 1);
2665: $typesCount--;
2666: continue;
2667: }
2668:
2669: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof AccessoryArrayListType) {
2670: $types[$j] = $types[$j]->makeList();
2671: array_splice($types, $i--, 1);
2672: $typesCount--;
2673: continue 2;
2674: }
2675:
2676: if (
2677: $types[$i] instanceof ConstantArrayType
2678: && $types[$j] instanceof NonEmptyArrayType
2679: && (count($types[$i]->getKeyTypes()) === 1 || $types[$i]->isList()->yes())
2680: && $types[$i]->isOptionalKey(0)
2681: && !$types[$i]->isUnsealed()->yes()
2682: ) {
2683: $types[$i] = $types[$i]->makeOffsetRequired($types[$i]->getKeyTypes()[0]);
2684: array_splice($types, $j--, 1);
2685: $typesCount--;
2686: continue;
2687: }
2688:
2689: if (
2690: $types[$j] instanceof ConstantArrayType
2691: && $types[$i] instanceof NonEmptyArrayType
2692: && (count($types[$j]->getKeyTypes()) === 1 || $types[$j]->isList()->yes())
2693: && $types[$j]->isOptionalKey(0)
2694: && !$types[$j]->isUnsealed()->yes()
2695: ) {
2696: $types[$j] = $types[$j]->makeOffsetRequired($types[$j]->getKeyTypes()[0]);
2697: array_splice($types, $i--, 1);
2698: $typesCount--;
2699: continue 2;
2700: }
2701:
2702: if ($types[$i] instanceof ConstantArrayType && $types[$j] instanceof HasOffsetValueType) {
2703: $offsetType = $types[$j]->getOffsetType();
2704: $valueType = $types[$j]->getValueType();
2705: $newValueType = self::intersect($types[$i]->getOffsetValueType($offsetType), $valueType);
2706: if ($newValueType instanceof NeverType) {
2707: return $newValueType;
2708: }
2709: $types[$i] = $types[$i]->setOffsetValueType($offsetType, $newValueType);
2710: array_splice($types, $j--, 1);
2711: $typesCount--;
2712: continue;
2713: }
2714:
2715: if ($types[$j] instanceof ConstantArrayType && $types[$i] instanceof HasOffsetValueType) {
2716: $offsetType = $types[$i]->getOffsetType();
2717: $valueType = $types[$i]->getValueType();
2718: $newValueType = self::intersect($types[$j]->getOffsetValueType($offsetType), $valueType);
2719: if ($newValueType instanceof NeverType) {
2720: return $newValueType;
2721: }
2722:
2723: $types[$j] = $types[$j]->setOffsetValueType($offsetType, $newValueType);
2724: array_splice($types, $i--, 1);
2725: $typesCount--;
2726: continue 2;
2727: }
2728:
2729: if ($types[$i] instanceof OversizedArrayType && $types[$j] instanceof HasOffsetValueType) {
2730: array_splice($types, $j--, 1);
2731: $typesCount--;
2732: continue;
2733: }
2734:
2735: if ($types[$j] instanceof OversizedArrayType && $types[$i] instanceof HasOffsetValueType) {
2736: array_splice($types, $i--, 1);
2737: $typesCount--;
2738: continue 2;
2739: }
2740:
2741: $constArrayIsI = $types[$i] instanceof ConstantArrayType && ($types[$j] instanceof ArrayType || $types[$j] instanceof ConstantArrayType);
2742: $constArrayIsJ = $types[$j] instanceof ConstantArrayType && ($types[$i] instanceof ArrayType || $types[$i] instanceof ConstantArrayType);
2743: if ($constArrayIsI || $constArrayIsJ) {
2744: $constArray = $constArrayIsI ? $types[$i] : $types[$j];
2745: $otherArray = $constArrayIsI ? $types[$j] : $types[$i];
2746:
2747: if (
2748: $otherArray instanceof ConstantArrayType
2749: && !$constArray->isUnsealed()->maybe()
2750: && !$otherArray->isUnsealed()->maybe()
2751: ) {
2752: $merged = self::intersectDefiniteConstantArrays($constArray, $otherArray);
2753: if ($merged instanceof NeverType) {
2754: if ($merged->getReason() === null) {
2755: $reasons = array_merge($isSuperTypeA->getReasons(), $isSuperTypeB->getReasons());
2756: if ($reasons !== []) {
2757: return new NeverType(reason: $reasons[0]);
2758: }
2759: }
2760: return $merged;
2761: }
2762: $newArrayType = $merged;
2763: } else {
2764: $newArray = ConstantArrayTypeBuilder::createEmpty();
2765: // Preserve unsealed extras from the source shape so the
2766: // rebuild doesn't silently turn `array{k: int, ...} & X`
2767: // into a sealed `array{k: int}` — intersect with the other
2768: // side's iterable key/value so the open part keeps both
2769: // sides' refinements.
2770: $constUnsealed = $constArray->getUnsealedTypes();
2771: if ($constUnsealed !== null && $constArray->isUnsealed()->yes()) {
2772: $newUnsealedKey = self::intersect($constUnsealed[0], $otherArray->getIterableKeyType());
2773: $newUnsealedValue = self::intersect($constUnsealed[1], $otherArray->getIterableValueType());
2774: if (!$newUnsealedKey instanceof NeverType && !$newUnsealedValue instanceof NeverType) {
2775: $newArray->makeUnsealed($newUnsealedKey, $newUnsealedValue);
2776: }
2777: }
2778: $valueTypes = $constArray->getValueTypes();
2779: foreach ($constArray->getKeyTypes() as $k => $keyType) {
2780: $hasOffset = $otherArray->hasOffsetValueType($keyType);
2781: if ($hasOffset->no()) {
2782: continue;
2783: }
2784: $newArray->setOffsetValueType(
2785: self::intersect($keyType, $otherArray->getIterableKeyType()),
2786: self::intersect($valueTypes[$k], $otherArray->getOffsetValueType($keyType)),
2787: $constArray->isOptionalKey($k) && !$hasOffset->yes(),
2788: );
2789: }
2790: $newArrayType = $newArray->getArray();
2791: if ($constArray->isList()->yes()) {
2792: $newArrayType = self::intersect($newArrayType, new AccessoryArrayListType());
2793: }
2794: }
2795:
2796: if ($constArrayIsI) {
2797: $types[$i] = $newArrayType;
2798: array_splice($types, $j, 1);
2799: } else {
2800: $types[$j] = $newArrayType;
2801: array_splice($types, $i--, 1);
2802: }
2803: $typesCount--;
2804: continue 2;
2805: }
2806:
2807: if (
2808: ($types[$i] instanceof ArrayType || $types[$i] instanceof ConstantArrayType || $types[$i] instanceof IterableType) &&
2809: ($types[$j] instanceof ArrayType || $types[$j] instanceof ConstantArrayType || $types[$j] instanceof IterableType)
2810: ) {
2811: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getKeyType());
2812: $itemType = self::intersect($types[$i]->getItemType(), $types[$j]->getItemType());
2813: if ($types[$i] instanceof IterableType && $types[$j] instanceof IterableType) {
2814: $types[$j] = new IterableType($keyType, $itemType);
2815: } else {
2816: $types[$j] = new ArrayType($keyType, $itemType);
2817: }
2818: array_splice($types, $i--, 1);
2819: $typesCount--;
2820: continue 2;
2821: }
2822:
2823: if ($types[$i] instanceof GenericClassStringType && $types[$j] instanceof GenericClassStringType) {
2824: $genericType = self::intersect($types[$i]->getGenericType(), $types[$j]->getGenericType());
2825: $types[$i] = new GenericClassStringType($genericType);
2826: array_splice($types, $j--, 1);
2827: $typesCount--;
2828: continue;
2829: }
2830:
2831: if (
2832: $types[$i] instanceof ArrayType
2833: && get_class($types[$i]) === ArrayType::class
2834: && $types[$j] instanceof AccessoryArrayListType
2835: && !$types[$j]->getIterableKeyType()->isSuperTypeOf($types[$i]->getIterableKeyType())->yes()
2836: ) {
2837: $keyType = self::intersect($types[$i]->getIterableKeyType(), $types[$j]->getIterableKeyType());
2838: if ($keyType instanceof NeverType) {
2839: return $keyType;
2840: }
2841: $types[$i] = new ArrayType($keyType, $types[$i]->getItemType());
2842: continue;
2843: }
2844:
2845: continue;
2846: }
2847:
2848: if ($isSuperTypeB->yes()) {
2849: array_splice($types, $i--, 1);
2850: $typesCount--;
2851: continue 2;
2852: }
2853:
2854: if ($isSuperTypeA->no()) {
2855: return new NeverType(reason: $isSuperTypeA->getReasons()[0] ?? null);
2856: }
2857: }
2858: }
2859:
2860: if ($typesCount === 1) {
2861: return $types[0];
2862: }
2863:
2864: $accessoryBaseTypes = [];
2865: foreach ($types as $type) {
2866: if (!$type instanceof AccessoryType) {
2867: $accessoryBaseTypes = null;
2868: break;
2869: }
2870: // Accessory types share their default base type: every string accessory
2871: // returns `string`, hasOffset() and hasOffsetValue() both return
2872: // `array|ArrayAccess`. Adding the same base type again narrows nothing -
2873: // intersection is idempotent - but the intersect() below distributes
2874: // `A & (B | C)` one union at a time, so n copies of `array|ArrayAccess`
2875: // would cost 2^n recursive calls before the duplicates are recognized at
2876: // the leaves. That is why isset() with many offsets used to grow
2877: // exponentially: each offset contributes one hasOffset().
2878: $baseType = $type->getDefaultBaseType();
2879: foreach ($accessoryBaseTypes as $addedBaseType) {
2880: if ($addedBaseType->equals($baseType)) {
2881: continue 2;
2882: }
2883: }
2884: $accessoryBaseTypes[] = $baseType;
2885: }
2886: if ($accessoryBaseTypes !== null) {
2887: // Accessory types never stand alone — supply the base type they refine.
2888: return self::intersect(self::intersect(...$accessoryBaseTypes), ...$types);
2889: }
2890:
2891: return new IntersectionType($types);
2892: }
2893:
2894: private static function intersectDefiniteConstantArrays(ConstantArrayType $a, ConstantArrayType $b): Type
2895: {
2896: $aSealed = $a->isUnsealed()->no();
2897: $bSealed = $b->isUnsealed()->no();
2898: $bothUnsealed = !$aSealed && !$bSealed && $a->getUnsealedTypes() !== null && $b->getUnsealedTypes() !== null;
2899:
2900: $aKeyByValue = [];
2901: foreach ($a->getKeyTypes() as $k => $keyType) {
2902: $aKeyByValue[$keyType->getValue()] = $k;
2903: }
2904: $bKeyByValue = [];
2905: foreach ($b->getKeyTypes() as $k => $keyType) {
2906: $bKeyByValue[$keyType->getValue()] = $k;
2907: }
2908:
2909: if ($aSealed && $bSealed) {
2910: foreach ($aKeyByValue as $keyValue => $k) {
2911: if (!$a->isOptionalKey($k) && !array_key_exists($keyValue, $bKeyByValue)) {
2912: return new NeverType();
2913: }
2914: }
2915: foreach ($bKeyByValue as $keyValue => $k) {
2916: if (!$b->isOptionalKey($k) && !array_key_exists($keyValue, $aKeyByValue)) {
2917: return new NeverType();
2918: }
2919: }
2920: }
2921:
2922: $newArray = ConstantArrayTypeBuilder::createEmpty();
2923:
2924: if ($bothUnsealed) {
2925: $aUnsealed = $a->getUnsealedTypes();
2926: $bUnsealed = $b->getUnsealedTypes();
2927: $unsealedKey = self::intersect($aUnsealed[0], $bUnsealed[0]);
2928: $unsealedValue = self::intersect($aUnsealed[1], $bUnsealed[1]);
2929: if ($unsealedKey instanceof NeverType || $unsealedValue instanceof NeverType) {
2930: return new NeverType();
2931: }
2932: $newArray->makeUnsealed($unsealedKey, $unsealedValue);
2933: } else {
2934: $never = new NeverType(true);
2935: $newArray->makeUnsealed($never, $never);
2936: }
2937:
2938: $resolveOtherValue = static function (ConstantArrayType $other, Type $keyType): ?Type {
2939: if ($other->hasOffsetValueType($keyType)->yes()) {
2940: return $other->getOffsetValueType($keyType);
2941: }
2942: $otherUnsealed = $other->getUnsealedTypes();
2943: if ($otherUnsealed === null) {
2944: return null;
2945: }
2946: [$unsealedKey, $unsealedValue] = $otherUnsealed;
2947: if ($unsealedKey instanceof NeverType && $unsealedKey->isExplicit()) {
2948: return null;
2949: }
2950: if ($unsealedKey->isSuperTypeOf($keyType)->no()) {
2951: return null;
2952: }
2953: return $unsealedValue;
2954: };
2955:
2956: $keysToProcess = [];
2957: foreach ($aKeyByValue as $keyValue => $k) {
2958: $keysToProcess[$keyValue] = [$k, $bKeyByValue[$keyValue] ?? null];
2959: }
2960: foreach ($bKeyByValue as $keyValue => $k) {
2961: if (array_key_exists($keyValue, $keysToProcess)) {
2962: continue;
2963: }
2964:
2965: $keysToProcess[$keyValue] = [null, $k];
2966: }
2967:
2968: foreach ($keysToProcess as [$aIdx, $bIdx]) {
2969: if ($aIdx !== null && $bIdx !== null) {
2970: $keyType = $a->getKeyTypes()[$aIdx];
2971: $value = self::intersect($a->getValueTypes()[$aIdx], $b->getValueTypes()[$bIdx]);
2972: $optional = $a->isOptionalKey($aIdx) && $b->isOptionalKey($bIdx);
2973: } elseif ($aIdx !== null) {
2974: $keyType = $a->getKeyTypes()[$aIdx];
2975: $aValue = $a->getValueTypes()[$aIdx];
2976: $bValue = $resolveOtherValue($b, $keyType);
2977: if ($bValue === null) {
2978: if ($a->isOptionalKey($aIdx)) {
2979: continue;
2980: }
2981: return new NeverType();
2982: }
2983: $value = self::intersect($aValue, $bValue);
2984: $optional = $a->isOptionalKey($aIdx);
2985: } else {
2986: /** @var int<0, max> $bIdx */
2987: $keyType = $b->getKeyTypes()[$bIdx];
2988: $bValue = $b->getValueTypes()[$bIdx];
2989: $aValue = $resolveOtherValue($a, $keyType);
2990: if ($aValue === null) {
2991: if ($b->isOptionalKey($bIdx)) {
2992: continue;
2993: }
2994: return new NeverType();
2995: }
2996: $value = self::intersect($aValue, $bValue);
2997: $optional = $b->isOptionalKey($bIdx);
2998: }
2999:
3000: if ($value instanceof NeverType) {
3001: if ($optional) {
3002: continue;
3003: }
3004: return new NeverType();
3005: }
3006: $newArray->setOffsetValueType($keyType, $value, $optional);
3007: }
3008:
3009: return $newArray->getArray();
3010: }
3011:
3012: /**
3013: * Merge two IntersectionTypes that have the same structure but differ
3014: * in HasOffsetValueType value types (matched by offset key).
3015: *
3016: * E.g. (A & hasOV('k', X)) | (A & hasOV('k', Y)) → (A & hasOV('k', X|Y))
3017: */
3018: private static function mergeIntersectionsForUnion(IntersectionType $a, IntersectionType $b): ?Type
3019: {
3020: $aTypes = $a->getTypes();
3021: $bTypes = $b->getTypes();
3022:
3023: if (count($aTypes) !== count($bTypes)) {
3024: return null;
3025: }
3026:
3027: $mergedTypes = [];
3028: $hasDifference = false;
3029: $bUsed = array_fill(0, count($bTypes), false);
3030:
3031: foreach ($aTypes as $aType) {
3032: $matched = false;
3033: foreach ($bTypes as $bIdx => $bType) {
3034: if ($bUsed[$bIdx]) {
3035: continue;
3036: }
3037:
3038: if ($aType->equals($bType)) {
3039: $mergedTypes[] = $aType;
3040: $bUsed[$bIdx] = true;
3041: $matched = true;
3042: break;
3043: }
3044:
3045: // HasOffsetValueType: merge value types when offset keys match
3046: if ($aType instanceof HasOffsetValueType && $bType instanceof HasOffsetValueType
3047: && $aType->getOffsetType()->equals($bType->getOffsetType())) {
3048: $mergedTypes[] = new HasOffsetValueType(
3049: $aType->getOffsetType(),
3050: self::union($aType->getValueType(), $bType->getValueType()),
3051: );
3052: $hasDifference = true;
3053: $bUsed[$bIdx] = true;
3054: $matched = true;
3055: break;
3056: }
3057:
3058: // HasOffsetType, HasMethodType, HasPropertyType: only equal values match (no merging possible)
3059: }
3060: if (!$matched) {
3061: return null;
3062: }
3063: }
3064:
3065: if (!$hasDifference) {
3066: return null;
3067: }
3068:
3069: $result = $mergedTypes[0];
3070: for ($i = 1, $count = count($mergedTypes); $i < $count; $i++) {
3071: $result = self::intersect($result, $mergedTypes[$i]);
3072: }
3073: return $result;
3074: }
3075:
3076: public static function removeFalsey(Type $type): Type
3077: {
3078: return self::remove($type, StaticTypeFactory::falsey());
3079: }
3080:
3081: public static function removeTruthy(Type $type): Type
3082: {
3083: return self::remove($type, StaticTypeFactory::truthy());
3084: }
3085:
3086: }
3087: