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