folly/folly/Range.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Docs: https://fburl.com/fbcref_range
//

/**
 * Range abstraction using a pair of iterators. It is not
 * similar to boost's range abstraction because an API identical
 * with the former StringPiece class is required, which is used alot
 * internally. This abstraction does fulfill the needs of boost's
 * range-oriented algorithms though.
 *
 * Note: (Keep memory lifetime in mind when using this class, since it
 * does not manage the data it refers to - just like an iterator
 * would not.)
 *
 * Additional documentation is in folly/docs/Range.md
 *
 * @refcode folly/docs/examples/folly/Range.h
 * @struct folly::range
 */

#pragma once

#include <folly/Portability.h>
#include <folly/hash/SpookyHashV2.h>
#include <folly/lang/CString.h>
#include <folly/lang/Exception.h>
#include <folly/portability/Constexpr.h>

#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cstddef>
#include <cstring>
#include <iosfwd>
#include <iterator>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>

#if __has_include(<fmt/format.h>)
#include <fmt/format.h>
#endif

#include <folly/CpuId.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.
FOLLY_PUSH_WARNING
FOLLY_GNU_DISABLE_WARNING(…)

namespace folly {

/**
 * Ubiquitous helper template for knowing what's a string.
 */
template <class T>
struct IsSomeString : std::false_type { … };

IsSomeString<std::basic_string<char, std::char_traits<char>, Alloc>>;

template <class Iter>
class Range;

/**
 * Finds the first occurrence of needle in haystack. The algorithm is on
 * average faster than O(haystack.size() * needle.size()) but not as fast
 * as Boyer-Moore. On the upside, it does not do any upfront
 * preprocessing and does not allocate memory.
 */
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 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 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 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.
 */
namespace detail {

/*
 * 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 <>
struct IsCharPointer<char*> { … };

template <>
struct IsCharPointer<const char*> { … };

template <class T>
struct IsUnsignedCharPointer { … };

template <>
struct IsUnsignedCharPointer<unsigned char*> { … };

template <>
struct IsUnsignedCharPointer<const unsigned char*> { … };

void range_is_char_type_f_(char const*);
void range_is_char_type_f_(wchar_t const*);
#if (defined(__cpp_char8_t) && __cpp_char8_t >= 201811L) || \
    FOLLY_CPLUSPLUS >= 202002
void range_is_char_type_f_(char8_t const*);
#endif
void range_is_char_type_f_(char16_t const*);
void range_is_char_type_f_(char32_t const*);
range_is_char_type_d_;
range_is_char_type_v_;

void range_is_byte_type_f_(unsigned char const*);
void range_is_byte_type_f_(signed char const*);
void range_is_byte_type_f_(std::byte const*);
range_is_byte_type_d_;
range_is_byte_type_v_;

struct range_traits_char_ { … };
struct range_traits_byte_ { … };
struct range_traits_fbck_ { … };

range_traits_c_;
range_traits_t_;

} // namespace detail

template <class Iter>
class Range { … };

template <class Iter>
const typename Range<Iter>::size_type Range<Iter>::npos = …;

template <class Iter>
void swap(Range<Iter>& lhs, Range<Iter>& rhs) { … }

/**
 * Create a range from two iterators, with type deduction.
 */
template <class Iter>
constexpr 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>
constexpr auto range(Collection& v) -> Range<decltype(v.data())> { … }
template <class Collection>
constexpr auto range(Collection const& v) -> Range<decltype(v.data())> { … }
template <class Collection>
constexpr auto crange(Collection const& v) -> Range<decltype(v.data())> { … }

template <class T, size_t n>
constexpr Range<T*> range(T (&array)[n]) { … }
template <class T, size_t n>
constexpr Range<T const*> range(T const (&array)[n]) { … }
template <class T, size_t n>
constexpr Range<T const*> crange(T const (&array)[n]) { … }

template <class T, size_t n>
constexpr Range<T*> range(std::array<T, n>& array) { … }
template <class T, size_t n>
constexpr Range<T const*> range(std::array<T, n> const& array) { … }
template <class T, size_t n>
constexpr Range<T const*> crange(std::array<T, n> const& array) { … }

template <class T>
constexpr Range<T const*> range(std::initializer_list<T> ilist) { … }

template <class T>
constexpr Range<T const*> crange(std::initializer_list<T> ilist) { … }

StringPiece;
MutableStringPiece;
ByteRange;
MutableByteRange;

template <class C>
std::basic_ostream<C>& operator<<(
    std::basic_ostream<C>& os, Range<C const*> piece) { … }

template <class C>
std::basic_ostream<C>& operator<<(std::basic_ostream<C>& os, Range<C*> piece) { … }

/**
 * Templated comparison operators
 */

template <class Iter>
inline bool operator==(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

template <class Iter>
inline bool operator!=(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

template <class Iter>
inline bool operator<(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

template <class Iter>
inline bool operator<=(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

template <class Iter>
inline bool operator>(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

template <class Iter>
inline bool operator>=(const Range<Iter>& lhs, const Range<Iter>& rhs) { … }

/**
 * Specializations of comparison operators for StringPiece
 */

namespace detail {

template <class A, class B>
struct ComparableAsStringPiece { … };

} // namespace detail

/**
 * operator== through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator==(
    const T& lhs, const U& rhs) { … }

/**
 * operator!= through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator!=(
    const T& lhs, const U& rhs) { … }

/**
 * operator< through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator<(
    const T& lhs, const U& rhs) { … }

/**
 * operator> through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator>(
    const T& lhs, const U& rhs) { … }

/**
 * operator< through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator<=(
    const T& lhs, const U& rhs) { … }

/**
 * operator> through conversion for Range<const char*>
 */
template <class T, class U>
std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator>=(
    const T& lhs, const U& rhs) { … }

/**
 * Finds substrings faster than brute force by borrowing from Boyer-Moore
 */
template <class Iter, class Comp>
size_t qfind(const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq) { … }

namespace detail {

inline size_t qfind_first_byte_of(
    const StringPiece haystack, const StringPiece needles) { … }

} // namespace detail

template <class Iter, class Comp>
size_t qfind_first_of(
    const Range<Iter>& haystack, const Range<Iter>& needles, Comp eq) { … }

struct AsciiCaseSensitive { … };

/**
 * Check if two ascii characters are case insensitive equal.
 * The difference between the lower/upper case characters are the 6-th bit.
 * We also check they are alpha chars, in case of xor = 32.
 */
struct AsciiCaseInsensitive { … };

template <class Iter>
size_t qfind(
    const Range<Iter>& haystack,
    const typename Range<Iter>::value_type& needle) { … }

template <class Iter>
size_t rfind(
    const Range<Iter>& haystack,
    const typename Range<Iter>::value_type& needle) { … }

// specialization for StringPiece
template <>
inline size_t qfind(const Range<const char*>& haystack, const char& needle) { … }

template <>
inline size_t rfind(const Range<const char*>& haystack, const char& needle) { … }

// specialization for ByteRange
template <>
inline size_t qfind(
    const Range<const unsigned char*>& haystack, const unsigned char& needle) { … }

template <>
inline size_t rfind(
    const Range<const unsigned char*>& haystack, const unsigned char& needle) { … }

template <class Iter>
size_t qfind_first_of(const Range<Iter>& haystack, const Range<Iter>& needles) { … }

// specialization for StringPiece
template <>
inline size_t qfind_first_of(
    const Range<const char*>& haystack, const Range<const char*>& needles) { … }

// specialization for ByteRange
template <>
inline size_t qfind_first_of(
    const Range<const unsigned char*>& haystack,
    const Range<const unsigned char*>& needles) { … }

template <class Key, class Enable>
struct hasher;

hasher<folly::Range<T *>, std::enable_if_t<std::is_integral<T>::value, void>>;

/**
 * _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 { … }

#if defined(__cpp_char8_t) && __cpp_char8_t >= 201811L
constexpr Range<char8_t const*> operator""_sp(
    char8_t const* str, size_t len) noexcept {
  return Range<char8_t const*>(str, len);
}
#endif

constexpr Range<char16_t const*> operator""_sp(
    char16_t const* str, size_t len) noexcept { … }

constexpr Range<char32_t const*> operator""_sp(
    char32_t const* str, size_t len) noexcept { … }

constexpr Range<wchar_t const*> operator""_sp(
    wchar_t const* str, size_t len) noexcept { … }
} // namespace string_piece_literals
} // namespace literals

} // namespace folly

// Avoid ambiguity in older fmt versions due to StringPiece's conversions.
#if FMT_VERSION >= 70000
namespace fmt {
template <>
struct formatter<folly::StringPiece> : private formatter<string_view> { … };
} // namespace fmt
#endif

FOLLY_POP_WARNING

FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(…)

// Unfortunately it is not possible to forward declare enable_view under
// MSVC 2019.8 due to compiler bugs, so we need to include the actual
// definition if available.
#if __has_include(<range/v3/range/concepts.hpp>) && defined(_MSC_VER)
#include <range/v3/range/concepts.hpp> // @manual
#else
namespace ranges {
enable_view;
} // namespace ranges
#endif

// Tell the range-v3 library that this type should satisfy
// the view concept (a lightweight, non-owning range).
namespace ranges {
enable_view;
} // namespace ranges