jpayne@69: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
jpayne@69: // Licensed under the MIT License:
jpayne@69: //
jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69: // of this software and associated documentation files (the "Software"), to deal
jpayne@69: // in the Software without restriction, including without limitation the rights
jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69: // copies of the Software, and to permit persons to whom the Software is
jpayne@69: // furnished to do so, subject to the following conditions:
jpayne@69: //
jpayne@69: // The above copyright notice and this permission notice shall be included in
jpayne@69: // all copies or substantial portions of the Software.
jpayne@69: //
jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69: // THE SOFTWARE.
jpayne@69: 
jpayne@69: // Parser combinator framework!
jpayne@69: //
jpayne@69: // This file declares several functions which construct parsers, usually taking other parsers as
jpayne@69: // input, thus making them parser combinators.
jpayne@69: //
jpayne@69: // A valid parser is any functor which takes a reference to an input cursor (defined below) as its
jpayne@69: // input and returns a Maybe.  The parser returns null on parse failure, or returns the parsed
jpayne@69: // result on success.
jpayne@69: //
jpayne@69: // An "input cursor" is any type which implements the same interface as IteratorInput, below.  Such
jpayne@69: // a type acts as a pointer to the current input location.  When a parser returns successfully, it
jpayne@69: // will have updated the input cursor to point to the position just past the end of what was parsed.
jpayne@69: // On failure, the cursor position is unspecified.
jpayne@69: 
jpayne@69: #pragma once
jpayne@69: 
jpayne@69: #include "../common.h"
jpayne@69: #include "../memory.h"
jpayne@69: #include "../array.h"
jpayne@69: #include "../tuple.h"
jpayne@69: #include "../vector.h"
jpayne@69: 
jpayne@69: #if _MSC_VER && _MSC_VER < 1920 && !__clang__
jpayne@69: #define KJ_MSVC_BROKEN_DECLTYPE 1
jpayne@69: #endif
jpayne@69: 
jpayne@69: #if KJ_MSVC_BROKEN_DECLTYPE
jpayne@69: #include <type_traits>  // result_of_t
jpayne@69: #endif
jpayne@69: 
jpayne@69: KJ_BEGIN_HEADER
jpayne@69: 
jpayne@69: namespace kj {
jpayne@69: namespace parse {
jpayne@69: 
jpayne@69: template <typename Element, typename Iterator>
jpayne@69: class IteratorInput {
jpayne@69:   // A parser input implementation based on an iterator range.
jpayne@69: 
jpayne@69: public:
jpayne@69:   IteratorInput(Iterator begin, Iterator end)
jpayne@69:       : parent(nullptr), pos(begin), end(end), best(begin) {}
jpayne@69:   explicit IteratorInput(IteratorInput& parent)
jpayne@69:       : parent(&parent), pos(parent.pos), end(parent.end), best(parent.pos) {}
jpayne@69:   ~IteratorInput() {
jpayne@69:     if (parent != nullptr) {
jpayne@69:       parent->best = kj::max(kj::max(pos, best), parent->best);
jpayne@69:     }
jpayne@69:   }
jpayne@69:   KJ_DISALLOW_COPY_AND_MOVE(IteratorInput);
jpayne@69: 
jpayne@69:   void advanceParent() {
jpayne@69:     parent->pos = pos;
jpayne@69:   }
jpayne@69:   void forgetParent() {
jpayne@69:     parent = nullptr;
jpayne@69:   }
jpayne@69: 
jpayne@69:   bool atEnd() { return pos == end; }
jpayne@69:   auto current() -> decltype(*instance<Iterator>()) {
jpayne@69:     KJ_IREQUIRE(!atEnd());
jpayne@69:     return *pos;
jpayne@69:   }
jpayne@69:   auto consume() -> decltype(*instance<Iterator>()) {
jpayne@69:     KJ_IREQUIRE(!atEnd());
jpayne@69:     return *pos++;
jpayne@69:   }
jpayne@69:   void next() {
jpayne@69:     KJ_IREQUIRE(!atEnd());
jpayne@69:     ++pos;
jpayne@69:   }
jpayne@69: 
jpayne@69:   Iterator getBest() { return kj::max(pos, best); }
jpayne@69: 
jpayne@69:   Iterator getPosition() { return pos; }
jpayne@69: 
jpayne@69: private:
jpayne@69:   IteratorInput* parent;
jpayne@69:   Iterator pos;
jpayne@69:   Iterator end;
jpayne@69:   Iterator best;  // furthest we got with any sub-input
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T> struct OutputType_;
jpayne@69: template <typename T> struct OutputType_<Maybe<T>> { typedef T Type; };
jpayne@69: template <typename Parser, typename Input>
jpayne@69: using OutputType = typename OutputType_<
jpayne@69: #if KJ_MSVC_BROKEN_DECLTYPE
jpayne@69:     std::result_of_t<Parser(Input)>
jpayne@69:     // The instance<T&>() based version below results in many compiler errors on MSVC2017.
jpayne@69: #else
jpayne@69:     decltype(instance<Parser&>()(instance<Input&>()))
jpayne@69: #endif
jpayne@69:     >::Type;
jpayne@69: // Synonym for the output type of a parser, given the parser type and the input type.
jpayne@69: 
jpayne@69: // =======================================================================================
jpayne@69: 
jpayne@69: template <typename Input, typename Output>
jpayne@69: class ParserRef {
jpayne@69:   // Acts as a reference to some other parser, with simplified type.  The referenced parser
jpayne@69:   // is polymorphic by virtual call rather than templates.  For grammars of non-trivial size,
jpayne@69:   // it is important to inject refs into the grammar here and there to prevent the parser types
jpayne@69:   // from becoming ridiculous.  Using too many of them can hurt performance, though.
jpayne@69: 
jpayne@69: public:
jpayne@69:   ParserRef(): parser(nullptr), wrapper(nullptr) {}
jpayne@69:   ParserRef(const ParserRef&) = default;
jpayne@69:   ParserRef(ParserRef&&) = default;
jpayne@69:   ParserRef& operator=(const ParserRef& other) = default;
jpayne@69:   ParserRef& operator=(ParserRef&& other) = default;
jpayne@69: 
jpayne@69:   template <typename Other>
jpayne@69:   constexpr ParserRef(Other&& other)
jpayne@69:       : parser(&other), wrapper(&WrapperImplInstance<Decay<Other>>::instance) {
jpayne@69:     static_assert(kj::isReference<Other>(), "ParserRef should not be assigned to a temporary.");
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename Other>
jpayne@69:   inline ParserRef& operator=(Other&& other) {
jpayne@69:     static_assert(kj::isReference<Other>(), "ParserRef should not be assigned to a temporary.");
jpayne@69:     parser = &other;
jpayne@69:     wrapper = &WrapperImplInstance<Decay<Other>>::instance;
jpayne@69:     return *this;
jpayne@69:   }
jpayne@69: 
jpayne@69:   KJ_ALWAYS_INLINE(Maybe<Output> operator()(Input& input) const) {
jpayne@69:     // Always inline in the hopes that this allows branch prediction to kick in so the virtual call
jpayne@69:     // doesn't hurt so much.
jpayne@69:     return wrapper->parse(parser, input);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   struct Wrapper {
jpayne@69:     virtual Maybe<Output> parse(const void* parser, Input& input) const = 0;
jpayne@69:   };
jpayne@69:   template <typename ParserImpl>
jpayne@69:   struct WrapperImpl: public Wrapper {
jpayne@69:     Maybe<Output> parse(const void* parser, Input& input) const override {
jpayne@69:       return (*reinterpret_cast<const ParserImpl*>(parser))(input);
jpayne@69:     }
jpayne@69:   };
jpayne@69:   template <typename ParserImpl>
jpayne@69:   struct WrapperImplInstance {
jpayne@69: #if _MSC_VER && !__clang__
jpayne@69:     // TODO(msvc): MSVC currently fails to initialize vtable pointers for constexpr values so
jpayne@69:     //   we have to make this just const instead.
jpayne@69:     static const WrapperImpl<ParserImpl> instance;
jpayne@69: #else
jpayne@69:     static constexpr WrapperImpl<ParserImpl> instance = WrapperImpl<ParserImpl>();
jpayne@69: #endif
jpayne@69:   };
jpayne@69: 
jpayne@69:   const void* parser;
jpayne@69:   const Wrapper* wrapper;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename Input, typename Output>
jpayne@69: template <typename ParserImpl>
jpayne@69: #if _MSC_VER && !__clang__
jpayne@69: const typename ParserRef<Input, Output>::template WrapperImpl<ParserImpl>
jpayne@69: ParserRef<Input, Output>::WrapperImplInstance<ParserImpl>::instance = WrapperImpl<ParserImpl>();
jpayne@69: #else
jpayne@69: constexpr typename ParserRef<Input, Output>::template WrapperImpl<ParserImpl>
jpayne@69: ParserRef<Input, Output>::WrapperImplInstance<ParserImpl>::instance;
jpayne@69: #endif
jpayne@69: 
jpayne@69: template <typename Input, typename ParserImpl>
jpayne@69: constexpr ParserRef<Input, OutputType<ParserImpl, Input>> ref(ParserImpl& impl) {
jpayne@69:   // Constructs a ParserRef.  You must specify the input type explicitly, e.g.
jpayne@69:   // `ref<MyInput>(myParser)`.
jpayne@69: 
jpayne@69:   return ParserRef<Input, OutputType<ParserImpl, Input>>(impl);
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // any
jpayne@69: // Output = one token
jpayne@69: 
jpayne@69: class Any_ {
jpayne@69: public:
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Decay<decltype(instance<Input>().consume())>> operator()(Input& input) const {
jpayne@69:     if (input.atEnd()) {
jpayne@69:       return nullptr;
jpayne@69:     } else {
jpayne@69:       return input.consume();
jpayne@69:     }
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: constexpr Any_ any = Any_();
jpayne@69: // A parser which matches any token and simply returns it.
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // exactly()
jpayne@69: // Output = Tuple<>
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class Exactly_ {
jpayne@69: public:
jpayne@69:   explicit constexpr Exactly_(T&& expected): expected(expected) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Tuple<>> operator()(Input& input) const {
jpayne@69:     if (input.atEnd() || input.current() != expected) {
jpayne@69:       return nullptr;
jpayne@69:     } else {
jpayne@69:       input.next();
jpayne@69:       return Tuple<>();
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   T expected;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: constexpr Exactly_<T> exactly(T&& expected) {
jpayne@69:   // Constructs a parser which succeeds when the input is exactly the token specified.  The
jpayne@69:   // result is always the empty tuple.
jpayne@69: 
jpayne@69:   return Exactly_<T>(kj::fwd<T>(expected));
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // exactlyConst()
jpayne@69: // Output = Tuple<>
jpayne@69: 
jpayne@69: template <typename T, T expected>
jpayne@69: class ExactlyConst_ {
jpayne@69: public:
jpayne@69:   explicit constexpr ExactlyConst_() {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Tuple<>> operator()(Input& input) const {
jpayne@69:     if (input.atEnd() || input.current() != expected) {
jpayne@69:       return nullptr;
jpayne@69:     } else {
jpayne@69:       input.next();
jpayne@69:       return Tuple<>();
jpayne@69:     }
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T, T expected>
jpayne@69: constexpr ExactlyConst_<T, expected> exactlyConst() {
jpayne@69:   // Constructs a parser which succeeds when the input is exactly the token specified.  The
jpayne@69:   // result is always the empty tuple.  This parser is templated on the token value which may cause
jpayne@69:   // it to perform better -- or worse.  Be sure to measure.
jpayne@69: 
jpayne@69:   return ExactlyConst_<T, expected>();
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // constResult()
jpayne@69: 
jpayne@69: template <typename SubParser, typename Result>
jpayne@69: class ConstResult_ {
jpayne@69: public:
jpayne@69:   explicit constexpr ConstResult_(SubParser&& subParser, Result&& result)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)), result(kj::fwd<Result>(result)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Result> operator()(Input& input) const {
jpayne@69:     if (subParser(input) == nullptr) {
jpayne@69:       return nullptr;
jpayne@69:     } else {
jpayne@69:       return result;
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69:   Result result;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, typename Result>
jpayne@69: constexpr ConstResult_<SubParser, Result> constResult(SubParser&& subParser, Result&& result) {
jpayne@69:   // Constructs a parser which returns exactly `result` if `subParser` is successful.
jpayne@69:   return ConstResult_<SubParser, Result>(kj::fwd<SubParser>(subParser), kj::fwd<Result>(result));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr ConstResult_<SubParser, Tuple<>> discard(SubParser&& subParser) {
jpayne@69:   // Constructs a parser which wraps `subParser` but discards the result.
jpayne@69:   return constResult(kj::fwd<SubParser>(subParser), Tuple<>());
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // sequence()
jpayne@69: // Output = Flattened Tuple of outputs of sub-parsers.
jpayne@69: 
jpayne@69: template <typename... SubParsers> class Sequence_;
jpayne@69: 
jpayne@69: template <typename FirstSubParser, typename... SubParsers>
jpayne@69: class Sequence_<FirstSubParser, SubParsers...> {
jpayne@69: public:
jpayne@69:   template <typename T, typename... U>
jpayne@69:   explicit constexpr Sequence_(T&& firstSubParser, U&&... rest)
jpayne@69:       : first(kj::fwd<T>(firstSubParser)), rest(kj::fwd<U>(rest)...) {}
jpayne@69: 
jpayne@69:   // TODO(msvc): The trailing return types on `operator()` and `parseNext()` expose at least two
jpayne@69:   //   bugs in MSVC:
jpayne@69:   //
jpayne@69:   //     1. An ICE.
jpayne@69:   //     2. 'error C2672: 'operator __surrogate_func': no matching overloaded function found)',
jpayne@69:   //        which crops up in numerous places when trying to build the capnp command line tools.
jpayne@69:   //
jpayne@69:   //   The only workaround I found for both bugs is to omit the trailing return types and instead
jpayne@69:   //   rely on C++14's return type deduction.
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   auto operator()(Input& input) const
jpayne@69: #if !_MSC_VER || __clang__
jpayne@69:       -> Maybe<decltype(tuple(
jpayne@69:           instance<OutputType<FirstSubParser, Input>>(),
jpayne@69:           instance<OutputType<SubParsers, Input>>()...))>
jpayne@69: #endif
jpayne@69:   {
jpayne@69:     return parseNext(input);
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename Input, typename... InitialParams>
jpayne@69:   auto parseNext(Input& input, InitialParams&&... initialParams) const
jpayne@69: #if !_MSC_VER || __clang__
jpayne@69:       -> Maybe<decltype(tuple(
jpayne@69:           kj::fwd<InitialParams>(initialParams)...,
jpayne@69:           instance<OutputType<FirstSubParser, Input>>(),
jpayne@69:           instance<OutputType<SubParsers, Input>>()...))>
jpayne@69: #endif
jpayne@69:   {
jpayne@69:     KJ_IF_MAYBE(firstResult, first(input)) {
jpayne@69:       return rest.parseNext(input, kj::fwd<InitialParams>(initialParams)...,
jpayne@69:                             kj::mv(*firstResult));
jpayne@69:     } else {
jpayne@69:       // TODO(msvc): MSVC depends on return type deduction to compile this function, so we need to
jpayne@69:       //   help it deduce the right type on this code path.
jpayne@69:       return Maybe<decltype(tuple(
jpayne@69:           kj::fwd<InitialParams>(initialParams)...,
jpayne@69:           instance<OutputType<FirstSubParser, Input>>(),
jpayne@69:           instance<OutputType<SubParsers, Input>>()...))>{nullptr};
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   FirstSubParser first;
jpayne@69:   Sequence_<SubParsers...> rest;
jpayne@69: };
jpayne@69: 
jpayne@69: template <>
jpayne@69: class Sequence_<> {
jpayne@69: public:
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Tuple<>> operator()(Input& input) const {
jpayne@69:     return parseNext(input);
jpayne@69:   }
jpayne@69: 
jpayne@69:   template <typename Input, typename... Params>
jpayne@69:   auto parseNext(Input& input, Params&&... params) const ->
jpayne@69:       Maybe<decltype(tuple(kj::fwd<Params>(params)...))> {
jpayne@69:     return tuple(kj::fwd<Params>(params)...);
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename... SubParsers>
jpayne@69: constexpr Sequence_<SubParsers...> sequence(SubParsers&&... subParsers) {
jpayne@69:   // Constructs a parser that executes each of the parameter parsers in sequence and returns a
jpayne@69:   // tuple of their results.
jpayne@69: 
jpayne@69:   return Sequence_<SubParsers...>(kj::fwd<SubParsers>(subParsers)...);
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // many()
jpayne@69: // Output = Array of output of sub-parser, or just a uint count if the sub-parser returns Tuple<>.
jpayne@69: 
jpayne@69: template <typename SubParser, bool atLeastOne>
jpayne@69: class Many_ {
jpayne@69:   template <typename Input, typename Output = OutputType<SubParser, Input>>
jpayne@69:   struct Impl;
jpayne@69: public:
jpayne@69:   explicit constexpr Many_(SubParser&& subParser)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   auto operator()(Input& input) const
jpayne@69:       -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input));
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, bool atLeastOne>
jpayne@69: template <typename Input, typename Output>
jpayne@69: struct Many_<SubParser, atLeastOne>::Impl {
jpayne@69:   static Maybe<Array<Output>> apply(const SubParser& subParser, Input& input) {
jpayne@69:     typedef Vector<OutputType<SubParser, Input>> Results;
jpayne@69:     Results results;
jpayne@69: 
jpayne@69:     while (!input.atEnd()) {
jpayne@69:       Input subInput(input);
jpayne@69: 
jpayne@69:       KJ_IF_MAYBE(subResult, subParser(subInput)) {
jpayne@69:         subInput.advanceParent();
jpayne@69:         results.add(kj::mv(*subResult));
jpayne@69:       } else {
jpayne@69:         break;
jpayne@69:       }
jpayne@69:     }
jpayne@69: 
jpayne@69:     if (atLeastOne && results.empty()) {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69: 
jpayne@69:     return results.releaseAsArray();
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, bool atLeastOne>
jpayne@69: template <typename Input>
jpayne@69: struct Many_<SubParser, atLeastOne>::Impl<Input, Tuple<>> {
jpayne@69:   // If the sub-parser output is Tuple<>, just return a count.
jpayne@69: 
jpayne@69:   static Maybe<uint> apply(const SubParser& subParser, Input& input) {
jpayne@69:     uint count = 0;
jpayne@69: 
jpayne@69:     while (!input.atEnd()) {
jpayne@69:       Input subInput(input);
jpayne@69: 
jpayne@69:       KJ_IF_MAYBE(subResult, subParser(subInput)) {
jpayne@69:         subInput.advanceParent();
jpayne@69:         ++count;
jpayne@69:       } else {
jpayne@69:         break;
jpayne@69:       }
jpayne@69:     }
jpayne@69: 
jpayne@69:     if (atLeastOne && count == 0) {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69: 
jpayne@69:     return count;
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, bool atLeastOne>
jpayne@69: template <typename Input>
jpayne@69: auto Many_<SubParser, atLeastOne>::operator()(Input& input) const
jpayne@69:     -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input)) {
jpayne@69:   return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, input);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr Many_<SubParser, false> many(SubParser&& subParser) {
jpayne@69:   // Constructs a parser that repeatedly executes the given parser until it fails, returning an
jpayne@69:   // Array of the results (or a uint count if `subParser` returns an empty tuple).
jpayne@69:   return Many_<SubParser, false>(kj::fwd<SubParser>(subParser));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr Many_<SubParser, true> oneOrMore(SubParser&& subParser) {
jpayne@69:   // Like `many()` but the parser must parse at least one item to be successful.
jpayne@69:   return Many_<SubParser, true>(kj::fwd<SubParser>(subParser));
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // times()
jpayne@69: // Output = Array of output of sub-parser, or Tuple<> if sub-parser returns Tuple<>.
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: class Times_ {
jpayne@69:   template <typename Input, typename Output = OutputType<SubParser, Input>>
jpayne@69:   struct Impl;
jpayne@69: public:
jpayne@69:   explicit constexpr Times_(SubParser&& subParser, uint count)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)), count(count) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   auto operator()(Input& input) const
jpayne@69:       -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input));
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69:   uint count;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: template <typename Input, typename Output>
jpayne@69: struct Times_<SubParser>::Impl {
jpayne@69:   static Maybe<Array<Output>> apply(const SubParser& subParser, uint count, Input& input) {
jpayne@69:     auto results = heapArrayBuilder<OutputType<SubParser, Input>>(count);
jpayne@69: 
jpayne@69:     while (results.size() < count) {
jpayne@69:       if (input.atEnd()) {
jpayne@69:         return nullptr;
jpayne@69:       } else KJ_IF_MAYBE(subResult, subParser(input)) {
jpayne@69:         results.add(kj::mv(*subResult));
jpayne@69:       } else {
jpayne@69:         return nullptr;
jpayne@69:       }
jpayne@69:     }
jpayne@69: 
jpayne@69:     return results.finish();
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: template <typename Input>
jpayne@69: struct Times_<SubParser>::Impl<Input, Tuple<>> {
jpayne@69:   // If the sub-parser output is Tuple<>, just return a count.
jpayne@69: 
jpayne@69:   static Maybe<Tuple<>> apply(const SubParser& subParser, uint count, Input& input) {
jpayne@69:     uint actualCount = 0;
jpayne@69: 
jpayne@69:     while (actualCount < count) {
jpayne@69:       if (input.atEnd()) {
jpayne@69:         return nullptr;
jpayne@69:       } else KJ_IF_MAYBE(subResult, subParser(input)) {
jpayne@69:         ++actualCount;
jpayne@69:       } else {
jpayne@69:         return nullptr;
jpayne@69:       }
jpayne@69:     }
jpayne@69: 
jpayne@69:     return tuple();
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: template <typename Input>
jpayne@69: auto Times_<SubParser>::operator()(Input& input) const
jpayne@69:     -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input)) {
jpayne@69:   return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, count, input);
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr Times_<SubParser> times(SubParser&& subParser, uint count) {
jpayne@69:   // Constructs a parser that repeats the subParser exactly `count` times.
jpayne@69:   return Times_<SubParser>(kj::fwd<SubParser>(subParser), count);
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // optional()
jpayne@69: // Output = Maybe<output of sub-parser>
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: class Optional_ {
jpayne@69: public:
jpayne@69:   explicit constexpr Optional_(SubParser&& subParser)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Maybe<OutputType<SubParser, Input>>> operator()(Input& input) const {
jpayne@69:     typedef Maybe<OutputType<SubParser, Input>> Result;
jpayne@69: 
jpayne@69:     Input subInput(input);
jpayne@69:     KJ_IF_MAYBE(subResult, subParser(subInput)) {
jpayne@69:       subInput.advanceParent();
jpayne@69:       return Result(kj::mv(*subResult));
jpayne@69:     } else {
jpayne@69:       return Result(nullptr);
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr Optional_<SubParser> optional(SubParser&& subParser) {
jpayne@69:   // Constructs a parser that accepts zero or one of the given sub-parser, returning a Maybe
jpayne@69:   // of the sub-parser's result.
jpayne@69:   return Optional_<SubParser>(kj::fwd<SubParser>(subParser));
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // oneOf()
jpayne@69: // All SubParsers must have same output type, which becomes the output type of the
jpayne@69: // OneOfParser.
jpayne@69: 
jpayne@69: template <typename... SubParsers>
jpayne@69: class OneOf_;
jpayne@69: 
jpayne@69: template <typename FirstSubParser, typename... SubParsers>
jpayne@69: class OneOf_<FirstSubParser, SubParsers...> {
jpayne@69: public:
jpayne@69:   explicit constexpr OneOf_(FirstSubParser&& firstSubParser, SubParsers&&... rest)
jpayne@69:       : first(kj::fwd<FirstSubParser>(firstSubParser)), rest(kj::fwd<SubParsers>(rest)...) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<OutputType<FirstSubParser, Input>> operator()(Input& input) const {
jpayne@69:     {
jpayne@69:       Input subInput(input);
jpayne@69:       Maybe<OutputType<FirstSubParser, Input>> firstResult = first(subInput);
jpayne@69: 
jpayne@69:       if (firstResult != nullptr) {
jpayne@69:         subInput.advanceParent();
jpayne@69:         return kj::mv(firstResult);
jpayne@69:       }
jpayne@69:     }
jpayne@69: 
jpayne@69:     // Hoping for some tail recursion here...
jpayne@69:     return rest(input);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   FirstSubParser first;
jpayne@69:   OneOf_<SubParsers...> rest;
jpayne@69: };
jpayne@69: 
jpayne@69: template <>
jpayne@69: class OneOf_<> {
jpayne@69: public:
jpayne@69:   template <typename Input>
jpayne@69:   decltype(nullptr) operator()(Input& input) const {
jpayne@69:     return nullptr;
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename... SubParsers>
jpayne@69: constexpr OneOf_<SubParsers...> oneOf(SubParsers&&... parsers) {
jpayne@69:   // Constructs a parser that accepts one of a set of options.  The parser behaves as the first
jpayne@69:   // sub-parser in the list which returns successfully.  All of the sub-parsers must return the
jpayne@69:   // same type.
jpayne@69:   return OneOf_<SubParsers...>(kj::fwd<SubParsers>(parsers)...);
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // transform()
jpayne@69: // Output = Result of applying transform functor to input value.  If input is a tuple, it is
jpayne@69: // unpacked to form the transformation parameters.
jpayne@69: 
jpayne@69: template <typename Position>
jpayne@69: struct Span {
jpayne@69: public:
jpayne@69:   inline const Position& begin() const { return begin_; }
jpayne@69:   inline const Position& end() const { return end_; }
jpayne@69: 
jpayne@69:   Span() = default;
jpayne@69:   inline constexpr Span(Position&& begin, Position&& end): begin_(mv(begin)), end_(mv(end)) {}
jpayne@69: 
jpayne@69: private:
jpayne@69:   Position begin_;
jpayne@69:   Position end_;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename Position>
jpayne@69: constexpr Span<Decay<Position>> span(Position&& start, Position&& end) {
jpayne@69:   return Span<Decay<Position>>(kj::fwd<Position>(start), kj::fwd<Position>(end));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: class Transform_ {
jpayne@69: public:
jpayne@69:   explicit constexpr Transform_(SubParser&& subParser, TransformFunc&& transform)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<decltype(kj::apply(instance<TransformFunc&>(),
jpayne@69:                            instance<OutputType<SubParser, Input>&&>()))>
jpayne@69:       operator()(Input& input) const {
jpayne@69:     KJ_IF_MAYBE(subResult, subParser(input)) {
jpayne@69:       return kj::apply(transform, kj::mv(*subResult));
jpayne@69:     } else {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69:   TransformFunc transform;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: class TransformOrReject_ {
jpayne@69: public:
jpayne@69:   explicit constexpr TransformOrReject_(SubParser&& subParser, TransformFunc&& transform)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   decltype(kj::apply(instance<TransformFunc&>(), instance<OutputType<SubParser, Input>&&>()))
jpayne@69:       operator()(Input& input) const {
jpayne@69:     KJ_IF_MAYBE(subResult, subParser(input)) {
jpayne@69:       return kj::apply(transform, kj::mv(*subResult));
jpayne@69:     } else {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69:   TransformFunc transform;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: class TransformWithLocation_ {
jpayne@69: public:
jpayne@69:   explicit constexpr TransformWithLocation_(SubParser&& subParser, TransformFunc&& transform)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<decltype(kj::apply(instance<TransformFunc&>(),
jpayne@69:                            instance<Span<Decay<decltype(instance<Input&>().getPosition())>>>(),
jpayne@69:                            instance<OutputType<SubParser, Input>&&>()))>
jpayne@69:       operator()(Input& input) const {
jpayne@69:     auto start = input.getPosition();
jpayne@69:     KJ_IF_MAYBE(subResult, subParser(input)) {
jpayne@69:       return kj::apply(transform, Span<decltype(start)>(kj::mv(start), input.getPosition()),
jpayne@69:                        kj::mv(*subResult));
jpayne@69:     } else {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69:   TransformFunc transform;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: constexpr Transform_<SubParser, TransformFunc> transform(
jpayne@69:     SubParser&& subParser, TransformFunc&& functor) {
jpayne@69:   // Constructs a parser which executes some other parser and then transforms the result by invoking
jpayne@69:   // `functor` on it.  Typically `functor` is a lambda.  It is invoked using `kj::apply`,
jpayne@69:   // meaning tuples will be unpacked as arguments.
jpayne@69:   return Transform_<SubParser, TransformFunc>(
jpayne@69:       kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: constexpr TransformOrReject_<SubParser, TransformFunc> transformOrReject(
jpayne@69:     SubParser&& subParser, TransformFunc&& functor) {
jpayne@69:   // Like `transform()` except that `functor` returns a `Maybe`.  If it returns null, parsing fails,
jpayne@69:   // otherwise the parser's result is the content of the `Maybe`.
jpayne@69:   return TransformOrReject_<SubParser, TransformFunc>(
jpayne@69:       kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
jpayne@69: }
jpayne@69: 
jpayne@69: template <typename SubParser, typename TransformFunc>
jpayne@69: constexpr TransformWithLocation_<SubParser, TransformFunc> transformWithLocation(
jpayne@69:     SubParser&& subParser, TransformFunc&& functor) {
jpayne@69:   // Like `transform` except that `functor` also takes a `Span` as its first parameter specifying
jpayne@69:   // the location of the parsed content.  The span's position type is whatever the parser input's
jpayne@69:   // getPosition() returns.
jpayne@69:   return TransformWithLocation_<SubParser, TransformFunc>(
jpayne@69:       kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // notLookingAt()
jpayne@69: // Fails if the given parser succeeds at the current location.
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: class NotLookingAt_ {
jpayne@69: public:
jpayne@69:   explicit constexpr NotLookingAt_(SubParser&& subParser)
jpayne@69:       : subParser(kj::fwd<SubParser>(subParser)) {}
jpayne@69: 
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Tuple<>> operator()(Input& input) const {
jpayne@69:     Input subInput(input);
jpayne@69:     subInput.forgetParent();
jpayne@69:     if (subParser(subInput) == nullptr) {
jpayne@69:       return Tuple<>();
jpayne@69:     } else {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   SubParser subParser;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename SubParser>
jpayne@69: constexpr NotLookingAt_<SubParser> notLookingAt(SubParser&& subParser) {
jpayne@69:   // Constructs a parser which fails at any position where the given parser succeeds.  Otherwise,
jpayne@69:   // it succeeds without consuming any input and returns an empty tuple.
jpayne@69:   return NotLookingAt_<SubParser>(kj::fwd<SubParser>(subParser));
jpayne@69: }
jpayne@69: 
jpayne@69: // -------------------------------------------------------------------
jpayne@69: // endOfInput()
jpayne@69: // Output = Tuple<>, only succeeds if at end-of-input
jpayne@69: 
jpayne@69: class EndOfInput_ {
jpayne@69: public:
jpayne@69:   template <typename Input>
jpayne@69:   Maybe<Tuple<>> operator()(Input& input) const {
jpayne@69:     if (input.atEnd()) {
jpayne@69:       return Tuple<>();
jpayne@69:     } else {
jpayne@69:       return nullptr;
jpayne@69:     }
jpayne@69:   }
jpayne@69: };
jpayne@69: 
jpayne@69: constexpr EndOfInput_ endOfInput = EndOfInput_();
jpayne@69: // A parser that succeeds only if it is called with no input.
jpayne@69: 
jpayne@69: }  // namespace parse
jpayne@69: }  // namespace kj
jpayne@69: 
jpayne@69: KJ_END_HEADER