summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Evan Brown <ezb@google.com>2022-11-09 11:40:57 -0800
committerGravatar Copybara-Service <copybara-worker@google.com>2022-11-09 11:41:51 -0800
commit8cfc1500f894c07995abf25c2ad31f38982432cf (patch)
tree53aba92699b115a7e26af87e9a1f3a88557891dd
parent66bfca85c825a0c53254fa7f7787784099395d69 (diff)
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
-rw-r--r--absl/container/internal/raw_hash_set.h41
-rw-r--r--absl/container/internal/raw_hash_set_test.cc26
2 files changed, 58 insertions, 9 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 676cebd7..1aa89204 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -809,12 +809,44 @@ size_t SelectBucketCountForIterRange(InputIter first, InputIter last,
"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 @@ class raw_hash_set {
}
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 6478d3fc..daa32814 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2082,13 +2082,29 @@ TEST(TableDeathTest, IteratorInvalidAssertsEqualityOperator) {
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)