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#include "reg_type.h"
18
19
20#include "base/casts.h"
21#include "dex_file-inl.h"
22#include "mirror/class.h"
23#include "mirror/class-inl.h"
24#include "mirror/object-inl.h"
25#include "mirror/object_array-inl.h"
26#include "object_utils.h"
27#include "reg_type_cache-inl.h"
28#include "scoped_thread_state_change.h"
29
30#include <limits>
31#include <sstream>
32
33namespace art {
34namespace verifier {
35
36UndefinedType* UndefinedType::instance_ = NULL;
37ConflictType* ConflictType::instance_ = NULL;
38BooleanType* BooleanType::instance = NULL;
39ByteType* ByteType::instance_ = NULL;
40ShortType* ShortType::instance_ = NULL;
41CharType* CharType::instance_ = NULL;
42FloatType* FloatType::instance_ = NULL;
43LongLoType* LongLoType::instance_ = NULL;
44LongHiType* LongHiType::instance_ = NULL;
45DoubleLoType* DoubleLoType::instance_ = NULL;
46DoubleHiType* DoubleHiType::instance_ = NULL;
47IntegerType* IntegerType::instance_ = NULL;
48
49int32_t RegType::ConstantValue() const {
50  ScopedObjectAccess soa(Thread::Current());
51  LOG(FATAL) << "Unexpected call to ConstantValue: " << *this;
52  return 0;
53}
54
55int32_t RegType::ConstantValueLo() const {
56  ScopedObjectAccess soa(Thread::Current());
57  LOG(FATAL) << "Unexpected call to ConstantValueLo: " << *this;
58  return 0;
59}
60
61int32_t RegType::ConstantValueHi() const {
62  ScopedObjectAccess soa(Thread::Current());
63  LOG(FATAL) << "Unexpected call to ConstantValueHi: " << *this;
64  return 0;
65}
66
67PrimitiveType::PrimitiveType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
68    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
69    : RegType(klass, descriptor, cache_id) {
70  CHECK(klass != NULL);
71  CHECK(!descriptor.empty());
72}
73
74Cat1Type::Cat1Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
75    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
76    : PrimitiveType(klass, descriptor, cache_id) {
77}
78
79Cat2Type::Cat2Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
80    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
81    : PrimitiveType(klass, descriptor, cache_id) {
82}
83
84std::string PreciseConstType::Dump() const {
85  std::stringstream result;
86  uint32_t val = ConstantValue();
87  if (val == 0) {
88    CHECK(IsPreciseConstant());
89    result << "Zero/null";
90  } else {
91    result << "Precise ";
92    if (IsConstantShort()) {
93      result << StringPrintf("Constant: %d", val);
94    } else {
95      result << StringPrintf("Constant: 0x%x", val);
96    }
97  }
98  return result.str();
99}
100
101std::string BooleanType::Dump() const {
102  return "boolean";
103}
104
105std::string ConflictType::Dump() const {
106    return "Conflict";
107}
108
109std::string ByteType::Dump() const {
110  return "Byte";
111}
112
113std::string ShortType::Dump() const {
114  return "short";
115}
116
117std::string CharType::Dump() const {
118  return "Char";
119}
120
121std::string FloatType::Dump() const {
122  return "float";
123}
124
125std::string LongLoType::Dump() const {
126  return "long (Low Half)";
127}
128
129std::string LongHiType::Dump() const {
130  return "long (High Half)";
131}
132
133std::string DoubleLoType::Dump() const {
134  return "Double (Low Half)";
135}
136
137std::string DoubleHiType::Dump() const {
138  return "Double (High Half)";
139}
140
141std::string IntegerType::Dump() const {
142    return "Integer";
143}
144
145DoubleHiType* DoubleHiType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
146                                           uint16_t cache_id) {
147  if (instance_ == NULL) {
148    instance_ = new DoubleHiType(klass, descriptor, cache_id);
149  }
150  return instance_;
151}
152
153DoubleHiType* DoubleHiType::GetInstance() {
154  CHECK(instance_ != NULL);
155  return instance_;
156}
157
158void DoubleHiType::Destroy() {
159  if (instance_ != NULL) {
160    delete instance_;
161    instance_ = NULL;
162  }
163}
164
165DoubleLoType* DoubleLoType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
166                                           uint16_t cache_id) {
167  if (instance_ == NULL) {
168    instance_ = new DoubleLoType(klass, descriptor, cache_id);
169  }
170  return instance_;
171}
172
173DoubleLoType* DoubleLoType::GetInstance() {
174  CHECK(instance_ != NULL);
175  return instance_;
176}
177
178void DoubleLoType::Destroy() {
179  if (instance_ != NULL) {
180    delete instance_;
181    instance_ = NULL;
182  }
183}
184
185LongLoType* LongLoType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
186                                       uint16_t cache_id) {
187  if (instance_ == NULL) {
188    instance_ = new LongLoType(klass, descriptor, cache_id);
189  }
190  return instance_;
191}
192
193LongHiType* LongHiType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
194                                       uint16_t cache_id) {
195  if (instance_ == NULL) {
196    instance_ = new LongHiType(klass, descriptor, cache_id);
197  }
198  return instance_;
199}
200
201LongHiType* LongHiType::GetInstance() {
202  CHECK(instance_ != NULL);
203  return instance_;
204}
205
206void LongHiType::Destroy() {
207  if (instance_ != NULL) {
208    delete instance_;
209    instance_ = NULL;
210  }
211}
212
213LongLoType* LongLoType::GetInstance() {
214  CHECK(instance_ != NULL);
215  return instance_;
216}
217
218void LongLoType::Destroy() {
219  if (instance_ != NULL) {
220    delete instance_;
221    instance_ = NULL;
222  }
223}
224
225FloatType* FloatType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
226                                     uint16_t cache_id) {
227  if (instance_ == NULL) {
228    instance_ = new FloatType(klass, descriptor, cache_id);
229  }
230  return instance_;
231}
232FloatType* FloatType::GetInstance() {
233  CHECK(instance_ != NULL);
234  return instance_;
235}
236
237void FloatType::Destroy() {
238  if (instance_ != NULL) {
239    delete instance_;
240    instance_ = NULL;
241  }
242}
243
244CharType* CharType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
245                                   uint16_t cache_id) {
246  if (instance_ == NULL) {
247    instance_ = new CharType(klass, descriptor, cache_id);
248  }
249  return instance_;
250}
251
252CharType* CharType::GetInstance() {
253  CHECK(instance_ != NULL);
254  return instance_;
255}
256
257void CharType::Destroy() {
258  if (instance_ != NULL) {
259    delete instance_;
260    instance_ = NULL;
261  }
262}
263
264ShortType* ShortType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
265                                     uint16_t cache_id) {
266  if (instance_ == NULL) {
267    instance_ = new ShortType(klass, descriptor, cache_id);
268  }
269  return instance_;
270}
271
272ShortType* ShortType::GetInstance() {
273  CHECK(instance_ != NULL);
274  return instance_;
275}
276
277void ShortType::Destroy() {
278  if (instance_ != NULL) {
279    delete instance_;
280    instance_ = NULL;
281  }
282}
283
284ByteType* ByteType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
285                                   uint16_t cache_id) {
286  if (instance_ == NULL) {
287    instance_ = new ByteType(klass, descriptor, cache_id);
288  }
289  return instance_;
290}
291
292ByteType* ByteType::GetInstance() {
293  CHECK(instance_ != NULL);
294  return instance_;
295}
296
297void ByteType::Destroy() {
298  if (instance_ != NULL) {
299    delete instance_;
300    instance_ = NULL;
301  }
302}
303
304IntegerType* IntegerType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
305                                         uint16_t cache_id) {
306  if (instance_ == NULL) {
307    instance_ = new IntegerType(klass, descriptor, cache_id);
308  }
309  return instance_;
310}
311
312IntegerType* IntegerType::GetInstance() {
313  CHECK(instance_ != NULL);
314  return instance_;
315}
316
317void IntegerType::Destroy() {
318  if (instance_ != NULL) {
319    delete instance_;
320    instance_ = NULL;
321  }
322}
323
324ConflictType* ConflictType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
325                                           uint16_t cache_id) {
326  if (instance_ == NULL) {
327    instance_ = new ConflictType(klass, descriptor, cache_id);
328  }
329  return instance_;
330}
331
332ConflictType* ConflictType::GetInstance() {
333  CHECK(instance_ != NULL);
334  return instance_;
335}
336
337void ConflictType::Destroy() {
338  if (instance_ != NULL) {
339    delete instance_;
340    instance_ = NULL;
341  }
342}
343
344BooleanType* BooleanType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
345                                         uint16_t cache_id) {
346  if (BooleanType::instance == NULL) {
347    instance = new BooleanType(klass, descriptor, cache_id);
348  }
349  return BooleanType::instance;
350}
351
352BooleanType* BooleanType::GetInstance() {
353  CHECK(BooleanType::instance != NULL);
354  return BooleanType::instance;
355}
356
357void BooleanType::Destroy() {
358  if (BooleanType::instance != NULL) {
359    delete instance;
360    instance = NULL;
361  }
362}
363
364std::string UndefinedType::Dump() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
365  return "Undefined";
366}
367
368UndefinedType* UndefinedType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
369                                             uint16_t cache_id) {
370  if (instance_ == NULL) {
371    instance_ = new UndefinedType(klass, descriptor, cache_id);
372  }
373  return instance_;
374}
375
376UndefinedType* UndefinedType::GetInstance() {
377  CHECK(instance_ != NULL);
378  return instance_;
379}
380
381void UndefinedType::Destroy() {
382  if (instance_ != NULL) {
383    delete instance_;
384    instance_ = NULL;
385  }
386}
387
388PreciseReferenceType::PreciseReferenceType(mirror::Class* klass, const std::string& descriptor,
389                                           uint16_t cache_id)
390    : RegType(klass, descriptor, cache_id) {
391  DCHECK(klass->IsInstantiable());
392}
393
394std::string UnresolvedMergedType::Dump() const {
395  std::stringstream result;
396  std::set<uint16_t> types = GetMergedTypes();
397  result << "UnresolvedMergedReferences(";
398  auto it = types.begin();
399  result << reg_type_cache_->GetFromId(*it).Dump();
400  for (++it; it != types.end(); ++it) {
401    result << ", ";
402    result << reg_type_cache_->GetFromId(*it).Dump();
403  }
404  result << ")";
405  return result.str();
406}
407
408std::string UnresolvedSuperClass::Dump() const {
409  std::stringstream result;
410  uint16_t super_type_id = GetUnresolvedSuperClassChildId();
411  result << "UnresolvedSuperClass(" << reg_type_cache_->GetFromId(super_type_id).Dump() << ")";
412  return result.str();
413}
414
415std::string UnresolvedReferenceType::Dump() const {
416  std::stringstream result;
417  result << "Unresolved Reference" << ": " << PrettyDescriptor(GetDescriptor());
418  return result.str();
419}
420
421std::string UnresolvedUninitializedRefType::Dump() const {
422  std::stringstream result;
423  result << "Unresolved And Uninitialized Reference" << ": " << PrettyDescriptor(GetDescriptor());
424  result << " Allocation PC: " << GetAllocationPc();
425  return result.str();
426}
427
428std::string UnresolvedUninitializedThisRefType::Dump() const {
429  std::stringstream result;
430  result << "Unresolved And Uninitialized This Reference" << PrettyDescriptor(GetDescriptor());
431  return result.str();
432}
433
434std::string ReferenceType::Dump() const {
435  std::stringstream result;
436  result << "Reference" << ": " << PrettyDescriptor(GetClass());
437  return result.str();
438}
439
440std::string PreciseReferenceType::Dump() const {
441  std::stringstream result;
442  result << "Precise Reference" << ": "<< PrettyDescriptor(GetClass());
443  return result.str();
444}
445
446std::string UninitializedReferenceType::Dump() const {
447  std::stringstream result;
448  result << "Uninitialized Reference" << ": " << PrettyDescriptor(GetClass());
449  result << " Allocation PC: " << GetAllocationPc();
450  return result.str();
451}
452
453std::string UninitializedThisReferenceType::Dump() const {
454  std::stringstream result;
455  result << "Uninitialized This Reference" << ": " << PrettyDescriptor(GetClass());
456  result << "Allocation PC: " << GetAllocationPc();
457  return result.str();
458}
459
460std::string ImpreciseConstType::Dump() const {
461  std::stringstream result;
462  uint32_t val = ConstantValue();
463  if (val == 0) {
464    CHECK(IsPreciseConstant());
465    result << "Zero/null";
466  } else {
467    result << "Imprecise ";
468    if (IsConstantShort()) {
469      result << StringPrintf("Constant: %d", val);
470    } else {
471      result << StringPrintf("Constant: 0x%x", val);
472    }
473  }
474  return result.str();
475}
476std::string PreciseConstLoType::Dump() const {
477  std::stringstream result;
478
479  int32_t val = ConstantValueLo();
480  result << "Precise ";
481  if (val >= std::numeric_limits<jshort>::min() &&
482      val <= std::numeric_limits<jshort>::max()) {
483    result << StringPrintf("Low-half Constant: %d", val);
484  } else {
485    result << StringPrintf("Low-half Constant: 0x%x", val);
486  }
487  return result.str();
488}
489
490std::string ImpreciseConstLoType::Dump() const {
491  std::stringstream result;
492
493  int32_t val = ConstantValueLo();
494  result << "Imprecise ";
495  if (val >= std::numeric_limits<jshort>::min() &&
496      val <= std::numeric_limits<jshort>::max()) {
497    result << StringPrintf("Low-half Constant: %d", val);
498  } else {
499    result << StringPrintf("Low-half Constant: 0x%x", val);
500  }
501  return result.str();
502}
503
504std::string PreciseConstHiType::Dump() const {
505  std::stringstream result;
506  int32_t val = ConstantValueHi();
507  result << "Precise ";
508  if (val >= std::numeric_limits<jshort>::min() &&
509      val <= std::numeric_limits<jshort>::max()) {
510    result << StringPrintf("High-half Constant: %d", val);
511  } else {
512    result << StringPrintf("High-half Constant: 0x%x", val);
513  }
514  return result.str();
515}
516
517std::string ImpreciseConstHiType::Dump() const {
518  std::stringstream result;
519  int32_t val = ConstantValueHi();
520  result << "Imprecise ";
521  if (val >= std::numeric_limits<jshort>::min() &&
522      val <= std::numeric_limits<jshort>::max()) {
523    result << StringPrintf("High-half Constant: %d", val);
524  } else {
525    result << StringPrintf("High-half Constant: 0x%x", val);
526  }
527  return result.str();
528}
529
530ConstantType::ConstantType(uint32_t constant, uint16_t cache_id)
531    : RegType(NULL, "", cache_id), constant_(constant) {
532}
533
534const RegType& UndefinedType::Merge(const RegType& incoming_type, RegTypeCache* reg_types) const
535    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
536  if (incoming_type.IsUndefined()) {
537    return *this;  // Undefined MERGE Undefined => Undefined
538  }
539  return reg_types->Conflict();
540}
541
542const RegType& RegType::HighHalf(RegTypeCache* cache) const {
543  DCHECK(IsLowHalf());
544  if (IsLongLo()) {
545    return cache->LongHi();
546  } else if (IsDoubleLo()) {
547    return cache->DoubleHi();
548  } else {
549    DCHECK(IsImpreciseConstantLo());
550    return cache->FromCat2ConstHi(ConstantValue(), false);
551  }
552}
553
554Primitive::Type RegType::GetPrimitiveType() const {
555  if (IsNonZeroReferenceTypes()) {
556    return Primitive::kPrimNot;
557  } else if (IsBooleanTypes()) {
558    return Primitive::kPrimBoolean;
559  } else if (IsByteTypes()) {
560    return Primitive::kPrimByte;
561  } else if (IsShortTypes()) {
562    return Primitive::kPrimShort;
563  } else if (IsCharTypes()) {
564    return Primitive::kPrimChar;
565  } else if (IsFloat()) {
566    return Primitive::kPrimFloat;
567  } else if (IsIntegralTypes()) {
568    return Primitive::kPrimInt;
569  } else if (IsDoubleLo()) {
570    return Primitive::kPrimDouble;
571  } else {
572    DCHECK(IsLongTypes());
573    return Primitive::kPrimLong;
574  }
575}
576
577bool UninitializedType::IsUninitializedTypes() const {
578  return true;
579}
580
581bool UninitializedType::IsNonZeroReferenceTypes() const {
582  return true;
583}
584
585bool UnresolvedType::IsNonZeroReferenceTypes() const {
586  return true;
587}
588std::set<uint16_t> UnresolvedMergedType::GetMergedTypes() const {
589  std::pair<uint16_t, uint16_t> refs = GetTopMergedTypes();
590  const RegType& _left(reg_type_cache_->GetFromId(refs.first));
591  RegType& __left(const_cast<RegType&>(_left));
592  UnresolvedMergedType* left = down_cast<UnresolvedMergedType*>(&__left);
593
594  RegType& _right(
595      const_cast<RegType&>(reg_type_cache_->GetFromId(refs.second)));
596  UnresolvedMergedType* right = down_cast<UnresolvedMergedType*>(&_right);
597
598  std::set<uint16_t> types;
599  if (left->IsUnresolvedMergedReference()) {
600    types = left->GetMergedTypes();
601  } else {
602    types.insert(refs.first);
603  }
604  if (right->IsUnresolvedMergedReference()) {
605    std::set<uint16_t> right_types = right->GetMergedTypes();
606    types.insert(right_types.begin(), right_types.end());
607  } else {
608    types.insert(refs.second);
609  }
610  if (kIsDebugBuild) {
611    for (const auto& type : types) {
612      CHECK(!reg_type_cache_->GetFromId(type).IsUnresolvedMergedReference());
613    }
614  }
615  return types;
616}
617
618const RegType& RegType::GetSuperClass(RegTypeCache* cache) const {
619  if (!IsUnresolvedTypes()) {
620    mirror::Class* super_klass = GetClass()->GetSuperClass();
621    if (super_klass != NULL) {
622      // A super class of a precise type isn't precise as a precise type indicates the register
623      // holds exactly that type.
624      return cache->FromClass(ClassHelper(super_klass).GetDescriptor(), super_klass, false);
625    } else {
626      return cache->Zero();
627    }
628  } else {
629    if (!IsUnresolvedMergedReference() && !IsUnresolvedSuperClass() &&
630        GetDescriptor()[0] == '[') {
631      // Super class of all arrays is Object.
632      return cache->JavaLangObject(true);
633    } else {
634      return cache->FromUnresolvedSuperClass(*this);
635    }
636  }
637}
638
639bool RegType::CanAccess(const RegType& other) const {
640  if (Equals(other)) {
641    return true;  // Trivial accessibility.
642  } else {
643    bool this_unresolved = IsUnresolvedTypes();
644    bool other_unresolved = other.IsUnresolvedTypes();
645    if (!this_unresolved && !other_unresolved) {
646      return GetClass()->CanAccess(other.GetClass());
647    } else if (!other_unresolved) {
648      return other.GetClass()->IsPublic();  // Be conservative, only allow if other is public.
649    } else {
650      return false;  // More complicated test not possible on unresolved types, be conservative.
651    }
652  }
653}
654
655bool RegType::CanAccessMember(mirror::Class* klass, uint32_t access_flags) const {
656  if ((access_flags & kAccPublic) != 0) {
657    return true;
658  }
659  if (!IsUnresolvedTypes()) {
660    return GetClass()->CanAccessMember(klass, access_flags);
661  } else {
662    return false;  // More complicated test not possible on unresolved types, be conservative.
663  }
664}
665
666bool RegType::IsObjectArrayTypes() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
667  if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
668    // Primitive arrays will always resolve
669    DCHECK(descriptor_[1] == 'L' || descriptor_[1] == '[');
670    return descriptor_[0] == '[';
671  } else if (HasClass()) {
672    mirror::Class* type = GetClass();
673    return type->IsArrayClass() && !type->GetComponentType()->IsPrimitive();
674  } else {
675    return false;
676  }
677}
678
679bool RegType::IsJavaLangObject() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
680  return IsReference() && GetClass()->IsObjectClass();
681}
682
683bool RegType::IsArrayTypes() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
684  if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
685    return descriptor_[0] == '[';
686  } else if (HasClass()) {
687    return GetClass()->IsArrayClass();
688  } else {
689    return false;
690  }
691}
692
693bool RegType::IsJavaLangObjectArray() const {
694  if (HasClass()) {
695    mirror::Class* type = GetClass();
696    return type->IsArrayClass() && type->GetComponentType()->IsObjectClass();
697  }
698  return false;
699}
700
701bool RegType::IsInstantiableTypes() const {
702  return IsUnresolvedTypes() || (IsNonZeroReferenceTypes() && GetClass()->IsInstantiable());
703}
704
705ImpreciseConstType::ImpreciseConstType(uint32_t constat, uint16_t cache_id)
706  : ConstantType(constat, cache_id) {
707}
708
709static bool AssignableFrom(const RegType& lhs, const RegType& rhs, bool strict)
710    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
711  if (lhs.Equals(rhs)) {
712    return true;
713  } else {
714    if (lhs.IsBoolean()) {
715      return rhs.IsBooleanTypes();
716    } else if (lhs.IsByte()) {
717      return rhs.IsByteTypes();
718    } else if (lhs.IsShort()) {
719      return rhs.IsShortTypes();
720    } else if (lhs.IsChar()) {
721      return rhs.IsCharTypes();
722    } else if (lhs.IsInteger()) {
723      return rhs.IsIntegralTypes();
724    } else if (lhs.IsFloat()) {
725      return rhs.IsFloatTypes();
726    } else if (lhs.IsLongLo()) {
727      return rhs.IsLongTypes();
728    } else if (lhs.IsDoubleLo()) {
729      return rhs.IsDoubleTypes();
730    } else {
731      CHECK(lhs.IsReferenceTypes())
732          << "Unexpected register type in IsAssignableFrom: '"
733          << lhs << "' := '" << rhs << "'";
734      if (rhs.IsZero()) {
735        return true;  // All reference types can be assigned null.
736      } else if (!rhs.IsReferenceTypes()) {
737        return false;  // Expect rhs to be a reference type.
738      } else if (lhs.IsJavaLangObject()) {
739        return true;  // All reference types can be assigned to Object.
740      } else if (!strict && !lhs.IsUnresolvedTypes() && lhs.GetClass()->IsInterface()) {
741        // If we're not strict allow assignment to any interface, see comment in ClassJoin.
742        return true;
743      } else if (lhs.IsJavaLangObjectArray()) {
744        return rhs.IsObjectArrayTypes();  // All reference arrays may be assigned to Object[]
745      } else if (lhs.HasClass() && rhs.HasClass() &&
746                 lhs.GetClass()->IsAssignableFrom(rhs.GetClass())) {
747        // We're assignable from the Class point-of-view.
748        return true;
749      } else {
750        // Unresolved types are only assignable for null and equality.
751        return false;
752      }
753    }
754  }
755}
756
757bool RegType::IsAssignableFrom(const RegType& src) const {
758  return AssignableFrom(*this, src, false);
759}
760
761bool RegType::IsStrictlyAssignableFrom(const RegType& src) const {
762  return AssignableFrom(*this, src, true);
763}
764
765int32_t ConstantType::ConstantValue() const {
766  DCHECK(IsConstantTypes());
767  return constant_;
768}
769
770int32_t ConstantType::ConstantValueLo() const {
771  DCHECK(IsConstantLo());
772  return constant_;
773}
774
775int32_t ConstantType::ConstantValueHi() const {
776  if (IsConstantHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()) {
777    return constant_;
778  } else {
779    DCHECK(false);
780    return 0;
781  }
782}
783
784static const RegType& SelectNonConstant(const RegType& a, const RegType& b) {
785  return a.IsConstant() ? b : a;
786}
787
788const RegType& RegType::Merge(const RegType& incoming_type, RegTypeCache* reg_types) const {
789  DCHECK(!Equals(incoming_type));  // Trivial equality handled by caller
790  if (IsConflict()) {
791    return *this;  // Conflict MERGE * => Conflict
792  } else if (incoming_type.IsConflict()) {
793    return incoming_type;  // * MERGE Conflict => Conflict
794  } else if (IsUndefined() || incoming_type.IsUndefined()) {
795    return reg_types->Conflict();  // Unknown MERGE * => Conflict
796  } else if (IsConstant() && incoming_type.IsConstant()) {
797    int32_t val1 = ConstantValue();
798    int32_t val2 = incoming_type.ConstantValue();
799    if (val1 >= 0 && val2 >= 0) {
800      // +ve1 MERGE +ve2 => MAX(+ve1, +ve2)
801      if (val1 >= val2) {
802        if (!IsPreciseConstant()) {
803          return *this;
804        } else {
805          return reg_types->FromCat1Const(val1, false);
806        }
807      } else {
808        if (!incoming_type.IsPreciseConstant()) {
809          return incoming_type;
810        } else {
811          return reg_types->FromCat1Const(val2, false);
812        }
813      }
814    } else if (val1 < 0 && val2 < 0) {
815      // -ve1 MERGE -ve2 => MIN(-ve1, -ve2)
816      if (val1 <= val2) {
817        if (!IsPreciseConstant()) {
818          return *this;
819        } else {
820          return reg_types->FromCat1Const(val1, false);
821        }
822      } else {
823        if (!incoming_type.IsPreciseConstant()) {
824          return incoming_type;
825        } else {
826          return reg_types->FromCat1Const(val2, false);
827        }
828      }
829    } else {
830      // Values are +ve and -ve, choose smallest signed type in which they both fit
831      if (IsConstantByte()) {
832        if (incoming_type.IsConstantByte()) {
833          return reg_types->ByteConstant();
834        } else if (incoming_type.IsConstantShort()) {
835          return reg_types->ShortConstant();
836        } else {
837          return reg_types->IntConstant();
838        }
839      } else if (IsConstantShort()) {
840        if (incoming_type.IsConstantShort()) {
841          return reg_types->ShortConstant();
842        } else {
843          return reg_types->IntConstant();
844        }
845      } else {
846        return reg_types->IntConstant();
847      }
848    }
849  } else if (IsConstantLo() && incoming_type.IsConstantLo()) {
850    int32_t val1 = ConstantValueLo();
851    int32_t val2 = incoming_type.ConstantValueLo();
852    return reg_types->FromCat2ConstLo(val1 | val2, false);
853  } else if (IsConstantHi() && incoming_type.IsConstantHi()) {
854    int32_t val1 = ConstantValueHi();
855    int32_t val2 = incoming_type.ConstantValueHi();
856    return reg_types->FromCat2ConstHi(val1 | val2, false);
857  } else if (IsIntegralTypes() && incoming_type.IsIntegralTypes()) {
858    if (IsBooleanTypes() && incoming_type.IsBooleanTypes()) {
859      return reg_types->Boolean();  // boolean MERGE boolean => boolean
860    }
861    if (IsByteTypes() && incoming_type.IsByteTypes()) {
862      return reg_types->Byte();  // byte MERGE byte => byte
863    }
864    if (IsShortTypes() && incoming_type.IsShortTypes()) {
865      return reg_types->Short();  // short MERGE short => short
866    }
867    if (IsCharTypes() && incoming_type.IsCharTypes()) {
868      return reg_types->Char();  // char MERGE char => char
869    }
870    return reg_types->Integer();  // int MERGE * => int
871  } else if ((IsFloatTypes() && incoming_type.IsFloatTypes()) ||
872             (IsLongTypes() && incoming_type.IsLongTypes()) ||
873             (IsLongHighTypes() && incoming_type.IsLongHighTypes()) ||
874             (IsDoubleTypes() && incoming_type.IsDoubleTypes()) ||
875             (IsDoubleHighTypes() && incoming_type.IsDoubleHighTypes())) {
876    // check constant case was handled prior to entry
877    DCHECK(!IsConstant() || !incoming_type.IsConstant());
878    // float/long/double MERGE float/long/double_constant => float/long/double
879    return SelectNonConstant(*this, incoming_type);
880  } else if (IsReferenceTypes() && incoming_type.IsReferenceTypes()) {
881    if (IsZero() || incoming_type.IsZero()) {
882      return SelectNonConstant(*this, incoming_type);  // 0 MERGE ref => ref
883    } else if (IsJavaLangObject() || incoming_type.IsJavaLangObject()) {
884      return reg_types->JavaLangObject(false);  // Object MERGE ref => Object
885    } else if (IsUnresolvedTypes() || incoming_type.IsUnresolvedTypes()) {
886      // We know how to merge an unresolved type with itself, 0 or Object. In this case we
887      // have two sub-classes and don't know how to merge. Create a new string-based unresolved
888      // type that reflects our lack of knowledge and that allows the rest of the unresolved
889      // mechanics to continue.
890      return reg_types->FromUnresolvedMerge(*this, incoming_type);
891    } else if (IsUninitializedTypes() || incoming_type.IsUninitializedTypes()) {
892      // Something that is uninitialized hasn't had its constructor called. Mark any merge
893      // of this type with something that is initialized as conflicting. The cases of a merge
894      // with itself, 0 or Object are handled above.
895      return reg_types->Conflict();
896    } else {  // Two reference types, compute Join
897      mirror::Class* c1 = GetClass();
898      mirror::Class* c2 = incoming_type.GetClass();
899      DCHECK(c1 != NULL && !c1->IsPrimitive());
900      DCHECK(c2 != NULL && !c2->IsPrimitive());
901      mirror::Class* join_class = ClassJoin(c1, c2);
902      if (c1 == join_class && !IsPreciseReference()) {
903        return *this;
904      } else if (c2 == join_class && !incoming_type.IsPreciseReference()) {
905        return incoming_type;
906      } else {
907        return reg_types->FromClass(ClassHelper(join_class).GetDescriptor(), join_class, false);
908      }
909    }
910  } else {
911    return reg_types->Conflict();  // Unexpected types => Conflict
912  }
913}
914
915// See comment in reg_type.h
916mirror::Class* RegType::ClassJoin(mirror::Class* s, mirror::Class* t) {
917  DCHECK(!s->IsPrimitive()) << PrettyClass(s);
918  DCHECK(!t->IsPrimitive()) << PrettyClass(t);
919  if (s == t) {
920    return s;
921  } else if (s->IsAssignableFrom(t)) {
922    return s;
923  } else if (t->IsAssignableFrom(s)) {
924    return t;
925  } else if (s->IsArrayClass() && t->IsArrayClass()) {
926    mirror::Class* s_ct = s->GetComponentType();
927    mirror::Class* t_ct = t->GetComponentType();
928    if (s_ct->IsPrimitive() || t_ct->IsPrimitive()) {
929      // Given the types aren't the same, if either array is of primitive types then the only
930      // common parent is java.lang.Object
931      mirror::Class* result = s->GetSuperClass();  // short-cut to java.lang.Object
932      DCHECK(result->IsObjectClass());
933      return result;
934    }
935    mirror::Class* common_elem = ClassJoin(s_ct, t_ct);
936    ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
937    mirror::ClassLoader* class_loader = s->GetClassLoader();
938    std::string descriptor("[");
939    descriptor += ClassHelper(common_elem).GetDescriptor();
940    mirror::Class* array_class = class_linker->FindClass(descriptor.c_str(), class_loader);
941    DCHECK(array_class != NULL);
942    return array_class;
943  } else {
944    size_t s_depth = s->Depth();
945    size_t t_depth = t->Depth();
946    // Get s and t to the same depth in the hierarchy
947    if (s_depth > t_depth) {
948      while (s_depth > t_depth) {
949        s = s->GetSuperClass();
950        s_depth--;
951      }
952    } else {
953      while (t_depth > s_depth) {
954        t = t->GetSuperClass();
955        t_depth--;
956      }
957    }
958    // Go up the hierarchy until we get to the common parent
959    while (s != t) {
960      s = s->GetSuperClass();
961      t = t->GetSuperClass();
962    }
963    return s;
964  }
965}
966
967void RegType::CheckInvariants() const {
968  if (IsConstant() || IsConstantLo() || IsConstantHi()) {
969    CHECK(descriptor_.empty()) << *this;
970    CHECK(klass_ == NULL) << *this;
971  }
972  if (klass_ != NULL) {
973    CHECK(!descriptor_.empty()) << *this;
974  }
975}
976
977void UninitializedThisReferenceType::CheckInvariants() const {
978  CHECK_EQ(GetAllocationPc(), 0U) << *this;
979}
980
981void UnresolvedUninitializedThisRefType::CheckInvariants() const {
982  CHECK_EQ(GetAllocationPc(), 0U) << *this;
983  CHECK(!descriptor_.empty()) << *this;
984  CHECK(klass_ == NULL) << *this;
985}
986
987void UnresolvedUninitializedRefType::CheckInvariants() const {
988  CHECK(!descriptor_.empty()) << *this;
989  CHECK(klass_ == NULL) << *this;
990}
991
992void UnresolvedMergedType::CheckInvariants() const {
993  // Unresolved merged types: merged types should be defined.
994  CHECK(descriptor_.empty()) << *this;
995  CHECK(klass_ == NULL) << *this;
996  CHECK_NE(merged_types_.first, 0U) << *this;
997  CHECK_NE(merged_types_.second, 0U) << *this;
998}
999
1000void UnresolvedReferenceType::CheckInvariants() const {
1001  CHECK(!descriptor_.empty()) << *this;
1002  CHECK(klass_ == NULL) << *this;
1003}
1004
1005void UnresolvedSuperClass::CheckInvariants() const {
1006  // Unresolved merged types: merged types should be defined.
1007  CHECK(descriptor_.empty()) << *this;
1008  CHECK(klass_ == NULL) << *this;
1009  CHECK_NE(unresolved_child_id_, 0U) << *this;
1010}
1011
1012std::ostream& operator<<(std::ostream& os, const RegType& rhs) {
1013  os << rhs.Dump();
1014  return os;
1015}
1016
1017}  // namespace verifier
1018}  // namespace art
1019