X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FRange.h;h=228a8d5535c213194b579ccda1e1144b16e7e45b;hp=c34d5cfe601efd766d7c43b3181422a02eae4686;hb=614eb71734a284e1a9fefabcc48743a3c8efd653;hpb=b0131bea126f9febe31c825fc4cd11d5d8996304

diff --git a/folly/Range.h b/folly/Range.h
index c34d5cfe..228a8d55 100644
--- a/folly/Range.h
+++ b/folly/Range.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2015 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -17,45 +17,50 @@
 // @author Mark Rabkin (mrabkin@fb.com)
 // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
 
-#ifndef FOLLY_RANGE_H_
-#define FOLLY_RANGE_H_
+#pragma once
 
 #include <folly/Portability.h>
-#include <folly/FBString.h>
-#include <folly/SpookyHashV2.h>
+#include <folly/hash/SpookyHashV2.h>
+#include <folly/portability/BitsFunctexcept.h>
+#include <folly/portability/Constexpr.h>
+#include <folly/portability/String.h>
 
-#include <algorithm>
 #include <boost/operators.hpp>
+#include <glog/logging.h>
+#include <algorithm>
+#include <array>
+#include <cassert>
 #include <climits>
+#include <cstddef>
 #include <cstring>
-#include <glog/logging.h>
 #include <iosfwd>
 #include <stdexcept>
 #include <string>
 #include <type_traits>
 
-// libc++ doesn't provide this header, nor does msvc
-#ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
-// This file appears in two locations: inside fbcode and in the
-// libstdc++ source code (when embedding fbstring as std::string).
-// To aid in this schizophrenic use, two macros are defined in
-// c++config.h:
-//   _LIBSTDCXX_FBSTRING - Set inside libstdc++.  This is useful to
-//      gate use inside fbcode v. libstdc++
-#include <bits/c++config.h>
-#endif
-
 #include <folly/CpuId.h>
-#include <folly/Traits.h>
 #include <folly/Likely.h>
+#include <folly/Traits.h>
+#include <folly/detail/RangeCommon.h>
+#include <folly/detail/RangeSse42.h>
 
 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wshadow"
