/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "subtype_check.h"

#include "gtest/gtest.h"
#include "android-base/logging.h"

namespace art {

constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
constexpr size_t BitString::kCapacity;

struct MockClass {
  explicit MockClass(MockClass* parent, size_t x = 0, size_t y = 0) {
    parent_ = parent;
    memset(&subtype_check_info_and_status_, 0u, sizeof(subtype_check_info_and_status_));

    // Start the numbering at '1' to match the bitstring numbering.
    // A bitstring numbering never starts at '0' which just means 'no value'.
    x_ = 1;
    if (parent_ != nullptr) {
      if (parent_->GetMaxChild() != nullptr) {
        x_ = parent_->GetMaxChild()->x_ + 1u;
      }

      parent_->children_.push_back(this);
      if (parent_->path_to_root_ != "") {
        path_to_root_ = parent->path_to_root_ + ",";
      }
      path_to_root_ += std::to_string(x_);
    } else {
      path_to_root_ = "";  // root has no path.
    }
    y_ = y;
    UNUSED(x);
  }

  MockClass() : MockClass(nullptr) {
  }

  ///////////////////////////////////////////////////////////////
  // Implementation of the SubtypeCheck::KlassT static interface.
  ///////////////////////////////////////////////////////////////

  MockClass* GetSuperClass() const {
    return parent_;
  }

  bool HasSuperClass() const {
    return GetSuperClass() != nullptr;
  }

  size_t Depth() const {
    if (parent_ == nullptr) {
      return 0u;
    } else {
      return parent_->Depth() + 1u;
    }
  }

  std::string PrettyClass() const
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return path_to_root_;
  }

  int32_t GetField32Volatile(art::MemberOffset offset = art::MemberOffset(0u)) const
      REQUIRES_SHARED(Locks::mutator_lock_) {
    UNUSED(offset);
    int32_t field_32 = 0;
    memcpy(&field_32, &subtype_check_info_and_status_, sizeof(int32_t));
    return field_32;
  }

  template <bool kTransactionActive>
  bool CasField32(art::MemberOffset offset,
                  int32_t old_value,
                  int32_t new_value,
                  CASMode mode ATTRIBUTE_UNUSED,
                  std::memory_order memory_order ATTRIBUTE_UNUSED)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    UNUSED(offset);
    if (old_value == GetField32Volatile(offset)) {
      memcpy(&subtype_check_info_and_status_, &new_value, sizeof(int32_t));
      return true;
    }
    return false;
  }

  MemberOffset StatusOffset() const {
    return MemberOffset(0);  // Doesn't matter. We ignore offset.
  }

  ///////////////////////////////////////////////////////////////
  // Convenience functions to make the testing easier
  ///////////////////////////////////////////////////////////////

  size_t GetNumberOfChildren() const {
    return children_.size();
  }

  MockClass* GetParent() const {
    return parent_;
  }

  MockClass* GetMaxChild() const {
    if (GetNumberOfChildren() > 0u) {
      return GetChild(GetNumberOfChildren() - 1);
    }
    return nullptr;
  }

  MockClass* GetChild(size_t idx) const {
    if (idx >= GetNumberOfChildren()) {
      return nullptr;
    }
    return children_[idx];
  }

  // Traverse the sibling at "X" at each level.
  // Once we get to level==depth, return yourself.
  MockClass* FindChildAt(size_t x, size_t depth) {
    if (Depth() == depth) {
      return this;
    } else if (GetNumberOfChildren() > 0) {
      return GetChild(x)->FindChildAt(x, depth);
    }
    return nullptr;
  }

  template <typename T>
  MockClass* Visit(T visitor, bool recursive = true) {
    if (!visitor(this)) {
      return this;
    }

    if (!recursive) {
      return this;
    }

    for (MockClass* child : children_) {
      MockClass* visit_res = child->Visit(visitor);
      if (visit_res != nullptr) {
        return visit_res;
      }
    }

    return nullptr;
  }

  size_t GetX() const {
    return x_;
  }

  bool SlowIsSubtypeOf(const MockClass* target) const {
    DCHECK(target != nullptr);
    const MockClass* kls = this;
    while (kls != nullptr) {
      if (kls == target) {
        return true;
      }
      kls = kls->GetSuperClass();
    }

    return false;
  }

  std::string ToDotGraph() const {
    std::stringstream ss;
    ss << std::endl;
    ss << "digraph MockClass {" << std::endl;
    ss << "    node [fontname=\"Arial\"];" << std::endl;
    ToDotGraphImpl(ss);
    ss << "}" << std::endl;
    return ss.str();
  }

  void ToDotGraphImpl(std::ostream& os) const {
    for (MockClass* child : children_) {
      os << "    '" << path_to_root_ << "' -> '" << child->path_to_root_ << "';" << std::endl;
      child->ToDotGraphImpl(os);
    }
  }

  std::vector<MockClass*> children_;
  MockClass* parent_;
  SubtypeCheckBitsAndStatus subtype_check_info_and_status_;
  size_t x_;
  size_t y_;
  std::string path_to_root_;
};

