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.
Stringify(BitString bit_string)33 std::string Stringify(BitString bit_string) {
34 std::stringstream ss;
35 ss << bit_string;
36 return ss.str();
37 }
38
MakeBitStringChar(size_t idx,size_t val)39 BitStringChar MakeBitStringChar(size_t idx, size_t val) {
40 return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx));
41 }
42
MakeBitStringChar(size_t val)43 BitStringChar MakeBitStringChar(size_t val) {
44 return BitStringChar(val, MinimumBitsToStore(val));
45 }
46
MakeBitString(std::initializer_list<size_t> values={})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>
AsUint(const T & value)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>
MakeBitStringMax()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
SetBitStringCharAt(BitString bit_string,size_t i,size_t val)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:
SetUpSubtypeCheckInfoTest89 void SetUp() override {
90 android::base::InitLogging(/*argv=*/nullptr);
91 }
92
TearDownSubtypeCheckInfoTest93 void TearDown() override {
94 }
95
MakeSubtypeCheckInfoSubtypeCheckInfoTest96 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
MakeSubtypeCheckInfoInfusedSubtypeCheckInfoTest105 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
MakeSubtypeCheckInfoUncheckedSubtypeCheckInfoTest116 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
HasNextSubtypeCheckInfoTest124 static bool HasNext(const SubtypeCheckInfo& io) {
125 return io.HasNext();
126 }
127
GetPathToRootSubtypeCheckInfoTest128 static BitString GetPathToRoot(const 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.
CopyClearedSubtypeCheckInfoTest134 static SubtypeCheckInfo CopyCleared(const 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
GetExpectedMessageForDeathTest(const char * msg)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
TEST_F(SubtypeCheckInfoTest,IllegalValues)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
TEST_F(SubtypeCheckInfoTest,States)194 TEST_F(SubtypeCheckInfoTest, States) {
195 EXPECT_EQ(SubtypeCheckInfo::kUninitialized, MakeSubtypeCheckInfo().GetState());
196 EXPECT_EQ(SubtypeCheckInfo::kInitialized,
197 MakeSubtypeCheckInfo(/*path_to_root=*/{}, /*next=*/MakeBitStringChar(1)).GetState());
198 EXPECT_EQ(SubtypeCheckInfo::kOverflowed,
199 MakeSubtypeCheckInfo(/*path_to_root=*/{},
200 /*next=*/MakeBitStringChar(1),
201 /*overflow=*/true,
202 /*depth=*/1u).GetState());
203 EXPECT_EQ(SubtypeCheckInfo::kAssigned,
204 MakeSubtypeCheckInfo(/*path_to_root=*/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_to_root=*/MakeBitStringMax(),
212 /*next=*/MakeBitStringChar(0),
213 /*overflow=*/false,
214 /*depth=*/BitString::kCapacity).GetState());
215 EXPECT_EQ(SubtypeCheckInfo::kInitialized,
216 MakeSubtypeCheckInfo(/*path_to_root=*/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_to_root=*/MakeBitStringMax(),
223 /*next=*/MakeBitStringChar(0),
224 /*overflow=*/true,
225 /*depth=*/BitString::kCapacity + 1u).GetState());
226 }
227
TEST_F(SubtypeCheckInfoTest,NextValue)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>
LenForPos()256 size_t LenForPos() { return BitString::GetBitLengthTotalAtPosition(kPos); }
257
TEST_F(SubtypeCheckInfoTest,EncodedPathToRoot)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
TEST_F(SubtypeCheckInfoTest,NewForRoot)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
TEST_F(SubtypeCheckInfoTest,CopyCleared)319 TEST_F(SubtypeCheckInfoTest, CopyCleared) {
320 SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
321 EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());
322
323 SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/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
TEST_F(SubtypeCheckInfoTest,NewForChild2)339 TEST_F(SubtypeCheckInfoTest, NewForChild2) {
340 SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
341 EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());
342
343 SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/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
TEST_F(SubtypeCheckInfoTest,NewForChild)349 TEST_F(SubtypeCheckInfoTest, NewForChild) {
350 SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
351 EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());
352
353 SubtypeCheckInfo childA = root.CreateChild(/*assign_next=*/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_next=*/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_next=*/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_next=*/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_next=*/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_next=*/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_next=*/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_next=*/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_next=*/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_next=*/true);
420 EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState());
421 EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2));
422 }
423 }
424