mfbt/Algorithm.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* A polyfill for `<algorithm>`. */
   8
   9 #ifndef mozilla_Algorithm_h
  10 #define mozilla_Algorithm_h
  11
  12 #include "mozilla/Result.h"
  13
  14 #include <iterator>
  15 #include <type_traits>
  16
  17 namespace mozilla {
  18
  19 // Returns true if all elements in the range [aFirst, aLast)
  20 // satisfy the predicate aPred.
  21 template <class Iter, class Pred>
  22 constexpr bool AllOf(Iter aFirst, Iter aLast, Pred aPred) {
  23   for (; aFirst != aLast; ++aFirst) {
  24     if (!aPred(*aFirst)) {
  25       return false;
  26     }
  27   }
  28   return true;
  29 }
  30
  31 // Like C++20's `std::any_of`.
  32 template <typename Iter, typename Pred>
  33 constexpr bool AnyOf(Iter aFirst, Iter aLast, Pred aPred) {
  34   for (; aFirst != aLast; ++aFirst) {
  35     if (aPred(*aFirst)) {
  36       return true;
  37     }
  38   }
  39
  40   return false;
  41 }
  42
  43 namespace detail {
  44 template <typename Transform, typename SrcIter>
  45 using ArrayElementTransformType = typename std::invoke_result_t<
  46     Transform, typename std::iterator_traits<SrcIter>::reference>;
  47
  48 template <typename Transform, typename SrcIter>
  49 struct TransformTraits {
  50   using result_type = ArrayElementTransformType<Transform, SrcIter>;
  51
  52   using result_ok_type = typename result_type::ok_type;
  53   using result_err_type = typename result_type::err_type;
  54 };
  55 }  // namespace detail
  56
  57 // An algorithm similar to TransformAbortOnErr combined with a condition that
  58 // allows to skip elements. At most std::distance(aIter, aEnd) elements will be
  59 // inserted into aDst.
  60 //
  61 // Type requirements, in addition to those specified in TransformAbortOnErr:
  62 // - Cond must be compatible with signature
  63 //   bool (const SrcIter::value_type&)
  64 template <typename SrcIter, typename DstIter, typename Cond, typename Transform>
  65 Result<Ok,
  66        typename detail::TransformTraits<Transform, SrcIter>::result_err_type>
  67 TransformIfAbortOnErr(SrcIter aIter, SrcIter aEnd, DstIter aDst, Cond aCond,
  68                       Transform aTransform) {
  69   for (; aIter != aEnd; ++aIter) {
  70     if (!aCond(static_cast<std::add_const_t<
  71                    typename std::iterator_traits<SrcIter>::value_type>&>(
  72             *aIter))) {
  73       continue;
  74     }
  75
  76     auto res = aTransform(*aIter);
  77     if (res.isErr()) {
  78       return Err(res.unwrapErr());
  79     }
  80
  81     *aDst++ = res.unwrap();
  82   }
  83   return Ok{};
  84 }
  85
  86 template <typename SrcRange, typename DstIter, typename Cond,
  87           typename Transform>
  88 auto TransformIfAbortOnErr(SrcRange& aRange, DstIter aDst, Cond aCond,
  89                            Transform aTransform) {
  90   using std::begin;
  91   using std::end;
  92   return TransformIfAbortOnErr(begin(aRange), end(aRange), aDst, aCond,
  93                                aTransform);
  94 }
  95
  96 // An algorithm similar to std::transform, adapted to error handling based on
  97 // mozilla::Result<V, E>. It iterates through the input range [aIter, aEnd) and
  98 // inserts the result of applying aTransform to each element into aDst, if
  99 // aTransform returns a success result. On the first error result, iterating is
 100 // aborted, and the error result is returned as an overall result. If all
 101 // transformations return a success result, Ok is returned as an overall result.
 102 //
 103 // Type requirements:
 104 // - SrcIter must be an InputIterator.
 105 // - DstIter must be an OutputIterator.
 106 // - Transform must be compatible with signature
 107 //   Result<DstIter::value_type, E> (SrcIter::reference)
 108 template <typename SrcIter, typename DstIter, typename Transform>
 109 Result<Ok,
 110        typename detail::TransformTraits<Transform, SrcIter>::result_err_type>
 111 TransformAbortOnErr(SrcIter aIter, SrcIter aEnd, DstIter aDst,
 112                     Transform aTransform) {
 113   return TransformIfAbortOnErr(
 114       aIter, aEnd, aDst, [](const auto&) { return true; }, aTransform);
 115 }
 116
 117 template <typename SrcRange, typename DstIter, typename Transform>
 118 auto TransformAbortOnErr(SrcRange& aRange, DstIter aDst, Transform aTransform) {
 119   using std::begin;
 120   using std::end;
 121   return TransformIfAbortOnErr(
 122       begin(aRange), end(aRange), aDst, [](const auto&) { return true; },
 123       aTransform);
 124 }
 125
 126 }  // namespace mozilla
 127
 128 #endif  // mozilla_Algorithm_h