std::ostream& operator<<(std::ostream& os, const MockClass& kls) {
  SubtypeCheckBits iod = kls.subtype_check_info_and_status_.subtype_check_info_;
  os << "MClass{D:" << kls.Depth() << ",W:" << kls.x_
     << ", OF:"
     << (iod.overflow_ ? "true" : "false")
     << ", bitstring: " << iod.bitstring_
     << ", mock_path: " << kls.path_to_root_
     << "}";
  return os;
}

struct MockSubtypeCheck {
  using SC = SubtypeCheck<MockClass*>;

  static MockSubtypeCheck Lookup(MockClass* klass) {
    MockSubtypeCheck mock;
    mock.klass_ = klass;
    return mock;
  }

  // Convenience functions to avoid using statics everywhere.
  //    static(class, args...) -> instance.method(args...)
  SubtypeCheckInfo::State EnsureInitialized()
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::EnsureInitialized(klass_);
  }

  SubtypeCheckInfo::State EnsureAssigned()
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::EnsureAssigned(klass_);
  }

  SubtypeCheckInfo::State ForceUninitialize()
    REQUIRES(Locks::subtype_check_lock_)
    REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::ForceUninitialize(klass_);
  }

  BitString::StorageType GetEncodedPathToRootForSource() const
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::GetEncodedPathToRootForSource(klass_);
  }

  BitString::StorageType GetEncodedPathToRootForTarget() const
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::GetEncodedPathToRootForTarget(klass_);
  }

  BitString::StorageType GetEncodedPathToRootMask() const
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::GetEncodedPathToRootMask(klass_);
  }

  SubtypeCheckInfo::Result IsSubtypeOf(const MockSubtypeCheck& target)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::IsSubtypeOf(klass_, target.klass_);
  }

  friend std::ostream& operator<<(std::ostream& os, const MockSubtypeCheck& tree)
      NO_THREAD_SAFETY_ANALYSIS {
    os << "(MockSubtypeCheck io:";
    SC::Dump(tree.klass_, os);
    os << ", class: " << tree.klass_->PrettyClass() << ")";
    return os;
  }

  // Additional convenience functions.
  SubtypeCheckInfo::State GetState() const
      REQUIRES(Locks::subtype_check_lock_)
      REQUIRES_SHARED(Locks::mutator_lock_) {
    return SC::GetSubtypeCheckInfo(klass_).GetState();
  }

  MockClass& GetClass() const {
    return *klass_;
  }

 private:
  MockClass* klass_;
};

struct MockScopedLockSubtypeCheck {
  MockScopedLockSubtypeCheck() ACQUIRE(*Locks::subtype_check_lock_) {}
  ~MockScopedLockSubtypeCheck() RELEASE(*Locks::subtype_check_lock_) {}
};

struct MockScopedLockMutator {
  MockScopedLockMutator() ACQUIRE_SHARED(*Locks::mutator_lock_) {}
  ~MockScopedLockMutator() RELEASE_SHARED(*Locks::mutator_lock_) {}
};

