blob: 26ecbc4f89234a649b45dc4ea03cd30dd5599002 [file] [log] [blame]
//===--- STLExtras.h - additions to the STL ---------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
/// \file Provides STL-style algorithms for convenience.
//
//===----------------------------------------------------------------------===//
#ifndef SWIFT_BASIC_INTERLEAVE_H
#define SWIFT_BASIC_INTERLEAVE_H
#include "swift/Basic/LLVM.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Casting.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <numeric>
#include <type_traits>
#include <unordered_set>
namespace swift {
//===----------------------------------------------------------------------===//
// Function Traits
//===----------------------------------------------------------------------===//
template <class T>
struct function_traits : function_traits<decltype(&T::operator())> {};
// function
template <class R, class... Args> struct function_traits<R(Args...)> {
using result_type = R;
using argument_types = std::tuple<Args...>;
};
// function pointer
template <class R, class... Args> struct function_traits<R (*)(Args...)> {
using result_type = R;
using argument_types = std::tuple<Args...>;
};
// std::function
template <class R, class... Args>
struct function_traits<std::function<R(Args...)>> {
using result_type = R;
using argument_types = std::tuple<Args...>;
};
// pointer-to-member-function (i.e., operator()'s)
template <class T, class R, class... Args>
struct function_traits<R (T::*)(Args...)> {
using result_type = R;
using argument_types = std::tuple<Args...>;
};
template <class T, class R, class... Args>
struct function_traits<R (T::*)(Args...) const> {
using result_type = R;
using argument_types = std::tuple<Args...>;
};
/// @{
/// The equivalent of std::for_each, but for two lists at once.
template <typename InputIt1, typename InputIt2, typename BinaryFunction>
inline void for_each(InputIt1 I1, InputIt1 E1, InputIt2 I2, BinaryFunction f) {
while (I1 != E1) {
f(*I1, *I2);
++I1; ++I2;
}
}
template <typename Container1, typename Container2, typename BinaryFunction>
inline void for_each(const Container1 &c1, const Container2 &c2,
BinaryFunction f) {
assert(c1.size() == c2.size());
for_each(c1.begin(), c1.end(), c2.begin(), f);
}
/// The equivalent of std::for_each, but for three lists at once.
template <typename InputIt1, typename InputIt2, typename InputIt3,
typename TernaryFunction>
inline void for_each3(InputIt1 I1, InputIt1 E1, InputIt2 I2, InputIt3 I3,
TernaryFunction f) {
while (I1 != E1) {
f(*I1, *I2, *I3);
++I1; ++I2; ++I3;
}
}
template <typename Container1, typename Container2, typename Container3,
typename TernaryFunction>
inline void for_each3(const Container1 &c1, const Container2 &c2,
const Container3 &c3,
TernaryFunction f) {
assert(c1.size() == c2.size());
assert(c2.size() == c3.size());
for_each3(c1.begin(), c1.end(), c2.begin(), c3.begin(), f);
}
/// The equivalent of std::for_each, but visits the set union of two sorted
/// lists without allocating additional memory.
///
/// This has the following requirements:
///
/// 1. The ranges must be sorted.
/// 2. The elements must have the same type.
/// 3. There are no duplicate elements.
/// 4. All elements must be comparable with std::less.
template <typename InputIt1, typename InputIt2, typename BinaryFunction>
inline void set_union_for_each(InputIt1 I1, InputIt1 E1, InputIt2 I2,
InputIt2 E2, BinaryFunction f) {
static_assert(
std::is_same<
typename std::iterator_traits<InputIt1>::value_type,
typename std::iterator_traits<InputIt2>::value_type
>::value,
"Expected both iterator types to have the same underlying value type");
using RefTy = typename std::iterator_traits<InputIt1>::reference;
while (true) {
// If we have reached the end of either list, visit the rest of the other
// list, We do not need to worry about duplicates since each array we know
// is unique.
if (I1 == E1) {
std::for_each(I2, E2, f);
return;
}
if (I2 == E2) {
std::for_each(I1, E1, f);
return;
}
// If I1 < I2, then visit I1 and continue.
if (std::less<RefTy>()(*I1, *I2)) {
f(*I1);
++I1;
continue;
}
// If I2 < I1, visit I2 and continue.
if (std::less<RefTy>()(*I2, *I1)) {
f(*I2);
++I2;
continue;
}
// Otherwise, we know that I1 and I2 equal. We know that we can only have
// one of each element in each list, so we can just visit I1 and continue.
f(*I1);
++I1;
++I2;
}
}
/// A container adapter for set_union_for_each.
///
/// To see the requirements upon the containers, please see the iterator based
/// set_union_for_each.
template <typename Container1, typename Container2, typename UnaryFunction>
inline void set_union_for_each(const Container1 &C1, const Container2 &C2,
UnaryFunction f) {
// Make sure that our iterators have the same value type.
static_assert(
std::is_same<
typename std::iterator_traits<
typename Container1::iterator
>::value_type,
typename std::iterator_traits<
typename Container2::iterator
>::value_type
>::value,
"Expected both containers to have the same iterator value type");
set_union_for_each(C1.begin(), C1.end(), C2.begin(), C2.end(), f);
}
/// If \p it is equal to \p end, then return \p defaultIter. Otherwise, return
/// std::next(\p it).
template <typename Iterator>
inline Iterator next_or_default(Iterator it, Iterator end,
Iterator defaultIter) {
return (it == end) ? defaultIter : std::next(it);
}
/// If \p it is equal to \p begin, then return \p defaultIter. Otherwise, return
/// std::prev(\p it).
template <typename Iterator>
inline Iterator prev_or_default(Iterator it, Iterator begin,
Iterator defaultIter) {
return (it == begin) ? defaultIter : std::prev(it);
}
/// Takes an iterator and an iterator pointing to the end of the iterator range.
/// If the iterator already points to the end of its range, simply return it,
/// otherwise return the next element.
template <typename Iterator>
inline Iterator next_or_end(Iterator it, Iterator end) {
return next_or_default(it, end, end);
}
template <typename Iterator>
inline Iterator prev_or_begin(Iterator it, Iterator begin) {
return prev_or_default(it, begin, begin);
}
/// @}
/// An iterator that walks a linked list of objects until it reaches
/// a null pointer.
template <class T, T* (&getNext)(T*)>
class LinkedListIterator {
T *Pointer;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = T *;
using reference = T *;
using pointer = void;
/// Returns an iterator range starting from the given pointer and
/// running until it reaches a null pointer.
static llvm::iterator_range<LinkedListIterator> rangeBeginning(T *pointer) {
return {pointer, nullptr};
}
constexpr LinkedListIterator(T *pointer) : Pointer(pointer) {}
T *operator*() const {
assert(Pointer && "dereferencing a null iterator");
return Pointer;
}
LinkedListIterator &operator++() {
Pointer = getNext(Pointer);
return *this;
}
LinkedListIterator operator++(int) {
auto copy = *this;
Pointer = getNext(Pointer);
return copy;
}
friend bool operator==(LinkedListIterator lhs, LinkedListIterator rhs) {
return lhs.Pointer == rhs.Pointer;
}
friend bool operator!=(LinkedListIterator lhs, LinkedListIterator rhs) {
return lhs.Pointer != rhs.Pointer;
}
};
/// An iterator that transforms the result of an underlying bidirectional
/// iterator with a given operation.
///
/// Slightly different semantics from llvm::map_iterator, but we should
/// probably figure out how to merge them eventually.
///
/// \tparam Iterator the underlying iterator.
///
/// \tparam Operation A function object that transforms the underlying
/// sequence's values into the new sequence's values.
template<typename Iterator, typename Operation>
class TransformIterator {
Iterator Current;
/// FIXME: Could optimize away this storage with EBCO tricks.
Operation Op;
/// The underlying reference type, which will be passed to the
/// operation.
using OpTraits = function_traits<Operation>;
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = typename OpTraits::result_type;
using reference = value_type;
using pointer = void; // FIXME: Should provide a pointer proxy.
using difference_type =
typename std::iterator_traits<Iterator>::difference_type;
/// Construct a new transforming iterator for the given iterator
/// and operation.
TransformIterator(Iterator current, Operation op)
: Current(current), Op(op) { }
reference operator*() const {
return Op(*Current);
}
TransformIterator &operator++() {
++Current;
return *this;
}
TransformIterator operator++(int) {
TransformIterator old = *this;
++*this;
return old;
}
TransformIterator &operator--() {
--Current;
return *this;
}
TransformIterator operator--(int) {
TransformIterator old = *this;
--*this;
return old;
}
friend bool operator==(TransformIterator lhs, TransformIterator rhs) {
return lhs.Current == rhs.Current;
}
friend bool operator!=(TransformIterator lhs, TransformIterator rhs) {
return !(lhs == rhs);
}
};
/// Create a new transform iterator.
template<typename Iterator, typename Operation>
inline TransformIterator<Iterator, Operation>
makeTransformIterator(Iterator current, Operation op) {
return TransformIterator<Iterator, Operation>(current, op);
}
/// A range transformed by a specific predicate.
template<typename Range, typename Operation>
class TransformRange {
Range Rng;
Operation Op;
public:
using iterator = TransformIterator<decltype(Rng.begin()), Operation>;
TransformRange(Range range, Operation op)
: Rng(range), Op(op) { }
iterator begin() const { return iterator(Rng.begin(), Op); }
iterator end() const { return iterator(Rng.end(), Op); }
bool empty() const { return begin() == end(); }
// The dummy template parameter keeps 'size()' from being eagerly
// instantiated.
template <typename Dummy = Range>
typename function_traits<decltype(&Dummy::size)>::result_type
size() const {
return Rng.size();
}
template <typename Index>
typename function_traits<Operation>::result_type
operator[](Index index) const {
return Op(Rng[index]);
}
typename std::iterator_traits<iterator>::value_type front() const {
assert(!empty() && "Front of empty range");
return *begin();
}
};
/// Create a new transform range.
template<typename Range, typename Operation>
inline TransformRange<Range, Operation>
makeTransformRange(Range range, Operation op) {
return TransformRange<Range, Operation>(range, op);
}
/// An iterator that filters and transforms the results of an
/// underlying forward iterator based on a transformation from the underlying
/// value type to an optional result type.
///
/// \tparam Iterator the underlying iterator.
///
/// \tparam OptionalTransform A function object that maps a value of
/// the underlying iterator type to an optional containing a value of
/// the resulting sequence, or an empty optional if this item should
/// be skipped.
template<typename Iterator, typename OptionalTransform>
class OptionalTransformIterator {
Iterator Current, End;
/// FIXME: Could optimize away this storage with EBCO tricks.
OptionalTransform Op;
/// Skip any non-matching elements.
void skipNonMatching() {
while (Current != End && !Op(*Current))
++Current;
}
using UnderlyingReference =
typename std::iterator_traits<Iterator>::reference;
using ResultReference =
typename std::result_of<OptionalTransform(UnderlyingReference)>::type;
public:
/// Used to indicate when the current iterator has already been
/// "primed", meaning that it's at the end or points to a value that
/// satisfies the transform.
enum PrimedT { Primed };
using iterator_category = std::forward_iterator_tag;
using reference = typename ResultReference::value_type;
using value_type = typename ResultReference::value_type;
using pointer = void; // FIXME: should add a proxy here.
using difference_type =
typename std::iterator_traits<Iterator>::difference_type;
/// Construct a new optional transform iterator for the given
/// iterator range and operation.
OptionalTransformIterator(Iterator current, Iterator end,
OptionalTransform op)
: Current(current), End(end), Op(op)
{
// Prime the iterator.
skipNonMatching();
}
/// Construct a new optional transform iterator for the given iterator range
/// and operation, where the iterator range has already been
/// "primed" by ensuring that it is empty or the current iterator
/// points to something that matches the operation.
OptionalTransformIterator(Iterator current, Iterator end,
OptionalTransform op, PrimedT)
: Current(current), End(end), Op(op)
{
// Assert that the iterators have already been primed.
assert((Current == End || Op(*Current)) && "Not primed!");
}
reference operator*() const {
return *Op(*Current);
}
reference operator*() { return *Op(*Current); }
OptionalTransformIterator &operator++() {
++Current;
skipNonMatching();
return *this;
}
OptionalTransformIterator operator++(int) {
OptionalTransformIterator old = *this;
++*this;
return old;
}
friend bool operator==(OptionalTransformIterator lhs,
OptionalTransformIterator rhs) {
return lhs.Current == rhs.Current;
}
friend bool operator!=(OptionalTransformIterator lhs,
OptionalTransformIterator rhs) {
return !(lhs == rhs);
}
};
/// Create a new filter iterator.
template<typename Iterator, typename OptionalTransform>
inline OptionalTransformIterator<Iterator, OptionalTransform>
makeOptionalTransformIterator(Iterator current, Iterator end,
OptionalTransform op) {
return OptionalTransformIterator<Iterator, OptionalTransform>(current, end,
op);
}
/// A range filtered and transformed by the optional transform.
template <typename Range, typename OptionalTransform,
typename Iterator = decltype(std::declval<Range>().begin())>
class OptionalTransformRange {
Iterator First, Last;
OptionalTransform Op;
public:
using iterator = OptionalTransformIterator<Iterator, OptionalTransform>;
OptionalTransformRange(Range range, OptionalTransform op)
: First(range.begin()), Last(range.end()), Op(op)
{
// Prime the sequence.
while (First != Last && !Op(*First))
++First;
}
iterator begin() const {
return iterator(First, Last, Op, iterator::Primed);
}
iterator end() const {
return iterator(Last, Last, Op, iterator::Primed);
}
bool empty() const { return First == Last; }
typename std::iterator_traits<iterator>::value_type front() const {
assert(!empty() && "Front of empty range");
return *begin();
}
};
/// Create a new filter range.
template<typename Range, typename OptionalTransform>
inline OptionalTransformRange<Range, OptionalTransform>
makeOptionalTransformRange(Range range, OptionalTransform op) {
return OptionalTransformRange<Range, OptionalTransform>(range, op);
}
/// Function object that attempts a downcast to a subclass, wrapping
/// the result in an optional to indicate success or failure.
template<typename Subclass>
struct DowncastAsOptional {
template <typename Superclass>
auto operator()(Superclass &value) const
-> llvm::Optional<decltype(llvm::cast<Subclass>(value))> {
if (auto result = llvm::dyn_cast<Subclass>(value))
return result;
return None;
}
template <typename Superclass>
auto operator()(const Superclass &value) const
-> llvm::Optional<decltype(llvm::cast<Subclass>(value))> {
if (auto result = llvm::dyn_cast<Subclass>(value))
return result;
return None;
}
};
template<typename Subclass, typename Iterator>
using DowncastFilterIterator
= OptionalTransformIterator<Iterator, DowncastAsOptional<Subclass>>;
template<typename Subclass, typename Iterator>
inline DowncastFilterIterator<Subclass, Iterator>
makeDowncastFilterIterator(Iterator current, Iterator end) {
DowncastAsOptional<Subclass> op;
return DowncastFilterIterator<Subclass, Iterator>(current, end, op);
}
template<typename Subclass, typename Range>
class DowncastFilterRange
: public OptionalTransformRange<Range, DowncastAsOptional<Subclass>> {
using Inherited = OptionalTransformRange<Range, DowncastAsOptional<Subclass>>;
public:
DowncastFilterRange(Range range)
: Inherited(range, DowncastAsOptional<Subclass>()) { }
};
template<typename Subclass, typename Range>
DowncastFilterRange<Subclass, Range>
makeDowncastFilterRange(Range range) {
return DowncastFilterRange<Subclass, Range>(range);
}
/// Sorts and then uniques a container with random access iterators and an erase
/// method that removes a range specified by random access iterators.
template <typename Container>
void sortUnique(
Container &C,
typename std::enable_if<
std::is_same<typename std::iterator_traits<
typename Container::iterator>::iterator_category,
std::random_access_iterator_tag>::value,
void>::type * = nullptr) {
std::sort(C.begin(), C.end());
C.erase(std::unique(C.begin(), C.end()), C.end());
}
/// Sorts and then uniques a container with random access iterators and an erase
/// method that removes a range specified by random access iterators.
template <typename Container, typename Comparator>
void sortUnique(
Container &C,
Comparator Cmp,
typename std::enable_if<
std::is_same<typename std::iterator_traits<
typename Container::iterator>::iterator_category,
std::random_access_iterator_tag>::value,
void>::type * = nullptr) {
std::sort(C.begin(), C.end(), Cmp);
C.erase(std::unique(C.begin(), C.end()), C.end());
}
/// Returns true if [II, IE) is a sorted and uniqued array. Returns false
/// otherwise.
template <typename IterTy>
inline bool is_sorted_and_uniqued(IterTy II, IterTy IE) {
using RefTy = typename std::iterator_traits<IterTy>::reference;
// The empty list is always sorted and uniqued.
if (II == IE)
return true;
// The list of one element is always sorted and uniqued.
auto LastI = II;
++II;
if (II == IE)
return true;
// Otherwise, until we reach the end of the list...
while (II != IE) {
// If LastI is greater than II then we know that our array is not sorted. If
// LastI equals II, then we know that our array is not unique. If both of
// those are conditions are false, then visit the next iterator element.
if (std::greater_equal<RefTy>()(*LastI, *II)) {
// Return false otherwise.
return false;
}
LastI = II;
++II;
}
// Success!
return true;
}
template <typename Container>
inline bool is_sorted_and_uniqued(const Container &C) {
return is_sorted_and_uniqued(C.begin(), C.end());
}
template <typename Container, typename T, typename BinaryOperation>
inline T accumulate(const Container &C, T init, BinaryOperation op) {
return std::accumulate(C.begin(), C.end(), init, op);
}
template <typename Container, typename T>
inline bool binary_search(const Container &C, const T &value) {
return std::binary_search(C.begin(), C.end(), value);
}
template <typename Container, typename T, typename BinaryOperation>
inline bool binary_search(const Container &C, const T &value, BinaryOperation op) {
return std::binary_search(C.begin(), C.end(), value, op);
}
/// Returns true if the range defined by \p mainBegin ..< \p mainEnd starts with
/// the same elements as the range defined by \p prefixBegin ..< \p prefixEnd.
///
/// This includes cases where the prefix range is empty, as well as when the two
/// ranges are the same length and contain the same elements.
template <typename MainInputIterator, typename PrefixInputIterator>
inline bool hasPrefix(MainInputIterator mainBegin,
const MainInputIterator mainEnd,
PrefixInputIterator prefixBegin,
const PrefixInputIterator prefixEnd) {
while (prefixBegin != prefixEnd) {
// If "main" is shorter than "prefix", it does not start with "prefix".
if (mainBegin == mainEnd)
return false;
// If there's a mismatch, "main" does not start with "prefix".
if (*mainBegin != *prefixBegin)
return false;
++prefixBegin;
++mainBegin;
}
// If we checked every element of "prefix", "main" does start with "prefix".
return true;
}
/// Provides default implementations of !=, <=, >, and >= based on == and <.
template <typename T>
class RelationalOperationsBase {
public:
friend bool operator>(const T &left, const T &right) {
return right < left;
}
friend bool operator>=(const T &left, const T &right) {
return !(left < right);
}
friend bool operator<=(const T &left, const T &right) {
return !(right < left);
}
friend bool operator!=(const T &left, const T &right) {
return !(left == right);
}
};
/// Cast a pointer to \c U to a pointer to a supertype \c T.
/// Example: Wobulator *w = up_cast<Wobulator>(coloredWobulator)
/// Useful with ?: where each arm is a different subtype.
/// If \c U is not a subtype of \c T, the compiler will complain.
template <typename T, typename U>
T *up_cast(U *ptr) { return ptr; }
/// Removes all runs of values that match \p pred from the range of \p begin
/// to \p end.
///
/// This is similar to std::unique, but std::unique leaves the first value in
/// place in a run of matching values, whereas this code removes all of them.
///
/// \returns The new end iterator for the container. You should erase elements
/// between this value and the existing end of the container.
template <typename Iterator, typename BinaryPredicate>
Iterator removeAdjacentIf(const Iterator first, const Iterator last,
BinaryPredicate pred) {
using element_reference_t =
typename std::iterator_traits<Iterator>::reference;
auto nextOverlap = std::adjacent_find(first, last, pred);
auto insertionPoint = nextOverlap;
while (nextOverlap != last) {
// We want to erase *all* the matching elements. There could be three or
// more of them. Search for the end of the run.
auto lastOverlapInRun =
std::adjacent_find(std::next(nextOverlap), last,
[&pred](element_reference_t left,
element_reference_t right) -> bool {
return !pred(left, right);
});
// If we get the end iterator back, that means all remaining elements match.
// If we don't, that means (lastOverlapInRun+1) is part of a different run.
if (lastOverlapInRun != last)
++lastOverlapInRun;
nextOverlap = std::adjacent_find(lastOverlapInRun, last, pred);
insertionPoint = std::move(lastOverlapInRun, nextOverlap, insertionPoint);
}
return insertionPoint;
}
namespace detail {
template <bool...> struct bool_pack;
} // namespace detail
template <bool... b>
using all_true =
std::is_same<detail::bool_pack<b..., true>, detail::bool_pack<true, b...>>;
/// traits class for checking whether Ts consists only of compound types.
template <class... Ts>
using are_all_compound = all_true<std::is_compound<Ts>::value...>;
/// Erase all elements in \p c that match the given predicate \p pred.
// FIXME: Remove this when C++20 is the new baseline.
template <class Key, class Hash, class KeyEqual, class Alloc, class Pred>
typename std::unordered_set<Key, Hash, KeyEqual, Alloc>::size_type
erase_if(std::unordered_set<Key, Hash, KeyEqual, Alloc> &c, Pred pred) {
auto startingSize = c.size();
for (auto i = c.begin(), last = c.end(); i != last;) {
if (pred(*i)) {
i = c.erase(i);
} else {
++i;
}
}
return startingSize - c.size();
}
} // end namespace swift
#endif // SWIFT_BASIC_INTERLEAVE_H