/*
|
* 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
|
