Add some functions to search ArrayRefs

[zturner]

Summary

This mirrors the interface of StringRef by adding functions for searching and dropping items from an ArrayRef until a certain condition is met. Specifically, this adds take_front, take_back, drop_front, and drop_back, along with helper functions find_if and find_if_not.

[chandlerc]

include/llvm/ADT/ArrayRef.h

34 ↗

(On Diff #78942)

I'm really reluctant to add APIs based around the 'npos' idea. How challenging does removing this and relying exclusively on iterator based constructs make things?

173 ↗

(On Diff #78942)

These are already inline functions, why not make them templates and use generic callables?

[zturner]

include/llvm/ADT/ArrayRef.h

173 ↗

(On Diff #78942)

joker-eph pointed me to llvm::find_if(), I think I will add llvm::find_if_not(), then have the functions use that, and that should address both of your comments at the same time.

[zturner]

• Deleted member find_if and find_if_not
• Deleted npos
• Convert take / drop functions to use llvm::find_if and llvm::find_if_not free functions.
• Updated the aforementioned functions to take a templatized predicate instead of an llvm::function_ref.

[chandlerc]

I would suggest passing the predicate by value instead of const reference to match the standard library. Feel free to fix up the range adapters in a separate patch and systematically.

Also, I'd suggest 'typename PredicateT' and 'PredicateT P' for naming conventions, if you want to be fully nit-picky. =D

[chandlerc]

LGTM with suggested changes, no need for a second iteration here.

llvm/trunk/include/llvm/ADT/ArrayRef.h

 //===--- ArrayRef.h - Array Reference Wrapper -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ARRAYREF_H
 #define LLVM_ADT_ARRAYREF_H
 
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include <array>
 #include <vector>
 
 namespace llvm {
   /// ArrayRef - Represent a constant reference to an array (0 or more elements
   /// consecutively in memory), i.e. a start pointer and a length.  It allows
   /// various APIs to take consecutive elements easily and conveniently.
public:
 
     /// equals - Check for element-wise equality.
     bool equals(ArrayRef RHS) const {
       if (Length != RHS.Length)
         return false;
       return std::equal(begin(), end(), RHS.begin());
     }
 
-    /// slice(n) - Chop off the first N elements of the array.
-    ArrayRef<T> slice(size_t N) const {
-      assert(N <= size() && "Invalid specifier");
-      return ArrayRef<T>(data()+N, size()-N);
-    }
-
     /// slice(n, m) - Chop off the first N elements of the array, and keep M
     /// elements in the array.
     ArrayRef<T> slice(size_t N, size_t M) const {
       assert(N+M <= size() && "Invalid specifier");
       return ArrayRef<T>(data()+N, M);
     }
 
+    /// slice(n) - Chop off the first N elements of the array.
+    ArrayRef<T> slice(size_t N) const { return slice(N, size() - N); }
+
     /// \brief Drop the first \p N elements of the array.
     ArrayRef<T> drop_front(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return slice(N, size() - N);
     }
 
     /// \brief Drop the last \p N elements of the array.
     ArrayRef<T> drop_back(size_t N = 1) const {
       assert(size() >= N && "Dropping more elements than exist");
       return slice(0, size() - N);
     }
 
+    /// \brief Return a copy of *this with the first N elements satisfying the
+    /// given predicate removed.
+    template <class PredicateT> ArrayRef<T> drop_while(PredicateT Pred) const {
+      return ArrayRef<T>(find_if_not(*this, Pred), end());
+    }
+
+    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// the given predicate removed.
+    template <class PredicateT> ArrayRef<T> drop_until(PredicateT Pred) const {
+      return ArrayRef<T>(find_if(*this, Pred), end());
+    }
+
     /// \brief Return a copy of *this with only the first \p N elements.
     ArrayRef<T> take_front(size_t N = 1) const {
       if (N >= size())
         return *this;
       return drop_back(size() - N);
     }
 
     /// \brief Return a copy of *this with only the last \p N elements.
     ArrayRef<T> take_back(size_t N = 1) const {
       if (N >= size())
         return *this;
       return drop_front(size() - N);
     }
 
+    /// \brief Return the first N elements of this Array that satisfy the given
+    /// predicate.
+    template <class PredicateT> ArrayRef<T> take_while(PredicateT Pred) const {
+      return ArrayRef<T>(begin(), find_if_not(*this, Pred));
+    }
+
+    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// given predicate.
+    template <class PredicateT> ArrayRef<T> take_until(PredicateT Pred) const {
+      return ArrayRef<T>(begin(), find_if(*this, Pred));
+    }
+
     /// @}
     /// @name Operator Overloads
     /// @{
     const T &operator[](size_t Index) const {
       assert(Index < Length && "Invalid index!");
       return Data[Index];
     }
 
public:
     }
 
     /// back - Get the last element.
     T &back() const {
       assert(!this->empty());
       return data()[this->size()-1];
     }
 
-    /// slice(n) - Chop off the first N elements of the array.
-    MutableArrayRef<T> slice(size_t N) const {
-      assert(N <= this->size() && "Invalid specifier");
-      return MutableArrayRef<T>(data()+N, this->size()-N);
-    }
-
     /// slice(n, m) - Chop off the first N elements of the array, and keep M
     /// elements in the array.
     MutableArrayRef<T> slice(size_t N, size_t M) const {
-      assert(N+M <= this->size() && "Invalid specifier");
-      return MutableArrayRef<T>(data()+N, M);
+      assert(N + M <= this->size() && "Invalid specifier");
+      return MutableArrayRef<T>(this->data() + N, M);
+    }
+
+    /// slice(n) - Chop off the first N elements of the array.
+    MutableArrayRef<T> slice(size_t N) const {
+      return slice(N, this->size() - N);
     }
 
     /// \brief Drop the first \p N elements of the array.
     MutableArrayRef<T> drop_front(size_t N = 1) const {
       assert(this->size() >= N && "Dropping more elements than exist");
       return slice(N, this->size() - N);
     }
 
     MutableArrayRef<T> drop_back(size_t N = 1) const {
       assert(this->size() >= N && "Dropping more elements than exist");
       return slice(0, this->size() - N);
     }
 
+    /// \brief Return a copy of *this with the first N elements satisfying the
+    /// given predicate removed.
+    template <class PredicateT>
+    MutableArrayRef<T> drop_while(PredicateT Pred) const {
+      return MutableArrayRef<T>(find_if_not(*this, Pred), end());
+    }
+
+    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// the given predicate removed.
+    template <class PredicateT>
+    MutableArrayRef<T> drop_until(PredicateT Pred) const {
+      return MutableArrayRef<T>(find_if(*this, Pred), end());
+    }
+
     /// \brief Return a copy of *this with only the first \p N elements.
     MutableArrayRef<T> take_front(size_t N = 1) const {
       if (N >= this->size())
         return *this;
       return drop_back(this->size() - N);
     }
 
     /// \brief Return a copy of *this with only the last \p N elements.
     MutableArrayRef<T> take_back(size_t N = 1) const {
       if (N >= this->size())
         return *this;
       return drop_front(this->size() - N);
     }
 
+    /// \brief Return the first N elements of this Array that satisfy the given
+    /// predicate.
+    template <class PredicateT>
+    MutableArrayRef<T> take_while(PredicateT Pred) const {
+      return MutableArrayRef<T>(begin(), find_if_not(*this, Pred));
+    }
+
+    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// given predicate.
+    template <class PredicateT>
+    MutableArrayRef<T> take_until(PredicateT Pred) const {
+      return MutableArrayRef<T>(begin(), find_if(*this, Pred));
+    }
+
     /// @}
     /// @name Operator Overloads
     /// @{
     T &operator[](size_t Index) const {
       assert(Index < this->size() && "Invalid index!");
       return data()[Index];
     }
   };

llvm/trunk/include/llvm/ADT/STLExtras.h

 
 /// Provide wrappers to std::find_if which take ranges instead of having to pass
 /// begin/end explicitly.
 template <typename R, class T>
 auto find_if(R &&Range, const T &Pred) -> decltype(Range.begin()) {
   return std::find_if(Range.begin(), Range.end(), Pred);
 }
 
+template <typename R, class PredicateT>
+auto find_if_not(R &&Range, PredicateT Pred) -> decltype(Range.begin()) {
+  return std::find_if_not(Range.begin(), Range.end(), Pred);
+}
+
 /// Provide wrappers to std::remove_if which take ranges instead of having to
 /// pass begin/end explicitly.
 template<typename R, class UnaryPredicate>
 auto remove_if(R &&Range, UnaryPredicate &&P) -> decltype(Range.begin()) {
   return std::remove_if(Range.begin(), Range.end(), P);
 }
 
 /// Wrapper function around std::find to detect if an element exists

llvm/trunk/unittests/ADT/ArrayRefTest.cpp

TEST(ArrayRefTest, DropFront) {
   ArrayRef<int> AR2(&TheNumbers[2], AR1.size() - 2);
   EXPECT_TRUE(AR1.drop_front(2).equals(AR2));
 
   // Check that drop_front accepts size_t-sized numbers.
   ArrayRef<char> AR3((const char *)0x10000, SIZE_MAX - 0x10000);
   EXPECT_EQ(1U, AR3.drop_front(AR3.size() - 1).size());
 }
 
+TEST(ArrayRefTest, DropWhile) {
+  static const int TheNumbers[] = {1, 3, 5, 8, 10, 11};
+  ArrayRef<int> AR1(TheNumbers);
+  ArrayRef<int> Expected = AR1.drop_front(3);
+  EXPECT_EQ(Expected, AR1.drop_while([](const int &N) { return N % 2 == 1; }));
+
+  EXPECT_EQ(AR1, AR1.drop_while([](const int &N) { return N < 0; }));
+  EXPECT_EQ(ArrayRef<int>(),
+            AR1.drop_while([](const int &N) { return N > 0; }));
+}
+
+TEST(ArrayRefTest, DropUntil) {
+  static const int TheNumbers[] = {1, 3, 5, 8, 10, 11};
+  ArrayRef<int> AR1(TheNumbers);
+  ArrayRef<int> Expected = AR1.drop_front(3);
+  EXPECT_EQ(Expected, AR1.drop_until([](const int &N) { return N % 2 == 0; }));
+
+  EXPECT_EQ(ArrayRef<int>(),
+            AR1.drop_until([](const int &N) { return N < 0; }));
+  EXPECT_EQ(AR1, AR1.drop_until([](const int &N) { return N > 0; }));
+}
+
 TEST(ArrayRefTest, TakeBack) {
   static const int TheNumbers[] = {4, 8, 15, 16, 23, 42};
   ArrayRef<int> AR1(TheNumbers);
   ArrayRef<int> AR2(AR1.end() - 1, 1);
   EXPECT_TRUE(AR1.take_back().equals(AR2));
 }
 
 TEST(ArrayRefTest, TakeFront) {
   static const int TheNumbers[] = {4, 8, 15, 16, 23, 42};
   ArrayRef<int> AR1(TheNumbers);
   ArrayRef<int> AR2(AR1.data(), 2);
   EXPECT_TRUE(AR1.take_front(2).equals(AR2));
 }
 
+TEST(ArrayRefTest, TakeWhile) {
+  static const int TheNumbers[] = {1, 3, 5, 8, 10, 11};
+  ArrayRef<int> AR1(TheNumbers);
+  ArrayRef<int> Expected = AR1.take_front(3);
+  EXPECT_EQ(Expected, AR1.take_while([](const int &N) { return N % 2 == 1; }));
+
+  EXPECT_EQ(ArrayRef<int>(),
+            AR1.take_while([](const int &N) { return N < 0; }));
+  EXPECT_EQ(AR1, AR1.take_while([](const int &N) { return N > 0; }));
+}
+
+TEST(ArrayRefTest, TakeUntil) {
+  static const int TheNumbers[] = {1, 3, 5, 8, 10, 11};
+  ArrayRef<int> AR1(TheNumbers);
+  ArrayRef<int> Expected = AR1.take_front(3);
+  EXPECT_EQ(Expected, AR1.take_until([](const int &N) { return N % 2 == 0; }));
+
+  EXPECT_EQ(AR1, AR1.take_until([](const int &N) { return N < 0; }));
+  EXPECT_EQ(ArrayRef<int>(),
+            AR1.take_until([](const int &N) { return N > 0; }));
+}
+
 TEST(ArrayRefTest, Equals) {
   static const int A1[] = {1, 2, 3, 4, 5, 6, 7, 8};
   ArrayRef<int> AR1(A1);
   EXPECT_TRUE(AR1.equals({1, 2, 3, 4, 5, 6, 7, 8}));
   EXPECT_FALSE(AR1.equals({8, 1, 2, 4, 5, 6, 6, 7}));
   EXPECT_FALSE(AR1.equals({2, 4, 5, 6, 6, 7, 8, 1}));
   EXPECT_FALSE(AR1.equals({0, 1, 2, 4, 5, 6, 6, 7}));
   EXPECT_FALSE(AR1.equals({1, 2, 42, 4, 5, 6, 7, 8}));