Add bssl::Vector::EraseIf

While I'm here, implement bssl::InplaceVector::EraseIf much more
straightforwardly. The STL already provides the hard part.

Change-Id: I6dfce1cfeba26e7b6bc749b4e64eceab4ba8564f
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/89007
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Lily Chen <chlily@google.com>
Commit-Queue: Lily Chen <chlily@google.com>
Auto-Submit: David Benjamin <davidben@google.com>

crypto/mem_internal.h

diff --git a/crypto/mem_internal.h b/crypto/mem_internal.h
index 088e1b4..14254ec 100644
--- a/crypto/mem_internal.h
+++ b/crypto/mem_internal.h
@@ -410,6 +410,14 @@
     return true;
   }
 
+  // EraseIf removes all elements that satisfy the predicate |pred|.
+  template <typename Pred>
+  void EraseIf(Pred pred) {
+    auto it = std::remove_if(begin(), end(), pred);
+    std::destroy(it, end());
+    size_ = it - begin();
+  }
+
  private:
   // If there is no room for one more element, creates a new backing array with
   // double the size of the old one and copies elements over.
@@ -622,25 +630,11 @@
     return *ret;
   }
 
+  // EraseIf removes all elements that satisfy the predicate |pred|.
   template <typename Pred>
   void EraseIf(Pred pred) {
-    // See if anything needs to be erased at all. This avoids a self-move.
-    auto iter = std::find_if(begin(), end(), pred);
-    if (iter == end()) {
-      return;
-    }
-
-    // Elements before the first to be erased may be left as-is.
-    size_t new_size = iter - begin();
-    // Swap all subsequent elements in if they are to be kept.
-    for (size_t i = new_size + 1; i < size(); i++) {
-      if (!pred((*this)[i])) {
-        (*this)[new_size] = std::move((*this)[i]);
-        new_size++;
-      }
-    }
-
-    Shrink(new_size);
+    auto it = std::remove_if(begin(), end(), pred);
+    Shrink(it - begin());
   }
 
  private:

crypto/mem_test.cc

diff --git a/crypto/mem_test.cc b/crypto/mem_test.cc
index 714df18..848df01 100644
--- a/crypto/mem_test.cc
+++ b/crypto/mem_test.cc
@@ -170,6 +170,81 @@
   EXPECT_EQ(3u, vec[3].array.size());
 }
 
+TEST(VectorTest, EraseIf) {
+  // Test that EraseIf never causes a self-move, and also correctly works with
+  // a move-only type that cannot be default-constructed.
+  class NoSelfMove {
+   public:
+    explicit NoSelfMove(int v) : v_(std::make_unique<int>(v)) {}
+    NoSelfMove(NoSelfMove &&other) { *this = std::move(other); }
+    NoSelfMove &operator=(NoSelfMove &&other) {
+      BSSL_CHECK(this != &other);
+      v_ = std::move(other.v_);
+      return *this;
+    }
+
+    int value() const { return *v_; }
+
+   private:
+    std::unique_ptr<int> v_;
+  };
+
+  Vector<NoSelfMove> vec;
+  auto reset = [&] {
+    vec.clear();
+    for (int i = 0; i < 8; i++) {
+      ASSERT_TRUE(vec.Push(NoSelfMove(i)));
+    }
+  };
+  auto expect = [&](const std::vector<int> &expected) {
+    ASSERT_EQ(vec.size(), expected.size());
+    for (size_t i = 0; i < vec.size(); i++) {
+      SCOPED_TRACE(i);
+      EXPECT_EQ(vec[i].value(), expected[i]);
+    }
+  };
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &) { return false; });
+  expect({0, 1, 2, 3, 4, 5, 6, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &) { return true; });
+  expect({});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() < 4; });
+  expect({4, 5, 6, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() >= 4; });
+  expect({0, 1, 2, 3});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() % 2 == 0; });
+  expect({1, 3, 5, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() % 2 == 1; });
+  expect({0, 2, 4, 6});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return 2 <= v.value() && v.value() <= 5; });
+  expect({0, 1, 6, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() == 0; });
+  expect({1, 2, 3, 4, 5, 6, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() == 4; });
+  expect({0, 1, 2, 3, 5, 6, 7});
+
+  ASSERT_NO_FATAL_FAILURE(reset());
+  vec.EraseIf([](const auto &v) { return v.value() == 7; });
+  expect({0, 1, 2, 3, 4, 5, 6});
+}
+
 TEST(VectorDeathTest, BoundsChecks) {
   Vector<int> vec;
   EXPECT_DEATH_IF_SUPPORTED(vec.front(), "");