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 50 BitString bs{}; 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 68 // Make max bistring, e.g. BitString[4095,15,2047] for {12,4,11} 69 template <size_t kCount = BitString::kCapacity> 70 BitString MakeBitStringMax() { 71 BitString bs{}; 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: 89 virtual void SetUp() { 90 android::base::InitLogging(/*argv*/nullptr); 91 } 92 93 virtual void TearDown() { 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 124 static bool HasNext(SubtypeCheckInfo io) { 125 return io.HasNext(); 126 } 127 128 static BitString GetPathToRoot(SubtypeCheckInfo io) { 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. 134 static SubtypeCheckInfo CopyCleared(SubtypeCheckInfo sc) { 135 SubtypeCheckInfo cleared_copy{}; 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}), 161 /*next*/MakeBitStringChar(0), 162 /*overflow*/false, 163 /*depth*/0u), 164 GetExpectedMessageForDeathTest("Path was too long for the depth")); 165 ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({1u, 1u}), 166 /*overflow*/false, 167 /*depth*/0u), 168 GetExpectedMessageForDeathTest("Bitstring too long for depth")); 169 ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}), 170 /*next*/MakeBitStringChar(0), 171 /*overflow*/false, 172 /*depth*/1u), 173 GetExpectedMessageForDeathTest("Expected \\(Assigned\\|Initialized\\) " 174 "state to have >0 Next value")); 175 ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({0u, 2u, 1u}), 176 /*overflow*/false, 177 /*depth*/2u), 178 GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); 179 ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 2u}), 180 /*next*/MakeBitStringChar(1u), 181 /*overflow*/false, 182 /*depth*/2u), 183 GetExpectedMessageForDeathTest("Path to root had non-0s following 0s")); 184 ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 1u, 1u}), 185 /*next*/MakeBitStringChar(0), 186 /*overflow*/false, 187 /*depth*/3u), 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, 197 MakeSubtypeCheckInfo(/*path*/{}, /*next*/MakeBitStringChar(1)).GetState()); 198 EXPECT_EQ(SubtypeCheckInfo::kOverflowed, 199 MakeSubtypeCheckInfo(/*path*/{}, 200 /*next*/MakeBitStringChar(1), 201 /*overflow*/true, 202 /*depth*/1u).GetState()); 203 EXPECT_EQ(SubtypeCheckInfo::kAssigned, 204 MakeSubtypeCheckInfo(/*path*/MakeBitString({1u}), 205 /*next*/MakeBitStringChar(1), 206 /*overflow*/false, 207 /*depth*/1u).GetState()); 208 209 // Test edge conditions: depth == BitString::kCapacity (No Next value). 210 EXPECT_EQ(SubtypeCheckInfo::kAssigned, 211 MakeSubtypeCheckInfo(/*path*/MakeBitStringMax(), 212 /*next*/MakeBitStringChar(0), 213 /*overflow*/false, 214 /*depth*/BitString::kCapacity).GetState()); 215 EXPECT_EQ(SubtypeCheckInfo::kInitialized, 216 MakeSubtypeCheckInfo(/*path*/MakeBitStringMax<BitString::kCapacity - 1u>(), 217 /*next*/MakeBitStringChar(0), 218 /*overflow*/false, 219 /*depth*/BitString::kCapacity).GetState()); 220 // Test edge conditions: depth > BitString::kCapacity (Must overflow). 221 EXPECT_EQ(SubtypeCheckInfo::kOverflowed, 222 MakeSubtypeCheckInfo(/*path*/MakeBitStringMax(), 223 /*next*/MakeBitStringChar(0), 224 /*overflow*/true, 225 /*depth*/BitString::kCapacity + 1u).GetState()); 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}), 231 /*overflow*/false, 232 /*depth*/0u).GetNext()); 233 EXPECT_EQ(MakeBitStringChar(2u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), 234 /*overflow*/false, 235 /*depth*/1u).GetNext()); 236 EXPECT_EQ(MakeBitStringChar(3u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}), 237 /*overflow*/false, 238 /*depth*/2u).GetNext()); 239 EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({0u, 2u, 1u}), 240 /*overflow*/false, 241 /*depth*/2u).GetNext()); 242 // Test edge conditions: depth == BitString::kCapacity (No Next value). 243 EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), 244 /*overflow*/false, 245 /*depth*/BitString::kCapacity))); 246 // Anything with depth >= BitString::kCapacity has no next value. 247 EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(), 248 /*overflow*/false, 249 /*depth*/BitString::kCapacity + 1u))); 250 EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax(), 251 /*overflow*/false, 252 /*depth*/std::numeric_limits<size_t>::max()))); 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 261 SubtypeCheckInfo sci = 262 MakeSubtypeCheckInfo(/*path_to_root*/MakeBitStringMax(), 263 /*next*/BitStringChar{}, 264 /*overflow*/false, 265 /*depth*/BitString::kCapacity); 266 // 0b000...111 where LSB == 1, and trailing 1s = the maximum bitstring representation. 267 EXPECT_EQ(MaxInt<StorageType>(LenForPos()), sci.GetEncodedPathToRoot()); 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]); 273 ASSERT_EQ(4u, BitString::kBitSizeAtPosition[1]); 274 ASSERT_EQ(11u, BitString::kBitSizeAtPosition[2]); 275 276 SubtypeCheckInfo sci2 = 277 MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), 278 /*overflow*/false, 279 /*depth*/BitString::kCapacity); 280 281 #define MAKE_ENCODED_PATH(pos0, pos1, pos2) \ 282 (((pos0) << 0) | \ 283 ((pos1) << BitString::kBitSizeAtPosition[0]) | \ 284 ((pos2) << (BitString::kBitSizeAtPosition[0] + BitString::kBitSizeAtPosition[1]))) 285 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()); 290 291 SubtypeCheckInfo sci3 = 292 MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), 293 /*overflow*/false, 294 /*depth*/BitString::kCapacity - 1u); 295 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()); 300 301 SubtypeCheckInfo sci4 = 302 MakeSubtypeCheckInfoUnchecked(MakeBitString({0b1010101u}), 303 /*overflow*/false, 304 /*depth*/BitString::kCapacity - 2u); 305 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()); 309 } 310 311 TEST_F(SubtypeCheckInfoTest, NewForRoot) { 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. 317 } 318 319 TEST_F(SubtypeCheckInfoTest, CopyCleared) { 320 SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot(); 321 EXPECT_EQ(MakeBitStringChar(1u), root.GetNext()); 322 323 SubtypeCheckInfo childC = root.CreateChild(/*assign*/true); 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 = 334 SubtypeCheckInfo::Create(SubtypeCheckBits{}, /*depth*/1u); 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 343 SubtypeCheckInfo childC = root.CreateChild(/*assign*/true); 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 353 SubtypeCheckInfo childA = root.CreateChild(/*assign*/false); 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 358 SubtypeCheckInfo childB = root.CreateChild(/*assign*/false); 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 363 SubtypeCheckInfo childC = root.CreateChild(/*assign*/true); 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) { 372 latest_child = latest_child.CreateChild(/*assign*/true); 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. 379 SubtypeCheckInfo child_of_deep = latest_child.CreateChild(/*assign*/true); 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. 384 SubtypeCheckInfo child_of_deep_2 = child_of_deep.CreateChild(/*assign*/true); 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 396 SubtypeCheckInfo child = root.CreateChild(/*assign*/true); 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. 406 SubtypeCheckInfo child = root.CreateChild(/*assign*/false); 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. 412 SubtypeCheckInfo child_of = root.CreateChild(/*assign*/true); 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. 419 SubtypeCheckInfo child_of2 = child_of.CreateChild(/*assign*/true); 420 EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState()); 421 EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2)); 422 } 423 } 424
