Home | History | Annotate | Download | only in verifier 
      1 /*
      2  * Copyright (C) 2012 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_RUNTIME_VERIFIER_REG_TYPE_H_
     18 #define ART_RUNTIME_VERIFIER_REG_TYPE_H_
     19 
     20 #include <stdint.h>
     21 #include <limits>
     22 #include <set>
     23 #include <string>
     24 #include <string_view>
     25 
     26 #include "base/arena_object.h"
     27 #include "base/bit_vector.h"
     28 #include "base/locks.h"
     29 #include "base/macros.h"
     30 #include "dex/primitive.h"
     31 #include "gc_root.h"
     32 #include "handle_scope.h"
     33 #include "obj_ptr.h"
     34 
     35 namespace art {
     36 namespace mirror {
     37 class Class;
     38 class ClassLoader;
     39 }  // namespace mirror
     40 
     41 class ArenaBitVector;
     42 class ScopedArenaAllocator;
     43 
     44 namespace verifier {
     45 
     46 class MethodVerifier;
     47 class RegTypeCache;
     48 
     49 /*
     50  * RegType holds information about the "type" of data held in a register.
     51  */
     52 class RegType {
     53  public:
     54   virtual bool IsUndefined() const { return false; }
     55   virtual bool IsConflict() const { return false; }
     56   virtual bool IsBoolean() const { return false; }
     57   virtual bool IsByte() const { return false; }
     58   virtual bool IsChar() const { return false; }
     59   virtual bool IsShort() const { return false; }
     60   virtual bool IsInteger() const { return false; }
     61   virtual bool IsLongLo() const { return false; }
     62   virtual bool IsLongHi() const { return false; }
     63   virtual bool IsFloat() const { return false; }
     64   virtual bool IsDouble() const { return false; }
     65   virtual bool IsDoubleLo() const { return false; }
     66   virtual bool IsDoubleHi() const { return false; }
     67   virtual bool IsUnresolvedReference() const { return false; }
     68   virtual bool IsUninitializedReference() const { return false; }
     69   virtual bool IsUninitializedThisReference() const { return false; }
     70   virtual bool IsUnresolvedAndUninitializedReference() const { return false; }
     71   virtual bool IsUnresolvedAndUninitializedThisReference() const {
     72     return false;
     73   }
     74   virtual bool IsUnresolvedMergedReference() const { return false; }
     75   virtual bool IsUnresolvedSuperClass() const { return false; }
     76   virtual bool IsReference() const { return false; }
     77   virtual bool IsPreciseReference() const { return false; }
     78   virtual bool IsPreciseConstant() const { return false; }
     79   virtual bool IsPreciseConstantLo() const { return false; }
     80   virtual bool IsPreciseConstantHi() const { return false; }
     81   virtual bool IsImpreciseConstantLo() const { return false; }
     82   virtual bool IsImpreciseConstantHi() const { return false; }
     83   virtual bool IsImpreciseConstant() const { return false; }
     84   virtual bool IsConstantTypes() const { return false; }
     85   bool IsConstant() const {
     86     return IsImpreciseConstant() || IsPreciseConstant();
     87   }
     88   bool IsConstantLo() const {
     89     return IsImpreciseConstantLo() || IsPreciseConstantLo();
     90   }
     91   bool IsPrecise() const {
     92     return IsPreciseConstantLo() || IsPreciseConstant() ||
     93            IsPreciseConstantHi();
     94   }
     95   bool IsLongConstant() const { return IsConstantLo(); }
     96   bool IsConstantHi() const {
     97     return (IsPreciseConstantHi() || IsImpreciseConstantHi());
     98   }
     99   bool IsLongConstantHigh() const { return IsConstantHi(); }
    100   virtual bool IsUninitializedTypes() const { return false; }
    101   virtual bool IsUnresolvedTypes() const { return false; }
    102 
    103   bool IsLowHalf() const {
    104     return (IsLongLo() || IsDoubleLo() || IsPreciseConstantLo() || IsImpreciseConstantLo());
    105   }
    106   bool IsHighHalf() const {
    107     return (IsLongHi() || IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    108   }
    109   bool IsLongOrDoubleTypes() const { return IsLowHalf(); }
    110   // Check this is the low half, and that type_h is its matching high-half.
    111   inline bool CheckWidePair(const RegType& type_h) const {
    112     if (IsLowHalf()) {
    113       return ((IsImpreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    114               (IsImpreciseConstantLo() && type_h.IsImpreciseConstantHi()) ||
    115               (IsPreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    116               (IsPreciseConstantLo() && type_h.IsImpreciseConstantHi()) ||
    117               (IsDoubleLo() && type_h.IsDoubleHi()) ||
    118               (IsLongLo() && type_h.IsLongHi()));
    119     }
    120     return false;
    121   }
    122   // The high half that corresponds to this low half
    123   const RegType& HighHalf(RegTypeCache* cache) const
    124       REQUIRES_SHARED(Locks::mutator_lock_);
    125 
    126   bool IsConstantBoolean() const;
    127   virtual bool IsConstantChar() const { return false; }
    128   virtual bool IsConstantByte() const { return false; }
    129   virtual bool IsConstantShort() const { return false; }
    130   virtual bool IsOne() const { return false; }
    131   virtual bool IsZero() const { return false; }
    132   virtual bool IsNull() const { return false; }
    133   bool IsReferenceTypes() const {
    134     return IsNonZeroReferenceTypes() || IsZero() || IsNull();
    135   }
    136   bool IsZeroOrNull() const {
    137     return IsZero() || IsNull();
    138   }
    139   virtual bool IsNonZeroReferenceTypes() const { return false; }
    140   bool IsCategory1Types() const {
    141     return IsChar() || IsInteger() || IsFloat() || IsConstant() || IsByte() ||
    142            IsShort() || IsBoolean();
    143   }
    144   bool IsCategory2Types() const {
    145     return IsLowHalf();  // Don't expect explicit testing of high halves
    146   }
    147   bool IsBooleanTypes() const { return IsBoolean() || IsConstantBoolean(); }
    148   bool IsByteTypes() const {
    149     return IsConstantByte() || IsByte() || IsBoolean();
    150   }
    151   bool IsShortTypes() const {
    152     return IsShort() || IsByte() || IsBoolean() || IsConstantShort();
    153   }
    154   bool IsCharTypes() const {
    155     return IsChar() || IsBooleanTypes() || IsConstantChar();
    156   }
    157   bool IsIntegralTypes() const {
    158     return IsInteger() || IsConstant() || IsByte() || IsShort() || IsChar() ||
    159            IsBoolean();
    160   }
    161   // Give the constant value encoded, but this shouldn't be called in the
    162   // general case.
    163   bool IsArrayIndexTypes() const { return IsIntegralTypes(); }
    164   // Float type may be derived from any constant type
    165   bool IsFloatTypes() const { return IsFloat() || IsConstant(); }
    166   bool IsLongTypes() const { return IsLongLo() || IsLongConstant(); }
    167   bool IsLongHighTypes() const {
    168     return (IsLongHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    169   }
    170   bool IsDoubleTypes() const { return IsDoubleLo() || IsLongConstant(); }
    171   bool IsDoubleHighTypes() const {
    172     return (IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    173   }
    174   virtual bool IsLong() const { return false; }
    175   bool HasClass() const {
    176     bool result = !klass_.IsNull();
    177     DCHECK_EQ(result, HasClassVirtual());
    178     return result;
    179   }
    180   virtual bool HasClassVirtual() const { return false; }
    181   bool IsJavaLangObject() const REQUIRES_SHARED(Locks::mutator_lock_);
    182   virtual bool IsArrayTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    183   virtual bool IsObjectArrayTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    184   Primitive::Type GetPrimitiveType() const;
    185   bool IsJavaLangObjectArray() const
    186       REQUIRES_SHARED(Locks::mutator_lock_);
    187   bool IsInstantiableTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    188   const std::string_view& GetDescriptor() const {
    189     DCHECK(HasClass() ||
    190            (IsUnresolvedTypes() && !IsUnresolvedMergedReference() &&
    191             !IsUnresolvedSuperClass()));
    192     return descriptor_;
    193   }
    194   ObjPtr<mirror::Class> GetClass() const REQUIRES_SHARED(Locks::mutator_lock_) {
    195     DCHECK(!IsUnresolvedReference());
    196     DCHECK(!klass_.IsNull()) << Dump();
    197     DCHECK(HasClass());
    198     return klass_.Read();
    199   }
    200   uint16_t GetId() const { return cache_id_; }
    201   const RegType& GetSuperClass(RegTypeCache* cache) const
    202       REQUIRES_SHARED(Locks::mutator_lock_);
    203 
    204   virtual std::string Dump() const
    205       REQUIRES_SHARED(Locks::mutator_lock_) = 0;
    206 
    207   // Can this type access other?
    208   bool CanAccess(const RegType& other) const
    209       REQUIRES_SHARED(Locks::mutator_lock_);
    210 
    211   // Can this type access a member with the given properties?
    212   bool CanAccessMember(ObjPtr<mirror::Class> klass, uint32_t access_flags) const
    213       REQUIRES_SHARED(Locks::mutator_lock_);
    214 
    215   // Can this type be assigned by src?
    216   // Note: Object and interface types may always be assigned to one another, see
    217   // comment on
    218   // ClassJoin.
    219   bool IsAssignableFrom(const RegType& src, MethodVerifier* verifier) const
    220       REQUIRES_SHARED(Locks::mutator_lock_);
    221 
    222   // Can this array type potentially be assigned by src.
    223   // This function is necessary as array types are valid even if their components types are not,
    224   // e.g., when they component type could not be resolved. The function will return true iff the
    225   // types are assignable. It will return false otherwise. In case of return=false, soft_error
    226   // will be set to true iff the assignment test failure should be treated as a soft-error, i.e.,
    227   // when both array types have the same 'depth' and the 'final' component types may be assignable
    228   // (both are reference types).
    229   bool CanAssignArray(const RegType& src,
    230                       RegTypeCache& reg_types,
    231                       Handle<mirror::ClassLoader> class_loader,
    232                       MethodVerifier* verifier,
    233                       bool* soft_error) const
    234       REQUIRES_SHARED(Locks::mutator_lock_);
    235 
    236   // Can this type be assigned by src? Variant of IsAssignableFrom that doesn't
    237   // allow assignment to
    238   // an interface from an Object.
    239   bool IsStrictlyAssignableFrom(const RegType& src, MethodVerifier* verifier) const
    240       REQUIRES_SHARED(Locks::mutator_lock_);
    241 
    242   // Are these RegTypes the same?
    243   bool Equals(const RegType& other) const { return GetId() == other.GetId(); }
    244 
    245   // Compute the merge of this register from one edge (path) with incoming_type
    246   // from another.
    247   const RegType& Merge(const RegType& incoming_type,
    248                        RegTypeCache* reg_types,
    249                        MethodVerifier* verifier) const
    250       REQUIRES_SHARED(Locks::mutator_lock_);
    251   // Same as above, but also handles the case where incoming_type == this.
    252   const RegType& SafeMerge(const RegType& incoming_type,
    253                            RegTypeCache* reg_types,
    254                            MethodVerifier* verifier) const
    255       REQUIRES_SHARED(Locks::mutator_lock_) {
    256     if (Equals(incoming_type)) {
    257       return *this;
    258     }
    259     return Merge(incoming_type, reg_types, verifier);
    260   }
    261 
    262   virtual ~RegType() {}
    263 
    264   void VisitRoots(RootVisitor* visitor, const RootInfo& root_info) const
    265       REQUIRES_SHARED(Locks::mutator_lock_);
    266 
    267   static void* operator new(size_t size) noexcept {
    268     return ::operator new(size);
    269   }
    270 
    271   static void* operator new(size_t size, ArenaAllocator* allocator) = delete;
    272   static void* operator new(size_t size, ScopedArenaAllocator* allocator);
    273 
    274   enum class AssignmentType {
    275     kBoolean,
    276     kByte,
    277     kShort,
    278     kChar,
    279     kInteger,
    280     kFloat,
    281     kLongLo,
    282     kDoubleLo,
    283     kConflict,
    284     kReference,
    285     kNotAssignable,
    286   };
    287 
    288   ALWAYS_INLINE
    289   inline AssignmentType GetAssignmentType() const {
    290     AssignmentType t = GetAssignmentTypeImpl();
    291     if (kIsDebugBuild) {
    292       if (IsBoolean()) {
    293         CHECK(AssignmentType::kBoolean == t);
    294       } else if (IsByte()) {
    295         CHECK(AssignmentType::kByte == t);
    296       } else if (IsShort()) {
    297         CHECK(AssignmentType::kShort == t);
    298       } else if (IsChar()) {
    299         CHECK(AssignmentType::kChar == t);
    300       } else if (IsInteger()) {
    301         CHECK(AssignmentType::kInteger == t);
    302       } else if (IsFloat()) {
    303         CHECK(AssignmentType::kFloat == t);
    304       } else if (IsLongLo()) {
    305         CHECK(AssignmentType::kLongLo == t);
    306       } else if (IsDoubleLo()) {
    307         CHECK(AssignmentType::kDoubleLo == t);
    308       } else if (IsConflict()) {
    309         CHECK(AssignmentType::kConflict == t);
    310       } else if (IsReferenceTypes()) {
    311         CHECK(AssignmentType::kReference == t);
    312       } else {
    313         LOG(FATAL) << "Unreachable";
    314         UNREACHABLE();
    315       }
    316     }
    317     return t;
    318   }
    319 
    320  protected:
    321   RegType(ObjPtr<mirror::Class> klass,
    322           const std::string_view& descriptor,
    323           uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    324       : descriptor_(descriptor),
    325         klass_(klass),
    326         cache_id_(cache_id) {}
    327 
    328   template <typename Class>
    329   void CheckConstructorInvariants(Class* this_ ATTRIBUTE_UNUSED) const
    330       REQUIRES_SHARED(Locks::mutator_lock_) {
    331     static_assert(std::is_final<Class>::value, "Class must be final.");
    332     if (kIsDebugBuild) {
    333       CheckInvariants();
    334     }
    335   }
    336 
    337   virtual AssignmentType GetAssignmentTypeImpl() const = 0;
    338 
    339   const std::string_view descriptor_;
    340   mutable GcRoot<mirror::Class> klass_;  // Non-const only due to moving classes.
    341   const uint16_t cache_id_;
    342 
    343   friend class RegTypeCache;
    344 
    345  private:
    346   virtual void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_);
    347 
    348   /*
    349    * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
    350    * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
    351    * S and T such that there isn't a parent of both S and T that isn't also the parent of J (ie J
    352    * is the deepest (lowest upper bound) parent of S and T).
    353    *
    354    * This operation applies for regular classes and arrays, however, for interface types there
    355    * needn't be a partial ordering on the types. We could solve the problem of a lack of a partial
    356    * order by introducing sets of types, however, the only operation permissible on an interface is
    357    * invoke-interface. In the tradition of Java verifiers [1] we defer the verification of interface
    358    * types until an invoke-interface call on the interface typed reference at runtime and allow
    359    * the perversion of Object being assignable to an interface type (note, however, that we don't
    360    * allow assignment of Object or Interface to any concrete class and are therefore type safe).
    361    *
    362    * Note: This may return null in case of internal errors, e.g., OOME when a new class would have
    363    *       to be created but there is no heap space. The exception will stay pending, and it is
    364    *       the job of the caller to handle it.
    365    *
    366    * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
    367    */
    368   static ObjPtr<mirror::Class> ClassJoin(ObjPtr<mirror::Class> s, ObjPtr<mirror::Class> t)
    369       REQUIRES_SHARED(Locks::mutator_lock_);
    370 
    371   static bool AssignableFrom(const RegType& lhs,
    372                              const RegType& rhs,
    373                              bool strict,
    374                              MethodVerifier* verifier)
    375       REQUIRES_SHARED(Locks::mutator_lock_);
    376 
    377   DISALLOW_COPY_AND_ASSIGN(RegType);
    378 };
    379 
    380 // Bottom type.
    381 class ConflictType final : public RegType {
    382  public:
    383   bool IsConflict() const override { return true; }
    384 
    385   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    386 
    387   // Get the singleton Conflict instance.
    388   static const ConflictType* GetInstance() PURE;
    389 
    390   // Create the singleton instance.
    391   static const ConflictType* CreateInstance(ObjPtr<mirror::Class> klass,
    392                                             const std::string_view& descriptor,
    393                                             uint16_t cache_id)
    394       REQUIRES_SHARED(Locks::mutator_lock_);
    395 
    396   // Destroy the singleton instance.
    397   static void Destroy();
    398 
    399   AssignmentType GetAssignmentTypeImpl() const override {
    400     return AssignmentType::kConflict;
    401   }
    402 
    403  private:
    404   ConflictType(ObjPtr<mirror::Class> klass,
    405                const std::string_view& descriptor,
    406                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    407       : RegType(klass, descriptor, cache_id) {
    408     CheckConstructorInvariants(this);
    409   }
    410 
    411   static const ConflictType* instance_;
    412 };
    413 
    414 // A variant of the bottom type used to specify an undefined value in the
    415 // incoming registers.
    416 // Merging with UndefinedType yields ConflictType which is the true bottom.
    417 class UndefinedType final : public RegType {
    418  public:
    419   bool IsUndefined() const override { return true; }
    420 
    421   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    422 
    423   // Get the singleton Undefined instance.
    424   static const UndefinedType* GetInstance() PURE;
    425 
    426   // Create the singleton instance.
    427   static const UndefinedType* CreateInstance(ObjPtr<mirror::Class> klass,
    428                                              const std::string_view& descriptor,
    429                                              uint16_t cache_id)
    430       REQUIRES_SHARED(Locks::mutator_lock_);
    431 
    432   // Destroy the singleton instance.
    433   static void Destroy();
    434 
    435   AssignmentType GetAssignmentTypeImpl() const override {
    436     return AssignmentType::kNotAssignable;
    437   }
    438 
    439  private:
    440   UndefinedType(ObjPtr<mirror::Class> klass,
    441                 const std::string_view& descriptor,
    442                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    443       : RegType(klass, descriptor, cache_id) {
    444     CheckConstructorInvariants(this);
    445   }
    446 
    447   static const UndefinedType* instance_;
    448 };
    449 
    450 class PrimitiveType : public RegType {
    451  public:
    452   PrimitiveType(ObjPtr<mirror::Class> klass,
    453                 const std::string_view& descriptor,
    454                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    455 
    456   bool HasClassVirtual() const override { return true; }
    457 };
    458 
    459 class Cat1Type : public PrimitiveType {
    460  public:
    461   Cat1Type(ObjPtr<mirror::Class> klass,
    462            const std::string_view& descriptor,
    463            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    464 };
    465 
    466 class IntegerType final : public Cat1Type {
    467  public:
    468   bool IsInteger() const override { return true; }
    469   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    470   static const IntegerType* CreateInstance(ObjPtr<mirror::Class> klass,
    471                                            const std::string_view& descriptor,
    472                                            uint16_t cache_id)
    473       REQUIRES_SHARED(Locks::mutator_lock_);
    474   static const IntegerType* GetInstance() PURE;
    475   static void Destroy();
    476 
    477   AssignmentType GetAssignmentTypeImpl() const override {
    478     return AssignmentType::kInteger;
    479   }
    480 
    481  private:
    482   IntegerType(ObjPtr<mirror::Class> klass,
    483               const std::string_view& descriptor,
    484               uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    485       : Cat1Type(klass, descriptor, cache_id) {
    486     CheckConstructorInvariants(this);
    487   }
    488   static const IntegerType* instance_;
    489 };
    490 
    491 class BooleanType final : public Cat1Type {
    492  public:
    493   bool IsBoolean() const override { return true; }
    494   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    495   static const BooleanType* CreateInstance(ObjPtr<mirror::Class> klass,
    496                                            const std::string_view& descriptor,
    497                                            uint16_t cache_id)
    498       REQUIRES_SHARED(Locks::mutator_lock_);
    499   static const BooleanType* GetInstance() PURE;
    500   static void Destroy();
    501 
    502   AssignmentType GetAssignmentTypeImpl() const override {
    503     return AssignmentType::kBoolean;
    504   }
    505 
    506  private:
    507   BooleanType(ObjPtr<mirror::Class> klass,
    508               const std::string_view& descriptor,
    509               uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    510       : Cat1Type(klass, descriptor, cache_id) {
    511     CheckConstructorInvariants(this);
    512   }
    513 
    514   static const BooleanType* instance_;
    515 };
    516 
    517 class ByteType final : public Cat1Type {
    518  public:
    519   bool IsByte() const override { return true; }
    520   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    521   static const ByteType* CreateInstance(ObjPtr<mirror::Class> klass,
    522                                         const std::string_view& descriptor,
    523                                         uint16_t cache_id)
    524       REQUIRES_SHARED(Locks::mutator_lock_);
    525   static const ByteType* GetInstance() PURE;
    526   static void Destroy();
    527 
    528   AssignmentType GetAssignmentTypeImpl() const override {
    529     return AssignmentType::kByte;
    530   }
    531 
    532  private:
    533   ByteType(ObjPtr<mirror::Class> klass,
    534            const std::string_view& descriptor,
    535            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    536       : Cat1Type(klass, descriptor, cache_id) {
    537     CheckConstructorInvariants(this);
    538   }
    539   static const ByteType* instance_;
    540 };
    541 
    542 class ShortType final : public Cat1Type {
    543  public:
    544   bool IsShort() const override { return true; }
    545   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    546   static const ShortType* CreateInstance(ObjPtr<mirror::Class> klass,
    547                                          const std::string_view& descriptor,
    548                                          uint16_t cache_id)
    549       REQUIRES_SHARED(Locks::mutator_lock_);
    550   static const ShortType* GetInstance() PURE;
    551   static void Destroy();
    552 
    553   AssignmentType GetAssignmentTypeImpl() const override {
    554     return AssignmentType::kShort;
    555   }
    556 
    557  private:
    558   ShortType(ObjPtr<mirror::Class> klass, const std::string_view& descriptor,
    559             uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    560       : Cat1Type(klass, descriptor, cache_id) {
    561     CheckConstructorInvariants(this);
    562   }
    563   static const ShortType* instance_;
    564 };
    565 
    566 class CharType final : public Cat1Type {
    567  public:
    568   bool IsChar() const override { return true; }
    569   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    570   static const CharType* CreateInstance(ObjPtr<mirror::Class> klass,
    571                                         const std::string_view& descriptor,
    572                                         uint16_t cache_id)
    573       REQUIRES_SHARED(Locks::mutator_lock_);
    574   static const CharType* GetInstance() PURE;
    575   static void Destroy();
    576 
    577   AssignmentType GetAssignmentTypeImpl() const override {
    578     return AssignmentType::kChar;
    579   }
    580 
    581  private:
    582   CharType(ObjPtr<mirror::Class> klass,
    583            const std::string_view& descriptor,
    584            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    585       : Cat1Type(klass, descriptor, cache_id) {
    586     CheckConstructorInvariants(this);
    587   }
    588   static const CharType* instance_;
    589 };
    590 
    591 class FloatType final : public Cat1Type {
    592  public:
    593   bool IsFloat() const override { return true; }
    594   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    595   static const FloatType* CreateInstance(ObjPtr<mirror::Class> klass,
    596                                          const std::string_view& descriptor,
    597                                          uint16_t cache_id)
    598       REQUIRES_SHARED(Locks::mutator_lock_);
    599   static const FloatType* GetInstance() PURE;
    600   static void Destroy();
    601 
    602   AssignmentType GetAssignmentTypeImpl() const override {
    603     return AssignmentType::kFloat;
    604   }
    605 
    606  private:
    607   FloatType(ObjPtr<mirror::Class> klass,
    608             const std::string_view& descriptor,
    609             uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    610       : Cat1Type(klass, descriptor, cache_id) {
    611     CheckConstructorInvariants(this);
    612   }
    613   static const FloatType* instance_;
    614 };
    615 
    616 class Cat2Type : public PrimitiveType {
    617  public:
    618   Cat2Type(ObjPtr<mirror::Class> klass,
    619            const std::string_view& descriptor,
    620            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    621 };
    622 
    623 class LongLoType final : public Cat2Type {
    624  public:
    625   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    626   bool IsLongLo() const override { return true; }
    627   bool IsLong() const override { return true; }
    628   static const LongLoType* CreateInstance(ObjPtr<mirror::Class> klass,
    629                                           const std::string_view& descriptor,
    630                                           uint16_t cache_id)
    631       REQUIRES_SHARED(Locks::mutator_lock_);
    632   static const LongLoType* GetInstance() PURE;
    633   static void Destroy();
    634 
    635   AssignmentType GetAssignmentTypeImpl() const override {
    636     return AssignmentType::kLongLo;
    637   }
    638 
    639  private:
    640   LongLoType(ObjPtr<mirror::Class> klass,
    641              const std::string_view& descriptor,
    642              uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    643       : Cat2Type(klass, descriptor, cache_id) {
    644     CheckConstructorInvariants(this);
    645   }
    646   static const LongLoType* instance_;
    647 };
    648 
    649 class LongHiType final : public Cat2Type {
    650  public:
    651   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    652   bool IsLongHi() const override { return true; }
    653   static const LongHiType* CreateInstance(ObjPtr<mirror::Class> klass,
    654                                           const std::string_view& descriptor,
    655                                           uint16_t cache_id)
    656       REQUIRES_SHARED(Locks::mutator_lock_);
    657   static const LongHiType* GetInstance() PURE;
    658   static void Destroy();
    659 
    660   AssignmentType GetAssignmentTypeImpl() const override {
    661     return AssignmentType::kNotAssignable;
    662   }
    663 
    664  private:
    665   LongHiType(ObjPtr<mirror::Class> klass,
    666              const std::string_view& descriptor,
    667              uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    668       : Cat2Type(klass, descriptor, cache_id) {
    669     CheckConstructorInvariants(this);
    670   }
    671   static const LongHiType* instance_;
    672 };
    673 
    674 class DoubleLoType final : public Cat2Type {
    675  public:
    676   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    677   bool IsDoubleLo() const override { return true; }
    678   bool IsDouble() const override { return true; }
    679   static const DoubleLoType* CreateInstance(ObjPtr<mirror::Class> klass,
    680                                             const std::string_view& descriptor,
    681                                             uint16_t cache_id)
    682       REQUIRES_SHARED(Locks::mutator_lock_);
    683   static const DoubleLoType* GetInstance() PURE;
    684   static void Destroy();
    685 
    686   AssignmentType GetAssignmentTypeImpl() const override {
    687     return AssignmentType::kDoubleLo;
    688   }
    689 
    690  private:
    691   DoubleLoType(ObjPtr<mirror::Class> klass,
    692                const std::string_view& descriptor,
    693                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    694       : Cat2Type(klass, descriptor, cache_id) {
    695     CheckConstructorInvariants(this);
    696   }
    697   static const DoubleLoType* instance_;
    698 };
    699 
    700 class DoubleHiType final : public Cat2Type {
    701  public:
    702   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    703   bool IsDoubleHi() const override { return true; }
    704   static const DoubleHiType* CreateInstance(ObjPtr<mirror::Class> klass,
    705                                             const std::string_view& descriptor,
    706                                             uint16_t cache_id)
    707       REQUIRES_SHARED(Locks::mutator_lock_);
    708   static const DoubleHiType* GetInstance() PURE;
    709   static void Destroy();
    710 
    711   AssignmentType GetAssignmentTypeImpl() const override {
    712     return AssignmentType::kNotAssignable;
    713   }
    714 
    715  private:
    716   DoubleHiType(ObjPtr<mirror::Class> klass,
    717                const std::string_view& descriptor,
    718                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    719       : Cat2Type(klass, descriptor, cache_id) {
    720     CheckConstructorInvariants(this);
    721   }
    722   static const DoubleHiType* instance_;
    723 };
    724 
    725 class ConstantType : public RegType {
    726  public:
    727   ConstantType(uint32_t constant, uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    728       : RegType(nullptr, "", cache_id), constant_(constant) {
    729   }
    730 
    731 
    732   // If this is a 32-bit constant, what is the value? This value may be
    733   // imprecise in which case
    734   // the value represents part of the integer range of values that may be held
    735   // in the register.
    736   int32_t ConstantValue() const {
    737     DCHECK(IsConstantTypes());
    738     return constant_;
    739   }
    740 
    741   int32_t ConstantValueLo() const {
    742     DCHECK(IsConstantLo());
    743     return constant_;
    744   }
    745 
    746   int32_t ConstantValueHi() const {
    747     if (IsConstantHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()) {
    748       return constant_;
    749     } else {
    750       DCHECK(false);
    751       return 0;
    752     }
    753   }
    754 
    755   bool IsZero() const override {
    756     return IsPreciseConstant() && ConstantValue() == 0;
    757   }
    758   bool IsOne() const override {
    759     return IsPreciseConstant() && ConstantValue() == 1;
    760   }
    761 
    762   bool IsConstantChar() const override {
    763     return IsConstant() && ConstantValue() >= 0 &&
    764            ConstantValue() <= std::numeric_limits<uint16_t>::max();
    765   }
    766   bool IsConstantByte() const override {
    767     return IsConstant() &&
    768            ConstantValue() >= std::numeric_limits<int8_t>::min() &&
    769            ConstantValue() <= std::numeric_limits<int8_t>::max();
    770   }
    771   bool IsConstantShort() const override {
    772     return IsConstant() &&
    773            ConstantValue() >= std::numeric_limits<int16_t>::min() &&
    774            ConstantValue() <= std::numeric_limits<int16_t>::max();
    775   }
    776   bool IsConstantTypes() const override { return true; }
    777 
    778   AssignmentType GetAssignmentTypeImpl() const override {
    779     return AssignmentType::kNotAssignable;
    780   }
    781 
    782  private:
    783   const uint32_t constant_;
    784 };
    785 
    786 class PreciseConstType final : public ConstantType {
    787  public:
    788   PreciseConstType(uint32_t constant, uint16_t cache_id)
    789       REQUIRES_SHARED(Locks::mutator_lock_)
    790       : ConstantType(constant, cache_id) {
    791     CheckConstructorInvariants(this);
    792   }
    793 
    794   bool IsPreciseConstant() const override { return true; }
    795 
    796   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    797 
    798   AssignmentType GetAssignmentTypeImpl() const override {
    799     return AssignmentType::kNotAssignable;
    800   }
    801 };
    802 
    803 class PreciseConstLoType final : public ConstantType {
    804  public:
    805   PreciseConstLoType(uint32_t constant, uint16_t cache_id)
    806       REQUIRES_SHARED(Locks::mutator_lock_)
    807       : ConstantType(constant, cache_id) {
    808     CheckConstructorInvariants(this);
    809   }
    810   bool IsPreciseConstantLo() const override { return true; }
    811   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    812 
    813   AssignmentType GetAssignmentTypeImpl() const override {
    814     return AssignmentType::kNotAssignable;
    815   }
    816 };
    817 
    818 class PreciseConstHiType final : public ConstantType {
    819  public:
    820   PreciseConstHiType(uint32_t constant, uint16_t cache_id)
    821       REQUIRES_SHARED(Locks::mutator_lock_)
    822       : ConstantType(constant, cache_id) {
    823     CheckConstructorInvariants(this);
    824   }
    825   bool IsPreciseConstantHi() const override { return true; }
    826   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    827 
    828   AssignmentType GetAssignmentTypeImpl() const override {
    829     return AssignmentType::kNotAssignable;
    830   }
    831 };
    832 
    833 class ImpreciseConstType final : public ConstantType {
    834  public:
    835   ImpreciseConstType(uint32_t constat, uint16_t cache_id)
    836        REQUIRES_SHARED(Locks::mutator_lock_)
    837        : ConstantType(constat, cache_id) {
    838     CheckConstructorInvariants(this);
    839   }
    840   bool IsImpreciseConstant() const override { return true; }
    841   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    842 
    843   AssignmentType GetAssignmentTypeImpl() const override {
    844     return AssignmentType::kNotAssignable;
    845   }
    846 };
    847 
    848 class ImpreciseConstLoType final : public ConstantType {
    849  public:
    850   ImpreciseConstLoType(uint32_t constant, uint16_t cache_id)
    851       REQUIRES_SHARED(Locks::mutator_lock_)
    852       : ConstantType(constant, cache_id) {
    853     CheckConstructorInvariants(this);
    854   }
    855   bool IsImpreciseConstantLo() const override { return true; }
    856   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    857 
    858   AssignmentType GetAssignmentTypeImpl() const override {
    859     return AssignmentType::kNotAssignable;
    860   }
    861 };
    862 
    863 class ImpreciseConstHiType final : public ConstantType {
    864  public:
    865   ImpreciseConstHiType(uint32_t constant, uint16_t cache_id)
    866       REQUIRES_SHARED(Locks::mutator_lock_)
    867       : ConstantType(constant, cache_id) {
    868     CheckConstructorInvariants(this);
    869   }
    870   bool IsImpreciseConstantHi() const override { return true; }
    871   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    872 
    873   AssignmentType GetAssignmentTypeImpl() const override {
    874     return AssignmentType::kNotAssignable;
    875   }
    876 };
    877 
    878 // Special "null" type that captures the semantics of null / bottom.
    879 class NullType final : public RegType {
    880  public:
    881   bool IsNull() const override {
    882     return true;
    883   }
    884 
    885   // Get the singleton Null instance.
    886   static const NullType* GetInstance() PURE;
    887 
    888   // Create the singleton instance.
    889   static const NullType* CreateInstance(ObjPtr<mirror::Class> klass,
    890                                         const std::string_view& descriptor,
    891                                         uint16_t cache_id)
    892       REQUIRES_SHARED(Locks::mutator_lock_);
    893 
    894   static void Destroy();
    895 
    896   std::string Dump() const override {
    897     return "null";
    898   }
    899 
    900   AssignmentType GetAssignmentTypeImpl() const override {
    901     return AssignmentType::kReference;
    902   }
    903 
    904   bool IsConstantTypes() const override {
    905     return true;
    906   }
    907 
    908  private:
    909   NullType(ObjPtr<mirror::Class> klass, const std::string_view& descriptor, uint16_t cache_id)
    910       REQUIRES_SHARED(Locks::mutator_lock_)
    911       : RegType(klass, descriptor, cache_id) {
    912     CheckConstructorInvariants(this);
    913   }
    914 
    915   static const NullType* instance_;
    916 };
    917 
    918 // Common parent of all uninitialized types. Uninitialized types are created by
    919 // "new" dex
    920 // instructions and must be passed to a constructor.
    921 class UninitializedType : public RegType {
    922  public:
    923   UninitializedType(ObjPtr<mirror::Class> klass,
    924                     const std::string_view& descriptor,
    925                     uint32_t allocation_pc,
    926                     uint16_t cache_id)
    927       : RegType(klass, descriptor, cache_id), allocation_pc_(allocation_pc) {}
    928 
    929   bool IsUninitializedTypes() const override;
    930   bool IsNonZeroReferenceTypes() const override;
    931 
    932   uint32_t GetAllocationPc() const {
    933     DCHECK(IsUninitializedTypes());
    934     return allocation_pc_;
    935   }
    936 
    937   AssignmentType GetAssignmentTypeImpl() const override {
    938     return AssignmentType::kReference;
    939   }
    940 
    941  private:
    942   const uint32_t allocation_pc_;
    943 };
    944 
    945 // Similar to ReferenceType but not yet having been passed to a constructor.
    946 class UninitializedReferenceType final : public UninitializedType {
    947  public:
    948   UninitializedReferenceType(ObjPtr<mirror::Class> klass,
    949                              const std::string_view& descriptor,
    950                              uint32_t allocation_pc,
    951                              uint16_t cache_id)
    952       REQUIRES_SHARED(Locks::mutator_lock_)
    953       : UninitializedType(klass, descriptor, allocation_pc, cache_id) {
    954     CheckConstructorInvariants(this);
    955   }
    956 
    957   bool IsUninitializedReference() const override { return true; }
    958 
    959   bool HasClassVirtual() const override { return true; }
    960 
    961   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    962 };
    963 
    964 // Similar to UnresolvedReferenceType but not yet having been passed to a
    965 // constructor.
    966 class UnresolvedUninitializedRefType final : public UninitializedType {
    967  public:
    968   UnresolvedUninitializedRefType(const std::string_view& descriptor,
    969                                  uint32_t allocation_pc,
    970                                  uint16_t cache_id)
    971       REQUIRES_SHARED(Locks::mutator_lock_)
    972       : UninitializedType(nullptr, descriptor, allocation_pc, cache_id) {
    973     CheckConstructorInvariants(this);
    974   }
    975 
    976   bool IsUnresolvedAndUninitializedReference() const override { return true; }
    977 
    978   bool IsUnresolvedTypes() const override { return true; }
    979 
    980   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
    981 
    982  private:
    983   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
    984 };
    985 
    986 // Similar to UninitializedReferenceType but special case for the this argument
    987 // of a constructor.
    988 class UninitializedThisReferenceType final : public UninitializedType {
    989  public:
    990   UninitializedThisReferenceType(ObjPtr<mirror::Class> klass,
    991                                  const std::string_view& descriptor,
    992                                  uint16_t cache_id)
    993       REQUIRES_SHARED(Locks::mutator_lock_)
    994       : UninitializedType(klass, descriptor, 0, cache_id) {
    995     CheckConstructorInvariants(this);
    996   }
    997 
    998   bool IsUninitializedThisReference() const override { return true; }
    999 
   1000   bool HasClassVirtual() const override { return true; }
   1001 
   1002   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1003 
   1004  private:
   1005   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
   1006 };
   1007 
   1008 class UnresolvedUninitializedThisRefType final : public UninitializedType {
   1009  public:
   1010   UnresolvedUninitializedThisRefType(const std::string_view& descriptor, uint16_t cache_id)
   1011       REQUIRES_SHARED(Locks::mutator_lock_)
   1012       : UninitializedType(nullptr, descriptor, 0, cache_id) {
   1013     CheckConstructorInvariants(this);
   1014   }
   1015 
   1016   bool IsUnresolvedAndUninitializedThisReference() const override { return true; }
   1017 
   1018   bool IsUnresolvedTypes() const override { return true; }
   1019 
   1020   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1021 
   1022  private:
   1023   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
   1024 };
   1025 
   1026 // A type of register holding a reference to an Object of type GetClass or a
   1027 // sub-class.
   1028 class ReferenceType final : public RegType {
   1029  public:
   1030   ReferenceType(ObjPtr<mirror::Class> klass,
   1031                 const std::string_view& descriptor,
   1032                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
   1033       : RegType(klass, descriptor, cache_id) {
   1034     CheckConstructorInvariants(this);
   1035   }
   1036 
   1037   bool IsReference() const override { return true; }
   1038 
   1039   bool IsNonZeroReferenceTypes() const override { return true; }
   1040 
   1041   bool HasClassVirtual() const override { return true; }
   1042 
   1043   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1044 
   1045   AssignmentType GetAssignmentTypeImpl() const override {
   1046     return AssignmentType::kReference;
   1047   }
   1048 };
   1049 
   1050 // A type of register holding a reference to an Object of type GetClass and only
   1051 // an object of that
   1052 // type.
   1053 class PreciseReferenceType final : public RegType {
   1054  public:
   1055   PreciseReferenceType(ObjPtr<mirror::Class> klass,
   1056                        const std::string_view& descriptor,
   1057                        uint16_t cache_id)
   1058       REQUIRES_SHARED(Locks::mutator_lock_);
   1059 
   1060   bool IsPreciseReference() const override { return true; }
   1061 
   1062   bool IsNonZeroReferenceTypes() const override { return true; }
   1063 
   1064   bool HasClassVirtual() const override { return true; }
   1065 
   1066   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1067 
   1068   AssignmentType GetAssignmentTypeImpl() const override {
   1069     return AssignmentType::kReference;
   1070   }
   1071 };
   1072 
   1073 // Common parent of unresolved types.
   1074 class UnresolvedType : public RegType {
   1075  public:
   1076   UnresolvedType(const std::string_view& descriptor, uint16_t cache_id)
   1077       REQUIRES_SHARED(Locks::mutator_lock_)
   1078       : RegType(nullptr, descriptor, cache_id) {}
   1079 
   1080   bool IsNonZeroReferenceTypes() const override;
   1081 
   1082   AssignmentType GetAssignmentTypeImpl() const override {
   1083     return AssignmentType::kReference;
   1084   }
   1085 };
   1086 
   1087 // Similar to ReferenceType except the Class couldn't be loaded. Assignability
   1088 // and other tests made
   1089 // of this type must be conservative.
   1090 class UnresolvedReferenceType final : public UnresolvedType {
   1091  public:
   1092   UnresolvedReferenceType(const std::string_view& descriptor, uint16_t cache_id)
   1093       REQUIRES_SHARED(Locks::mutator_lock_)
   1094       : UnresolvedType(descriptor, cache_id) {
   1095     CheckConstructorInvariants(this);
   1096   }
   1097 
   1098   bool IsUnresolvedReference() const override { return true; }
   1099 
   1100   bool IsUnresolvedTypes() const override { return true; }
   1101 
   1102   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1103 
   1104  private:
   1105   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
   1106 };
   1107 
   1108 // Type representing the super-class of an unresolved type.
   1109 class UnresolvedSuperClass final : public UnresolvedType {
   1110  public:
   1111   UnresolvedSuperClass(uint16_t child_id, RegTypeCache* reg_type_cache,
   1112                        uint16_t cache_id)
   1113       REQUIRES_SHARED(Locks::mutator_lock_)
   1114       : UnresolvedType("", cache_id),
   1115         unresolved_child_id_(child_id),
   1116         reg_type_cache_(reg_type_cache) {
   1117     CheckConstructorInvariants(this);
   1118   }
   1119 
   1120   bool IsUnresolvedSuperClass() const override { return true; }
   1121 
   1122   bool IsUnresolvedTypes() const override { return true; }
   1123 
   1124   uint16_t GetUnresolvedSuperClassChildId() const {
   1125     DCHECK(IsUnresolvedSuperClass());
   1126     return static_cast<uint16_t>(unresolved_child_id_ & 0xFFFF);
   1127   }
   1128 
   1129   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1130 
   1131  private:
   1132   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
   1133 
   1134   const uint16_t unresolved_child_id_;
   1135   const RegTypeCache* const reg_type_cache_;
   1136 };
   1137 
   1138 // A merge of unresolved (and resolved) types. If the types were resolved this may be
   1139 // Conflict or another known ReferenceType.
   1140 class UnresolvedMergedType final : public UnresolvedType {
   1141  public:
   1142   // Note: the constructor will copy the unresolved BitVector, not use it directly.
   1143   UnresolvedMergedType(const RegType& resolved,
   1144                        const BitVector& unresolved,
   1145                        const RegTypeCache* reg_type_cache,
   1146                        uint16_t cache_id)
   1147       REQUIRES_SHARED(Locks::mutator_lock_);
   1148 
   1149   // The resolved part. See description below.
   1150   const RegType& GetResolvedPart() const {
   1151     return resolved_part_;
   1152   }
   1153   // The unresolved part.
   1154   const BitVector& GetUnresolvedTypes() const {
   1155     return unresolved_types_;
   1156   }
   1157 
   1158   bool IsUnresolvedMergedReference() const override { return true; }
   1159 
   1160   bool IsUnresolvedTypes() const override { return true; }
   1161 
   1162   bool IsArrayTypes() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1163   bool IsObjectArrayTypes() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1164 
   1165   std::string Dump() const override REQUIRES_SHARED(Locks::mutator_lock_);
   1166 
   1167  private:
   1168   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) override;
   1169 
   1170   const RegTypeCache* const reg_type_cache_;
   1171 
   1172   // The original implementation of merged types was a binary tree. Collection of the flattened
   1173   // types ("leaves") can be expensive, so we store the expanded list now, as two components:
   1174   // 1) A resolved component. We use Zero when there is no resolved component, as that will be
   1175   //    an identity merge.
   1176   // 2) A bitvector of the unresolved reference types. A bitvector was chosen with the assumption
   1177   //    that there should not be too many types in flight in practice. (We also bias the index
   1178   //    against the index of Zero, which is one of the later default entries in any cache.)
   1179   const RegType& resolved_part_;
   1180   const BitVector unresolved_types_;
   1181 };
   1182 
   1183 std::ostream& operator<<(std::ostream& os, const RegType& rhs)
   1184     REQUIRES_SHARED(Locks::mutator_lock_);
   1185 
   1186 }  // namespace verifier
   1187 }  // namespace art
   1188 
   1189 #endif  // ART_RUNTIME_VERIFIER_REG_TYPE_H_
   1190