struct SubtypeCheckTest : public ::testing::Test {
 protected:
  void SetUp() override {
    android::base::InitLogging(/*argv=*/nullptr);

    CreateRootedTree(BitString::kCapacity + 2u, BitString::kCapacity + 2u);
  }

  void TearDown() override {
  }

  void CreateRootedTree(size_t width, size_t height) {
    all_classes_.clear();
    root_ = CreateClassFor(/*parent=*/nullptr, /*x=*/0, /*y=*/0);
    CreateTreeFor(root_, /*width=*/width, /*levels=*/height);
  }

  MockClass* CreateClassFor(MockClass* parent, size_t x, size_t y) {
    MockClass* kls = new MockClass(parent, x, y);
    all_classes_.push_back(std::unique_ptr<MockClass>(kls));
    return kls;
  }

  void CreateTreeFor(MockClass* parent, size_t width, size_t levels) {
    DCHECK(parent != nullptr);
    if (levels == 0) {
      return;
    }

    for (size_t i = 0; i < width; ++i) {
      MockClass* child = CreateClassFor(parent, i, parent->y_ + 1);
      CreateTreeFor(child, width, levels - 1);
    }
  }

  MockClass* root_ = nullptr;
  std::vector<std::unique_ptr<MockClass>> all_classes_;
};

TEST_F(SubtypeCheckTest, LookupAllChildren) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  root_->Visit([&](MockClass* kls) {
    MockScopedLockSubtypeCheck lock_a;
    MockScopedLockMutator lock_b;

    EXPECT_EQ(SubtypeCheckInfo::kUninitialized, SCTree::Lookup(kls).GetState());
    return true;  // Keep visiting.
  });
}

TEST_F(SubtypeCheckTest, LookupRoot) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree root = SCTree::Lookup(root_);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());
  EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, root.IsSubtypeOf(root)) << root;
}

TEST_F(SubtypeCheckTest, EnsureInitializedFirstLevel) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree root = SCTree::Lookup(root_);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());

  ASSERT_LT(0u, root_->GetNumberOfChildren());

  // Initialize root's children only.
  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
    MockClass* child = root_->GetChild(i);
    SCTree child_tree = SCTree::Lookup(child);
    // Before: all unknown.
    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
    // Transition.
    EXPECT_EQ(SubtypeCheckInfo::kInitialized, child_tree.EnsureInitialized());
    // After: "src instanceof target" known, but "target instanceof src" unknown.
    EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
  }
}

TEST_F(SubtypeCheckTest, EnsureAssignedFirstLevel) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree root = SCTree::Lookup(root_);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());

  ASSERT_LT(0u, root_->GetNumberOfChildren());

  // Initialize root's children only.
  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
    MockClass* child = root_->GetChild(i);
    SCTree child_tree = SCTree::Lookup(child);
    // Before: all unknown.
    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
    EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
    // Transition.
    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.EnsureAssigned());
    // After: "src instanceof target" known, and "target instanceof src" known.
    EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child_tree.IsSubtypeOf(root)) << child_tree;
    EXPECT_EQ(SubtypeCheckInfo::kNotSubtypeOf, root.IsSubtypeOf(child_tree)) << child_tree;
  }
}

TEST_F(SubtypeCheckTest, EnsureInitializedSecondLevelWithPreassign) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree root = SCTree::Lookup(root_);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());

  ASSERT_LT(0u, root_->GetNumberOfChildren());

  // Initialize root's children.
  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
    MockClass* child = root_->GetChild(i);
    SCTree child_tree = SCTree::Lookup(child);

    ASSERT_EQ(1u, child->Depth());

    EXPECT_EQ(SubtypeCheckInfo::kInitialized, child_tree.EnsureInitialized()) << *child;
    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.EnsureAssigned())
              << *child << ", root:" << *root_;
    for (size_t j = 0; j < child->GetNumberOfChildren(); ++j) {
      MockClass* child2 = child->GetChild(j);
      ASSERT_EQ(2u, child2->Depth());
      SCTree child2_tree = SCTree::Lookup(child2);

      // Before: all unknown.
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
                << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(root))
                << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(child_tree))
                << child2_tree;

      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, child2_tree.GetState()) << *child2;
      EXPECT_EQ(SubtypeCheckInfo::kInitialized, child2_tree.EnsureInitialized()) << *child2;

      // After: src=child2_tree is known, otherwise unknown.
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
                << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(child_tree)) << child2_tree;
    }

    // The child is "assigned" as a side-effect of initializing sub-children.
    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.GetState());
  }
}

