summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Evan Brown <ezb@google.com>2023-04-12 09:57:09 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2023-04-12 09:57:55 -0700
commit2126f023986070c518d676a6a116124fc0c5ba00 (patch)
treee873ed0190e19a5ba07146c13b399faf5ad006de /absl
parentcb204d6d9c3f2066580e606bcbe54e3383791d5f (diff)
In debug mode, detect cases of btree comparators that violate transitivity, i.e. comp(A,B) && comp(B,C) -> comp(A,C).
When inserting a new element, we verify that the key is ordered correctly with respect to all the other values on the node, which can be done in constant time. PiperOrigin-RevId: 523729309 Change-Id: Idb5a5912a9aa5411d086cb9fa76791523046778a
Diffstat (limited to 'absl')
-rw-r--r--absl/container/BUILD.bazel1
-rw-r--r--absl/container/CMakeLists.txt1
-rw-r--r--absl/container/btree_test.cc73
-rw-r--r--absl/container/internal/btree.h39
4 files changed, 114 insertions, 0 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 038e5234..902f6ed3 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -1001,6 +1001,7 @@ cc_test(
"//absl/random",
"//absl/strings",
"//absl/types:compare",
+ "//absl/types:optional",
"@com_google_googletest//:gtest_main",
],
)
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index 43d60b9d..3c48270b 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -80,6 +80,7 @@ absl_cc_test(
absl::counting_allocator
absl::flags
absl::hash_testing
+ absl::optional
absl::random_random
absl::raw_logging_internal
absl::strings
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index cc763b29..1b6a3f47 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -46,6 +46,7 @@
#include "absl/strings/str_split.h"
#include "absl/strings/string_view.h"
#include "absl/types/compare.h"
+#include "absl/types/optional.h"
ABSL_FLAG(int, test_values, 10000, "The number of values to use for tests");
@@ -3137,6 +3138,78 @@ TEST(Btree, InvalidComparatorsCaught) {
absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set;
EXPECT_DEATH(set.insert({0, 1, 2}), "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");
}
+ // Verify that we detect cases of comparators that violate transitivity.
+ // When the comparators below check for the presence of an optional field,
+ // they violate transitivity because instances that have the optional field
+ // compare differently with each other from how they compare with instances
+ // that don't have the optional field.
+ struct ClockTime {
+ absl::optional<int> hour;
+ int minute;
+ };
+ // `comp(a,b) && comp(b,c) && !comp(a,c)` violates transitivity.
+ ClockTime a = {absl::nullopt, 1};
+ ClockTime b = {2, 5};
+ ClockTime c = {6, 0};
+ {
+ struct NonTransitiveTimeCmp {
+ bool operator()(ClockTime lhs, ClockTime rhs) const {
+ if (lhs.hour.has_value() && rhs.hour.has_value() &&
+ *lhs.hour != *rhs.hour) {
+ return *lhs.hour < *rhs.hour;
+ }
+ return lhs.minute < rhs.minute;
+ }
+ };
+ NonTransitiveTimeCmp cmp;
+ ASSERT_TRUE(cmp(a, b) && cmp(b, c) && !cmp(a, c));
+ absl::btree_set<ClockTime, NonTransitiveTimeCmp> set;
+ EXPECT_DEATH(set.insert({a, b, c}), "is_ordered_correctly");
+ absl::btree_multiset<ClockTime, NonTransitiveTimeCmp> mset;
+ EXPECT_DEATH(mset.insert({a, a, b, b, c, c}), "is_ordered_correctly");
+ }
+ {
+ struct ThreeWayNonTransitiveTimeCmp {
+ absl::weak_ordering operator()(ClockTime lhs, ClockTime rhs) const {
+ if (lhs.hour.has_value() && rhs.hour.has_value() &&
+ *lhs.hour != *rhs.hour) {
+ return *lhs.hour < *rhs.hour ? absl::weak_ordering::less
+ : absl::weak_ordering::greater;
+ }
+ return lhs.minute < rhs.minute ? absl::weak_ordering::less
+ : lhs.minute == rhs.minute ? absl::weak_ordering::equivalent
+ : absl::weak_ordering::greater;
+ }
+ };
+ ThreeWayNonTransitiveTimeCmp cmp;
+ ASSERT_TRUE(cmp(a, b) < 0 && cmp(b, c) < 0 && cmp(a, c) > 0);
+ absl::btree_set<ClockTime, ThreeWayNonTransitiveTimeCmp> set;
+ EXPECT_DEATH(set.insert({a, b, c}), "is_ordered_correctly");
+ absl::btree_multiset<ClockTime, ThreeWayNonTransitiveTimeCmp> mset;
+ EXPECT_DEATH(mset.insert({a, a, b, b, c, c}), "is_ordered_correctly");
+ }
+}
+
+TEST(Btree, MutatedKeysCaught) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ struct IntPtrCmp {
+ bool operator()(int *lhs, int *rhs) const { return *lhs < *rhs; }
+ };
+ {
+ absl::btree_set<int *, IntPtrCmp> set;
+ int arr[] = {0, 1, 2};
+ set.insert({&arr[0], &arr[1], &arr[2]});
+ arr[0] = 100;
+ EXPECT_DEATH(set.insert(&arr[0]), "is_ordered_correctly");
+ }
+ {
+ absl::btree_multiset<int *, IntPtrCmp> set;
+ int arr[] = {0, 1, 2};
+ set.insert({&arr[0], &arr[0], &arr[1], &arr[1], &arr[2], &arr[2]});
+ arr[0] = 100;
+ EXPECT_DEATH(set.insert(&arr[0]), "is_ordered_correctly");
+ }
}
#ifndef _MSC_VER
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index cd1569b3..2ed57a62 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -892,6 +892,38 @@ class btree_node {
}
}
+ // Returns whether key i is ordered correctly with respect to the other keys
+ // in the node. The motivation here is to detect comparators that violate
+ // transitivity. Note: we only do comparisons of keys on this node rather than
+ // the whole tree so that this is constant time.
+ template <typename Compare>
+ bool is_ordered_correctly(field_type i, const Compare &comp) const {
+ if (std::is_base_of<BtreeTestOnlyCheckedCompareOptOutBase,
+ Compare>::value ||
+ params_type::kIsKeyCompareStringAdapted) {
+ return true;
+ }
+
+ const auto compare = [&](field_type a, field_type b) {
+ const absl::weak_ordering cmp =
+ compare_internal::do_three_way_comparison(comp, key(a), key(b));
+ return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
+ };
+ int cmp = -1;
+ constexpr bool kCanHaveEquivKeys =
+ params_type::template can_have_multiple_equivalent_keys<key_type>();
+ for (field_type j = start(); j < finish(); ++j) {
+ if (j == i) {
+ if (cmp > 0) return false;
+ continue;
+ }
+ int new_cmp = compare(j, i);
+ if (new_cmp < cmp || (!kCanHaveEquivKeys && new_cmp == 0)) return false;
+ cmp = new_cmp;
+ }
+ return true;
+ }
+
// Emplaces a value at position i, shifting all existing values and
// children at positions >= i to the right by 1.
template <typename... Args>
@@ -2816,6 +2848,13 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&...args)
}
iter.node_->emplace_value(static_cast<field_type>(iter.position_), alloc,
std::forward<Args>(args)...);
+ assert(
+ iter.node_->is_ordered_correctly(static_cast<field_type>(iter.position_),
+ original_key_compare(key_comp())) &&
+ "If this assert fails, then either (1) the comparator may violate "
+ "transitivity, i.e. comp(a,b) && comp(b,c) -> comp(a,c) (see "
+ "https://en.cppreference.com/w/cpp/named_req/Compare), or (2) a "
+ "key may have been mutated after it was inserted into the tree.");
++size_;
iter.update_generation();
return iter;