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