runtime: Bitstring implementation for subtype checking (2/4).
Implement the subtype checking label as a stand-alone data type.
This stores the bitstring and overflow bits. The bitstring
contains the encoded (path to root, next) bits.
Test: art/test.py -b -j32 --host --target
Bug: 64692057
Change-Id: I2229e1938f5377d637595ba3f81b8af3464d1ae7
diff --git a/runtime/Android.bp b/runtime/Android.bp
index 3059533..0e9e989 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -604,6 +604,7 @@
"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 0000000..4305ff8
--- /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 0000000..f60e0ac
--- /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 0000000..bc2e84e
--- /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));
+ }
+}