summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-10-02 10:17:27 -0700
committerGravatar Andy Getz <durandal@google.com>2020-10-02 22:03:20 -0400
commit887d0eee6bab35847253181b32e78ff707010ccd (patch)
treeacaa30bb0aee7dba9371367bb4833424178cd78f
parentb978fc02f02ba79c545f99d0d65bd066fb8cebf8 (diff)
Export of internal Abseil changes
-- d6e582e21ceec768aa72e857c10ba80cad2f2202 by Abseil Team <absl-team@google.com>: adds bounds-checking for the second range in absl::c_mismatch The API for the two-range absl::c_mismatch is misleading as it doesn't check the bounds of the second range against the first one. This commit cleans up the internals of the overload to make sure that buggy calls are not exploitable; non-buggy calls are unaffected. This is consistent with both C++14's two-range std::mismatch and C++20's std::ranges::mismatch (see http://wg21.link/mismatch). PiperOrigin-RevId: 335050236 GitOrigin-RevId: d6e582e21ceec768aa72e857c10ba80cad2f2202 Change-Id: I77e0d030adf35c09069ceab5ea67efdf09377390
-rw-r--r--absl/algorithm/container.h39
-rw-r--r--absl/algorithm/container_test.cc99
2 files changed, 108 insertions, 30 deletions
diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h
index 5c033571..7778ab17 100644
--- a/absl/algorithm/container.h
+++ b/absl/algorithm/container.h
@@ -340,24 +340,43 @@ container_algorithm_internal::ContainerDifferenceType<const C> c_count_if(
// c_mismatch()
//
// Container-based version of the <algorithm> `std::mismatch()` function to
-// return the first element where two ordered containers differ.
+// return the first element where two ordered containers differ. Applies `==` to
+// the first N elements of `c1` and `c2`, where N = min(size(c1), size(c2)).
template <typename C1, typename C2>
container_algorithm_internal::ContainerIterPairType<C1, C2>
c_mismatch(C1& c1, C2& c2) {
- return std::mismatch(container_algorithm_internal::c_begin(c1),
- container_algorithm_internal::c_end(c1),
- container_algorithm_internal::c_begin(c2));
+ auto first1 = container_algorithm_internal::c_begin(c1);
+ auto last1 = container_algorithm_internal::c_end(c1);
+ auto first2 = container_algorithm_internal::c_begin(c2);
+ auto last2 = container_algorithm_internal::c_end(c2);
+
+ for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
+ if (*first1 != *first2) {
+ break;
+ }
+ }
+
+ return std::make_pair(first1, first2);
}
// Overload of c_mismatch() for using a predicate evaluation other than `==` as
-// the function's test condition.
+// the function's test condition. Applies `pred`to the first N elements of `c1`
+// and `c2`, where N = min(size(c1), size(c2)).
template <typename C1, typename C2, typename BinaryPredicate>
container_algorithm_internal::ContainerIterPairType<C1, C2>
-c_mismatch(C1& c1, C2& c2, BinaryPredicate&& pred) {
- return std::mismatch(container_algorithm_internal::c_begin(c1),
- container_algorithm_internal::c_end(c1),
- container_algorithm_internal::c_begin(c2),
- std::forward<BinaryPredicate>(pred));
+c_mismatch(C1& c1, C2& c2, BinaryPredicate pred) {
+ auto first1 = container_algorithm_internal::c_begin(c1);
+ auto last1 = container_algorithm_internal::c_end(c1);
+ auto first2 = container_algorithm_internal::c_begin(c2);
+ auto last2 = container_algorithm_internal::c_end(c2);
+
+ for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
+ if (!pred(*first1, *first2)) {
+ break;
+ }
+ }
+
+ return std::make_pair(first1, first2);
}
// c_equal()
diff --git a/absl/algorithm/container_test.cc b/absl/algorithm/container_test.cc
index 3abf5cea..fb940560 100644
--- a/absl/algorithm/container_test.cc
+++ b/absl/algorithm/container_test.cc
@@ -57,9 +57,7 @@ class NonMutatingTest : public testing::Test {
};
struct AccumulateCalls {
- void operator()(int value) {
- calls.push_back(value);
- }
+ void operator()(int value) { calls.push_back(value); }
std::vector<int> calls;
};
@@ -68,7 +66,6 @@ bool BinPredicate(int v1, int v2) { return v1 < v2; }
bool Equals(int v1, int v2) { return v1 == v2; }
bool IsOdd(int x) { return x % 2 != 0; }
-
TEST_F(NonMutatingTest, Distance) {
EXPECT_EQ(container_.size(), absl::c_distance(container_));
EXPECT_EQ(sequence_.size(), absl::c_distance(sequence_));
@@ -151,13 +148,79 @@ TEST_F(NonMutatingTest, CountIf) {
}
TEST_F(NonMutatingTest, Mismatch) {
- absl::c_mismatch(container_, sequence_);
- absl::c_mismatch(sequence_, container_);
+ // Testing necessary as absl::c_mismatch executes logic.
+ {
+ auto result = absl::c_mismatch(vector_, sequence_);
+ EXPECT_EQ(result.first, vector_.end());
+ EXPECT_EQ(result.second, sequence_.end());
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_);
+ EXPECT_EQ(result.first, sequence_.end());
+ EXPECT_EQ(result.second, vector_.end());
+ }
+
+ sequence_.back() = 5;
+ {
+ auto result = absl::c_mismatch(vector_, sequence_);
+ EXPECT_EQ(result.first, std::prev(vector_.end()));
+ EXPECT_EQ(result.second, std::prev(sequence_.end()));
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_);
+ EXPECT_EQ(result.first, std::prev(sequence_.end()));
+ EXPECT_EQ(result.second, std::prev(vector_.end()));
+ }
+
+ sequence_.pop_back();
+ {
+ auto result = absl::c_mismatch(vector_, sequence_);
+ EXPECT_EQ(result.first, std::prev(vector_.end()));
+ EXPECT_EQ(result.second, sequence_.end());
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_);
+ EXPECT_EQ(result.first, sequence_.end());
+ EXPECT_EQ(result.second, std::prev(vector_.end()));
+ }
}
TEST_F(NonMutatingTest, MismatchWithPredicate) {
- absl::c_mismatch(container_, sequence_, BinPredicate);
- absl::c_mismatch(sequence_, container_, BinPredicate);
+ // Testing necessary as absl::c_mismatch executes logic.
+ {
+ auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
+ EXPECT_EQ(result.first, vector_.begin());
+ EXPECT_EQ(result.second, sequence_.begin());
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
+ EXPECT_EQ(result.first, sequence_.begin());
+ EXPECT_EQ(result.second, vector_.begin());
+ }
+
+ sequence_.front() = 0;
+ {
+ auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
+ EXPECT_EQ(result.first, vector_.begin());
+ EXPECT_EQ(result.second, sequence_.begin());
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
+ EXPECT_EQ(result.first, std::next(sequence_.begin()));
+ EXPECT_EQ(result.second, std::next(vector_.begin()));
+ }
+
+ sequence_.clear();
+ {
+ auto result = absl::c_mismatch(vector_, sequence_, BinPredicate);
+ EXPECT_EQ(result.first, vector_.begin());
+ EXPECT_EQ(result.second, sequence_.end());
+ }
+ {
+ auto result = absl::c_mismatch(sequence_, vector_, BinPredicate);
+ EXPECT_EQ(result.first, sequence_.end());
+ EXPECT_EQ(result.second, vector_.begin());
+ }
}
TEST_F(NonMutatingTest, Equal) {
@@ -519,11 +582,9 @@ TEST_F(SortingTest, IsSortedUntil) {
TEST_F(SortingTest, NthElement) {
std::vector<int> unsorted = {2, 4, 1, 3};
absl::c_nth_element(unsorted, unsorted.begin() + 2);
- EXPECT_THAT(unsorted,
- ElementsAre(Lt(3), Lt(3), 3, Gt(3)));
+ EXPECT_THAT(unsorted, ElementsAre(Lt(3), Lt(3), 3, Gt(3)));
absl::c_nth_element(unsorted, unsorted.begin() + 2, std::greater<int>());
- EXPECT_THAT(unsorted,
- ElementsAre(Gt(2), Gt(2), 2, Lt(2)));
+ EXPECT_THAT(unsorted, ElementsAre(Gt(2), Gt(2), 2, Lt(2)));
}
TEST(MutatingTest, IsPartitioned) {
@@ -778,10 +839,9 @@ MATCHER_P2(IsElement, key, value, "") {
TEST(MutatingTest, StableSort) {
std::vector<Element> test_vector = {{1, 1}, {2, 1}, {2, 0}, {1, 0}, {2, 2}};
absl::c_stable_sort(test_vector);
- EXPECT_THAT(
- test_vector,
- ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1),
- IsElement(2, 0), IsElement(2, 2)));
+ EXPECT_THAT(test_vector,
+ ElementsAre(IsElement(1, 1), IsElement(1, 0), IsElement(2, 1),
+ IsElement(2, 0), IsElement(2, 2)));
}
TEST(MutatingTest, StableSortWithPredicate) {
@@ -789,10 +849,9 @@ TEST(MutatingTest, StableSortWithPredicate) {
absl::c_stable_sort(test_vector, [](const Element& e1, const Element& e2) {
return e2 < e1;
});
- EXPECT_THAT(
- test_vector,
- ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2),
- IsElement(1, 1), IsElement(1, 0)));
+ EXPECT_THAT(test_vector,
+ ElementsAre(IsElement(2, 1), IsElement(2, 0), IsElement(2, 2),
+ IsElement(1, 1), IsElement(1, 0)));
}
TEST(MutatingTest, ReplaceCopyIf) {