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 <limits>
     21 #include <stdint.h>
     22 #include <set>
     23 #include <string>
     24 
     25 #include "jni.h"
     26 
     27 #include "base/macros.h"
     28 #include "gc_root.h"
     29 #include "globals.h"
     30 #include "object_callbacks.h"
     31 #include "primitive.h"
     32 
     33 namespace art {
     34 namespace mirror {
     35 class Class;
     36 }  // namespace mirror
     37 namespace verifier {
     38 
     39 class RegTypeCache;
     40 /*
     41  * RegType holds information about the "type" of data held in a register.
     42  */
     43 class RegType {
     44  public:
     45   virtual bool IsUndefined() const { return false; }
     46   virtual bool IsConflict() const { return false; }
     47   virtual bool IsBoolean() const { return false; }
     48   virtual bool IsByte() const { return false; }
     49   virtual bool IsChar() const { return false; }
     50   virtual bool IsShort() const { return false; }
     51   virtual bool IsInteger() const { return false; }
     52   virtual bool IsLongLo() const { return false; }
     53   virtual bool IsLongHi() const { return false; }
     54   virtual bool IsFloat() const { return false; }
     55   virtual bool IsDouble() const { return false; }
     56   virtual bool IsDoubleLo() const { return false; }
     57   virtual bool IsDoubleHi() const { return false; }
     58   virtual bool IsUnresolvedReference() const { return false; }
     59   virtual bool IsUninitializedReference() const { return false; }
     60   virtual bool IsUninitializedThisReference() const { return false; }
     61   virtual bool IsUnresolvedAndUninitializedReference() const { return false; }
     62   virtual bool IsUnresolvedAndUninitializedThisReference() const { return false; }
     63   virtual bool IsUnresolvedMergedReference() const { return false; }
     64   virtual bool IsUnresolvedSuperClass() const { return false; }
     65   virtual bool IsReference() const { return false; }
     66   virtual bool IsPreciseReference() const { return false; }
     67   virtual bool IsPreciseConstant() const { return false; }
     68   virtual bool IsPreciseConstantLo() const { return false; }
     69   virtual bool IsPreciseConstantHi() const { return false; }
     70   virtual bool IsImpreciseConstantLo() const { return false; }
     71   virtual bool IsImpreciseConstantHi() const { return false; }
     72   virtual bool IsImpreciseConstant() const { return false; }
     73   virtual bool IsConstantTypes() const { return false; }
     74   bool IsConstant() const {
     75     return IsPreciseConstant() || IsImpreciseConstant();
     76   }
     77   bool IsConstantLo() const {
     78     return IsPreciseConstantLo() || IsImpreciseConstantLo();
     79   }
     80   bool IsPrecise() const {
     81     return IsPreciseConstantLo() || IsPreciseConstant() || IsPreciseConstantHi();
     82   }
     83   bool IsLongConstant() const {
     84     return IsConstantLo();
     85   }
     86   bool IsConstantHi() const {
     87     return (IsPreciseConstantHi() || IsImpreciseConstantHi());
     88   }
     89   bool IsLongConstantHigh() const {
     90     return IsConstantHi();
     91   }
     92   virtual bool IsUninitializedTypes() const { return false; }
     93   bool IsUnresolvedTypes() const {
     94     return IsUnresolvedReference() || IsUnresolvedAndUninitializedReference() ||
     95            IsUnresolvedAndUninitializedThisReference() ||
     96            IsUnresolvedMergedReference() || IsUnresolvedSuperClass();
     97   }
     98 
     99   bool IsLowHalf() const {
    100     return (IsLongLo() || IsDoubleLo() || IsPreciseConstantLo() ||
    101             IsImpreciseConstantLo());
    102   }
    103   bool IsHighHalf() const {
    104     return (IsLongHi() || IsDoubleHi() || IsPreciseConstantHi() ||
    105             IsImpreciseConstantHi());
    106   }
    107   bool IsLongOrDoubleTypes() const {
    108     return IsLowHalf();
    109   }
    110   // Check this is the low half, and that type_h is its matching high-half.
    111   inline bool CheckWidePair(RegType& type_h) const {
    112     if (IsLowHalf()) {
    113       return ((IsPreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    114               (IsPreciseConstantLo() && type_h.IsImpreciseConstantHi()) ||
    115               (IsImpreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    116               (IsImpreciseConstantLo() && 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   RegType& HighHalf(RegTypeCache* cache) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    124 
    125   bool IsConstantBoolean() const {
    126     return IsConstant() && (ConstantValue() >= 0) && (ConstantValue() <= 1);
    127   }
    128   virtual bool IsConstantChar() const {
    129     return false;
    130   }
    131   virtual bool IsConstantByte() const {
    132     return false;
    133   }
    134   virtual bool IsConstantShort() const {
    135     return false;
    136   }
    137   virtual bool IsOne() const {
    138     return false;
    139   }
    140   virtual bool IsZero() const {
    141     return false;
    142   }
    143   bool IsReferenceTypes() const {
    144     return IsNonZeroReferenceTypes() || IsZero();
    145   }
    146   virtual bool IsNonZeroReferenceTypes() const {
    147     return false;
    148   }
    149   bool IsCategory1Types() const {
    150     return IsChar() || IsInteger() || IsFloat() || IsConstant() || IsByte() || IsShort() ||
    151         IsBoolean();
    152   }
    153   bool IsCategory2Types() const {
    154     return IsLowHalf();  // Don't expect explicit testing of high halves
    155   }
    156   bool IsBooleanTypes() const {
    157     return IsBoolean() || IsConstantBoolean();
    158   }
    159   bool IsByteTypes() const {
    160     return IsConstantByte() || IsByte() || IsBoolean();
    161   }
    162   bool IsShortTypes() const {
    163     return IsShort() || IsByte() || IsBoolean() || IsConstantShort();
    164   }
    165   bool IsCharTypes() const {
    166     return IsChar() || IsBooleanTypes() || IsConstantChar();
    167   }
    168   bool IsIntegralTypes() const {
    169     return IsInteger() || IsConstant() || IsByte() || IsShort() || IsChar() || IsBoolean();
    170   }
    171   // Give the constant value encoded, but this shouldn't be called in the general case.
    172   virtual int32_t ConstantValue() const;
    173   virtual int32_t ConstantValueLo() const;
    174   virtual int32_t ConstantValueHi() const;
    175   bool IsArrayIndexTypes() const {
    176     return IsIntegralTypes();
    177   }
    178   // Float type may be derived from any constant type
    179   bool IsFloatTypes() const {
    180     return IsFloat() || IsConstant();
    181   }
    182   bool IsLongTypes() const {
    183     return IsLongLo() || IsLongConstant();
    184   }
    185   bool IsLongHighTypes() const {
    186     return (IsLongHi() ||
    187             IsPreciseConstantHi() ||
    188             IsImpreciseConstantHi());
    189   }
    190   bool IsDoubleTypes() const {
    191     return IsDoubleLo() || IsLongConstant();
    192   }
    193   bool IsDoubleHighTypes() const {
    194     return (IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    195   }
    196   virtual bool IsLong() const {
    197     return false;
    198   }
    199   virtual bool HasClass() const {
    200     return false;
    201   }
    202   bool IsJavaLangObject() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    203   bool IsArrayTypes() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    204   bool IsObjectArrayTypes() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    205   Primitive::Type GetPrimitiveType() const;
    206   bool IsJavaLangObjectArray() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    207   bool IsInstantiableTypes() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    208   const std::string& GetDescriptor() const {
    209     DCHECK(HasClass() || (IsUnresolvedTypes() && !IsUnresolvedMergedReference() &&
    210                           !IsUnresolvedSuperClass()));
    211     return descriptor_;
    212   }
    213   mirror::Class* GetClass() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    214     DCHECK(!IsUnresolvedReference());
    215     DCHECK(!klass_.IsNull()) << Dump();
    216     DCHECK(HasClass());
    217     return klass_.Read();
    218   }
    219   uint16_t GetId() const {
    220     return cache_id_;
    221   }
    222   RegType& GetSuperClass(RegTypeCache* cache)
    223       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    224 
    225   virtual std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) = 0;
    226 
    227   // Can this type access other?
    228   bool CanAccess(RegType& other) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    229 
    230   // Can this type access a member with the given properties?
    231   bool CanAccessMember(mirror::Class* klass, uint32_t access_flags)
    232     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    233 
    234   // Can this type be assigned by src?
    235   // Note: Object and interface types may always be assigned to one another, see comment on
    236   // ClassJoin.
    237   bool IsAssignableFrom(RegType& src) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    238 
    239   // Can this type be assigned by src? Variant of IsAssignableFrom that doesn't allow assignment to
    240   // an interface from an Object.
    241   bool IsStrictlyAssignableFrom(RegType& src) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    242 
    243   // Are these RegTypes the same?
    244   bool Equals(RegType& other) const {
    245     return GetId() == other.GetId();
    246   }
    247 
    248   // Compute the merge of this register from one edge (path) with incoming_type from another.
    249   virtual RegType& Merge(RegType& incoming_type, RegTypeCache* reg_types)
    250       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    251 
    252   /*
    253    * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
    254    * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
    255    * 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
    256    * is the deepest (lowest upper bound) parent of S and T).
    257    *
    258    * This operation applies for regular classes and arrays, however, for interface types there
    259    * needn't be a partial ordering on the types. We could solve the problem of a lack of a partial
    260    * order by introducing sets of types, however, the only operation permissible on an interface is
    261    * invoke-interface. In the tradition of Java verifiers [1] we defer the verification of interface
    262    * types until an invoke-interface call on the interface typed reference at runtime and allow
    263    * the perversion of Object being assignable to an interface type (note, however, that we don't
    264    * allow assignment of Object or Interface to any concrete class and are therefore type safe).
    265    *
    266    * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
    267    */
    268   static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t)
    269       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    270 
    271   virtual ~RegType() {}
    272 
    273   void VisitRoots(RootCallback* callback, void* arg) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    274 
    275  protected:
    276   RegType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    277       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    278       : descriptor_(descriptor), klass_(GcRoot<mirror::Class>(klass)), cache_id_(cache_id) {
    279     if (kIsDebugBuild) {
    280       CheckInvariants();
    281     }
    282   }
    283 
    284   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    285 
    286 
    287   const std::string descriptor_;
    288   GcRoot<mirror::Class> klass_;
    289   const uint16_t cache_id_;
    290 
    291   friend class RegTypeCache;
    292 
    293  private:
    294   DISALLOW_COPY_AND_ASSIGN(RegType);
    295 };
    296 
    297 // Bottom type.
    298 class ConflictType : public RegType {
    299  public:
    300   bool IsConflict() const {
    301     return true;
    302   }
    303 
    304   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    305 
    306   // Get the singleton Conflict instance.
    307   static ConflictType* GetInstance();
    308 
    309   // Create the singleton instance.
    310   static ConflictType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    311                                       uint16_t cache_id)
    312       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    313 
    314   // Destroy the singleton instance.
    315   static void Destroy();
    316 
    317  private:
    318   ConflictType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    319       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    320       : RegType(klass, descriptor, cache_id) {
    321   }
    322 
    323   static ConflictType* instance_;
    324 };
    325 
    326 // A variant of the bottom type used to specify an undefined value in the incoming registers.
    327 // Merging with UndefinedType yields ConflictType which is the true bottom.
    328 class UndefinedType : public RegType {
    329  public:
    330   bool IsUndefined() const {
    331     return true;
    332   }
    333 
    334   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    335 
    336   // Get the singleton Undefined instance.
    337   static UndefinedType* GetInstance();
    338 
    339   // Create the singleton instance.
    340   static UndefinedType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    341                                        uint16_t cache_id)
    342       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    343 
    344   // Destroy the singleton instance.
    345   static void Destroy();
    346 
    347  private:
    348   UndefinedType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    349      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    350       : RegType(klass, descriptor, cache_id) {
    351   }
    352 
    353   virtual RegType& Merge(RegType& incoming_type, RegTypeCache* reg_types)
    354       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    355 
    356   static UndefinedType* instance_;
    357 };
    358 
    359 class PrimitiveType : public RegType {
    360  public:
    361   PrimitiveType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    362       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    363 };
    364 
    365 class Cat1Type : public PrimitiveType {
    366  public:
    367   Cat1Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    368       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    369 };
    370 
    371 class IntegerType : public Cat1Type {
    372  public:
    373   bool IsInteger() const {
    374     return true;
    375   }
    376   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    377   static IntegerType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    378                                      uint16_t cache_id)
    379       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    380   static IntegerType* GetInstance();
    381   static void Destroy();
    382  private:
    383   IntegerType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    384       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    385       : Cat1Type(klass, descriptor, cache_id) {
    386   }
    387   static IntegerType* instance_;
    388 };
    389 
    390 class BooleanType : public Cat1Type {
    391  public:
    392   bool IsBoolean() const {
    393     return true;
    394   }
    395   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    396   static BooleanType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    397                                      uint16_t cache_id)
    398       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    399   static BooleanType* GetInstance();
    400   static void Destroy();
    401  private:
    402   BooleanType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    403       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    404       : Cat1Type(klass, descriptor, cache_id) {
    405   }
    406 
    407   static BooleanType* instance;
    408 };
    409 
    410 class ByteType : public Cat1Type {
    411  public:
    412   bool IsByte() const {
    413     return true;
    414   }
    415   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    416   static ByteType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    417                                   uint16_t cache_id)
    418       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    419   static ByteType* GetInstance();
    420   static void Destroy();
    421  private:
    422   ByteType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    423       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    424       : Cat1Type(klass, descriptor, cache_id) {
    425   }
    426   static ByteType* instance_;
    427 };
    428 
    429 class ShortType : public Cat1Type {
    430  public:
    431   bool IsShort() const {
    432     return true;
    433   }
    434   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    435   static ShortType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    436                                    uint16_t cache_id)
    437       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    438   static ShortType* GetInstance();
    439   static void Destroy();
    440  private:
    441   ShortType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    442       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    443       : Cat1Type(klass, descriptor, cache_id) {
    444   }
    445   static ShortType* instance_;
    446 };
    447 
    448 class CharType : public Cat1Type {
    449  public:
    450   bool IsChar() const {
    451     return true;
    452   }
    453   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    454   static CharType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    455                                   uint16_t cache_id)
    456       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    457   static CharType* GetInstance();
    458   static void Destroy();
    459  private:
    460   CharType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    461       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    462       : Cat1Type(klass, descriptor, cache_id) {
    463   }
    464   static CharType* instance_;
    465 };
    466 
    467 class FloatType : public Cat1Type {
    468  public:
    469   bool IsFloat() const {
    470     return true;
    471   }
    472   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    473   static FloatType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    474                                    uint16_t cache_id)
    475       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    476   static FloatType* GetInstance();
    477   static void Destroy();
    478  private:
    479   FloatType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    480       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    481       : Cat1Type(klass, descriptor, cache_id) {
    482   }
    483   static FloatType* instance_;
    484 };
    485 
    486 class Cat2Type : public PrimitiveType {
    487  public:
    488   Cat2Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    489       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    490 };
    491 
    492 class LongLoType : public Cat2Type {
    493  public:
    494   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    495   bool IsLongLo() const {
    496     return true;
    497   }
    498   bool IsLong() const {
    499     return true;
    500   }
    501   static LongLoType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    502                                     uint16_t cache_id)
    503       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    504   static LongLoType* GetInstance();
    505   static void Destroy();
    506  private:
    507   LongLoType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    508       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    509       : Cat2Type(klass, descriptor, cache_id) {
    510   }
    511   static LongLoType* instance_;
    512 };
    513 
    514 class LongHiType : public Cat2Type {
    515  public:
    516   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    517   bool IsLongHi() const {
    518     return true;
    519   }
    520   static LongHiType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    521                                     uint16_t cache_id)
    522       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    523   static LongHiType* GetInstance();
    524   static void Destroy();
    525  private:
    526   LongHiType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    527       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    528       : Cat2Type(klass, descriptor, cache_id) {
    529   }
    530   static LongHiType* instance_;
    531 };
    532 
    533 class DoubleLoType : public Cat2Type {
    534  public:
    535   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    536   bool IsDoubleLo() const {
    537     return true;
    538   }
    539   bool IsDouble() const {
    540     return true;
    541   }
    542   static DoubleLoType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    543                                       uint16_t cache_id)
    544       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    545   static DoubleLoType* GetInstance();
    546   static void Destroy();
    547  private:
    548   DoubleLoType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    549       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    550       : Cat2Type(klass, descriptor, cache_id) {
    551   }
    552   static DoubleLoType* instance_;
    553 };
    554 
    555 class DoubleHiType : public Cat2Type {
    556  public:
    557   std::string Dump();
    558   virtual bool IsDoubleHi() const {
    559     return true;
    560   }
    561   static DoubleHiType* CreateInstance(mirror::Class* klass, const std::string& descriptor,
    562                                       uint16_t cache_id)
    563       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    564   static DoubleHiType* GetInstance();
    565   static void Destroy();
    566  private:
    567   DoubleHiType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    568       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    569       : Cat2Type(klass, descriptor, cache_id) {
    570   }
    571   static DoubleHiType* instance_;
    572 };
    573 
    574 class ConstantType : public RegType {
    575  public:
    576   ConstantType(uint32_t constat, uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    577 
    578   // If this is a 32-bit constant, what is the value? This value may be imprecise in which case
    579   // the value represents part of the integer range of values that may be held in the register.
    580   int32_t ConstantValue() const {
    581     DCHECK(IsConstantTypes());
    582     return constant_;
    583   }
    584   int32_t ConstantValueLo() const;
    585   int32_t ConstantValueHi() const;
    586 
    587   bool IsZero() const {
    588     return IsPreciseConstant() && ConstantValue() == 0;
    589   }
    590   bool IsOne() const {
    591     return IsPreciseConstant() && ConstantValue() == 1;
    592   }
    593 
    594   bool IsConstantChar() const {
    595     return IsConstant() && ConstantValue() >= 0 &&
    596            ConstantValue() <= std::numeric_limits<jchar>::max();
    597   }
    598   bool IsConstantByte() const {
    599     return IsConstant() &&
    600            ConstantValue() >= std::numeric_limits<jbyte>::min() &&
    601            ConstantValue() <= std::numeric_limits<jbyte>::max();
    602   }
    603   bool IsConstantShort() const {
    604     return IsConstant() &&
    605            ConstantValue() >= std::numeric_limits<jshort>::min() &&
    606            ConstantValue() <= std::numeric_limits<jshort>::max();
    607   }
    608   virtual bool IsConstantTypes() const { return true; }
    609 
    610  private:
    611   const uint32_t constant_;
    612 };
    613 
    614 class PreciseConstType : public ConstantType {
    615  public:
    616   PreciseConstType(uint32_t constat, uint16_t cache_id) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    617       : ConstantType(constat, cache_id) {
    618   }
    619 
    620   bool IsPreciseConstant() const {
    621     return true;
    622   }
    623 
    624   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    625 };
    626 
    627 class PreciseConstLoType : public ConstantType {
    628  public:
    629   PreciseConstLoType(uint32_t constat, uint16_t cache_id)
    630      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    631       : ConstantType(constat, cache_id) {
    632   }
    633   bool IsPreciseConstantLo() const {
    634     return true;
    635   }
    636   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    637 };
    638 
    639 class PreciseConstHiType : public ConstantType {
    640  public:
    641   PreciseConstHiType(uint32_t constat, uint16_t cache_id)
    642      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    643       : ConstantType(constat, cache_id) {
    644   }
    645   bool IsPreciseConstantHi() const {
    646     return true;
    647   }
    648   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    649 };
    650 
    651 class ImpreciseConstType : public ConstantType {
    652  public:
    653   ImpreciseConstType(uint32_t constat, uint16_t cache_id)
    654      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    655   bool IsImpreciseConstant() const {
    656     return true;
    657   }
    658   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    659 };
    660 
    661 class ImpreciseConstLoType : public ConstantType {
    662  public:
    663   ImpreciseConstLoType(uint32_t constat, uint16_t cache_id)
    664      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : ConstantType(constat, cache_id) {
    665   }
    666   bool IsImpreciseConstantLo() const {
    667     return true;
    668   }
    669   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    670 };
    671 
    672 class ImpreciseConstHiType : public ConstantType {
    673  public:
    674   ImpreciseConstHiType(uint32_t constat, uint16_t cache_id)
    675      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : ConstantType(constat, cache_id) {
    676   }
    677   bool IsImpreciseConstantHi() const {
    678     return true;
    679   }
    680   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    681 };
    682 
    683 // Common parent of all uninitialized types. Uninitialized types are created by "new" dex
    684 // instructions and must be passed to a constructor.
    685 class UninitializedType : public RegType {
    686  public:
    687   UninitializedType(mirror::Class* klass, const std::string& descriptor, uint32_t allocation_pc,
    688                     uint16_t cache_id)
    689       : RegType(klass, descriptor, cache_id), allocation_pc_(allocation_pc) {
    690   }
    691 
    692   bool IsUninitializedTypes() const;
    693   bool IsNonZeroReferenceTypes() const;
    694 
    695   uint32_t GetAllocationPc() const {
    696     DCHECK(IsUninitializedTypes());
    697     return allocation_pc_;
    698   }
    699 
    700  private:
    701   const uint32_t allocation_pc_;
    702 };
    703 
    704 // Similar to ReferenceType but not yet having been passed to a constructor.
    705 class UninitializedReferenceType : public UninitializedType {
    706  public:
    707   UninitializedReferenceType(mirror::Class* klass, const std::string& descriptor,
    708                              uint32_t allocation_pc, uint16_t cache_id)
    709       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    710       : UninitializedType(klass, descriptor, allocation_pc, cache_id) {
    711   }
    712 
    713   bool IsUninitializedReference() const {
    714     return true;
    715   }
    716 
    717   bool HasClass() const {
    718     return true;
    719   }
    720 
    721   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    722 };
    723 
    724 // Similar to UnresolvedReferenceType but not yet having been passed to a constructor.
    725 class UnresolvedUninitializedRefType : public UninitializedType {
    726  public:
    727   UnresolvedUninitializedRefType(const std::string& descriptor, uint32_t allocation_pc,
    728                                  uint16_t cache_id)
    729       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    730       : UninitializedType(NULL, descriptor, allocation_pc, cache_id) {
    731     if (kIsDebugBuild) {
    732       CheckInvariants();
    733     }
    734   }
    735 
    736   bool IsUnresolvedAndUninitializedReference() const {
    737     return true;
    738   }
    739 
    740   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    741  private:
    742   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    743 };
    744 
    745 // Similar to UninitializedReferenceType but special case for the this argument of a constructor.
    746 class UninitializedThisReferenceType : public UninitializedType {
    747  public:
    748   UninitializedThisReferenceType(mirror::Class* klass, const std::string& descriptor,
    749                                  uint16_t cache_id)
    750       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    751       : UninitializedType(klass, descriptor, 0, cache_id) {
    752     if (kIsDebugBuild) {
    753       CheckInvariants();
    754     }
    755   }
    756 
    757   virtual bool IsUninitializedThisReference() const {
    758     return true;
    759   }
    760 
    761   bool HasClass() const {
    762     return true;
    763   }
    764 
    765   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    766 
    767  private:
    768   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    769 };
    770 
    771 class UnresolvedUninitializedThisRefType : public UninitializedType {
    772  public:
    773   UnresolvedUninitializedThisRefType(const std::string& descriptor, uint16_t cache_id)
    774       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    775       : UninitializedType(NULL, descriptor, 0, cache_id) {
    776     if (kIsDebugBuild) {
    777       CheckInvariants();
    778     }
    779   }
    780 
    781   bool IsUnresolvedAndUninitializedThisReference() const {
    782     return true;
    783   }
    784 
    785   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    786  private:
    787   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    788 };
    789 
    790 // A type of register holding a reference to an Object of type GetClass or a sub-class.
    791 class ReferenceType : public RegType {
    792  public:
    793   ReferenceType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    794      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    795      : RegType(klass, descriptor, cache_id) {
    796   }
    797 
    798   bool IsReference() const {
    799     return true;
    800   }
    801 
    802   bool IsNonZeroReferenceTypes() const {
    803     return true;
    804   }
    805 
    806   bool HasClass() const {
    807     return true;
    808   }
    809 
    810   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    811 };
    812 
    813 // A type of register holding a reference to an Object of type GetClass and only an object of that
    814 // type.
    815 class PreciseReferenceType : public RegType {
    816  public:
    817   PreciseReferenceType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
    818       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    819 
    820   bool IsPreciseReference() const {
    821     return true;
    822   }
    823 
    824   bool IsNonZeroReferenceTypes() const {
    825     return true;
    826   }
    827 
    828   bool HasClass() const {
    829     return true;
    830   }
    831 
    832   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    833 };
    834 
    835 // Common parent of unresolved types.
    836 class UnresolvedType : public RegType {
    837  public:
    838   UnresolvedType(const std::string& descriptor, uint16_t cache_id)
    839       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : RegType(NULL, descriptor, cache_id) {
    840   }
    841 
    842   bool IsNonZeroReferenceTypes() const;
    843 };
    844 
    845 // Similar to ReferenceType except the Class couldn't be loaded. Assignability and other tests made
    846 // of this type must be conservative.
    847 class UnresolvedReferenceType : public UnresolvedType {
    848  public:
    849   UnresolvedReferenceType(const std::string& descriptor, uint16_t cache_id)
    850      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : UnresolvedType(descriptor, cache_id) {
    851     if (kIsDebugBuild) {
    852       CheckInvariants();
    853     }
    854   }
    855 
    856   bool IsUnresolvedReference() const {
    857     return true;
    858   }
    859 
    860   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    861  private:
    862   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    863 };
    864 
    865 // Type representing the super-class of an unresolved type.
    866 class UnresolvedSuperClass : public UnresolvedType {
    867  public:
    868   UnresolvedSuperClass(uint16_t child_id, RegTypeCache* reg_type_cache, uint16_t cache_id)
    869       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    870       : UnresolvedType("", cache_id), unresolved_child_id_(child_id),
    871         reg_type_cache_(reg_type_cache) {
    872     if (kIsDebugBuild) {
    873       CheckInvariants();
    874     }
    875   }
    876 
    877   bool IsUnresolvedSuperClass() const {
    878     return true;
    879   }
    880 
    881   uint16_t GetUnresolvedSuperClassChildId() const {
    882     DCHECK(IsUnresolvedSuperClass());
    883     return static_cast<uint16_t>(unresolved_child_id_ & 0xFFFF);
    884   }
    885 
    886   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    887 
    888  private:
    889   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    890 
    891   const uint16_t unresolved_child_id_;
    892   const RegTypeCache* const reg_type_cache_;
    893 };
    894 
    895 // A merge of two unresolved types. If the types were resolved this may be Conflict or another
    896 // known ReferenceType.
    897 class UnresolvedMergedType : public UnresolvedType {
    898  public:
    899   UnresolvedMergedType(uint16_t left_id, uint16_t right_id, const RegTypeCache* reg_type_cache,
    900                        uint16_t cache_id)
    901       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    902       : UnresolvedType("", cache_id), reg_type_cache_(reg_type_cache), merged_types_(left_id, right_id) {
    903     if (kIsDebugBuild) {
    904       CheckInvariants();
    905     }
    906   }
    907 
    908   // The top of a tree of merged types.
    909   std::pair<uint16_t, uint16_t> GetTopMergedTypes() const {
    910     DCHECK(IsUnresolvedMergedReference());
    911     return merged_types_;
    912   }
    913 
    914   // The complete set of merged types.
    915   std::set<uint16_t> GetMergedTypes() const;
    916 
    917   bool IsUnresolvedMergedReference() const {
    918     return true;
    919   }
    920 
    921   std::string Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    922 
    923  private:
    924   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    925 
    926   const RegTypeCache* const reg_type_cache_;
    927   const std::pair<uint16_t, uint16_t> merged_types_;
    928 };
    929 
    930 std::ostream& operator<<(std::ostream& os, const RegType& rhs)
    931     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    932 
    933 }  // namespace verifier
    934 }  // namespace art
    935 
    936 #endif  // ART_RUNTIME_VERIFIER_REG_TYPE_H_
    937