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