+FOLLY_PUSH_WARNING
+FOLLY_GCC_DISABLE_WARNING("-Wshadow")
 
 namespace folly {
 
-template <class T> class Range;
+/**
+ * Ubiquitous helper template for knowing what's a string.
+ */
+template <class T>
+struct IsSomeString : std::false_type {};
+
+template <>
+struct IsSomeString<std::string> : std::true_type {};
+
+template <class Iter>
+class Range;
 
 /**
  * Finds the first occurrence of needle in haystack. The algorithm is on
@@ -63,37 +68,40 @@ template <class T> class Range;
  * as Boyer-Moore. On the upside, it does not do any upfront
  * preprocessing and does not allocate memory.
  */
-template <class T, class Comp = std::equal_to<typename Range<T>::value_type>>
-inline size_t qfind(const Range<T> & haystack,
-                    const Range<T> & needle,
-                    Comp eq = Comp());
+template <
+    class Iter,
+    class Comp = std::equal_to<typename Range<Iter>::value_type>>
+inline size_t
+qfind(const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq = Comp());
 
 /**
  * Finds the first occurrence of needle in haystack. The result is the
  * offset reported to the beginning of haystack, or string::npos if
  * needle wasn't found.
  */
-template <class T>
-size_t qfind(const Range<T> & haystack,
-             const typename Range<T>::value_type& needle);
+template <class Iter>
+size_t qfind(
+    const Range<Iter>& haystack,
+    const typename Range<Iter>::value_type& needle);
 
 /**
  * Finds the last occurrence of needle in haystack. The result is the
  * offset reported to the beginning of haystack, or string::npos if
  * needle wasn't found.
  */
-template <class T>
-size_t rfind(const Range<T> & haystack,
-             const typename Range<T>::value_type& needle);
-
+template <class Iter>
+size_t rfind(
+    const Range<Iter>& haystack,
+    const typename Range<Iter>::value_type& needle);
 
 /**
  * Finds the first occurrence of any element of needle in
  * haystack. The algorithm is O(haystack.size() * needle.size()).
  */
-template <class T>
-inline size_t qfind_first_of(const Range<T> & haystack,
-                             const Range<T> & needle);
+template <class Iter>
+inline size_t qfind_first_of(
+    const Range<Iter>& haystack,
+    const Range<Iter>& needle);
 
 /**
  * Small internal helper - returns the value just before an iterator.
@@ -105,9 +113,10 @@ namespace detail {
  */
 template <class Iter>
 typename std::enable_if<
-  std::is_same<typename std::iterator_traits<Iter>::iterator_category,
-               std::random_access_iterator_tag>::value,
-  typename std::iterator_traits<Iter>::reference>::type
+    std::is_same<
+        typename std::iterator_traits<Iter>::iterator_category,
+        std::random_access_iterator_tag>::value,
+    typename std::iterator_traits<Iter>::reference>::type
 value_before(Iter i) {
   return i[-1];
 }
@@ -117,9 +126,10 @@ value_before(Iter i) {
  */
 template <class Iter>
 typename std::enable_if<
-  !std::is_same<typename std::iterator_traits<Iter>::iterator_category,
-                std::random_access_iterator_tag>::value,
-  typename std::iterator_traits<Iter>::reference>::type
+    !std::is_same<
+        typename std::iterator_traits<Iter>::iterator_category,
+        std::random_access_iterator_tag>::value,
+    typename std::iterator_traits<Iter>::reference>::type
 value_before(Iter i) {
   return *--i;
 }
@@ -128,7 +138,8 @@ value_before(Iter i) {
  * Use IsCharPointer<T>::type to enable const char* or char*.
  * Use IsCharPointer<T>::const_type to enable only const char*.
  */
-template <class T> struct IsCharPointer {};
+template <class T>
+struct IsCharPointer {};
 
 template <>
 struct IsCharPointer<char*> {
@@ -155,14 +166,14 @@ struct IsCharPointer<const char*> {
  * wouldn't.)
  */
 template <class Iter>
-class Range : private boost::totally_ordered<Range<Iter> > {
-public:
+class Range : private boost::totally_ordered<Range<Iter>> {
+ public:
   typedef std::size_t size_type;
   typedef Iter iterator;
   typedef Iter const_iterator;
   typedef typename std::remove_reference<
-    typename std::iterator_traits<Iter>::reference>::type
-  value_type;
+      typename std::iterator_traits<Iter>::reference>::type value_type;
+  using difference_type = typename std::iterator_traits<Iter>::difference_type;
   typedef typename std::iterator_traits<Iter>::reference reference;
 
   /**
@@ -172,41 +183,40 @@ public:
    * args which are const.
    */
   typedef typename std::conditional<
-    std::is_same<Iter, char*>::value
-      || std::is_same<Iter, unsigned char*>::value,
-    Range<const value_type*>,
-    Range<Iter>>::type const_range_type;
+      std::is_same<Iter, char*>::value ||
+          std::is_same<Iter, unsigned char*>::value,
+      Range<const value_type*>,
+      Range<Iter>>::type const_range_type;
 
   typedef std::char_traits<typename std::remove_const<value_type>::type>
-    traits_type;
+      traits_type;
 
   static const size_type npos;
 
   // Works for all iterators
-  constexpr Range() : b_(), e_() {
-  }
+  constexpr Range() : b_(), e_() {}
 
   constexpr Range(const Range&) = default;
   constexpr Range(Range&&) = default;
 
-public:
+ public:
   // Works for all iterators
-  constexpr Range(Iter start, Iter end) : b_(start), e_(end) {
-  }
+  constexpr Range(Iter start, Iter end) : b_(start), e_(end) {}
 
   // Works only for random-access iterators
-  constexpr Range(Iter start, size_t size)
-      : b_(start), e_(start + size) { }
+  constexpr Range(Iter start, size_t size) : b_(start), e_(start + size) {}
 
-#if FOLLY_HAVE_CONSTEXPR_STRLEN
-  template <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
-  constexpr /* implicit */ Range(Iter str)
-      : b_(str), e_(str + strlen(str)) {}
-#else
-  template <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
-  /* implicit */ Range(Iter str)
-      : b_(str), e_(str + strlen(str)) {}
+#if !__clang__ || __CLANG_PREREQ(3, 7) // Clang 3.6 crashes on this line
+  /* implicit */ Range(std::nullptr_t) = delete;
 #endif
+
+  constexpr /* implicit */ Range(Iter str)
+      : b_(str), e_(str + constexpr_strlen(str)) {
+    static_assert(
+        std::is_same<int, typename detail::IsCharPointer<Iter>::type>::value,
+        "This constructor is only available for character ranges");
+  }
+
   template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
   /* implicit */ Range(const std::string& str)
       : b_(str.data()), e_(b_ + str.size()) {}
@@ -214,18 +224,19 @@ public:
   template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
   Range(const std::string& str, std::string::size_type startFrom) {
     if (UNLIKELY(startFrom > str.size())) {
-      throw std::out_of_range("index out of range");
+      std::__throw_out_of_range("index out of range");
     }
     b_ = str.data() + startFrom;
     e_ = str.data() + str.size();
   }
 
   template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
-  Range(const std::string& str,
-        std::string::size_type startFrom,
-        std::string::size_type size) {
+  Range(
+      const std::string& str,
+      std::string::size_type startFrom,
+      std::string::size_type size) {
     if (UNLIKELY(startFrom > str.size())) {
-      throw std::out_of_range("index out of range");
+      std::__throw_out_of_range("index out of range");
     }
     b_ = str.data() + startFrom;
     if (str.size() - startFrom < size) {
@@ -235,34 +246,61 @@ public:
     }
   }
 
-  Range(const Range& other,
-        size_type first,
-        size_type length = npos)
-      : Range(other.subpiece(first, length))
-    { }
-
-  template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
-  /* implicit */ Range(const fbstring& str)
-    : b_(str.data()), e_(b_ + str.size()) { }
-
-  template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
-  Range(const fbstring& str, fbstring::size_type startFrom) {
-    if (UNLIKELY(startFrom > str.size())) {
-      throw std::out_of_range("index out of range");
+  Range(const Range& other, size_type first, size_type length = npos)
+      : Range(other.subpiece(first, length)) {}
+
+  template <
+      class Container,
+      class = typename std::enable_if<
+          std::is_same<Iter, typename Container::const_pointer>::value>::type,
+      class = decltype(
+          Iter(std::declval<Container const&>().data()),
+          Iter(
+              std::declval<Container const&>().data() +
+              std::declval<Container const&>().size()))>
+  /* implicit */ constexpr Range(Container const& container)
+      : b_(container.data()), e_(b_ + container.size()) {}
+
+  template <
+      class Container,
+      class = typename std::enable_if<
+          std::is_same<Iter, typename Container::const_pointer>::value>::type,
+      class = decltype(
+          Iter(std::declval<Container const&>().data()),
+          Iter(
+              std::declval<Container const&>().data() +
+              std::declval<Container const&>().size()))>
+  Range(Container const& container, typename Container::size_type startFrom) {
+    auto const cdata = container.data();
+    auto const csize = container.size();
+    if (UNLIKELY(startFrom > csize)) {
+      std::__throw_out_of_range("index out of range");
     }
-    b_ = str.data() + startFrom;
-    e_ = str.data() + str.size();
-  }
-
-  template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
-  Range(const fbstring& str, fbstring::size_type startFrom,
-        fbstring::size_type size) {
-    if (UNLIKELY(startFrom > str.size())) {
-      throw std::out_of_range("index out of range");
+    b_ = cdata + startFrom;
+    e_ = cdata + csize;
+  }
+
+  template <
+      class Container,
+      class = typename std::enable_if<
+          std::is_same<Iter, typename Container::const_pointer>::value>::type,
+      class = decltype(
+          Iter(std::declval<Container const&>().data()),
+          Iter(
+              std::declval<Container const&>().data() +
+              std::declval<Container const&>().size()))>
+  Range(
+      Container const& container,
+      typename Container::size_type startFrom,
+      typename Container::size_type size) {
+    auto const cdata = container.data();
+    auto const csize = container.size();
+    if (UNLIKELY(startFrom > csize)) {
+      std::__throw_out_of_range("index out of range");
     }
-    b_ = str.data() + startFrom;
-    if (str.size() - startFrom < size) {
-      e_ = str.data() + str.size();
+    b_ = cdata + startFrom;
+    if (csize - startFrom < size) {
+      e_ = cdata + csize;
     } else {
       e_ = b_ + size;
     }
@@ -272,64 +310,101 @@ public:
   // Range<const unsigned char*> (aka ByteRange), as they're both frequently
   // used to represent ranges of bytes.  Allow explicit conversion in the other
   // direction.
-  template <class OtherIter, typename std::enable_if<
-      (std::is_same<Iter, const unsigned char*>::value &&
-       (std::is_same<OtherIter, const char*>::value ||
-        std::is_same<OtherIter, char*>::value)), int>::type = 0>
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (std::is_same<Iter, const unsigned char*>::value &&
+           (std::is_same<OtherIter, const char*>::value ||
+            std::is_same<OtherIter, char*>::value)),
+          int>::type = 0>
   /* implicit */ Range(const Range<OtherIter>& other)
-    : b_(reinterpret_cast<const unsigned char*>(other.begin())),
-      e_(reinterpret_cast<const unsigned char*>(other.end())) {
-  }
-
-  template <class OtherIter, typename std::enable_if<
-      (std::is_same<Iter, unsigned char*>::value &&
-       std::is_same<OtherIter, char*>::value), int>::type = 0>
+      : b_(reinterpret_cast<const unsigned char*>(other.begin())),
+        e_(reinterpret_cast<const unsigned char*>(other.end())) {}
+
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (std::is_same<Iter, unsigned char*>::value &&
+           std::is_same<OtherIter, char*>::value),
+          int>::type = 0>
   /* implicit */ Range(const Range<OtherIter>& other)
-    : b_(reinterpret_cast<unsigned char*>(other.begin())),
-      e_(reinterpret_cast<unsigned char*>(other.end())) {
-  }
-
-  template <class OtherIter, typename std::enable_if<
-      (std::is_same<Iter, const char*>::value &&
-       (std::is_same<OtherIter, const unsigned char*>::value ||
-        std::is_same<OtherIter, unsigned char*>::value)), int>::type = 0>
+      : b_(reinterpret_cast<unsigned char*>(other.begin())),
+        e_(reinterpret_cast<unsigned char*>(other.end())) {}
+
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (std::is_same<Iter, const char*>::value &&
+           (std::is_same<OtherIter, const unsigned char*>::value ||
+            std::is_same<OtherIter, unsigned char*>::value)),
+          int>::type = 0>
   explicit Range(const Range<OtherIter>& other)
-    : b_(reinterpret_cast<const char*>(other.begin())),
-      e_(reinterpret_cast<const char*>(other.end())) {
-  }
-
-  template <class OtherIter, typename std::enable_if<
-      (std::is_same<Iter, char*>::value &&
-       std::is_same<OtherIter, unsigned char*>::value), int>::type = 0>
+      : b_(reinterpret_cast<const char*>(other.begin())),
+        e_(reinterpret_cast<const char*>(other.end())) {}
+
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (std::is_same<Iter, char*>::value &&
+           std::is_same<OtherIter, unsigned char*>::value),
+          int>::type = 0>
   explicit Range(const Range<OtherIter>& other)
-    : b_(reinterpret_cast<char*>(other.begin())),
-      e_(reinterpret_cast<char*>(other.end())) {
-  }
+      : b_(reinterpret_cast<char*>(other.begin())),
+        e_(reinterpret_cast<char*>(other.end())) {}
 
   // Allow implicit conversion from Range<From> to Range<To> if From is
   // implicitly convertible to To.
-  template <class OtherIter, typename std::enable_if<
-     (!std::is_same<Iter, OtherIter>::value &&
-      std::is_convertible<OtherIter, Iter>::value), int>::type = 0>
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (!std::is_same<Iter, OtherIter>::value &&
+           std::is_convertible<OtherIter, Iter>::value),
+          int>::type = 0>
   constexpr /* implicit */ Range(const Range<OtherIter>& other)
-    : b_(other.begin()),
-      e_(other.end()) {
-  }
+      : b_(other.begin()), e_(other.end()) {}
 
   // Allow explicit conversion from Range<From> to Range<To> if From is
   // explicitly convertible to To.
-  template <class OtherIter, typename std::enable_if<
-    (!std::is_same<Iter, OtherIter>::value &&
-     !std::is_convertible<OtherIter, Iter>::value &&
-     std::is_constructible<Iter, const OtherIter&>::value), int>::type = 0>
+  template <
+      class OtherIter,
+      typename std::enable_if<
+          (!std::is_same<Iter, OtherIter>::value &&
+           !std::is_convertible<OtherIter, Iter>::value &&
+           std::is_constructible<Iter, const OtherIter&>::value),
+          int>::type = 0>
   constexpr explicit Range(const Range<OtherIter>& other)
-    : b_(other.begin()),
-      e_(other.end()) {
-  }
+      : b_(other.begin()), e_(other.end()) {}
+
+  /**
+   * Allow explicit construction of Range() from a std::array of a
+   * convertible type.
+   *
+   * For instance, this allows constructing StringPiece from a
+   * std::array<char, N> or a std::array<const char, N>
+   */
+  template <
+      class T,
+      size_t N,
+      typename = typename std::enable_if<
+          std::is_convertible<const T*, Iter>::value>::type>
+  constexpr explicit Range(const std::array<T, N>& array)
+      : b_{array.empty() ? nullptr : &array.at(0)},
+        e_{array.empty() ? nullptr : &array.at(0) + N} {}
+  template <
+      class T,
+      size_t N,
+      typename =
+          typename std::enable_if<std::is_convertible<T*, Iter>::value>::type>
+  constexpr explicit Range(std::array<T, N>& array)
+      : b_{array.empty() ? nullptr : &array.at(0)},
+        e_{array.empty() ? nullptr : &array.at(0) + N} {}
 
   Range& operator=(const Range& rhs) & = default;
   Range& operator=(Range&& rhs) & = default;
 
+  template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
+  Range& operator=(std::string&& rhs) = delete;
+
   void clear() {
     b_ = Iter();
     e_ = Iter();
@@ -350,21 +425,39 @@ public:
     reset(str.data(), str.size());
   }
 
-  size_type size() const {
-    assert(b_ <= e_);
-    return e_ - b_;
+  constexpr size_type size() const {
+    // It would be nice to assert(b_ <= e_) here.  This can be achieved even
+    // in a C++11 compatible constexpr function:
+    // http://ericniebler.com/2014/09/27/assert-and-constexpr-in-cxx11/
+    // Unfortunately current gcc versions have a bug causing it to reject
+    // this check in a constexpr function:
+    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71448
+    return size_type(e_ - b_);
+  }
+  constexpr size_type walk_size() const {
+    return size_type(std::distance(b_, e_));
+  }
+  constexpr bool empty() const {
+    return b_ == e_;
+  }
+  constexpr Iter data() const {
+    return b_;
+  }
+  constexpr Iter start() const {
+    return b_;
   }
-  size_type walk_size() const {
-    assert(b_ <= e_);
-    return std::distance(b_, e_);
+  constexpr Iter begin() const {
+    return b_;
+  }
+  constexpr Iter end() const {
+    return e_;
+  }
+  constexpr Iter cbegin() const {
+    return b_;
+  }
+  constexpr Iter cend() const {
+    return e_;
   }
-  bool empty() const { return b_ == e_; }
-  Iter data() const { return b_; }
-  Iter start() const { return b_; }
-  Iter begin() const { return b_; }
-  Iter end() const { return e_; }
-  Iter cbegin() const { return b_; }
-  Iter cend() const { return e_; }
   value_type& front() {
     assert(b_ < e_);
     return *b_;
@@ -381,16 +474,23 @@ public:
     assert(b_ < e_);
     return detail::value_before(e_);
   }
+
+  template <typename Tgt>
+  auto to() const
+      -> decltype(Tgt(std::declval<Iter const&>(), std::declval<size_type>())) {
+    return Tgt(b_, size());
+  }
   // Works only for Range<const char*> and Range<char*>
-  std::string str() const { return std::string(b_, size()); }
-  std::string toString() const { return str(); }
-  // Works only for Range<const char*> and Range<char*>
-  fbstring fbstr() const { return fbstring(b_, size()); }
-  fbstring toFbstring() const { return fbstr(); }
+  std::string str() const {
+    return to<std::string>();
+  }
+  std::string toString() const {
+    return to<std::string>();
+  }
 
   const_range_type castToConst() const {
     return const_range_type(*this);
-  };
+  }
 
   // Works only for Range<const char*> and Range<char*>
   int compare(const const_range_type& o) const {
@@ -402,8 +502,9 @@ public:
       // We check the signed bit of the subtraction and bit shift it
       // to produce either 0 or 2. The subtraction yields the
       // comparison values of either -1 or 1.
-      r = (static_cast<int>(
-             (osize - tsize) >> (CHAR_BIT * sizeof(size_t) - 1)) << 1) - 1;
+      r = (static_cast<int>((osize - tsize) >> (CHAR_BIT * sizeof(size_t) - 1))
+           << 1) -
+          1;
     }
     return r;
   }
@@ -419,12 +520,16 @@ public:
   }
 
   value_type& at(size_t i) {
-    if (i >= size()) throw std::out_of_range("index out of range");
+    if (i >= size()) {
+      std::__throw_out_of_range("index out of range");
+    }
     return b_[i];
   }
 
   const value_type& at(size_t i) const {
-    if (i >= size()) throw std::out_of_range("index out of range");
+    if (i >= size()) {
+      std::__throw_out_of_range("index out of range");
+    }
     return b_[i];
   }
 
@@ -434,6 +539,19 @@ public:
   // (The above advice does not apply if you are targeting a 32-bit system.)
   //
   // Works only for Range<const char*> and Range<char*>
+  //
+  //
+  //         ** WANT TO GET RID OF THIS LINT? **
+  //
+  // A) Use a better hash function (*cough*folly::Hash*cough*), but
+  //    only if you don't serialize data in a format that depends on
+  //    this formula (ie the writer and reader assume this exact hash
+  //    function is used).
+  //
+  // B) If you have to use this exact function then make your own hasher
+  //    object and copy the body over (see thrift example: D3972362).
+  //    https://github.com/facebook/fbthrift/commit/f8ed502e24ab4a32a9d5f266580
+  FOLLY_DEPRECATED("Replace with folly::Hash if the hash is not serialized")
   uint32_t hash() const {
     // Taken from fbi/nstring.h:
     //    Quick and dirty bernstein hash...fine for short ascii strings
@@ -446,18 +564,42 @@ public:
 
   void advance(size_type n) {
     if (UNLIKELY(n > size())) {
-      throw std::out_of_range("index out of range");
+      std::__throw_out_of_range("index out of range");
     }
     b_ += n;
   }
 
   void subtract(size_type n) {
     if (UNLIKELY(n > size())) {
-      throw std::out_of_range("index out of range");
+      std::__throw_out_of_range("index out of range");
     }
     e_ -= n;
   }
 
+  Range subpiece(size_type first, size_type length = npos) const {
+    if (UNLIKELY(first > size())) {
+      std::__throw_out_of_range("index out of range");
+    }
+
+    return Range(b_ + first, std::min(length, size() - first));
+  }
+
+  // unchecked versions
+  void uncheckedAdvance(size_type n) {
+    DCHECK_LE(n, size());
+    b_ += n;
+  }
+
+  void uncheckedSubtract(size_type n) {
+    DCHECK_LE(n, size());
+    e_ -= n;
+  }
+
+  Range uncheckedSubpiece(size_type first, size_type length = npos) const {
+    DCHECK_LE(first, size());
+    return Range(b_ + first, std::min(length, size() - first));
+  }
+
   void pop_front() {
     assert(b_ < e_);
     ++b_;
@@ -468,27 +610,23 @@ public:
     --e_;
   }
 
-  Range subpiece(size_type first, size_type length = npos) const {
-    if (UNLIKELY(first > size())) {
-      throw std::out_of_range("index out of range");
-    }
-
-    return Range(b_ + first, std::min(length, size() - first));
-  }
-
   // string work-alike functions
   size_type find(const_range_type str) const {
     return qfind(castToConst(), str);
   }
 
   size_type find(const_range_type str, size_t pos) const {
-    if (pos > size()) return std::string::npos;
+    if (pos > size()) {
+      return std::string::npos;
+    }
     size_t ret = qfind(castToConst().subpiece(pos), str);
     return ret == npos ? ret : ret + pos;
   }
 
   size_type find(Iter s, size_t pos, size_t n) const {
-    if (pos > size()) return std::string::npos;
+    if (pos > size()) {
+      return std::string::npos;
+    }
     auto forFinding = castToConst();
     size_t ret = qfind(
         pos ? forFinding.subpiece(pos) : forFinding, const_range_type(s, n));
@@ -502,7 +640,9 @@ public:
 
   // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor
   size_type find(const Iter s, size_t pos) const {
-    if (pos > size()) return std::string::npos;
+    if (pos > size()) {
+      return std::string::npos;
+    }
     size_type ret = qfind(castToConst().subpiece(pos), const_range_type(s));
     return ret == npos ? ret : ret + pos;
   }
@@ -516,7 +656,9 @@ public:
   }
 
   size_type find(value_type c, size_t pos) const {
-    if (pos > size()) return std::string::npos;
+    if (pos > size()) {
+      return std::string::npos;
+    }
     size_type ret = qfind(castToConst().subpiece(pos), c);
     return ret == npos ? ret : ret + pos;
   }
@@ -526,7 +668,9 @@ public:
   }
 
   size_type find_first_of(const_range_type needles, size_t pos) const {
-    if (pos > size()) return std::string::npos;
+    if (pos > size()) {
+      return std::string::npos;
+    }
     size_type ret = qfind_first_of(castToConst().subpiece(pos), needles);
     return ret == npos ? ret : ret + pos;
   }
@@ -575,24 +719,66 @@ public:
    * Does this Range start with another range?
    */
   bool startsWith(const const_range_type& other) const {
-    return size() >= other.size()
-      && castToConst().subpiece(0, other.size()) == other;
+    return size() >= other.size() &&
+        castToConst().subpiece(0, other.size()) == other;
   }
   bool startsWith(value_type c) const {
     return !empty() && front() == c;
   }
 
+  template <class Comp>
+  bool startsWith(const const_range_type& other, Comp&& eq) const {
+    if (size() < other.size()) {
+      return false;
+    }
+    auto const trunc = subpiece(0, other.size());
+    return std::equal(
+        trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq));
+  }
+
   /**
    * Does this Range end with another range?
    */
   bool endsWith(const const_range_type& other) const {
-    return size() >= other.size()
-      && castToConst().subpiece(size() - other.size()) == other;
+    return size() >= other.size() &&
+        castToConst().subpiece(size() - other.size()) == other;
   }
   bool endsWith(value_type c) const {
     return !empty() && back() == c;
   }
 
+  template <class Comp>
+  bool endsWith(const const_range_type& other, Comp&& eq) const {
+    if (size() < other.size()) {
+      return false;
+    }
+    auto const trunc = subpiece(size() - other.size());
+    return std::equal(
+        trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq));
+  }
+
+  template <class Comp>
+  bool equals(const const_range_type& other, Comp&& eq) const {
+    return size() == other.size() &&
+        std::equal(begin(), end(), other.begin(), std::forward<Comp>(eq));
+  }
+
+  /**
+   * Remove the items in [b, e), as long as this subrange is at the beginning
+   * or end of the Range.
+   *
+   * Required for boost::algorithm::trim()
+   */
+  void erase(Iter b, Iter e) {
+    if (b == b_) {
+      b_ = e;
+    } else if (e == e_) {
+      e_ = b;
+    } else {
+      std::__throw_out_of_range("index out of range");
+    }
+  }
+
   /**
    * Remove the given prefix and return true if the range starts with the given
    * prefix; return false otherwise.
@@ -718,7 +904,12 @@ public:
     auto i = find(delimiter);
     Range result(b_, i == std::string::npos ? size() : i);
 
-    b_ = result.end() == e_ ? e_ : std::next(result.end(), delimiter.size());
+    b_ = result.end() == e_
+        ? e_
+        : std::next(
+              result.end(),
+              typename std::iterator_traits<Iter>::difference_type(
+                  delimiter.size()));
 
     return result;
   }
@@ -786,24 +977,26 @@ public:
    * @author: Marcelo Juchem <marcelo@fb.com>
    */
   template <typename TProcess, typename... Args>
-  auto split_step(value_type delimiter, TProcess &&process, Args &&...args)
-    -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...))
-  { return process(split_step(delimiter), std::forward<Args>(args)...); }
+  auto split_step(value_type delimiter, TProcess&& process, Args&&... args)
+      -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...)) {
+    return process(split_step(delimiter), std::forward<Args>(args)...);
+  }
 
   template <typename TProcess, typename... Args>
-  auto split_step(Range delimiter, TProcess &&process, Args &&...args)
-    -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...))
-  { return process(split_step(delimiter), std::forward<Args>(args)...); }
+  auto split_step(Range delimiter, TProcess&& process, Args&&... args)
+      -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...)) {
+    return process(split_step(delimiter), std::forward<Args>(args)...);
+  }
 
-private:
+ private:
   Iter b_, e_;
 };
 
 template <class Iter>
 const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos;
 
-template <class T>
-void swap(Range<T>& lhs, Range<T>& rhs) {
+template <class Iter>
+void swap(Range<Iter>& lhs, Range<Iter>& rhs) {
   lhs.swap(rhs);
 }
 
@@ -811,7 +1004,7 @@ void swap(Range<T>& lhs, Range<T>& rhs) {
  * Create a range from two iterators, with type deduction.
  */
 template <class Iter>
-Range<Iter> range(Iter first, Iter last) {
+constexpr Range<Iter> range(Iter first, Iter last) {
   return Range<Iter>(first, last);
 }
 
@@ -819,32 +1012,63 @@ Range<Iter> range(Iter first, Iter last) {
  * Creates a range to reference the contents of a contiguous-storage container.
  */
 // Use pointers for types with '.data()' member
-template <class Collection,
-          class T = typename std::remove_pointer<
-              decltype(std::declval<Collection>().data())>::type>
-Range<T*> range(Collection&& v) {
-  return Range<T*>(v.data(), v.data() + v.size());
+template <class Collection>
+constexpr auto range(Collection& v) -> Range<decltype(v.data())> {
+  return Range<decltype(v.data())>(v.data(), v.data() + v.size());
+}
+template <class Collection>
+constexpr auto range(Collection const& v) -> Range<decltype(v.data())> {
+  return Range<decltype(v.data())>(v.data(), v.data() + v.size());
+}
+template <class Collection>
+constexpr auto crange(Collection const& v) -> Range<decltype(v.data())> {
+  return Range<decltype(v.data())>(v.data(), v.data() + v.size());
 }
 
 template <class T, size_t n>
-Range<T*> range(T (&array)[n]) {
+constexpr Range<T*> range(T (&array)[n]) {
   return Range<T*>(array, array + n);
 }
+template <class T, size_t n>
+constexpr Range<T const*> range(T const (&array)[n]) {
+  return Range<T const*>(array, array + n);
+}
+template <class T, size_t n>
+constexpr Range<T const*> crange(T const (&array)[n]) {
+  return Range<T const*>(array, array + n);
+}
+
+template <class T, size_t n>
+constexpr Range<T*> range(std::array<T, n>& array) {
+  return Range<T*>{array};
+}
+template <class T, size_t n>
+constexpr Range<T const*> range(std::array<T, n> const& array) {
+  return Range<T const*>{array};
+}
+template <class T, size_t n>
+constexpr Range<T const*> crange(std::array<T, n> const& array) {
+  return Range<T const*>{array};
+}
 
 typedef Range<const char*> StringPiece;
 typedef Range<char*> MutableStringPiece;
 typedef Range<const unsigned char*> ByteRange;
 typedef Range<unsigned char*> MutableByteRange;
 
-inline std::ostream& operator<<(std::ostream& os,
-                                const StringPiece piece) {
-  os.write(piece.start(), piece.size());
+template <class C>
+std::basic_ostream<C>& operator<<(
+    std::basic_ostream<C>& os,
+    Range<C const*> piece) {
+  using StreamSize = decltype(os.width());
+  os.write(piece.start(), static_cast<StreamSize>(piece.size()));
   return os;
 }
 
-inline std::ostream& operator<<(std::ostream& os,
-                                const MutableStringPiece piece) {
-  os.write(piece.start(), piece.size());
+template <class C>
+std::basic_ostream<C>& operator<<(std::basic_ostream<C>& os, Range<C*> piece) {
+  using StreamSize = decltype(os.width());
+  os.write(piece.start(), static_cast<StreamSize>(piece.size()));
   return os;
 }
 
@@ -852,13 +1076,13 @@ inline std::ostream& operator<<(std::ostream& os,
  * Templated comparison operators
  */
 
-template <class T>
-inline bool operator==(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator==(const Range<Iter>& lhs, const Range<Iter>& rhs) {
   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
 }
 
-template <class T>
-inline bool operator<(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator<(const Range<Iter>& lhs, const Range<Iter>& rhs) {
   return lhs.compare(rhs) < 0;
 }
 
@@ -871,12 +1095,10 @@ namespace detail {
 template <class A, class B>
 struct ComparableAsStringPiece {
   enum {
-    value =
-    (std::is_convertible<A, StringPiece>::value
-     && std::is_same<B, StringPiece>::value)
-    ||
-    (std::is_convertible<B, StringPiece>::value
-     && std::is_same<A, StringPiece>::value)
+    value = (std::is_convertible<A, StringPiece>::value &&
+             std::is_same<B, StringPiece>::value) ||
+        (std::is_convertible<B, StringPiece>::value &&
+         std::is_same<A, StringPiece>::value)
   };
 };
 
@@ -886,8 +1108,7 @@ struct ComparableAsStringPiece {
  * operator== through conversion for Range<const char*>
  */
 template <class T, class U>
-typename
-std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+_t<std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>>
 operator==(const T& lhs, const U& rhs) {
   return StringPiece(lhs) == StringPiece(rhs);
 }
@@ -896,8 +1117,7 @@ operator==(const T& lhs, const U& rhs) {
  * operator< through conversion for Range<const char*>
  */
 template <class T, class U>
-typename
-std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+_t<std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>>
 operator<(const T& lhs, const U& rhs) {
   return StringPiece(lhs) < StringPiece(rhs);
 }
@@ -906,8 +1126,7 @@ operator<(const T& lhs, const U& rhs) {
  * operator> through conversion for Range<const char*>
  */
 template <class T, class U>
-typename
-std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+_t<std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>>
 operator>(const T& lhs, const U& rhs) {
   return StringPiece(lhs) > StringPiece(rhs);
 }
@@ -916,8 +1135,7 @@ operator>(const T& lhs, const U& rhs) {
  * operator< through conversion for Range<const char*>
  */
 template <class T, class U>
-typename
-std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+_t<std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>>
 operator<=(const T& lhs, const U& rhs) {
   return StringPiece(lhs) <= StringPiece(rhs);
 }
@@ -926,33 +1144,25 @@ operator<=(const T& lhs, const U& rhs) {
  * operator> through conversion for Range<const char*>
  */
 template <class T, class U>
-typename
-std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+_t<std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>>
 operator>=(const T& lhs, const U& rhs) {
   return StringPiece(lhs) >= StringPiece(rhs);
 }
 
-// Do NOT use this, use SpookyHashV2 instead, see commment on hash() above.
-struct StringPieceHash {
-  std::size_t operator()(const StringPiece str) const {
-    return static_cast<std::size_t>(str.hash());
-  }
-};
-
 /**
  * Finds substrings faster than brute force by borrowing from Boyer-Moore
  */
-template <class T, class Comp>
-size_t qfind(const Range<T>& haystack,
-             const Range<T>& needle,
-             Comp eq) {
+template <class Iter, class Comp>
+size_t qfind(const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq) {
   // Don't use std::search, use a Boyer-Moore-like trick by comparing
   // the last characters first
   auto const nsize = needle.size();
   if (haystack.size() < nsize) {
     return std::string::npos;
   }
-  if (!nsize) return 0;
+  if (!nsize) {
+    return 0;
+  }
   auto const nsize_1 = nsize - 1;
   auto const lastNeedle = needle[nsize_1];
 
@@ -974,7 +1184,7 @@ size_t qfind(const Range<T>& haystack,
     }
     // Here we know that the last char matches
     // Continue in pedestrian mode
-    for (size_t j = 0; ; ) {
+    for (size_t j = 0;;) {
       assert(j < nsize);
       if (!eq(i[j], needle[j])) {
         // Not found, we can skip
@@ -991,7 +1201,7 @@ size_t qfind(const Range<T>& haystack,
       // Check if done searching
       if (++j == nsize) {
         // Yay
-        return i - haystack.begin();
+        return size_t(i - haystack.begin());
       }
     }
   }
@@ -1000,37 +1210,24 @@ size_t qfind(const Range<T>& haystack,
 
 namespace detail {
 
-size_t qfind_first_byte_of_nosse(const StringPiece haystack,
-                                 const StringPiece needles);
-
-#if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
-size_t qfind_first_byte_of_sse42(const StringPiece haystack,
-                                 const StringPiece needles);
-
-inline size_t qfind_first_byte_of(const StringPiece haystack,
-                                  const StringPiece needles) {
-  static auto const qfind_first_byte_of_fn =
-    folly::CpuId().sse42() ? qfind_first_byte_of_sse42
-                           : qfind_first_byte_of_nosse;
+inline size_t qfind_first_byte_of(
+    const StringPiece haystack,
+    const StringPiece needles) {
+  static auto const qfind_first_byte_of_fn = folly::CpuId().sse42()
+      ? qfind_first_byte_of_sse42
+      : qfind_first_byte_of_nosse;
   return qfind_first_byte_of_fn(haystack, needles);
 }
 
-#else
-inline size_t qfind_first_byte_of(const StringPiece haystack,
-                                  const StringPiece needles) {
-  return qfind_first_byte_of_nosse(haystack, needles);
-}
-#endif // FOLLY_HAVE_EMMINTRIN_H
-
 } // namespace detail
 
-template <class T, class Comp>
-size_t qfind_first_of(const Range<T> & haystack,
-                      const Range<T> & needles,
-                      Comp eq) {
-  auto ret = std::find_first_of(haystack.begin(), haystack.end(),
-                                needles.begin(), needles.end(),
-                                eq);
+template <class Iter, class Comp>
+size_t qfind_first_of(
+    const Range<Iter>& haystack,
+    const Range<Iter>& needles,
+    Comp eq) {
+  auto ret = std::find_first_of(
+      haystack.begin(), haystack.end(), needles.begin(), needles.end(), eq);
   return ret == haystack.end() ? std::string::npos : ret - haystack.begin();
 }
 
@@ -1048,27 +1245,30 @@ struct AsciiCaseSensitive {
 struct AsciiCaseInsensitive {
   bool operator()(char lhs, char rhs) const {
     char k = lhs ^ rhs;
-    if (k == 0) return true;
-    if (k != 32) return false;
+    if (k == 0) {
+      return true;
+    }
+    if (k != 32) {
+      return false;
+    }
     k = lhs | rhs;
     return (k >= 'a' && k <= 'z');
   }
 };
 
-extern const AsciiCaseSensitive asciiCaseSensitive;
-extern const AsciiCaseInsensitive asciiCaseInsensitive;
-
-template <class T>
-size_t qfind(const Range<T>& haystack,
-             const typename Range<T>::value_type& needle) {
+template <class Iter>
+size_t qfind(
+    const Range<Iter>& haystack,
+    const typename Range<Iter>::value_type& needle) {
   auto pos = std::find(haystack.begin(), haystack.end(), needle);
   return pos == haystack.end() ? std::string::npos : pos - haystack.data();
 }
 
-template <class T>
-size_t rfind(const Range<T>& haystack,
-             const typename Range<T>::value_type& needle) {
-  for (auto i = haystack.size(); i-- > 0; ) {
+template <class Iter>
+size_t rfind(
+    const Range<Iter>& haystack,
+    const typename Range<Iter>::value_type& needle) {
+  for (auto i = haystack.size(); i-- > 0;) {
     if (haystack[i] == needle) {
       return i;
     }
@@ -1079,73 +1279,123 @@ size_t rfind(const Range<T>& haystack,
 // specialization for StringPiece
 template <>
 inline size_t qfind(const Range<const char*>& haystack, const char& needle) {
+  // memchr expects a not-null pointer, early return if the range is empty.
+  if (haystack.empty()) {
+    return std::string::npos;
+  }
   auto pos = static_cast<const char*>(
-    ::memchr(haystack.data(), needle, haystack.size()));
+      ::memchr(haystack.data(), needle, haystack.size()));
   return pos == nullptr ? std::string::npos : pos - haystack.data();
 }
 
-#if FOLLY_HAVE_MEMRCHR
 template <>
 inline size_t rfind(const Range<const char*>& haystack, const char& needle) {
+  // memchr expects a not-null pointer, early return if the range is empty.
+  if (haystack.empty()) {
+    return std::string::npos;
+  }
   auto pos = static_cast<const char*>(
-    ::memrchr(haystack.data(), needle, haystack.size()));
+      ::memrchr(haystack.data(), needle, haystack.size()));
   return pos == nullptr ? std::string::npos : pos - haystack.data();
 }
-#endif
 
 // specialization for ByteRange
 template <>
-inline size_t qfind(const Range<const unsigned char*>& haystack,
-                    const unsigned char& needle) {
+inline size_t qfind(
+    const Range<const unsigned char*>& haystack,
+    const unsigned char& needle) {
+  // memchr expects a not-null pointer, early return if the range is empty.
+  if (haystack.empty()) {
+    return std::string::npos;
+  }
   auto pos = static_cast<const unsigned char*>(
-    ::memchr(haystack.data(), needle, haystack.size()));
+      ::memchr(haystack.data(), needle, haystack.size()));
   return pos == nullptr ? std::string::npos : pos - haystack.data();
 }
 
-#if FOLLY_HAVE_MEMRCHR
 template <>
-inline size_t rfind(const Range<const unsigned char*>& haystack,
-                    const unsigned char& needle) {
+inline size_t rfind(
+    const Range<const unsigned char*>& haystack,
+    const unsigned char& needle) {
+  // memchr expects a not-null pointer, early return if the range is empty.
+  if (haystack.empty()) {
+    return std::string::npos;
+  }
   auto pos = static_cast<const unsigned char*>(
-    ::memrchr(haystack.data(), needle, haystack.size()));
+      ::memrchr(haystack.data(), needle, haystack.size()));
   return pos == nullptr ? std::string::npos : pos - haystack.data();
 }
-#endif
 
-template <class T>
-size_t qfind_first_of(const Range<T>& haystack,
-                      const Range<T>& needles) {
-  return qfind_first_of(haystack, needles, asciiCaseSensitive);
+template <class Iter>
+size_t qfind_first_of(const Range<Iter>& haystack, const Range<Iter>& needles) {
+  return qfind_first_of(haystack, needles, AsciiCaseSensitive());
 }
 
 // specialization for StringPiece
 template <>
-inline size_t qfind_first_of(const Range<const char*>& haystack,
-                             const Range<const char*>& needles) {
+inline size_t qfind_first_of(
+    const Range<const char*>& haystack,
+    const Range<const char*>& needles) {
   return detail::qfind_first_byte_of(haystack, needles);
 }
 
 // specialization for ByteRange
 template <>
-inline size_t qfind_first_of(const Range<const unsigned char*>& haystack,
-                             const Range<const unsigned char*>& needles) {
-  return detail::qfind_first_byte_of(StringPiece(haystack),
-                                     StringPiece(needles));
+inline size_t qfind_first_of(
+    const Range<const unsigned char*>& haystack,
+    const Range<const unsigned char*>& needles) {
+  return detail::qfind_first_byte_of(
+      StringPiece(haystack), StringPiece(needles));
 }
 
-template<class Key>
+template <class Key, class Enable>
 struct hasher;
 
-template <class T> struct hasher<folly::Range<T*>> {
+template <class T>
+struct hasher<
+    folly::Range<T*>,
+    typename std::enable_if<std::is_pod<T>::value, void>::type> {
   size_t operator()(folly::Range<T*> r) const {
     return hash::SpookyHashV2::Hash64(r.begin(), r.size() * sizeof(T), 0);
   }
 };
 
-}  // !namespace folly
+/**
+ * _sp is a user-defined literal suffix to make an appropriate Range
+ * specialization from a literal string.
+ *
+ * Modeled after C++17's `sv` suffix.
+ */
+inline namespace literals {
+inline namespace string_piece_literals {
+constexpr Range<char const*> operator"" _sp(
+    char const* str,
+    size_t len) noexcept {
+  return Range<char const*>(str, len);
+}
 
-#pragma GCC diagnostic pop
+constexpr Range<char16_t const*> operator"" _sp(
+    char16_t const* str,
+    size_t len) noexcept {
+  return Range<char16_t const*>(str, len);
+}
 
-FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
+constexpr Range<char32_t const*> operator"" _sp(
+    char32_t const* str,
+    size_t len) noexcept {
+  return Range<char32_t const*>(str, len);
+}
 
-#endif // FOLLY_RANGE_H_
+constexpr Range<wchar_t const*> operator"" _sp(
+    wchar_t const* str,
+    size_t len) noexcept {
+  return Range<wchar_t const*>(str, len);
+}
+} // namespace string_piece_literals
+} // namespace literals
+
+} // namespace folly
+
+FOLLY_POP_WARNING
+
+FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);