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