diff options
| -rw-r--r-- | runtime/Android.bp | 1 | ||||
| -rw-r--r-- | runtime/subtype_check_bits.h | 66 | ||||
| -rw-r--r-- | runtime/subtype_check_info.h | 527 | ||||
| -rw-r--r-- | runtime/subtype_check_info_test.cc | 421 |
4 files changed, 1015 insertions, 0 deletions
diff --git a/runtime/Android.bp b/runtime/Android.bp index d9bb04ebac..52ec782de8 100644 --- a/runtime/Android.bp +++ b/runtime/Android.bp @@ -616,6 +616,7 @@ art_cc_test { "prebuilt_tools_test.cc", "reference_table_test.cc", "runtime_callbacks_test.cc", + "subtype_check_info_test.cc", "thread_pool_test.cc", "transaction_test.cc", "type_lookup_table_test.cc", diff --git a/runtime/subtype_check_bits.h b/runtime/subtype_check_bits.h new file mode 100644 index 0000000000..4305ff849a --- /dev/null +++ b/runtime/subtype_check_bits.h @@ -0,0 +1,66 @@ +/* + * 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. + */ + +#ifndef ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ +#define ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ + +#include "base/bit_string.h" +#include "base/bit_struct.h" +#include "base/bit_utils.h" + +namespace art { + +/** + * The SubtypeCheckBits memory layout (in bits): + * + * Variable + * | + * <---- up to 23 bits ----> v +---> 1 bit + * | + * +-------------------------+--------+-----------+---++ + * | Bitstring | | + * +-------------------------+--------+-----------+ | + * | Path To Root | Next | (unused) | OF | + * +---+---------------------+--------+ | | + * | | | | | ... | | (0....0) | | + * +---+---------------------+--------+-----------+----+ + * MSB LSB + * + * The bitstring takes up to 23 bits; anything exceeding that is truncated: + * - Path To Root is a list of chars, encoded as a BitString: + * starting at the root (in MSB), each character is a sibling index unique to the parent, + * Paths longer than BitString::kCapacity are truncated to fit within the BitString. + * - Next is a single BitStringChar (immediatelly following Path To Root) + * When new children are assigned paths, they get allocated the parent's Next value. + * The next value is subsequently incremented. + * + * The exact bit position of (unused) is variable-length: + * In the cases that the "Path To Root" + "Next" does not fill up the entire + * BitString capacity, the remaining bits are (unused) and left as 0s. + * + * There is also an additional "OF" (overflow) field to indicate that the + * PathToRoot has been truncated. + * + * See subtype_check.h and subtype_check_info.h for more details. + */ +BITSTRUCT_DEFINE_START(SubtypeCheckBits, /*size*/ BitString::BitStructSizeOf() + 1u) + BitStructUint</*lsb*/0, /*width*/1> overflow_; + BitStructField<BitString, /*lsb*/1> bitstring_; +BITSTRUCT_DEFINE_END(SubtypeCheckBits); + +} // namespace art + +#endif // ART_RUNTIME_SUBTYPE_CHECK_BITS_H_ diff --git a/runtime/subtype_check_info.h b/runtime/subtype_check_info.h new file mode 100644 index 0000000000..f60e0ac661 --- /dev/null +++ b/runtime/subtype_check_info.h @@ -0,0 +1,527 @@ +/* + * 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. + */ + +#ifndef ART_RUNTIME_SUBTYPE_CHECK_INFO_H_ +#define ART_RUNTIME_SUBTYPE_CHECK_INFO_H_ + +#include "base/bit_string.h" +#include "subtype_check_bits.h" + +// Forward-declare for testing purposes. +struct SubtypeCheckInfoTest; + +namespace art { + +/** + * SubtypeCheckInfo is a logical label for the class SubtypeCheck data, which is necessary to + * perform efficient O(1) subtype comparison checks. See also subtype_check.h + * for the more general explanation of how the labels are used overall. + * + * For convenience, we also store the class depth within an SubtypeCheckInfo, since nearly all + * calculations are dependent on knowing the depth of the class. + * + * A SubtypeCheckInfo logically has: + * * Depth - How many levels up to the root (j.l.Object)? + * * PathToRoot - Possibly truncated BitString that encodes path to root + * * Next - The value a newly inserted Child would get appended to its path. + * * Overflow - If this path can never become a full path. + * + * Depending on the values of the above, it can be in one of these logical states, + * which are introduced in subtype_check.h: + * + * Transient States Terminal States + * + * +-----------------+ +--------------------+ +-------------------+ + * | | | | | | + * | Uninitialized | +---> Initialized | +---> Assigned | + * | | | | | | + * +--------+--------+ +---------+----------+ +-------------------+ + * | | + * | | + * | | +-------------------+ + * | +----------------> | + * | | Overflowed | + * +-----------------------------------------> | + * +-------------------+ + * + * Invariants: + * + * Initialized => Parent >= Initialized + * + * Assigned => Parent == Assigned + * + * Overflowed => Parent == Overflowed || Parent.Next == Overflowed + * + * Thread-safety invariants: + * + * Initialized => Parent == Assigned + * // For a class that has an Initialized bitstring, its superclass needs to have an + * // Assigned bitstring since if its super class's bitstring is not Assigned yet, + * // once it becomes Assigned, we cannot update its children's bitstrings to maintain + * // all the tree invariants (below) atomically. + * + * -------------------------------------------------------------------------------------------- + * Knowing these transitions above, we can more closely define the various terms and operations: + * + * Definitions: + * (see also base/bit_string.h definitions). + * + * Depth := Distance(Root, Class) + * Safe(Depth) := Min(Depth, MaxBitstringLen) + * PathToRoot := Bitstring[0..Safe(Depth)) + * Next := Bitstring[Depth] + * OF ∈ {False, True} + * TruncPath(D) := PathToRoot[0..D) + * + * Local Invariants: + * + * Uninitialized <=> StrLen(PathToRoot) == 0 + * Next == 0 + * Initialized <=> StrLen(PathToRoot) < Depth + * Next == 0 + * Assigned <=> StrLen(PathToRoot) == Depth + * Next > 1 + * Overflowed <=> OF == True + * + * Tree Invariants: + * + * Uninitialized => + * forall child ∈ Children(Class): + * child.State == Uninitialized + * + * Assigned => + * forall child ∈ Children(Class): + * Next > Child.PathToRoot[Child.Depth-1] + * + * ! Uninitialized => + * forall ancestor ∈ Ancestors(Class): + * TruncPath(ancestor.Depth) == ancestor.PathToRoot + * forall unrelated ∈ (Classes - Ancestors(Class)) + * s.t. unrelated.State == Assigned: + * TruncPath(unrelated.Depth) != unrelated.PathToRoot + * + * Thread-safety invariants: + * + * Initialized <=> StrLen(PathToRoot) == Safe(Depth - 1) + * // Initialized State corresponds to exactly 1 bitstring. + * // Cannot transition from Initialized to Initialized. + */ +struct SubtypeCheckInfo { + // See above documentation for possible state transitions. + enum State { + kUninitialized, + kInitialized, + kAssigned, + kOverflowed + }; + + // The result of a "src IsSubType target" check: + enum Result { + kUnknownSubtypeOf, // Not enough data. Operand states weren't high enough. + kNotSubtypeOf, // Enough data. src is not a subchild of the target. + kSubtypeOf // Enough data. src is a subchild of the target. + }; + + // Chop off the depth, returning only the bitstring+of state. + // (Used to store into memory, since storing the depth would be redundant.) + SubtypeCheckBits GetSubtypeCheckBits() const { + return bitstring_and_of_; + } + + // Create from the depth and the bitstring+of state. + // This is done for convenience to avoid passing in "depth" everywhere, + // since our current state is almost always a function of depth. + static SubtypeCheckInfo Create(SubtypeCheckBits compressed_value, size_t depth) { + SubtypeCheckInfo io; + io.depth_ = depth; + io.bitstring_and_of_ = compressed_value; + io.DcheckInvariants(); + return io; + } + + // Is this a subtype of the target? + // + // The current state must be at least Initialized, and the target state + // must be Assigned, otherwise the result will return kUnknownSubtypeOf. + // + // Normally, return kSubtypeOf or kNotSubtypeOf. + Result IsSubtypeOf(const SubtypeCheckInfo& target) { + if (target.GetState() != SubtypeCheckInfo::kAssigned) { + return Result::kUnknownSubtypeOf; + } else if (GetState() == SubtypeCheckInfo::kUninitialized) { + return Result::kUnknownSubtypeOf; + } + + BitString::StorageType source_value = GetEncodedPathToRoot(); + BitString::StorageType target_value = target.GetEncodedPathToRoot(); + BitString::StorageType target_mask = target.GetEncodedPathToRootMask(); + + bool result = (source_value & target_mask) == (target_value); + if (result) { + DCHECK_EQ(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot()) + << "Source: " << *this << ", Target: " << target; + } else { + DCHECK_NE(GetPathToRoot().Truncate(target.GetSafeDepth()), target.GetPathToRoot()) + << "Source: " << *this << ", Target: " << target; + } + + // Note: We could've also used shifts here, as described in subtype_check_bits.h, + // but it doesn't make much of a difference in the Runtime since we aren't trying to optimize + // for code size. + + return result ? Result::kSubtypeOf : Result::kNotSubtypeOf; + } + + // Returns a new root SubtypeCheckInfo with a blank PathToRoot. + // Post-condition: The return valued has an Assigned state. + static SubtypeCheckInfo CreateRoot() { + SubtypeCheckInfo io{}; // NOLINT + io.depth_ = 0u; + io.SetNext(io.GetNext() + 1u); + + // The root is always considered assigned once it is no longer Initialized. + DCHECK_EQ(SubtypeCheckInfo::kAssigned, io.GetState()); + return io; + } + + // Copies the current PathToRoot into the child. + // + // If assign_next is true, then also assign a new SubtypeCheckInfo for a child by + // assigning the current Next value to its PathToRoot[Depth] component. + // Updates the current Next value as a side effect. + // + // Preconditions: State is either Assigned or Overflowed. + // Returns: A new child >= Initialized state. + SubtypeCheckInfo CreateChild(bool assign_next) { + SubtypeCheckInfo child = *this; // Copy everything (path, next, of). + child.depth_ = depth_ + 1u; + + // Must be Assigned or Overflowed in order to create a subchild. + DCHECK(GetState() == kAssigned || GetState() == kOverflowed) + << "Unexpected bitstring state: " << GetState(); + + // Begin transition to >= Initialized. + + // Always attempt to re-initialize Child's Next value. + // Next must be non-0 to disambiguate it from Uninitialized. + child.MaybeInitNext(); + + // Always clear the inherited Parent's next Value on the child. + OverwriteNextValueFromParent(/*inout*/&child, BitStringChar{}); // NOLINT + + // The state is now Initialized | Overflowed. + DCHECK_NE(kAssigned, child.GetState()) << child.GetBitString(); + DCHECK_NE(kUninitialized, child.GetState()) << child.GetBitString(); + + if (assign_next == false) { + child.DcheckInvariants(); + return child; + } + + // Begin transition to >= Assigned. + + // Assign attempt. + if (HasNext() && !bitstring_and_of_.overflow_) { + // Do not bother assigning if parent had overflowed. + BitStringChar next = GetNext(); + if (next != next.MaximumValue()) { + // The parent's "next" value is now the child's latest path element. + OverwriteNextValueFromParent(/*inout*/&child, next); + // Update self next value, so that future CreateChild calls + // do not get the same path value. + SetNext(next + 1u); + } else { + child.MarkOverflowed(); // Too wide. + } + } else { + child.MarkOverflowed(); // Too deep, or parent was already overflowed. + } + + // The state is now Assigned | Overflowed. + DCHECK(child.GetState() == kAssigned || child.GetState() == kOverflowed); + + child.DcheckInvariants(); + return child; + } + + // Get the current state (Uninitialized, Initialized, Assigned, or Overflowed). + // See the "SubtypeCheckInfo" documentation above which explains how a state is determined. + State GetState() const { + if (GetBitString() == BitString{}) { // NOLINT + // Empty bitstring (all 0s) -> uninitialized. + DCHECK(!bitstring_and_of_.overflow_); + return kUninitialized; + } + + if (bitstring_and_of_.overflow_) { + // Overflowed if and only if the OF bit was set. + return kOverflowed; + } + + // Either Assigned or Initialized. + BitString path_to_root = GetPathToRoot(); + + DCHECK(!HasNext() || GetNext() != BitStringChar{}) // NOLINT + << "Expected (Assigned|Initialized) state to have >0 Next value: " + << GetNext() << " path: " << path_to_root; + + if (path_to_root.Length() == depth_) { + return kAssigned; + } + + return kInitialized; + } + + // Retrieve the path to root bitstring as a plain uintN_t value that is amenable to + // be used by a fast check "encoded_src & mask_target == encoded_target". + BitString::StorageType GetEncodedPathToRoot() const { + BitString::StorageType data = static_cast<BitString::StorageType>(GetPathToRoot()); + // Bit strings are logically in the least-significant memory. + // Shift it so the bits are all most-significant. + return data << (BitSizeOf(data) - BitStructSizeOf<BitString>()); + } + + // Retrieve the path to root bitstring mask as a plain uintN_t that is amenable to + // be used by a fast check "encoded_src & mask_target == encoded_target". + BitString::StorageType GetEncodedPathToRootMask() const { + size_t num_bitchars = GetSafeDepth(); + size_t bitlength = BitString::GetBitLengthTotalAtPosition(num_bitchars); + + BitString::StorageType mask_all = + std::numeric_limits<BitString::StorageType>::max(); + BitString::StorageType mask_lsb = + MaskLeastSignificant<BitString::StorageType>( + BitSizeOf<BitString::StorageType>() - bitlength); + + BitString::StorageType result = mask_all & ~mask_lsb; + + // TODO: refactor above code into MaskMostSignificant? + return result; + } + + // Get the "Next" bitchar, assuming that there is one to get. + BitStringChar GetNext() const { + DCHECK(HasNext()); + return GetBitString()[depth_]; + } + + // Try to get the Next value, if there is one. + // Returns: Whether or not there was a Next value. + bool MaybeGetNext(/*out*/BitStringChar* next) const { + DCHECK(next != nullptr); + + if (HasNext()) { + *next = GetBitString()[depth_]; + return true; + } + return false; + } + + private: + // Constructor intended for testing. Runs all invariant checks. + SubtypeCheckInfo(BitString path_to_root, BitStringChar next, bool overflow, size_t depth) { + SubtypeCheckBits iod; + iod.bitstring_ = path_to_root; + iod.overflow_ = overflow; + + bitstring_and_of_ = iod; + depth_ = depth; + + // Len(Path-to-root) <= Depth. + DCHECK_GE(depth_, path_to_root.Length()) + << "Path was too long for the depth, path: " << path_to_root; + + bool did_overlap = false; + if (HasNext()) { + if (kIsDebugBuild) { + did_overlap = (GetNext() != BitStringChar{}); // NOLINT + } + + SetNext(next); + + DCHECK_EQ(next, GetNext()); + } + // "Next" must be set before we can check the invariants. + DcheckInvariants(); + DCHECK(!did_overlap) + << "Path to root overlapped with Next value, path: " << path_to_root; + DCHECK_EQ(path_to_root, GetPathToRoot()); + } + + // Factory intended for testing. Skips DcheckInvariants. + static SubtypeCheckInfo MakeUnchecked(BitString bitstring, bool overflow, size_t depth) { + SubtypeCheckBits iod; + iod.bitstring_ = bitstring; + iod.overflow_ = overflow; + + SubtypeCheckInfo io; + io.depth_ = depth; + io.bitstring_and_of_ = iod; + + return io; + } + + void SetNext(BitStringChar next) { + DCHECK(HasNext()); + BitString bs = GetBitString(); + bs.SetAt(depth_, next); + SetBitString(bs); + } + + void SetNextUnchecked(BitStringChar next) { + BitString bs = GetBitString(); + bs.SetAt(depth_, next); + SetBitStringUnchecked(bs); + } + + void MaybeInitNext() { + if (HasNext()) { + // Clearing out the "Next" value like this + // is often an intermediate operation which temporarily + // violates the invariants. Do not do the extra dchecks. + SetNextUnchecked(BitStringChar{}); // NOLINT + SetNextUnchecked(GetNext()+1u); + } + } + + BitString GetPathToRoot() const { + size_t end = GetSafeDepth(); + return GetBitString().Truncate(end); + } + + bool HasNext() const { + return depth_ < BitString::kCapacity; + } + + void MarkOverflowed() { + bitstring_and_of_.overflow_ = true; + } + + static constexpr bool HasBitStringCharStorage(size_t idx) { + return idx < BitString::kCapacity; + } + + size_t GetSafeDepth() const { + return GetSafeDepth(depth_); + } + + // Get a "safe" depth, one that is truncated to the bitstring max capacity. + // Using a value larger than this will cause undefined behavior. + static size_t GetSafeDepth(size_t depth) { + return std::min(depth, BitString::kCapacity); + } + + BitString GetBitString() const { + return bitstring_and_of_.bitstring_; + } + + void SetBitString(const BitString& val) { + SetBitStringUnchecked(val); + DcheckInvariants(); + } + + void SetBitStringUnchecked(const BitString& val) { + bitstring_and_of_.bitstring_ = val; + } + + void OverwriteNextValueFromParent(/*inout*/SubtypeCheckInfo* child, BitStringChar value) const { + // Helper function for CreateChild. + if (HasNext()) { + // When we copied the "Next" value, it is now our + // last path component in the child. + // Always overwrite it with either a cleared value or the parent's Next value. + BitString bs = child->GetBitString(); + + // Safe write. This.Next always occupies same slot as Child[Depth_]. + DCHECK(child->HasBitStringCharStorage(depth_)); + + bs.SetAt(depth_, value); + + // The child is temporarily in a bad state until it is fixed up further. + // Do not do the normal dchecks which do not allow transient badness. + child->SetBitStringUnchecked(bs); + } + } + + void DcheckInvariants() const { + if (kIsDebugBuild) { + CHECK_GE(GetSafeDepth(depth_ + 1u), GetBitString().Length()) + << "Bitstring too long for depth, bitstring: " << GetBitString() << ", depth: " << depth_; + + BitString path_to_root = GetPathToRoot(); + + // A 'null' (\0) character in path-to-root must be followed only + // by other null characters. + size_t i; + for (i = 0; i < BitString::kCapacity; ++i) { + BitStringChar bc = path_to_root[i]; + if (bc == 0u) { + break; + } + } + + // All characters following a 0 must also be 0. + for (; i < BitString::kCapacity; ++i) { + BitStringChar bc = path_to_root[i]; + if (bc != 0u) { + LOG(FATAL) << "Path to root had non-0s following 0s: " << path_to_root; + } + } + + // Trigger any dchecks in GetState. + (void)GetState(); + } + } + + SubtypeCheckInfo() = default; + size_t depth_; + SubtypeCheckBits bitstring_and_of_; + + friend struct ::SubtypeCheckInfoTest; + friend std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io); +}; + +// Prints the SubtypeCheckInfo::State, e.g. "kUnitialized". +inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo::State& state) { + switch (state) { + case SubtypeCheckInfo::kUninitialized: + os << "kUninitialized"; + break; + case SubtypeCheckInfo::kInitialized: + os << "kInitialized"; + break; + case SubtypeCheckInfo::kAssigned: + os << "kAssigned"; + break; + case SubtypeCheckInfo::kOverflowed: + os << "kOverflowed"; + break; + default: + os << "(Invalid SubtypeCheckInfo::State " << static_cast<int>(state) << ")"; + } + return os; +} + +// Prints e.g. "SubtypeCheckInfo{BitString[1,2,3], depth: 3, of:1}" +inline std::ostream& operator<<(std::ostream& os, const SubtypeCheckInfo& io) { + os << "SubtypeCheckInfo{" << io.GetBitString() << ", " + << "depth: " << io.depth_ << ", of:" << io.bitstring_and_of_.overflow_ << "}"; + return os; +} + +} // namespace art + +#endif // ART_RUNTIME_SUBTYPE_CHECK_INFO_H_ diff --git a/runtime/subtype_check_info_test.cc b/runtime/subtype_check_info_test.cc new file mode 100644 index 0000000000..bc2e84e37d --- /dev/null +++ b/runtime/subtype_check_info_test.cc @@ -0,0 +1,421 @@ +/* + * 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{}; // NOLINT + + 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,7,255] for {12,3,8} +template <size_t kCount = BitString::kCapacity> +BitString MakeBitStringMax() { + BitString bs{}; // NOLINT + + 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: + virtual void SetUp() { + android::base::InitLogging(/*argv*/nullptr); + } + + virtual void TearDown() { + } + + 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(SubtypeCheckInfo io) { + return io.HasNext(); + } + + static BitString GetPathToRoot(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(SubtypeCheckInfo sc) { + SubtypeCheckInfo cleared_copy{}; // NOLINT + 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*/{}, /*next*/MakeBitStringChar(1)).GetState()); + EXPECT_EQ(SubtypeCheckInfo::kOverflowed, + MakeSubtypeCheckInfo(/*path*/{}, + /*next*/MakeBitStringChar(1), + /*overflow*/true, + /*depth*/1u).GetState()); + EXPECT_EQ(SubtypeCheckInfo::kAssigned, + MakeSubtypeCheckInfo(/*path*/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*/MakeBitStringMax(), + /*next*/MakeBitStringChar(0), + /*overflow*/false, + /*depth*/BitString::kCapacity).GetState()); + EXPECT_EQ(SubtypeCheckInfo::kInitialized, + MakeSubtypeCheckInfo(/*path*/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*/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 io = + MakeSubtypeCheckInfo(/*path_to_root*/MakeBitStringMax(), + /*next*/BitStringChar{}, // NOLINT + /*overflow*/false, + /*depth*/BitString::kCapacity); + // 0b11111...000 where MSB == 1, and leading 1s = the maximum bitstring representation. + EXPECT_EQ(MaxInt<StorageType>(LenForPos()) << (BitSizeOf<StorageType>() - LenForPos()), + io.GetEncodedPathToRoot()); + + EXPECT_EQ(MaxInt<StorageType>(LenForPos()) << (BitSizeOf<StorageType>() - LenForPos()), + io.GetEncodedPathToRootMask()); + + // 0b11111...000 where MSB == 1, and leading 1s = the maximum bitstring representation. + + // 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(3u, BitString::kBitSizeAtPosition[1]); + ASSERT_EQ(8u, BitString::kBitSizeAtPosition[2]); + + SubtypeCheckInfo io2 = + MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), + /*overflow*/false, + /*depth*/BitString::kCapacity); + +#define MAKE_ENCODED_PATH(pos0, pos1, pos2) (((pos0) << 3u << 8u << 9u) | ((pos1) << 8u << 9u) | ((pos2) << 9u)) + + EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b111, 0b0), io2.GetEncodedPathToRoot()); + EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b111, 0b11111111), io2.GetEncodedPathToRootMask()); + + SubtypeCheckInfo io3 = + MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(), + /*overflow*/false, + /*depth*/BitString::kCapacity - 1u); + + EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b111, 0b0), io3.GetEncodedPathToRoot()); + EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b111, 0b0), io3.GetEncodedPathToRootMask()); + + SubtypeCheckInfo io4 = + MakeSubtypeCheckInfoUnchecked(MakeBitString({0b1010101u}), + /*overflow*/false, + /*depth*/BitString::kCapacity - 2u); + + EXPECT_EQ(MAKE_ENCODED_PATH(0b1010101u, 0b000, 0b0), io4.GetEncodedPathToRoot()); + EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b000, 0b0), io4.GetEncodedPathToRootMask()); +} + +TEST_F(SubtypeCheckInfoTest, NewForRoot) { + SubtypeCheckInfo io = SubtypeCheckInfo::CreateRoot(); + EXPECT_EQ(SubtypeCheckInfo::kAssigned, io.GetState()); // Root is always assigned. + EXPECT_EQ(0u, GetPathToRoot(io).Length()); // Root's path length is 0. + EXPECT_TRUE(HasNext(io)); // Root always has a "Next". + EXPECT_EQ(MakeBitStringChar(1u), io.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*/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); // NOLINT + 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*/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*/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*/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*/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*/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*/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*/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*/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*/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*/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*/true); + EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState()); + EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2)); + } +} |