| /* |
| * 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_info.h" |
| |
| #include "gtest/gtest.h" |
| #include "android-base/logging.h" |
| |
| namespace art { |
| |
| constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity]; |
| constexpr size_t BitString::kCapacity; |
| |
| }; // namespace art |
| |
| using namespace art; // NOLINT |
| |
| // These helper functions are only used by the test, |
| // so they are not in the main BitString class. |
| std::string Stringify(BitString bit_string) { |
| std::stringstream ss; |
| ss << bit_string; |
| return ss.str(); |
| } |
| |
| BitStringChar MakeBitStringChar(size_t idx, size_t val) { |
| return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx)); |
| } |
| |
| BitStringChar MakeBitStringChar(size_t val) { |
| return BitStringChar(val, MinimumBitsToStore(val)); |
| } |
| |
| BitString MakeBitString(std::initializer_list<size_t> values = {}) { |
| CHECK_GE(BitString::kCapacity, values.size()); |
| |
| BitString bs{}; |
| |
| size_t i = 0; |
| for (size_t val : values) { |
| bs.SetAt(i, MakeBitStringChar(i, val)); |
| ++i; |
| } |
| |
| return bs; |
| } |
| |
| template <typename T> |
| size_t AsUint(const T& value) { |
| size_t uint_value = 0; |
| memcpy(&uint_value, &value, sizeof(value)); |
| return uint_value; |
| } |
| |
| // Make max bistring, e.g. BitString[4095,15,2047] for {12,4,11} |
| template <size_t kCount = BitString::kCapacity> |
| BitString MakeBitStringMax() { |
| BitString bs{}; |
| |
| for (size_t i = 0; i < kCount; ++i) { |
| bs.SetAt(i, |
| MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i]))); |
| } |
| |
| return bs; |
| } |
| |
| BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) { |
| BitString bs = bit_string; |
| bs.SetAt(i, MakeBitStringChar(i, val)); |
| return bs; |
| } |
| |
| struct SubtypeCheckInfoTest : public ::testing::Test { |
| protected: |
| void SetUp() override { |
| android::base::InitLogging(/*argv=*/nullptr); |
| } |
| |
| void TearDown() override { |
| } |
| |
| static SubtypeCheckInfo MakeSubtypeCheckInfo(BitString path_to_root = {}, |
| BitStringChar next = {}, |
| bool overflow = false, |
| size_t depth = 1u) { |
| // Depth=1 is good default because it will go through all state transitions, |
| // and its children will also go through all state transitions. |
| return SubtypeCheckInfo(path_to_root, next, overflow, depth); |
| } |
| |
| static SubtypeCheckInfo MakeSubtypeCheckInfoInfused(BitString bs = {}, |
| bool overflow = false, |
| size_t depth = 1u) { |
| // Depth=1 is good default because it will go through all state transitions, |
| // and its children will also go through all state transitions. |
| SubtypeCheckBits iod; |
| iod.bitstring_ = bs; |
| iod.overflow_ = overflow; |
| return SubtypeCheckInfo::Create(iod, depth); |
| } |
| |
| static SubtypeCheckInfo MakeSubtypeCheckInfoUnchecked(BitString bs = {}, |
| bool overflow = false, |
| size_t depth = 1u) { |
| // Depth=1 is good default because it will go through all state transitions, |
| // and its children will also go through all state transitions. |
| return SubtypeCheckInfo::MakeUnchecked(bs, overflow, depth); |
| } |
| |
| static bool HasNext(const SubtypeCheckInfo& io) { |
| return io.HasNext(); |
| } |
| |
| static BitString GetPathToRoot(const SubtypeCheckInfo& io) { |
| return io.GetPathToRoot(); |
| } |
| |
| // Create an SubtypeCheckInfo with the same depth, but with everything else reset. |
| // Returns: SubtypeCheckInfo in the Uninitialized state. |
| static SubtypeCheckInfo CopyCleared(const SubtypeCheckInfo& sc) { |
| SubtypeCheckInfo cleared_copy{}; |
| cleared_copy.depth_ = sc.depth_; |
| DCHECK_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState()); |
| return cleared_copy; |
| } |
| }; |
| |
| const char* GetExpectedMessageForDeathTest(const char* msg) { |
| #ifdef ART_TARGET_ANDROID |
| // On Android, dcheck failure messages go to logcat, |
| // which gtest death tests does not check, and thus the tests would fail with |
| // "unexpected message ''" |
| UNUSED(msg); |
| return ""; // Still ensures there was a bad return code, but match anything. |
| #else |
| return msg; |
| #endif |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, IllegalValues) { |
| // This test relies on BitString being at least 3 large. |
| // It will need to be updated otherwise. |
| ASSERT_LE(3u, BitString::kCapacity); |
| |
| // Illegal values during construction would cause a Dcheck failure and crash. |
| ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/false, |
| /*depth=*/0u), |
| GetExpectedMessageForDeathTest("Path was too long for the depth")); |
| ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({1u, 1u}), |
| /*overflow=*/false, |
| /*depth=*/0u), |
| GetExpectedMessageForDeathTest("Bitstring too long for depth")); |
| ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/false, |
| /*depth=*/1u), |
| GetExpectedMessageForDeathTest("Expected \\(Assigned\\|Initialized\\) " |
| "state to have >0 Next value")); |
| ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({0u, 2u, 1u}), |
| /*overflow=*/false, |
| /*depth=*/2u), |
| GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 2u}), |
| /*next=*/MakeBitStringChar(1u), |
| /*overflow=*/false, |
| /*depth=*/2u), |
| GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 1u, 1u}), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/false, |
| /*depth=*/3u), |
| GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| |
| // These are really slow (~1sec per death test on host), |
| // keep them down to a minimum. |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, States) { |
| EXPECT_EQ(SubtypeCheckInfo::kUninitialized, MakeSubtypeCheckInfo().GetState()); |
| EXPECT_EQ(SubtypeCheckInfo::kInitialized, |
| MakeSubtypeCheckInfo(/*path_to_root=*/{}, /*next=*/MakeBitStringChar(1)).GetState()); |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, |
| MakeSubtypeCheckInfo(/*path_to_root=*/{}, |
| /*next=*/MakeBitStringChar(1), |
| /*overflow=*/true, |
| /*depth=*/1u).GetState()); |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, |
| MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitString({1u}), |
| /*next=*/MakeBitStringChar(1), |
| /*overflow=*/false, |
| /*depth=*/1u).GetState()); |
| |
| // Test edge conditions: depth == BitString::kCapacity (No Next value). |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, |
| MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity).GetState()); |
| EXPECT_EQ(SubtypeCheckInfo::kInitialized, |
| MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax<BitString::kCapacity - 1u>(), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity).GetState()); |
| // Test edge conditions: depth > BitString::kCapacity (Must overflow). |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, |
| MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| /*next=*/MakeBitStringChar(0), |
| /*overflow=*/true, |
| /*depth=*/BitString::kCapacity + 1u).GetState()); |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, NextValue) { |
| // Validate "Next" is correctly aliased as the Bitstring[Depth] character. |
| EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
| /*overflow=*/false, |
| /*depth=*/0u).GetNext()); |
| EXPECT_EQ(MakeBitStringChar(2u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
| /*overflow=*/false, |
| /*depth=*/1u).GetNext()); |
| EXPECT_EQ(MakeBitStringChar(3u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
| /*overflow=*/false, |
| /*depth=*/2u).GetNext()); |
| EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({0u, 2u, 1u}), |
| /*overflow=*/false, |
| /*depth=*/2u).GetNext()); |
| // Test edge conditions: depth == BitString::kCapacity (No Next value). |
| EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity))); |
| // Anything with depth >= BitString::kCapacity has no next value. |
| EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity + 1u))); |
| EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax(), |
| /*overflow=*/false, |
| /*depth=*/std::numeric_limits<size_t>::max()))); |
| } |
| |
| template <size_t kPos = BitString::kCapacity> |
| size_t LenForPos() { return BitString::GetBitLengthTotalAtPosition(kPos); } |
| |
| TEST_F(SubtypeCheckInfoTest, EncodedPathToRoot) { |
| using StorageType = BitString::StorageType; |
| |
| SubtypeCheckInfo sci = |
| MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| /*next=*/BitStringChar{}, |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity); |
| // 0b000...111 where LSB == 1, and trailing 1s = the maximum bitstring representation. |
| EXPECT_EQ(MaxInt<StorageType>(LenForPos()), sci.GetEncodedPathToRoot()); |
| |
| // The rest of this test is written assuming kCapacity == 3 for convenience. |
| // Please update the test if this changes. |
| ASSERT_EQ(3u, BitString::kCapacity); |
| ASSERT_EQ(12u, BitString::kBitSizeAtPosition[0]); |
| ASSERT_EQ(4u, BitString::kBitSizeAtPosition[1]); |
| ASSERT_EQ(11u, BitString::kBitSizeAtPosition[2]); |
| |
| SubtypeCheckInfo sci2 = |
| MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity); |
| |
| #define MAKE_ENCODED_PATH(pos0, pos1, pos2) \ |
| (((pos0) << 0) | \ |
| ((pos1) << BitString::kBitSizeAtPosition[0]) | \ |
| ((pos2) << (BitString::kBitSizeAtPosition[0] + BitString::kBitSizeAtPosition[1]))) |
| |
| EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| sci2.GetEncodedPathToRoot()); |
| EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b11111111111), |
| sci2.GetEncodedPathToRootMask()); |
| |
| SubtypeCheckInfo sci3 = |
| MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity - 1u); |
| |
| EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| sci3.GetEncodedPathToRoot()); |
| EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| sci3.GetEncodedPathToRootMask()); |
| |
| SubtypeCheckInfo sci4 = |
| MakeSubtypeCheckInfoUnchecked(MakeBitString({0b1010101u}), |
| /*overflow=*/false, |
| /*depth=*/BitString::kCapacity - 2u); |
| |
| EXPECT_EQ(MAKE_ENCODED_PATH(0b1010101u, 0b0000, 0b0), sci4.GetEncodedPathToRoot()); |
| EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b0000, 0b0), |
| sci4.GetEncodedPathToRootMask()); |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, NewForRoot) { |
| SubtypeCheckInfo sci = SubtypeCheckInfo::CreateRoot(); |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, sci.GetState()); // Root is always assigned. |
| EXPECT_EQ(0u, GetPathToRoot(sci).Length()); // Root's path length is 0. |
| EXPECT_TRUE(HasNext(sci)); // Root always has a "Next". |
| EXPECT_EQ(MakeBitStringChar(1u), sci.GetNext()); // Next>=1 to disambiguate from Uninitialized. |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, CopyCleared) { |
| SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| |
| SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| |
| SubtypeCheckInfo cleared_copy = CopyCleared(childC); |
| EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState()); |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy)); |
| |
| // CopyCleared is just a thin wrapper around value-init and providing the depth. |
| SubtypeCheckInfo cleared_copy_value = |
| SubtypeCheckInfo::Create(SubtypeCheckBits{}, /*depth=*/1u); |
| EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy_value.GetState()); |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy_value)); |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, NewForChild2) { |
| SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| |
| SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| } |
| |
| TEST_F(SubtypeCheckInfoTest, NewForChild) { |
| SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| |
| SubtypeCheckInfo childA = root.CreateChild(/*assign_next=*/false); |
| EXPECT_EQ(SubtypeCheckInfo::kInitialized, childA.GetState()); |
| EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); // Next unchanged for Initialize. |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(childA)); |
| |
| SubtypeCheckInfo childB = root.CreateChild(/*assign_next=*/false); |
| EXPECT_EQ(SubtypeCheckInfo::kInitialized, childB.GetState()); |
| EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); // Next unchanged for Initialize. |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(childB)); |
| |
| SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| |
| { |
| size_t cur_depth = 1u; |
| SubtypeCheckInfo latest_child = childC; |
| while (cur_depth != BitString::kCapacity) { |
| latest_child = latest_child.CreateChild(/*assign_next=*/true); |
| ASSERT_EQ(SubtypeCheckInfo::kAssigned, latest_child.GetState()); |
| ASSERT_EQ(cur_depth + 1u, GetPathToRoot(latest_child).Length()); |
| cur_depth++; |
| } |
| |
| // Future assignments will result in a too-deep overflow. |
| SubtypeCheckInfo child_of_deep = latest_child.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep.GetState()); |
| EXPECT_EQ(GetPathToRoot(latest_child), GetPathToRoot(child_of_deep)); |
| |
| // Assignment of too-deep overflow also causes overflow. |
| SubtypeCheckInfo child_of_deep_2 = child_of_deep.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep_2.GetState()); |
| EXPECT_EQ(GetPathToRoot(child_of_deep), GetPathToRoot(child_of_deep_2)); |
| } |
| |
| { |
| size_t cur_next = 2u; |
| while (true) { |
| if (cur_next == MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[0u])) { |
| break; |
| } |
| |
| SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/true); |
| ASSERT_EQ(SubtypeCheckInfo::kAssigned, child.GetState()); |
| ASSERT_EQ(MakeBitStringChar(cur_next+1u), root.GetNext()); |
| ASSERT_EQ(MakeBitString({cur_next}), GetPathToRoot(child)); |
| |
| cur_next++; |
| } |
| // Now the root will be in a state that further assigns will be too-wide overflow. |
| |
| // Initialization still succeeds. |
| SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/false); |
| EXPECT_EQ(SubtypeCheckInfo::kInitialized, child.GetState()); |
| EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext()); |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(child)); |
| |
| // Assignment goes to too-wide Overflow. |
| SubtypeCheckInfo child_of = root.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of.GetState()); |
| EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext()); |
| EXPECT_EQ(MakeBitString({}), GetPathToRoot(child_of)); |
| |
| // Assignment of overflowed child still succeeds. |
| // The path to root is the same. |
| SubtypeCheckInfo child_of2 = child_of.CreateChild(/*assign_next=*/true); |
| EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState()); |
| EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2)); |
| } |
| } |