TEST_F(SubtypeCheckTest, EnsureInitializedSecondLevelDontPreassign) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree root = SCTree::Lookup(root_);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, root.EnsureInitialized());

  ASSERT_LT(0u, root_->GetNumberOfChildren());

  // Initialize root's children only.
  for (size_t i = 0; i < root_->GetNumberOfChildren(); ++i) {
    MockClass* child = root_->GetChild(i);
    SCTree child_tree = SCTree::Lookup(child);

    ASSERT_EQ(1u, child->Depth());

    for (size_t j = 0; j < child->GetNumberOfChildren(); ++j) {
      MockClass* child2 = child->GetChild(j);
      ASSERT_EQ(2u, child2->Depth());
      SCTree child2_tree = SCTree::Lookup(child2);
      // Before: all unknown.
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
                << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child2_tree.IsSubtypeOf(child_tree))
                << child2_tree;
      // Transition.
      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, child2_tree.GetState()) << *child2;
      EXPECT_EQ(SubtypeCheckInfo::kInitialized, child2_tree.EnsureInitialized()) << *child2;
      // After: src=child2_tree is known, otherwise unknown.
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, root.IsSubtypeOf(child2_tree)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, child_tree.IsSubtypeOf(child2_tree))
                << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(root)) << child2_tree;
      EXPECT_EQ(SubtypeCheckInfo::kSubtypeOf, child2_tree.IsSubtypeOf(child_tree)) << child2_tree;
    }

    // The child is "assigned" as a side-effect of initializing sub-children.
    EXPECT_EQ(SubtypeCheckInfo::kAssigned, child_tree.GetState());
  }
}

void ApplyTransition(MockSubtypeCheck sc_tree,
                     SubtypeCheckInfo::State transition,
                     SubtypeCheckInfo::State expected) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;

  EXPECT_EQ(SubtypeCheckInfo::kUninitialized, sc_tree.GetState()) << sc_tree.GetClass();

  if (transition == SubtypeCheckInfo::kUninitialized) {
    EXPECT_EQ(expected, sc_tree.ForceUninitialize()) << sc_tree.GetClass();
  } else if (transition == SubtypeCheckInfo::kInitialized) {
    EXPECT_EQ(expected, sc_tree.EnsureInitialized()) << sc_tree.GetClass();
  } else if (transition == SubtypeCheckInfo::kAssigned) {
    EXPECT_EQ(expected, sc_tree.EnsureAssigned()) << sc_tree.GetClass();
  }
}

enum MockSubtypeOfTransition {
  kNone,
  kUninitialized,
  kInitialized,
  kAssigned,
};

std::ostream& operator<<(std::ostream& os, const MockSubtypeOfTransition& transition) {
  if (transition == MockSubtypeOfTransition::kUninitialized) {
    os << "kUninitialized";
  } else if (transition == MockSubtypeOfTransition::kInitialized) {
    os << "kInitialized";
  } else if (transition == MockSubtypeOfTransition::kAssigned) {
    os << "kAssigned";
  } else {
    os << "kNone";
  }
  return os;
}

SubtypeCheckInfo::State ApplyTransition(MockSubtypeCheck sc_tree,
                                        MockSubtypeOfTransition transition) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;

  if (transition ==  MockSubtypeOfTransition::kUninitialized) {
    return sc_tree.ForceUninitialize();
  } else if (transition == MockSubtypeOfTransition::kInitialized) {
    return sc_tree.EnsureInitialized();
  } else if (transition == MockSubtypeOfTransition::kAssigned) {
    return sc_tree.EnsureAssigned();
  }

  return sc_tree.GetState();
}

