Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2017 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "subtype_check_info.h" |
| 18 | |
| 19 | #include "gtest/gtest.h" |
| 20 | #include "android-base/logging.h" |
| 21 | |
| 22 | namespace art { |
| 23 | |
| 24 | constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity]; |
| 25 | constexpr size_t BitString::kCapacity; |
| 26 | |
| 27 | }; // namespace art |
| 28 | |
| 29 | using namespace art; // NOLINT |
| 30 | |
| 31 | // These helper functions are only used by the test, |
| 32 | // so they are not in the main BitString class. |
| 33 | std::string Stringify(BitString bit_string) { |
| 34 | std::stringstream ss; |
| 35 | ss << bit_string; |
| 36 | return ss.str(); |
| 37 | } |
| 38 | |
| 39 | BitStringChar MakeBitStringChar(size_t idx, size_t val) { |
| 40 | return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx)); |
| 41 | } |
| 42 | |
| 43 | BitStringChar MakeBitStringChar(size_t val) { |
| 44 | return BitStringChar(val, MinimumBitsToStore(val)); |
| 45 | } |
| 46 | |
| 47 | BitString MakeBitString(std::initializer_list<size_t> values = {}) { |
| 48 | CHECK_GE(BitString::kCapacity, values.size()); |
| 49 | |
Igor Murashkin | 5573c37 | 2017-11-16 13:34:30 -0800 | [diff] [blame] | 50 | BitString bs{}; |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 51 | |
| 52 | size_t i = 0; |
| 53 | for (size_t val : values) { |
| 54 | bs.SetAt(i, MakeBitStringChar(i, val)); |
| 55 | ++i; |
| 56 | } |
| 57 | |
| 58 | return bs; |
| 59 | } |
| 60 | |
| 61 | template <typename T> |
| 62 | size_t AsUint(const T& value) { |
| 63 | size_t uint_value = 0; |
| 64 | memcpy(&uint_value, &value, sizeof(value)); |
| 65 | return uint_value; |
| 66 | } |
| 67 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 68 | // Make max bistring, e.g. BitString[4095,15,2047] for {12,4,11} |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 69 | template <size_t kCount = BitString::kCapacity> |
| 70 | BitString MakeBitStringMax() { |
Igor Murashkin | 5573c37 | 2017-11-16 13:34:30 -0800 | [diff] [blame] | 71 | BitString bs{}; |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 72 | |
| 73 | for (size_t i = 0; i < kCount; ++i) { |
| 74 | bs.SetAt(i, |
| 75 | MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i]))); |
| 76 | } |
| 77 | |
| 78 | return bs; |
| 79 | } |
| 80 | |
| 81 | BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) { |
| 82 | BitString bs = bit_string; |
| 83 | bs.SetAt(i, MakeBitStringChar(i, val)); |
| 84 | return bs; |
| 85 | } |
| 86 | |
| 87 | struct SubtypeCheckInfoTest : public ::testing::Test { |
| 88 | protected: |
Andreas Gampe | fa6a1b0 | 2018-09-07 08:11:55 -0700 | [diff] [blame] | 89 | void SetUp() override { |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 90 | android::base::InitLogging(/*argv=*/nullptr); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 91 | } |
| 92 | |
Andreas Gampe | fa6a1b0 | 2018-09-07 08:11:55 -0700 | [diff] [blame] | 93 | void TearDown() override { |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | static SubtypeCheckInfo MakeSubtypeCheckInfo(BitString path_to_root = {}, |
| 97 | BitStringChar next = {}, |
| 98 | bool overflow = false, |
| 99 | size_t depth = 1u) { |
| 100 | // Depth=1 is good default because it will go through all state transitions, |
| 101 | // and its children will also go through all state transitions. |
| 102 | return SubtypeCheckInfo(path_to_root, next, overflow, depth); |
| 103 | } |
| 104 | |
| 105 | static SubtypeCheckInfo MakeSubtypeCheckInfoInfused(BitString bs = {}, |
| 106 | bool overflow = false, |
| 107 | size_t depth = 1u) { |
| 108 | // Depth=1 is good default because it will go through all state transitions, |
| 109 | // and its children will also go through all state transitions. |
| 110 | SubtypeCheckBits iod; |
| 111 | iod.bitstring_ = bs; |
| 112 | iod.overflow_ = overflow; |
| 113 | return SubtypeCheckInfo::Create(iod, depth); |
| 114 | } |
| 115 | |
| 116 | static SubtypeCheckInfo MakeSubtypeCheckInfoUnchecked(BitString bs = {}, |
| 117 | bool overflow = false, |
| 118 | size_t depth = 1u) { |
| 119 | // Depth=1 is good default because it will go through all state transitions, |
| 120 | // and its children will also go through all state transitions. |
| 121 | return SubtypeCheckInfo::MakeUnchecked(bs, overflow, depth); |
| 122 | } |
| 123 | |
Andreas Gampe | bc802de | 2018-06-20 17:24:11 -0700 | [diff] [blame] | 124 | static bool HasNext(const SubtypeCheckInfo& io) { |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 125 | return io.HasNext(); |
| 126 | } |
| 127 | |
Andreas Gampe | bc802de | 2018-06-20 17:24:11 -0700 | [diff] [blame] | 128 | static BitString GetPathToRoot(const SubtypeCheckInfo& io) { |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 129 | return io.GetPathToRoot(); |
| 130 | } |
| 131 | |
| 132 | // Create an SubtypeCheckInfo with the same depth, but with everything else reset. |
| 133 | // Returns: SubtypeCheckInfo in the Uninitialized state. |
Stephen Hines | 48ba197 | 2018-09-24 13:35:54 -0700 | [diff] [blame] | 134 | static SubtypeCheckInfo CopyCleared(const SubtypeCheckInfo& sc) { |
Igor Murashkin | 5573c37 | 2017-11-16 13:34:30 -0800 | [diff] [blame] | 135 | SubtypeCheckInfo cleared_copy{}; |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 136 | cleared_copy.depth_ = sc.depth_; |
| 137 | DCHECK_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState()); |
| 138 | return cleared_copy; |
| 139 | } |
| 140 | }; |
| 141 | |
| 142 | const char* GetExpectedMessageForDeathTest(const char* msg) { |
| 143 | #ifdef ART_TARGET_ANDROID |
| 144 | // On Android, dcheck failure messages go to logcat, |
| 145 | // which gtest death tests does not check, and thus the tests would fail with |
| 146 | // "unexpected message ''" |
| 147 | UNUSED(msg); |
| 148 | return ""; // Still ensures there was a bad return code, but match anything. |
| 149 | #else |
| 150 | return msg; |
| 151 | #endif |
| 152 | } |
| 153 | |
| 154 | TEST_F(SubtypeCheckInfoTest, IllegalValues) { |
| 155 | // This test relies on BitString being at least 3 large. |
| 156 | // It will need to be updated otherwise. |
| 157 | ASSERT_LE(3u, BitString::kCapacity); |
| 158 | |
| 159 | // Illegal values during construction would cause a Dcheck failure and crash. |
| 160 | ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 161 | /*next=*/MakeBitStringChar(0), |
| 162 | /*overflow=*/false, |
| 163 | /*depth=*/0u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 164 | GetExpectedMessageForDeathTest("Path was too long for the depth")); |
| 165 | ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({1u, 1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 166 | /*overflow=*/false, |
| 167 | /*depth=*/0u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 168 | GetExpectedMessageForDeathTest("Bitstring too long for depth")); |
| 169 | ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 170 | /*next=*/MakeBitStringChar(0), |
| 171 | /*overflow=*/false, |
| 172 | /*depth=*/1u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 173 | GetExpectedMessageForDeathTest("Expected \\(Assigned\\|Initialized\\) " |
| 174 | "state to have >0 Next value")); |
| 175 | ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({0u, 2u, 1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 176 | /*overflow=*/false, |
| 177 | /*depth=*/2u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 178 | GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| 179 | ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 2u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 180 | /*next=*/MakeBitStringChar(1u), |
| 181 | /*overflow=*/false, |
| 182 | /*depth=*/2u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 183 | GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| 184 | ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 1u, 1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 185 | /*next=*/MakeBitStringChar(0), |
| 186 | /*overflow=*/false, |
| 187 | /*depth=*/3u), |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 188 | GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); |
| 189 | |
| 190 | // These are really slow (~1sec per death test on host), |
| 191 | // keep them down to a minimum. |
| 192 | } |
| 193 | |
| 194 | TEST_F(SubtypeCheckInfoTest, States) { |
| 195 | EXPECT_EQ(SubtypeCheckInfo::kUninitialized, MakeSubtypeCheckInfo().GetState()); |
| 196 | EXPECT_EQ(SubtypeCheckInfo::kInitialized, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 197 | MakeSubtypeCheckInfo(/*path_to_root=*/{}, /*next=*/MakeBitStringChar(1)).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 198 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 199 | MakeSubtypeCheckInfo(/*path_to_root=*/{}, |
| 200 | /*next=*/MakeBitStringChar(1), |
| 201 | /*overflow=*/true, |
| 202 | /*depth=*/1u).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 203 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 204 | MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitString({1u}), |
| 205 | /*next=*/MakeBitStringChar(1), |
| 206 | /*overflow=*/false, |
| 207 | /*depth=*/1u).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 208 | |
| 209 | // Test edge conditions: depth == BitString::kCapacity (No Next value). |
| 210 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 211 | MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| 212 | /*next=*/MakeBitStringChar(0), |
| 213 | /*overflow=*/false, |
| 214 | /*depth=*/BitString::kCapacity).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 215 | EXPECT_EQ(SubtypeCheckInfo::kInitialized, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 216 | MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax<BitString::kCapacity - 1u>(), |
| 217 | /*next=*/MakeBitStringChar(0), |
| 218 | /*overflow=*/false, |
| 219 | /*depth=*/BitString::kCapacity).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 220 | // Test edge conditions: depth > BitString::kCapacity (Must overflow). |
| 221 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 222 | MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| 223 | /*next=*/MakeBitStringChar(0), |
| 224 | /*overflow=*/true, |
| 225 | /*depth=*/BitString::kCapacity + 1u).GetState()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 226 | } |
| 227 | |
| 228 | TEST_F(SubtypeCheckInfoTest, NextValue) { |
| 229 | // Validate "Next" is correctly aliased as the Bitstring[Depth] character. |
| 230 | EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 231 | /*overflow=*/false, |
| 232 | /*depth=*/0u).GetNext()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 233 | EXPECT_EQ(MakeBitStringChar(2u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 234 | /*overflow=*/false, |
| 235 | /*depth=*/1u).GetNext()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 236 | EXPECT_EQ(MakeBitStringChar(3u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 237 | /*overflow=*/false, |
| 238 | /*depth=*/2u).GetNext()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 239 | EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({0u, 2u, 1u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 240 | /*overflow=*/false, |
| 241 | /*depth=*/2u).GetNext()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 242 | // Test edge conditions: depth == BitString::kCapacity (No Next value). |
| 243 | EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 244 | /*overflow=*/false, |
| 245 | /*depth=*/BitString::kCapacity))); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 246 | // Anything with depth >= BitString::kCapacity has no next value. |
| 247 | EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 248 | /*overflow=*/false, |
| 249 | /*depth=*/BitString::kCapacity + 1u))); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 250 | EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax(), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 251 | /*overflow=*/false, |
| 252 | /*depth=*/std::numeric_limits<size_t>::max()))); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 253 | } |
| 254 | |
| 255 | template <size_t kPos = BitString::kCapacity> |
| 256 | size_t LenForPos() { return BitString::GetBitLengthTotalAtPosition(kPos); } |
| 257 | |
| 258 | TEST_F(SubtypeCheckInfoTest, EncodedPathToRoot) { |
| 259 | using StorageType = BitString::StorageType; |
| 260 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 261 | SubtypeCheckInfo sci = |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 262 | MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(), |
| 263 | /*next=*/BitStringChar{}, |
| 264 | /*overflow=*/false, |
| 265 | /*depth=*/BitString::kCapacity); |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 266 | // 0b000...111 where LSB == 1, and trailing 1s = the maximum bitstring representation. |
| 267 | EXPECT_EQ(MaxInt<StorageType>(LenForPos()), sci.GetEncodedPathToRoot()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 268 | |
| 269 | // The rest of this test is written assuming kCapacity == 3 for convenience. |
| 270 | // Please update the test if this changes. |
| 271 | ASSERT_EQ(3u, BitString::kCapacity); |
| 272 | ASSERT_EQ(12u, BitString::kBitSizeAtPosition[0]); |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 273 | ASSERT_EQ(4u, BitString::kBitSizeAtPosition[1]); |
| 274 | ASSERT_EQ(11u, BitString::kBitSizeAtPosition[2]); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 275 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 276 | SubtypeCheckInfo sci2 = |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 277 | MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 278 | /*overflow=*/false, |
| 279 | /*depth=*/BitString::kCapacity); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 280 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 281 | #define MAKE_ENCODED_PATH(pos0, pos1, pos2) \ |
| 282 | (((pos0) << 0) | \ |
| 283 | ((pos1) << BitString::kBitSizeAtPosition[0]) | \ |
| 284 | ((pos2) << (BitString::kBitSizeAtPosition[0] + BitString::kBitSizeAtPosition[1]))) |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 285 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 286 | EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| 287 | sci2.GetEncodedPathToRoot()); |
| 288 | EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b11111111111), |
| 289 | sci2.GetEncodedPathToRootMask()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 290 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 291 | SubtypeCheckInfo sci3 = |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 292 | MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 293 | /*overflow=*/false, |
| 294 | /*depth=*/BitString::kCapacity - 1u); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 295 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 296 | EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| 297 | sci3.GetEncodedPathToRoot()); |
| 298 | EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0), |
| 299 | sci3.GetEncodedPathToRootMask()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 300 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 301 | SubtypeCheckInfo sci4 = |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 302 | MakeSubtypeCheckInfoUnchecked(MakeBitString({0b1010101u}), |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 303 | /*overflow=*/false, |
| 304 | /*depth=*/BitString::kCapacity - 2u); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 305 | |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 306 | EXPECT_EQ(MAKE_ENCODED_PATH(0b1010101u, 0b0000, 0b0), sci4.GetEncodedPathToRoot()); |
| 307 | EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b0000, 0b0), |
| 308 | sci4.GetEncodedPathToRootMask()); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 309 | } |
| 310 | |
| 311 | TEST_F(SubtypeCheckInfoTest, NewForRoot) { |
Vladimir Marko | dc682aa | 2018-01-04 18:42:57 +0000 | [diff] [blame] | 312 | SubtypeCheckInfo sci = SubtypeCheckInfo::CreateRoot(); |
| 313 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, sci.GetState()); // Root is always assigned. |
| 314 | EXPECT_EQ(0u, GetPathToRoot(sci).Length()); // Root's path length is 0. |
| 315 | EXPECT_TRUE(HasNext(sci)); // Root always has a "Next". |
| 316 | EXPECT_EQ(MakeBitStringChar(1u), sci.GetNext()); // Next>=1 to disambiguate from Uninitialized. |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 317 | } |
| 318 | |
| 319 | TEST_F(SubtypeCheckInfoTest, CopyCleared) { |
| 320 | SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| 321 | EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| 322 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 323 | SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 324 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| 325 | EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| 326 | EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| 327 | |
| 328 | SubtypeCheckInfo cleared_copy = CopyCleared(childC); |
| 329 | EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState()); |
| 330 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy)); |
| 331 | |
| 332 | // CopyCleared is just a thin wrapper around value-init and providing the depth. |
| 333 | SubtypeCheckInfo cleared_copy_value = |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 334 | SubtypeCheckInfo::Create(SubtypeCheckBits{}, /*depth=*/1u); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 335 | EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy_value.GetState()); |
| 336 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy_value)); |
| 337 | } |
| 338 | |
| 339 | TEST_F(SubtypeCheckInfoTest, NewForChild2) { |
| 340 | SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| 341 | EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| 342 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 343 | SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 344 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| 345 | EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| 346 | EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| 347 | } |
| 348 | |
| 349 | TEST_F(SubtypeCheckInfoTest, NewForChild) { |
| 350 | SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); |
| 351 | EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); |
| 352 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 353 | SubtypeCheckInfo childA = root.CreateChild(/*assign_next=*/false); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 354 | EXPECT_EQ(SubtypeCheckInfo::kInitialized, childA.GetState()); |
| 355 | EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); // Next unchanged for Initialize. |
| 356 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(childA)); |
| 357 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 358 | SubtypeCheckInfo childB = root.CreateChild(/*assign_next=*/false); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 359 | EXPECT_EQ(SubtypeCheckInfo::kInitialized, childB.GetState()); |
| 360 | EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); // Next unchanged for Initialize. |
| 361 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(childB)); |
| 362 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 363 | SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 364 | EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState()); |
| 365 | EXPECT_EQ(MakeBitStringChar(2u), root.GetNext()); // Next incremented for Assign. |
| 366 | EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC)); |
| 367 | |
| 368 | { |
| 369 | size_t cur_depth = 1u; |
| 370 | SubtypeCheckInfo latest_child = childC; |
| 371 | while (cur_depth != BitString::kCapacity) { |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 372 | latest_child = latest_child.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 373 | ASSERT_EQ(SubtypeCheckInfo::kAssigned, latest_child.GetState()); |
| 374 | ASSERT_EQ(cur_depth + 1u, GetPathToRoot(latest_child).Length()); |
| 375 | cur_depth++; |
| 376 | } |
| 377 | |
| 378 | // Future assignments will result in a too-deep overflow. |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 379 | SubtypeCheckInfo child_of_deep = latest_child.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 380 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep.GetState()); |
| 381 | EXPECT_EQ(GetPathToRoot(latest_child), GetPathToRoot(child_of_deep)); |
| 382 | |
| 383 | // Assignment of too-deep overflow also causes overflow. |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 384 | SubtypeCheckInfo child_of_deep_2 = child_of_deep.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 385 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep_2.GetState()); |
| 386 | EXPECT_EQ(GetPathToRoot(child_of_deep), GetPathToRoot(child_of_deep_2)); |
| 387 | } |
| 388 | |
| 389 | { |
| 390 | size_t cur_next = 2u; |
| 391 | while (true) { |
| 392 | if (cur_next == MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[0u])) { |
| 393 | break; |
| 394 | } |
| 395 | |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 396 | SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 397 | ASSERT_EQ(SubtypeCheckInfo::kAssigned, child.GetState()); |
| 398 | ASSERT_EQ(MakeBitStringChar(cur_next+1u), root.GetNext()); |
| 399 | ASSERT_EQ(MakeBitString({cur_next}), GetPathToRoot(child)); |
| 400 | |
| 401 | cur_next++; |
| 402 | } |
| 403 | // Now the root will be in a state that further assigns will be too-wide overflow. |
| 404 | |
| 405 | // Initialization still succeeds. |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 406 | SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/false); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 407 | EXPECT_EQ(SubtypeCheckInfo::kInitialized, child.GetState()); |
| 408 | EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext()); |
| 409 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(child)); |
| 410 | |
| 411 | // Assignment goes to too-wide Overflow. |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 412 | SubtypeCheckInfo child_of = root.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 413 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of.GetState()); |
| 414 | EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext()); |
| 415 | EXPECT_EQ(MakeBitString({}), GetPathToRoot(child_of)); |
| 416 | |
| 417 | // Assignment of overflowed child still succeeds. |
| 418 | // The path to root is the same. |
Andreas Gampe | 98ea9d9 | 2018-10-19 14:06:15 -0700 | [diff] [blame] | 419 | SubtypeCheckInfo child_of2 = child_of.CreateChild(/*assign_next=*/true); |
Igor Murashkin | f31a00c | 2017-10-27 10:52:07 -0700 | [diff] [blame] | 420 | EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState()); |
| 421 | EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2)); |
| 422 | } |
| 423 | } |