Make GetState() handle overflowed state and 0 path to root
Fix GetState() so that it deals correctly with an overflowed state in
which the path to root is entirely zero. We don't try to salvage
the DCHECK for now. Fix the stated invariants to be more consistent
with the code.
Bug: 69564627
Test: AOSP builds & runs. Host tests pass.
Change-Id: Idd975f03d4292e4fc52ad7714bbb2b1b98e17f96
diff --git a/runtime/base/bit_string.h b/runtime/base/bit_string.h
index a2164f3..bfbe8ea 100644
--- a/runtime/base/bit_string.h
+++ b/runtime/base/bit_string.h
@@ -114,7 +114,7 @@
/**
* BitString
*
- * MSB LSB
+ * lsb (least significant bit) msb
* +------------+------------+------------+-----+------------+
* | | | | | |
* | Char0 | Char1 | Char2 | ... | CharN |
@@ -131,8 +131,9 @@
* "ABCDE...K" := [A,B,C,D,E, ... K] + [0]*(N-idx(K)) s.t. N >= K.
* // Padded with trailing 0s to fit (N+1) bitstring chars.
* MaxBitstringLen := N+1
- * StrLen(Bitstring) := MaxBitStringLen - | forall char in CharI..CharN : char == 0 AND Char(I-1) != 0 |
- * // Maximum length - the # of consecutive trailing zeroes.
+ * StrLen(Bitstring) := I s.t. (I == 0 OR Char(I-1) != 0)
+ * AND forall char in CharI..CharN : char == 0
+ * // = Maximum length - the # of consecutive trailing zeroes.
* Bitstring[N] := CharN
* Bitstring[I..N) := [CharI, CharI+1, ... CharN-1]
*
@@ -278,8 +279,8 @@
private:
friend std::ostream& operator<<(std::ostream& os, const BitString& bit_string);
- // Data is stored with the "highest" position in the least-significant-bit.
- // As positions approach 0, the bits are stored with increasing significance.
+ // Data is stored with the first character in the least-significant-bit.
+ // Unused bits are zero.
StorageType storage_;
};
diff --git a/runtime/subtype_check_info.h b/runtime/subtype_check_info.h
index cd579c3..8320fb3 100644
--- a/runtime/subtype_check_info.h
+++ b/runtime/subtype_check_info.h
@@ -90,10 +90,13 @@
*
* Uninitialized <=> StrLen(PathToRoot) == 0
* Next == 0
+ * OF == False
* Initialized <=> StrLen(PathToRoot) < Depth
- * Next == 0
+ * Next == 1
+ * OF == False
* Assigned <=> StrLen(PathToRoot) == Depth
- * Next > 1
+ * Next >= 1
+ * OF == False
* Overflowed <=> OF == True
*
* Tree Invariants:
@@ -219,7 +222,7 @@
// Next must be non-0 to disambiguate it from Uninitialized.
child.MaybeInitNext();
- // Always clear the inherited Parent's next Value on the child.
+ // Always clear the inherited Parent's next Value, i.e. the child's last path entry.
OverwriteNextValueFromParent(/*inout*/&child, BitStringChar{});
// The state is now Initialized | Overflowed.
@@ -235,7 +238,6 @@
// 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.
@@ -260,17 +262,16 @@
// 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().IsEmpty()) {
- // 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;
}
+ if (GetBitString().IsEmpty()) {
+ // Empty bitstring (all 0s) -> uninitialized.
+ return kUninitialized;
+ }
+
// Either Assigned or Initialized.
BitString path_to_root = GetPathToRoot();
@@ -387,6 +388,7 @@
SetBitStringUnchecked(bs);
}
+ // If there is a next field, set it to 1.
void MaybeInitNext() {
if (HasNext()) {
// Clearing out the "Next" value like this