enum {
  kBeforeTransition = 0,
  kAfterTransition = 1,
  kAfterChildren = 2,
};

const char* StringifyTransition(int x) {
  if (x == kBeforeTransition) {
    return "kBeforeTransition";
  } else if (x == kAfterTransition) {
    return "kAfterTransition";
  } else if (x == kAfterChildren) {
    return "kAfterChildren";
  }

  return "<<Unknown>>";
}

struct TransitionHistory {
  void Record(int transition_label, MockClass* kls) {
    ss_ << "<<<" << StringifyTransition(transition_label) << ">>>";
    ss_ << "{Self}: " << *kls;

    if (kls->HasSuperClass()) {
      ss_ << "{Parent}: " << *(kls->GetSuperClass());
    }
    ss_ << "================== ";
  }

  friend std::ostream& operator<<(std::ostream& os, const TransitionHistory& t) {
    os << t.ss_.str();
    return os;
  }

  std::stringstream ss_;
};

template <typename T, typename T2>
void EnsureStateChangedTestRecursiveGeneric(MockClass* klass,
                                            size_t cur_depth,
                                            size_t total_depth,
                                            T2 transition_func,
                                            T expect_checks) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  SCTree sc_tree = SCTree::Lookup(klass);
  MockSubtypeOfTransition requested_transition = transition_func(klass);

  // FIXME: need to print before(self, parent) and after(self, parent)
  // to make any sense of what's going on.

  auto do_expect_checks = [&](int transition_label, TransitionHistory& transition_details) {
    MockScopedLockSubtypeCheck lock_a;
    MockScopedLockMutator lock_b;

    transition_details.Record(transition_label, klass);

    SCOPED_TRACE(transition_details);
    ASSERT_EQ(cur_depth, klass->Depth());

    ASSERT_NO_FATAL_FAILURE(expect_checks(klass,
                                          transition_label,
                                          sc_tree.GetState(),
                                          requested_transition));
  };

  TransitionHistory transition_history;
  do_expect_checks(kBeforeTransition, transition_history);
  SubtypeCheckInfo::State state = ApplyTransition(sc_tree, requested_transition);
  UNUSED(state);
  do_expect_checks(kAfterTransition, transition_history);

  if (total_depth == cur_depth) {
    return;
  }

  // Initialize root's children only.
  for (size_t i = 0; i < klass->GetNumberOfChildren(); ++i) {
    MockClass* child = klass->GetChild(i);
    EnsureStateChangedTestRecursiveGeneric(child,
                                           cur_depth + 1u,
                                           total_depth,
                                           transition_func,
                                           expect_checks);
  }

  do_expect_checks(kAfterChildren, transition_history);
}

void EnsureStateChangedTestRecursive(
    MockClass* klass,
    size_t cur_depth,
    size_t total_depth,
    const std::vector<std::pair<SubtypeCheckInfo::State, SubtypeCheckInfo::State>>& transitions) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  ASSERT_EQ(cur_depth, klass->Depth());
  ApplyTransition(SCTree::Lookup(klass),
                  transitions[cur_depth].first,
                  transitions[cur_depth].second);

  if (total_depth == cur_depth + 1) {
    return;
  }

  // Initialize root's children only.
  for (size_t i = 0; i < klass->GetNumberOfChildren(); ++i) {
    MockClass* child = klass->GetChild(i);
    EnsureStateChangedTestRecursive(child, cur_depth + 1u, total_depth, transitions);
  }
}

void EnsureStateChangedTest(
    MockClass* root,
    size_t depth,
    const std::vector<std::pair<SubtypeCheckInfo::State, SubtypeCheckInfo::State>>& transitions) {
  ASSERT_EQ(depth, transitions.size());

  EnsureStateChangedTestRecursive(root, /*cur_depth=*/0u, depth, transitions);
}

