1/*
2 * Copyright (C) 2017 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 "subtype_check.h"
18
19#include "gtest/gtest.h"
20#include "android-base/logging.h"
21
22namespace art {
23
24constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
25constexpr size_t BitString::kCapacity;
26
27struct MockClass {
28  explicit MockClass(MockClass* parent, size_t x = 0, size_t y = 0) {
29    parent_ = parent;
30    memset(&subtype_check_info_and_status_, 0u, sizeof(subtype_check_info_and_status_));
31
32    // Start the numbering at '1' to match the bitstring numbering.
33    // A bitstring numbering never starts at '0' which just means 'no value'.
34    x_ = 1;
35    if (parent_ != nullptr) {
36      if (parent_->GetMaxChild() != nullptr) {
37        x_ = parent_->GetMaxChild()->x_ + 1u;
38      }
39
40      parent_->children_.push_back(this);
41      if (parent_->path_to_root_ != "") {
42        path_to_root_ = parent->path_to_root_ + ",";
43      }
44      path_to_root_ += std::to_string(x_);
45    } else {
46      path_to_root_ = "";  // root has no path.
47    }
48    y_ = y;
49    UNUSED(x);
50  }
51
52  MockClass() : MockClass(nullptr) {
53  }
54
55  ///////////////////////////////////////////////////////////////
56  // Implementation of the SubtypeCheck::KlassT static interface.
57  ///////////////////////////////////////////////////////////////
58
59  MockClass* GetSuperClass() const {
60    return parent_;
61  }
62
63  bool HasSuperClass() const {
64    return GetSuperClass() != nullptr;
65  }
66
67  size_t Depth() const {
68    if (parent_ == nullptr) {
69      return 0u;
70    } else {
71      return parent_->Depth() + 1u;
72    }
73  }
74
75  std::string PrettyClass() const
76      REQUIRES_SHARED(Locks::mutator_lock_) {
77    return path_to_root_;
78  }
79
80  int32_t GetField32Volatile(art::MemberOffset offset = art::MemberOffset(0u)) const
81      REQUIRES_SHARED(Locks::mutator_lock_) {
82    UNUSED(offset);
83    int32_t field_32 = 0;
84    memcpy(&field_32, &subtype_check_info_and_status_, sizeof(int32_t));
85    return field_32;
86  }
87
88  template <bool kTransactionActive>
89  bool CasFieldWeakSequentiallyConsistent32(art::MemberOffset offset,
90                                            int32_t old_value,
91                                            int32_t new_value)
92      REQUIRES_SHARED(Locks::mutator_lock_) {
93    UNUSED(offset);
94    if (old_value == GetField32Volatile(offset)) {
95      memcpy(&subtype_check_info_and_status_, &new_value, sizeof(int32_t));
96      return true;
97    }
98    return false;
99  }
100
101  MemberOffset StatusOffset() const {
102    return MemberOffset(0);  // Doesn't matter. We ignore offset.
103  }
104
105  ///////////////////////////////////////////////////////////////
106  // Convenience functions to make the testing easier
107  ///////////////////////////////////////////////////////////////
108
109  size_t GetNumberOfChildren() const {
110    return children_.size();
111  }
112
113  MockClass* GetParent() const {
114    return parent_;
115  }
116
117  MockClass* GetMaxChild() const {
118    if (GetNumberOfChildren() > 0u) {
119      return GetChild(GetNumberOfChildren() - 1);
120    }
121    return nullptr;
122  }
123
124  MockClass* GetChild(size_t idx) const {
125    if (idx >= GetNumberOfChildren()) {
126      return nullptr;
127    }
128    return children_[idx];
129  }
130
131  // Traverse the sibling at "X" at each level.
132  // Once we get to level==depth, return yourself.
133  MockClass* FindChildAt(size_t x, size_t depth) {
134    if (Depth() == depth) {
135      return this;
136    } else if (GetNumberOfChildren() > 0) {
137      return GetChild(x)->FindChildAt(x, depth);
138    }
139    return nullptr;
140  }
141
142  template <typename T>
143  MockClass* Visit(T visitor, bool recursive = true) {
144    if (!visitor(this)) {
145      return this;
146    }
147
148    if (!recursive) {
149      return this;
150    }
151
152    for (MockClass* child : children_) {
153      MockClass* visit_res = child->Visit(visitor);
154      if (visit_res != nullptr) {
155        return visit_res;
156      }
157    }
158
159    return nullptr;
160  }
161
162  size_t GetX() const {
163    return x_;
164  }
165
166  bool SlowIsSubtypeOf(const MockClass* target) const {
167    DCHECK(target != nullptr);
168    const MockClass* kls = this;
169    while (kls != nullptr) {
170      if (kls == target) {
171        return true;
172      }
173      kls = kls->GetSuperClass();
174    }
175
176    return false;
177  }
178
179  std::string ToDotGraph() const {
180    std::stringstream ss;
181    ss << std::endl;
182    ss << "digraph MockClass {" << std::endl;
183    ss << "    node [fontname=\"Arial\"];" << std::endl;
184    ToDotGraphImpl(ss);
185    ss << "}" << std::endl;
186    return ss.str();
187  }
188
189  void ToDotGraphImpl(std::ostream& os) const {
190    for (MockClass* child : children_) {
191      os << "    '" << path_to_root_ << "' -> '" << child->path_to_root_ << "';" << std::endl;
192      child->ToDotGraphImpl(os);
193    }
194  }
195
196  std::vector<MockClass*> children_;
197  MockClass* parent_;
198  SubtypeCheckBitsAndStatus subtype_check_info_and_status_;
199  size_t x_;
200  size_t y_;
201  std::string path_to_root_;
202};
203
204std::ostream& operator<<(std::ostream& os, const MockClass& kls) {
205  SubtypeCheckBits iod = kls.subtype_check_info_and_status_.subtype_check_info_;
206  os << "MClass{D:" << kls.Depth() << ",W:" << kls.x_
207     << ", OF:"
208     << (iod.overflow_ ? "true" : "false")
209     << ", bitstring: " << iod.bitstring_
210     << ", mock_path: " << kls.path_to_root_
211     << "}";
212  return os;
213}
214
215struct MockSubtypeCheck {
216  using SC = SubtypeCheck<MockClass*>;
217
218  static MockSubtypeCheck Lookup(MockClass* klass) {
219    MockSubtypeCheck mock;
220    mock.klass_ = klass;
221    return mock;
222  }
223
224  // Convenience functions to avoid using statics everywhere.
225  //    static(class, args...) -> instance.method(args...)
226  SubtypeCheckInfo::State EnsureInitialized()
227      REQUIRES(Locks::subtype_check_lock_)
228      REQUIRES_SHARED(Locks::mutator_lock_) {
229    return SC::EnsureInitialized(klass_);
230  }
231
232  SubtypeCheckInfo::State EnsureAssigned()
233      REQUIRES(Locks::subtype_check_lock_)
234      REQUIRES_SHARED(Locks::mutator_lock_) {
235    return SC::EnsureAssigned(klass_);
236  }
237
238  SubtypeCheckInfo::State ForceUninitialize()
239    REQUIRES(Locks::subtype_check_lock_)
240    REQUIRES_SHARED(Locks::mutator_lock_) {
241    return SC::ForceUninitialize(klass_);
242  }
243
244  BitString::StorageType GetEncodedPathToRootForSource() const
245      REQUIRES(Locks::subtype_check_lock_)
246      REQUIRES_SHARED(Locks::mutator_lock_) {
247    return SC::GetEncodedPathToRootForSource(klass_);
248  }
249
250  BitString::StorageType GetEncodedPathToRootForTarget() const
251      REQUIRES(Locks::subtype_check_lock_)
252      REQUIRES_SHARED(Locks::mutator_lock_) {
253    return SC::GetEncodedPathToRootForTarget(klass_);
254  }
255
256  BitString::StorageType GetEncodedPathToRootMask() const
257      REQUIRES(Locks::subtype_check_lock_)
258      REQUIRES_SHARED(Locks::mutator_lock_) {
259    return SC::GetEncodedPathToRootMask(klass_);
260  }
261
262  SubtypeCheckInfo::Result IsSubtypeOf(const MockSubtypeCheck& target)
263      REQUIRES_SHARED(Locks::mutator_lock_) {
264    return SC::IsSubtypeOf(klass_, target.klass_);
265  }
266
267  friend std::ostream& operator<<(std::ostream& os, const MockSubtypeCheck& tree)
268      NO_THREAD_SAFETY_ANALYSIS {
269    os << "(MockSubtypeCheck io:";
270    SC::Dump(tree.klass_, os);
271    os << ", class: " << tree.klass_->PrettyClass() << ")";
272    return os;
273  }
274
275  // Additional convenience functions.
276  SubtypeCheckInfo::State GetState() const
277      REQUIRES(Locks::subtype_check_lock_)
278      REQUIRES_SHARED(Locks::mutator_lock_) {
279    return SC::GetSubtypeCheckInfo(klass_).GetState();
280  }
281
282  MockClass& GetClass() const {
283    return *klass_;
284  }
285
286 private:
287  MockClass* klass_;
288};
289
290struct MockScopedLockSubtypeCheck {
291  MockScopedLockSubtypeCheck() ACQUIRE(*Locks::subtype_check_lock_) {}
292  ~MockScopedLockSubtypeCheck() RELEASE(*Locks::subtype_check_lock_) {}
293};
294
295struct MockScopedLockMutator {
296  MockScopedLockMutator() ACQUIRE_SHARED(*Locks::mutator_lock_) {}
297  ~MockScopedLockMutator() RELEASE_SHARED(*Locks::mutator_lock_) {}
298};
299
300struct SubtypeCheckTest : public ::testing::Test {
301 protected:
302  virtual void SetUp() {
303    android::base::InitLogging(/*argv*/nullptr);
304
305    CreateRootedTree(BitString::kCapacity + 2u, BitString::kCapacity + 2u);
306  }
307
308  virtual void TearDown() {
309  }
310
311  void CreateRootedTree(size_t width, size_t height) {
312    all_classes_.clear();
313    root_ = CreateClassFor(/*parent*/nullptr, /*x*/0, /*y*/0);
314    CreateTreeFor(root_, /*width*/width, /*depth*/height);
315  }
316
317  MockClass* CreateClassFor(MockClass* parent, size_t x, size_t y) {
318    MockClass* kls = new MockClass(parent, x, y);
319    all_classes_.push_back(std::unique_ptr<MockClass>(kls));
320    return kls;
321  }
322
323  void CreateTreeFor(MockClass* parent, size_t width, size_t levels) {
324    DCHECK(parent != nullptr);
325    if (levels == 0) {
326      return;
327    }
328
329    for (size_t i = 0; i < width; ++i) {
330      MockClass* child = CreateClassFor(parent, i, parent->y_ + 1);
331      CreateTreeFor(child, width, levels - 1);
332    }
333  }
334
335  MockClass* root_ = nullptr;
336  std::vector<std::unique_ptr<MockClass>> all_classes_;
337};
338
339TEST_F(SubtypeCheckTest, LookupAllChildren) {
340  MockScopedLockSubtypeCheck lock_a;
341  MockScopedLockMutator lock_b;
342  using SCTree = MockSubtypeCheck;
343
344  root_->Visit([&](MockClass* kls) {
345    MockScopedLockSubtypeCheck lock_a;
346    MockScopedLockMutator lock_b;
347
348    EXPECT_EQ(SubtypeCheckInfo::kUninitialized, SCTree::Lookup(kls).GetState());
349    return true;  // Keep visiting.
350  });
351}
352
353TEST_F(SubtypeCheckTest, LookupRoot) {
354  MockScopedLockSubtypeCheck lock_a;
355  MockScopedLockMutator lock_b;
356  using SCTree = MockSubtypeCheck;
357
358  SCTree root = SCTree::Lookup(root_);
359  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
360  EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, root.IsSubtypeOf(root)) << root;
361}
362
363TEST_F(SubtypeCheckTest, EnsureInitializedFirstLevel) {
364  MockScopedLockSubtypeCheck lock_a;
365  MockScopedLockMutator lock_b;
366  using SCTree = MockSubtypeCheck;
367
368  SCTree root = SCTree::Lookup(root_);
369  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
370
371  ASSERT_LT(0u, root_->GetNumberOfChildren());
372
373  // Initialize root's children only.
374  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
375    MockClass* child = root_->GetChild(i);
376    SCTree child_tree = SCTree::Lookup(child);
377    // Before: all unknown.
378    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
379    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
380    // Transition.
381    EXPECT_EQ(SubtypeCheckInfo::kInitialized, child_tree.EnsureInitialized());
382    // After: "src instanceof target" known, but "target instanceof src" unknown.
383    EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
384    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
385  }
386}
387
388TEST_F(SubtypeCheckTest, EnsureAssignedFirstLevel) {
389  MockScopedLockSubtypeCheck lock_a;
390  MockScopedLockMutator lock_b;
391  using SCTree = MockSubtypeCheck;
392
393  SCTree root = SCTree::Lookup(root_);
394  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
395
396  ASSERT_LT(0u, root_->GetNumberOfChildren());
397
398  // Initialize root's children only.
399  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
400    MockClass* child = root_->GetChild(i);
401    SCTree child_tree = SCTree::Lookup(child);
402    // Before: all unknown.
403    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
404    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
405    // Transition.
406    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.EnsureAssigned());
407    // After: "src instanceof target" known, and "target instanceof src" known.
408    EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
409    EXPECT_EQ(SubtypeCheckInfo::kNotSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
410  }
411}
412
413TEST_F(SubtypeCheckTest, EnsureInitializedSecondLevelWithPreassign) {
414  MockScopedLockSubtypeCheck lock_a;
415  MockScopedLockMutator lock_b;
416  using SCTree = MockSubtypeCheck;
417
418  SCTree root = SCTree::Lookup(root_);
419  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
420
421  ASSERT_LT(0u, root_->GetNumberOfChildren());
422
423  // Initialize root's children.
424  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
425    MockClass* child = root_->GetChild(i);
426    SCTree child_tree = SCTree::Lookup(child);
427
428    ASSERT_EQ(1u, child->Depth());
429
430    EXPECT_EQ(SubtypeCheckInfo::kInitialized, child_tree.EnsureInitialized()) << *child;
431    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.EnsureAssigned())
432              << *child << ", root:" << *root_;
433    for (size_t j = 0; j < child->GetNumberOfChildren(); ++j) {
434      MockClass* child2 = child->GetChild(j);
435      ASSERT_EQ(2u, child2->Depth());
436      SCTree child2_tree = SCTree::Lookup(child2);
437
438      // Before: all unknown.
439      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
440      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
441                << child2_tree;
442      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(root))
443                << child2_tree;
444      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(child_tree))
445                << child2_tree;
446
447      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, child2_tree.GetState()) << *child2;
448      EXPECT_EQ(SubtypeCheckInfo::kInitialized, child2_tree.EnsureInitialized()) << *child2;
449
450      // After: src=child2_tree is known, otherwise unknown.
451      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
452      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
453                << child2_tree;
454      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
455      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(child_tree)) << child2_tree;
456    }
457
458    // The child is "assigned" as a side-effect of initializing sub-children.
459    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.GetState());
460  }
461}
462
463TEST_F(SubtypeCheckTest, EnsureInitializedSecondLevelDontPreassign) {
464  MockScopedLockSubtypeCheck lock_a;
465  MockScopedLockMutator lock_b;
466  using SCTree = MockSubtypeCheck;
467
468  SCTree root = SCTree::Lookup(root_);
469  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
470
471  ASSERT_LT(0u, root_->GetNumberOfChildren());
472
473  // Initialize root's children only.
474  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
475    MockClass* child = root_->GetChild(i);
476    SCTree child_tree = SCTree::Lookup(child);
477
478    ASSERT_EQ(1u, child->Depth());
479
480    for (size_t j = 0; j < child->GetNumberOfChildren(); ++j) {
481      MockClass* child2 = child->GetChild(j);
482      ASSERT_EQ(2u, child2->Depth());
483      SCTree child2_tree = SCTree::Lookup(child2);
484      // Before: all unknown.
485      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
486      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
487                << child2_tree;
488      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
489      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(child_tree))
490                << child2_tree;
491      // Transition.
492      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, child2_tree.GetState()) << *child2;
493      EXPECT_EQ(SubtypeCheckInfo::kInitialized, child2_tree.EnsureInitialized()) << *child2;
494      // After: src=child2_tree is known, otherwise unknown.
495      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
496      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
497                << child2_tree;
498      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
499      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(child_tree)) << child2_tree;
500    }
501
502    // The child is "assigned" as a side-effect of initializing sub-children.
503    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.GetState());
504  }
505}
506
507void ApplyTransition(MockSubtypeCheck sc_tree,
508                     SubtypeCheckInfo::State transition,
509                     SubtypeCheckInfo::State expected) {
510  MockScopedLockSubtypeCheck lock_a;
511  MockScopedLockMutator lock_b;
512
513  EXPECT_EQ(SubtypeCheckInfo::kUninitialized, sc_tree.GetState()) << sc_tree.GetClass();
514
515  if (transition == SubtypeCheckInfo::kUninitialized) {
516    EXPECT_EQ(expected, sc_tree.ForceUninitialize()) << sc_tree.GetClass();
517  } else if (transition == SubtypeCheckInfo::kInitialized) {
518    EXPECT_EQ(expected, sc_tree.EnsureInitialized()) << sc_tree.GetClass();
519  } else if (transition == SubtypeCheckInfo::kAssigned) {
520    EXPECT_EQ(expected, sc_tree.EnsureAssigned()) << sc_tree.GetClass();
521  }
522}
523
524enum MockSubtypeOfTransition {
525  kNone,
526  kUninitialized,
527  kInitialized,
528  kAssigned,
529};
530
531std::ostream& operator<<(std::ostream& os, const MockSubtypeOfTransition& transition) {
532  if (transition == MockSubtypeOfTransition::kUninitialized) {
533    os << "kUninitialized";
534  } else if (transition == MockSubtypeOfTransition::kInitialized) {
535    os << "kInitialized";
536  } else if (transition == MockSubtypeOfTransition::kAssigned) {
537    os << "kAssigned";
538  } else {
539    os << "kNone";
540  }
541  return os;
542}
543
544SubtypeCheckInfo::State ApplyTransition(MockSubtypeCheck sc_tree,
545                                        MockSubtypeOfTransition transition) {
546  MockScopedLockSubtypeCheck lock_a;
547  MockScopedLockMutator lock_b;
548
549  if (transition ==  MockSubtypeOfTransition::kUninitialized) {
550    return sc_tree.ForceUninitialize();
551  } else if (transition == MockSubtypeOfTransition::kInitialized) {
552    return sc_tree.EnsureInitialized();
553  } else if (transition == MockSubtypeOfTransition::kAssigned) {
554    return sc_tree.EnsureAssigned();
555  }
556
557  return sc_tree.GetState();
558}
559
560enum {
561  kBeforeTransition = 0,
562  kAfterTransition = 1,
563  kAfterChildren = 2,
564};
565
566const char* StringifyTransition(int x) {
567  if (x == kBeforeTransition) {
568    return "kBeforeTransition";
569  } else if (x == kAfterTransition) {
570    return "kAfterTransition";
571  } else if (x == kAfterChildren) {
572    return "kAfterChildren";
573  }
574
575  return "<<Unknown>>";
576}
577
578struct TransitionHistory {
579  void Record(int transition_label, MockClass* kls) {
580    ss_ << "<<<" << StringifyTransition(transition_label) << ">>>";
581    ss_ << "{Self}: " << *kls;
582
583    if (kls->HasSuperClass()) {
584      ss_ << "{Parent}: " << *(kls->GetSuperClass());
585    }
586    ss_ << "================== ";
587  }
588
589  friend std::ostream& operator<<(std::ostream& os, const TransitionHistory& t) {
590    os << t.ss_.str();
591    return os;
592  }
593
594  std::stringstream ss_;
595};
596
597template <typename T, typename T2>
598void EnsureStateChangedTestRecursiveGeneric(MockClass* klass,
599                                            size_t cur_depth,
600                                            size_t total_depth,
601                                            T2 transition_func,
602                                            T expect_checks) {
603  MockScopedLockSubtypeCheck lock_a;
604  MockScopedLockMutator lock_b;
605  using SCTree = MockSubtypeCheck;
606
607  SCTree sc_tree = SCTree::Lookup(klass);
608  MockSubtypeOfTransition requested_transition = transition_func(klass);
609
610  // FIXME: need to print before(self, parent) and after(self, parent)
611  // to make any sense of what's going on.
612
613  auto do_expect_checks = [&](int transition_label, TransitionHistory& transition_details) {
614    MockScopedLockSubtypeCheck lock_a;
615    MockScopedLockMutator lock_b;
616
617    transition_details.Record(transition_label, klass);
618
619    SCOPED_TRACE(transition_details);
620    ASSERT_EQ(cur_depth, klass->Depth());
621
622    ASSERT_NO_FATAL_FAILURE(expect_checks(klass,
623                                          transition_label,
624                                          sc_tree.GetState(),
625                                          requested_transition));
626  };
627
628  TransitionHistory transition_history;
629  do_expect_checks(kBeforeTransition, transition_history);
630  SubtypeCheckInfo::State state = ApplyTransition(sc_tree, requested_transition);
631  UNUSED(state);
632  do_expect_checks(kAfterTransition, transition_history);
633
634  if (total_depth == cur_depth) {
635    return;
636  }
637
638  // Initialize root's children only.
639  for (size_t i = 0; i < klass->GetNumberOfChildren(); ++i) {
640    MockClass* child = klass->GetChild(i);
641    EnsureStateChangedTestRecursiveGeneric(child,
642                                           cur_depth + 1u,
643                                           total_depth,
644                                           transition_func,
645                                           expect_checks);
646  }
647
648  do_expect_checks(kAfterChildren, transition_history);
649}
650
651void EnsureStateChangedTestRecursive(
652    MockClass* klass,
653    size_t cur_depth,
654    size_t total_depth,
655    std::vector<std::pair<SubtypeCheckInfo::State, SubtypeCheckInfo::State>> transitions) {
656  MockScopedLockSubtypeCheck lock_a;
657  MockScopedLockMutator lock_b;
658  using SCTree = MockSubtypeCheck;
659
660  ASSERT_EQ(cur_depth, klass->Depth());
661  ApplyTransition(SCTree::Lookup(klass), transitions[cur_depth].first, transitions[cur_depth].second);
662
663  if (total_depth == cur_depth + 1) {
664    return;
665  }
666
667  // Initialize root's children only.
668  for (size_t i = 0; i < klass->GetNumberOfChildren(); ++i) {
669    MockClass* child = klass->GetChild(i);
670    EnsureStateChangedTestRecursive(child, cur_depth + 1u, total_depth, transitions);
671  }
672}
673
674void EnsureStateChangedTest(
675    MockClass* root,
676    size_t depth,
677    std::vector<std::pair<SubtypeCheckInfo::State, SubtypeCheckInfo::State>> transitions) {
678  ASSERT_EQ(depth, transitions.size());
679
680  EnsureStateChangedTestRecursive(root, /*cur_depth*/0u, depth, transitions);
681}
682
683TEST_F(SubtypeCheckTest, EnsureInitialized_NoOverflow) {
684  auto transitions = [](MockClass* kls) {
685    UNUSED(kls);
686    return MockSubtypeOfTransition::kInitialized;
687  };
688
689  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity;
690  auto expected = [=](MockClass* kls,
691                      int expect_when,
692                      SubtypeCheckInfo::State actual_state,
693                      MockSubtypeOfTransition transition) {
694    if (expect_when == kBeforeTransition) {
695      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, actual_state);
696      return;
697    }
698
699    if (expect_when == kAfterTransition) {
700      // After explicit transition has been completed.
701      switch (kls->Depth()) {
702      case 0:
703        if (transition >= MockSubtypeOfTransition::kInitialized) {
704          EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
705        }
706        break;
707      default:
708        if (transition >= MockSubtypeOfTransition::kInitialized) {
709          if (transition == MockSubtypeOfTransition::kInitialized) {
710            EXPECT_EQ(SubtypeCheckInfo::kInitialized, actual_state);
711          } else if (transition == MockSubtypeOfTransition::kAssigned) {
712            EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
713          }
714        }
715        break;
716      }
717    }
718
719    if (expect_when == kAfterChildren) {
720      if (transition >= MockSubtypeOfTransition::kInitialized) {
721        ASSERT_NE(kls->Depth(), kMaxDepthForThisTest);
722        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
723      }
724    }
725  };
726
727  // Initialize every level 0-3.
728  // Intermediate levels become "assigned", max levels become initialized.
729  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
730
731  auto transitions_uninitialize = [](MockClass* kls) {
732    UNUSED(kls);
733    return MockSubtypeOfTransition::kUninitialized;
734  };
735
736  auto expected_uninitialize = [](MockClass* kls,
737                                  int expect_when,
738                                  SubtypeCheckInfo::State actual_state,
739                                  MockSubtypeOfTransition transition) {
740    UNUSED(kls);
741    UNUSED(transition);
742    if (expect_when >= kAfterTransition) {
743      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, actual_state);
744    }
745  };
746
747  // Uninitialize the entire tree after it was assigned.
748  EnsureStateChangedTestRecursiveGeneric(root_,
749                                         0u,
750                                         kMaxDepthForThisTest,
751                                         transitions_uninitialize,
752                                         expected_uninitialize);
753}
754
755TEST_F(SubtypeCheckTest, EnsureAssigned_TooDeep) {
756  auto transitions = [](MockClass* kls) {
757    UNUSED(kls);
758    return MockSubtypeOfTransition::kAssigned;
759  };
760
761  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity + 1u;
762  auto expected = [=](MockClass* kls,
763                      int expect_when,
764                      SubtypeCheckInfo::State actual_state,
765                      MockSubtypeOfTransition transition) {
766    UNUSED(transition);
767    if (expect_when == kAfterTransition) {
768      if (kls->Depth() > BitString::kCapacity) {
769        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
770      }
771    }
772  };
773
774  // Assign every level 0-4.
775  // We cannot assign 4th level, so it will overflow instead.
776  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
777}
778
779TEST_F(SubtypeCheckTest, EnsureAssigned_TooDeep_OfTooDeep) {
780  auto transitions = [](MockClass* kls) {
781    UNUSED(kls);
782    return MockSubtypeOfTransition::kAssigned;
783  };
784
785  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity + 2u;
786  auto expected = [=](MockClass* kls,
787                      int expect_when,
788                      SubtypeCheckInfo::State actual_state,
789                      MockSubtypeOfTransition transition) {
790    UNUSED(transition);
791    if (expect_when == kAfterTransition) {
792      if (kls->Depth() > BitString::kCapacity) {
793        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
794      }
795    }
796  };
797
798  // Assign every level 0-5.
799  // We cannot assign 4th level, so it will overflow instead.
800  // In addition, level 5th cannot be assigned (parent is overflowed), so it will also fail.
801  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
802}
803
804constexpr size_t MaxWidthCutOff(size_t depth) {
805  if (depth == 0) {
806    return 1;
807  }
808  if (depth > BitString::kCapacity) {
809    return std::numeric_limits<size_t>::max();
810  }
811  return MaxInt<size_t>(BitString::kBitSizeAtPosition[depth - 1]);
812}
813
814// Either itself is too wide, or any of the parents were too wide.
815bool IsTooWide(MockClass* kls) {
816  if (kls == nullptr || kls->Depth() == 0u) {
817    // Root is never too wide.
818    return false;
819  } else {
820    if (kls->GetX() >= MaxWidthCutOff(kls->Depth())) {
821      return true;
822    }
823  }
824  return IsTooWide(kls->GetParent());
825}
826
827// Either itself is too deep, or any of the parents were too deep.
828bool IsTooDeep(MockClass* kls) {
829  if (kls == nullptr || kls->Depth() == 0u) {
830    // Root is never too deep.
831    return false;
832  } else {
833    if (kls->Depth() > BitString::kCapacity) {
834      return true;
835    }
836  }
837  return false;
838}
839
840TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide) {
841  auto transitions = [](MockClass* kls) {
842    UNUSED(kls);
843    return MockSubtypeOfTransition::kAssigned;
844  };
845
846  // Pick the 2nd level because has the most narrow # of bits.
847  constexpr size_t kTargetDepth = 2;
848  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);
849
850  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
851  auto expected = [=](MockClass* kls,
852                      int expect_when,
853                      SubtypeCheckInfo::State actual_state,
854                      MockSubtypeOfTransition transition) {
855    UNUSED(transition);
856    // Note: purposefuly ignore the too-deep children in the premade tree.
857    if (expect_when == kAfterTransition && kls->Depth() <= BitString::kCapacity) {
858      if (IsTooWide(kls)) {
859        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
860      } else {
861        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
862      }
863    }
864  };
865
866  {
867    // Create too-wide siblings at the kTargetDepth level.
868    MockClass* child = root_->FindChildAt(/*x*/0, kTargetDepth - 1u);
869    CreateTreeFor(child, kMaxWidthCutOff*2, /*depth*/1);
870    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren());
871    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
872    // Leave the rest of the tree as the default.
873  }
874
875  // Try to assign every level
876  // It will fail once it gets to the "too wide" siblings and cause overflows.
877  EnsureStateChangedTestRecursiveGeneric(root_,
878                                         0u,
879                                         kMaxDepthForThisTest,
880                                         transitions,
881                                         expected);
882}
883
884TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide_TooWide) {
885  auto transitions = [](MockClass* kls) {
886    UNUSED(kls);
887    return MockSubtypeOfTransition::kAssigned;
888  };
889
890  // Pick the 2nd level because has the most narrow # of bits.
891  constexpr size_t kTargetDepth = 2;
892  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);
893  constexpr size_t kMaxWidthCutOffSub = MaxWidthCutOff(kTargetDepth+1u);
894
895  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
896  auto expected = [=](MockClass* kls,
897                      int expect_when,
898                      SubtypeCheckInfo::State actual_state,
899                      MockSubtypeOfTransition transition) {
900    UNUSED(transition);
901    // Note: purposefuly ignore the too-deep children in the premade tree.
902    if (expect_when == kAfterTransition && kls->Depth() <= BitString::kCapacity) {
903      if (IsTooWide(kls)) {
904        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
905      } else {
906        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
907      }
908    }
909  };
910
911  {
912    // Create too-wide siblings at the kTargetDepth level.
913    MockClass* child = root_->FindChildAt(/*x*/0, kTargetDepth - 1);
914    CreateTreeFor(child, kMaxWidthCutOff*2, /*depth*/1);
915    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren()) << *child;
916    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
917    // Leave the rest of the tree as the default.
918
919    // Create too-wide children for a too-wide parent.
920    MockClass* child_subchild = child->FindChildAt(/*x*/0, kTargetDepth);
921    CreateTreeFor(child_subchild, kMaxWidthCutOffSub*2, /*depth*/1);
922    ASSERT_LE(kMaxWidthCutOffSub*2, child_subchild->GetNumberOfChildren()) << *child_subchild;
923    ASSERT_TRUE(IsTooWide(child_subchild->GetMaxChild())) << *(child_subchild->GetMaxChild());
924  }
925
926  // Try to assign every level
927  // It will fail once it gets to the "too wide" siblings and cause overflows.
928  // Furthermore, assigning any subtree whose ancestor is too wide will also fail.
929  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
930}
931
932void EnsureSubtypeOfCorrect(MockClass* a, MockClass* b) {
933  MockScopedLockSubtypeCheck lock_a;
934  MockScopedLockMutator lock_b;
935  using SCTree = MockSubtypeCheck;
936
937  auto IsAssigned = [](SCTree& tree) {
938    MockScopedLockSubtypeCheck lock_a;
939    MockScopedLockMutator lock_b;
940    // This assumes that MockClass is always called with EnsureAssigned.
941    EXPECT_NE(SubtypeCheckInfo::kInitialized, tree.GetState());
942    EXPECT_NE(SubtypeCheckInfo::kUninitialized, tree.GetState());
943    // Use our own test checks, so we are actually testing different logic than the impl.
944    return !(IsTooDeep(&tree.GetClass()) || IsTooWide(&tree.GetClass()));
945  };
946
947  SCTree src_tree = SCTree::Lookup(a);
948  SCTree target_tree = SCTree::Lookup(b);
949
950  SCOPED_TRACE("class A");
951  SCOPED_TRACE(*a);
952  SCOPED_TRACE("class B");
953  SCOPED_TRACE(*b);
954
955  SubtypeCheckInfo::Result slow_result =
956      a->SlowIsSubtypeOf(b) ? SubtypeCheckInfo::kSubtypeOf : SubtypeCheckInfo::kNotSubtypeOf;
957  SubtypeCheckInfo::Result fast_result = src_tree.IsSubtypeOf(target_tree);
958
959  // Target must be Assigned for this check to succeed.
960  // Source is either Overflowed | Assigned (in this case).
961
962  if (IsAssigned(src_tree) && IsAssigned(target_tree)) {
963    ASSERT_EQ(slow_result, fast_result);
964  } else if (IsAssigned(src_tree)) {
965    // A is assigned. B is >= initialized.
966    ASSERT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, fast_result);
967  } else if (IsAssigned(target_tree)) {
968    // B is assigned. A is >= initialized.
969    ASSERT_EQ(slow_result, fast_result);
970  } else {
971    // Neither A,B are assigned.
972    ASSERT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, fast_result);
973  }
974
975  // Use asserts,  not expects to immediately fail.
976  // Otherwise the entire tree (very large) could potentially be broken.
977}
978
979void EnsureSubtypeOfRecursive(MockClass* kls_root) {
980  MockScopedLockMutator mutator_lock_fake_;
981
982  auto visit_func = [&](MockClass* kls) {
983    kls->Visit([&](MockClass* inner_class) {
984      EnsureSubtypeOfCorrect(kls, inner_class);
985      EnsureSubtypeOfCorrect(inner_class, kls);
986
987      if (::testing::Test::HasFatalFailure()) {
988        return false;
989      }
990
991      return true;  // Keep visiting.
992    });
993
994    if (::testing::Test::HasFatalFailure()) {
995        return false;
996    }
997
998    return true;  // Keep visiting.
999  };
1000
1001  ASSERT_NO_FATAL_FAILURE(kls_root->Visit(visit_func));
1002}
1003
1004TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide_TooDeep) {
1005  auto transitions = [](MockClass* kls) {
1006    UNUSED(kls);
1007    return MockSubtypeOfTransition::kAssigned;
1008  };
1009
1010  // Pick the 2nd level because has the most narrow # of bits.
1011  constexpr size_t kTargetDepth = 2;
1012  constexpr size_t kTooDeepTargetDepth = BitString::kCapacity + 1;
1013  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);
1014
1015  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
1016  auto expected = [=](MockClass* kls,
1017                      int expect_when,
1018                      SubtypeCheckInfo::State actual_state,
1019                      MockSubtypeOfTransition transition) {
1020    UNUSED(transition);
1021    if (expect_when == kAfterTransition) {
1022      if (IsTooDeep(kls)) {
1023        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
1024      } else if (IsTooWide(kls)) {
1025        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
1026      } else {
1027        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
1028      }
1029    }
1030  };
1031
1032  {
1033    // Create too-wide siblings at the kTargetDepth level.
1034    MockClass* child = root_->FindChildAt(/*x*/0, kTargetDepth - 1u);
1035    CreateTreeFor(child, kMaxWidthCutOff*2, /*depth*/1);
1036    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren());
1037    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
1038    // Leave the rest of the tree as the default.
1039
1040    // Create too-deep children for a too-wide parent.
1041    MockClass* child_subchild = child->GetMaxChild();
1042    ASSERT_TRUE(child_subchild != nullptr);
1043    ASSERT_EQ(0u, child_subchild->GetNumberOfChildren()) << *child_subchild;
1044    CreateTreeFor(child_subchild, /*width*/1, /*levels*/kTooDeepTargetDepth);
1045    MockClass* too_deep_child = child_subchild->FindChildAt(0, kTooDeepTargetDepth + 2);
1046    ASSERT_TRUE(too_deep_child != nullptr) << child_subchild->ToDotGraph();
1047    ASSERT_TRUE(IsTooWide(too_deep_child)) << *(too_deep_child);
1048    ASSERT_TRUE(IsTooDeep(too_deep_child)) << *(too_deep_child);
1049  }
1050
1051  // Try to assign every level
1052  // It will fail once it gets to the "too wide" siblings and cause overflows.
1053  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
1054
1055  // Check every class against every class for "x instanceof y".
1056  EnsureSubtypeOfRecursive(root_);
1057}
1058
1059// TODO: add dcheck for child-parent invariants (e.g. child < parent.next) and death tests
1060
1061}  // namespace art
1062