1// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
2// Licensed under the MIT License:
3//
4// Permission is hereby granted, free of charge, to any person obtaining a copy
5// of this software and associated documentation files (the "Software"), to deal
6// in the Software without restriction, including without limitation the rights
7// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8// copies of the Software, and to permit persons to whom the Software is
9// furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20// THE SOFTWARE.
21
22// Parser combinator framework!
23//
24// This file declares several functions which construct parsers, usually taking other parsers as
25// input, thus making them parser combinators.
26//
27// A valid parser is any functor which takes a reference to an input cursor (defined below) as its
28// input and returns a Maybe. The parser returns null on parse failure, or returns the parsed
29// result on success.
30//
31// An "input cursor" is any type which implements the same interface as IteratorInput, below. Such
32// a type acts as a pointer to the current input location. When a parser returns successfully, it
33// will have updated the input cursor to point to the position just past the end of what was parsed.
34// On failure, the cursor position is unspecified.
35
36#pragma once
37
38#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
39#pragma GCC system_header
40#endif
41
42#include "../common.h"
43#include "../memory.h"
44#include "../array.h"
45#include "../tuple.h"
46#include "../vector.h"
47#if _MSC_VER && !__clang__
48#include <type_traits> // result_of_t
49#endif
50
51namespace kj {
52namespace parse {
53
54template <typename Element, typename Iterator>
55class IteratorInput {
56 // A parser input implementation based on an iterator range.
57
58public:
59 IteratorInput(Iterator begin, Iterator end)
60 : parent(nullptr), pos(begin), end(end), best(begin) {}
61 explicit IteratorInput(IteratorInput& parent)
62 : parent(&parent), pos(parent.pos), end(parent.end), best(parent.pos) {}
63 ~IteratorInput() {
64 if (parent != nullptr) {
65 parent->best = kj::max(kj::max(pos, best), parent->best);
66 }
67 }
68 KJ_DISALLOW_COPY(IteratorInput);
69
70 void advanceParent() {
71 parent->pos = pos;
72 }
73 void forgetParent() {
74 parent = nullptr;
75 }
76
77 bool atEnd() { return pos == end; }
78 auto current() -> decltype(*instance<Iterator>()) {
79 KJ_IREQUIRE(!atEnd());
80 return *pos;
81 }
82 auto consume() -> decltype(*instance<Iterator>()) {
83 KJ_IREQUIRE(!atEnd());
84 return *pos++;
85 }
86 void next() {
87 KJ_IREQUIRE(!atEnd());
88 ++pos;
89 }
90
91 Iterator getBest() { return kj::max(pos, best); }
92
93 Iterator getPosition() { return pos; }
94
95private:
96 IteratorInput* parent;
97 Iterator pos;
98 Iterator end;
99 Iterator best; // furthest we got with any sub-input
100};
101
102template <typename T> struct OutputType_;
103template <typename T> struct OutputType_<Maybe<T>> { typedef T Type; };
104template <typename Parser, typename Input>
105using OutputType = typename OutputType_<
106#if _MSC_VER && !__clang__
107 std::result_of_t<Parser(Input)>
108 // The instance<T&>() based version below results in:
109 // C2064: term does not evaluate to a function taking 1 arguments
110#else
111 decltype(instance<Parser&>()(instance<Input&>()))
112#endif
113 >::Type;
114// Synonym for the output type of a parser, given the parser type and the input type.
115
116// =======================================================================================
117
118template <typename Input, typename Output>
119class ParserRef {
120 // Acts as a reference to some other parser, with simplified type. The referenced parser
121 // is polymorphic by virtual call rather than templates. For grammars of non-trivial size,
122 // it is important to inject refs into the grammar here and there to prevent the parser types
123 // from becoming ridiculous. Using too many of them can hurt performance, though.
124
125public:
126 ParserRef(): parser(nullptr), wrapper(nullptr) {}
127 ParserRef(const ParserRef&) = default;
128 ParserRef(ParserRef&&) = default;
129 ParserRef& operator=(const ParserRef& other) = default;
130 ParserRef& operator=(ParserRef&& other) = default;
131
132 template <typename Other>
133 constexpr ParserRef(Other&& other)
134 : parser(&other), wrapper(&WrapperImplInstance<Decay<Other>>::instance) {
135 static_assert(kj::isReference<Other>(), "ParserRef should not be assigned to a temporary.");
136 }
137
138 template <typename Other>
139 inline ParserRef& operator=(Other&& other) {
140 static_assert(kj::isReference<Other>(), "ParserRef should not be assigned to a temporary.");
141 parser = &other;
142 wrapper = &WrapperImplInstance<Decay<Other>>::instance;
143 return *this;
144 }
145
146 KJ_ALWAYS_INLINE(Maybe<Output> operator()(Input& input) const) {
147 // Always inline in the hopes that this allows branch prediction to kick in so the virtual call
148 // doesn't hurt so much.
149 return wrapper->parse(parser, input);
150 }
151
152private:
153 struct Wrapper {
154 virtual Maybe<Output> parse(const void* parser, Input& input) const = 0;
155 };
156 template <typename ParserImpl>
157 struct WrapperImpl: public Wrapper {
158 Maybe<Output> parse(const void* parser, Input& input) const override {
159 return (*reinterpret_cast<const ParserImpl*>(parser))(input);
160 }
161 };
162 template <typename ParserImpl>
163 struct WrapperImplInstance {
164#if _MSC_VER && !__clang__
165 // TODO(msvc): MSVC currently fails to initialize vtable pointers for constexpr values so
166 // we have to make this just const instead.
167 static const WrapperImpl<ParserImpl> instance;
168#else
169 static constexpr WrapperImpl<ParserImpl> instance = WrapperImpl<ParserImpl>();
170#endif
171 };
172
173 const void* parser;
174 const Wrapper* wrapper;
175};
176
177template <typename Input, typename Output>
178template <typename ParserImpl>
179#if _MSC_VER && !__clang__
180const typename ParserRef<Input, Output>::template WrapperImpl<ParserImpl>
181ParserRef<Input, Output>::WrapperImplInstance<ParserImpl>::instance = WrapperImpl<ParserImpl>();
182#else
183constexpr typename ParserRef<Input, Output>::template WrapperImpl<ParserImpl>
184ParserRef<Input, Output>::WrapperImplInstance<ParserImpl>::instance;
185#endif
186
187template <typename Input, typename ParserImpl>
188constexpr ParserRef<Input, OutputType<ParserImpl, Input>> ref(ParserImpl& impl) {
189 // Constructs a ParserRef. You must specify the input type explicitly, e.g.
190 // `ref<MyInput>(myParser)`.
191
192 return ParserRef<Input, OutputType<ParserImpl, Input>>(impl);
193}
194
195// -------------------------------------------------------------------
196// any
197// Output = one token
198
199class Any_ {
200public:
201 template <typename Input>
202 Maybe<Decay<decltype(instance<Input>().consume())>> operator()(Input& input) const {
203 if (input.atEnd()) {
204 return nullptr;
205 } else {
206 return input.consume();
207 }
208 }
209};
210
211constexpr Any_ any = Any_();
212// A parser which matches any token and simply returns it.
213
214// -------------------------------------------------------------------
215// exactly()
216// Output = Tuple<>
217
218template <typename T>
219class Exactly_ {
220public:
221 explicit constexpr Exactly_(T&& expected): expected(expected) {}
222
223 template <typename Input>
224 Maybe<Tuple<>> operator()(Input& input) const {
225 if (input.atEnd() || input.current() != expected) {
226 return nullptr;
227 } else {
228 input.next();
229 return Tuple<>();
230 }
231 }
232
233private:
234 T expected;
235};
236
237template <typename T>
238constexpr Exactly_<T> exactly(T&& expected) {
239 // Constructs a parser which succeeds when the input is exactly the token specified. The
240 // result is always the empty tuple.
241
242 return Exactly_<T>(kj::fwd<T>(expected));
243}
244
245// -------------------------------------------------------------------
246// exactlyConst()
247// Output = Tuple<>
248
249template <typename T, T expected>
250class ExactlyConst_ {
251public:
252 explicit constexpr ExactlyConst_() {}
253
254 template <typename Input>
255 Maybe<Tuple<>> operator()(Input& input) const {
256 if (input.atEnd() || input.current() != expected) {
257 return nullptr;
258 } else {
259 input.next();
260 return Tuple<>();
261 }
262 }
263};
264
265template <typename T, T expected>
266constexpr ExactlyConst_<T, expected> exactlyConst() {
267 // Constructs a parser which succeeds when the input is exactly the token specified. The
268 // result is always the empty tuple. This parser is templated on the token value which may cause
269 // it to perform better -- or worse. Be sure to measure.
270
271 return ExactlyConst_<T, expected>();
272}
273
274// -------------------------------------------------------------------
275// constResult()
276
277template <typename SubParser, typename Result>
278class ConstResult_ {
279public:
280 explicit constexpr ConstResult_(SubParser&& subParser, Result&& result)
281 : subParser(kj::fwd<SubParser>(subParser)), result(kj::fwd<Result>(result)) {}
282
283 template <typename Input>
284 Maybe<Result> operator()(Input& input) const {
285 if (subParser(input) == nullptr) {
286 return nullptr;
287 } else {
288 return result;
289 }
290 }
291
292private:
293 SubParser subParser;
294 Result result;
295};
296
297template <typename SubParser, typename Result>
298constexpr ConstResult_<SubParser, Result> constResult(SubParser&& subParser, Result&& result) {
299 // Constructs a parser which returns exactly `result` if `subParser` is successful.
300 return ConstResult_<SubParser, Result>(kj::fwd<SubParser>(subParser), kj::fwd<Result>(result));
301}
302
303template <typename SubParser>
304constexpr ConstResult_<SubParser, Tuple<>> discard(SubParser&& subParser) {
305 // Constructs a parser which wraps `subParser` but discards the result.
306 return constResult(kj::fwd<SubParser>(subParser), Tuple<>());
307}
308
309// -------------------------------------------------------------------
310// sequence()
311// Output = Flattened Tuple of outputs of sub-parsers.
312
313template <typename... SubParsers> class Sequence_;
314
315template <typename FirstSubParser, typename... SubParsers>
316class Sequence_<FirstSubParser, SubParsers...> {
317public:
318 template <typename T, typename... U>
319 explicit constexpr Sequence_(T&& firstSubParser, U&&... rest)
320 : first(kj::fwd<T>(firstSubParser)), rest(kj::fwd<U>(rest)...) {}
321
322 // TODO(msvc): The trailing return types on `operator()` and `parseNext()` expose at least two
323 // bugs in MSVC:
324 //
325 // 1. An ICE.
326 // 2. 'error C2672: 'operator __surrogate_func': no matching overloaded function found)',
327 // which crops up in numerous places when trying to build the capnp command line tools.
328 //
329 // The only workaround I found for both bugs is to omit the trailing return types and instead
330 // rely on C++14's return type deduction.
331
332 template <typename Input>
333 auto operator()(Input& input) const
334#if !_MSC_VER || __clang__
335 -> Maybe<decltype(tuple(
336 instance<OutputType<FirstSubParser, Input>>(),
337 instance<OutputType<SubParsers, Input>>()...))>
338#endif
339 {
340 return parseNext(input);
341 }
342
343 template <typename Input, typename... InitialParams>
344 auto parseNext(Input& input, InitialParams&&... initialParams) const
345#if !_MSC_VER || __clang__
346 -> Maybe<decltype(tuple(
347 kj::fwd<InitialParams>(initialParams)...,
348 instance<OutputType<FirstSubParser, Input>>(),
349 instance<OutputType<SubParsers, Input>>()...))>
350#endif
351 {
352 KJ_IF_MAYBE(firstResult, first(input)) {
353 return rest.parseNext(input, kj::fwd<InitialParams>(initialParams)...,
354 kj::mv(*firstResult));
355 } else {
356 // TODO(msvc): MSVC depends on return type deduction to compile this function, so we need to
357 // help it deduce the right type on this code path.
358 return Maybe<decltype(tuple(
359 kj::fwd<InitialParams>(initialParams)...,
360 instance<OutputType<FirstSubParser, Input>>(),
361 instance<OutputType<SubParsers, Input>>()...))>{nullptr};
362 }
363 }
364
365private:
366 FirstSubParser first;
367 Sequence_<SubParsers...> rest;
368};
369
370template <>
371class Sequence_<> {
372public:
373 template <typename Input>
374 Maybe<Tuple<>> operator()(Input& input) const {
375 return parseNext(input);
376 }
377
378 template <typename Input, typename... Params>
379 auto parseNext(Input& input, Params&&... params) const ->
380 Maybe<decltype(tuple(kj::fwd<Params>(params)...))> {
381 return tuple(kj::fwd<Params>(params)...);
382 }
383};
384
385template <typename... SubParsers>
386constexpr Sequence_<SubParsers...> sequence(SubParsers&&... subParsers) {
387 // Constructs a parser that executes each of the parameter parsers in sequence and returns a
388 // tuple of their results.
389
390 return Sequence_<SubParsers...>(kj::fwd<SubParsers>(subParsers)...);
391}
392
393// -------------------------------------------------------------------
394// many()
395// Output = Array of output of sub-parser, or just a uint count if the sub-parser returns Tuple<>.
396
397template <typename SubParser, bool atLeastOne>
398class Many_ {
399 template <typename Input, typename Output = OutputType<SubParser, Input>>
400 struct Impl;
401public:
402 explicit constexpr Many_(SubParser&& subParser)
403 : subParser(kj::fwd<SubParser>(subParser)) {}
404
405 template <typename Input>
406 auto operator()(Input& input) const
407 -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input));
408
409private:
410 SubParser subParser;
411};
412
413template <typename SubParser, bool atLeastOne>
414template <typename Input, typename Output>
415struct Many_<SubParser, atLeastOne>::Impl {
416 static Maybe<Array<Output>> apply(const SubParser& subParser, Input& input) {
417 typedef Vector<OutputType<SubParser, Input>> Results;
418 Results results;
419
420 while (!input.atEnd()) {
421 Input subInput(input);
422
423 KJ_IF_MAYBE(subResult, subParser(subInput)) {
424 subInput.advanceParent();
425 results.add(kj::mv(*subResult));
426 } else {
427 break;
428 }
429 }
430
431 if (atLeastOne && results.empty()) {
432 return nullptr;
433 }
434
435 return results.releaseAsArray();
436 }
437};
438
439template <typename SubParser, bool atLeastOne>
440template <typename Input>
441struct Many_<SubParser, atLeastOne>::Impl<Input, Tuple<>> {
442 // If the sub-parser output is Tuple<>, just return a count.
443
444 static Maybe<uint> apply(const SubParser& subParser, Input& input) {
445 uint count = 0;
446
447 while (!input.atEnd()) {
448 Input subInput(input);
449
450 KJ_IF_MAYBE(subResult, subParser(subInput)) {
451 subInput.advanceParent();
452 ++count;
453 } else {
454 break;
455 }
456 }
457
458 if (atLeastOne && count == 0) {
459 return nullptr;
460 }
461
462 return count;
463 }
464};
465
466template <typename SubParser, bool atLeastOne>
467template <typename Input>
468auto Many_<SubParser, atLeastOne>::operator()(Input& input) const
469 -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input)) {
470 return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, input);
471}
472
473template <typename SubParser>
474constexpr Many_<SubParser, false> many(SubParser&& subParser) {
475 // Constructs a parser that repeatedly executes the given parser until it fails, returning an
476 // Array of the results (or a uint count if `subParser` returns an empty tuple).
477 return Many_<SubParser, false>(kj::fwd<SubParser>(subParser));
478}
479
480template <typename SubParser>
481constexpr Many_<SubParser, true> oneOrMore(SubParser&& subParser) {
482 // Like `many()` but the parser must parse at least one item to be successful.
483 return Many_<SubParser, true>(kj::fwd<SubParser>(subParser));
484}
485
486// -------------------------------------------------------------------
487// times()
488// Output = Array of output of sub-parser, or Tuple<> if sub-parser returns Tuple<>.
489
490template <typename SubParser>
491class Times_ {
492 template <typename Input, typename Output = OutputType<SubParser, Input>>
493 struct Impl;
494public:
495 explicit constexpr Times_(SubParser&& subParser, uint count)
496 : subParser(kj::fwd<SubParser>(subParser)), count(count) {}
497
498 template <typename Input>
499 auto operator()(Input& input) const
500 -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input));
501
502private:
503 SubParser subParser;
504 uint count;
505};
506
507template <typename SubParser>
508template <typename Input, typename Output>
509struct Times_<SubParser>::Impl {
510 static Maybe<Array<Output>> apply(const SubParser& subParser, uint count, Input& input) {
511 auto results = heapArrayBuilder<OutputType<SubParser, Input>>(count);
512
513 while (results.size() < count) {
514 if (input.atEnd()) {
515 return nullptr;
516 } else KJ_IF_MAYBE(subResult, subParser(input)) {
517 results.add(kj::mv(*subResult));
518 } else {
519 return nullptr;
520 }
521 }
522
523 return results.finish();
524 }
525};
526
527template <typename SubParser>
528template <typename Input>
529struct Times_<SubParser>::Impl<Input, Tuple<>> {
530 // If the sub-parser output is Tuple<>, just return a count.
531
532 static Maybe<Tuple<>> apply(const SubParser& subParser, uint count, Input& input) {
533 uint actualCount = 0;
534
535 while (actualCount < count) {
536 if (input.atEnd()) {
537 return nullptr;
538 } else KJ_IF_MAYBE(subResult, subParser(input)) {
539 ++actualCount;
540 } else {
541 return nullptr;
542 }
543 }
544
545 return tuple();
546 }
547};
548
549template <typename SubParser>
550template <typename Input>
551auto Times_<SubParser>::operator()(Input& input) const
552 -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input)) {
553 return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, count, input);
554}
555
556template <typename SubParser>
557constexpr Times_<SubParser> times(SubParser&& subParser, uint count) {
558 // Constructs a parser that repeats the subParser exactly `count` times.
559 return Times_<SubParser>(kj::fwd<SubParser>(subParser), count);
560}
561
562// -------------------------------------------------------------------
563// optional()
564// Output = Maybe<output of sub-parser>
565
566template <typename SubParser>
567class Optional_ {
568public:
569 explicit constexpr Optional_(SubParser&& subParser)
570 : subParser(kj::fwd<SubParser>(subParser)) {}
571
572 template <typename Input>
573 Maybe<Maybe<OutputType<SubParser, Input>>> operator()(Input& input) const {
574 typedef Maybe<OutputType<SubParser, Input>> Result;
575
576 Input subInput(input);
577 KJ_IF_MAYBE(subResult, subParser(subInput)) {
578 subInput.advanceParent();
579 return Result(kj::mv(*subResult));
580 } else {
581 return Result(nullptr);
582 }
583 }
584
585private:
586 SubParser subParser;
587};
588
589template <typename SubParser>
590constexpr Optional_<SubParser> optional(SubParser&& subParser) {
591 // Constructs a parser that accepts zero or one of the given sub-parser, returning a Maybe
592 // of the sub-parser's result.
593 return Optional_<SubParser>(kj::fwd<SubParser>(subParser));
594}
595
596// -------------------------------------------------------------------
597// oneOf()
598// All SubParsers must have same output type, which becomes the output type of the
599// OneOfParser.
600
601template <typename... SubParsers>
602class OneOf_;
603
604template <typename FirstSubParser, typename... SubParsers>
605class OneOf_<FirstSubParser, SubParsers...> {
606public:
607 explicit constexpr OneOf_(FirstSubParser&& firstSubParser, SubParsers&&... rest)
608 : first(kj::fwd<FirstSubParser>(firstSubParser)), rest(kj::fwd<SubParsers>(rest)...) {}
609
610 template <typename Input>
611 Maybe<OutputType<FirstSubParser, Input>> operator()(Input& input) const {
612 {
613 Input subInput(input);
614 Maybe<OutputType<FirstSubParser, Input>> firstResult = first(subInput);
615
616 if (firstResult != nullptr) {
617 subInput.advanceParent();
618 return kj::mv(firstResult);
619 }
620 }
621
622 // Hoping for some tail recursion here...
623 return rest(input);
624 }
625
626private:
627 FirstSubParser first;
628 OneOf_<SubParsers...> rest;
629};
630
631template <>
632class OneOf_<> {
633public:
634 template <typename Input>
635 decltype(nullptr) operator()(Input& input) const {
636 return nullptr;
637 }
638};
639
640template <typename... SubParsers>
641constexpr OneOf_<SubParsers...> oneOf(SubParsers&&... parsers) {
642 // Constructs a parser that accepts one of a set of options. The parser behaves as the first
643 // sub-parser in the list which returns successfully. All of the sub-parsers must return the
644 // same type.
645 return OneOf_<SubParsers...>(kj::fwd<SubParsers>(parsers)...);
646}
647
648// -------------------------------------------------------------------
649// transform()
650// Output = Result of applying transform functor to input value. If input is a tuple, it is
651// unpacked to form the transformation parameters.
652
653template <typename Position>
654struct Span {
655public:
656 inline const Position& begin() const { return begin_; }
657 inline const Position& end() const { return end_; }
658
659 Span() = default;
660 inline constexpr Span(Position&& begin, Position&& end): begin_(mv(begin)), end_(mv(end)) {}
661
662private:
663 Position begin_;
664 Position end_;
665};
666
667template <typename Position>
668constexpr Span<Decay<Position>> span(Position&& start, Position&& end) {
669 return Span<Decay<Position>>(kj::fwd<Position>(start), kj::fwd<Position>(end));
670}
671
672template <typename SubParser, typename TransformFunc>
673class Transform_ {
674public:
675 explicit constexpr Transform_(SubParser&& subParser, TransformFunc&& transform)
676 : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
677
678 template <typename Input>
679 Maybe<decltype(kj::apply(instance<TransformFunc&>(),
680 instance<OutputType<SubParser, Input>&&>()))>
681 operator()(Input& input) const {
682 KJ_IF_MAYBE(subResult, subParser(input)) {
683 return kj::apply(transform, kj::mv(*subResult));
684 } else {
685 return nullptr;
686 }
687 }
688
689private:
690 SubParser subParser;
691 TransformFunc transform;
692};
693
694template <typename SubParser, typename TransformFunc>
695class TransformOrReject_ {
696public:
697 explicit constexpr TransformOrReject_(SubParser&& subParser, TransformFunc&& transform)
698 : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
699
700 template <typename Input>
701 decltype(kj::apply(instance<TransformFunc&>(), instance<OutputType<SubParser, Input>&&>()))
702 operator()(Input& input) const {
703 KJ_IF_MAYBE(subResult, subParser(input)) {
704 return kj::apply(transform, kj::mv(*subResult));
705 } else {
706 return nullptr;
707 }
708 }
709
710private:
711 SubParser subParser;
712 TransformFunc transform;
713};
714
715template <typename SubParser, typename TransformFunc>
716class TransformWithLocation_ {
717public:
718 explicit constexpr TransformWithLocation_(SubParser&& subParser, TransformFunc&& transform)
719 : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}
720
721 template <typename Input>
722 Maybe<decltype(kj::apply(instance<TransformFunc&>(),
723 instance<Span<Decay<decltype(instance<Input&>().getPosition())>>>(),
724 instance<OutputType<SubParser, Input>&&>()))>
725 operator()(Input& input) const {
726 auto start = input.getPosition();
727 KJ_IF_MAYBE(subResult, subParser(input)) {
728 return kj::apply(transform, Span<decltype(start)>(kj::mv(start), input.getPosition()),
729 kj::mv(*subResult));
730 } else {
731 return nullptr;
732 }
733 }
734
735private:
736 SubParser subParser;
737 TransformFunc transform;
738};
739
740template <typename SubParser, typename TransformFunc>
741constexpr Transform_<SubParser, TransformFunc> transform(
742 SubParser&& subParser, TransformFunc&& functor) {
743 // Constructs a parser which executes some other parser and then transforms the result by invoking
744 // `functor` on it. Typically `functor` is a lambda. It is invoked using `kj::apply`,
745 // meaning tuples will be unpacked as arguments.
746 return Transform_<SubParser, TransformFunc>(
747 kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
748}
749
750template <typename SubParser, typename TransformFunc>
751constexpr TransformOrReject_<SubParser, TransformFunc> transformOrReject(
752 SubParser&& subParser, TransformFunc&& functor) {
753 // Like `transform()` except that `functor` returns a `Maybe`. If it returns null, parsing fails,
754 // otherwise the parser's result is the content of the `Maybe`.
755 return TransformOrReject_<SubParser, TransformFunc>(
756 kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
757}
758
759template <typename SubParser, typename TransformFunc>
760constexpr TransformWithLocation_<SubParser, TransformFunc> transformWithLocation(
761 SubParser&& subParser, TransformFunc&& functor) {
762 // Like `transform` except that `functor` also takes a `Span` as its first parameter specifying
763 // the location of the parsed content. The span's position type is whatever the parser input's
764 // getPosition() returns.
765 return TransformWithLocation_<SubParser, TransformFunc>(
766 kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
767}
768
769// -------------------------------------------------------------------
770// notLookingAt()
771// Fails if the given parser succeeds at the current location.
772
773template <typename SubParser>
774class NotLookingAt_ {
775public:
776 explicit constexpr NotLookingAt_(SubParser&& subParser)
777 : subParser(kj::fwd<SubParser>(subParser)) {}
778
779 template <typename Input>
780 Maybe<Tuple<>> operator()(Input& input) const {
781 Input subInput(input);
782 subInput.forgetParent();
783 if (subParser(subInput) == nullptr) {
784 return Tuple<>();
785 } else {
786 return nullptr;
787 }
788 }
789
790private:
791 SubParser subParser;
792};
793
794template <typename SubParser>
795constexpr NotLookingAt_<SubParser> notLookingAt(SubParser&& subParser) {
796 // Constructs a parser which fails at any position where the given parser succeeds. Otherwise,
797 // it succeeds without consuming any input and returns an empty tuple.
798 return NotLookingAt_<SubParser>(kj::fwd<SubParser>(subParser));
799}
800
801// -------------------------------------------------------------------
802// endOfInput()
803// Output = Tuple<>, only succeeds if at end-of-input
804
805class EndOfInput_ {
806public:
807 template <typename Input>
808 Maybe<Tuple<>> operator()(Input& input) const {
809 if (input.atEnd()) {
810 return Tuple<>();
811 } else {
812 return nullptr;
813 }
814 }
815};
816
817constexpr EndOfInput_ endOfInput = EndOfInput_();
818// A parser that succeeds only if it is called with no input.
819
820} // namespace parse
821} // namespace kj
822