TEST_F(SubtypeCheckTest, EnsureInitialized_NoOverflow) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kInitialized;
  };

  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity;
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    if (expect_when == kBeforeTransition) {
      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, actual_state);
      return;
    }

    if (expect_when == kAfterTransition) {
      // After explicit transition has been completed.
      switch (kls->Depth()) {
      case 0:
        if (transition >= MockSubtypeOfTransition::kInitialized) {
          EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
        }
        break;
      default:
        if (transition >= MockSubtypeOfTransition::kInitialized) {
          if (transition == MockSubtypeOfTransition::kInitialized) {
            EXPECT_EQ(SubtypeCheckInfo::kInitialized, actual_state);
          } else if (transition == MockSubtypeOfTransition::kAssigned) {
            EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
          }
        }
        break;
      }
    }

    if (expect_when == kAfterChildren) {
      if (transition >= MockSubtypeOfTransition::kInitialized) {
        ASSERT_NE(kls->Depth(), kMaxDepthForThisTest);
        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
      }
    }
  };

  // Initialize every level 0-3.
  // Intermediate levels become "assigned", max levels become initialized.
  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);

  auto transitions_uninitialize = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kUninitialized;
  };

  auto expected_uninitialize = [](MockClass* kls,
                                  int expect_when,
                                  SubtypeCheckInfo::State actual_state,
                                  MockSubtypeOfTransition transition) {
    UNUSED(kls);
    UNUSED(transition);
    if (expect_when >= kAfterTransition) {
      EXPECT_EQ(SubtypeCheckInfo::kUninitialized, actual_state);
    }
  };

  // Uninitialize the entire tree after it was assigned.
  EnsureStateChangedTestRecursiveGeneric(root_,
                                         0u,
                                         kMaxDepthForThisTest,
                                         transitions_uninitialize,
                                         expected_uninitialize);
}

TEST_F(SubtypeCheckTest, EnsureAssigned_TooDeep) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kAssigned;
  };

  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity + 1u;
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    UNUSED(transition);
    if (expect_when == kAfterTransition) {
      if (kls->Depth() > BitString::kCapacity) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      }
    }
  };

  // Assign every level 0-4.
  // We cannot assign 4th level, so it will overflow instead.
  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
}

TEST_F(SubtypeCheckTest, EnsureAssigned_TooDeep_OfTooDeep) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kAssigned;
  };

  constexpr size_t kMaxDepthForThisTest = BitString::kCapacity + 2u;
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    UNUSED(transition);
    if (expect_when == kAfterTransition) {
      if (kls->Depth() > BitString::kCapacity) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      }
    }
  };

  // Assign every level 0-5.
  // We cannot assign 4th level, so it will overflow instead.
  // In addition, level 5th cannot be assigned (parent is overflowed), so it will also fail.
  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
}

constexpr size_t MaxWidthCutOff(size_t depth) {
  if (depth == 0) {
    return 1;
  }
  if (depth > BitString::kCapacity) {
    return std::numeric_limits<size_t>::max();
  }
  return MaxInt<size_t>(BitString::kBitSizeAtPosition[depth - 1]);
}

// Either itself is too wide, or any of the parents were too wide.
bool IsTooWide(MockClass* kls) {
  if (kls == nullptr || kls->Depth() == 0u) {
    // Root is never too wide.
    return false;
  } else {
    if (kls->GetX() >= MaxWidthCutOff(kls->Depth())) {
      return true;
    }
  }
  return IsTooWide(kls->GetParent());
}

// Either itself is too deep, or any of the parents were too deep.
bool IsTooDeep(MockClass* kls) {
  if (kls == nullptr || kls->Depth() == 0u) {
    // Root is never too deep.
    return false;
  } else {
    if (kls->Depth() > BitString::kCapacity) {
      return true;
    }
  }
  return false;
}

TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kAssigned;
  };

  // Pick the 2nd level because has the most narrow # of bits.
  constexpr size_t kTargetDepth = 2;
  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);

  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    UNUSED(transition);
    // Note: purposefuly ignore the too-deep children in the premade tree.
    if (expect_when == kAfterTransition && kls->Depth() <= BitString::kCapacity) {
      if (IsTooWide(kls)) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      } else {
        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
      }
    }
  };

  {
    // Create too-wide siblings at the kTargetDepth level.
    MockClass* child = root_->FindChildAt(/*x=*/0, kTargetDepth - 1u);
    CreateTreeFor(child, kMaxWidthCutOff*2, /*levels=*/1);
    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren());
    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
    // Leave the rest of the tree as the default.
  }

  // Try to assign every level
  // It will fail once it gets to the "too wide" siblings and cause overflows.
  EnsureStateChangedTestRecursiveGeneric(root_,
                                         0u,
                                         kMaxDepthForThisTest,
                                         transitions,
                                         expected);
}

TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide_TooWide) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kAssigned;
  };

  // Pick the 2nd level because has the most narrow # of bits.
  constexpr size_t kTargetDepth = 2;
  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);
  constexpr size_t kMaxWidthCutOffSub = MaxWidthCutOff(kTargetDepth+1u);

  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    UNUSED(transition);
    // Note: purposefuly ignore the too-deep children in the premade tree.
    if (expect_when == kAfterTransition && kls->Depth() <= BitString::kCapacity) {
      if (IsTooWide(kls)) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      } else {
        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
      }
    }
  };

  {
    // Create too-wide siblings at the kTargetDepth level.
    MockClass* child = root_->FindChildAt(/*x=*/0, kTargetDepth - 1);
    CreateTreeFor(child, kMaxWidthCutOff*2, /*levels=*/1);
    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren()) << *child;
    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
    // Leave the rest of the tree as the default.

    // Create too-wide children for a too-wide parent.
    MockClass* child_subchild = child->FindChildAt(/*x=*/0, kTargetDepth);
    CreateTreeFor(child_subchild, kMaxWidthCutOffSub*2, /*levels=*/1);
    ASSERT_LE(kMaxWidthCutOffSub*2, child_subchild->GetNumberOfChildren()) << *child_subchild;
    ASSERT_TRUE(IsTooWide(child_subchild->GetMaxChild())) << *(child_subchild->GetMaxChild());
  }

  // Try to assign every level
  // It will fail once it gets to the "too wide" siblings and cause overflows.
  // Furthermore, assigning any subtree whose ancestor is too wide will also fail.
  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);
}

void EnsureSubtypeOfCorrect(MockClass* a, MockClass* b) {
  MockScopedLockSubtypeCheck lock_a;
  MockScopedLockMutator lock_b;
  using SCTree = MockSubtypeCheck;

  auto IsAssigned = [](SCTree& tree) {
    MockScopedLockSubtypeCheck lock_a;
    MockScopedLockMutator lock_b;
    // This assumes that MockClass is always called with EnsureAssigned.
    EXPECT_NE(SubtypeCheckInfo::kInitialized, tree.GetState());
    EXPECT_NE(SubtypeCheckInfo::kUninitialized, tree.GetState());
    // Use our own test checks, so we are actually testing different logic than the impl.
    return !(IsTooDeep(&tree.GetClass()) || IsTooWide(&tree.GetClass()));
  };

  SCTree src_tree = SCTree::Lookup(a);
  SCTree target_tree = SCTree::Lookup(b);

  SCOPED_TRACE("class A");
  SCOPED_TRACE(*a);
  SCOPED_TRACE("class B");
  SCOPED_TRACE(*b);

  SubtypeCheckInfo::Result slow_result =
      a->SlowIsSubtypeOf(b) ? SubtypeCheckInfo::kSubtypeOf : SubtypeCheckInfo::kNotSubtypeOf;
  SubtypeCheckInfo::Result fast_result = src_tree.IsSubtypeOf(target_tree);

  // Target must be Assigned for this check to succeed.
  // Source is either Overflowed | Assigned (in this case).

  if (IsAssigned(src_tree) && IsAssigned(target_tree)) {
    ASSERT_EQ(slow_result, fast_result);
  } else if (IsAssigned(src_tree)) {
    // A is assigned. B is >= initialized.
    ASSERT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, fast_result);
  } else if (IsAssigned(target_tree)) {
    // B is assigned. A is >= initialized.
    ASSERT_EQ(slow_result, fast_result);
  } else {
    // Neither A,B are assigned.
    ASSERT_EQ(SubtypeCheckInfo::kUnknownSubtypeOf, fast_result);
  }

  // Use asserts,  not expects to immediately fail.
  // Otherwise the entire tree (very large) could potentially be broken.
}

