| /* |
| * 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 CasFieldWeakSequentiallyConsistent32(art::MemberOffset offset, |
| int32_t old_value, |
| int32_t new_value) |
| 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: |
| virtual void SetUp() { |
| android::base::InitLogging(/*argv*/nullptr); |
| |
| CreateRootedTree(BitString::kCapacity + 2u, BitString::kCapacity + 2u); |
| } |
| |
| virtual void TearDown() { |
| } |
| |
| void CreateRootedTree(size_t width, size_t height) { |
| all_classes_.clear(); |
| root_ = CreateClassFor(/*parent*/nullptr, /*x*/0, /*y*/0); |
| CreateTreeFor(root_, /*width*/width, /*depth*/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, |
| 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, |
| 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, /*depth*/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, /*depth*/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, /*depth*/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, /*depth*/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 |
