Improve error messages when comparing swisstable iterators.
We check for comparisons of swisstable iterators from different heap allocations, which can indicate either iterators from different containers or that there was a rehash between when the iterators were initialized.
PiperOrigin-RevId: 487304602
Change-Id: I5c596c5ea07948d66e048f99937f9032a630344f
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 676cebd..1aa8920 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -809,12 +809,44 @@
"the table might have rehashed."); \
} while (0)
-inline void AssertIsValid(ctrl_t* ctrl) {
+// Note that for comparisons, null/end iterators are valid.
+inline void AssertIsValidForComparison(const ctrl_t* ctrl) {
ABSL_HARDENING_ASSERT((ctrl == nullptr || IsFull(*ctrl)) &&
- "Invalid operation on iterator. The element might have "
+ "Invalid iterator comparison. The element might have "
"been erased or the table might have rehashed.");
}
+// If the two iterators come from the same container, then their pointers will
+// interleave such that ctrl_a <= ctrl_b < slot_a <= slot_b or vice/versa.
+// Note: we take slots by reference so that it's not UB if they're uninitialized
+// as long as we don't read them (when ctrl is null).
+inline bool AreItersFromSameContainer(const ctrl_t* ctrl_a,
+ const ctrl_t* ctrl_b,
+ const void* const& slot_a,
+ const void* const& slot_b) {
+ // If either control byte is null, then we can't tell.
+ if (ctrl_a == nullptr || ctrl_b == nullptr) return true;
+ const void* low_slot = slot_a;
+ const void* hi_slot = slot_b;
+ if (ctrl_a > ctrl_b) {
+ std::swap(ctrl_a, ctrl_b);
+ std::swap(low_slot, hi_slot);
+ }
+ return ctrl_b < low_slot && low_slot <= hi_slot;
+}
+
+// Asserts that two iterators come from the same container.
+// Note: we take slots by reference so that it's not UB if they're uninitialized
+// as long as we don't read them (when ctrl is null).
+inline void AssertSameContainer(const ctrl_t* ctrl_a, const ctrl_t* ctrl_b,
+ const void* const& slot_a,
+ const void* const& slot_b) {
+ ABSL_HARDENING_ASSERT(
+ AreItersFromSameContainer(ctrl_a, ctrl_b, slot_a, slot_b) &&
+ "Invalid iterator comparison. The iterators may be from different "
+ "containers or the container might have rehashed.");
+}
+
struct FindInfo {
size_t offset;
size_t probe_length;
@@ -1067,8 +1099,9 @@
}
friend bool operator==(const iterator& a, const iterator& b) {
- AssertIsValid(a.ctrl_);
- AssertIsValid(b.ctrl_);
+ AssertSameContainer(a.ctrl_, b.ctrl_, a.slot_, b.slot_);
+ AssertIsValidForComparison(a.ctrl_);
+ AssertIsValidForComparison(b.ctrl_);
return a.ctrl_ == b.ctrl_;
}
friend bool operator!=(const iterator& a, const iterator& b) {
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 6478d3f..daa3281 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2082,13 +2082,29 @@
ASSERT_NE(iter2, t.end());
t.erase(iter1);
// Extra simple "regexp" as regexp support is highly varied across platforms.
- const char* const kDeathMessage =
- "Invalid operation on iterator. The element might have .*been erased or "
+ const char* const kErasedDeathMessage =
+ "Invalid iterator comparison. The element might have .*been erased or "
"the table might have rehashed.";
- EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kDeathMessage);
- EXPECT_DEATH_IF_SUPPORTED(void(iter2 != iter1), kDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kErasedDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(iter2 != iter1), kErasedDeathMessage);
t.erase(iter2);
- EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kErasedDeathMessage);
+
+ IntTable t1, t2;
+ t1.insert(0);
+ t2.insert(0);
+ iter1 = t1.begin();
+ iter2 = t2.begin();
+ const char* const kContainerDiffDeathMessage =
+ "Invalid iterator comparison. The iterators may be from different "
+ ".*containers or the container might have rehashed.";
+ EXPECT_DEATH_IF_SUPPORTED(void(iter1 == iter2), kContainerDiffDeathMessage);
+ EXPECT_DEATH_IF_SUPPORTED(void(iter2 == iter1), kContainerDiffDeathMessage);
+
+ for (int i = 0; i < 10; ++i) t1.insert(i);
+ // There should have been a rehash in t1.
+ EXPECT_DEATH_IF_SUPPORTED(void(iter1 == t1.begin()),
+ kContainerDiffDeathMessage);
}
#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE)
