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