2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
16 #include "hphp/hhbbc/type-system.h"
18 #include <type_traits>
24 #include <folly/Traits.h>
25 #include <folly/Hash.h>
27 #include "hphp/runtime/base/array-init.h"
28 #include "hphp/runtime/base/array-iterator.h"
29 #include "hphp/runtime/base/double-to-int64.h"
30 #include "hphp/runtime/base/repo-auth-type.h"
31 #include "hphp/runtime/base/tv-comparisons.h"
32 #include "hphp/runtime/base/type-structure.h"
33 #include "hphp/runtime/base/type-structure-helpers-defs.h"
34 #include "hphp/runtime/base/vanilla-dict.h"
35 #include "hphp/runtime/base/vanilla-vec.h"
37 #include "hphp/hhbbc/class-util.h"
38 #include "hphp/hhbbc/context.h"
39 #include "hphp/hhbbc/eval-cell.h"
40 #include "hphp/hhbbc/index.h"
41 #include "hphp/hhbbc/type-structure.h"
43 #include "hphp/util/check-size.h"
44 #include "hphp/util/configs/eval.h"
46 namespace HPHP::HHBBC
{
50 #define X(y, ...) const Type T##y{B##y};
51 HHBBC_TYPE_PREDEFINED(X
)
54 const StaticString
s_Awaitable("HH\\Awaitable");
58 //////////////////////////////////////////////////////////////////////
60 // When widening a type, allow no specialized information at a nesting depth
61 // greater than this. This keeps any such types from growing unbounded.
62 constexpr int kTypeWidenMaxDepth
= 8;
64 //////////////////////////////////////////////////////////////////////
66 // Each of these bits corresponds to a particular specialization
67 // type(s). We say these bits "support" the specialization because the
68 // specialization is only allowed if the bit is present. Right now we
69 // only allow specialized data if there's only one support bit (there
70 // can be any non-support bits).
71 constexpr trep kSupportBits
=
72 BStr
| BDbl
| BInt
| BCls
| BObj
| BArrLikeN
| BLazyCls
| BEnumClassLabel
;
73 // These bits don't correspond to any potential specialized data and
74 // can be present freely.
75 constexpr trep kNonSupportBits
= BCell
& ~kSupportBits
;
77 //////////////////////////////////////////////////////////////////////
79 // HHBBC consumes a LOT of memory, and much of it is used by Types.
80 // We keep the type representation compact; don't expand it accidentally.
81 static_assert(CheckSize
<DCls
, 8>(), "");
82 static_assert(CheckSize
<Type
, 16>(), "");
84 //////////////////////////////////////////////////////////////////////
86 template <typename T
, typename
... Args
>
87 void construct(T
& dest
, Args
&&... src
) {
88 new (&dest
) T
{ std::forward
<Args
>(src
)... };
92 void destroy(T
& t
) { t
.~T(); }
94 template <typename T
, typename
... Args
>
95 void construct_inner(T
& dest
, Args
&&... args
) {
97 dest
.emplace(std::forward
<Args
>(args
)...);
100 //////////////////////////////////////////////////////////////////////
102 LegacyMark
legacyMarkFromSArr(SArray a
) {
103 if (a
->isKeysetType()) return LegacyMark::Bottom
;
104 return a
->isLegacyArray() ? LegacyMark::Marked
: LegacyMark::Unmarked
;
107 LegacyMark
unionOf(LegacyMark a
, LegacyMark b
) {
108 if (a
== b
) return a
;
109 if (a
== LegacyMark::Bottom
) return b
;
110 if (b
== LegacyMark::Bottom
) return a
;
111 return LegacyMark::Unknown
;
114 LegacyMark
intersectionOf(LegacyMark a
, LegacyMark b
) {
115 if (a
== b
) return a
;
116 if (a
== LegacyMark::Bottom
) return LegacyMark::Bottom
;
117 if (b
== LegacyMark::Bottom
) return LegacyMark::Bottom
;
118 if (a
== LegacyMark::Unknown
) return b
;
119 if (b
== LegacyMark::Unknown
) return a
;
120 return LegacyMark::Bottom
;
123 bool legacyMarkSubtypeOf(LegacyMark a
, LegacyMark b
) {
124 if (a
== b
) return true;
125 if (a
== LegacyMark::Bottom
) return true;
126 return b
== LegacyMark::Unknown
;
129 bool legacyMarkCouldBe(LegacyMark a
, LegacyMark b
) {
130 if (a
== b
) return true;
131 if (a
== LegacyMark::Bottom
|| b
== LegacyMark::Bottom
) return false;
132 return a
== LegacyMark::Unknown
|| b
== LegacyMark::Unknown
;
135 LegacyMark
project(LegacyMark m
, trep b
) {
136 return couldBe(b
, Type::kLegacyMarkBits
) ? m
: LegacyMark::Bottom
;
139 LegacyMark
legacyMark(LegacyMark m
, trep b
) {
140 if (!couldBe(b
, Type::kLegacyMarkBits
)) return LegacyMark::Unmarked
;
141 assertx(m
!= LegacyMark::Bottom
);
145 //////////////////////////////////////////////////////////////////////
147 // Return true if specializations with the given supports bits must
148 // contain at least uncounted types. That is, they have to be at least
149 // "could be" uncounted. If any of the specific array types in the
150 // trep are entirely static, the specialization must contain uncounted
152 bool mustContainUncounted(trep b
) {
153 if ((b
& BVecN
) == BSVecN
) return true;
154 if ((b
& BDictN
) == BSDictN
) return true;
155 if ((b
& BKeysetN
) == BSKeysetN
) return true;
159 // Return the allowed key types for the given array type. The first
160 // type is the upper bound. All keys in the array must be a subtype of
161 // this. The second type is the lower bound. All keys in the array
162 // must at least *could be* this. In other words, the keys are allowed
163 // to be wider than the lower bound, but not any wider than the upper
165 std::pair
<trep
, trep
> allowedKeyBits(trep b
) {
166 // Ignore anything but the array bits
168 assertx(b
!= BBottom
);
170 auto upper
= BBottom
;
171 auto lower
= BArrKey
;
173 if (couldBe(b
, BVec
)) {
174 // Vecs only ever have int keys
179 if (couldBe(b
, BArrLikeN
)) {
180 if (subtypeOf(b
, BSArrLikeN
)) {
181 // If the array is entirely static, all keys must be static.
185 // Otherwise, the array isn't entirely static, so the upper
186 // bound is not UncArrKey. However, the lower bound might be if
187 // at least one of the specific array types is entirely static.
189 lower
&= mustContainUncounted(b
) ? BUncArrKey
: BArrKey
;
192 return std::make_pair(upper
, lower
);
195 // Same as allowedKeyBits, except for the array values. In some cases
196 // we might know that the array is packed, which further constrains
197 // the values for a Keyset.
198 std::pair
<trep
, trep
> allowedValBits(trep b
, bool packed
) {
199 // Ignore anything but the array bits
201 assertx(b
!= BBottom
);
203 auto upper
= BBottom
;
204 auto lower
= BInitCell
;
206 if (couldBe(b
, BKeysetN
)) {
207 // For a packed keyset, we know the values must be ints. Otherwise
208 // we can infer the staticness of the values if the keyset is
213 } else if (subtypeAmong(b
, BSKeysetN
, BKeysetN
)) {
222 if (couldBe(b
, BArrLikeN
)) {
223 if (subtypeOf(b
, BSArrLikeN
)) {
224 // Same logic as allowedKeyBits()
229 lower
&= mustContainUncounted(b
) ? BInitUnc
: BInitCell
;
232 return std::make_pair(upper
, lower
);
235 //////////////////////////////////////////////////////////////////////
238 * The following functions make DArr* structs out of static arrays, to
239 * simplify implementing some of the type system operations on them.
241 * When they return std::nullopt it is not a conservative thing: it
242 * implies the array is definitely not packed, packedN, struct-like,
243 * etc (we use this to return false in couldBe).
246 Optional
<DArrLikePacked
> toDArrLikePacked(SArray ar
) {
247 assertx(!ar
->empty());
249 std::vector
<Type
> elems
;
250 elems
.reserve(ar
->size());
251 auto idx
= size_t{0};
252 for (ArrayIter
iter(ar
); iter
; ++iter
, ++idx
) {
253 auto const key
= *iter
.first().asTypedValue();
254 if (key
.m_type
!= KindOfInt64
) return std::nullopt
;
255 if (key
.m_data
.num
!= idx
) return std::nullopt
;
256 elems
.emplace_back(from_cell(iter
.secondVal()));
259 return DArrLikePacked
{ std::move(elems
) };
262 Optional
<DArrLikePackedN
> toDArrLikePackedN(SArray ar
) {
263 assertx(!ar
->empty());
266 auto idx
= int64_t{0};
267 for (ArrayIter
iter(ar
); iter
; ++iter
, ++idx
) {
268 auto const key
= *iter
.first().asTypedValue();
269 if (key
.m_type
!= KindOfInt64
) return std::nullopt
;
270 if (key
.m_data
.num
!= idx
) return std::nullopt
;
271 t
|= from_cell(iter
.secondVal());
274 return DArrLikePackedN
{ std::move(t
) };
277 Optional
<DArrLikeMap
> toDArrLikeMap(SArray ar
) {
278 assertx(!ar
->empty());
279 auto map
= MapElems
{};
280 auto idx
= int64_t{0};
282 for (ArrayIter
iter(ar
); iter
; ++iter
) {
283 auto const key
= *iter
.first().asTypedValue();
285 packed
= isIntType(key
.m_type
) && key
.m_data
.num
== idx
;
288 auto const value
= iter
.secondVal();
291 isIntType(key
.m_type
)
292 ? MapElem::IntKey(from_cell(value
))
293 : MapElem::SStrKey(from_cell(value
))
296 if (packed
) return std::nullopt
;
298 return DArrLikeMap
{ std::move(map
), TBottom
, TBottom
};
301 Optional
<DArrLikeMapN
> toDArrLikeMapN(SArray ar
) {
302 assertx(!ar
->empty());
306 auto idx
= int64_t{0};
308 for (ArrayIter
iter(ar
); iter
; ++iter
) {
309 auto const key
= *iter
.first().asTypedValue();
311 v
|= from_cell(iter
.secondVal());
313 packed
= isIntType(key
.m_type
) && key
.m_data
.num
== idx
;
318 if (packed
|| is_scalar_counted(k
)) return std::nullopt
;
319 return DArrLikeMapN
{ std::move(k
), std::move(v
) };
322 // Convert a static array to a Type containing either DArrLikePacked
323 // or DArrLikeMap, whatever is appropriate.
324 Type
toDArrLike(SArray ar
, trep bits
, LegacyMark mark
) {
325 assertx(!ar
->empty());
326 assertx(bits
& BSArrLikeN
);
328 if (auto p
= toDArrLikePacked(ar
)) {
329 return packed_impl(bits
, mark
, std::move(p
->elems
));
332 auto d
= toDArrLikeMap(ar
);
338 std::move(d
->optKey
),
343 //////////////////////////////////////////////////////////////////////
345 std::tuple
<Type
,Type
,int64_t> val_key_values(SArray a
) {
346 assertx(!a
->empty());
350 for (ArrayIter
iter(a
); iter
; ++iter
) {
351 auto const k
= *iter
.first().asTypedValue();
353 val
|= from_cell(iter
.secondVal());
354 if (k
.m_type
!= KindOfInt64
) continue;
355 if (k
.m_data
.num
> lastK
) lastK
= k
.m_data
.num
;
357 return std::make_tuple(std::move(key
), std::move(val
), lastK
);
360 // Calculate the appropriate key type for a DArrLikePacked. Normally
361 // this would just be TInt, but a packed array of length 1 is actually
362 // ival(0). This isn't just an optimization. This distinction is
363 // needed to properly enforce invariants on keysets.
364 Type
packed_key(const DArrLikePacked
& a
) {
365 return a
.elems
.size() == 1 ? ival(0) : TInt
;
368 Type
packed_values(const DArrLikePacked
& a
) {
370 for (auto const& e
: a
.elems
) ret
|= e
;
374 //////////////////////////////////////////////////////////////////////
376 // Convert the key for a given MapElem into its equivalent type.
377 Type
map_key(TypedValue k
, const MapElem
& mapElem
) {
378 assertx(tvIsPlausible(k
));
379 if (isIntType(k
.m_type
)) {
380 assertx(mapElem
.keyStaticness
== TriBool::Yes
);
381 return ival(k
.m_data
.num
);
383 assertx(k
.m_type
== KindOfPersistentString
);
384 switch (mapElem
.keyStaticness
) {
385 case TriBool::Yes
: return sval(k
.m_data
.pstr
);
386 case TriBool::Maybe
: return sval_nonstatic(k
.m_data
.pstr
);
387 case TriBool::No
: return sval_counted(k
.m_data
.pstr
);
389 always_assert(false);
392 // Like map_key but only produces sval_nonstatic() types (this is
393 // needed to model key lookup properly, since it does not care about
395 Type
map_key_nonstatic(TypedValue k
) {
396 assertx(tvIsPlausible(k
));
397 if (isIntType(k
.m_type
)) return ival(k
.m_data
.num
);
398 assertx(k
.m_type
== KindOfPersistentString
);
399 return sval_nonstatic(k
.m_data
.pstr
);
402 std::pair
<Type
,Type
> map_key_values(const DArrLikeMap
& a
) {
403 auto ret
= std::make_pair(a
.optKey
, a
.optVal
);
404 for (auto const& kv
: a
.map
) {
405 ret
.first
|= map_key(kv
.first
, kv
.second
);
406 ret
.second
|= kv
.second
.val
;
411 //////////////////////////////////////////////////////////////////////
413 template <bool context
>
414 bool subtypeCls(const DCls
& a
, const DCls
& b
) {
415 if (context
&& !a
.isCtx() && b
.isCtx()) return false;
417 auto const nonRegA
= a
.containsNonRegular();
418 auto const nonRegB
= b
.containsNonRegular();
420 auto const impl
= [&] (Optional
<res::Class
> exact1
,
421 folly::Range
<const res::Class
*> sub1
,
422 Optional
<res::Class
> exact2
,
423 folly::Range
<const res::Class
*> sub2
) {
425 (!exact1
|| !exact1
->exactSubtypeOfExact(*exact2
, nonRegA
, nonRegB
))) {
430 std::begin(sub2
), std::end(sub2
),
431 [&] (res::Class c2
) {
432 if (exact1
&& exact1
->exactSubtypeOf(c2
, nonRegA
, nonRegB
)) {
436 std::begin(sub1
), std::end(sub1
),
437 [&] (res::Class c1
) {
438 return c1
.subSubtypeOf(c2
, nonRegA
, nonRegB
);
445 auto const toExact
= [] (const DCls
& c
) -> Optional
<res::Class
> {
446 if (c
.isExact()) return c
.cls();
447 if (c
.isIsectAndExact()) return c
.isectAndExact().first
;
451 auto const toSub
= [] (const DCls
& c
) -> folly::Range
<const res::Class
*> {
453 if (c
.isIsect()) return c
.isect();
454 if (c
.isIsectAndExact()) return *c
.isectAndExact().second
;
460 a
.isSub() ? std::array
<res::Class
, 1>{a
.cls()} : toSub(a
),
462 b
.isSub() ? std::array
<res::Class
, 1>{b
.cls()} : toSub(b
)
466 bool couldBeCls(const DCls
& a
, const DCls
& b
) {
467 auto const nonRegA
= a
.containsNonRegular();
468 auto const nonRegB
= b
.containsNonRegular();
470 auto const impl
= [&] (Optional
<res::Class
> exact1
,
471 folly::Range
<const res::Class
*> sub1
,
472 Optional
<res::Class
> exact2
,
473 folly::Range
<const res::Class
*> sub2
) {
475 if (exact2
&& !exact1
->exactCouldBeExact(*exact2
, nonRegA
, nonRegB
)) {
478 auto const all
= std::all_of(
479 std::begin(sub2
), std::end(sub2
),
480 [&] (res::Class c2
) {
481 return exact1
->exactCouldBe(c2
, nonRegA
, nonRegB
);
484 if (!all
) return false;
487 auto const all
= std::all_of(
488 std::begin(sub1
), std::end(sub1
),
489 [&] (res::Class c1
) {
490 if (exact2
&& !exact2
->exactCouldBe(c1
, nonRegB
, nonRegA
)) {
494 std::begin(sub2
), std::end(sub2
),
495 [&] (res::Class c2
) { return c1
.subCouldBe(c2
, nonRegA
, nonRegB
); }
499 if (!all
) return false;
501 if (sub1
.empty() || sub2
.empty()) return true;
502 if (sub1
.size() < 2 && sub2
.size() < 2) return true;
504 return res::Class::couldBeIsect(sub1
, sub2
, nonRegA
, nonRegB
);
507 auto const toExact
= [] (const DCls
& c
) -> Optional
<res::Class
> {
508 if (c
.isExact()) return c
.cls();
509 if (c
.isIsectAndExact()) return c
.isectAndExact().first
;
513 auto const toSub
= [] (const DCls
& c
) -> folly::Range
<const res::Class
*> {
515 if (c
.isIsect()) return c
.isect();
516 if (c
.isIsectAndExact()) return *c
.isectAndExact().second
;
522 a
.isSub() ? std::array
<res::Class
, 1>{a
.cls()} : toSub(a
),
524 b
.isSub() ? std::array
<res::Class
, 1>{b
.cls()} : toSub(b
)
528 //////////////////////////////////////////////////////////////////////
529 template <typename T
>
530 struct DataTagTrait
{};
532 // Represents no specialization. Used in a few places where we need to
533 // dispatch between specializations and no specialization.
534 struct DArrLikeNone
{ trep bits
; };
536 template<> struct DataTagTrait
<DArrLikePacked
> { using tag
= SArray
; };
537 template<> struct DataTagTrait
<DArrLikePackedN
> { using tag
= SArray
; };
538 template<> struct DataTagTrait
<DArrLikeMap
> { using tag
= SArray
; };
539 template<> struct DataTagTrait
<DArrLikeMapN
> { using tag
= SArray
; };
540 template<> struct DataTagTrait
<SArray
> { using tag
= SArray
; };
541 template<> struct DataTagTrait
<DArrLikeNone
> { using tag
= SArray
; };
544 * Helper for dealing with dualDispatchDataFn's---most of them are commutative.
545 * This shuffles values to the right in a canonical order to need less
548 template<class InnerFn
>
549 struct Commute
: InnerFn
{
551 template<class... Args
>
552 explicit Commute(Args
&&... args
) : InnerFn(std::forward
<Args
>(args
)...) {}
554 using result_type
= typename
InnerFn::result_type
;
556 using InnerFn::operator();
558 template<class T1
, class T2
>
559 typename
std::enable_if
<!std::is_same
<T1
, T2
>::value
&&
560 std::is_same
<typename DataTagTrait
<T1
>::tag
,
561 typename DataTagTrait
<T2
>::tag
>::value
,
563 operator()(const T1
& a
, const T2
& b
) const {
564 return InnerFn::operator()(b
, a
);
569 struct DualDispatchCouldBeImpl
{
570 static constexpr bool disjoint
= false;
571 using result_type
= bool;
573 static bool couldBePacked(const DArrLikePacked
& a
, const DArrLikePacked
& b
) {
574 auto const asz
= a
.elems
.size();
575 auto const bsz
= b
.elems
.size();
576 if (asz
!= bsz
) return false;
577 for (auto i
= size_t{0}; i
< asz
; ++i
) {
578 if (!a
.elems
[i
].couldBe(b
.elems
[i
])) return false;
583 static bool couldBeMap(const DArrLikeMap
& a
, const DArrLikeMap
& b
) {
584 // If A and B don't have optional elements, their values are
585 // completely disjoint if the number of keys are different.
586 if (!a
.hasOptElements() && !b
.hasOptElements() &&
587 a
.map
.size() != b
.map
.size()) {
591 // Check the common prefix of A and B. The keys must be the same and
592 // there must be an intersection among the values.
593 auto aIt
= begin(a
.map
);
594 auto bIt
= begin(b
.map
);
595 while (aIt
!= end(a
.map
) && bIt
!= end(b
.map
)) {
596 if (!tvSame(aIt
->first
, bIt
->first
)) return false;
597 if (aIt
->second
.keyStaticness
!= bIt
->second
.keyStaticness
&&
598 aIt
->second
.keyStaticness
!= TriBool::Maybe
&&
599 bIt
->second
.keyStaticness
!= TriBool::Maybe
) {
602 if (!aIt
->second
.val
.couldBe(bIt
->second
.val
)) return false;
607 // Process the remaining known keys (only A or B will be
608 // processed). The known keys must have an intersection with the
609 // other map's optional values (if any).
610 while (aIt
!= end(a
.map
)) {
611 if (!map_key(aIt
->first
, aIt
->second
).couldBe(b
.optKey
)) {
614 if (!aIt
->second
.val
.couldBe(b
.optVal
)) return false;
618 while (bIt
!= end(b
.map
)) {
619 if (!map_key(bIt
->first
, bIt
->second
).couldBe(a
.optKey
)) {
622 if (!bIt
->second
.val
.couldBe(a
.optVal
)) return false;
629 explicit DualDispatchCouldBeImpl(trep b
) : isect
{b
} {}
631 bool operator()() const { return false; }
633 bool operator()(SArray a
, SArray b
) const {
636 bool operator()(const DArrLikePacked
& a
, const DArrLikePacked
& b
) const {
637 return couldBePacked(a
, b
);
639 bool operator()(const DArrLikePackedN
& a
, const DArrLikePackedN
& b
) const {
640 return a
.type
.couldBe(b
.type
);
642 bool operator()(const DArrLikeMap
& a
, const DArrLikeMap
& b
) const {
643 return couldBeMap(a
, b
);
645 bool operator()(const DArrLikeMapN
& a
, const DArrLikeMapN
& b
) const {
646 if (!a
.key
.couldBe(b
.key
) || !a
.val
.couldBe(b
.val
)) return false;
647 // Keyset specializations can only be either other if the key ==
648 // val invariant holds after intersecting them.
649 if (!subtypeAmong(isect
, BKeysetN
, BArrLikeN
)) return true;
650 if (a
.key
== a
.val
&& b
.key
== b
.val
) return true;
651 return intersection_of(a
.key
, b
.key
).couldBe(intersection_of(a
.val
, b
.val
));
654 bool operator()(const DArrLikePacked
& a
, SArray b
) const {
655 if (a
.elems
.size() != b
->size()) return false;
656 auto const p
= toDArrLikePacked(b
);
657 return p
&& couldBePacked(a
, *p
);
660 bool operator()(const DArrLikeMap
& a
, SArray b
) const {
661 // If A doesn't have optional elements, there's no intersection if
662 // they have a different number of known keys.
663 if (!a
.hasOptElements() && a
.map
.size() != b
->size()) return false;
664 auto const m
= toDArrLikeMap(b
);
665 return m
&& couldBeMap(a
, *m
);
668 bool operator()(const DArrLikePackedN
& a
, SArray b
) const {
669 auto const p
= toDArrLikePackedN(b
);
670 return p
&& a
.type
.couldBe(p
->type
);
673 bool operator()(const DArrLikeMapN
& a
, SArray b
) const {
674 assertx(!b
->empty());
678 [&] (TypedValue k
, TypedValue v
) {
679 bad
|= !(a
.key
.couldBe(from_cell(k
)) && a
.val
.couldBe(from_cell(v
)));
686 bool operator()(const DArrLikePacked
& a
, const DArrLikePackedN
& b
) const {
687 for (auto const& t
: a
.elems
) {
688 if (!t
.couldBe(b
.type
)) return false;
693 bool operator()(const DArrLikePackedN
& a
, const DArrLikeMapN
& b
) const {
694 if (!b
.key
.couldBe(BInt
) || !a
.type
.couldBe(b
.val
)) return false;
695 if (!subtypeAmong(isect
, BKeysetN
, BArrLikeN
)) return true;
696 if (a
.type
== TInt
&& b
.key
== b
.val
) return true;
697 return intersection_of(b
.key
, TInt
).couldBe(intersection_of(a
.type
, b
.val
));
700 bool operator()(const DArrLikeMap
& a
, const DArrLikeMapN
& b
) const {
701 for (auto const& kv
: a
.map
) {
702 if (!map_key(kv
.first
, kv
.second
).couldBe(b
.key
)) return false;
703 if (!kv
.second
.val
.couldBe(b
.val
)) return false;
705 // We can ignore optional elements here. If the values
706 // corresponding to just the known keys already intersect with B,
707 // then we have an intersection so we're done.
711 bool operator()(const DArrLikePacked
&, const DArrLikeMap
&) const {
712 // Map does not contain any packed arrays.
715 bool operator()(const DArrLikePacked
& a
, const DArrLikeMapN
& b
) const {
716 auto const packedKey
= packed_key(a
);
717 if (!b
.key
.couldBe(packedKey
)) return false;
718 for (auto const& t
: a
.elems
) {
719 if (!t
.couldBe(b
.val
)) return false;
721 if (!subtypeAmong(isect
, BKeysetN
, BArrLikeN
)) return true;
722 auto const vals
= packed_values(a
);
723 if (vals
== packedKey
&& b
.key
== b
.val
) return true;
725 intersection_of(b
.key
, packedKey
).couldBe(intersection_of(vals
, b
.val
));
727 bool operator()(const DArrLikePackedN
&, const DArrLikeMap
&) const {
728 // Map does not contain any packed arrays.
732 // Operators on DArrLikeNone. These must check if the
733 // specialization's key and value are "allowed" for None's trep.
735 bool operator()(const DArrLikeNone
&, SArray
) const {
736 // None contains all possible arrays, so it always could be.
739 bool operator()(const DArrLikeNone
& a
, const DArrLikePackedN
& b
) const {
740 auto const key
= allowedKeyBits(a
.bits
).first
;
741 if (!couldBe(key
, BInt
)) return false;
742 auto const val
= allowedValBits(a
.bits
, true).first
;
743 return b
.type
.couldBe(val
);
745 bool operator()(const DArrLikeNone
& a
, const DArrLikePacked
& b
) const {
746 auto const key
= allowedKeyBits(a
.bits
).first
;
747 if (!couldBe(key
, BInt
)) return false;
748 auto const val
= allowedValBits(a
.bits
, true).first
;
749 for (auto const& t
: b
.elems
) {
750 if (!t
.couldBe(val
)) return false;
754 bool operator()(const DArrLikeNone
& a
, const DArrLikeMapN
& b
) const {
755 auto const key
= allowedKeyBits(a
.bits
).first
;
756 auto const val
= allowedValBits(a
.bits
, false).first
;
757 return b
.key
.couldBe(key
) && b
.val
.couldBe(val
);
759 bool operator()(const DArrLikeNone
& a
, const DArrLikeMap
& b
) const {
760 // Vec cannot have a Map specialization.
761 if (subtypeAmong(isect
, BVecN
, BArrLikeN
)) return false;
762 auto const key
= allowedKeyBits(a
.bits
).first
;
763 auto const val
= allowedValBits(a
.bits
, false).first
;
764 for (auto const& kv
: b
.map
) {
765 if (!map_key(kv
.first
, kv
.second
).couldBe(key
)) return false;
766 if (!kv
.second
.val
.couldBe(val
)) return false;
775 // pre: neither type is a subtype of the other (except for the
776 // DArrLikeNone variants)
777 struct DualDispatchIntersectionImpl
{
778 static constexpr bool disjoint
= false;
779 using result_type
= Type
;
781 DualDispatchIntersectionImpl(trep b
, LegacyMark m
)
782 : isect
{b
}, mark
{m
} {}
784 // For any specific array type which is entirely static, remove it.
785 static trep
remove_single_static_bits(trep b
) {
786 if ((b
& BVecN
) == BSVecN
) b
&= ~BSVecN
;
787 if ((b
& BDictN
) == BSDictN
) b
&= ~BSDictN
;
788 if ((b
& BKeysetN
) == BSKeysetN
) b
&= ~BSKeysetN
;
792 Type
operator()() const { not_reached(); }
794 static MapElem
intersect_map_elem(MapElem e1
, MapElem e2
) {
796 if (e1
.keyStaticness
!= e2
.keyStaticness
) {
797 if (e1
.keyStaticness
== TriBool::Maybe
) {
798 staticness
= e2
.keyStaticness
;
799 } else if (e2
.keyStaticness
== TriBool::Maybe
) {
800 staticness
= e1
.keyStaticness
;
802 return MapElem
{ TBottom
, TriBool::No
};
805 staticness
= e1
.keyStaticness
;
809 intersection_of(std::move(e1
.val
), std::move(e2
.val
)),
814 static MapElem
intersect_map_elem(MapElem e
, Type key
, Type val
) {
815 auto staticness
= e
.keyStaticness
;
816 if (!key
.couldBe(BCounted
)) {
817 if (e
.keyStaticness
== TriBool::No
) {
818 return MapElem
{ TBottom
, TriBool::No
};
820 if (e
.keyStaticness
== TriBool::Maybe
) staticness
= TriBool::Yes
;
822 if (!key
.couldBe(BUnc
)) {
823 if (e
.keyStaticness
== TriBool::Yes
) {
824 return MapElem
{ TBottom
, TriBool::No
};
826 if (e
.keyStaticness
== TriBool::Maybe
) staticness
= TriBool::No
;
830 intersection_of(std::move(e
.val
), std::move(val
)),
836 * When intersecting two array types, we may have to change the
837 * types in the specialization to match. For example, if the
838 * intersection produces a trep of BVec, we cannot have non-int
839 * keys. Likewise, if the intersection produces a static array type
840 * trep, we cannot have counted types in the
841 * specialization. However, the key/value types in the
842 * specialization can also cause us to remove array types from the
845 * Namely, conflicts due to the allowed upper bound (see
846 * allowedKeyBits()/allowedValBits()) are handled by modifying the
847 * specialization's types. Conflicts due to the allowed lower bound
848 * are handled by removing violating trep bits.
850 * This makes the interactions tricky to model, since changing the
851 * trep bits might change what is allowed in the
852 * specialization. When we perform the intersection, we proceed as
853 * normal. If we need to modify the trep bits, we do so, but then
854 * restart the intersection from the beginning (with the new trep
855 * bits). This is a rare operation so there's no real cost.
857 * All the intersection helper functions take the current trep by
858 * ref and return an optional Type. If it returns std::nullopt, the
859 * trep is assumed to be modified and the process
860 * restarts. Otherwise the operation is assumed to have finished
861 * successfully. This is guaranteed to terminate because we only
862 * return std::nullopt when we've removed bits from the trep (and
863 * thus we'll eventually run out of bits to remove).
866 template <typename F
>
867 Optional
<Type
> intersect_packed(trep
& bits
,
868 std::vector
<Type
> elems
,
870 auto const valBits
= allowedValBits(bits
, true);
873 for (auto& e
: elems
) {
875 if (e
.is(BBottom
)) return TBottom
;
877 if (!e
.subtypeOf(valBits
.first
)) {
878 e
= intersection_of(std::move(e
), Type
{valBits
.first
});
879 if (e
.is(BBottom
)) return TBottom
;
882 if (subtypeAmong(bits
, BKeysetN
, BArrLikeN
)) {
884 if (!e
.subtypeOf(iv
)) {
885 e
= intersection_of(std::move(e
), std::move(iv
));
887 if (e
.is(BBottom
)) return TBottom
;
890 if (!e
.couldBe(valBits
.second
)) {
891 if (couldBe(bits
, BKeysetN
) && !e
.couldBe(BInt
)) {
893 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
897 if (mustContainUncounted(bits
) && !e
.couldBe(BUnc
)) {
898 bits
= remove_single_static_bits(bits
);
899 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
904 if (couldBe(bits
, BKeysetN
) && !e
.couldBe(ival(i
))) {
906 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
913 return packed_impl(bits
, mark
, std::move(elems
));
916 Optional
<Type
> handle_packedn(trep
& bits
, Type val
) const {
917 if (val
.is(BBottom
)) return TBottom
;
919 auto const valBits
= allowedValBits(bits
, true);
920 if (!val
.subtypeOf(valBits
.first
)) {
921 val
= intersection_of(std::move(val
), Type
{valBits
.first
});
922 if (val
.is(BBottom
)) return TBottom
;
925 if (subtypeAmong(bits
, BKeysetN
, BArrLikeN
)) {
926 if (!val
.subtypeOf(BInt
)) {
927 val
= intersection_of(std::move(val
), TInt
);
928 if (val
.is(BBottom
)) return TBottom
;
930 if (is_specialized_int(val
)) {
931 if (ival_of(val
) == 0) {
932 return packed_impl(bits
, mark
, std::vector
<Type
>{std::move(val
)});
938 if (!val
.couldBe(valBits
.second
)) {
939 if (couldBe(bits
, BKeysetN
) && !val
.couldBe(BInt
)) {
941 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
945 if (mustContainUncounted(bits
) && !val
.couldBe(BUnc
)) {
946 bits
= remove_single_static_bits(bits
);
947 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
952 if (couldBe(bits
, BKeysetN
) &&
953 is_specialized_int(val
) &&
956 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
960 return packedn_impl(bits
, mark
, std::move(val
));
963 Optional
<Type
> handle_mapn(trep
& bits
, Type key
, Type val
) const {
964 if (key
.is(BBottom
) || val
.is(BBottom
)) return TBottom
;
966 // Special case: A Vec on its own cannot have a Map specialization
967 // (it can unioned with other array types). If the intersection has
968 // produced one, turn the specialization into a PackedN.
969 if (subtypeAmong(bits
, BVecN
, BArrLikeN
)) {
970 if (!key
.couldBe(BInt
)) return TBottom
;
971 return handle_packedn(bits
, std::move(val
));
974 auto const keyBits
= allowedKeyBits(bits
);
975 auto const valBits
= allowedValBits(bits
, false);
977 if (!key
.subtypeOf(keyBits
.first
)) {
978 key
= intersection_of(std::move(key
), Type
{keyBits
.first
});
979 if (key
.is(BBottom
)) return TBottom
;
981 if (!val
.subtypeOf(valBits
.first
)) {
982 val
= intersection_of(std::move(val
), Type
{valBits
.first
});
983 if (val
.is(BBottom
)) return TBottom
;
986 if (subtypeAmong(bits
, BKeysetN
, BArrLikeN
) && key
!= val
) {
987 auto isect
= intersection_of(key
, val
);
988 if (isect
.is(BBottom
)) return TBottom
;
989 if (!key
.subtypeOf(isect
)) key
= isect
;
990 if (!val
.subtypeOf(isect
)) val
= isect
;
993 if (!key
.couldBe(keyBits
.second
)) {
994 if (couldBe(bits
, BVecN
) && !key
.couldBe(BInt
)) {
996 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1000 if (couldBe(bits
, BKeysetN
)) {
1002 subtypeAmong(bits
, BSKeysetN
, BKeysetN
) ? BUncArrKey
: BArrKey
;
1003 if (!key
.couldBe(arrkey
)) {
1005 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1006 return std::nullopt
;
1010 if (mustContainUncounted(bits
) && !key
.couldBe(BUnc
)) {
1011 bits
= remove_single_static_bits(bits
);
1012 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1013 return std::nullopt
;
1017 if (!val
.couldBe(valBits
.second
)) {
1018 if (couldBe(bits
, BKeysetN
)) {
1020 subtypeAmong(bits
, BSKeysetN
, BKeysetN
) ? BUncArrKey
: BArrKey
;
1021 if (!val
.couldBe(arrkey
)) {
1023 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1024 return std::nullopt
;
1028 if (mustContainUncounted(bits
) && !val
.couldBe(BUnc
)) {
1029 bits
= remove_single_static_bits(bits
);
1030 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1031 return std::nullopt
;
1035 if (couldBe(bits
, BKeysetN
) && !key
.couldBe(val
)) {
1037 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1038 return std::nullopt
;
1041 return mapn_impl(bits
, mark
, std::move(key
), std::move(val
));
1044 Optional
<Type
> handle_map(trep
& bits
,
1047 Type optVal
) const {
1048 auto const valBits
= allowedValBits(bits
, false);
1049 auto const keyBits
= allowedKeyBits(bits
);
1051 for (auto it
= elems
.begin(); it
!= elems
.end(); ++it
) {
1053 assertx(tvIsPlausible(kv
.first
));
1055 if (subtypeOf(keyBits
.first
, BUncArrKey
)) {
1056 if (kv
.second
.keyStaticness
== TriBool::No
) return TBottom
;
1057 if (kv
.second
.keyStaticness
== TriBool::Maybe
) {
1058 elems
.update(it
, kv
.second
.withStaticness(TriBool::Yes
));
1062 if (!kv
.second
.val
.subtypeOf(valBits
.first
)) {
1063 auto val
= intersection_of(kv
.second
.val
, Type
{valBits
.first
});
1064 if (val
.is(BBottom
)) return TBottom
;
1065 if (!kv
.second
.val
.subtypeOf(val
)) {
1066 elems
.update(it
, kv
.second
.withType(std::move(val
)));
1069 if (subtypeAmong(bits
, BKeysetN
, BArrLikeN
)) {
1070 auto key
= map_key(kv
.first
, kv
.second
);
1071 if (key
!= kv
.second
.val
) {
1072 auto val
= intersection_of(std::move(key
), kv
.second
.val
);
1073 if (val
.is(BBottom
)) return TBottom
;
1074 elems
.update(it
, MapElem::KeyFromType(val
, val
));
1078 if (mustContainUncounted(bits
) &&
1079 kv
.second
.keyStaticness
== TriBool::No
) {
1080 bits
= remove_single_static_bits(bits
);
1081 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1082 return std::nullopt
;
1085 if (!kv
.second
.val
.couldBe(valBits
.second
)) {
1086 if (couldBe(bits
, BKeysetN
)) {
1088 subtypeAmong(bits
, BSKeysetN
, BKeysetN
) ? BUncArrKey
: BArrKey
;
1089 if (!kv
.second
.val
.couldBe(val
)) {
1091 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1092 return std::nullopt
;
1095 if (mustContainUncounted(bits
) && !kv
.second
.val
.couldBe(BUnc
)) {
1096 bits
= remove_single_static_bits(bits
);
1097 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1098 return std::nullopt
;
1101 if (couldBe(bits
, BKeysetN
) &&
1102 !kv
.second
.val
.couldBe(map_key(kv
.first
, kv
.second
))) {
1104 if (!couldBe(bits
, BArrLikeN
)) return TBottom
;
1105 return std::nullopt
;
1109 if (!optKey
.is(BBottom
)) {
1110 assertx(!optVal
.is(BBottom
));
1112 if (!optVal
.subtypeOf(valBits
.first
)) {
1113 optVal
= intersection_of(std::move(optVal
), Type
{valBits
.first
});
1116 if (!optKey
.subtypeOf(keyBits
.first
)) {
1117 optKey
= intersection_of(std::move(optKey
), Type
{keyBits
.first
});
1120 if (optKey
.is(BBottom
) || optVal
.is(BBottom
)) {
1125 if (subtypeAmong(bits
, BKeysetN
, BArrLikeN
) && optKey
!= optVal
) {
1126 auto isect
= intersection_of(optKey
, optVal
);
1128 if (is_specialized_int(isect
)) {
1129 auto const tv
= make_tv
<KindOfInt64
>(ival_of(isect
));
1130 if (elems
.find(tv
) != elems
.end()) {
1131 isect
= remove_int(std::move(isect
));
1133 } else if (is_specialized_string(isect
)) {
1134 auto const tv
= make_tv
<KindOfPersistentString
>(sval_of(isect
));
1135 if (elems
.find(tv
) != elems
.end()) {
1136 isect
= remove_string(std::move(isect
));
1140 if (!optKey
.subtypeOf(isect
)) optKey
= isect
;
1141 if (!optVal
.subtypeOf(isect
)) optVal
= isect
;
1154 // Helper function to deal with the restart logic. Keep looping,
1155 // calling f with the bits until it returns something.
1156 template <typename F
> Type
handle(F f
) const {
1159 auto const DEBUG_ONLY origBits
= bits
;
1160 auto const result
= f(bits
);
1161 if (result
) return *result
;
1162 assertx(couldBe(bits
, BArrLikeN
));
1163 assertx(bits
!= origBits
&& subtypeOf(bits
, origBits
));
1167 // The SArray is known to not be a subtype, so the intersection must be empty
1168 Type
operator()(const DArrLikePacked
&, const SArray
) const {
1171 Type
operator()(const DArrLikePackedN
&, const SArray
) const {
1174 Type
operator()(const DArrLikeMapN
&, const SArray
) const {
1177 Type
operator()(const DArrLikeMap
&, const SArray
) const {
1180 Type
operator()(const SArray
, const SArray
) const {
1184 Type
operator()(const DArrLikePacked
& a
, const DArrLikePacked
& b
) const {
1185 if (a
.elems
.size() != b
.elems
.size()) return TBottom
;
1189 return intersect_packed(bits
, a
.elems
, [&] { return b
.elems
[i
++]; });
1193 Type
operator()(const DArrLikePacked
& a
, const DArrLikePackedN
& b
) const {
1196 return intersect_packed(bits
, a
.elems
, [&] { return b
.type
; });
1200 Type
operator()(const DArrLikePacked
& a
, const DArrLikeMapN
& b
) const {
1201 if (!b
.key
.couldBe(packed_key(a
))) return TBottom
;
1204 return intersect_packed(bits
, a
.elems
, [&] { return b
.val
; });
1208 Type
operator()(const DArrLikePacked
&, const DArrLikeMap
&) const {
1209 // We don't allow DArrLikeMaps which are packed
1213 Type
operator()(const DArrLikePackedN
& a
, const DArrLikePackedN
& b
) const {
1216 return handle_packedn(bits
, intersection_of(a
.type
, b
.type
));
1220 Type
operator()(const DArrLikePackedN
& a
, const DArrLikeMapN
& b
) const {
1221 if (!b
.key
.couldBe(BInt
)) return TBottom
;
1224 return handle_packedn(bits
, intersection_of(b
.val
, a
.type
));
1228 Type
operator()(const DArrLikePackedN
&, const DArrLikeMap
&) const {
1232 Type
operator()(const DArrLikeMapN
& a
, const DArrLikeMapN
& b
) const {
1237 intersection_of(a
.key
, b
.key
),
1238 intersection_of(a
.val
, b
.val
)
1243 Type
operator()(const DArrLikeMapN
& a
, const DArrLikeMap
& b
) const {
1245 [&] (trep
& bits
) -> Optional
<Type
> {
1246 auto map
= MapElems
{};
1248 for (auto const& kv
: b
.map
) {
1249 if (!map_key(kv
.first
, kv
.second
).couldBe(a
.key
)) return TBottom
;
1250 auto elem
= intersect_map_elem(kv
.second
, a
.key
, a
.val
);
1251 if (elem
.val
.is(BBottom
)) return TBottom
;
1252 map
.emplace_back(kv
.first
, std::move(elem
));
1255 auto optKey
= TBottom
;
1256 auto optVal
= TBottom
;
1257 if (b
.hasOptElements()) {
1258 optKey
= intersection_of(b
.optKey
, a
.key
);
1259 optVal
= intersection_of(b
.optVal
, a
.val
);
1260 if (optKey
.is(BBottom
) || optVal
.is(BBottom
)) {
1267 bits
, std::move(map
), std::move(optKey
), std::move(optVal
)
1273 Type
operator()(const DArrLikeMap
& a
, const DArrLikeMap
& b
) const {
1274 // Two maps without optional elements have no values in common if
1275 // they have different sets of keys.
1276 if (!a
.hasOptElements() && !b
.hasOptElements() &&
1277 a
.map
.size() != b
.map
.size()) {
1282 [&] (trep
& bits
) -> Optional
<Type
> {
1283 auto map
= MapElems
{};
1285 auto aIt
= begin(a
.map
);
1286 auto bIt
= begin(b
.map
);
1288 // Intersect the common known keys
1289 while (aIt
!= end(a
.map
) && bIt
!= end(b
.map
)) {
1290 if (!tvSame(aIt
->first
, bIt
->first
)) return TBottom
;
1291 auto elem
= intersect_map_elem(aIt
->second
, bIt
->second
);
1292 if (elem
.val
.is(BBottom
)) return TBottom
;
1293 map
.emplace_back(aIt
->first
, std::move(elem
));
1298 // Any remaining known keys are only in A, or in B. Intersect them
1299 // with the optional elements in the other map. If the other map
1300 // doesn't have optional elements, the intersection will be
1302 while (aIt
!= end(a
.map
)) {
1303 if (!map_key(aIt
->first
, aIt
->second
).couldBe(b
.optKey
)) {
1307 intersect_map_elem(aIt
->second
, b
.optKey
, b
.optVal
);
1308 if (elem
.val
.is(BBottom
)) return TBottom
;
1309 map
.emplace_back(aIt
->first
, std::move(elem
));
1313 while (bIt
!= end(b
.map
)) {
1314 if (!map_key(bIt
->first
, bIt
->second
).couldBe(a
.optKey
)) {
1318 intersect_map_elem(bIt
->second
, a
.optKey
, a
.optVal
);
1319 if (elem
.val
.is(BBottom
)) return TBottom
;
1320 map
.emplace_back(bIt
->first
, std::move(elem
));
1324 auto optKey
= TBottom
;
1325 auto optVal
= TBottom
;
1326 if (a
.hasOptElements() && b
.hasOptElements()) {
1327 optKey
= intersection_of(a
.optKey
, b
.optKey
);
1328 optVal
= intersection_of(a
.optVal
, b
.optVal
);
1329 if (optKey
.is(BBottom
) || optVal
.is(BBottom
)) {
1336 bits
, std::move(map
), std::move(optKey
), std::move(optVal
)
1342 Type
operator()(const DArrLikeNone
&, SArray
) const {
1343 // We know one is not a subtype of the other, so we shouldn't get
1347 Type
operator()(const DArrLikeNone
&, const DArrLikePackedN
& b
) const {
1349 [&] (trep
& bits
) -> Optional
<Type
> {
1350 auto const keys
= allowedKeyBits(bits
).first
;
1351 if (!couldBe(keys
, BInt
)) return TBottom
;
1352 auto const vals
= allowedValBits(bits
, true).first
;
1353 return handle_packedn(bits
, intersection_of(Type
{vals
}, b
.type
));
1357 Type
operator()(const DArrLikeNone
&, const DArrLikePacked
& b
) const {
1359 [&] (trep
& bits
) -> Optional
<Type
> {
1360 auto const keys
= allowedKeyBits(bits
).first
;
1361 if (!couldBe(keys
, BInt
)) return TBottom
;
1362 auto const vals
= Type
{allowedValBits(bits
, true).first
};
1363 return intersect_packed(bits
, b
.elems
, [&] { return vals
; });
1367 Type
operator()(const DArrLikeNone
&, const DArrLikeMapN
& b
) const {
1370 auto const keys
= allowedKeyBits(bits
).first
;
1371 auto const vals
= allowedValBits(bits
, false).first
;
1374 intersection_of(b
.key
, Type
{keys
}),
1375 intersection_of(b
.val
, Type
{vals
})
1380 Type
operator()(const DArrLikeNone
&, const DArrLikeMap
& b
) const {
1382 [&] (trep
& bits
) -> Optional
<Type
> {
1383 auto const keys
= Type
{allowedKeyBits(bits
).first
};
1384 auto const vals
= Type
{allowedValBits(bits
, false).first
};
1386 auto map
= MapElems
{};
1387 for (auto const& kv
: b
.map
) {
1388 if (!map_key(kv
.first
, kv
.second
).couldBe(keys
)) return TBottom
;
1389 auto elem
= intersect_map_elem(kv
.second
, keys
, vals
);
1390 if (elem
.val
.is(BBottom
)) return TBottom
;
1391 map
.emplace_back(kv
.first
, std::move(elem
));
1394 auto optKey
= TBottom
;
1395 auto optVal
= TBottom
;
1396 if (b
.hasOptElements()) {
1397 optKey
= intersection_of(b
.optKey
, keys
);
1398 optVal
= intersection_of(b
.optVal
, vals
);
1399 if (optKey
.is(BBottom
) || optVal
.is(BBottom
)) {
1406 bits
, std::move(map
), std::move(optKey
), std::move(optVal
)
1417 struct DualDispatchUnionImpl
{
1418 static constexpr bool disjoint
= false;
1419 using result_type
= Type
;
1421 DualDispatchUnionImpl(trep combined
, LegacyMark m
)
1422 : combined
{combined
}, mark
{m
} {}
1424 static MapElem
union_map_elem(MapElem e1
, MapElem e2
) {
1426 union_of(std::move(e1
.val
), std::move(e2
.val
)),
1427 e1
.keyStaticness
| e2
.keyStaticness
1431 Type
operator()() const { not_reached(); }
1433 Type
operator()(const DArrLikePacked
& a
, const DArrLikePacked
& b
) const {
1434 if (a
.elems
.size() != b
.elems
.size()) {
1435 return packedn_impl(
1436 combined
, mark
, union_of(packed_values(a
), packed_values(b
))
1440 for (auto i
= size_t{0}; i
< a
.elems
.size(); ++i
) {
1441 ret
[i
] |= b
.elems
[i
];
1443 return packed_impl(combined
, mark
, std::move(ret
));
1446 Type
operator()(const DArrLikePackedN
& a
, const DArrLikePackedN
& b
) const {
1447 return packedn_impl(combined
, mark
, union_of(a
.type
, b
.type
));
1450 Type
operator()(const DArrLikePacked
& a
, const DArrLikePackedN
& b
) const {
1451 return (*this)(DArrLikePackedN
{ packed_values(a
) }, b
);
1454 Type
operator()(const DArrLikeMap
& a
, const DArrLikeMap
& b
) const {
1455 auto map
= MapElems
{};
1457 // Keep the common prefix of known keys in both A and B.
1458 auto aIt
= begin(a
.map
);
1459 auto bIt
= begin(b
.map
);
1460 while (aIt
!= end(a
.map
) && bIt
!= end(b
.map
)) {
1461 if (!tvSame(aIt
->first
, bIt
->first
)) break;
1462 map
.emplace_back(aIt
->first
, union_map_elem(aIt
->second
, bIt
->second
));
1467 // If there's no common prefix, fall back to MapN.
1469 auto mkva
= map_key_values(a
);
1470 auto mkvb
= map_key_values(b
);
1474 union_of(std::move(mkva
.first
), std::move(mkvb
.first
)),
1475 union_of(std::move(mkva
.second
), std::move(mkvb
.second
))
1479 // Any non-common known keys will be combined into the optional
1481 auto optKey
= union_of(a
.optKey
, b
.optKey
);
1482 auto optVal
= union_of(a
.optVal
, b
.optVal
);
1484 while (aIt
!= end(a
.map
)) {
1485 optKey
|= map_key(aIt
->first
, aIt
->second
);
1486 optVal
|= aIt
->second
.val
;
1489 while (bIt
!= end(b
.map
)) {
1490 optKey
|= map_key(bIt
->first
, bIt
->second
);
1491 optVal
|= bIt
->second
.val
;
1504 Type
operator()(SArray a
, SArray b
) const {
1505 assertx(a
!= b
); // Should've been handled earlier in union_of.
1506 assertx(!a
->empty());
1507 assertx(!b
->empty());
1509 auto const p1
= toDArrLikePacked(a
);
1510 auto const p2
= toDArrLikePacked(b
);
1512 if (p2
) return (*this)(*p1
, *p2
);
1513 return (*this)(*p1
, *toDArrLikeMap(b
));
1515 return (*this)(*p2
, *toDArrLikeMap(a
));
1517 return (*this)(*toDArrLikeMap(a
), *toDArrLikeMap(b
));
1521 Type
operator()(const DArrLikeMapN
& a
, const DArrLikeMapN
& b
) const {
1525 union_of(a
.key
, b
.key
),
1526 union_of(a
.val
, b
.val
)
1530 Type
operator()(const DArrLikePacked
& a
, SArray b
) const {
1531 assertx(!b
->empty());
1532 auto const p
= toDArrLikePacked(b
);
1533 if (p
) return (*this)(a
, *p
);
1534 return (*this)(a
, *toDArrLikeMap(b
));
1537 Type
operator()(const DArrLikePackedN
& a
, SArray b
) const {
1538 assertx(!b
->empty());
1539 auto const p
= toDArrLikePackedN(b
);
1540 if (p
) return (*this)(a
, *p
);
1541 return (*this)(a
, *toDArrLikeMap(b
));
1544 Type
operator()(const DArrLikeMap
& a
, SArray b
) const {
1545 assertx(!b
->empty());
1546 auto const m
= toDArrLikeMap(b
);
1547 if (m
) return (*this)(a
, *m
);
1548 return (*this)(*toDArrLikePacked(b
), a
);
1551 Type
operator()(const DArrLikeMapN
& a
, SArray b
) const {
1552 assertx(!b
->empty());
1553 auto const m1
= toDArrLikeMapN(b
);
1554 if (m1
) return (*this)(a
, *m1
);
1555 auto const m2
= toDArrLikeMap(b
);
1556 if (m2
) return (*this)(*m2
, a
);
1557 return (*this)(*toDArrLikePackedN(b
), a
);
1560 Type
operator()(const DArrLikePacked
& a
, const DArrLikeMap
& b
) const {
1561 auto mkv
= map_key_values(b
);
1565 union_of(std::move(mkv
.first
), packed_key(a
)),
1566 union_of(std::move(mkv
.second
), packed_values(a
))
1570 Type
operator()(const DArrLikePacked
& a
, const DArrLikeMapN
& b
) const {
1574 union_of(packed_key(a
), b
.key
),
1575 union_of(packed_values(a
), b
.val
)
1579 Type
operator()(const DArrLikePackedN
& a
, const DArrLikeMap
& b
) const {
1580 auto mkv
= map_key_values(b
);
1584 union_of(TInt
, std::move(mkv
.first
)),
1585 union_of(a
.type
, std::move(mkv
.second
))
1589 Type
operator()(const DArrLikePackedN
& a
, const DArrLikeMapN
& b
) const {
1593 union_of(TInt
, b
.key
),
1594 union_of(a
.type
, b
.val
)
1598 Type
operator()(const DArrLikeMap
& a
, const DArrLikeMapN
& b
) const {
1599 auto mkv
= map_key_values(a
);
1603 union_of(std::move(mkv
.first
), b
.key
),
1604 union_of(std::move(mkv
.second
), b
.val
)
1608 Type
operator()(const DArrLikeNone
& a
, const DArrLikePackedN
& b
) const {
1609 // Special case: A Vec is always known to be packed. So if we
1610 // union together a Vec with something else with a packed
1611 // specialization, we can keep the packed specialization.
1612 if (!subtypeAmong(a
.bits
, BVecN
, BArrLikeN
)) {
1613 return (*this)(a
, DArrLikeMapN
{ TInt
, b
.type
});
1615 auto val
= Type
{allowedValBits(a
.bits
, true).first
};
1616 if (!val
.strictSubtypeOf(BInitCell
)) return Type
{ combined
, mark
};
1617 return packedn_impl(combined
, mark
, union_of(std::move(val
), b
.type
));
1619 Type
operator()(const DArrLikeNone
& a
, const DArrLikeMapN
& b
) const {
1620 // Special case: Map includes all possible array structures, so we
1621 // can just union together None's implied key/value types into the
1623 auto key
= Type
{allowedKeyBits(a
.bits
).first
};
1624 auto val
= Type
{allowedValBits(a
.bits
, false).first
};
1625 if (!key
.strictSubtypeOf(BArrKey
) && !val
.strictSubtypeOf(BInitCell
)) {
1626 return Type
{ combined
, mark
};
1631 union_of(std::move(key
), b
.key
),
1632 union_of(std::move(val
), b
.val
)
1635 Type
operator()(const DArrLikeNone
& a
, SArray b
) const {
1636 assertx(!b
->empty());
1637 if (auto const p
= toDArrLikePacked(b
)) {
1638 return (*this)(a
, *p
);
1640 return (*this)(a
, *toDArrLikeMap(b
));
1642 Type
operator()(const DArrLikeNone
& a
, const DArrLikePacked
& b
) const {
1643 if (!subtypeAmong(a
.bits
, BVecN
, BArrLikeN
)) {
1644 return (*this)(a
, DArrLikeMapN
{ packed_key(b
), packed_values(b
) });
1646 auto val
= Type
{allowedValBits(a
.bits
, true).first
};
1647 if (!val
.strictSubtypeOf(BInitCell
)) return Type
{ combined
, mark
};
1648 return packedn_impl(
1651 union_of(std::move(val
), packed_values(b
))
1654 Type
operator()(const DArrLikeNone
& a
, const DArrLikeMap
& b
) const {
1655 auto key
= Type
{allowedKeyBits(a
.bits
).first
};
1656 auto val
= Type
{allowedValBits(a
.bits
, false).first
};
1657 if (!key
.strictSubtypeOf(BArrKey
) && !val
.strictSubtypeOf(BInitCell
)) {
1658 return Type
{ combined
, mark
};
1660 auto mkv
= map_key_values(b
);
1664 union_of(std::move(key
), std::move(mkv
.first
)),
1665 union_of(std::move(val
), std::move(mkv
.second
))
1675 * Subtype is not a commutative relation, so this is the only
1676 * dualDispatchDataFn helper that doesn't use Commute<>.
1678 template<bool contextSensitive
>
1679 struct DualDispatchSubtype
{
1680 static constexpr bool disjoint
= false;
1681 using result_type
= bool;
1683 static bool subtype(const Type
& a
, const Type
& b
) {
1684 return contextSensitive
? a
.moreRefined(b
) : a
.subtypeOf(b
);
1687 static bool subtypePacked(const DArrLikePacked
& a
, const DArrLikePacked
& b
) {
1688 auto const asz
= a
.elems
.size();
1689 auto const bsz
= b
.elems
.size();
1690 if (asz
!= bsz
) return false;
1691 for (auto i
= size_t{0}; i
< asz
; ++i
) {
1692 if (!subtype(a
.elems
[i
], b
.elems
[i
])) return false;
1697 static bool subtypeMap(const DArrLikeMap
& a
, const DArrLikeMap
& b
) {
1698 // If both A and B both don't have optional elements, their values
1699 // are completely disjoint if there's a different number of keys.
1700 if (!a
.hasOptElements() && !b
.hasOptElements() &&
1701 a
.map
.size() != b
.map
.size()) {
1705 // Check the common prefix of known keys. The keys must be the same
1706 // and have compatible types.
1707 auto aIt
= begin(a
.map
);
1708 auto bIt
= begin(b
.map
);
1709 while (aIt
!= end(a
.map
) && bIt
!= end(b
.map
)) {
1710 if (!tvSame(aIt
->first
, bIt
->first
)) return false;
1711 if (aIt
->second
.keyStaticness
!= bIt
->second
.keyStaticness
) {
1712 if (bIt
->second
.keyStaticness
!= TriBool::Maybe
) return false;
1714 if (!subtype(aIt
->second
.val
, bIt
->second
.val
)) return false;
1718 // If B has more known keys than A, A cannot be a subtype of B. It
1719 // doesn't matter if A has optional elements since there's values in
1720 // A which doesn't have them, while B always has the keys.
1721 if (bIt
!= end(b
.map
)) return false;
1723 // If A has any remaining known keys, check they're compatible with
1724 // B's optional elements (if any).
1725 while (aIt
!= end(a
.map
)) {
1726 if (!subtype(map_key(aIt
->first
, aIt
->second
), b
.optKey
)) {
1729 if (!subtype(aIt
->second
.val
, b
.optVal
)) return false;
1733 // Finally the optional values (if any) of A and B must be
1736 subtype(a
.optKey
, b
.optKey
) &&
1737 subtype(a
.optVal
, b
.optVal
);
1740 bool operator()() const { return false; }
1742 bool operator()(SArray a
, SArray b
) const {
1745 bool operator()(const DArrLikePacked
& a
, const DArrLikePacked
& b
) const {
1746 return subtypePacked(a
, b
);
1748 bool operator()(const DArrLikePackedN
& a
, const DArrLikePackedN
& b
) const {
1749 return subtype(a
.type
, b
.type
);
1751 bool operator()(const DArrLikeMap
& a
, const DArrLikeMap
& b
) const {
1752 return subtypeMap(a
, b
);
1754 bool operator()(const DArrLikeMapN
& a
, const DArrLikeMapN
& b
) const {
1755 return subtype(a
.key
, b
.key
) && subtype(a
.val
, b
.val
);
1758 bool operator()(const DArrLikeMap
&, SArray
) const {
1759 // A map (even with all constant values) is never considered a
1760 // subtype of a static array.
1764 bool operator()(SArray a
, const DArrLikeMap
& b
) const {
1765 // If the map doesn't have optional elements, its values are
1766 // disjoint from the static array if the keys are of different
1768 if (!b
.hasOptElements() && a
->size() != b
.map
.size()) return false;
1769 auto const m
= toDArrLikeMap(a
);
1770 return m
&& subtypeMap(*m
, b
);
1773 bool operator()(SArray a
, const DArrLikePacked
& b
) const {
1774 if (a
->size() != b
.elems
.size()) return false;
1775 auto const p
= toDArrLikePacked(a
);
1776 return p
&& subtypePacked(*p
, b
);
1779 bool operator()(const DArrLikePacked
& a
, SArray b
) const {
1780 // A packed array (even with all constant values) is never
1781 // considered a subtype of a static array.
1785 bool operator()(const DArrLikePackedN
& a
, const DArrLikeMapN
& b
) const {
1786 return b
.key
.couldBe(BInt
) && subtype(a
.type
, b
.val
);
1789 bool operator()(const DArrLikePacked
& a
, const DArrLikeMapN
& b
) const {
1790 if (!b
.key
.couldBe(packed_key(a
))) return false;
1791 for (auto const& v
: a
.elems
) {
1792 if (!subtype(v
, b
.val
)) return false;
1797 bool operator()(const DArrLikeMap
& a
, const DArrLikeMapN
& b
) const {
1798 for (auto const& kv
: a
.map
) {
1799 if (!subtype(map_key(kv
.first
, kv
.second
), b
.key
)) return false;
1800 if (!subtype(kv
.second
.val
, b
.val
)) return false;
1802 return subtype(a
.optKey
, b
.key
) && subtype(a
.optVal
, b
.val
);
1805 bool operator()(SArray a
, const DArrLikeMapN
& b
) const {
1809 [&] (TypedValue k
, TypedValue v
) {
1810 bad
|= !(b
.key
.couldBe(from_cell(k
)) && b
.val
.couldBe(from_cell(v
)));
1817 bool operator()(const DArrLikePacked
& a
, const DArrLikePackedN
& b
) const {
1818 for (auto const& t
: a
.elems
) {
1819 if (!subtype(t
, b
.type
)) return false;
1824 bool operator()(SArray a
, const DArrLikePackedN
& b
) const {
1825 assertx(!a
->empty());
1826 auto p
= toDArrLikePackedN(a
);
1827 return p
&& subtype(p
->type
, b
.type
);
1830 bool operator()(const DArrLikeNone
&, SArray
) const {
1833 bool operator()(const DArrLikeNone
&, const DArrLikeMap
&) const {
1836 bool operator()(const DArrLikeNone
&, const DArrLikePacked
&) const {
1840 bool operator()(const DArrLikeNone
& a
, const DArrLikePackedN
& b
) const {
1841 if (!subtypeAmong(a
.bits
, BVecN
, BArrLikeN
)) return false;
1842 auto const val
= Type
{allowedValBits(a
.bits
, true).first
};
1843 return val
.subtypeOf(b
.type
);
1845 bool operator()(const DArrLikeNone
& a
, const DArrLikeMapN
& b
) const {
1846 auto const key
= Type
{allowedKeyBits(a
.bits
).first
};
1847 auto const val
= Type
{allowedValBits(a
.bits
, false).first
};
1849 key
.subtypeOf(b
.key
) &&
1850 val
.subtypeOf(b
.val
);
1853 bool operator()(const DArrLikePackedN
&, const DArrLikePacked
&) const {
1854 // PackedN contains arrays with an arbitrary number of keys, while Packed
1855 // contains arrays with a fixed number of keys, so there's always arrays in
1856 // PackedN which aren't in Packed.
1859 bool operator()(const DArrLikePackedN
&, SArray
) const {
1860 // PackedN contains arrays with an arbitrary number of keys, while SArray is
1861 // just a single array.
1864 bool operator()(const DArrLikeMap
&, const DArrLikePacked
&) const {
1865 // Map does not contain any packed arrays.
1868 bool operator()(const DArrLikeMap
&, const DArrLikePackedN
&) const {
1869 // Map does not contain any packed arrays.
1872 bool operator()(const DArrLikePacked
&, const DArrLikeMap
&) const {
1873 // Map does not contain any packed arrays.
1876 bool operator()(const DArrLikePackedN
&, const DArrLikeMap
&) const {
1877 // Map does not contain any packed arrays.
1880 bool operator()(const DArrLikeMapN
&, const DArrLikePackedN
&) const {
1881 // MapN will always contain more arrays than PackedN because packed arrays
1882 // are a subset of all possible arrays.
1885 bool operator()(const DArrLikeMapN
&, const DArrLikePacked
&) const {
1886 // MapN contains arrays with an arbitrary number of keys, while Packed
1887 // contains arrays with a fixed number of keys, so there's always arrays in
1888 // MapN which aren't in Packed.
1891 bool operator()(const DArrLikeMapN
&, const DArrLikeMap
&) const {
1892 // MapN contains arrays with an arbitrary number of keys, while Map contains
1893 // arrays with a fixed number of keys, so there's always arrays in MapN
1894 // which aren't in Map.
1897 bool operator()(const DArrLikeMapN
&, SArray
) const {
1898 // MapN contains arrays with an arbitrary number of keys, while SArray is
1899 // just a single array.
1904 using DualDispatchCouldBe
= Commute
<DualDispatchCouldBeImpl
>;
1905 using DualDispatchUnion
= Commute
<DualDispatchUnionImpl
>;
1906 using DualDispatchIntersection
= Commute
<DualDispatchIntersectionImpl
>;
1908 //////////////////////////////////////////////////////////////////////
1909 // Helpers for creating literal array-like types
1911 template<typename AInit
, bool force_static
, bool allow_counted
>
1912 Optional
<TypedValue
> fromTypeVec(const std::vector
<Type
>& elems
,
1915 mark
= legacyMark(mark
, bits
);
1916 if (mark
== LegacyMark::Unknown
) return std::nullopt
;
1918 AInit ai
{elems
.size()};
1919 for (auto const& t
: elems
) {
1920 auto const v
= allow_counted
? tvCounted(t
) : tv(t
);
1921 if (!v
) return std::nullopt
;
1922 ai
.append(tvAsCVarRef(&*v
));
1924 auto var
= ai
.toVariant();
1926 if (mark
== LegacyMark::Marked
) {
1927 var
.asArrRef().setLegacyArray(true);
1930 if (force_static
) var
.setEvalScalar();
1931 return tvReturn(std::move(var
));
1934 template<bool allow_counted
>
1935 bool checkTypeVec(const std::vector
<Type
>& elems
, trep bits
, LegacyMark mark
) {
1936 if (legacyMark(mark
, bits
) == LegacyMark::Unknown
) return false;
1937 for (auto const& t
: elems
) {
1938 if (allow_counted
? !is_scalar_counted(t
) : !is_scalar(t
)) return false;
1943 Variant
keyHelper(SString key
) {
1944 return Variant
{ key
, Variant::PersistentStrInit
{} };
1946 const Variant
& keyHelper(const TypedValue
& v
) {
1947 return tvAsCVarRef(&v
);
1949 template <typename AInit
>
1950 void add(AInit
& ai
, const Variant
& key
, const Variant
& value
) {
1951 ai
.setValidKey(key
, value
);
1953 void add(KeysetInit
& ai
, const Variant
& key
, const Variant
& value
) {
1954 assertx(tvSame(*key
.asTypedValue(), *value
.asTypedValue()));
1958 template<typename AInit
, bool force_static
, bool allow_counted
>
1959 Optional
<TypedValue
> fromTypeMap(const MapElems
& elems
,
1962 mark
= legacyMark(mark
, bits
);
1963 if (mark
== LegacyMark::Unknown
) return std::nullopt
;
1965 auto val
= eval_cell_value([&] () -> TypedValue
{
1966 AInit ai
{elems
.size()};
1967 for (auto const& elm
: elems
) {
1968 if (!allow_counted
&& elm
.second
.keyStaticness
== TriBool::No
) {
1969 return make_tv
<KindOfUninit
>();
1972 allow_counted
? tvCounted(elm
.second
.val
) : tv(elm
.second
.val
);
1973 if (!v
) return make_tv
<KindOfUninit
>();
1974 add(ai
, keyHelper(elm
.first
), tvAsCVarRef(&*v
));
1976 auto var
= ai
.toVariant();
1978 if (mark
== LegacyMark::Marked
) {
1979 var
.asArrRef().setLegacyArray(true);
1982 if (force_static
) var
.setEvalScalar();
1983 return tvReturn(std::move(var
));
1985 if (val
&& val
->m_type
== KindOfUninit
) val
.reset();
1989 template<bool allow_counted
>
1990 bool checkTypeMap(const MapElems
& elems
, trep bits
, LegacyMark mark
) {
1991 if (legacyMark(mark
, bits
) == LegacyMark::Unknown
) return false;
1992 for (auto const& elem
: elems
) {
1993 if (!allow_counted
&& elem
.second
.keyStaticness
== TriBool::No
) {
1997 ? !is_scalar_counted(elem
.second
.val
)
1998 : !is_scalar(elem
.second
.val
)) {
2005 struct KeysetAppendInit
: KeysetInit
{
2006 using KeysetInit::KeysetInit
;
2007 KeysetAppendInit
& append(const Variant
& v
) {
2008 add(*v
.asTypedValue());
2013 //////////////////////////////////////////////////////////////////////
2017 //////////////////////////////////////////////////////////////////////
2019 // We ref-count the IsectSet, so multiple copies of a DCls can share
2020 // it. This is basically copy_ptr, but we can't use that easily with
2021 // our CompactTaggedPtr representation.
2022 struct DCls::IsectWrapper
{
2024 std::atomic
<uint32_t> refcount
{1};
2025 void acquire() { refcount
.fetch_add(1, std::memory_order_relaxed
); }
2027 if (refcount
.fetch_sub(1, std::memory_order_relaxed
) == 1) {
2033 struct DCls::IsectAndExactWrapper
{
2036 std::atomic
<uint32_t> refcount
{1};
2037 void acquire() { refcount
.fetch_add(1, std::memory_order_relaxed
); }
2039 if (refcount
.fetch_sub(1, std::memory_order_relaxed
) == 1) {
2045 DCls::DCls(const DCls
& o
) : val
{o
.val
} {
2047 rawIsect()->acquire();
2048 } else if (isIsectAndExact()) {
2049 rawIsectAndExact()->acquire();
2055 rawIsect()->release();
2056 } else if (isIsectAndExact()) {
2057 rawIsectAndExact()->release();
2061 DCls
& DCls::operator=(const DCls
& o
) {
2062 if (this == &o
) return *this;
2064 auto const copy
= [&] {
2066 o
.rawIsect()->acquire();
2067 } else if (o
.isIsectAndExact()) {
2068 o
.rawIsectAndExact()->acquire();
2074 auto const i
= rawIsect();
2077 } else if (isIsectAndExact()) {
2078 auto const i
= rawIsectAndExact();
2086 DCls
DCls::MakeExact(res::Class cls
, bool nonReg
) {
2088 nonReg
? TagExact
: Tag(TagExact
| TagReg
),
2089 (void*)cls
.toOpaque()
2093 DCls
DCls::MakeSub(res::Class cls
, bool nonReg
) {
2095 nonReg
? TagNone
: TagReg
,
2096 (void*)cls
.toOpaque()
2100 DCls
DCls::MakeIsect(IsectSet isect
, bool nonReg
) {
2101 assertx(isect
.size() > 1);
2102 auto w
= new IsectWrapper
{std::move(isect
)};
2104 nonReg
? TagIsect
: Tag(TagIsect
| TagReg
),
2109 DCls
DCls::MakeIsectAndExact(res::Class exact
, IsectSet isect
, bool nonReg
) {
2110 assertx(!isect
.empty());
2111 assertx(exact
.isMissingDebug());
2112 auto w
= new IsectAndExactWrapper
{exact
, std::move(isect
)};
2114 nonReg
? Tag(TagIsect
| TagExact
) : Tag(TagIsect
| TagExact
| TagReg
),
2119 res::Class
DCls::cls() const {
2120 assertx(!isIsect() && !isIsectAndExact());
2122 return res::Class::fromOpaque((uintptr_t)val
.ptr());
2125 res::Class
DCls::smallestCls() const {
2128 : (isIsectAndExact() ? isectAndExact().first
: cls());
2131 const DCls::IsectSet
& DCls::isect() const {
2132 return rawIsect()->isects
;
2135 std::pair
<res::Class
, const DCls::IsectSet
*> DCls::isectAndExact() const {
2136 auto const r
= rawIsectAndExact();
2137 return std::make_pair(r
->exact
, &r
->isects
);
2140 void DCls::setCls(res::Class cls
) {
2141 assertx(!isIsect() && !isIsectAndExact());
2142 val
.set(val
.tag(), (void*)cls
.toOpaque());
2145 bool DCls::same(const DCls
& o
, bool checkCtx
) const {
2147 if (val
.tag() != o
.val
.tag()) return false;
2149 if (removeCtx(val
.tag()) != removeCtx(o
.val
.tag())) return false;
2153 auto const& isect1
= isect();
2154 auto const& isect2
= o
.isect();
2155 if (&isect1
== &isect2
) return true;
2156 if (isect1
.size() != isect2
.size()) return false;
2158 begin(isect1
), end(isect1
),
2159 begin(isect2
), end(isect2
),
2160 [] (res::Class c1
, res::Class c2
) { return c1
.same(c2
); }
2162 } else if (isIsectAndExact()) {
2163 auto const [exact1
, isect1
] = isectAndExact();
2164 auto const [exact2
, isect2
] = o
.isectAndExact();
2165 if (!exact1
.same(exact2
)) return false;
2166 if (isect1
== isect2
) return true;
2167 if (isect1
->size() != isect2
->size()) return false;
2169 begin(*isect1
), end(*isect1
),
2170 begin(*isect2
), end(*isect2
),
2171 [] (res::Class c1
, res::Class c2
) { return c1
.same(c2
); }
2174 return cls().same(o
.cls());
2178 DCls::IsectWrapper
* DCls::rawIsect() const {
2181 return (IsectWrapper
*)val
.ptr();
2184 DCls::IsectAndExactWrapper
* DCls::rawIsectAndExact() const {
2185 assertx(isIsectAndExact());
2187 return (IsectAndExactWrapper
*)val
.ptr();
2190 void DCls::serde(BlobEncoder
& sd
) const {
2194 } else if (isIsectAndExact()) {
2195 auto [e
, i
] = isectAndExact();
2202 void DCls::serde(BlobDecoder
& sd
) {
2203 auto const tag
= sd
.template make
<decltype(val
.tag())>();
2204 if (tagIsIsect(tag
)) {
2205 auto i
= sd
.make
<IsectSet
>();
2206 val
.set(tag
, new IsectWrapper
{std::move(i
)});
2207 } else if (tagIsIsectAndExact(tag
)) {
2208 auto e
= sd
.make
<res::Class
>();
2209 auto i
= sd
.make
<IsectSet
>();
2210 val
.set(tag
, new IsectAndExactWrapper
{e
, std::move(i
)});
2212 auto c
= sd
.make
<res::Class
>();
2213 val
.set(tag
, (void*)c
.toOpaque());
2217 //////////////////////////////////////////////////////////////////////
2219 MapElem
MapElem::KeyFromType(const Type
& key
, Type val
) {
2220 assertx(is_scalar_counted(key
));
2221 assertx(is_specialized_int(key
) || is_specialized_string(key
));
2224 !key
.couldBe(BCounted
)
2226 : (!key
.couldBe(BUnc
) ? TriBool::No
: TriBool::Maybe
)
2230 //////////////////////////////////////////////////////////////////////
2231 // Helpers for managing context types.
2233 Type
Type::unctxHelper(Type t
, bool& changed
) {
2236 switch (t
.m_dataTag
) {
2238 if (t
.m_data
.dobj
.isCtx()) {
2239 t
.m_data
.dobj
.setCtx(false);
2243 case DataTag::WaitHandle
: {
2244 auto const& inner
= t
.m_data
.dwh
->inner
;
2245 auto ty
= unctxHelper(inner
, changed
);
2246 if (changed
) t
.m_data
.dwh
.mutate()->inner
= std::move(ty
);
2250 if (t
.m_data
.dcls
.isCtx()) {
2251 t
.m_data
.dcls
.setCtx(false);
2255 case DataTag::ArrLikePacked
: {
2256 auto const packed
= t
.m_data
.packed
.get();
2257 HPHP::HHBBC::DArrLikePacked
* mutated
= nullptr;
2258 for (size_t i
= 0; i
< packed
->elems
.size(); ++i
) {
2260 const auto ty
= unctxHelper(packed
->elems
[i
], c
);
2264 mutated
= t
.m_data
.packed
.mutate();
2266 mutated
->elems
[i
] = ty
;
2271 case DataTag::ArrLikePackedN
: {
2272 auto const packedn
= t
.m_data
.packedn
.get();
2273 auto ty
= unctxHelper(packedn
->type
, changed
);
2275 t
.m_data
.packedn
.mutate()->type
= ty
;
2279 case DataTag::ArrLikeMap
: {
2280 auto const map
= t
.m_data
.map
.get();
2282 HPHP::HHBBC::DArrLikeMap
* mutated
= nullptr;
2283 for (auto it
= map
->map
.begin(); it
!= map
->map
.end(); ++it
) {
2284 auto const ty
= unctxHelper(it
->second
.val
, changed
);
2286 offset
= std::distance(it
, map
->map
.begin());
2287 mutated
= t
.m_data
.map
.mutate();
2292 auto it
= mutated
->map
.begin();
2293 for (std::advance(it
, offset
);
2294 it
!= mutated
->map
.end();
2297 auto ty
= unctxHelper(it
->second
.val
, c
);
2299 mutated
->map
.update(it
, it
->second
.withType(std::move(ty
)));
2304 auto ty
= unctxHelper(t
.m_data
.map
->optVal
, changed2
);
2305 if (changed2
) t
.m_data
.map
.mutate()->optVal
= std::move(ty
);
2306 changed
|= changed2
;
2309 case DataTag::ArrLikeMapN
: {
2310 auto const mapn
= t
.m_data
.mapn
.get();
2311 auto ty
= unctxHelper(mapn
->val
, changed
);
2312 if (changed
) t
.m_data
.mapn
.mutate()->val
= std::move(ty
);
2319 case DataTag::ArrLikeVal
:
2320 case DataTag::LazyCls
:
2321 case DataTag::EnumClassLabel
:
2327 //////////////////////////////////////////////////////////////////////
2329 Type
& Type::operator=(const Type
& o
) noexcept
{
2330 SCOPE_EXIT
{ assertx(checkInvariants()); };
2331 if (this == &o
) return *this;
2333 construct(*this, o
);
2337 Type
& Type::operator=(Type
&& o
) noexcept
{
2338 SCOPE_EXIT
{ assertx(checkInvariants());
2339 assertx(o
.checkInvariants()); };
2340 if (this == &o
) return *this;
2342 construct(*this, std::move(o
));
2346 const Type
& Type::operator |= (const Type
& other
) {
2347 *this = union_of(std::move(*this), other
);
2351 const Type
& Type::operator |= (Type
&& other
) {
2352 *this = union_of(std::move(*this), std::move(other
));
2356 const Type
& Type::operator &= (const Type
& other
) {
2357 *this = intersection_of(std::move(*this), other
);
2361 const Type
& Type::operator &= (Type
&& other
) {
2362 *this = intersection_of(std::move(*this), std::move(other
));
2366 //////////////////////////////////////////////////////////////////////
2368 void Type::copyData(const Type
& o
) {
2369 assertx(m_dataTag
!= DataTag::None
);
2370 switch (m_dataTag
) {
2371 case DataTag::None
: not_reached();
2372 #define DT(tag_name,type,name) \
2373 case DataTag::tag_name: \
2374 construct(m_data.name, o.m_data.name); \
2382 void Type::moveData(Type
&& o
) {
2383 assertx(m_dataTag
!= DataTag::None
);
2384 o
.m_dataTag
= DataTag::None
;
2385 switch (m_dataTag
) {
2386 case DataTag::None
: not_reached();
2387 #define DT(tag_name,type,name) \
2388 case DataTag::tag_name: \
2389 construct(m_data.name, std::move(o.m_data.name)); \
2397 void Type::destroyData() {
2398 assertx(m_dataTag
!= DataTag::None
);
2399 switch (m_dataTag
) {
2400 case DataTag::None
: not_reached();
2401 #define DT(tag_name,type,name) \
2402 case DataTag::tag_name: \
2403 destroy(m_data.name); \
2411 //////////////////////////////////////////////////////////////////////
2413 template<typename Ret
, typename T
, typename Function
>
2414 struct Type::DDHelperFn
{
2416 typename
std::enable_if
<(!std::is_same
<Y
,T
>::value
|| !Function::disjoint
) &&
2417 std::is_same
<typename DataTagTrait
<Y
>::tag
,
2418 typename DataTagTrait
<T
>::tag
>::value
,
2420 operator()(const Y
& y
) const { return f(t
, y
); }
2423 typename
std::enable_if
<(std::is_same
<Y
,T
>::value
&& Function::disjoint
) &&
2424 std::is_same
<typename DataTagTrait
<Y
>::tag
,
2425 typename DataTagTrait
<T
>::tag
>::value
,
2427 operator()(const Y
&) const { not_reached(); }
2430 typename
std::enable_if
<!std::is_same
<typename DataTagTrait
<Y
>::tag
,
2431 typename DataTagTrait
<T
>::tag
>::value
,
2433 operator()(const Y
&) const { return f(); }
2435 Ret
operator()() const { return f(); }
2440 template<typename Ret
, typename T
, typename Function
>
2441 Type::DDHelperFn
<Ret
,T
,Function
> Type::ddbind(const Function
& f
,
2446 // Dispatcher for the second argument for dualDispatchDataFn.
2447 template<typename Ret
, typename T
, typename F
>
2448 Ret
Type::dd2nd(const Type
& o
, DDHelperFn
<Ret
,T
,F
> f
) const {
2449 switch (o
.m_dataTag
) {
2450 case DataTag::None
: not_reached();
2451 case DataTag::Int
: return f();
2452 case DataTag::Dbl
: return f();
2453 case DataTag::Cls
: return f();
2454 case DataTag::Str
: return f();
2455 case DataTag::LazyCls
: return f();
2456 case DataTag::EnumClassLabel
: return f();
2457 case DataTag::Obj
: return f();
2458 case DataTag::WaitHandle
: return f();
2459 case DataTag::ArrLikeVal
: return f(o
.m_data
.aval
);
2460 case DataTag::ArrLikePacked
: return f(*o
.m_data
.packed
);
2461 case DataTag::ArrLikePackedN
: return f(*o
.m_data
.packedn
);
2462 case DataTag::ArrLikeMap
: return f(*o
.m_data
.map
);
2463 case DataTag::ArrLikeMapN
: return f(*o
.m_data
.mapn
);
2469 * Dual-dispatch on (this->m_dataTag, o.m_dataTag)
2471 * See the DualDispatch* classes above
2473 template<typename F
>
2474 typename
F::result_type
2475 Type::dualDispatchDataFn(const Type
& o
, F f
) const {
2476 using R
= typename
F::result_type
;
2477 switch (m_dataTag
) {
2478 case DataTag::None
: not_reached();
2479 case DataTag::Int
: return f();
2480 case DataTag::Dbl
: return f();
2481 case DataTag::Cls
: return f();
2482 case DataTag::Str
: return f();
2483 case DataTag::LazyCls
: return f();
2484 case DataTag::EnumClassLabel
: return f();
2485 case DataTag::Obj
: return f();
2486 case DataTag::WaitHandle
: return f();
2487 case DataTag::ArrLikeVal
: return dd2nd(o
, ddbind
<R
>(f
, m_data
.aval
));
2488 case DataTag::ArrLikePacked
: return dd2nd(o
, ddbind
<R
>(f
, *m_data
.packed
));
2489 case DataTag::ArrLikePackedN
: return dd2nd(o
, ddbind
<R
>(f
, *m_data
.packedn
));
2490 case DataTag::ArrLikeMap
: return dd2nd(o
, ddbind
<R
>(f
, *m_data
.map
));
2491 case DataTag::ArrLikeMapN
: return dd2nd(o
, ddbind
<R
>(f
, *m_data
.mapn
));
2497 * Like dualDispatchDataFn, but use DArrLikeNone for *this.
2499 template<typename Function
>
2500 typename
Function::result_type
2501 Type::dispatchArrLikeNone(const Type
& o
, Function f
) const {
2502 assertx(couldBe(BArrLikeN
));
2503 assertx(!is_specialized_array_like(*this));
2506 ddbind
<typename
Function::result_type
>(f
, DArrLikeNone
{ bits() })
2510 //////////////////////////////////////////////////////////////////////
2512 template<bool contextSensitive
>
2513 bool Type::equivImpl(const Type
& o
) const {
2514 if (bits() != o
.bits()) return false;
2515 if (m_legacyMark
!= o
.m_legacyMark
) return false;
2516 if (hasData() != o
.hasData()) return false;
2517 if (!hasData()) return true;
2519 if (m_dataTag
!= o
.m_dataTag
) return false;
2521 switch (m_dataTag
) {
2525 assertx(m_data
.sval
->isStatic());
2526 assertx(o
.m_data
.sval
->isStatic());
2527 return m_data
.sval
== o
.m_data
.sval
;
2528 case DataTag::LazyCls
:
2529 assertx(m_data
.lazyclsval
->isStatic());
2530 assertx(o
.m_data
.lazyclsval
->isStatic());
2531 return m_data
.lazyclsval
== o
.m_data
.lazyclsval
;
2532 case DataTag::EnumClassLabel
:
2533 assertx(m_data
.eclval
->isStatic());
2534 assertx(o
.m_data
.eclval
->isStatic());
2535 return m_data
.eclval
== o
.m_data
.eclval
;
2536 case DataTag::ArrLikeVal
:
2537 assertx(m_data
.aval
->isStatic());
2538 assertx(o
.m_data
.aval
->isStatic());
2539 return m_data
.aval
== o
.m_data
.aval
;
2541 return m_data
.ival
== o
.m_data
.ival
;
2543 return double_equals(m_data
.dval
, o
.m_data
.dval
);
2545 return m_data
.dobj
.same(o
.m_data
.dobj
, contextSensitive
);
2546 case DataTag::WaitHandle
:
2547 assertx(m_data
.dwh
->cls
.same(o
.m_data
.dwh
->cls
));
2548 return m_data
.dwh
->inner
.equivImpl
<contextSensitive
>(
2552 return m_data
.dcls
.same(o
.m_data
.dcls
, contextSensitive
);
2553 case DataTag::ArrLikePacked
:
2554 if (m_data
.packed
->elems
.size() != o
.m_data
.packed
->elems
.size()) {
2557 for (auto i
= 0; i
< m_data
.packed
->elems
.size(); i
++) {
2558 if (!m_data
.packed
->elems
[i
]
2559 .equivImpl
<contextSensitive
>(o
.m_data
.packed
->elems
[i
])) {
2564 case DataTag::ArrLikePackedN
:
2565 return m_data
.packedn
->type
2566 .equivImpl
<contextSensitive
>(o
.m_data
.packedn
->type
);
2567 case DataTag::ArrLikeMap
: {
2568 if (m_data
.map
->map
.size() != o
.m_data
.map
->map
.size()) {
2571 auto it
= o
.m_data
.map
->map
.begin();
2572 for (auto const& kv
: m_data
.map
->map
) {
2573 if (!tvSame(kv
.first
, it
->first
)) return false;
2574 if (kv
.second
.keyStaticness
!= it
->second
.keyStaticness
) return false;
2575 if (!kv
.second
.val
.equivImpl
<contextSensitive
>(it
->second
.val
)) {
2581 m_data
.map
->optKey
.equivImpl
<contextSensitive
>(o
.m_data
.map
->optKey
) &&
2582 m_data
.map
->optVal
.equivImpl
<contextSensitive
>(o
.m_data
.map
->optVal
);
2584 case DataTag::ArrLikeMapN
:
2585 return m_data
.mapn
->key
.equivImpl
<contextSensitive
>(o
.m_data
.mapn
->key
) &&
2586 m_data
.mapn
->val
.equivImpl
<contextSensitive
>(o
.m_data
.mapn
->val
);
2591 bool Type::equivalentlyRefined(const Type
& o
) const {
2592 return equivImpl
<true>(o
);
2595 bool Type::operator==(const Type
& o
) const {
2596 return equivImpl
<false>(o
);
2599 size_t Type::hash() const {
2600 using U1
= std::underlying_type
<trep
>::type
;
2601 using U2
= std::underlying_type
<decltype(m_dataTag
)>::type
;
2602 auto const rawBits
= U1
{bits()};
2603 auto const rawTag
= static_cast<U2
>(m_dataTag
);
2606 [&] () -> uintptr_t {
2607 switch (m_dataTag
) {
2610 case DataTag::Obj
: {
2611 if (m_data
.dobj
.isExact() || m_data
.dobj
.isSub()) {
2612 return folly::hash::hash_combine(
2613 m_data
.dobj
.cls().hash(),
2614 m_data
.dobj
.containsNonRegular()
2617 if (m_data
.dobj
.isIsect()) {
2618 return folly::hash::hash_range(
2619 begin(m_data
.dobj
.isect()),
2620 end(m_data
.dobj
.isect()),
2621 m_data
.dobj
.containsNonRegular(),
2622 [] (res::Class c
) { return c
.hash(); }
2625 assertx(m_data
.dobj
.isIsectAndExact());
2626 auto const [e
, i
] = m_data
.dobj
.isectAndExact();
2627 return folly::hash::hash_range(
2629 folly::hash::hash_combine(
2631 m_data
.dobj
.containsNonRegular()
2633 [] (res::Class c
) { return c
.hash(); }
2636 case DataTag::WaitHandle
:
2637 return m_data
.dwh
->inner
.hash();
2638 case DataTag::Cls
: {
2639 if (m_data
.dcls
.isExact() || m_data
.dcls
.isSub()) {
2640 return folly::hash::hash_combine(
2641 m_data
.dcls
.cls().hash(),
2642 m_data
.dcls
.containsNonRegular()
2645 if (m_data
.dcls
.isIsect()) {
2646 return folly::hash::hash_range(
2647 begin(m_data
.dcls
.isect()),
2648 end(m_data
.dcls
.isect()),
2649 m_data
.dcls
.containsNonRegular(),
2650 [] (res::Class c
) { return c
.hash(); }
2653 assertx(m_data
.dcls
.isIsectAndExact());
2654 auto const [e
, i
] = m_data
.dcls
.isectAndExact();
2655 return folly::hash::hash_range(
2657 folly::hash::hash_combine(
2659 m_data
.dcls
.containsNonRegular()
2661 [] (res::Class c
) { return c
.hash(); }
2665 return (uintptr_t)m_data
.sval
;
2666 case DataTag::LazyCls
:
2667 return (uintptr_t)m_data
.lazyclsval
;
2668 case DataTag::EnumClassLabel
:
2669 return (uintptr_t)m_data
.eclval
;
2673 return std::hash
<double>{}(m_data
.dval
);
2674 case DataTag::ArrLikeVal
:
2675 return (uintptr_t)m_data
.aval
;
2676 case DataTag::ArrLikePacked
:
2677 return folly::hash::hash_range(
2678 m_data
.packed
->elems
.begin(),
2679 m_data
.packed
->elems
.end(),
2681 [] (const Type
& t
) { return t
.hash(); }
2683 case DataTag::ArrLikePackedN
:
2684 return m_data
.packedn
->type
.hash();
2685 case DataTag::ArrLikeMap
:
2686 return folly::hash::hash_range(
2687 m_data
.map
->map
.begin(),
2688 m_data
.map
->map
.end(),
2689 folly::hash::hash_combine(
2690 m_data
.map
->optKey
.hash(),
2691 m_data
.map
->optVal
.hash()
2693 [] (const std::pair
<TypedValue
, MapElem
>& p
) {
2694 return folly::hash::hash_combine(
2695 map_key(p
.first
, p
.second
).hash(),
2700 case DataTag::ArrLikeMapN
:
2701 return folly::hash::hash_combine(
2702 m_data
.mapn
->key
.hash(),
2703 m_data
.mapn
->val
.hash()
2709 return folly::hash::hash_combine(rawBits
, rawTag
, data
);
2712 template<bool contextSensitive
>
2713 bool Type::subtypeOfImpl(const Type
& o
) const {
2714 using HPHP::HHBBC::couldBe
;
2716 auto const isect
= bits() & o
.bits();
2717 if (isect
!= bits()) return false;
2719 if (!legacyMarkSubtypeOf(project(m_legacyMark
, isect
),
2720 project(o
.m_legacyMark
, isect
))) {
2724 // If the (non-empty) intersection cannot contain data, or if the
2725 // other type has no data, the bits are sufficient.
2726 if (!couldBe(isect
, kSupportBits
)) return true;
2727 if (!o
.hasData()) return true;
2729 // For any specialized data in the other type which is supported by
2730 // the intersection, there must be the same specialization in *this
2731 // which is equal or more specific.
2733 if (couldBe(isect
, BObj
) && is_specialized_obj(o
)) {
2734 // For BObj, it could be a wait handle or a specialized object, so
2735 // we must convert between them to match.
2736 if (!is_specialized_obj(*this)) return false;
2738 if (is_specialized_wait_handle(*this)) {
2739 if (is_specialized_wait_handle(o
)) {
2740 assertx(m_data
.dwh
->cls
.same(o
.m_data
.dwh
->cls
));
2741 return m_data
.dwh
->inner
.subtypeOfImpl
<contextSensitive
>(
2745 return subtypeCls
<contextSensitive
>(m_data
.dwh
->cls
, o
.m_data
.dobj
);
2746 } else if (is_specialized_wait_handle(o
)) {
2747 if (!subtypeCls
<contextSensitive
>(m_data
.dobj
, o
.m_data
.dwh
->cls
)) return false;
2748 if (subtypeCls
<contextSensitive
>(o
.m_data
.dwh
->cls
, m_data
.dobj
)) return false;
2751 return subtypeCls
<contextSensitive
>(m_data
.dobj
, o
.m_data
.dobj
);
2755 if (couldBe(isect
, BCls
) && is_specialized_cls(o
)) {
2757 is_specialized_cls(*this) &&
2758 subtypeCls
<contextSensitive
>(m_data
.dcls
, o
.m_data
.dcls
);
2761 if (couldBe(isect
, BArrLikeN
) && is_specialized_array_like(o
)) {
2762 if (is_specialized_array_like(*this)) {
2763 return dualDispatchDataFn(o
, DualDispatchSubtype
<contextSensitive
>{});
2765 return dispatchArrLikeNone(o
, DualDispatchSubtype
<contextSensitive
>{});
2768 if (couldBe(isect
, BStr
) && is_specialized_string(o
)) {
2770 is_specialized_string(*this) &&
2771 m_data
.sval
== o
.m_data
.sval
;
2774 if (couldBe(isect
, BLazyCls
) && is_specialized_lazycls(o
)) {
2776 is_specialized_lazycls(*this) &&
2777 m_data
.lazyclsval
== o
.m_data
.lazyclsval
;
2780 if (couldBe(isect
, BEnumClassLabel
) && is_specialized_ecl(o
)) {
2782 is_specialized_ecl(*this) &&
2783 m_data
.eclval
== o
.m_data
.eclval
;
2786 if (couldBe(isect
, BInt
) && is_specialized_int(o
)) {
2788 is_specialized_int(*this) &&
2789 m_data
.ival
== o
.m_data
.ival
;
2792 if (couldBe(isect
, BDbl
) && is_specialized_double(o
)) {
2794 is_specialized_double(*this) &&
2795 double_equals(m_data
.dval
, o
.m_data
.dval
);
2801 bool Type::moreRefined(const Type
& o
) const {
2802 assertx(checkInvariants());
2803 assertx(o
.checkInvariants());
2804 return subtypeOfImpl
<true>(o
);
2807 bool Type::strictlyMoreRefined(const Type
& o
) const {
2808 assertx(checkInvariants());
2809 assertx(o
.checkInvariants());
2810 return subtypeOfImpl
<true>(o
) &&
2811 !equivImpl
<true>(o
);
2814 bool Type::subtypeOf(const Type
& o
) const {
2815 assertx(checkInvariants());
2816 assertx(o
.checkInvariants());
2817 return subtypeOfImpl
<false>(o
);
2820 bool Type::strictSubtypeOf(const Type
& o
) const {
2821 assertx(checkInvariants());
2822 assertx(o
.checkInvariants());
2823 return *this != o
&& subtypeOf(o
);
2826 bool Type::couldBe(const Type
& o
) const {
2827 using HPHP::HHBBC::subtypeOf
;
2829 assertx(checkInvariants());
2830 assertx(o
.checkInvariants());
2832 auto const isect
= bits() & o
.bits();
2833 if (!isect
) return false;
2835 if (!legacyMarkCouldBe(project(m_legacyMark
, isect
),
2836 project(o
.m_legacyMark
, isect
))) {
2840 // If the intersection has any non-supported bits, we can simply
2841 // ignore all specializations. Regardless if the specializations
2842 // match or not, we know there's a bit unaffected, so they could be
2844 if (!subtypeOf(isect
, kSupportBits
)) return true;
2845 if (!hasData() && !o
.hasData()) return true;
2847 // Specialized data can only make couldBe be false if both sides
2848 // have the same specialization which has disjoint
2849 // values. Specializations not supported by the intersection are
2852 if (subtypeOf(isect
, BObj
)) {
2853 if (!is_specialized_obj(*this) || !is_specialized_obj(o
)) return true;
2855 if (is_specialized_wait_handle(*this)) {
2856 if (is_specialized_wait_handle(o
)) {
2857 assertx(m_data
.dwh
->cls
.same(o
.m_data
.dwh
->cls
));
2860 return couldBeCls(m_data
.dwh
->cls
, o
.m_data
.dobj
);
2861 } else if (is_specialized_wait_handle(o
)) {
2862 return couldBeCls(m_data
.dobj
, o
.m_data
.dwh
->cls
);
2864 return couldBeCls(m_data
.dobj
, o
.m_data
.dobj
);
2868 if (subtypeOf(isect
, BCls
)) {
2869 if (!is_specialized_cls(*this) || !is_specialized_cls(o
)) return true;
2870 return couldBeCls(m_data
.dcls
, o
.m_data
.dcls
);
2873 if (subtypeOf(isect
, BArrLikeN
)) {
2874 if (is_specialized_array_like(*this)) {
2875 if (is_specialized_array_like(o
)) {
2876 return dualDispatchDataFn(o
, DualDispatchCouldBe
{isect
});
2878 return o
.dispatchArrLikeNone(*this, DualDispatchCouldBe
{isect
});
2879 } else if (is_specialized_array_like(o
)) {
2880 return dispatchArrLikeNone(o
, DualDispatchCouldBe
{isect
});
2885 if (subtypeOf(isect
, BStr
)) {
2886 if (!is_specialized_string(*this) || !is_specialized_string(o
)) return true;
2887 return m_data
.sval
== o
.m_data
.sval
;
2890 if (subtypeOf(isect
, BLazyCls
)) {
2891 if (!is_specialized_lazycls(*this) || !is_specialized_lazycls(o
)) {
2894 return m_data
.lazyclsval
== o
.m_data
.lazyclsval
;
2897 if (subtypeOf(isect
, BEnumClassLabel
)) {
2898 if (!is_specialized_ecl(*this) || !is_specialized_ecl(o
)) {
2901 return m_data
.eclval
== o
.m_data
.eclval
;
2904 if (subtypeOf(isect
, BInt
)) {
2905 if (!is_specialized_int(*this) || !is_specialized_int(o
)) return true;
2906 return m_data
.ival
== o
.m_data
.ival
;
2909 if (subtypeOf(isect
, BDbl
)) {
2910 if (!is_specialized_double(*this) || !is_specialized_double(o
)) return true;
2911 return double_equals(m_data
.dval
, o
.m_data
.dval
);
2917 bool Type::checkInvariants() const {
2918 if (!debug
) return true;
2920 SCOPE_ASSERT_DETAIL("checkInvariants") { return show(*this); };
2922 constexpr const size_t kMaxArrayCheck
= 100;
2924 // NB: Avoid performing operations which can trigger recursive
2925 // checkInvariants() calls, which can cause exponential time
2926 // blow-ups. Try to stick with bit manipulations and avoid more
2927 // complicated operators.
2929 assertx(subtypeOf(BTop
));
2930 assertx(subtypeOf(BCell
) || bits() == BTop
);
2931 assertx(IMPLIES(bits() == BTop
, !hasData()));
2933 if (HPHP::HHBBC::couldBe(bits(), kLegacyMarkBits
)) {
2934 assertx(m_legacyMark
!= LegacyMark::Bottom
);
2936 assertx(m_legacyMark
== LegacyMark::Bottom
);
2939 assertx(IMPLIES(hasData(), couldBe(kSupportBits
)));
2940 assertx(IMPLIES(subtypeOf(kNonSupportBits
), !hasData()));
2942 switch (m_dataTag
) {
2946 assertx(m_data
.sval
->isStatic());
2947 assertx(couldBe(BStr
));
2948 assertx(subtypeOf(BStr
| kNonSupportBits
));
2950 case DataTag::LazyCls
:
2951 assertx(m_data
.lazyclsval
->isStatic());
2952 assertx(couldBe(BLazyCls
));
2953 assertx(subtypeOf(BLazyCls
| kNonSupportBits
));
2955 case DataTag::EnumClassLabel
:
2956 assertx(m_data
.eclval
->isStatic());
2957 assertx(couldBe(BEnumClassLabel
));
2958 assertx(subtypeOf(BEnumClassLabel
| kNonSupportBits
));
2961 assertx(couldBe(BDbl
));
2962 assertx(subtypeOf(BDbl
| kNonSupportBits
));
2965 assertx(couldBe(BInt
));
2966 assertx(subtypeOf(BInt
| kNonSupportBits
));
2969 assertx(couldBe(BCls
));
2970 assertx(subtypeOf(BCls
| kNonSupportBits
));
2971 if (m_data
.dcls
.isExact()) {
2972 if (!m_data
.dcls
.cls().isSerialized()) {
2975 m_data
.dcls
.containsNonRegular(),
2976 m_data
.dcls
.cls().mightBeNonRegular()
2981 !m_data
.dcls
.containsNonRegular(),
2982 m_data
.dcls
.cls().mightBeRegular()
2986 } else if (m_data
.dcls
.isSub()) {
2987 if (!m_data
.dcls
.cls().isSerialized()) {
2988 assertx(m_data
.dcls
.cls().couldBeOverridden());
2991 m_data
.dcls
.containsNonRegular(),
2992 m_data
.dcls
.cls().mightContainNonRegular()
2997 !m_data
.dcls
.containsNonRegular(),
2998 m_data
.dcls
.cls().couldBeOverriddenByRegular()
3002 } else if (m_data
.dcls
.isIsect()) {
3003 // There's way more things we could verify here, but it gets
3004 // expensive (and requires the index).
3005 assertx(m_data
.dcls
.isect().size() > 1);
3006 for (auto const DEBUG_ONLY c
: m_data
.dcls
.isect()) {
3007 if (c
.isSerialized()) continue;
3010 !m_data
.dcls
.containsNonRegular(),
3011 c
.mightBeRegular() || c
.couldBeOverriddenByRegular()
3016 assertx(m_data
.dcls
.isIsectAndExact());
3017 // There's way more things we could verify here, but it gets
3018 // expensive (and requires the index).
3019 auto const DEBUG_ONLY
[e
, i
] = m_data
.dcls
.isectAndExact();
3020 assertx(!i
->empty());
3021 if (!e
.isSerialized()) {
3022 assertx(e
.isMissingDebug());
3023 assertx(IMPLIES(!m_data
.dcls
.containsNonRegular(),
3024 e
.mightBeRegular() || e
.couldBeOverriddenByRegular()));
3026 for (auto const DEBUG_ONLY c
: *i
) {
3027 if (c
.isSerialized()) continue;
3028 assertx(!c
.same(e
));
3029 assertx(!c
.hasCompleteChildren());
3032 !m_data
.dcls
.containsNonRegular(),
3033 c
.mightBeRegular() || c
.couldBeOverriddenByRegular()
3040 assertx(couldBe(BObj
));
3041 assertx(subtypeOf(BObj
| kNonSupportBits
));
3042 assertx(!m_data
.dobj
.containsNonRegular());
3043 if (m_data
.dobj
.isExact()) {
3044 if (!m_data
.dobj
.cls().isSerialized()) {
3045 assertx(m_data
.dobj
.cls().mightBeRegular());
3047 } else if (m_data
.dobj
.isSub()) {
3048 if (!m_data
.dobj
.cls().isSerialized()) {
3049 assertx(m_data
.dobj
.cls().couldBeOverriddenByRegular());
3051 } else if (m_data
.dobj
.isIsect()) {
3052 // There's way more things we could verify here, but it gets
3053 // expensive (and requires the index).
3054 assertx(m_data
.dobj
.isect().size() > 1);
3055 for (auto const DEBUG_ONLY c
: m_data
.dobj
.isect()) {
3056 if (c
.isSerialized()) continue;
3057 assertx(c
.mightBeRegular() || c
.couldBeOverriddenByRegular());
3060 assertx(m_data
.dcls
.isIsectAndExact());
3061 // There's way more things we could verify here, but it gets
3062 // expensive (and requires the index).
3063 auto const DEBUG_ONLY
[e
, i
] = m_data
.dcls
.isectAndExact();
3064 assertx(!i
->empty());
3065 if (!e
.isSerialized()) {
3066 assertx(e
.isMissingDebug());
3067 assertx(e
.mightBeRegular() || e
.couldBeOverriddenByRegular());
3069 for (auto const DEBUG_ONLY c
: *i
) {
3070 if (c
.isSerialized()) continue;
3071 assertx(!c
.same(e
));
3072 assertx(!c
.hasCompleteChildren());
3073 assertx(c
.mightBeRegular() || c
.couldBeOverriddenByRegular());
3077 case DataTag::WaitHandle
:
3078 assertx(couldBe(BObj
));
3079 assertx(subtypeOf(BObj
| kNonSupportBits
));
3080 assertx(!m_data
.dwh
.isNull());
3081 // We need to know something relevant about the inner type if we
3082 // have a specialization.
3083 assertx(m_data
.dwh
->inner
.strictSubtypeOf(BInitCell
));
3084 assertx(!m_data
.dwh
->cls
.containsNonRegular());
3085 assertx(m_data
.dwh
->cls
.isSub());
3086 assertx(!m_data
.dwh
->cls
.isCtx());
3088 m_data
.dwh
->cls
.cls().name()->tsame(s_Awaitable
.get())
3090 assertx(m_data
.dwh
->cls
.cls().isSerialized() ||
3091 m_data
.dwh
->cls
.cls().isComplete());
3093 case DataTag::ArrLikeVal
: {
3094 assertx(m_data
.aval
->isStatic());
3095 assertx(!m_data
.aval
->empty());
3096 assertx(couldBe(BArrLikeN
));
3097 assertx(subtypeOf(BArrLikeN
| kNonSupportBits
));
3099 // If we know the type is a static array, we should know its
3100 // (static) specific array type.
3101 DEBUG_ONLY
auto const b
= bits() & BArrLikeN
;
3102 switch (m_data
.aval
->kind()) {
3103 case ArrayData::kDictKind
:
3104 case ArrayData::kBespokeDictKind
:
3105 assertx(b
== BSDictN
);
3107 case ArrayData::kVecKind
:
3108 case ArrayData::kBespokeVecKind
:
3109 assertx(b
== BSVecN
);
3111 case ArrayData::kKeysetKind
:
3112 case ArrayData::kBespokeKeysetKind
:
3113 assertx(b
== BSKeysetN
);
3115 case ArrayData::kNumKinds
:
3116 always_assert(false);
3119 // If the array is non-empty, the LegacyMark information should
3120 // match the static array precisely. This isn't the case if it
3121 // could be empty since the empty portion could have had different
3122 // LegaycMark information.
3123 if (!couldBe(BArrLikeE
)) {
3124 assertx(legacyMarkFromSArr(m_data
.aval
) == m_legacyMark
);
3129 case DataTag::ArrLikePacked
: {
3130 assertx(!m_data
.packed
->elems
.empty());
3131 assertx(couldBe(BArrLikeN
));
3132 assertx(subtypeOf(BArrLikeN
| kNonSupportBits
));
3133 if (m_data
.packed
->elems
.size() <= kMaxArrayCheck
) {
3134 DEBUG_ONLY
auto const vals
= allowedValBits(bits(), true);
3135 DEBUG_ONLY
auto const isKeyset
= subtypeAmong(BKeysetN
, BArrLikeN
);
3136 DEBUG_ONLY
auto const maybeKeyset
= couldBe(BKeysetN
);
3137 DEBUG_ONLY
auto idx
= size_t{0};
3138 for (DEBUG_ONLY
auto const& v
: m_data
.packed
->elems
) {
3139 assertx(!v
.is(BBottom
));
3140 assertx(v
.subtypeOf(vals
.first
));
3141 assertx(v
.couldBe(vals
.second
));
3142 assertx(IMPLIES(isKeyset
, v
== ival(idx
)));
3143 assertx(IMPLIES(maybeKeyset
, v
.couldBe(ival(idx
))));
3149 case DataTag::ArrLikeMap
: {
3150 assertx(!m_data
.map
->map
.empty());
3151 // ArrLikeMap cannot support Vec arrays, since it does not
3152 // contain any packed arrays.
3153 assertx(couldBe(BDictN
| BKeysetN
));
3154 assertx(subtypeOf(BDictN
| BKeysetN
| kNonSupportBits
));
3156 DEBUG_ONLY
auto const key
= allowedKeyBits(bits());
3157 DEBUG_ONLY
auto const val
= allowedValBits(bits(), false);
3158 DEBUG_ONLY
auto const isKeyset
= subtypeAmong(BKeysetN
, BArrLikeN
);
3159 DEBUG_ONLY
auto const maybeKeyset
= couldBe(BKeysetN
);
3161 if (m_data
.map
->map
.size() <= kMaxArrayCheck
) {
3162 DEBUG_ONLY
auto idx
= size_t{0};
3163 DEBUG_ONLY
auto packed
= true;
3164 for (DEBUG_ONLY
auto const& kv
: m_data
.map
->map
) {
3165 DEBUG_ONLY
auto const keyType
= map_key(kv
.first
, kv
.second
);
3166 assertx(!kv
.second
.val
.is(BBottom
));
3167 assertx(kv
.second
.val
.subtypeOf(val
.first
));
3168 assertx(kv
.second
.val
.couldBe(val
.second
));
3169 assertx(keyType
.subtypeOf(key
.first
));
3170 assertx(keyType
.couldBe(key
.second
));
3173 packed
= isIntType(kv
.first
.m_type
) && kv
.first
.m_data
.num
== idx
;
3177 assertx(IMPLIES(isKeyset
, keyType
== kv
.second
.val
));
3178 assertx(IMPLIES(maybeKeyset
, keyType
.couldBe(kv
.second
.val
)));
3180 // Map shouldn't have packed-like keys. If it does, it should be Packed
3185 // Optional elements are either both Bottom or both not
3186 assertx(m_data
.map
->optKey
.is(BBottom
) ==
3187 m_data
.map
->optVal
.is(BBottom
));
3188 if (!m_data
.map
->optKey
.is(BBottom
)) {
3189 assertx(m_data
.map
->optKey
.subtypeOf(key
.first
));
3190 assertx(m_data
.map
->optVal
.subtypeOf(val
.first
));
3191 assertx(IMPLIES(isKeyset
, m_data
.map
->optKey
== m_data
.map
->optVal
));
3192 // If the optional element has a key with specialized data, it
3193 // cannot be the same value as a known key.
3194 if (is_specialized_int(m_data
.map
->optKey
)) {
3195 DEBUG_ONLY
auto const tv
=
3196 make_tv
<KindOfInt64
>(ival_of(m_data
.map
->optKey
));
3197 assertx(m_data
.map
->map
.find(tv
) == m_data
.map
->map
.end());
3198 } else if (is_specialized_string(m_data
.map
->optKey
)) {
3199 DEBUG_ONLY
auto const tv
=
3200 make_tv
<KindOfPersistentString
>(sval_of(m_data
.map
->optKey
));
3201 assertx(m_data
.map
->map
.find(tv
) == m_data
.map
->map
.end());
3206 case DataTag::ArrLikePackedN
: {
3207 assertx(couldBe(BArrLikeN
));
3208 assertx(subtypeOf(BArrLikeN
| kNonSupportBits
));
3209 assertx(!m_data
.packedn
->type
.is(BBottom
));
3210 DEBUG_ONLY
auto const vals
= allowedValBits(bits(), true);
3211 DEBUG_ONLY
auto const isKeyset
= subtypeAmong(BKeysetN
, BArrLikeN
);
3212 DEBUG_ONLY
auto const maybeKeyset
= couldBe(BKeysetN
);
3213 assertx(m_data
.packedn
->type
.subtypeOf(vals
.first
));
3214 assertx(m_data
.packedn
->type
.couldBe(vals
.second
));
3215 assertx(IMPLIES(maybeKeyset
,
3216 !is_specialized_int(m_data
.packedn
->type
) ||
3217 ival_of(m_data
.packedn
->type
) == 0));
3218 assertx(IMPLIES(isKeyset
, !m_data
.packedn
->type
.hasData()));
3220 // If the only array bits are BVecN, then we already know the
3221 // array is packed. We only want a specialization if the value is
3222 // better than what the bits imply (either TInitCell or TInitUnc).
3223 if (subtypeAmong(BVecN
, BArrLikeN
)) {
3224 assertx(m_data
.packedn
->type
.strictSubtypeOf(vals
.first
));
3228 case DataTag::ArrLikeMapN
: {
3229 // MapN cannot contain just Vec, only a potential union of
3230 // Vec with other array types. MapN represents all possible
3231 // arrays, including packed arrays, but an array type of just
3232 // Vec implies the array is definitely packed, so we should be
3233 // using PackedN instead.
3234 assertx(couldBe(BDictN
| BKeysetN
));
3235 assertx(subtypeOf(BArrLikeN
| kNonSupportBits
));
3236 assertx(!m_data
.mapn
->key
.is(BBottom
));
3237 assertx(!m_data
.mapn
->val
.is(BBottom
));
3239 DEBUG_ONLY
auto const key
= allowedKeyBits(bits());
3240 DEBUG_ONLY
auto const val
= allowedValBits(bits(), false);
3241 DEBUG_ONLY
auto const isKeyset
= subtypeAmong(BKeysetN
, BArrLikeN
);
3242 DEBUG_ONLY
auto const maybeKeyset
= couldBe(BKeysetN
);
3244 assertx(m_data
.mapn
->key
.subtypeOf(key
.first
));
3245 assertx(m_data
.mapn
->key
.couldBe(key
.second
));
3246 assertx(m_data
.mapn
->val
.subtypeOf(val
.first
));
3247 assertx(m_data
.mapn
->val
.couldBe(val
.second
));
3249 // Either the key or the value need to be a strict subtype of what
3250 // the bits imply. MapN is already the most general specialized
3251 // array type. If both the key and value are not any better than
3252 // what the bits imply, we should not have a specialized type at
3253 // all (this is needed for == to be correct).
3254 assertx(m_data
.mapn
->key
.strictSubtypeOf(key
.first
) ||
3255 m_data
.mapn
->val
.strictSubtypeOf(val
.first
));
3257 // MapN shouldn't have a specialized key. If it does, then that
3258 // implies it only contains arrays of size 1, which means it
3259 // should be Map instead.
3260 assertx(!is_scalar_counted(m_data
.mapn
->key
));
3261 assertx(IMPLIES(maybeKeyset
, m_data
.mapn
->key
.couldBe(m_data
.mapn
->val
)));
3262 assertx(IMPLIES(isKeyset
, m_data
.mapn
->key
== m_data
.mapn
->val
));
3269 //////////////////////////////////////////////////////////////////////
3271 Type
wait_handle(Type inner
) {
3272 assertx(inner
.subtypeOf(BInitCell
));
3273 auto const wh
= res::Class::get(s_Awaitable
.get());
3274 assertx(wh
.isComplete());
3275 assertx(wh
.couldBeOverriddenByRegular());
3276 auto t
= Type
{ BObj
, LegacyMark::Bottom
};
3278 auto dcls
= DCls::MakeSub(wh
, false);
3279 if (!inner
.strictSubtypeOf(BInitCell
)) {
3280 construct(t
.m_data
.dobj
, std::move(dcls
));
3281 t
.m_dataTag
= DataTag::Obj
;
3285 copy_ptr
<DWaitHandle
>(std::move(dcls
), std::move(inner
))
3287 t
.m_dataTag
= DataTag::WaitHandle
;
3289 assertx(t
.checkInvariants());
3293 bool is_specialized_wait_handle(const Type
& t
) {
3294 return t
.m_dataTag
== DataTag::WaitHandle
;
3297 Type
wait_handle_inner(const Type
& t
) {
3298 assertx(is_specialized_wait_handle(t
));
3299 return t
.m_data
.dwh
->inner
;
3302 // Turn a DWaitHandle into the matching DObj specialization (IE,
3303 // dropping any awaited type knowledge).
3304 Type
demote_wait_handle(Type wh
) {
3305 assertx(is_specialized_wait_handle(wh
));
3306 auto t
= Type
{ wh
.bits(), wh
.m_legacyMark
};
3307 construct(t
.m_data
.dobj
, std::move(wh
.m_data
.dwh
->cls
));
3308 t
.m_dataTag
= DataTag::Obj
;
3309 assertx(!is_specialized_wait_handle(t
));
3310 assertx(is_specialized_obj(t
));
3314 Type
sval(SString val
) {
3315 assertx(val
->isStatic());
3316 auto r
= Type
{ BSStr
, LegacyMark::Bottom
};
3317 r
.m_data
.sval
= val
;
3318 r
.m_dataTag
= DataTag::Str
;
3319 assertx(r
.checkInvariants());
3323 Type
sval_nonstatic(SString val
) {
3324 assertx(val
->isStatic());
3325 auto r
= Type
{ BStr
, LegacyMark::Bottom
};
3326 r
.m_data
.sval
= val
;
3327 r
.m_dataTag
= DataTag::Str
;
3328 assertx(r
.checkInvariants());
3332 Type
sval_counted(SString val
) {
3333 assertx(val
->isStatic());
3334 auto r
= Type
{ BCStr
, LegacyMark::Bottom
};
3335 r
.m_data
.sval
= val
;
3336 r
.m_dataTag
= DataTag::Str
;
3337 assertx(r
.checkInvariants());
3341 Type
sempty() { return sval(staticEmptyString()); }
3342 Type
sempty_nonstatic() { return sval_nonstatic(staticEmptyString()); }
3343 Type
sempty_counted() { return sval_counted(staticEmptyString()); }
3345 Type
ival(int64_t val
) {
3346 auto r
= Type
{ BInt
, LegacyMark::Bottom
};
3347 r
.m_data
.ival
= val
;
3348 r
.m_dataTag
= DataTag::Int
;
3349 assertx(r
.checkInvariants());
3353 Type
dval(double val
) {
3354 auto r
= Type
{ BDbl
, LegacyMark::Bottom
};
3355 r
.m_data
.dval
= val
;
3356 r
.m_dataTag
= DataTag::Dbl
;
3357 assertx(r
.checkInvariants());
3361 Type
lazyclsval(SString val
) {
3362 auto r
= Type
{ BLazyCls
, LegacyMark::Bottom
};
3363 r
.m_data
.lazyclsval
= val
;
3364 r
.m_dataTag
= DataTag::LazyCls
;
3365 assertx(r
.checkInvariants());
3369 Type
enumclasslabelval(SString val
) {
3370 auto r
= Type
{ BEnumClassLabel
, LegacyMark::Bottom
};
3371 r
.m_data
.eclval
= val
;
3372 r
.m_dataTag
= DataTag::EnumClassLabel
;
3373 assertx(r
.checkInvariants());
3377 Type
vec_val(SArray val
) {
3378 assertx(val
->isStatic());
3379 assertx(val
->isVecType());
3380 auto const mark
= legacyMarkFromSArr(val
);
3381 if (val
->empty()) return Type
{ BSVecE
, mark
};
3382 auto t
= Type
{ BSVecN
, mark
};
3383 t
.m_data
.aval
= val
;
3384 t
.m_dataTag
= DataTag::ArrLikeVal
;
3385 assertx(t
.checkInvariants());
3389 Type
vec_empty() { return vec_val(staticEmptyVec()); }
3390 Type
some_vec_empty() {
3391 return Type
{ BVecE
, legacyMarkFromSArr(staticEmptyVec()) };
3394 Type
packedn_impl(trep bits
, LegacyMark mark
, Type elem
) {
3395 auto t
= Type
{ bits
, mark
};
3396 auto const valBits
= allowedValBits(bits
, true);
3397 assertx(elem
.subtypeOf(valBits
.first
));
3398 if (subtypeAmong(bits
, BVecN
, BArrLikeN
)) {
3399 if (!elem
.strictSubtypeOf(valBits
.first
)) return t
;
3401 construct_inner(t
.m_data
.packedn
, std::move(elem
));
3402 t
.m_dataTag
= DataTag::ArrLikePackedN
;
3403 assertx(t
.checkInvariants());
3407 Type
packed_impl(trep bits
, LegacyMark mark
, std::vector
<Type
> elems
) {
3408 assertx(!elems
.empty());
3409 auto t
= Type
{ bits
, mark
};
3410 construct_inner(t
.m_data
.packed
, std::move(elems
));
3411 t
.m_dataTag
= DataTag::ArrLikePacked
;
3412 assertx(t
.checkInvariants());
3416 Type
vec_n(Type ty
) {
3417 return packedn_impl(BVecN
, LegacyMark::Unmarked
, std::move(ty
));
3420 Type
svec_n(Type ty
) {
3421 return packedn_impl(BSVecN
, LegacyMark::Unmarked
, std::move(ty
));
3424 Type
vec(std::vector
<Type
> elems
) {
3427 LegacyMark::Unmarked
,
3432 Type
svec(std::vector
<Type
> elems
) {
3435 LegacyMark::Unmarked
,
3440 Type
dict_val(SArray val
) {
3441 assertx(val
->isStatic());
3442 assertx(val
->isDictType());
3443 auto const mark
= legacyMarkFromSArr(val
);
3444 if (val
->empty()) return Type
{ BSDictE
, mark
};
3445 auto t
= Type
{ BSDictN
, mark
};
3446 t
.m_data
.aval
= val
;
3447 t
.m_dataTag
= DataTag::ArrLikeVal
;
3448 assertx(t
.checkInvariants());
3452 Type
dict_empty() { return dict_val(staticEmptyDictArray()); }
3454 Type
some_dict_empty() {
3455 return Type
{ BDictE
, legacyMarkFromSArr(staticEmptyDictArray()) };
3458 Type
dict_map(MapElems m
, Type optKey
, Type optVal
) {
3461 LegacyMark::Unmarked
,
3468 Type
sdict_map(MapElems m
, Type optKey
, Type optVal
) {
3471 LegacyMark::Unmarked
,
3478 Type
dict_n(Type k
, Type v
) {
3481 LegacyMark::Unmarked
,
3487 Type
sdict_n(Type k
, Type v
) {
3490 LegacyMark::Unmarked
,
3496 Type
dict_packed(std::vector
<Type
> v
) {
3499 LegacyMark::Unmarked
,
3504 Type
sdict_packed(std::vector
<Type
> v
) {
3507 LegacyMark::Unmarked
,
3512 Type
dict_packedn(Type t
) {
3513 return packedn_impl(BDictN
, LegacyMark::Unmarked
, std::move(t
));
3516 Type
sdict_packedn(Type t
) {
3517 return packedn_impl(BSDictN
, LegacyMark::Unmarked
, std::move(t
));
3520 Type
keyset_val(SArray val
) {
3521 assertx(val
->isStatic());
3522 assertx(val
->isKeysetType());
3523 if (val
->empty()) return keyset_empty();
3524 auto r
= Type
{ BSKeysetN
, LegacyMark::Bottom
};
3525 r
.m_data
.aval
= val
;
3526 r
.m_dataTag
= DataTag::ArrLikeVal
;
3527 assertx(r
.checkInvariants());
3531 Type
keyset_empty() { return Type
{ BSKeysetE
, LegacyMark::Bottom
}; }
3532 Type
some_keyset_empty() { return Type
{ BKeysetE
, LegacyMark::Bottom
}; }
3534 Type
keyset_n(Type kv
) {
3535 assertx(kv
.subtypeOf(BArrKey
));
3545 Type
skeyset_n(Type kv
) {
3546 assertx(kv
.subtypeOf(BUncArrKey
));
3556 Type
keyset_map(MapElems m
) {
3566 Type
subObj(res::Class val
) {
3567 if (auto const w
= val
.withoutNonRegular()) {
3572 auto t
= Type
{ BObj
, LegacyMark::Bottom
};
3575 val
.couldBeOverriddenByRegular()
3576 ? DCls::MakeSub(val
, false)
3577 : DCls::MakeExact(val
, false)
3579 t
.m_dataTag
= DataTag::Obj
;
3580 assertx(t
.checkInvariants());
3584 Type
objExact(res::Class val
) {
3585 if (!val
.mightBeRegular()) return TBottom
;
3586 auto t
= Type
{ BObj
, LegacyMark::Bottom
};
3589 DCls::MakeExact(val
, false)
3591 t
.m_dataTag
= DataTag::Obj
;
3592 assertx(t
.checkInvariants());
3596 Type
subCls(res::Class val
, bool nonReg
) {
3597 if (!nonReg
|| !val
.mightContainNonRegular()) {
3598 if (auto const w
= val
.withoutNonRegular()) {
3605 auto r
= Type
{ BCls
, LegacyMark::Bottom
};
3608 (nonReg
? val
.couldBeOverridden() : val
.couldBeOverriddenByRegular())
3609 ? DCls::MakeSub(val
, nonReg
)
3610 : DCls::MakeExact(val
, nonReg
)
3612 r
.m_dataTag
= DataTag::Cls
;
3613 assertx(r
.checkInvariants());
3617 Type
clsExact(res::Class val
, bool nonReg
) {
3618 if (!nonReg
|| !val
.mightBeNonRegular()) {
3619 if (!val
.mightBeRegular()) return TBottom
;
3622 auto r
= Type
{ BCls
, LegacyMark::Bottom
};
3625 DCls::MakeExact(val
, nonReg
)
3627 r
.m_dataTag
= DataTag::Cls
;
3628 assertx(r
.checkInvariants());
3632 Type
isectObjInternal(DCls::IsectSet isect
) {
3633 // NB: No canonicalization done here. This is only used internally
3634 // and we assume the IsectSet is already canonicalized.
3635 assertx(isect
.size() > 1);
3636 auto t
= Type
{ BObj
, LegacyMark::Bottom
};
3637 construct(t
.m_data
.dobj
, DCls::MakeIsect(std::move(isect
), false));
3638 t
.m_dataTag
= DataTag::Obj
;
3639 assertx(t
.checkInvariants());
3643 Type
isectClsInternal(DCls::IsectSet isect
, bool nonReg
) {
3644 // NB: No canonicalization done here. This is only used internally
3645 // and we assume the IsectSet is already canonicalized.
3646 assertx(isect
.size() > 1);
3647 auto t
= Type
{ BCls
, LegacyMark::Bottom
};
3648 construct(t
.m_data
.dcls
, DCls::MakeIsect(std::move(isect
), nonReg
));
3649 t
.m_dataTag
= DataTag::Cls
;
3650 assertx(t
.checkInvariants());
3654 Type
isectAndExactObjInternal(res::Class exact
, DCls::IsectSet isect
) {
3655 assertx(exact
.isMissingDebug());
3656 assertx(!isect
.empty());
3657 auto t
= Type
{ BObj
, LegacyMark::Bottom
};
3660 DCls::MakeIsectAndExact(exact
, std::move(isect
), false)
3662 t
.m_dataTag
= DataTag::Obj
;
3663 assertx(t
.checkInvariants());
3667 Type
isectAndExactClsInternal(res::Class exact
,
3668 DCls::IsectSet isect
,
3670 assertx(exact
.isMissingDebug());
3671 assertx(!isect
.empty());
3672 auto t
= Type
{ BCls
, LegacyMark::Bottom
};
3675 DCls::MakeIsectAndExact(exact
, std::move(isect
), nonReg
)
3677 t
.m_dataTag
= DataTag::Cls
;
3678 assertx(t
.checkInvariants());
3682 Type
map_impl(trep bits
, LegacyMark mark
, MapElems m
,
3683 Type optKey
, Type optVal
) {
3684 assertx(!m
.empty());
3685 assertx(optKey
.is(BBottom
) == optVal
.is(BBottom
));
3687 // A Map cannot be packed, so if it is, use a different
3689 auto idx
= int64_t{0};
3691 for (auto const& p
: m
) {
3692 if (!isIntType(p
.first
.m_type
) || p
.first
.m_data
.num
!= idx
) {
3699 // The map is actually packed. If there's no optional elements, we
3700 // can turn it into a Packed.
3701 if (optKey
.is(BBottom
)) {
3702 std::vector
<Type
> elems
;
3703 for (auto& p
: m
) elems
.emplace_back(p
.second
.val
);
3704 return packed_impl(bits
, mark
, std::move(elems
));
3707 // There are optional elements. We cannot represent optionals in
3708 // packed representations, so we need to collapse the values into
3710 auto vals
= std::move(optVal
);
3711 for (auto const& p
: m
) vals
|= p
.second
.val
;
3713 // Special case, if the optional elements represent a single key,
3714 // and that key is next in packed order, we can use PackedN.
3715 if (auto const k
= tvCounted(optKey
)) {
3716 if (isIntType(k
->m_type
) && k
->m_data
.num
== idx
) {
3717 return packedn_impl(bits
, mark
, std::move(vals
));
3721 // Not known to be packed including the optional elements, so use
3722 // MapN, which is most general (it can contain packed and
3723 // non-packed types).
3727 union_of(idx
== 1 ? ival(0) : TInt
, optKey
),
3732 auto r
= Type
{ bits
, mark
};
3739 r
.m_dataTag
= DataTag::ArrLikeMap
;
3740 assertx(r
.checkInvariants());
3744 Type
mapn_impl(trep bits
, LegacyMark mark
, Type k
, Type v
) {
3745 assertx(k
.subtypeOf(BArrKey
));
3747 auto const keyBits
= allowedKeyBits(bits
);
3748 auto const valBits
= allowedValBits(bits
, false);
3749 assertx(k
.subtypeOf(keyBits
.first
));
3750 assertx(v
.subtypeOf(valBits
.first
));
3752 // A MapN cannot have a constant key (because that can actually make it be a
3753 // subtype of Map sometimes), so if it does, make it a Map instead.
3754 if (auto val
= tvCounted(k
)) {
3756 m
.emplace_back(*val
, MapElem::KeyFromType(k
, std::move(v
)));
3757 return map_impl(bits
, mark
, std::move(m
), TBottom
, TBottom
);
3760 auto r
= Type
{ bits
, mark
};
3761 if (!k
.strictSubtypeOf(keyBits
.first
) && !v
.strictSubtypeOf(valBits
.first
)) {
3770 r
.m_dataTag
= DataTag::ArrLikeMapN
;
3771 assertx(r
.checkInvariants());
3776 t
.m_bits
|= BInitNull
;
3777 assertx(t
.checkInvariants());
3781 Type
unopt(Type t
) {
3782 t
.m_bits
&= ~BInitNull
;
3783 assertx(t
.checkInvariants());
3787 Type
return_with_context(Type t
, Type context
) {
3788 assertx(t
.subtypeOf(BInitCell
));
3789 assertx(context
.subtypeOf(BObj
) || context
.subtypeOf(BCls
));
3791 if (context
.is(BBottom
)) return unctx(t
);
3793 if (t
.m_dataTag
== DataTag::Obj
&& t
.m_data
.dobj
.isCtx()) {
3794 if (!context
.subtypeOf(BObj
)) context
= toobj(context
);
3795 if (context
.m_dataTag
== DataTag::Obj
) {
3796 auto const& d
= dobj_of(context
);
3797 if (d
.isExact() && d
.cls().couldBeMocked()) {
3798 context
= subObj(d
.cls());
3801 auto [obj
, rest
] = split_obj(std::move(t
));
3803 intersection_of(unctx(std::move(obj
)), std::move(context
)),
3807 if (is_specialized_cls(t
) && t
.m_data
.dcls
.isCtx()) {
3808 if (!context
.subtypeOf(BCls
)) context
= objcls(context
);
3809 if (is_specialized_cls(context
)) {
3810 auto const& d
= dcls_of(context
);
3811 if (d
.isExact() && d
.cls().couldBeMocked()) {
3812 context
= subCls(d
.cls(), true);
3815 auto [cls
, rest
] = split_cls(std::move(t
));
3817 intersection_of(unctx(std::move(cls
)), std::move(context
)),
3824 Type
setctx(Type t
, bool to
) {
3825 if (t
.m_dataTag
== DataTag::Obj
) t
.m_data
.dobj
.setCtx(to
);
3826 if (is_specialized_cls(t
)) t
.m_data
.dcls
.setCtx(to
);
3830 Type
unctx(Type t
) {
3832 return Type::unctxHelper(t
, c
);
3835 bool is_specialized_array_like(const Type
& t
) {
3836 switch (t
.m_dataTag
) {
3839 case DataTag::LazyCls
:
3840 case DataTag::EnumClassLabel
:
3842 case DataTag::WaitHandle
:
3847 case DataTag::ArrLikeVal
:
3848 case DataTag::ArrLikePacked
:
3849 case DataTag::ArrLikePackedN
:
3850 case DataTag::ArrLikeMap
:
3851 case DataTag::ArrLikeMapN
:
3857 bool is_specialized_array_like_arrval(const Type
& t
) {
3858 return t
.m_dataTag
== DataTag::ArrLikeVal
;
3860 bool is_specialized_array_like_packedn(const Type
& t
) {
3861 return t
.m_dataTag
== DataTag::ArrLikePackedN
;
3863 bool is_specialized_array_like_packed(const Type
& t
) {
3864 return t
.m_dataTag
== DataTag::ArrLikePacked
;
3866 bool is_specialized_array_like_mapn(const Type
& t
) {
3867 return t
.m_dataTag
== DataTag::ArrLikeMapN
;
3869 bool is_specialized_array_like_map(const Type
& t
) {
3870 return t
.m_dataTag
== DataTag::ArrLikeMap
;
3873 bool is_specialized_obj(const Type
& t
) {
3875 t
.m_dataTag
== DataTag::Obj
||
3876 t
.m_dataTag
== DataTag::WaitHandle
;
3879 bool is_specialized_cls(const Type
& t
) {
3880 return t
.m_dataTag
== DataTag::Cls
;
3883 bool is_specialized_string(const Type
& t
) {
3884 return t
.m_dataTag
== DataTag::Str
;
3887 bool is_specialized_lazycls(const Type
& t
) {
3888 return t
.m_dataTag
== DataTag::LazyCls
;
3891 bool is_specialized_ecl(const Type
& t
) {
3892 return t
.m_dataTag
== DataTag::EnumClassLabel
;
3895 bool is_specialized_int(const Type
& t
) {
3896 return t
.m_dataTag
== DataTag::Int
;
3899 bool is_specialized_double(const Type
& t
) {
3900 return t
.m_dataTag
== DataTag::Dbl
;
3903 Type
toobj(const Type
& t
) {
3904 assertx(t
.subtypeOf(BCls
));
3905 assertx(!t
.subtypeOf(BBottom
));
3907 if (!is_specialized_cls(t
)) return TObj
;
3909 auto const& d
= dcls_of(t
);
3913 return objExact(d
.cls());
3914 } else if (d
.isSub()) {
3915 return subObj(d
.cls());
3916 } else if (d
.isIsect()) {
3917 if (!d
.containsNonRegular()) return isectObjInternal(d
.isect());
3918 auto const u
= res::Class::removeNonRegular(d
.isect());
3919 if (u
.empty()) return TBottom
;
3920 if (u
.size() == 1) return subObj(u
.front());
3921 DCls::IsectSet set
{u
.begin(), u
.end()};
3922 return isectObjInternal(std::move(set
));
3924 assertx(d
.isIsectAndExact());
3925 auto const [e
, i
] = d
.isectAndExact();
3926 if (!d
.containsNonRegular()) return isectAndExactObjInternal(e
, *i
);
3927 if (!e
.mightBeRegular()) return TBottom
;
3928 auto const u
= res::Class::removeNonRegular(*i
);
3929 if (u
.empty()) return TBottom
;
3930 DCls::IsectSet set
{u
.begin(), u
.end()};
3931 return isectAndExactObjInternal(e
, std::move(set
));
3938 Type
objcls(const Type
& t
) {
3939 assertx(t
.subtypeOf(BObj
));
3940 assertx(!t
.subtypeOf(BBottom
));
3941 if (!is_specialized_obj(t
)) return TCls
;
3942 auto const& d
= dobj_of(t
);
3943 assertx(!d
.containsNonRegular());
3944 auto r
= Type
{ BCls
, LegacyMark::Bottom
};
3945 construct(r
.m_data
.dcls
, d
);
3946 r
.m_dataTag
= DataTag::Cls
;
3947 return setctx(std::move(r
), d
.isCtx());
3950 //////////////////////////////////////////////////////////////////////
3952 Optional
<int64_t> arr_size(const Type
& t
) {
3953 if (t
.subtypeOf(BArrLikeE
)) return 0;
3954 if (!t
.subtypeOf(BArrLikeN
)) return std::nullopt
;
3956 switch (t
.m_dataTag
) {
3957 case DataTag::ArrLikeVal
:
3958 return t
.m_data
.aval
->size();
3960 case DataTag::ArrLikeMap
:
3961 if (t
.m_data
.map
->hasOptElements()) return std::nullopt
;
3962 return t
.m_data
.map
->map
.size();
3964 case DataTag::ArrLikePacked
:
3965 return t
.m_data
.packed
->elems
.size();
3971 case DataTag::LazyCls
:
3972 case DataTag::EnumClassLabel
:
3973 case DataTag::ArrLikePackedN
:
3974 case DataTag::ArrLikeMapN
:
3976 case DataTag::WaitHandle
:
3978 return std::nullopt
;
3983 Type::ArrayCat
categorize_array(const Type
& t
) {
3984 auto hasInts
= false;
3985 auto hasStrs
= false;
3986 auto isPacked
= true;
3987 // Even if all the values are constants, we can't produce a constant array
3988 // unless the d/varray-ness is definitely known.
3989 auto val
= t
.subtypeOf(BVec
) || t
.subtypeOf(BDict
) || t
.subtypeOf(BKeyset
);
3991 auto const checkKey
= [&] (const TypedValue
& key
) {
3992 if (isStringType(key
.m_type
)) {
3998 if (key
.m_data
.num
!= idx
++) isPacked
= false;
3999 return hasStrs
&& !isPacked
;
4003 switch (t
.m_dataTag
) {
4004 case DataTag::ArrLikeVal
:
4005 IterateKV(t
.m_data
.aval
,
4006 [&] (TypedValue k
, TypedValue
) {
4011 case DataTag::ArrLikeMap
:
4012 if (t
.m_data
.map
->hasOptElements()) return {};
4013 for (auto const& elem
: t
.m_data
.map
->map
) {
4014 if (checkKey(elem
.first
) && !val
) break;
4015 val
= val
&& tv(elem
.second
.val
);
4019 case DataTag::ArrLikePacked
:
4020 for (auto const& elem
: t
.m_data
.packed
->elems
) {
4022 val
= val
&& tv(elem
);
4031 case DataTag::LazyCls
:
4032 case DataTag::EnumClassLabel
:
4033 case DataTag::ArrLikePackedN
:
4034 case DataTag::ArrLikeMapN
:
4036 case DataTag::WaitHandle
:
4042 hasInts
? (isPacked
? Type::ArrayCat::Packed
: Type::ArrayCat::Mixed
) :
4043 hasStrs
? Type::ArrayCat::Struct
: Type::ArrayCat::Empty
;
4045 return { cat
, val
};
4048 CompactVector
<LSString
> get_string_keys(const Type
& t
) {
4049 CompactVector
<LSString
> strs
;
4051 switch (t
.m_dataTag
) {
4052 case DataTag::ArrLikeVal
:
4053 IterateKV(t
.m_data
.aval
,
4054 [&] (TypedValue k
, TypedValue
) {
4055 assertx(isStringType(k
.m_type
));
4056 strs
.push_back(k
.m_data
.pstr
);
4060 case DataTag::ArrLikeMap
:
4061 assertx(!t
.m_data
.map
->hasOptElements());
4062 for (auto const& elem
: t
.m_data
.map
->map
) {
4063 assertx(isStringType(elem
.first
.m_type
));
4064 strs
.push_back(elem
.first
.m_data
.pstr
);
4068 case DataTag::ArrLikePacked
:
4073 case DataTag::LazyCls
:
4074 case DataTag::EnumClassLabel
:
4075 case DataTag::ArrLikePackedN
:
4076 case DataTag::ArrLikeMapN
:
4078 case DataTag::WaitHandle
:
4080 always_assert(false);
4086 template<typename R
, bool force_static
, bool allow_counted
>
4088 template<DataType dt
,typename
... Args
>
4089 static R
make(Args
&&... args
) {
4090 return make_tv
<dt
>(std::forward
<Args
>(args
)...);
4092 template<typename
... Args
>
4093 static R
makePersistentArray(Args
&&... args
) {
4094 return make_persistent_array_like_tv(std::forward
<Args
>(args
)...);
4096 template<typename Init
, typename
... Args
>
4097 static R
fromMap(Args
&&... args
) {
4098 return fromTypeMap
<Init
, force_static
, allow_counted
>(
4099 std::forward
<Args
>(args
)...
4102 template<typename Init
, typename
... Args
>
4103 static R
fromVec(Args
&&... args
) {
4104 return fromTypeVec
<Init
, force_static
, allow_counted
>(
4105 std::forward
<Args
>(args
)...
4110 template<bool ignored
, bool allow_counted
>
4111 struct tvHelper
<bool, ignored
, allow_counted
> {
4112 template <DataType dt
, typename
... Args
>
4113 static bool make(Args
&&...) { return true; }
4114 template <typename
... Args
>
4115 static bool makePersistentArray(Args
&&...) { return true; }
4116 template<typename Init
, typename
... Args
>
4117 static bool fromMap(Args
&&... args
) {
4118 return checkTypeMap
<allow_counted
>(std::forward
<Args
>(args
)...);
4120 template<typename Init
, typename
... Args
>
4121 static bool fromVec(Args
&&... args
) {
4122 return checkTypeVec
<allow_counted
>(std::forward
<Args
>(args
)...);
4126 template<typename R
, bool force_static
, bool allow_counted
>
4127 R
tvImpl(const Type
& t
) {
4128 assertx(t
.checkInvariants());
4129 using H
= tvHelper
<R
, force_static
, allow_counted
>;
4131 auto const emptyArray
= [&] (auto unmarked
, auto marked
) {
4132 auto const mark
= legacyMark(t
.m_legacyMark
, t
.bits());
4133 if (mark
== LegacyMark::Unknown
) return R
{};
4135 auto const ad
= mark
== LegacyMark::Unmarked
? unmarked() : marked();
4136 assertx(ad
->empty());
4137 return H::makePersistentArray(ad
);
4141 case BUninit
: return H::template make
<KindOfUninit
>();
4142 case BInitNull
: return H::template make
<KindOfNull
>();
4143 case BTrue
: return H::template make
<KindOfBoolean
>(true);
4144 case BFalse
: return H::template make
<KindOfBoolean
>(false);
4147 return emptyArray(staticEmptyVec
, staticEmptyMarkedVec
);
4150 return emptyArray(staticEmptyDictArray
, staticEmptyMarkedDictArray
);
4153 return H::template make
<KindOfPersistentKeyset
>(staticEmptyKeysetArray());
4159 if (allow_counted
) {
4162 return emptyArray(staticEmptyVec
, staticEmptyMarkedVec
);
4164 return emptyArray(staticEmptyDictArray
, staticEmptyMarkedDictArray
);
4166 return H::template make
<KindOfPersistentKeyset
>(staticEmptyKeysetArray());
4172 switch (t
.m_dataTag
) {
4174 if (!t
.subtypeOf(BInt
)) break;
4175 return H::template make
<KindOfInt64
>(t
.m_data
.ival
);
4177 if (!t
.subtypeOf(BDbl
)) break;
4178 return H::template make
<KindOfDouble
>(t
.m_data
.dval
);
4180 if (!t
.subtypeOf(BStr
) || (!allow_counted
&& t
.subtypeOf(BCStr
))) break;
4181 return H::template make
<KindOfPersistentString
>(t
.m_data
.sval
);
4182 case DataTag::LazyCls
:
4183 if (!t
.subtypeOf(BLazyCls
)) break;
4184 return H::template make
<KindOfLazyClass
>(
4185 LazyClassData::create(t
.m_data
.lazyclsval
));
4186 case DataTag::EnumClassLabel
:
4187 if (!t
.subtypeOf(BEnumClassLabel
)) break;
4188 return H::template make
<KindOfEnumClassLabel
>(t
.m_data
.eclval
);
4189 case DataTag::ArrLikeVal
:
4190 // It's a Type invariant that the bits will be exactly one of
4191 // the array types with ArrLikeVal. We don't care which.
4192 if (!t
.subtypeOf(BArrLikeN
)) break;
4193 return H::makePersistentArray(const_cast<ArrayData
*>(t
.m_data
.aval
));
4194 case DataTag::ArrLikeMap
:
4195 if (t
.m_data
.map
->hasOptElements()) break;
4196 if (t
.subtypeOf(BDictN
) && (allow_counted
|| !t
.subtypeOf(BCDictN
))) {
4197 return H::template fromMap
<DictInit
>(t
.m_data
.map
->map
,
4200 } else if (t
.subtypeOf(BKeysetN
) &&
4201 (allow_counted
|| !t
.subtypeOf(BCKeysetN
))) {
4202 return H::template fromMap
<KeysetInit
>(t
.m_data
.map
->map
,
4207 case DataTag::ArrLikePacked
:
4208 if (t
.subtypeOf(BVecN
) &&
4209 (allow_counted
|| !t
.subtypeOf(BCVecN
))) {
4210 return H::template fromVec
<VecInit
>(t
.m_data
.packed
->elems
,
4213 } else if (t
.subtypeOf(BDictN
) &&
4214 (allow_counted
|| !t
.subtypeOf(BCDictN
))) {
4215 return H::template fromVec
<DictInit
>(t
.m_data
.packed
->elems
,
4218 } else if (t
.subtypeOf(BKeysetN
) &&
4219 (allow_counted
|| !t
.subtypeOf(BCKeysetN
))) {
4220 return H::template fromVec
<KeysetAppendInit
>(t
.m_data
.packed
->elems
,
4225 case DataTag::ArrLikePackedN
:
4226 case DataTag::ArrLikeMapN
:
4228 case DataTag::WaitHandle
:
4237 Optional
<TypedValue
> tv(const Type
& t
) {
4238 return tvImpl
<Optional
<TypedValue
>, true, false>(t
);
4241 Optional
<TypedValue
> tvNonStatic(const Type
& t
) {
4242 return tvImpl
<Optional
<TypedValue
>, false, false>(t
);
4245 Optional
<TypedValue
> tvCounted(const Type
& t
) {
4246 return tvImpl
<Optional
<TypedValue
>, true, true>(t
);
4249 bool is_scalar(const Type
& t
) {
4250 return tvImpl
<bool, true, false>(t
);
4253 bool is_scalar_counted(const Type
& t
) {
4254 return tvImpl
<bool, true, true>(t
);
4257 Type
scalarize(Type t
) {
4258 assertx(is_scalar(t
));
4260 switch (t
.m_dataTag
) {
4262 assertx(t
.subtypeOf(BNull
| BBool
| BArrLikeE
));
4263 t
.m_bits
&= (BNull
| BBool
| BSArrLikeE
);
4267 case DataTag::LazyCls
:
4268 case DataTag::EnumClassLabel
:
4270 case DataTag::ArrLikeVal
:
4271 t
.m_bits
&= BSArrLike
;
4276 case DataTag::ArrLikeMap
:
4277 case DataTag::ArrLikePacked
:
4278 return from_cell(*tv(t
));
4279 case DataTag::ArrLikePackedN
:
4280 case DataTag::ArrLikeMapN
:
4282 case DataTag::WaitHandle
:
4287 assertx(t
.checkInvariants());
4291 Type
type_of_istype(IsTypeOp op
) {
4293 case IsTypeOp::Null
: return TNull
;
4294 case IsTypeOp::Bool
: return TBool
;
4295 case IsTypeOp::Int
: return TInt
;
4296 case IsTypeOp::Dbl
: return TDbl
;
4297 case IsTypeOp::Str
: return union_of(TStr
, TCls
, TLazyCls
);
4298 case IsTypeOp::Res
: return TRes
;
4299 case IsTypeOp::Vec
: return TVec
;
4300 case IsTypeOp::Dict
: return TDict
;
4301 case IsTypeOp::Keyset
: return TKeyset
;
4302 case IsTypeOp::Obj
: return TObj
;
4303 case IsTypeOp::ClsMeth
: return union_of(TClsMeth
, TRClsMeth
);
4304 case IsTypeOp::Class
: return union_of(TCls
, TLazyCls
);
4305 case IsTypeOp::Func
: return union_of(TFunc
, TRFunc
);
4306 case IsTypeOp::ArrLike
: return TArrLike
;
4307 case IsTypeOp::Scalar
: always_assert(false);
4308 case IsTypeOp::LegacyArrLike
: always_assert(false);
4313 Optional
<IsTypeOp
> type_to_istypeop(const Type
& t
) {
4314 if (t
.subtypeOf(BNull
)) return IsTypeOp::Null
;
4315 if (t
.subtypeOf(BBool
)) return IsTypeOp::Bool
;
4316 if (t
.subtypeOf(BInt
)) return IsTypeOp::Int
;
4317 if (t
.subtypeOf(BDbl
)) return IsTypeOp::Dbl
;
4318 if (t
.subtypeOf(BStr
)) return IsTypeOp::Str
;
4319 if (t
.subtypeOf(BVec
)) return IsTypeOp::Vec
;
4320 if (t
.subtypeOf(BDict
)) return IsTypeOp::Dict
;
4321 if (t
.subtypeOf(BRes
)) return IsTypeOp::Res
;
4322 if (t
.subtypeOf(BKeyset
)) return IsTypeOp::Keyset
;
4323 if (t
.subtypeOf(BObj
)) return IsTypeOp::Obj
;
4324 if (t
.subtypeOf(BClsMeth
)) return IsTypeOp::ClsMeth
;
4325 if (t
.subtypeOf(BCls
)) return IsTypeOp::Class
;
4326 if (t
.subtypeOf(BLazyCls
)) return IsTypeOp::Class
;
4327 if (t
.subtypeOf(BFunc
)) return IsTypeOp::Func
;
4328 return std::nullopt
;
4331 Optional
<Type
> type_of_type_structure(const IIndex
& index
,
4334 auto base
= [&] () -> Optional
<Type
> {
4335 switch (get_ts_kind(ts
)) {
4336 case TypeStructure::Kind::T_int
: return TInt
;
4337 case TypeStructure::Kind::T_bool
: return TBool
;
4338 case TypeStructure::Kind::T_float
: return TDbl
;
4339 case TypeStructure::Kind::T_string
: return union_of(TStr
,TCls
,TLazyCls
);
4340 case TypeStructure::Kind::T_resource
: return TRes
;
4341 case TypeStructure::Kind::T_num
: return TNum
;
4342 case TypeStructure::Kind::T_arraykey
: return TArrKey
;
4343 case TypeStructure::Kind::T_dict
: return TDict
;
4344 case TypeStructure::Kind::T_vec
: return TVec
;
4345 case TypeStructure::Kind::T_keyset
: return TKeyset
;
4346 case TypeStructure::Kind::T_void
:
4347 case TypeStructure::Kind::T_null
: return TNull
;
4348 case TypeStructure::Kind::T_tuple
: {
4349 auto const tsElems
= get_ts_elem_types(ts
);
4350 std::vector
<Type
> v
;
4351 for (auto i
= 0; i
< tsElems
->size(); i
++) {
4352 auto t
= type_of_type_structure(
4353 index
, ctx
, tsElems
->getValue(i
).getArrayData());
4354 if (!t
) return std::nullopt
;
4355 v
.emplace_back(remove_uninit(std::move(t
.value())));
4357 if (v
.empty()) return std::nullopt
;
4360 case TypeStructure::Kind::T_shape
: {
4361 // Taking a very conservative approach to shapes where we dont do any
4362 // conversions if the shape contains unknown or optional fields
4363 if (does_ts_shape_allow_unknown_fields(ts
)) return std::nullopt
;
4364 auto map
= MapElems
{};
4365 auto const fields
= get_ts_fields(ts
);
4366 for (auto i
= 0; i
< fields
->size(); i
++) {
4367 auto const keyV
= fields
->getKey(i
);
4368 if (!keyV
.isString()) return std::nullopt
;
4369 auto key
= keyV
.getStringData();
4370 auto const wrapper
= fields
->getValue(i
).getArrayData();
4372 // Shapes can be defined using class constants, these keys
4373 // must be resolved, and to side-step the issue of shapes
4374 // potentially being packed arrays if the keys are
4375 // consecutive integers beginning with 0, we allow only keys
4376 // that resolve to strings here.
4377 if (wrapper
->exists(s_is_cls_cns
)) {
4378 std::string cls
, cns
;
4379 auto const matched
= folly::split("::", key
->data(), cls
, cns
);
4380 always_assert(matched
);
4382 auto const rcls
= index
.resolve_class(makeStaticString(cls
));
4383 if (!rcls
) return std::nullopt
;
4385 auto const lookup
= index
.lookup_class_constant(
4387 clsExact(*rcls
, true),
4388 sval(makeStaticString(cns
))
4390 if (lookup
.found
!= TriBool::Yes
|| lookup
.mightThrow
) {
4391 return std::nullopt
;
4394 auto const vcns
= tv(lookup
.ty
);
4395 if (!vcns
|| !isStringType(type(*vcns
))) return std::nullopt
;
4396 key
= val(*vcns
).pstr
;
4399 // Optional fields are hard to represent as a type
4400 if (is_optional_ts_shape_field(wrapper
)) return std::nullopt
;
4402 auto const value
= [&] () -> SArray
{
4403 auto const v
= wrapper
->get(s_value
);
4404 if (!v
.is_init()) return wrapper
;
4405 if (!tvIsDict(v
)) return nullptr;
4408 if (!value
) return std::nullopt
;
4410 auto t
= type_of_type_structure(index
, ctx
, value
);
4411 if (!t
) return std::nullopt
;
4414 make_tv
<KindOfPersistentString
>(key
),
4415 MapElem::SStrKey(remove_uninit(std::move(t
.value())))
4418 if (map
.empty()) return std::nullopt
;
4419 return dict_map(map
);
4421 case TypeStructure::Kind::T_union
: {
4422 auto const tsTypes
= get_ts_union_types(ts
);
4424 for (auto i
= 0; i
< tsTypes
->size(); i
++) {
4425 auto t
= type_of_type_structure(
4426 index
, ctx
, tsTypes
->getValue(i
).getArrayData());
4427 if (!t
) return std::nullopt
;
4432 case TypeStructure::Kind::T_recursiveUnion
: {
4433 // Since our type can't cleanly represent a recursive type be
4434 // conservative here and bail.
4435 return std::nullopt
;
4437 case TypeStructure::Kind::T_vec_or_dict
: return union_of(TVec
, TDict
);
4438 case TypeStructure::Kind::T_any_array
: return TArrLike
;
4439 case TypeStructure::Kind::T_nothing
:
4440 case TypeStructure::Kind::T_noreturn
:
4441 case TypeStructure::Kind::T_mixed
:
4442 case TypeStructure::Kind::T_dynamic
:
4443 case TypeStructure::Kind::T_nonnull
:
4444 case TypeStructure::Kind::T_class
:
4445 case TypeStructure::Kind::T_interface
:
4446 case TypeStructure::Kind::T_unresolved
:
4447 case TypeStructure::Kind::T_typeaccess
:
4448 case TypeStructure::Kind::T_darray
:
4449 case TypeStructure::Kind::T_varray
:
4450 case TypeStructure::Kind::T_varray_or_darray
:
4451 case TypeStructure::Kind::T_xhp
:
4452 case TypeStructure::Kind::T_enum
:
4453 case TypeStructure::Kind::T_fun
:
4454 case TypeStructure::Kind::T_typevar
:
4455 case TypeStructure::Kind::T_trait
:
4456 case TypeStructure::Kind::T_reifiedtype
:
4457 return std::nullopt
;
4461 if (base
&& is_ts_nullable(ts
)) base
= opt(std::move(*base
));
4465 const DCls
& dobj_of(const Type
& t
) {
4466 assertx(t
.checkInvariants());
4467 assertx(is_specialized_obj(t
));
4468 if (t
.m_dataTag
== DataTag::Obj
) return t
.m_data
.dobj
;
4469 assertx(is_specialized_wait_handle(t
));
4470 return t
.m_data
.dwh
->cls
;
4473 const DCls
& dcls_of(const Type
& t
) {
4474 assertx(t
.checkInvariants());
4475 assertx(is_specialized_cls(t
));
4476 return t
.m_data
.dcls
;
4479 SString
sval_of(const Type
& t
) {
4480 assertx(t
.checkInvariants());
4481 assertx(is_specialized_string(t
));
4482 return t
.m_data
.sval
;
4485 SString
lazyclsval_of(const Type
& t
) {
4486 assertx(t
.checkInvariants());
4487 assertx(is_specialized_lazycls(t
));
4488 return t
.m_data
.lazyclsval
;
4491 SString
eclval_of(const Type
& t
) {
4492 assertx(t
.checkInvariants());
4493 assertx(is_specialized_ecl(t
));
4494 return t
.m_data
.eclval
;
4497 int64_t ival_of(const Type
& t
) {
4498 assertx(t
.checkInvariants());
4499 assertx(is_specialized_int(t
));
4500 return t
.m_data
.ival
;
4503 Type
from_cell(TypedValue cell
) {
4504 assertx(tvIsPlausible(cell
));
4506 switch (cell
.m_type
) {
4507 case KindOfUninit
: return TUninit
;
4508 case KindOfNull
: return TInitNull
;
4509 case KindOfBoolean
: return cell
.m_data
.num
? TTrue
: TFalse
;
4510 case KindOfInt64
: return ival(cell
.m_data
.num
);
4511 case KindOfDouble
: return dval(cell
.m_data
.dbl
);
4513 case KindOfPersistentString
:
4515 always_assert(cell
.m_data
.pstr
->isStatic());
4516 return sval(cell
.m_data
.pstr
);
4518 case KindOfPersistentVec
:
4520 always_assert(cell
.m_data
.parr
->isStatic());
4521 always_assert(cell
.m_data
.parr
->isVecType());
4522 return vec_val(cell
.m_data
.parr
);
4524 case KindOfPersistentDict
:
4526 always_assert(cell
.m_data
.parr
->isStatic());
4527 always_assert(cell
.m_data
.parr
->isDictType());
4528 return dict_val(cell
.m_data
.parr
);
4530 case KindOfPersistentKeyset
:
4532 always_assert(cell
.m_data
.parr
->isStatic());
4533 always_assert(cell
.m_data
.parr
->isKeysetType());
4534 return keyset_val(cell
.m_data
.parr
);
4536 case KindOfLazyClass
: return lazyclsval(cell
.m_data
.plazyclass
.name());
4538 case KindOfEnumClassLabel
:
4539 always_assert(cell
.m_data
.pstr
->isStatic());
4540 return enumclasslabelval(cell
.m_data
.pstr
);
4543 case KindOfResource
:
4548 case KindOfRClsMeth
:
4552 0 && "reference counted/class/func/clsmeth type in from_cell");
4555 Type
from_DataType(DataType dt
) {
4557 case KindOfUninit
: return TUninit
;
4558 case KindOfNull
: return TInitNull
;
4559 case KindOfBoolean
: return TBool
;
4560 case KindOfInt64
: return TInt
;
4561 case KindOfDouble
: return TDbl
;
4562 case KindOfPersistentString
:
4563 case KindOfString
: return TStr
;
4564 case KindOfPersistentVec
:
4565 case KindOfVec
: return TVec
;
4566 case KindOfPersistentDict
:
4567 case KindOfDict
: return TDict
;
4568 case KindOfPersistentKeyset
:
4569 case KindOfKeyset
: return TKeyset
;
4570 case KindOfObject
: return TObj
;
4571 case KindOfResource
: return TRes
;
4572 case KindOfRFunc
: return TRFunc
;
4573 case KindOfFunc
: return TFunc
;
4574 case KindOfClass
: return TCls
;
4575 case KindOfLazyClass
: return TLazyCls
;
4576 case KindOfClsMeth
: return TClsMeth
;
4577 case KindOfRClsMeth
: return TRClsMeth
;
4578 case KindOfEnumClassLabel
: return TEnumClassLabel
;
4580 always_assert(0 && "dt in from_DataType didn't satisfy preconditions");
4583 Type
from_hni_constraint(SString s
) {
4584 if (!s
) return TCell
;
4590 ret
= opt(std::move(ret
));
4594 if (!tstrcmp(p
, annotTypeName(AnnotType::Null
))) return opt(std::move(ret
));
4595 if (!tstrcmp(p
, annotTypeName(AnnotType::Object
))) return union_of(std::move(ret
), TObj
);
4596 if (!tstrcmp(p
, annotTypeName(AnnotType::Resource
))) return union_of(std::move(ret
), TRes
);
4597 if (!tstrcmp(p
, annotTypeName(AnnotType::Bool
))) return union_of(std::move(ret
), TBool
);
4598 if (!tstrcmp(p
, annotTypeName(AnnotType::Int
))) return union_of(std::move(ret
), TInt
);
4599 if (!tstrcmp(p
, annotTypeName(AnnotType::Float
))) return union_of(std::move(ret
), TDbl
);
4600 if (!tstrcmp(p
, annotTypeName(AnnotType::Number
))) return union_of(std::move(ret
), TNum
);
4601 if (!tstrcmp(p
, annotTypeName(AnnotType::String
))) return union_of(std::move(ret
), TStr
);
4602 if (!tstrcmp(p
, annotTypeName(AnnotType::ArrayKey
))) return union_of(std::move(ret
), TArrKey
);
4603 if (!tstrcmp(p
, annotTypeName(AnnotType::Dict
))) return union_of(std::move(ret
), TDict
);
4604 if (!tstrcmp(p
, annotTypeName(AnnotType::Vec
))) return union_of(std::move(ret
), TVec
);
4605 if (!tstrcmp(p
, annotTypeName(AnnotType::Keyset
))) return union_of(std::move(ret
), TKeyset
);
4606 if (!tstrcmp(p
, kAnnotTypeVarrayStr
)) {
4607 return union_of(std::move(ret
), TVec
);
4609 if (!tstrcmp(p
, kAnnotTypeDarrayStr
)) {
4610 return union_of(std::move(ret
), TDict
);
4612 if (!tstrcmp(p
, kAnnotTypeVarrayOrDarrayStr
)) {
4613 return union_of(std::move(ret
), TVec
, TDict
);
4615 if (!tstrcmp(p
, annotTypeName(AnnotType::VecOrDict
))) {
4616 return union_of(std::move(ret
), TVec
, TDict
);
4618 if (!tstrcmp(p
, annotTypeName(AnnotType::ArrayLike
))) {
4619 return union_of(std::move(ret
), TArrLike
);
4621 if (!tstrcmp(p
, annotTypeName(AnnotType::Classname
))) {
4622 if (!Cfg::Eval::ClassPassesClassname
) {
4623 return union_of(ret
, TStr
);
4625 return union_of(ret
, union_of(TStr
, union_of(TCls
, TLazyCls
)));
4627 if (!tstrcmp(p
, annotTypeName(AnnotType::Mixed
))) return TInitCell
;
4628 if (!tstrcmp(p
, annotTypeName(AnnotType::Nonnull
))) return union_of(std::move(ret
), TNonNull
);
4630 // It might be an object, or we might want to support type aliases in HNI at
4631 // some point. For now just be conservative.
4635 Type
intersection_of(Type a
, Type b
) {
4636 using HPHP::HHBBC::couldBe
;
4638 auto isect
= a
.bits() & b
.bits();
4639 if (!isect
) return TBottom
;
4641 auto mark
= intersectionOf(
4642 project(a
.m_legacyMark
, isect
),
4643 project(b
.m_legacyMark
, isect
)
4645 if (couldBe(isect
, Type::kLegacyMarkBits
) &&
4646 mark
== LegacyMark::Bottom
) {
4647 isect
&= ~Type::kLegacyMarkBits
;
4648 if (!isect
) return TBottom
;
4649 a
= remove_bits(std::move(a
), Type::kLegacyMarkBits
);
4650 b
= remove_bits(std::move(b
), Type::kLegacyMarkBits
);
4651 assertx(!a
.is(BBottom
));
4652 assertx(!b
.is(BBottom
));
4655 // Return intersected type without a specialization.
4656 auto const nodata
= [&] {
4658 return Type
{ isect
, mark
};
4660 // If the intersection cannot support a specialization, there's no
4661 // need to check them.
4662 if (!couldBe(isect
, kSupportBits
)) return nodata();
4663 if (!a
.hasData() && !b
.hasData()) return nodata();
4665 // Return intersected type re-using the specialization in the given
4666 // type. Update the bits to match the intersection.
4667 auto const reuse
= [&] (Type
& dst
) {
4669 dst
.m_legacyMark
= mark
;
4670 assertx(dst
.checkInvariants());
4671 return std::move(dst
);
4674 // Try to determine if the given wait-handle and given specialized
4675 // object are a subtype of either. If so, return the (reused) more
4676 // specific type. Return std::nullopt if neither are.
4677 auto const whAndObj
= [&] (Type
& wh
, Type
& obj
) -> Optional
<Type
> {
4678 // The order of checks is important here. If the obj is the
4679 // Awaitable object, then both subtype checks will pass (because
4680 // they're equal), but we should reuse the wait-handle in that
4681 // case, so check that first.
4682 if (subtypeCls
<true>(wh
.m_data
.dwh
->cls
, obj
.m_data
.dobj
)) return reuse(wh
);
4683 if (subtypeCls
<true>(obj
.m_data
.dobj
, wh
.m_data
.dwh
->cls
)) return reuse(obj
);
4684 return std::nullopt
;
4687 // If both sides have matching specialized data, check if the
4688 // specializations match. If so, reuse one of the sides. If not, the
4689 // supported bits for this data cannot be present in the
4690 // intersection, so remove it. If this makes the intersection
4691 // TBottom, we're done. Otherwise, just return nodata() (the
4692 // intersection cannot possibly have any specialized data because
4693 // each side can only have one and we already determined they don't
4694 // match). If only one side has a specialization, check if that
4695 // specialization is supported by the intersection. If so, we can
4696 // keep it. If not, ignore it and check for other specialized
4697 // types. Note that this means the order of checking for
4698 // specializations determines the priority of which specializations
4699 // to keep when there's a mismatch.
4701 // For WaitHandles, first check if one is potentially a subtype of
4702 // the other (even if one is a TObj). If not, demote the wait handle
4703 // to an object specialization and fall into the below object
4704 // specialization checks.
4705 if (is_specialized_wait_handle(a
)) {
4706 if (is_specialized_wait_handle(b
)) {
4707 assertx(couldBe(isect
, BObj
));
4708 assertx(a
.m_data
.dwh
->cls
.same(b
.m_data
.dwh
->cls
));
4709 if (a
.m_data
.dwh
->inner
.subtypeOf(b
.m_data
.dwh
->inner
)) {
4712 if (b
.m_data
.dwh
->inner
.subtypeOf(a
.m_data
.dwh
->inner
)) {
4715 auto i
= intersection_of(
4716 a
.m_data
.dwh
->inner
,
4719 if (i
.strictSubtypeOf(BInitCell
)) {
4720 a
.m_data
.dwh
.mutate()->inner
= std::move(i
);
4723 a
= demote_wait_handle(std::move(a
));
4726 if (is_specialized_obj(b
)) {
4727 assertx(couldBe(isect
, BObj
));
4728 if (auto const t
= whAndObj(a
, b
)) return *t
;
4729 a
= demote_wait_handle(std::move(a
));
4730 } else if (couldBe(isect
, BObj
)) {
4733 } else if (is_specialized_wait_handle(b
)) {
4734 if (is_specialized_obj(a
)) {
4735 assertx(couldBe(isect
, BObj
));
4736 if (auto const t
= whAndObj(b
, a
)) return *t
;
4737 b
= demote_wait_handle(std::move(b
));
4738 } else if (couldBe(isect
, BObj
)) {
4743 auto const isectDCls
= [&] (DCls
& acls
, DCls
& bcls
, bool isObj
) {
4744 auto const fail
= [&] {
4745 isect
&= isObj
? ~BObj
: ~BCls
;
4746 return isect
? nodata() : TBottom
;
4749 auto const ctx
= acls
.isCtx() || bcls
.isCtx();
4750 if (subtypeCls
<false>(acls
, bcls
)) return setctx(reuse(a
), ctx
);
4751 if (subtypeCls
<false>(bcls
, acls
)) return setctx(reuse(b
), ctx
);
4752 if (!couldBeCls(acls
, bcls
)) return fail();
4754 auto const nonRegA
= acls
.containsNonRegular();
4755 auto const nonRegB
= bcls
.containsNonRegular();
4757 auto isectNonReg
= nonRegA
&& nonRegB
;
4759 // Exact classes should have been definitively resolved by one of
4760 // the above checks. The exception is if we have unresolved
4761 // classes and the other class isn't exact. In that case, the
4762 // intersection is just the unresolved class. Since the unresolved
4763 // class is exact, any intersection must contain only it (or be
4766 auto const handleExact
= [&] (DCls
& exact
, DCls
& sub
, bool subNonReg
) {
4767 assertx(exact
.isExact());
4768 assertx(exact
.cls().isMissingDebug());
4769 assertx(!sub
.isExact());
4771 auto const ecls
= exact
.cls();
4772 if (!isectNonReg
&& !ecls
.mightBeRegular()) return fail();
4776 auto scls
= sub
.cls();
4777 if (!isectNonReg
&& subNonReg
) {
4778 auto const w
= scls
.withoutNonRegular();
4779 if (!w
) return fail();
4782 set
.emplace_back(scls
);
4783 } else if (sub
.isIsect()) {
4784 if (!isectNonReg
&& subNonReg
) {
4785 auto const u
= res::Class::removeNonRegular(sub
.isect());
4786 if (u
.empty()) return fail();
4787 set
.insert(std::end(set
), std::begin(u
), std::end(u
));
4792 assertx(sub
.isIsectAndExact());
4793 auto const [ecls2
, i
] = sub
.isectAndExact();
4795 auto e
= isObj
? objExact(ecls
) : clsExact(ecls
, isectNonReg
);
4796 if (e
.is(BBottom
)) return fail();
4797 auto e2
= isObj
? objExact(ecls2
) : clsExact(ecls2
, isectNonReg
);
4798 if (e2
.is(BBottom
)) return fail();
4800 auto rhs
= [&, i
=i
] {
4801 if (i
->size() == 1) {
4803 ? subObj(i
->front())
4804 : subCls(i
->front(), isectNonReg
);
4806 DCls::IsectSet set
{i
->begin(), i
->end()};
4808 ? isectObjInternal(std::move(set
))
4809 : isectClsInternal(std::move(set
), isectNonReg
);
4812 if (rhs
.is(BBottom
)) return fail();
4814 auto ret
= intersection_of(
4815 intersection_of(std::move(e
), std::move(e2
)),
4818 if (ret
.is(BBottom
)) return fail();
4819 return setctx(reuse(ret
), ctx
);
4824 begin(set
), end(set
),
4825 [&] (res::Class c
) { return c
.same(ecls
); }
4833 : isectAndExactObjInternal(ecls
, std::move(set
))
4836 ? clsExact(ecls
, isectNonReg
)
4837 : isectAndExactClsInternal(ecls
, std::move(set
), isectNonReg
)
4839 if (ret
.is(BBottom
)) return fail();
4840 return setctx(reuse(ret
), ctx
);
4843 auto const handleIsectAndExact
= [&] (DCls
& isectExact
, Type rhs
) {
4844 assertx(isectExact
.isIsectAndExact());
4846 auto const [e
, i
] = isectExact
.isectAndExact();
4848 isObj
? objExact(e
) : clsExact(e
, isectNonReg
);
4849 if (exact
.is(BBottom
)) return fail();
4851 auto lhs
= [&, i
=i
] {
4852 if (i
->size() == 1) {
4854 ? subObj(i
->front())
4855 : subCls(i
->front(), isectNonReg
);
4857 DCls::IsectSet set
{i
->begin(), i
->end()};
4859 ? isectObjInternal(std::move(set
))
4860 : isectClsInternal(std::move(set
), isectNonReg
);
4863 if (lhs
.is(BBottom
)) return fail();
4865 auto ret
= intersection_of(
4866 intersection_of(std::move(lhs
), std::move(rhs
)),
4869 if (ret
.is(BBottom
)) return fail();
4870 return setctx(reuse(ret
), ctx
);
4873 if (acls
.isExact()) {
4874 return handleExact(acls
, bcls
, nonRegB
);
4875 } else if (bcls
.isExact()) {
4876 return handleExact(bcls
, acls
, nonRegA
);
4877 } else if (acls
.isIsectAndExact()) {
4878 return handleIsectAndExact(acls
, std::move(b
));
4879 } else if (bcls
.isIsectAndExact()) {
4880 return handleIsectAndExact(bcls
, std::move(a
));
4883 auto const i
= [&] {
4884 if (acls
.isIsect()) {
4885 if (bcls
.isIsect()) {
4886 return res::Class::intersect(
4894 return res::Class::intersect(
4896 std::array
<res::Class
, 1>{bcls
.cls()},
4902 } else if (bcls
.isIsect()) {
4903 return res::Class::intersect(
4904 std::array
<res::Class
, 1>{acls
.cls()},
4911 return res::Class::intersect(
4912 std::array
<res::Class
, 1>{acls
.cls()},
4913 std::array
<res::Class
, 1>{bcls
.cls()},
4921 // Empty list here means the intersection is empty, which
4922 // shouldn't happen because we already checked that they could be
4924 assertx(!i
.empty());
4925 assertx(IMPLIES(!nonRegA
|| !nonRegB
, !isectNonReg
));
4926 if (i
.size() == 1) {
4929 : subCls(i
.front(), isectNonReg
);
4930 return setctx(reuse(ret
), ctx
);
4933 DCls::IsectSet set
{i
.begin(), i
.end()};
4935 ? isectObjInternal(std::move(set
))
4936 : isectClsInternal(std::move(set
), isectNonReg
);
4937 return setctx(reuse(ret
), ctx
);
4940 if (is_specialized_obj(a
)) {
4941 if (is_specialized_obj(b
)) {
4942 assertx(!is_specialized_wait_handle(a
));
4943 assertx(!is_specialized_wait_handle(b
));
4944 assertx(couldBe(isect
, BObj
));
4945 return isectDCls(a
.m_data
.dobj
, b
.m_data
.dobj
, true);
4947 if (couldBe(isect
, BObj
)) return reuse(a
);
4948 } else if (is_specialized_obj(b
)) {
4949 if (couldBe(isect
, BObj
)) return reuse(b
);
4952 if (is_specialized_cls(a
)) {
4953 if (is_specialized_cls(b
)) {
4954 assertx(couldBe(isect
, BCls
));
4955 return isectDCls(a
.m_data
.dcls
, b
.m_data
.dcls
, false);
4957 if (couldBe(isect
, BCls
)) return reuse(a
);
4958 } else if (is_specialized_cls(b
)) {
4959 if (couldBe(isect
, BCls
)) return reuse(b
);
4962 // Attempt to re-use t or intersect it with the isect bits.
4963 auto const adjustArrSpec
= [&] (Type
& t
) {
4964 if (t
.m_dataTag
== DataTag::ArrLikeVal
) {
4965 // ArrLikeVal doesn't require any intersection
4966 if (t
.couldBe(BArrLikeE
) && !couldBe(isect
, BArrLikeE
)) {
4967 // If the intersection stripped empty bits off leaving just a
4968 // ArrLikeVal, we need to restore the precise LegacyMark.
4969 mark
= legacyMarkFromSArr(t
.m_data
.aval
);
4973 // Optimization: if t's existing trep is the same as the
4974 // intersection (array wise), the intersection won't modify
4975 // anything, so we can skip it.
4976 if ((t
.bits() & BArrLikeN
) == (isect
& BArrLikeN
)) {
4979 // Otherwise we can't reuse t and must perform the intersection.
4980 return Type
{isect
}.dispatchArrLikeNone(
4981 t
, DualDispatchIntersection
{ isect
, mark
}
4985 // Arrays need more care because we have to intersect the
4986 // specialization with a DArrNone to constrain the specialization
4987 // types appropriately.
4988 if (is_specialized_array_like(a
)) {
4989 if (is_specialized_array_like(b
)) {
4990 assertx(couldBe(isect
, BArrLikeN
));
4991 auto const i
= [&] {
4992 if (a
.dualDispatchDataFn(b
, DualDispatchSubtype
<true>{})) {
4993 return adjustArrSpec(a
);
4995 if (b
.dualDispatchDataFn(a
, DualDispatchSubtype
<true>{})) {
4996 return adjustArrSpec(b
);
4998 return a
.dualDispatchDataFn(
5000 DualDispatchIntersection
{ isect
, mark
}
5003 if (!i
.is(BBottom
)) return i
;
5004 isect
&= ~BArrLikeN
;
5005 mark
= project(mark
, isect
);
5006 return isect
? nodata() : TBottom
;
5008 if (couldBe(isect
, BArrLikeN
)) {
5009 auto const i
= adjustArrSpec(a
);
5010 if (!i
.is(BBottom
)) return i
;
5011 isect
&= ~BArrLikeN
;
5012 mark
= project(mark
, isect
);
5013 return isect
? nodata() : TBottom
;
5015 } else if (is_specialized_array_like(b
)) {
5016 if (couldBe(isect
, BArrLikeN
)) {
5017 auto const i
= adjustArrSpec(b
);
5018 if (!i
.is(BBottom
)) return i
;
5019 isect
&= ~BArrLikeN
;
5020 mark
= project(mark
, isect
);
5021 return isect
? nodata() : TBottom
;
5025 if (is_specialized_string(a
)) {
5026 if (is_specialized_string(b
)) {
5027 assertx(couldBe(isect
, BStr
));
5028 if (a
.m_data
.sval
== b
.m_data
.sval
) return reuse(a
);
5030 return isect
? nodata() : TBottom
;
5032 if (couldBe(isect
, BStr
)) return reuse(a
);
5033 } else if (is_specialized_string(b
)) {
5034 if (couldBe(isect
, BStr
)) return reuse(b
);
5037 if (is_specialized_lazycls(a
)) {
5038 if (is_specialized_lazycls(b
)) {
5039 assertx(couldBe(isect
, BLazyCls
));
5040 if (a
.m_data
.lazyclsval
== b
.m_data
.lazyclsval
) return reuse(a
);
5042 return isect
? nodata() : TBottom
;
5044 if (couldBe(isect
, BLazyCls
)) return reuse(a
);
5045 } else if (is_specialized_lazycls(b
)) {
5046 if (couldBe(isect
, BLazyCls
)) return reuse(b
);
5049 if (is_specialized_ecl(a
)) {
5050 if (is_specialized_ecl(b
)) {
5051 assertx(couldBe(isect
, BEnumClassLabel
));
5052 if (a
.m_data
.eclval
== b
.m_data
.eclval
) return reuse(a
);
5053 isect
&= ~BEnumClassLabel
;
5054 return isect
? nodata() : TBottom
;
5056 if (couldBe(isect
, BEnumClassLabel
)) return reuse(a
);
5057 } else if (is_specialized_ecl(b
)) {
5058 if (couldBe(isect
, BEnumClassLabel
)) return reuse(b
);
5061 if (is_specialized_int(a
)) {
5062 if (is_specialized_int(b
)) {
5063 assertx(couldBe(isect
, BInt
));
5064 if (a
.m_data
.ival
== b
.m_data
.ival
) return reuse(a
);
5066 return isect
? nodata() : TBottom
;
5068 if (couldBe(isect
, BInt
)) return reuse(a
);
5069 } else if (is_specialized_int(b
)) {
5070 if (couldBe(isect
, BInt
)) return reuse(b
);
5073 if (is_specialized_double(a
)) {
5074 if (is_specialized_double(b
)) {
5075 assertx(couldBe(isect
, BDbl
));
5076 if (double_equals(a
.m_data
.dval
, b
.m_data
.dval
)) return reuse(a
);
5078 return isect
? nodata() : TBottom
;
5080 if (couldBe(isect
, BDbl
)) return reuse(a
);
5081 } else if (is_specialized_double(b
)) {
5082 if (couldBe(isect
, BDbl
)) return reuse(b
);
5088 Type
union_of(Type a
, Type b
) {
5089 auto const combined
= a
.bits() | b
.bits();
5090 auto const mark
= unionOf(a
.m_legacyMark
, b
.m_legacyMark
);
5092 auto const nodata
= [&] { return Type
{ combined
, mark
}; };
5093 if (!a
.hasData() && !b
.hasData()) return nodata();
5095 auto const reuse
= [&] (Type
& dst
) {
5096 dst
.m_bits
= combined
;
5097 dst
.m_legacyMark
= mark
;
5098 assertx(dst
.checkInvariants());
5099 return std::move(dst
);
5102 // Check if the given DWaitHandle or DObj is a subtype of each
5103 // other, returning the less specific type. Returns std::nullopt if
5104 // neither of them is.
5105 auto const whAndObj
= [&] (Type
& wh
, Type
& obj
) -> Optional
<Type
> {
5106 // The order of checks is important here. If the obj is the
5107 // Awaitable object, then both subtype checks will pass (because
5108 // they're equal), but we should reuse obj in that case, so check
5110 if (subtypeCls
<true>(wh
.m_data
.dwh
->cls
, obj
.m_data
.dobj
)) return reuse(obj
);
5111 if (subtypeCls
<true>(obj
.m_data
.dobj
, wh
.m_data
.dwh
->cls
)) return reuse(wh
);
5112 return std::nullopt
;
5115 // If both sides have the same specialization, check if they are
5116 // equal. If they are, reuse one of the sides. Otherwise if they are
5117 // not, return nodata() (we assume the union of two unequal
5118 // specializations is the full type). If only one side has a
5119 // specialization, check if the other side has the support bits. If
5120 // it does not, we can reuse the type with the specialization (since
5121 // it's not being unioned with anything on the other
5122 // side). Otherwise we have nodata(). If the union contains more
5123 // than one set of support bits, we can never keep any
5126 // For wait handles, if one is a specialized object try to determine
5127 // if one of them is a subtype of the other. If not, demote the wait
5128 // handle to a DObj and use that.
5129 if (is_specialized_wait_handle(a
)) {
5130 if (is_specialized_wait_handle(b
)) {
5131 assertx(a
.m_data
.dwh
->cls
.same(b
.m_data
.dwh
->cls
));
5132 auto const& atype
= a
.m_data
.dwh
->inner
;
5133 auto const& btype
= b
.m_data
.dwh
->inner
;
5134 if (atype
.subtypeOf(btype
)) return reuse(b
);
5135 if (btype
.subtypeOf(atype
)) return reuse(a
);
5136 auto u
= union_of(atype
, btype
);
5137 if (!u
.strictSubtypeOf(BInitCell
)) {
5138 a
= demote_wait_handle(std::move(a
));
5140 a
.m_data
.dwh
.mutate()->inner
= std::move(u
);
5144 if (is_specialized_obj(b
)) {
5145 if (auto const t
= whAndObj(a
, b
)) return *t
;
5146 a
= demote_wait_handle(std::move(a
));
5148 if (b
.couldBe(BObj
) || !subtypeOf(combined
, BObj
| kNonSupportBits
)) {
5153 } else if (is_specialized_wait_handle(b
)) {
5154 if (is_specialized_obj(a
)) {
5155 if (auto const t
= whAndObj(b
, a
)) return *t
;
5156 b
= demote_wait_handle(std::move(b
));
5158 if (a
.couldBe(BObj
) || !subtypeOf(combined
, BObj
| kNonSupportBits
)) {
5165 auto const unionDcls
= [&] (const DCls
& acls
, const DCls
& bcls
, bool isObj
) {
5166 auto const isCtx
= acls
.isCtx() && bcls
.isCtx();
5167 if (subtypeCls
<false>(acls
, bcls
)) return setctx(reuse(b
), isCtx
);
5168 if (subtypeCls
<false>(bcls
, acls
)) return setctx(reuse(a
), isCtx
);
5170 auto const nonRegA
= acls
.containsNonRegular();
5171 auto const nonRegB
= bcls
.containsNonRegular();
5173 auto const handleIsectAndExact
= [&] (const DCls
& isectExact
,
5176 assertx(isectExact
.isIsectAndExact());
5178 auto const [e
, i
] = isectExact
.isectAndExact();
5180 isObj
? objExact(e
) : clsExact(e
, nonReg
);
5181 assertx(!exact
.is(BBottom
));
5183 auto lhs
= [&, i
=i
] {
5184 if (i
->size() == 1) {
5186 ? subObj(i
->front())
5187 : subCls(i
->front(), nonReg
);
5189 DCls::IsectSet set
{i
->begin(), i
->end()};
5191 ? isectObjInternal(std::move(set
))
5192 : isectClsInternal(std::move(set
), nonReg
);
5195 assertx(!lhs
.is(BBottom
));
5197 auto ret
= intersection_of(
5198 union_of(std::move(exact
), rhs
),
5199 union_of(std::move(lhs
), rhs
)
5201 assertx(!ret
.is(BBottom
));
5202 return setctx(reuse(ret
), isCtx
);
5205 if (acls
.isIsectAndExact()) {
5206 return handleIsectAndExact(acls
, std::move(b
), nonRegA
);
5207 } else if (bcls
.isIsectAndExact()) {
5208 return handleIsectAndExact(bcls
, std::move(a
), nonRegB
);
5211 auto const u
= [&] {
5212 if (acls
.isIsect()) {
5213 if (bcls
.isIsect()) {
5214 return res::Class::combine(
5223 return res::Class::combine(
5225 std::array
<res::Class
, 1>{bcls
.cls()},
5232 } else if (bcls
.isIsect()) {
5233 return res::Class::combine(
5234 std::array
<res::Class
, 1>{acls
.cls()},
5242 return res::Class::combine(
5243 std::array
<res::Class
, 1>{acls
.cls()},
5244 std::array
<res::Class
, 1>{bcls
.cls()},
5253 // Empty list means there's no classes in common, which means it's
5254 // just a TObj/TCls.
5255 if (u
.empty()) return nodata();
5256 if (u
.size() == 1) {
5257 // We need not to distinguish between Obj<=T and Obj=T, and
5258 // always return an Obj<=Ancestor, because that is the single
5259 // type that includes both children.
5262 : subCls(u
.front(), nonRegA
|| nonRegB
);
5263 assertx(!ret
.is(BBottom
));
5264 return setctx(reuse(ret
), isCtx
);
5267 DCls::IsectSet set
{u
.begin(), u
.end()};
5269 ? isectObjInternal(std::move(set
))
5270 : isectClsInternal(std::move(set
), nonRegA
|| nonRegB
);
5271 assertx(!ret
.is(BBottom
));
5272 return setctx(reuse(ret
), isCtx
);
5275 if (is_specialized_obj(a
)) {
5276 if (is_specialized_obj(b
)) {
5277 assertx(!is_specialized_wait_handle(a
));
5278 assertx(!is_specialized_wait_handle(b
));
5279 return unionDcls(a
.m_data
.dobj
, b
.m_data
.dobj
, true);
5281 if (b
.couldBe(BObj
) || !subtypeOf(combined
, BObj
| kNonSupportBits
)) {
5285 } else if (is_specialized_obj(b
)) {
5286 if (a
.couldBe(BObj
) || !subtypeOf(combined
, BObj
| kNonSupportBits
)) {
5292 if (is_specialized_cls(a
)) {
5293 if (is_specialized_cls(b
)) return unionDcls(a
.m_data
.dcls
, b
.m_data
.dcls
, false);
5294 if (b
.couldBe(BCls
) || !subtypeOf(combined
, BCls
| kNonSupportBits
)) {
5298 } else if (is_specialized_cls(b
)) {
5299 if (a
.couldBe(BCls
) || !subtypeOf(combined
, BCls
| kNonSupportBits
)) {
5305 if (is_specialized_array_like(a
)) {
5306 if (is_specialized_array_like(b
)) {
5307 if (a
.dualDispatchDataFn(b
, DualDispatchSubtype
<true>{})) return reuse(b
);
5308 if (b
.dualDispatchDataFn(a
, DualDispatchSubtype
<true>{})) return reuse(a
);
5309 return a
.dualDispatchDataFn(b
, DualDispatchUnion
{ combined
, mark
});
5311 if (!subtypeOf(combined
, BArrLikeN
| kNonSupportBits
)) return nodata();
5312 if (!b
.couldBe(BArrLikeN
)) return reuse(a
);
5313 if (b
.dispatchArrLikeNone(a
, DualDispatchSubtype
<true>{})) return reuse(a
);
5314 return b
.dispatchArrLikeNone(a
, DualDispatchUnion
{ combined
, mark
});
5315 } else if (is_specialized_array_like(b
)) {
5316 if (!subtypeOf(combined
, BArrLikeN
| kNonSupportBits
)) return nodata();
5317 if (!a
.couldBe(BArrLikeN
)) return reuse(b
);
5318 if (a
.dispatchArrLikeNone(b
, DualDispatchSubtype
<true>{})) return reuse(b
);
5319 return a
.dispatchArrLikeNone(b
, DualDispatchUnion
{ combined
, mark
});
5322 if (is_specialized_string(a
)) {
5323 if (is_specialized_string(b
)) {
5324 if (a
.m_data
.sval
== b
.m_data
.sval
) return reuse(a
);
5327 if (b
.couldBe(BStr
) || !subtypeOf(combined
, BStr
| kNonSupportBits
)) {
5331 } else if (is_specialized_string(b
)) {
5332 if (a
.couldBe(BStr
) || !subtypeOf(combined
, BStr
| kNonSupportBits
)) {
5338 if (is_specialized_lazycls(a
)) {
5339 if (is_specialized_lazycls(b
)) {
5340 if (a
.m_data
.lazyclsval
== b
.m_data
.lazyclsval
) return reuse(a
);
5343 if (b
.couldBe(BLazyCls
) ||
5344 !subtypeOf(combined
, BLazyCls
| kNonSupportBits
)) {
5348 } else if (is_specialized_lazycls(b
)) {
5349 if (a
.couldBe(BLazyCls
) ||
5350 !subtypeOf(combined
, BLazyCls
| kNonSupportBits
)) {
5356 if (is_specialized_ecl(a
)) {
5357 if (is_specialized_ecl(b
)) {
5358 if (a
.m_data
.eclval
== b
.m_data
.eclval
) return reuse(a
);
5361 if (b
.couldBe(BEnumClassLabel
) ||
5362 !subtypeOf(combined
, BEnumClassLabel
| kNonSupportBits
)) {
5366 } else if (is_specialized_ecl(b
)) {
5367 if (a
.couldBe(BEnumClassLabel
) ||
5368 !subtypeOf(combined
, BEnumClassLabel
| kNonSupportBits
)) {
5374 if (is_specialized_int(a
)) {
5375 if (is_specialized_int(b
)) {
5376 if (a
.m_data
.ival
== b
.m_data
.ival
) return reuse(a
);
5379 if (b
.couldBe(BInt
) || !subtypeOf(combined
, BInt
| kNonSupportBits
)) {
5383 } else if (is_specialized_int(b
)) {
5384 if (a
.couldBe(BInt
) || !subtypeOf(combined
, BInt
| kNonSupportBits
)) {
5390 if (is_specialized_double(a
)) {
5391 if (is_specialized_double(b
)) {
5392 if (double_equals(a
.m_data
.dval
, b
.m_data
.dval
)) return reuse(a
);
5395 if (b
.couldBe(BDbl
) || !subtypeOf(combined
, BDbl
| kNonSupportBits
)) {
5399 } else if (is_specialized_double(b
)) {
5400 if (a
.couldBe(BDbl
) || !subtypeOf(combined
, BDbl
| kNonSupportBits
)) {
5406 always_assert(false);
5409 bool could_have_magic_bool_conversion(const Type
& t
) {
5410 if (!t
.couldBe(BObj
)) return false;
5411 if (!is_specialized_obj(t
)) return true;
5412 auto const& dobj
= dobj_of(t
);
5413 if (dobj
.isIsect()) {
5414 for (auto const cls
: dobj
.isect()) {
5415 if (!cls
.couldHaveMagicBool()) return false;
5418 } else if (dobj
.isIsectAndExact()) {
5419 auto const [e
, i
] = dobj
.isectAndExact();
5420 if (!e
.couldHaveMagicBool()) return false;
5421 for (auto const cls
: *i
) {
5422 if (!cls
.couldHaveMagicBool()) return false;
5426 return dobj
.cls().couldHaveMagicBool();
5429 std::pair
<Emptiness
, bool> emptiness(const Type
& t
) {
5430 assertx(t
.subtypeOf(BCell
));
5432 auto const emptyMask
= BNull
| BFalse
| BArrLikeE
;
5433 auto const nonEmptyMask
=
5434 BTrue
| BArrLikeN
| BObj
| BCls
| BLazyCls
| BFunc
|
5435 BRFunc
| BClsMeth
| BRClsMeth
| BEnumClassLabel
;
5436 auto const bothMask
=
5437 BCell
& ~(emptyMask
| nonEmptyMask
| BInt
| BDbl
| BStr
);
5438 auto empty
= t
.couldBe(emptyMask
| bothMask
);
5439 auto nonempty
= t
.couldBe(nonEmptyMask
| bothMask
);
5441 t
.subtypeOf(BPrim
| BStr
| BObj
| BArrLike
| BCls
| BLazyCls
|
5442 BFunc
| BRFunc
| BClsMeth
| BRClsMeth
| BEnumClassLabel
);
5444 if (could_have_magic_bool_conversion(t
)) {
5449 auto const check
= [&] (TypedValue tv
) {
5450 (tvToBool(tv
) ? nonempty
: empty
) = true;
5453 if (t
.couldBe(BInt
)) {
5454 if (is_specialized_int(t
)) {
5455 check(make_tv
<KindOfInt64
>(t
.m_data
.ival
));
5461 if (t
.couldBe(BDbl
)) {
5462 if (is_specialized_double(t
)) {
5463 check(make_tv
<KindOfDouble
>(t
.m_data
.dval
));
5469 if (t
.couldBe(BStr
)) {
5470 if (is_specialized_string(t
)) {
5471 check(make_tv
<KindOfPersistentString
>(t
.m_data
.sval
));
5479 return std::make_pair(
5480 empty
? Emptiness::Maybe
: Emptiness::NonEmpty
,
5484 assertx(empty
|| t
.is(BBottom
));
5485 return std::make_pair(Emptiness::Empty
, effectfree
);
5488 void widen_type_impl(Type
& t
, uint32_t depth
) {
5489 // Right now to guarantee termination we need to just limit the nesting depth
5490 // of the type to a fixed degree.
5491 auto const checkDepth
= [&] {
5492 if (depth
>= kTypeWidenMaxDepth
) {
5493 t
= Type
{ t
.bits(), t
.m_legacyMark
};
5499 switch (t
.m_dataTag
) {
5502 case DataTag::LazyCls
:
5503 case DataTag::EnumClassLabel
:
5508 case DataTag::ArrLikeVal
:
5511 case DataTag::WaitHandle
:
5512 widen_type_impl(t
.m_data
.dwh
.mutate()->inner
, depth
+ 1);
5515 case DataTag::ArrLikePacked
: {
5516 if (checkDepth()) return;
5517 auto& packed
= *t
.m_data
.packed
.mutate();
5518 for (auto& e
: packed
.elems
) {
5519 widen_type_impl(e
, depth
+ 1);
5524 case DataTag::ArrLikePackedN
: {
5525 if (checkDepth()) return;
5526 auto& packed
= *t
.m_data
.packedn
.mutate();
5527 widen_type_impl(packed
.type
, depth
+ 1);
5531 case DataTag::ArrLikeMap
: {
5532 if (checkDepth()) return;
5533 auto& map
= *t
.m_data
.map
.mutate();
5534 for (auto it
= map
.map
.begin(); it
!= map
.map
.end(); it
++) {
5535 auto temp
= it
->second
.val
;
5536 widen_type_impl(temp
, depth
+ 1);
5537 map
.map
.update(it
, it
->second
.withType(std::move(temp
)));
5539 if (map
.hasOptElements()) {
5540 // Key must be at least ArrKey, which doesn't need widening.
5541 widen_type_impl(map
.optVal
, depth
+ 1);
5546 case DataTag::ArrLikeMapN
: {
5547 if (checkDepth()) return;
5548 auto& map
= *t
.m_data
.mapn
.mutate();
5549 // Key must be at least ArrKey, which doesn't need widening.
5550 widen_type_impl(map
.val
, depth
+ 1);
5558 Type
widen_type(Type t
) {
5559 widen_type_impl(t
, 0);
5563 Type
widening_union(const Type
& a
, const Type
& b
) {
5564 return widen_type(union_of(a
, b
));
5567 Type
stack_flav(Type a
) {
5568 if (a
.subtypeOf(BUninit
)) return TUninit
;
5569 if (a
.subtypeOf(BInitCell
)) return TInitCell
;
5570 always_assert(0 && "stack_flav passed invalid type");
5573 Type
loosen_string_staticness(Type t
) {
5574 auto bits
= t
.bits();
5575 if (couldBe(bits
, BStr
)) bits
|= BStr
;
5577 assertx(t
.checkInvariants());
5581 Type
loosen_array_staticness(Type t
) {
5582 auto bits
= t
.bits();
5583 auto const check
= [&] (trep a
) {
5584 if (couldBe(bits
, a
)) bits
|= a
;
5593 if (t
.m_dataTag
== DataTag::ArrLikeVal
) {
5594 return toDArrLike(t
.m_data
.aval
, bits
, t
.m_legacyMark
);
5597 assertx(t
.checkInvariants());
5601 Type
loosen_staticness(Type t
) {
5602 if (t
.m_dataTag
== DataTag::ArrLikeVal
) {
5603 // ArrLikeVal always needs static ArrLikeN support, so we if we
5604 // want to loosen the trep, we need to convert to the equivalent
5605 // DArrLike instead.
5606 return loosen_staticness(toDArrLike(t
.m_data
.aval
, t
.bits(), t
.m_legacyMark
));
5609 auto bits
= t
.bits();
5610 auto const check
= [&] (trep a
) {
5611 if (couldBe(bits
, a
)) bits
|= a
;
5615 check(BEnumClassLabel
);
5625 switch (t
.m_dataTag
) {
5628 case DataTag::LazyCls
:
5629 case DataTag::EnumClassLabel
:
5636 case DataTag::WaitHandle
: {
5637 auto& inner
= t
.m_data
.dwh
.mutate()->inner
;
5638 auto loosened
= loosen_staticness(std::move(inner
));
5639 if (!loosened
.strictSubtypeOf(BInitCell
)) {
5640 return demote_wait_handle(t
);
5642 inner
= std::move(loosened
);
5646 case DataTag::ArrLikePacked
: {
5647 auto& packed
= *t
.m_data
.packed
.mutate();
5648 for (auto& e
: packed
.elems
) {
5649 e
= loosen_staticness(std::move(e
));
5654 case DataTag::ArrLikePackedN
: {
5655 auto& packed
= *t
.m_data
.packedn
.mutate();
5656 auto loosened
= loosen_staticness(std::move(packed
.type
));
5657 if (t
.subtypeAmong(BVecN
, BArrLikeN
) &&
5658 !loosened
.strictSubtypeOf(BInitCell
)) {
5659 return Type
{ bits
, t
.m_legacyMark
};
5661 packed
.type
= std::move(loosened
);
5665 case DataTag::ArrLikeMap
: {
5666 auto& map
= *t
.m_data
.map
.mutate();
5667 for (auto it
= map
.map
.begin(); it
!= map
.map
.end(); ++it
) {
5668 auto val
= loosen_staticness(it
->second
.val
);
5673 !isIntType(it
->first
.m_type
) ? TriBool::Maybe
: TriBool::Yes
5677 map
.optKey
= loosen_staticness(std::move(map
.optKey
));
5678 map
.optVal
= loosen_staticness(std::move(map
.optVal
));
5682 case DataTag::ArrLikeMapN
: {
5683 auto& map
= *t
.m_data
.mapn
.mutate();
5684 auto loosenedKey
= loosen_staticness(std::move(map
.key
));
5685 auto loosenedVal
= loosen_staticness(std::move(map
.val
));
5686 auto const keyBits
= allowedKeyBits(bits
);
5687 auto const valBits
= allowedValBits(bits
, false);
5688 if (!loosenedKey
.strictSubtypeOf(keyBits
.first
) &&
5689 !loosenedVal
.strictSubtypeOf(valBits
.first
)) {
5690 return Type
{ bits
, t
.m_legacyMark
};
5692 map
.key
= std::move(loosenedKey
);
5693 map
.val
= std::move(loosenedVal
);
5697 case DataTag::ArrLikeVal
:
5698 always_assert(false);
5701 assertx(t
.checkInvariants());
5705 Type
loosen_vec_or_dict(Type t
) {
5706 if (t
.couldBe(BVec
| BDict
)) t
|= union_of(TVec
, TDict
);
5710 Type
loosen_string_values(Type t
) {
5711 return t
.m_dataTag
== DataTag::Str
5712 ? Type
{ t
.bits(), t
.m_legacyMark
} : t
;
5715 Type
loosen_array_values(Type a
) {
5716 switch (a
.m_dataTag
) {
5717 case DataTag::ArrLikeVal
:
5718 case DataTag::ArrLikePacked
:
5719 case DataTag::ArrLikePackedN
:
5720 case DataTag::ArrLikeMap
:
5721 case DataTag::ArrLikeMapN
:
5722 return Type
{ a
.bits(), a
.m_legacyMark
};
5725 case DataTag::LazyCls
:
5726 case DataTag::EnumClassLabel
:
5730 case DataTag::WaitHandle
:
5737 Type
loosen_values(Type a
) {
5739 switch (a
.m_dataTag
) {
5741 case DataTag::LazyCls
:
5742 case DataTag::EnumClassLabel
:
5745 case DataTag::ArrLikeVal
:
5746 case DataTag::ArrLikePacked
:
5747 case DataTag::ArrLikePackedN
:
5748 case DataTag::ArrLikeMap
:
5749 case DataTag::ArrLikeMapN
:
5750 return Type
{ a
.bits(), a
.m_legacyMark
};
5753 case DataTag::WaitHandle
:
5759 if (t
.couldBe(BFalse
) || t
.couldBe(BTrue
)) t
|= TBool
;
5763 Type
loosen_emptiness(Type t
) {
5764 auto const check
= [&] (trep a
, trep b
) {
5766 if (t
.hasData() && kSupportBits
& b
& ~t
.bits()) {
5768 t
.m_dataTag
= DataTag::None
;
5773 check(BSVec
, BSVec
);
5775 check(BSDict
, BSDict
);
5776 check(BCDict
, BDict
);
5777 check(BSKeyset
, BSKeyset
);
5778 check(BCKeyset
, BKeyset
);
5780 assertx(t
.checkInvariants());
5784 Type
loosen_likeness(Type t
) {
5785 if (t
.couldBe(BCls
| BLazyCls
)) t
|= TSStr
;
5789 Type
loosen_likeness_recursively(Type t
) {
5790 t
= loosen_likeness(std::move(t
));
5792 switch (t
.m_dataTag
) {
5795 case DataTag::LazyCls
:
5796 case DataTag::EnumClassLabel
:
5803 case DataTag::ArrLikeVal
:
5804 // Static arrays cannot currently contain function or class pointers.
5807 case DataTag::WaitHandle
: {
5808 auto& inner
= t
.m_data
.dwh
.mutate()->inner
;
5809 auto loosened
= loosen_likeness_recursively(inner
);
5810 if (!loosened
.strictSubtypeOf(BInitCell
)) {
5811 return demote_wait_handle(std::move(t
));
5813 inner
= std::move(loosened
);
5817 case DataTag::ArrLikePacked
: {
5818 auto& packed
= *t
.m_data
.packed
.mutate();
5819 for (auto& e
: packed
.elems
) {
5820 e
= loosen_likeness_recursively(std::move(e
));
5825 case DataTag::ArrLikePackedN
: {
5826 auto& packed
= *t
.m_data
.packedn
.mutate();
5827 auto loosened
= loosen_likeness_recursively(packed
.type
);
5828 if (t
.subtypeAmong(BVecN
, BArrLikeN
) &&
5829 !loosened
.strictSubtypeOf(allowedValBits(t
.bits(), true).first
)) {
5830 return Type
{ t
.bits(), t
.m_legacyMark
};
5832 packed
.type
= std::move(loosened
);
5836 case DataTag::ArrLikeMap
: {
5837 auto& map
= *t
.m_data
.map
.mutate();
5838 for (auto it
= map
.map
.begin(); it
!= map
.map
.end(); it
++) {
5839 auto val
= loosen_likeness_recursively(it
->second
.val
);
5840 map
.map
.update(it
, it
->second
.withType(std::move(val
)));
5842 map
.optVal
= loosen_likeness_recursively(std::move(map
.optVal
));
5846 case DataTag::ArrLikeMapN
: {
5847 auto& map
= *t
.m_data
.mapn
.mutate();
5848 auto loosened
= loosen_likeness_recursively(map
.val
);
5849 if (!map
.key
.strictSubtypeOf(allowedKeyBits(t
.bits()).first
) &&
5850 !loosened
.strictSubtypeOf(allowedValBits(t
.bits(), false).first
)) {
5851 return Type
{ t
.bits(), t
.m_legacyMark
};
5853 map
.val
= std::move(loosened
);
5858 assertx(t
.checkInvariants());
5862 Type
loosen_all(Type t
) {
5875 Type
loosen_to_datatype(Type t
) {
5876 if (t
.couldBe(BFalse
) || t
.couldBe(BTrue
)) t
|= TBool
;
5877 return loosen_staticness(
5880 Type
{ t
.bits(), t
.m_legacyMark
}
5886 Type
add_nonemptiness(Type t
) {
5887 auto const check
= [&] (trep a
, trep b
) {
5888 if (t
.couldBe(a
)) t
.m_bits
|= b
;
5890 check(BSVecE
, BSVecN
);
5891 check(BCVecE
, BVecN
);
5892 check(BSDictE
, BSDictN
);
5893 check(BCDictE
, BDictN
);
5894 check(BSKeysetE
, BSKeysetN
);
5895 check(BCKeysetE
, BKeysetN
);
5899 Type
to_cell(Type t
) {
5900 assertx(t
.subtypeOf(BCell
));
5901 if (!t
.couldBe(BUninit
)) return t
;
5902 auto const bits
= (t
.bits() & ~BUninit
) | BInitNull
;
5904 assertx(t
.checkInvariants());
5908 Type
remove_uninit(Type t
) {
5909 t
.m_bits
&= ~BUninit
;
5910 assertx(t
.checkInvariants());
5914 Type
remove_data(Type t
, trep support
) {
5915 auto const bits
= t
.bits() & ~support
;
5916 return Type
{ bits
, project(t
.m_legacyMark
, bits
) };
5919 Type
remove_int(Type t
) {
5920 assertx(t
.subtypeOf(BCell
));
5921 if (t
.m_dataTag
== DataTag::Int
) {
5922 return remove_data(std::move(t
), BInt
);
5925 assertx(t
.checkInvariants());
5929 Type
remove_double(Type t
) {
5930 assertx(t
.subtypeOf(BCell
));
5931 if (t
.m_dataTag
== DataTag::Dbl
) {
5932 return remove_data(std::move(t
), BDbl
);
5935 assertx(t
.checkInvariants());
5939 Type
remove_string(Type t
) {
5940 assertx(t
.subtypeOf(BCell
));
5941 if (t
.m_dataTag
== DataTag::Str
) {
5942 return remove_data(std::move(t
), BStr
);
5945 assertx(t
.checkInvariants());
5949 Type
remove_lazycls(Type t
) {
5950 assertx(t
.subtypeOf(BCell
));
5951 if (t
.m_dataTag
== DataTag::LazyCls
) {
5952 return remove_data(std::move(t
), BLazyCls
);
5954 t
.m_bits
&= ~BLazyCls
;
5955 assertx(t
.checkInvariants());
5959 Type
remove_cls(Type t
) {
5960 assertx(t
.subtypeOf(BCell
));
5961 if (t
.m_dataTag
== DataTag::Cls
) {
5962 return remove_data(std::move(t
), BCls
);
5965 assertx(t
.checkInvariants());
5969 Type
remove_obj(Type t
) {
5970 assertx(t
.subtypeOf(BCell
));
5971 if (is_specialized_obj(t
)) {
5972 return remove_data(std::move(t
), BObj
);
5975 assertx(t
.checkInvariants());
5979 Type
remove_keyset(Type t
) {
5980 assertx(t
.subtypeOf(BCell
));
5981 if (!is_specialized_array_like(t
)) {
5982 // If there's no specialization, we can just remove the bits.
5983 t
.m_bits
&= ~BKeyset
;
5984 assertx(t
.checkInvariants());
5987 auto removed
= Type
{t
.bits() & ~BKeyset
, t
.m_legacyMark
};
5988 // Otherwise use intersection_of to remove the Keyset while trying
5989 // to preserve the specialization
5990 return intersection_of(std::move(t
), std::move(removed
));
5993 Type
remove_bits(Type t
, trep bits
) {
5994 assertx(t
.subtypeOf(BCell
));
5996 // Find the support bits for the specialization, if any
5997 auto const support
= [&] {
5998 switch (t
.m_dataTag
) {
5999 case DataTag::None
: return BBottom
;
6000 case DataTag::Int
: return BInt
;
6001 case DataTag::Dbl
: return BDbl
;
6002 case DataTag::Str
: return BStr
;
6003 case DataTag::LazyCls
: return BLazyCls
;
6004 case DataTag::EnumClassLabel
: return BEnumClassLabel
;
6006 case DataTag::WaitHandle
: return BObj
;
6007 case DataTag::Cls
: return BCls
;
6008 case DataTag::ArrLikePacked
:
6009 case DataTag::ArrLikePackedN
:
6010 case DataTag::ArrLikeMap
:
6011 case DataTag::ArrLikeMapN
:
6012 case DataTag::ArrLikeVal
: return BArrLikeN
;
6017 // If the support bits are present, remove the data while removing
6019 if (couldBe(bits
, support
)) return remove_data(std::move(t
), bits
);
6020 // Otherwise we can just remove the bits
6021 auto const old
= t
.bits();
6023 if (t
.m_dataTag
== DataTag::ArrLikeVal
&&
6024 !t
.couldBe(BArrLikeE
) &&
6025 couldBe(old
, BArrLikeE
)) {
6026 // If removing the bits removes BArrLikeE with a ArrLikeVal
6027 // specialization, we need to restore the exact LegacyMark
6028 // corresponding to the static array.
6029 t
.m_legacyMark
= legacyMarkFromSArr(t
.m_data
.aval
);
6031 t
.m_legacyMark
= project(t
.m_legacyMark
, t
.bits());
6033 assertx(t
.checkInvariants());
6037 std::pair
<Type
, Type
> split_obj(Type t
) {
6038 assertx(t
.subtypeOf(BCell
));
6039 auto const b
= t
.bits();
6040 if (is_specialized_obj(t
)) {
6041 auto const mark
= t
.m_legacyMark
;
6043 t
.m_legacyMark
= LegacyMark::Bottom
;
6044 return std::make_pair(std::move(t
), Type
{ b
& ~BObj
, mark
});
6047 return std::make_pair(Type
{ b
& BObj
, LegacyMark::Bottom
}, std::move(t
));
6050 std::pair
<Type
, Type
> split_cls(Type t
) {
6051 assertx(t
.subtypeOf(BCell
));
6052 auto const b
= t
.bits();
6053 if (is_specialized_cls(t
)) {
6054 auto const mark
= t
.m_legacyMark
;
6056 t
.m_legacyMark
= LegacyMark::Bottom
;
6057 return std::make_pair(std::move(t
), Type
{ b
& ~BCls
, mark
});
6060 return std::make_pair(Type
{ b
& BCls
, LegacyMark::Bottom
}, std::move(t
));
6063 std::pair
<Type
, Type
> split_array_like(Type t
) {
6064 assertx(t
.subtypeOf(BCell
));
6065 auto const b
= t
.bits();
6066 if (is_specialized_array_like(t
)) {
6067 t
.m_bits
&= BArrLike
;
6068 return std::make_pair(
6070 Type
{ b
& ~BArrLike
, LegacyMark::Bottom
}
6073 auto const mark
= t
.m_legacyMark
;
6074 t
.m_bits
&= ~BArrLike
;
6075 t
.m_legacyMark
= LegacyMark::Bottom
;
6076 return std::make_pair(Type
{ b
& BArrLike
, mark
}, std::move(t
));
6079 std::pair
<Type
, Type
> split_string(Type t
) {
6080 assertx(t
.subtypeOf(BCell
));
6081 auto const b
= t
.bits();
6082 if (is_specialized_string(t
)) {
6083 auto const mark
= t
.m_legacyMark
;
6085 t
.m_legacyMark
= LegacyMark::Bottom
;
6086 return std::make_pair(std::move(t
), Type
{ b
& ~BStr
, mark
});
6089 return std::make_pair(Type
{ b
& BStr
, LegacyMark::Bottom
}, std::move(t
));
6092 std::pair
<Type
, Type
> split_lazycls(Type t
) {
6093 assertx(t
.subtypeOf(BCell
));
6094 auto const b
= t
.bits();
6095 if (is_specialized_lazycls(t
)) {
6096 auto const mark
= t
.m_legacyMark
;
6097 t
.m_bits
&= BLazyCls
;
6098 t
.m_legacyMark
= LegacyMark::Bottom
;
6099 return std::make_pair(std::move(t
), Type
{ b
& ~BLazyCls
, mark
});
6101 t
.m_bits
&= ~BLazyCls
;
6102 return std::make_pair(Type
{ b
& BLazyCls
, LegacyMark::Bottom
}, std::move(t
));
6105 Type
assert_emptiness(Type t
) {
6106 auto const stripVal
= [&] (TypedValue tv
, trep support
) {
6107 if (tvToBool(tv
)) t
= remove_data(std::move(t
), support
);
6110 if (t
.couldBe(BArrLikeN
)) {
6111 t
= remove_data(std::move(t
), BArrLikeN
);
6114 if (t
.couldBe(BLazyCls
)) {
6115 t
= remove_data(std::move(t
), BLazyCls
);
6118 if (t
.couldBe(BCls
)) {
6119 t
= remove_data(std::move(t
), BCls
);
6122 if (t
.couldBe(BFunc
)) {
6123 t
= remove_data(std::move(t
), BFunc
);
6126 if (t
.couldBe(BRFunc
)) {
6127 t
= remove_data(std::move(t
), BRFunc
);
6130 if (t
.couldBe(BClsMeth
)) {
6131 t
= remove_data(std::move(t
), BClsMeth
);
6134 if (t
.couldBe(BRClsMeth
)) {
6135 t
= remove_data(std::move(t
), BRClsMeth
);
6138 if (t
.couldBe(BEnumClassLabel
)) {
6139 t
= remove_data(std::move(t
), BEnumClassLabel
);
6142 if (!could_have_magic_bool_conversion(t
) && t
.couldBe(BObj
)) {
6143 t
= remove_data(std::move(t
), BObj
);
6146 if (t
.couldBe(BInt
)) {
6147 if (is_specialized_int(t
)) {
6148 stripVal(make_tv
<KindOfInt64
>(t
.m_data
.ival
), BInt
);
6150 t
= union_of(remove_int(std::move(t
)), ival(0));
6154 if (t
.couldBe(BStr
)) {
6155 if (is_specialized_string(t
)) {
6156 stripVal(make_tv
<KindOfPersistentString
>(t
.m_data
.sval
), BStr
);
6159 t
.subtypeAmong(BSStr
, BStr
) ? sempty() :
6160 t
.subtypeAmong(BCStr
, BStr
) ? sempty_counted() :
6162 t
= union_of(remove_string(std::move(t
)), empty
);
6166 if (t
.couldBe(BDbl
)) {
6167 if (is_specialized_double(t
)) {
6168 stripVal(make_tv
<KindOfDouble
>(t
.m_data
.dval
), BDbl
);
6170 t
= union_of(remove_double(std::move(t
)), dval(0));
6175 assertx(t
.checkInvariants());
6179 Type
assert_nonemptiness(Type t
) {
6180 assertx(t
.subtypeOf(BCell
));
6182 auto const stripVal
= [&] (TypedValue tv
, trep support
) {
6183 if (!tvToBool(tv
)) t
= remove_data(std::move(t
), support
);
6186 switch (t
.m_dataTag
) {
6189 case DataTag::WaitHandle
:
6191 case DataTag::ArrLikePacked
:
6192 case DataTag::ArrLikePackedN
:
6193 case DataTag::ArrLikeMap
:
6194 case DataTag::ArrLikeMapN
:
6195 case DataTag::ArrLikeVal
:
6196 case DataTag::LazyCls
:
6197 case DataTag::EnumClassLabel
:
6200 stripVal(make_tv
<KindOfInt64
>(t
.m_data
.ival
), BInt
);
6203 stripVal(make_tv
<KindOfDouble
>(t
.m_data
.dval
), BDbl
);
6206 stripVal(make_tv
<KindOfPersistentString
>(t
.m_data
.sval
), BStr
);
6209 auto const old
= t
.bits();
6210 t
.m_bits
&= ~(BNull
| BFalse
| BArrLikeE
);
6211 if (t
.m_dataTag
== DataTag::ArrLikeVal
&& couldBe(old
, BArrLikeE
)) {
6212 t
.m_legacyMark
= legacyMarkFromSArr(t
.m_data
.aval
);
6214 t
.m_legacyMark
= project(t
.m_legacyMark
, t
.bits());
6216 assertx(t
.checkInvariants());
6220 //////////////////////////////////////////////////////////////////////
6222 Type
promote_classish(Type t
) {
6223 if (!t
.couldBe(BCls
| BLazyCls
)) return t
;
6224 t
.m_bits
&= ~(BCls
| BLazyCls
);
6227 if (t
.m_dataTag
== DataTag::LazyCls
) {
6228 auto const name
= t
.m_data
.lazyclsval
;
6229 destroy(t
.m_data
.lazyclsval
);
6230 construct(t
.m_data
.sval
, name
);
6231 t
.m_dataTag
= DataTag::Str
;
6232 } else if (t
.m_dataTag
== DataTag::Cls
) {
6233 // If there could be subclasses we don't know the exact name, so
6234 // must drop the specialization.
6235 if (!t
.m_data
.dcls
.isExact()) {
6236 destroy(t
.m_data
.dcls
);
6237 t
.m_dataTag
= DataTag::None
;
6239 auto const name
= t
.m_data
.dcls
.cls().name();
6240 destroy(t
.m_data
.dcls
);
6241 construct(t
.m_data
.sval
, name
);
6242 t
.m_dataTag
= DataTag::Str
;
6245 // Since t could be BCls or BLazyCls, it cannot have any
6246 // specialization other than the above two.
6247 assertx(t
.m_dataTag
== DataTag::None
);
6250 assertx(t
.checkInvariants());
6254 //////////////////////////////////////////////////////////////////////
6256 // The COWer subclasses allow for traversing specializations while
6257 // potentially COWing the types. We can avoid COWing the type (and all
6258 // of it's parent types) until we know we're going to make a change.
6261 virtual Type
& operator()() = 0;
6262 virtual const Type
& noCOW() const = 0;
6265 struct WaitHandleCOWer
: public COWer
{
6266 WaitHandleCOWer(COWer
& parent
, const DWaitHandle
& h
)
6267 : parent
{parent
}, current
{&h
} {}
6268 const DWaitHandle
& get() const { return *current
; }
6269 DWaitHandle
& getAndCOW() {
6272 assertx(t
.m_dataTag
== DataTag::WaitHandle
);
6273 cowed
= t
.m_data
.dwh
.mutate();
6278 Type
& operator()() { return getAndCOW().inner
; }
6279 const Type
& noCOW() const { return get().inner
; }
6281 DWaitHandle
* cowed
{nullptr};
6282 const DWaitHandle
* current
;
6285 struct ArrLikePackedNCOWer
: public COWer
{
6286 ArrLikePackedNCOWer(COWer
& parent
, const DArrLikePackedN
& h
)
6287 : parent
{parent
}, current
{&h
} {}
6288 const DArrLikePackedN
& get() const { return *current
; }
6289 DArrLikePackedN
& getAndCOW() {
6292 assertx(t
.m_dataTag
== DataTag::ArrLikePackedN
);
6293 cowed
= t
.m_data
.packedn
.mutate();
6298 Type
& operator()() { return getAndCOW().type
; }
6299 const Type
& noCOW() const { return get().type
; }
6301 DArrLikePackedN
* cowed
{nullptr};
6302 const DArrLikePackedN
* current
;
6305 struct ArrLikePackedCOWer
: public COWer
{
6306 ArrLikePackedCOWer(COWer
& parent
, const DArrLikePacked
& h
)
6307 : parent
{parent
}, current
{&h
} {}
6308 const DArrLikePacked
& get() const { return *current
; }
6309 DArrLikePacked
& getAndCOW() {
6312 assertx(t
.m_dataTag
== DataTag::ArrLikePacked
);
6313 cowed
= t
.m_data
.packed
.mutate();
6318 Type
& operator()() { return getAndCOW().elems
[idx
]; }
6319 const Type
& noCOW() const { return currentElem(); }
6321 const Type
& currentElem() const { return get().elems
[idx
]; }
6323 assertx(idx
< get().elems
.size());
6324 return ++idx
< get().elems
.size();
6328 DArrLikePacked
* cowed
{nullptr};
6329 const DArrLikePacked
* current
;
6333 struct ArrLikeMapNCOWer
: public COWer
{
6334 ArrLikeMapNCOWer(COWer
& parent
, const DArrLikeMapN
& h
)
6335 : parent
{parent
}, current
{&h
} {}
6336 const DArrLikeMapN
& get() const { return *current
; }
6337 DArrLikeMapN
& getAndCOW() {
6340 assertx(t
.m_dataTag
== DataTag::ArrLikeMapN
);
6341 cowed
= t
.m_data
.mapn
.mutate();
6346 Type
& operator()() { return isKey
? getAndCOW().key
: getAndCOW().val
; }
6347 const Type
& noCOW() const { return keyOrValue(); }
6349 const Type
& keyOrValue() const { return isKey
? get().key
: get().val
; }
6350 void toValue() { assertx(isKey
); isKey
= false; }
6353 DArrLikeMapN
* cowed
{nullptr};
6354 const DArrLikeMapN
* current
;
6358 struct ArrLikeMapCOWer
: public COWer
{
6359 ArrLikeMapCOWer(COWer
& parent
, const DArrLikeMap
& h
)
6360 : parent
{parent
}, current
{&h
} { iter
= begin(current
->map
); }
6361 const DArrLikeMap
& get() const { return *current
; }
6362 DArrLikeMap
& getAndCOW() {
6365 assertx(t
.m_dataTag
== DataTag::ArrLikeMap
);
6366 cowed
= t
.m_data
.map
.mutate();
6368 iter
= begin(cowed
->map
);
6369 for (size_t i
= 0; i
< idx
; ++i
) ++iter
;
6373 Type
& operator()() {
6374 auto& m
= getAndCOW();
6375 if (iter
!= end(m
.map
)) return const_cast<Type
&>(iter
->second
.val
);
6376 return isOptKey
? m
.optKey
: m
.optVal
;
6378 const Type
& noCOW() const {
6379 auto const& m
= get();
6380 if (iter
!= end(m
.map
)) return iter
->second
.val
;
6381 return isOptKey
? m
.optKey
: m
.optVal
;
6384 const Type
& currentElem() const {
6385 assertx(iter
!= end(get().map
));
6386 return iter
->second
.val
;
6389 assertx(iter
!= end(get().map
));
6391 return ++iter
!= end(get().map
);
6394 const Type
& optKeyOrValue() const {
6395 return isOptKey
? get().optKey
: get().optVal
;
6398 assertx(iter
== end(get().map
));
6404 DArrLikeMap
* cowed
{nullptr};
6405 const DArrLikeMap
* current
;
6407 MapElems::iterator iter
;
6408 bool isOptKey
{true};
6411 struct TypeCOWer
: public COWer
{
6412 explicit TypeCOWer(Type
& t
) : t
{t
} {}
6413 Type
& operator()() { return t
; }
6414 const Type
& noCOW() const { return t
; }
6418 //////////////////////////////////////////////////////////////////////
6420 void unserialize_classes_impl(const IIndex
& index
,
6423 SCOPE_EXIT
{ parent
.noCOW().checkInvariants(); };
6425 auto const onDCls
= [&] (const DCls
& dcls
, bool isObj
) {
6426 auto newT
= [&] () -> Optional
<Type
> {
6427 if (dcls
.isIsect()) {
6428 auto const& isect
= dcls
.isect();
6432 [] (res::Class i
) { return i
.isSerialized(); }
6434 return std::nullopt
;
6436 auto const nonReg
= dcls
.containsNonRegular();
6438 auto out
= TInitCell
;
6439 for (auto const i
: isect
) {
6440 auto const u
= i
.unserialize(index
);
6441 if (!u
) return TBottom
;
6442 out
&= isObj
? subObj(*u
) : subCls(*u
, nonReg
);
6445 } else if (dcls
.isIsectAndExact()) {
6446 auto const [e
, isect
] = dcls
.isectAndExact();
6447 if (!e
.isSerialized() &&
6451 [] (res::Class i
) { return i
.isSerialized(); }
6453 return std::nullopt
;
6455 auto const nonReg
= dcls
.containsNonRegular();
6457 auto const eu
= e
.unserialize(index
);
6458 if (!eu
) return TBottom
;
6459 auto out
= isObj
? objExact(*eu
) : clsExact(*eu
, nonReg
);
6460 for (auto const i
: *isect
) {
6461 auto const u
= i
.unserialize(index
);
6462 if (!u
) return TBottom
;
6463 out
&= isObj
? subObj(*u
) : subCls(*u
, nonReg
);
6467 auto const& cls
= dcls
.cls();
6468 if (!cls
.isSerialized()) return std::nullopt
;
6469 auto const u
= cls
.unserialize(index
);
6470 if (!u
) return TBottom
;
6472 if (dcls
.isExact()) {
6475 : clsExact(*u
, dcls
.containsNonRegular());
6477 assertx(dcls
.isSub());
6480 : subCls(*u
, dcls
.containsNonRegular());
6482 return std::nullopt
;
6488 if (newT
->is(BBottom
)) {
6489 p
= isObj
? remove_obj(std::move(p
)) : remove_cls(std::move(p
));
6491 auto const bits
= p
.m_bits
;
6492 auto const mark
= p
.m_legacyMark
;
6493 p
= setctx(std::move(*newT
), dcls
.isCtx());
6495 p
.m_legacyMark
= mark
;
6499 switch (t
.m_dataTag
) {
6504 case DataTag::LazyCls
:
6505 case DataTag::EnumClassLabel
:
6506 case DataTag::ArrLikeVal
:
6507 // These can never contain objects or classes.
6509 case DataTag::WaitHandle
: {
6510 WaitHandleCOWer next
{parent
, *t
.m_data
.dwh
};
6511 unserialize_classes_impl(index
, next
.get().inner
, next
);
6512 auto const& dcls
= next
.get().cls
;
6513 if (dcls
.cls().isSerialized()) {
6514 auto const u
= dcls
.cls().unserialize(index
);
6515 assertx(u
.has_value());
6516 next
.getAndCOW().cls
.setCls(*u
);
6518 assertx(!dcls
.isIsect());
6521 case DataTag::ArrLikePacked
: {
6522 ArrLikePackedCOWer next
{parent
, *t
.m_data
.packed
};
6524 unserialize_classes_impl(index
, next
.currentElem(), next
);
6525 if (next
.currentElem().is(BBottom
)) {
6527 p
= remove_bits(std::move(p
), BArrLikeN
);
6530 } while (next
.nextElem());
6533 case DataTag::ArrLikePackedN
: {
6534 ArrLikePackedNCOWer next
{parent
, *t
.m_data
.packedn
};
6535 unserialize_classes_impl(index
, next
.get().type
, next
);
6536 if (next
.get().type
.is(BBottom
)) {
6538 p
= remove_bits(std::move(p
), BArrLikeN
);
6542 case DataTag::ArrLikeMap
: {
6543 ArrLikeMapCOWer next
{parent
, *t
.m_data
.map
};
6544 auto isBottom
= false;
6546 unserialize_classes_impl(index
, next
.currentElem(), next
);
6547 if (next
.currentElem().is(BBottom
)) {
6549 p
= remove_bits(std::move(p
), BArrLikeN
);
6553 } while(next
.nextElem());
6555 assertx(next
.optKeyOrValue().is(BBottom
) ||
6556 next
.optKeyOrValue().subtypeOf(BArrKey
));
6557 assertx(!next
.optKeyOrValue().couldBe(BCls
| BObj
));
6559 unserialize_classes_impl(index
, next
.optKeyOrValue(), next
);
6563 case DataTag::ArrLikeMapN
: {
6564 ArrLikeMapNCOWer next
{parent
, *t
.m_data
.mapn
};
6565 assertx(next
.keyOrValue().subtypeOf(BArrKey
));
6566 assertx(!next
.keyOrValue().couldBe(BCls
| BObj
));
6568 unserialize_classes_impl(index
, next
.keyOrValue(), next
);
6569 if (next
.keyOrValue().is(BBottom
)) {
6571 p
= remove_bits(std::move(p
), BArrLikeN
);
6576 onDCls(t
.m_data
.dobj
, true);
6579 onDCls(t
.m_data
.dcls
, false);
6584 Type
unserialize_classes(const IIndex
& index
, Type t
) {
6586 unserialize_classes_impl(index
, t
, cower
);
6590 //////////////////////////////////////////////////////////////////////
6592 IterTypes
iter_types(const Type
& iterable
) {
6593 // Only array types and objects can be iterated. Everything else raises a
6594 // warning and jumps out of the loop.
6595 if (!iterable
.couldBe(BArrLike
| BObj
| BClsMeth
)) {
6596 return { TBottom
, TBottom
, IterTypes::Count::Empty
, true, true };
6599 // Optional types are okay here because a null will not set any locals (but it
6601 if (!iterable
.subtypeOf(BOptArrLike
)) {
6605 IterTypes::Count::Any
,
6607 iterable
.couldBe(BObj
)
6611 auto const mayThrow
= iterable
.couldBe(BInitNull
);
6613 if (iterable
.subtypeOf(BOptArrLikeE
)) {
6614 return { TBottom
, TBottom
, IterTypes::Count::Empty
, mayThrow
, false };
6617 // If we get a null, it will be as if we have any empty array, so consider
6618 // that possibly "empty".
6619 auto const maybeEmpty
= mayThrow
|| !iterable
.subtypeOf(BOptArrLikeN
);
6621 auto const count
= [&] (Optional
<size_t> size
) {
6626 ? IterTypes::Count::ZeroOrOne
6627 : IterTypes::Count::Single
;
6630 return maybeEmpty
? IterTypes::Count::Any
: IterTypes::Count::NonEmpty
;
6633 if (!is_specialized_array_like(iterable
)) {
6634 auto kv
= [&]() -> std::pair
<Type
, Type
> {
6635 if (iterable
.subtypeOf(BInitNull
| BSVec
)) {
6636 return { TInt
, TInitUnc
};
6638 if (iterable
.subtypeOf(BInitNull
| BSKeyset
)) {
6639 return { TUncArrKey
, TUncArrKey
};
6641 if (iterable
.subtypeOf(BInitNull
| BSArrLike
)) {
6642 return { TUncArrKey
, TInitUnc
};
6644 if (iterable
.subtypeOf(BInitNull
| BVec
)) {
6645 return { TInt
, TInitCell
};
6647 if (iterable
.subtypeOf(BInitNull
| BKeyset
)) {
6648 return { TArrKey
, TArrKey
};
6650 return { TArrKey
, TInitCell
};
6654 std::move(kv
.first
),
6655 std::move(kv
.second
),
6656 count(std::nullopt
),
6662 switch (iterable
.m_dataTag
) {
6665 case DataTag::LazyCls
:
6666 case DataTag::EnumClassLabel
:
6668 case DataTag::WaitHandle
:
6672 always_assert(false);
6673 case DataTag::ArrLikeVal
: {
6674 auto [key
, val
, _
] = val_key_values(iterable
.m_data
.aval
);
6678 count(iterable
.m_data
.aval
->size()),
6683 case DataTag::ArrLikePacked
:
6685 packed_key(*iterable
.m_data
.packed
),
6686 packed_values(*iterable
.m_data
.packed
),
6687 count(iterable
.m_data
.packed
->elems
.size()),
6691 case DataTag::ArrLikePackedN
:
6694 iterable
.m_data
.packedn
->type
,
6695 count(std::nullopt
),
6699 case DataTag::ArrLikeMap
: {
6700 auto kv
= map_key_values(*iterable
.m_data
.map
);
6702 std::move(kv
.first
),
6703 std::move(kv
.second
),
6704 iterable
.m_data
.map
->hasOptElements()
6705 ? count(std::nullopt
)
6706 : count(iterable
.m_data
.map
->map
.size()),
6711 case DataTag::ArrLikeMapN
:
6713 iterable
.m_data
.mapn
->key
,
6714 iterable
.m_data
.mapn
->val
,
6715 count(std::nullopt
),
6724 bool could_contain_objects(const Type
& t
) {
6725 if (t
.couldBe(BObj
)) return true;
6726 if (!t
.couldBe(BCArrLikeN
)) return false;
6728 switch (t
.m_dataTag
) {
6731 case DataTag::LazyCls
:
6732 case DataTag::EnumClassLabel
:
6734 case DataTag::WaitHandle
:
6739 case DataTag::ArrLikeVal
: return false;
6740 case DataTag::ArrLikePacked
:
6741 for (auto const& e
: t
.m_data
.packed
->elems
) {
6742 if (could_contain_objects(e
)) return true;
6745 case DataTag::ArrLikePackedN
:
6746 return could_contain_objects(t
.m_data
.packedn
->type
);
6747 case DataTag::ArrLikeMap
:
6748 for (auto const& kv
: t
.m_data
.map
->map
) {
6749 if (could_contain_objects(kv
.second
.val
)) return true;
6751 if (could_contain_objects(t
.m_data
.map
->optVal
)) return true;
6753 case DataTag::ArrLikeMapN
:
6754 return could_contain_objects(t
.m_data
.mapn
->val
);
6760 bool is_type_might_raise(const Type
& testTy
, const Type
& valTy
) {
6761 auto const mayLogClsMeth
=
6762 Cfg::Eval::IsVecNotices
&&
6763 valTy
.couldBe(BClsMeth
) &&
6764 (testTy
.is(BVec
| BClsMeth
) ||
6765 testTy
.is(BArrLike
| BClsMeth
));
6767 assertx(!testTy
.is(BVec
| BClsMeth
));
6768 assertx(!mayLogClsMeth
);
6770 if (testTy
.couldBe(BInitNull
) && !testTy
.subtypeOf(BInitNull
)) {
6771 return is_type_might_raise(unopt(testTy
), valTy
);
6774 if (testTy
.is(BStr
| BCls
| BLazyCls
)) {
6775 return Cfg::Eval::ClassIsStringNotices
&& valTy
.couldBe(BCls
| BLazyCls
);
6776 } else if (testTy
.is(BVec
) || testTy
.is(BVec
| BClsMeth
)) {
6777 return mayLogClsMeth
;
6778 } else if (testTy
.is(BDict
)) {
6784 bool is_type_might_raise(IsTypeOp testOp
, const Type
& valTy
) {
6786 case IsTypeOp::Scalar
:
6787 case IsTypeOp::LegacyArrLike
:
6790 return is_type_might_raise(type_of_istype(testOp
), valTy
);
6794 bool inner_types_might_raise(const Type
& t1
, const Type
& t2
) {
6795 assertx(t1
.subtypeOf(BArrLike
));
6796 assertx(t2
.subtypeOf(BArrLike
));
6798 // If either is an empty array, there are no inner elements to warn about.
6799 if (!t1
.couldBe(BArrLikeN
) || !t2
.couldBe(BArrLikeN
)) return false;
6801 auto const checkOne
= [&] (const Type
& t
, Optional
<size_t>& sz
) {
6802 switch (t
.m_dataTag
) {
6807 case DataTag::LazyCls
:
6808 case DataTag::EnumClassLabel
:
6810 case DataTag::WaitHandle
:
6816 case DataTag::ArrLikeVal
:
6817 sz
= t
.m_data
.aval
->size();
6819 case DataTag::ArrLikePacked
:
6820 sz
= t
.m_data
.packed
->elems
.size();
6822 case DataTag::ArrLikePackedN
:
6823 return t
.m_data
.packedn
->type
.couldBe(BArrLike
| BObj
| BClsMeth
);
6824 case DataTag::ArrLikeMap
:
6825 if (!t
.m_data
.map
->hasOptElements()) sz
= t
.m_data
.map
->map
.size();
6827 case DataTag::ArrLikeMapN
:
6828 return t
.m_data
.mapn
->val
.couldBe(BArrLike
| BObj
| BClsMeth
);
6833 Optional
<size_t> sz1
;
6834 if (!checkOne(t1
, sz1
)) return false;
6835 Optional
<size_t> sz2
;
6836 if (!checkOne(t2
, sz2
)) return false;
6838 // if the arrays have different sizes, we don't even check their contents
6839 if (sz1
&& sz2
&& *sz1
!= *sz2
) return false;
6840 size_t numToCheck
= 1;
6841 if (sz1
&& *sz1
> numToCheck
) numToCheck
= *sz1
;
6842 if (sz2
&& *sz2
> numToCheck
) numToCheck
= *sz2
;
6847 MapElems::iterator it
;
6850 Optional
<Type
> vals1
;
6851 Optional
<Type
> vals2
;
6853 for (size_t i
= 0; i
< numToCheck
; i
++) {
6854 auto const nextType
= [&] (const Type
& t
,
6856 Optional
<Type
>& vals
) {
6857 switch (t
.m_dataTag
) {
6862 case DataTag::LazyCls
:
6863 case DataTag::EnumClassLabel
:
6865 case DataTag::WaitHandle
:
6871 case DataTag::ArrLikeVal
:
6873 p
.pos
= t
.m_data
.aval
->iter_begin();
6875 p
.pos
= t
.m_data
.aval
->iter_advance(p
.pos
);
6877 return from_cell(t
.m_data
.aval
->nvGetVal(p
.pos
));
6878 case DataTag::ArrLikePacked
:
6879 return t
.m_data
.packed
->elems
[i
];
6880 case DataTag::ArrLikePackedN
:
6881 return t
.m_data
.packedn
->type
;
6882 case DataTag::ArrLikeMap
:
6883 if (t
.m_data
.map
->hasOptElements()) {
6884 if (!vals
) vals
= map_key_values(*t
.m_data
.map
).second
;
6889 p
.it
= t
.m_data
.map
->map
.begin();
6893 return p
.it
->second
.val
;
6894 case DataTag::ArrLikeMapN
:
6895 return t
.m_data
.mapn
->val
;
6899 if (compare_might_raise(nextType(t1
, p1
, vals1
), nextType(t2
, p2
, vals2
))) {
6906 bool compare_might_raise(const Type
& t1
, const Type
& t2
) {
6907 if (!Cfg::Eval::EmitClsMethPointers
&&
6908 Cfg::Eval::RaiseClassConversionNoticeSampleRate
== 0) {
6912 auto const checkOne
= [&] (const trep bits
) -> Optional
<bool> {
6913 if (t1
.subtypeOf(bits
) && t2
.subtypeOf(bits
)) {
6914 return inner_types_might_raise(t1
, t2
);
6916 if (t1
.couldBe(bits
) && t2
.couldBe(BArrLike
)) return true;
6917 if (t2
.couldBe(bits
) && t1
.couldBe(BArrLike
)) return true;
6918 return std::nullopt
;
6921 if (auto const f
= checkOne(BDict
)) return *f
;
6922 if (auto const f
= checkOne(BVec
)) return *f
;
6923 if (auto const f
= checkOne(BKeyset
)) return *f
;
6925 if (Cfg::Eval::EmitClsMethPointers
) {
6926 if (t1
.couldBe(BClsMeth
) && t2
.couldBe(BVec
)) return true;
6927 if (t1
.couldBe(BVec
) && t2
.couldBe(BClsMeth
)) return true;
6930 if (Cfg::Eval::RaiseClassConversionNoticeSampleRate
> 0) {
6931 if (t1
.couldBe(BStr
) && t2
.couldBe(BLazyCls
)) return true;
6932 if (t1
.couldBe(BStr
) && t2
.couldBe(BCls
)) return true;
6933 if (t1
.couldBe(BLazyCls
) && t2
.couldBe(BStr
)) return true;
6934 if (t1
.couldBe(BCls
) && t2
.couldBe(BStr
)) return true;
6937 return t1
.couldBe(BObj
) && t2
.couldBe(BObj
);
6940 //////////////////////////////////////////////////////////////////////
6942 std::pair
<Type
, bool> array_like_elem(const Type
& arr
, const Type
& key
) {
6943 assertx(arr
.couldBe(BArrLike
));
6944 assertx(key
.subtypeOf(BArrKey
));
6945 assertx(!key
.is(BBottom
));
6947 // Fast path: if the array is one specific type, we can just do the
6948 // lookup without intersections.
6949 if (arr
.subtypeAmong(BVec
, BArrLike
) ||
6950 arr
.subtypeAmong(BDict
, BArrLike
) ||
6951 arr
.subtypeAmong(BKeyset
, BArrLike
)) {
6952 return array_like_elem_impl(arr
, key
);
6955 // Otherwise split up the array into its constituent array types, do
6956 // the lookup for each one, then union together the results.
6957 auto elem
= TBottom
;
6958 auto present
= true;
6959 auto const combine
= [&] (std::pair
<Type
, bool> r
) {
6960 elem
|= std::move(r
.first
);
6961 present
&= r
.second
;
6963 if (arr
.couldBe(BVec
)) {
6964 combine(array_like_elem_impl(intersection_of(arr
, TVec
), key
));
6966 if (arr
.couldBe(BDict
)) {
6967 combine(array_like_elem_impl(intersection_of(arr
, TDict
), key
));
6969 if (arr
.couldBe(BKeyset
)) {
6970 combine(array_like_elem_impl(intersection_of(arr
, TKeyset
), key
));
6972 return std::make_pair(elem
, present
);
6975 std::pair
<Type
, bool> arr_val_elem(const Type
& arr
, const Type
& key
) {
6976 assertx(arr
.m_dataTag
== DataTag::ArrLikeVal
);
6977 assertx(key
.subtypeOf(BArrKey
));
6979 auto const ad
= arr
.m_data
.aval
;
6980 assertx(!ad
->empty());
6982 if (auto const k
= tvCounted(key
)) {
6983 auto const r
= ad
->get(*k
);
6984 if (r
.is_init()) return { from_cell(r
), true };
6985 return { TBottom
, false };
6988 auto const loosened
= loosen_string_staticness(key
);
6993 [&] (TypedValue k
, TypedValue v
) {
6994 if (from_cell(k
).couldBe(loosened
)) ty
|= from_cell(v
);
6995 return !ty
.strictSubtypeOf(BInitUnc
);
6998 assertx(ty
.subtypeOf(BInitUnc
));
6999 return { ty
, false };
7002 std::pair
<Type
, bool> arr_packed_elem(const Type
& arr
, const Type
& key
) {
7003 assertx(arr
.m_dataTag
== DataTag::ArrLikePacked
);
7004 assertx(key
.subtypeOf(BArrKey
));
7006 if (!key
.couldBe(BInt
)) return { TBottom
, false };
7008 auto const& pack
= *arr
.m_data
.packed
;
7009 if (is_specialized_int(key
)) {
7010 auto const idx
= ival_of(key
);
7011 if (idx
>= 0 && idx
< pack
.elems
.size()) {
7012 return { pack
.elems
[idx
], key
.subtypeOf(BInt
) };
7014 return { TBottom
, false };
7017 return { packed_values(pack
), false };
7020 std::pair
<Type
, bool> arr_packedn_elem(const Type
& arr
, const Type
& key
) {
7021 assertx(arr
.m_dataTag
== DataTag::ArrLikePackedN
);
7022 assertx(key
.subtypeOf(BArrKey
));
7024 if (!key
.couldBe(BInt
)) return { TBottom
, false };
7025 if (is_specialized_int(key
) && ival_of(key
) < 0) {
7026 return { TBottom
, false };
7028 return { arr
.m_data
.packedn
->type
, false };
7031 std::pair
<Type
, bool> arr_map_elem(const Type
& arr
, const Type
& key
) {
7032 assertx(arr
.m_dataTag
== DataTag::ArrLikeMap
);
7033 assertx(key
.subtypeOf(BArrKey
));
7034 assertx(!key
.is(BBottom
));
7036 auto const& map
= *arr
.m_data
.map
;
7038 // If the key has a known value, it either matches a known key in
7039 // the map, or it doesn't, but could match the optional key. The
7040 // known keys and the optional key are disjoint, so we can skip it
7041 // for an exact match.
7042 if (auto const k
= tvCounted(key
)) {
7043 auto const it
= map
.map
.find(*k
);
7044 if (it
!= map
.map
.end()) return { it
->second
.val
, true };
7045 if (loosen_string_staticness(map
.optKey
).couldBe(key
)) {
7046 return { map
.optVal
, false };
7048 return { TBottom
, false };
7052 for (auto const& kv
: map
.map
) {
7053 if (map_key_nonstatic(kv
.first
).couldBe(key
)) ty
|= kv
.second
.val
;
7054 if (!ty
.strictSubtypeOf(BInitCell
)) break;
7056 if (loosen_string_staticness(map
.optKey
).couldBe(key
)) {
7059 return { ty
, false };
7062 std::pair
<Type
, bool> arr_mapn_elem(const Type
& arr
, const Type
& key
) {
7063 assertx(arr
.m_dataTag
== DataTag::ArrLikeMapN
);
7064 assertx(key
.subtypeOf(BArrKey
));
7065 if (!loosen_string_staticness(key
).couldBe(arr
.m_data
.mapn
->key
)) {
7066 return { TBottom
, false };
7068 return { arr
.m_data
.mapn
->val
, false };
7071 std::pair
<Type
, bool> array_like_elem_impl(const Type
& arr
, const Type
& key
) {
7072 assertx(!arr
.is(BBottom
));
7073 assertx(arr
.subtypeAmong(BVec
, BArrLike
) ||
7074 arr
.subtypeAmong(BDict
, BArrLike
) ||
7075 arr
.subtypeAmong(BKeyset
, BArrLike
));
7076 assertx(key
.subtypeOf(BArrKey
));
7077 assertx(!key
.is(BBottom
));
7079 // If it's always empty, there's nothing to lookup
7080 if (!arr
.couldBe(BArrLikeN
)) return { TBottom
, false };
7082 auto r
= [&] () -> std::pair
<Type
, bool> {
7083 switch (arr
.m_dataTag
) {
7085 case DataTag::LazyCls
:
7086 case DataTag::EnumClassLabel
:
7088 case DataTag::WaitHandle
:
7092 case DataTag::None
: {
7093 // Even without a specialization, there's some special cases
7095 if (arr
.subtypeAmong(BVecN
, BArrLikeN
)) {
7096 if (!key
.couldBe(BInt
)) return { TBottom
, false };
7097 if (is_specialized_int(key
) && ival_of(key
) < 0) {
7098 return { TBottom
, false };
7101 // Otherwise we can use the staticness to determine a possible
7103 auto const isStatic
= arr
.subtypeAmong(BSArrLikeN
, BArrLikeN
);
7104 if (arr
.subtypeAmong(BKeysetN
, BArrLikeN
)) {
7105 return { isStatic
? TUncArrKey
: TArrKey
, false };
7107 return { isStatic
? TInitUnc
: TInitCell
, false };
7109 case DataTag::ArrLikeVal
:
7110 return arr_val_elem(arr
, key
);
7111 case DataTag::ArrLikePacked
:
7112 return arr_packed_elem(arr
, key
);
7113 case DataTag::ArrLikePackedN
:
7114 return arr_packedn_elem(arr
, key
);
7115 case DataTag::ArrLikeMap
:
7116 return arr_map_elem(arr
, key
);
7117 case DataTag::ArrLikeMapN
:
7118 return arr_mapn_elem(arr
, key
);
7122 // If the array could be empty, we're never sure we'll find the
7124 if (arr
.couldBe(BArrLikeE
)) r
.second
= false;
7125 if (arr
.subtypeAmong(BKeysetN
, BArrLikeN
)) {
7126 // Enforce the invariant that the value returned for a Keyset
7127 // always matches the key.
7128 r
.first
= intersection_of(
7130 loosen_string_staticness(key
)
7136 //////////////////////////////////////////////////////////////////////
7138 std::pair
<Type
, bool> array_like_set(Type base
,
7141 assertx(base
.subtypeOf(BCell
));
7142 assertx(base
.couldBe(BArrLike
));
7143 assertx(key
.subtypeOf(BArrKey
));
7144 assertx(!key
.is(BBottom
));
7146 // NB: Be careful here about unnecessarily copying base/arr
7147 // here. The impl function will mutate the specialization and we
7148 // want to modify it in place as much as possible. So we go out of
7149 // our way to move in as many cases as we can.
7151 auto [arr
, rest
] = split_array_like(std::move(base
));
7152 if (arr
.subtypeOf(BVec
) || arr
.subtypeOf(BDict
)) {
7153 // Fast path, we do the set directly without splitting the array
7154 // into its specific types.
7155 auto r
= array_like_set_impl(std::move(arr
), key
, val
);
7156 return std::make_pair(
7157 union_of(std::move(r
.first
), std::move(rest
)),
7162 // Sets aren't allowed on a keyset.
7163 if (arr
.subtypeOf(BKeyset
)) return std::make_pair(std::move(rest
), true);
7165 // Otherwise split the array intoits specific array types, do the
7166 // set on each one, then union the results back together.
7167 auto result
= TBottom
;
7168 auto mightThrow
= false;
7169 auto const combine
= [&] (std::pair
<Type
, bool> r
) {
7170 result
|= std::move(r
.first
);
7171 mightThrow
|= r
.second
;
7174 if (arr
.couldBe(BVec
)) {
7175 // If this is the last usage of arr, move it instead of copying.
7177 if (arr
.couldBe(BDict
)) {
7183 array_like_set_impl(intersection_of(std::move(i
), TVec
), key
, val
)
7186 if (arr
.couldBe(BDict
)) {
7188 array_like_set_impl(intersection_of(std::move(arr
), TDict
), key
, val
)
7191 if (arr
.couldBe(BKeyset
)) mightThrow
= true;
7193 return std::make_pair(
7194 union_of(std::move(result
), std::move(rest
)),
7199 bool arr_packed_set(Type
& pack
,
7203 assertx(pack
.m_dataTag
== DataTag::ArrLikePacked
);
7204 assertx(key
.subtypeOf(BArrKey
));
7206 auto& packed
= pack
.m_data
.packed
;
7208 if (pack
.subtypeOf(BVec
)) {
7209 if (is_specialized_int(key
)) {
7210 auto const idx
= ival_of(key
);
7211 if (idx
< 0 || idx
>= packed
->elems
.size()) {
7215 packed
.mutate()->elems
[idx
] = val
;
7216 return maybeEmpty
|| !key
.subtypeOf(BInt
);
7219 for (auto& e
: packed
.mutate()->elems
) e
|= val
;
7223 if (auto const k
= tvCounted(key
)) {
7224 if (isIntType(k
->m_type
)) {
7225 if (k
->m_data
.num
>= 0) {
7227 if (k
->m_data
.num
== 0) {
7228 if (packed
->elems
.size() == 1) {
7229 packed
.mutate()->elems
[0] = val
;
7232 pack
= packedn_impl(
7235 union_of(packed_values(*packed
), val
)
7240 if (k
->m_data
.num
< packed
->elems
.size()) {
7241 packed
.mutate()->elems
[k
->m_data
.num
] = val
;
7244 if (k
->m_data
.num
== packed
->elems
.size()) {
7245 packed
.mutate()->elems
.push_back(val
);
7254 for (size_t i
= 0; i
< packed
->elems
.size(); ++i
) {
7256 make_tv
<KindOfInt64
>(i
),
7257 MapElem::IntKey(packed
->elems
[i
])
7260 elems
.emplace_back(*k
, MapElem::KeyFromType(key
, val
));
7262 map_impl(pack
.bits(), pack
.m_legacyMark
, std::move(elems
), TBottom
, TBottom
);
7270 union_of(packed_key(*packed
), key
),
7271 union_of(packed_values(*packed
), val
)
7276 bool arr_packedn_set(Type
& pack
,
7280 assertx(pack
.m_dataTag
== DataTag::ArrLikePackedN
);
7281 assertx(key
.subtypeOf(BArrKey
));
7283 auto const keepPacked
= [&] (bool mightThrow
) {
7284 auto t
= union_of(pack
.m_data
.packedn
->type
, val
);
7285 if (pack
.subtypeOf(BVec
) && !t
.strictSubtypeOf(BInitCell
)) {
7286 pack
= Type
{ pack
.bits(), pack
.m_legacyMark
};
7288 pack
.m_data
.packedn
.mutate()->type
= std::move(t
);
7293 if (pack
.subtypeOf(BVec
)) {
7294 if (is_specialized_int(key
)) {
7295 auto const idx
= ival_of(key
);
7300 if (idx
== 0 && !maybeEmpty
&& key
.subtypeOf(BInt
)) {
7301 return keepPacked(false);
7304 return keepPacked(true);
7307 if (auto const k
= tvCounted(key
)) {
7308 if (isIntType(k
->m_type
)) {
7309 if (k
->m_data
.num
== 0) return keepPacked(false);
7310 if (k
->m_data
.num
== 1 && !maybeEmpty
) return keepPacked(false);
7317 union_of(TInt
, key
),
7318 union_of(pack
.m_data
.packedn
->type
, val
)
7323 bool arr_map_set(Type
& map
,
7327 assertx(map
.m_dataTag
== DataTag::ArrLikeMap
);
7328 assertx(key
.subtypeOf(BArrKey
));
7329 assertx(!map
.subtypeOf(BVec
));
7331 auto mutated
= map
.m_data
.map
.mutate();
7333 // NB: At runtime, keysets do *not* get updated with the new value
7334 // if there's a match. This is irrelevant for tracking the key
7335 // values, but matters with regards to staticness.
7338 // If the array could be empty, we have to effectively deal with
7339 // the union of a single element array (the result of the set on
7340 // the empty array), and the updated non-empty array. In most
7341 // cases this cannot be represented with a Map representation and
7342 // we need to fall back to MapN.
7343 if (auto const k
= tvCounted(key
)) {
7344 // Special case: if the key is known and matches the first key
7345 // of the map, we can keep the map representation. The first
7346 // element is known and the rest of the values become optional.
7347 assertx(!mutated
->map
.empty());
7348 if (tvSame(mutated
->map
.begin()->first
, *k
)) {
7349 auto it
= mutated
->map
.begin();
7350 auto mapKey
= map_key(it
->first
, it
->second
);
7351 DEBUG_ONLY
auto const& mapVal
= it
->second
.val
;
7353 auto restKey
= mutated
->optKey
;
7354 auto restVal
= mutated
->optVal
;
7355 while (it
!= mutated
->map
.end()) {
7356 restKey
|= map_key(it
->first
, it
->second
);
7357 restVal
|= it
->second
.val
;
7361 if (!map
.subtypeOf(BKeyset
)) {
7364 MapElem::KeyFromType(union_of(std::move(mapKey
), key
), val
)
7367 // For Keysets we also have to deal with possibly no longer
7368 // knowing the key's staticness.
7369 assertx(key
== val
);
7370 assertx(mapKey
== mapVal
);
7371 auto const u
= union_of(std::move(mapKey
), key
);
7374 MapElem::KeyFromType(u
, u
)
7389 // Otherwise we cannot represent the result precisely and must use
7391 auto mkv
= map_key_values(*mutated
);
7395 union_of(key
, std::move(mkv
.first
)),
7396 union_of(val
, std::move(mkv
.second
))
7401 // If the array cannot be empty, we can always keep the Map
7404 if (auto const k
= tvCounted(key
)) {
7405 // The new key is known
7406 if (auto const it
= mutated
->map
.find(*k
); it
!= mutated
->map
.end()) {
7407 // It matches an existing key. Set its associated type to be the
7409 if (!map
.subtypeOf(BKeyset
)) {
7410 mutated
->map
.update(it
, it
->second
.withType(val
));
7415 if (mutated
->hasOptElements()) {
7416 // The Map has optional elements. If the optional element
7417 // represents a single key, and that key is the same as the new
7418 // key, we can turn the optional element into a known key. An
7419 // optional element representing a single key means "this array
7420 // might end with this key, or might not". Since we're setting
7421 // this key, the new array definitely ends with that key.
7422 if (auto const optK
= tvCounted(mutated
->optKey
)) {
7423 if (tvSame(*optK
, *k
)) {
7424 if (!map
.subtypeOf(BKeyset
)) {
7425 mutated
->map
.emplace_back(
7427 MapElem::KeyFromType(union_of(key
, mutated
->optKey
), val
)
7430 // For Keysets we also have to deal with possibly no
7431 // longer knowing the key's staticness.
7432 assertx(key
== val
);
7433 assertx(mutated
->optKey
== mutated
->optVal
);
7434 auto const u
= union_of(key
, mutated
->optKey
);
7435 mutated
->map
.emplace_back(
7437 MapElem::KeyFromType(u
, u
)
7440 mutated
->optKey
= TBottom
;
7441 mutated
->optVal
= TBottom
;
7445 // Otherwise just add the new key and value to the optional
7446 // elements. We've lost the complete key structure of the array.
7447 mutated
->optKey
|= key
;
7448 mutated
->optVal
|= val
;
7450 // There's no optional elements and we know this key doesn't
7451 // exist in the Map. Add it as the next known key.
7452 mutated
->map
.emplace_back(*k
, MapElem::KeyFromType(key
, val
));
7457 // The new key isn't known. The key either matches an existing key,
7458 // or its a new one. For an existing key which can possibly match,
7459 // union in the new value type. Then add the new key and value to
7460 // the optional elements since it might not match. We don't have to
7461 // modify the known keys for Keysets because at runtime updates
7462 // never modify existing values.
7463 if (!map
.subtypeOf(BKeyset
)) {
7464 for (auto it
= mutated
->map
.begin(); it
!= mutated
->map
.end(); ++it
) {
7465 if (key
.couldBe(map_key_nonstatic(it
->first
))) {
7466 mutated
->map
.update(
7468 it
->second
.withType(union_of(it
->second
.val
, val
))
7473 mutated
->optKey
|= key
;
7474 mutated
->optVal
|= val
;
7478 std::pair
<Type
,bool> array_like_set_impl(Type arr
,
7481 // Note: array_like_set forbids Keysets, but this can be called by
7482 // array_like_newelem_impl, which does.
7483 assertx(arr
.subtypeOf(BVec
) ||
7484 arr
.subtypeOf(BDict
) ||
7485 arr
.subtypeOf(BKeyset
));
7486 assertx(key
.subtypeOf(BArrKey
));
7487 assertx(!arr
.is(BBottom
));
7488 assertx(!val
.is(BBottom
));
7489 assertx(!key
.is(BBottom
));
7490 assertx(IMPLIES(arr
.subtypeOf(BKeyset
), key
== val
));
7492 // Remove emptiness and loosen staticness from the bits
7493 auto const bits
= [&] {
7495 if (arr
.couldBe(BVec
)) b
|= BVecN
;
7496 if (arr
.couldBe(BDict
)) b
|= BDictN
;
7497 if (arr
.couldBe(BKeyset
)) b
|= BKeysetN
;
7501 // Before anything, check for specific cases of bad keys:
7502 if (arr
.subtypeOf(BVec
)) {
7503 if (!key
.couldBe(BInt
) || (is_specialized_int(key
) && ival_of(key
) < 0)) {
7504 return { TBottom
, true };
7508 if (!arr
.couldBe(BArrLikeN
)) {
7509 // Can't set into an empty Vec (only newelem)
7510 if (arr
.subtypeOf(BVec
)) return { TBottom
, true };
7511 // mapn_impl will use the appropriate map or packed representation
7512 return { mapn_impl(bits
, arr
.m_legacyMark
, key
, val
), false };
7515 switch (arr
.m_dataTag
) {
7517 case DataTag::LazyCls
:
7518 case DataTag::EnumClassLabel
:
7520 case DataTag::WaitHandle
:
7525 case DataTag::None
: {
7527 assertx(arr
.checkInvariants());
7528 auto const isVec
= arr
.subtypeOf(BVec
);
7529 return { std::move(arr
), isVec
};
7531 case DataTag::ArrLikeVal
:
7532 return array_like_set_impl(
7533 toDArrLike(arr
.m_data
.aval
, arr
.bits(), arr
.m_legacyMark
),
7536 case DataTag::ArrLikePacked
: {
7537 auto const maybeEmpty
= arr
.couldBe(BArrLikeE
);
7539 auto const mightThrow
= arr_packed_set(arr
, key
, val
, maybeEmpty
);
7540 assertx(arr
.checkInvariants());
7541 return { std::move(arr
), mightThrow
};
7543 case DataTag::ArrLikePackedN
: {
7544 auto const maybeEmpty
= arr
.couldBe(BArrLikeE
);
7546 auto const mightThrow
= arr_packedn_set(arr
, key
, val
, maybeEmpty
);
7547 assertx(arr
.checkInvariants());
7548 return { std::move(arr
), mightThrow
};
7550 case DataTag::ArrLikeMap
: {
7551 auto const maybeEmpty
= arr
.couldBe(BArrLikeE
);
7553 auto const mightThrow
= arr_map_set(arr
, key
, val
, maybeEmpty
);
7554 assertx(arr
.checkInvariants());
7555 return { std::move(arr
), mightThrow
};
7557 case DataTag::ArrLikeMapN
: {
7558 assertx(!arr
.subtypeOf(BVec
));
7560 auto m
= arr
.m_data
.mapn
.mutate();
7561 auto newKey
= union_of(std::move(m
->key
), key
);
7562 auto newVal
= union_of(std::move(m
->val
), val
);
7563 if (!newKey
.strictSubtypeOf(BArrKey
) &&
7564 !newVal
.strictSubtypeOf(
7565 arr
.subtypeOf(BKeyset
) ? BArrKey
: BInitCell
)
7567 return { Type
{ bits
, arr
.m_legacyMark
}, false };
7569 m
->key
= std::move(newKey
);
7570 m
->val
= std::move(newVal
);
7571 assertx(arr
.checkInvariants());
7572 return { std::move(arr
), false };
7579 //////////////////////////////////////////////////////////////////////
7581 std::pair
<Type
, bool> array_like_newelem(Type base
, const Type
& val
) {
7582 assertx(base
.subtypeOf(BCell
));
7583 assertx(base
.couldBe(BArrLike
));
7584 assertx(val
.subtypeOf(BInitCell
));
7586 // NB: Be careful here about unnecessarily copying base/arr
7587 // here. The impl function will mutate the specialization and we
7588 // want to modify it in place as much as possible. So we go out of
7589 // our way to move in as many cases as we can.
7590 auto [arr
, rest
] = split_array_like(std::move(base
));
7592 // Fast path: if the array is just one of the specific array types,
7593 // we can skip the intersection and do the newelem directly.
7594 if (arr
.subtypeOf(BVec
) ||
7595 arr
.subtypeOf(BDict
) ||
7596 arr
.subtypeOf(BKeyset
)) {
7597 auto r
= array_like_newelem_impl(std::move(arr
), val
);
7598 return std::make_pair(
7599 union_of(std::move(r
.first
), std::move(rest
)),
7604 // Otherwise split the array into its specific types and perform the
7605 // newelem on each one, then union the results together.
7607 auto result
= TBottom
;
7608 auto mightThrow
= false;
7609 auto const combine
= [&] (std::pair
<Type
, bool> r
) {
7610 result
|= std::move(r
.first
);
7611 mightThrow
|= r
.second
;
7614 if (arr
.couldBe(BVec
)) {
7615 combine(array_like_newelem_impl(intersection_of(arr
, TVec
), val
));
7617 if (arr
.couldBe(BDict
)) {
7618 // Try to move arr instead of copying if this will be the last
7621 if (arr
.couldBe(BKeyset
)) {
7627 array_like_newelem_impl(intersection_of(std::move(i
), TDict
), val
)
7630 if (arr
.couldBe(BKeyset
)) {
7632 array_like_newelem_impl(intersection_of(std::move(arr
), TKeyset
), val
)
7635 return std::make_pair(
7636 union_of(std::move(result
), std::move(rest
)),
7641 bool arr_map_newelem(Type
& map
, const Type
& val
, bool update
) {
7642 assertx(map
.m_dataTag
== DataTag::ArrLikeMap
);
7644 // If the highest key is int64_t max, the chosen key will wrap
7645 // around, which will trigger a warning and not actually append
7647 auto const findLastK
= [&] {
7649 for (auto const& kv
: map
.m_data
.map
->map
) {
7650 if (kv
.first
.m_type
== KindOfInt64
&&
7651 kv
.first
.m_data
.num
> lastK
) {
7652 lastK
= kv
.first
.m_data
.num
;
7658 // If the Map has optional elements, we can't know what the new key
7659 // is (but it won't modify known keys).
7660 if (map
.m_data
.map
->hasOptElements()) {
7661 // If the optional value is a single known key, we might still be
7662 // able to infer if the append might throw or not.
7663 auto mightThrow
= true;
7664 if (auto const v
= tvCounted(map
.m_data
.map
->optKey
)) {
7665 auto lastK
= findLastK();
7666 if (v
->m_type
== KindOfInt64
&& v
->m_data
.num
> lastK
) {
7667 lastK
= v
->m_data
.num
;
7669 mightThrow
= (lastK
== std::numeric_limits
<int64_t>::max());
7673 auto mutated
= map
.m_data
.map
.mutate();
7674 mutated
->optKey
|= TInt
;
7675 mutated
->optVal
|= val
;
7680 auto const lastK
= findLastK();
7681 if (lastK
== std::numeric_limits
<int64_t>::max()) return true;
7683 map
.m_data
.map
.mutate()->map
.emplace_back(
7684 make_tv
<KindOfInt64
>(lastK
+ 1),
7685 MapElem::IntKey(val
)
7688 // Otherwise we know the append will succeed without potentially
7693 std::pair
<Type
, bool> array_like_newelem_impl(Type arr
, const Type
& val
) {
7694 assertx(arr
.subtypeOf(BVec
) ||
7695 arr
.subtypeOf(BDict
) ||
7696 arr
.subtypeOf(BKeyset
));
7697 assertx(!arr
.is(BBottom
));
7698 assertx(!val
.is(BBottom
));
7700 // "Appends" on a keyset are actually modeled as a set with the same
7702 if (arr
.subtypeOf(BKeyset
)) {
7703 // Since the val is going to be used like a key, we need to deal
7704 // with promotions (and possible invalid keys).
7705 auto [key
, promotion
] = promote_classlike_to_key(val
);
7706 auto keyMaybeBad
= false;
7707 if (!key
.subtypeOf(BArrKey
)) {
7708 key
= intersection_of(std::move(key
), TArrKey
);
7711 if (key
.is(BBottom
)) return { TBottom
, true };
7712 auto r
= array_like_set_impl(std::move(arr
), key
, key
);
7715 r
.second
|| keyMaybeBad
|| promotion
== Promotion::YesMightThrow
7720 * NB: Appends on dicts and darrays can potentially throw for two
7723 * - If m_nextKI is negative, which means that the "next key" for
7724 * append would be a negative integer key. This raises a warning
7725 * (and does not append anything).
7727 * - If m_nextKI does not match the highest integer key in the array
7728 * (and if Eval.DictDArrayAppendNotices is true, which we
7729 * assume). This raises a notice.
7731 * Since HHBBC does not attempt to track m_nextKI for arrays, we
7732 * have to be pessimistic and assume that any append on a darry or
7733 * dict can throw. However we can avoid it in certain situations:
7735 * Since HHBBC pessimizes its knowledge of inner array structure
7736 * whenever it encounters an unset, if we have a specialized array
7737 * type, we know there's never been an unset on the array. Therefore
7738 * we can safely infer m_nextKI from what we know about the keys. If
7739 * the array is static, or if have an ArrLikeMap, we can iterate
7740 * over the keys. If we have a packed representation, we know the
7741 * keys are contiguous (and thus can only wrap if we have 2^63
7744 * This will have to be revisited if we ever decide to model unsets
7745 * (hopefully m_nextKI would be gone by then).
7748 // Loosen staticness and remove emptiness from the bits
7749 auto const bits
= [&] {
7751 if (arr
.couldBe(BVec
)) b
|= BVecN
;
7752 if (arr
.couldBe(BDict
)) b
|= BDictN
;
7756 if (!arr
.couldBe(BArrLikeN
)) {
7758 packed_impl(bits
, arr
.m_legacyMark
, { val
}),
7759 false // Appends cannot throw on an empty array
7763 switch (arr
.m_dataTag
) {
7765 case DataTag::LazyCls
:
7766 case DataTag::EnumClassLabel
:
7768 case DataTag::WaitHandle
:
7773 case DataTag::None
: {
7775 assertx(arr
.checkInvariants());
7776 // Dict can throw on append, vec will not.
7777 auto const isDict
= arr
.subtypeOf(BDict
);
7778 return { std::move(arr
), isDict
};
7780 case DataTag::ArrLikeVal
:
7781 return array_like_newelem_impl(
7782 toDArrLike(arr
.m_data
.aval
, arr
.bits(), arr
.m_legacyMark
),
7785 case DataTag::ArrLikePacked
:
7786 // Packed arrays have contiguous keys, so the internal iterator
7787 // should match the size of the array. Therefore appends cannot
7789 if (arr
.couldBe(BArrLikeE
)) {
7792 bits
, arr
.m_legacyMark
,
7793 union_of(packed_values(*arr
.m_data
.packed
), val
)
7799 arr
.m_data
.packed
.mutate()->elems
.push_back(val
);
7800 assertx(arr
.checkInvariants());
7801 return { std::move(arr
), false };
7802 case DataTag::ArrLikePackedN
:
7803 // Ditto, with regards to packed array appends not throwing.
7804 if (arr
.subtypeOf(BVec
)) {
7805 auto t
= union_of(arr
.m_data
.packedn
.mutate()->type
, val
);
7806 if (!t
.strictSubtypeOf(BInitCell
)) {
7807 return { Type
{ bits
, arr
.m_legacyMark
}, false };
7810 arr
.m_data
.packedn
.mutate()->type
= std::move(t
);
7813 arr
.m_data
.packedn
.mutate()->type
|= val
;
7815 assertx(arr
.checkInvariants());
7816 return { std::move(arr
), false };
7817 case DataTag::ArrLikeMap
: {
7818 assertx(!arr
.subtypeOf(BVec
));
7819 if (arr
.couldBe(BArrLikeE
)) {
7820 // Dict and darray can throw on append depending on the state of
7821 // the internal iterator. This isn't an issue for an empty
7822 // array, so we use the possibility inferred from the non-empty
7824 auto const mightThrow
= arr_map_newelem(arr
, val
, false);
7825 auto mkv
= map_key_values(*arr
.m_data
.map
);
7830 union_of(std::move(mkv
.first
), TInt
),
7831 union_of(std::move(mkv
.second
), val
)
7837 auto const mightThrow
= arr_map_newelem(arr
, val
, true);
7838 assertx(arr
.checkInvariants());
7839 return { std::move(arr
), mightThrow
};
7841 case DataTag::ArrLikeMapN
: {
7842 // We don't know the specific keys of the map, so its possible
7843 // the append could throw.
7844 assertx(!arr
.subtypeOf(BVec
));
7846 auto m
= arr
.m_data
.mapn
.mutate();
7847 auto newKey
= union_of(std::move(m
->key
), TInt
);
7848 auto newVal
= union_of(std::move(m
->val
), val
);
7849 if (!newKey
.strictSubtypeOf(BArrKey
) &&
7850 !newVal
.strictSubtypeOf(BInitCell
)) {
7851 return { Type
{ bits
, arr
.m_legacyMark
}, true };
7853 m
->key
= std::move(newKey
);
7854 m
->val
= std::move(newVal
);
7855 assertx(arr
.checkInvariants());
7856 return { std::move(arr
), true };
7863 //////////////////////////////////////////////////////////////////////
7865 std::pair
<Type
, Promotion
> promote_classlike_to_key(Type ty
) {
7866 // Cls and LazyCls promotes to the name of the class it represents
7867 // (a static string). If its a Cls, we can possibly know the string
7869 auto promoted
= false;
7870 if (ty
.couldBe(BLazyCls
)) {
7872 if (!is_specialized_lazycls(ty
)) return TSStr
;
7873 auto const name
= lazyclsval_of(ty
);
7876 ty
= union_of(remove_lazycls(std::move(ty
)), std::move(t
));
7879 if (ty
.couldBe(BCls
)) {
7881 if (!is_specialized_cls(ty
)) return TSStr
;
7882 auto const& dcls
= dcls_of(ty
);
7883 if (!dcls
.isExact()) return TSStr
;
7884 return sval(dcls
.cls().name());
7886 ty
= union_of(remove_cls(std::move(ty
)), std::move(t
));
7890 return std::make_pair(
7893 ? (Cfg::Eval::RaiseClassConversionNoticeSampleRate
> 0
7894 ? Promotion::YesMightThrow
7900 //////////////////////////////////////////////////////////////////////
7902 Optional
<RepoAuthType
> make_repo_type_arr(const Type
& t
) {
7903 assertx(t
.subtypeOf(BOptArrLike
));
7904 assertx(is_specialized_array_like(t
));
7906 using T
= RepoAuthType::Tag
;
7908 auto const tag
= [&]() -> Optional
<T
> {
7910 if (t.subtypeOf(BS##tag)) return T::S##tag##Spec; \
7911 if (t.subtypeOf(B##tag)) return T::tag##Spec; \
7912 if (t.subtypeOf(BOptS##tag)) return T::OptS##tag##Spec; \
7913 if (t.subtypeOf(BOpt##tag)) return T::Opt##tag##Spec; \
7920 // The JIT doesn't (currently) take advantage of specializations
7921 // for any array types except the above, so there's no point in
7923 return std::nullopt
;
7925 if (!tag
) return std::nullopt
;
7927 // NB: Because of the type checks above for the tag, we know that
7928 // the empty bits must correspond to the specialization (which is
7929 // not true in general).
7930 auto const emptiness
= t
.couldBe(BArrLikeE
)
7931 ? RepoAuthType::Array::Empty::Maybe
7932 : RepoAuthType::Array::Empty::No
;
7934 auto const arr
= [&]() -> const RepoAuthType::Array
* {
7935 switch (t
.m_dataTag
) {
7938 case DataTag::LazyCls
:
7939 case DataTag::EnumClassLabel
:
7941 case DataTag::WaitHandle
:
7945 always_assert(false);
7946 case DataTag::ArrLikeVal
:
7947 case DataTag::ArrLikeMap
:
7948 case DataTag::ArrLikeMapN
:
7950 case DataTag::ArrLikePackedN
:
7951 return RepoAuthType::Array::packed(
7953 make_repo_type(t
.m_data
.packedn
->type
)
7955 case DataTag::ArrLikePacked
:
7957 std::vector
<RepoAuthType
> repoTypes
;
7959 begin(t
.m_data
.packed
->elems
), end(t
.m_data
.packed
->elems
),
7960 std::back_inserter(repoTypes
),
7961 [&] (const Type
& t2
) { return make_repo_type(t2
); }
7963 return RepoAuthType::Array::tuple(emptiness
, repoTypes
);
7967 always_assert(false);
7969 if (!arr
) return std::nullopt
;
7971 return RepoAuthType
{ *tag
, arr
};
7974 RepoAuthType
make_repo_type(const Type
& t
) {
7975 assertx(t
.subtypeOf(BCell
));
7976 assertx(!t
.subtypeOf(BBottom
));
7977 using T
= RepoAuthType::Tag
;
7979 if (is_specialized_obj(t
)) {
7980 if (t
.subtypeOf(BOptObj
)) {
7981 auto const& dobj
= dobj_of(t
);
7982 return RepoAuthType
{
7984 ? (t
.couldBe(BInitNull
) ? T::OptExactObj
: T::ExactObj
)
7985 : (t
.couldBe(BInitNull
) ? T::OptSubObj
: T::SubObj
),
7986 dobj
.smallestCls().name()
7989 if (t
.subtypeOf(BUninit
| BObj
)) {
7990 auto const& dobj
= dobj_of(t
);
7991 return RepoAuthType
{
7992 dobj
.isExact() ? T::UninitExactObj
: T::UninitSubObj
,
7993 dobj
.smallestCls().name()
7998 if (is_specialized_cls(t
) && t
.subtypeOf(BOptCls
)) {
7999 auto const& dcls
= dcls_of(t
);
8000 return RepoAuthType
{
8002 ? (t
.couldBe(BInitNull
) ? T::OptExactCls
: T::ExactCls
)
8003 : (t
.couldBe(BInitNull
) ? T::OptSubCls
: T::SubCls
),
8004 dcls
.smallestCls().name()
8008 if (is_specialized_array_like(t
) && t
.subtypeOf(BOptArrLike
)) {
8009 if (auto const rat
= make_repo_type_arr(t
)) return *rat
;
8012 #define X(tag) if (t.subtypeOf(B##tag)) return RepoAuthType{T::tag};
8015 if (t.subtypeOf(B##tag)) return RepoAuthType{T::tag}; \
8016 if (t.subtypeOf(BOpt##tag)) return RepoAuthType{T::Opt##tag}; \
8020 if (t.subtypeOf(BUninit | B##tag)) return RepoAuthType{T::Uninit##tag}; \
8026 #define Y(types, tag) \
8027 if (t.subtypeOf(types)) return RepoAuthType{T::tag}; \
8028 if (t.subtypeOf(BInitNull | types)) return RepoAuthType{T::Opt##tag}; \
8052 Y(BSStr
|BCls
|BLazyCls
, UncStrLike
)
8053 Y(BStr
|BCls
|BLazyCls
, StrLike
)
8054 Y(BUncArrKey
|BCls
|BLazyCls
, UncArrKeyCompat
)
8055 Y(BArrKey
|BCls
|BLazyCls
, ArrKeyCompat
)
8056 Y(BVec
|BClsMeth
, VecCompat
)
8057 Y(BArrLike
|BClsMeth
, ArrLikeCompat
)
8069 always_assert(false);
8072 //////////////////////////////////////////////////////////////////////
8074 // Testing only functions used to construct Types which are hard to
8075 // construct using the normal interfaces.
8077 Type
set_trep_for_testing(Type t
, trep bits
) {
8079 t
.m_legacyMark
= Type::topLegacyMarkForBits(bits
);
8080 assertx(t
.checkInvariants());
8084 trep
get_trep_for_testing(const Type
& t
) {
8088 Type
make_obj_for_testing(trep bits
, res::Class cls
,
8089 bool isSub
, bool isCtx
, bool canonicalize
) {
8092 if (auto const w
= cls
.withoutNonRegular()) {
8097 } else if (!cls
.mightBeRegular()) {
8101 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8102 auto const useSub
= [&] {
8103 if (!canonicalize
) return isSub
;
8104 if (!isSub
) return !cls
.isComplete();
8105 return cls
.couldBeOverriddenByRegular();
8109 useSub
? DCls::MakeSub(cls
, false) : DCls::MakeExact(cls
, false)
8111 t
.m_dataTag
= DataTag::Obj
;
8112 t
.m_data
.dobj
.setCtx(isCtx
);
8113 assertx(t
.checkInvariants());
8117 Type
make_cls_for_testing(trep bits
, res::Class cls
,
8118 bool isSub
, bool isCtx
,
8119 bool canonicalize
, bool nonReg
) {
8122 if (!nonReg
|| !cls
.mightContainNonRegular()) {
8123 if (auto const w
= cls
.withoutNonRegular()) {
8130 } else if (!nonReg
|| !cls
.mightBeNonRegular()) {
8131 if (!cls
.mightBeRegular()) return TBottom
;
8135 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8136 auto const useSub
= [&] {
8137 if (!canonicalize
) return isSub
;
8138 if (!isSub
) return !cls
.isComplete();
8139 return nonReg
? cls
.couldBeOverridden() : cls
.couldBeOverriddenByRegular();
8143 useSub
? DCls::MakeSub(cls
, nonReg
) : DCls::MakeExact(cls
, nonReg
)
8145 t
.m_dataTag
= DataTag::Cls
;
8146 t
.m_data
.dcls
.setCtx(isCtx
);
8147 assertx(t
.checkInvariants());
8151 Type
make_arrval_for_testing(trep bits
, SArray a
) {
8152 auto t
= Type
{ bits
, legacyMarkFromSArr(a
) };
8154 t
.m_dataTag
= DataTag::ArrLikeVal
;
8155 assertx(t
.checkInvariants());
8159 Type
make_arrpacked_for_testing(trep bits
,
8160 std::vector
<Type
> elems
,
8161 Optional
<LegacyMark
> mark
) {
8162 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8163 construct_inner(t
.m_data
.packed
, std::move(elems
));
8164 t
.m_dataTag
= DataTag::ArrLikePacked
;
8165 if (mark
) t
.m_legacyMark
= *mark
;
8166 assertx(t
.checkInvariants());
8170 Type
make_arrpackedn_for_testing(trep bits
, Type elem
) {
8171 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8172 construct_inner(t
.m_data
.packedn
, std::move(elem
));
8173 t
.m_dataTag
= DataTag::ArrLikePackedN
;
8174 assertx(t
.checkInvariants());
8178 Type
make_arrmap_for_testing(trep bits
,
8182 Optional
<LegacyMark
> mark
) {
8183 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8190 t
.m_dataTag
= DataTag::ArrLikeMap
;
8191 if (mark
) t
.m_legacyMark
= *mark
;
8192 assertx(t
.checkInvariants());
8196 Type
make_arrmapn_for_testing(trep bits
, Type key
, Type val
) {
8197 auto t
= Type
{ bits
, Type::topLegacyMarkForBits(bits
) };
8198 construct_inner(t
.m_data
.mapn
, std::move(key
), std::move(val
));
8199 t
.m_dataTag
= DataTag::ArrLikeMapN
;
8200 assertx(t
.checkInvariants());
8204 Type
set_mark_for_testing(Type t
, LegacyMark mark
) {
8205 t
.m_legacyMark
= mark
;
8206 assertx(t
.checkInvariants());
8210 Type
loosen_mark_for_testing(Type t
) {
8211 if (t
.m_dataTag
== DataTag::ArrLikeVal
) return t
;
8213 t
.m_legacyMark
= Type::topLegacyMarkForBits(t
.bits());
8215 switch (t
.m_dataTag
) {
8218 case DataTag::LazyCls
:
8219 case DataTag::EnumClassLabel
:
8226 case DataTag::WaitHandle
: {
8227 auto& inner
= t
.m_data
.dwh
.mutate()->inner
;
8228 inner
= loosen_mark_for_testing(std::move(inner
));
8232 case DataTag::ArrLikePacked
: {
8233 auto& packed
= *t
.m_data
.packed
.mutate();
8234 for (auto& e
: packed
.elems
) {
8235 e
= loosen_mark_for_testing(std::move(e
));
8240 case DataTag::ArrLikePackedN
: {
8241 auto& packed
= *t
.m_data
.packedn
.mutate();
8242 packed
.type
= loosen_mark_for_testing(std::move(packed
.type
));
8246 case DataTag::ArrLikeMap
: {
8247 auto& map
= *t
.m_data
.map
.mutate();
8248 for (auto it
= map
.map
.begin(); it
!= map
.map
.end(); it
++) {
8249 auto val
= loosen_mark_for_testing(it
->second
.val
);
8250 map
.map
.update(it
, it
->second
.withType(std::move(val
)));
8252 map
.optKey
= loosen_mark_for_testing(std::move(map
.optKey
));
8253 map
.optVal
= loosen_mark_for_testing(std::move(map
.optVal
));
8257 case DataTag::ArrLikeMapN
: {
8258 auto& map
= *t
.m_data
.mapn
.mutate();
8259 map
.key
= loosen_mark_for_testing(std::move(map
.key
));
8260 map
.val
= loosen_mark_for_testing(std::move(map
.val
));
8264 case DataTag::ArrLikeVal
:
8265 always_assert(false);
8268 assertx(t
.checkInvariants());