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