void EnsureSubtypeOfRecursive(MockClass* kls_root) {
  MockScopedLockMutator mutator_lock_fake_;

  auto visit_func = [&](MockClass* kls) {
    kls->Visit([&](MockClass* inner_class) {
      EnsureSubtypeOfCorrect(kls, inner_class);
      EnsureSubtypeOfCorrect(inner_class, kls);

      if (::testing::Test::HasFatalFailure()) {
        return false;
      }

      return true;  // Keep visiting.
    });

    if (::testing::Test::HasFatalFailure()) {
        return false;
    }

    return true;  // Keep visiting.
  };

  ASSERT_NO_FATAL_FAILURE(kls_root->Visit(visit_func));
}

TEST_F(SubtypeCheckTest, EnsureInitialized_TooWide_TooDeep) {
  auto transitions = [](MockClass* kls) {
    UNUSED(kls);
    return MockSubtypeOfTransition::kAssigned;
  };

  // Pick the 2nd level because has the most narrow # of bits.
  constexpr size_t kTargetDepth = 2;
  constexpr size_t kTooDeepTargetDepth = BitString::kCapacity + 1;
  constexpr size_t kMaxWidthCutOff = MaxWidthCutOff(kTargetDepth);

  constexpr size_t kMaxDepthForThisTest = std::numeric_limits<size_t>::max();
  auto expected = [=](MockClass* kls,
                      int expect_when,
                      SubtypeCheckInfo::State actual_state,
                      MockSubtypeOfTransition transition) {
    UNUSED(transition);
    if (expect_when == kAfterTransition) {
      if (IsTooDeep(kls)) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      } else if (IsTooWide(kls)) {
        EXPECT_EQ(SubtypeCheckInfo::kOverflowed, actual_state);
      } else {
        EXPECT_EQ(SubtypeCheckInfo::kAssigned, actual_state);
      }
    }
  };

  {
    // Create too-wide siblings at the kTargetDepth level.
    MockClass* child = root_->FindChildAt(/*x=*/0, kTargetDepth - 1u);
    CreateTreeFor(child, kMaxWidthCutOff*2, /*levels=*/1);
    ASSERT_LE(kMaxWidthCutOff*2, child->GetNumberOfChildren());
    ASSERT_TRUE(IsTooWide(child->GetMaxChild())) << *(child->GetMaxChild());
    // Leave the rest of the tree as the default.

    // Create too-deep children for a too-wide parent.
    MockClass* child_subchild = child->GetMaxChild();
    ASSERT_TRUE(child_subchild != nullptr);
    ASSERT_EQ(0u, child_subchild->GetNumberOfChildren()) << *child_subchild;
    CreateTreeFor(child_subchild, /*width=*/1, /*levels=*/kTooDeepTargetDepth);
    MockClass* too_deep_child = child_subchild->FindChildAt(0, kTooDeepTargetDepth + 2);
    ASSERT_TRUE(too_deep_child != nullptr) << child_subchild->ToDotGraph();
    ASSERT_TRUE(IsTooWide(too_deep_child)) << *(too_deep_child);
    ASSERT_TRUE(IsTooDeep(too_deep_child)) << *(too_deep_child);
  }

  // Try to assign every level
  // It will fail once it gets to the "too wide" siblings and cause overflows.
  EnsureStateChangedTestRecursiveGeneric(root_, 0u, kMaxDepthForThisTest, transitions, expected);

  // Check every class against every class for "x instanceof y".
  EnsureSubtypeOfRecursive(root_);
}

// TODO: add dcheck for child-parent invariants (e.g. child < parent.next) and death tests

}  // namespace art