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

35

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?

172

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

[zturner]

include/llvm/ADT/ArrayRef.h

172

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.

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.
   ///
   /// This class does not own the underlying data, it is expected to be used in
   /// situations where the data resides in some other buffer, whose lifetime
   /// extends past that of the ArrayRef. For this reason, it is not in general
   /// safe to store an ArrayRef.
   ///
   /// This is intended to be trivially copyable, so it should be passed by
   /// value.
   template<typename T>
   class LLVM_NODISCARD ArrayRef {
   public:
     typedef const T *iterator;
     typedef const T *const_iterator;
     typedef size_t size_type;
 
     typedef std::reverse_iterator<iterator> reverse_iterator;
 
   private:
     /// The start of the array, in an external buffer.
     const T *Data;
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 Pred> ArrayRef<T> drop_while(const Pred &P) const {
+      return ArrayRef<T>(find_if_not(*this, P), end());
+    }
+
+    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// the given predicate removed.
+    template <class Pred> ArrayRef<T> drop_until(const Pred &P) const {
+      return ArrayRef<T>(find_if(*this, P), 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 Pred> ArrayRef<T> take_while(const Pred &P) const {
+      return ArrayRef<T>(begin(), find_if_not(*this, P));
+    }
+
+    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// given predicate.
+    template <class Pred> ArrayRef<T> take_until(const Pred &P) const {
+      return ArrayRef<T>(begin(), find_if(*this, P));
+    }
+
     /// @}
     /// @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 Pred> MutableArrayRef<T> drop_while(const Pred &P) const {
+      return MutableArrayRef<T>(find_if_not(*this, P), end());
+    }
+
+    /// \brief Return a copy of *this with the first N elements not satisfying
+    /// the given predicate removed.
+    template <class Pred> MutableArrayRef<T> drop_until(const Pred &P) const {
+      return MutableArrayRef<T>(find_if(*this, P), 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 Pred> MutableArrayRef<T> take_while(const Pred &P) const {
+      return MutableArrayRef<T>(begin(), find_if_not(*this, F));
+    }
+
+    /// \brief Return the first N elements of this Array that don't satisfy the
+    /// given predicate.
+    template <class Pred> MutableArrayRef<T> take_until(const Pred &P) const {
+      return MutableArrayRef<T>(begin(), find_if(*this, F));
+    }
+
     /// @}
     /// @name Operator Overloads
     /// @{
     T &operator[](size_t Index) const {
       assert(Index < this->size() && "Invalid index!");
       return data()[Index];
     }
   };

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 T>
+auto find_if_not(R &&Range, const T &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

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}));