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