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