common.h 24.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
// Copyright (c) 2013, Kenton Varda <temporal@gmail.com>
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

24 25 26 27 28 29 30 31 32 33 34 35 36 37
// Parser combinator framework!
//
// This file declares several functions which construct parsers, usually taking other parsers as
// input, thus making them parser combinators.
//
// A valid parser is any functor which takes a reference to an input cursor (defined below) as its
// input and returns a Maybe.  The parser returns null on parse failure, or returns the parsed
// result on success.
//
// An "input cursor" is any type which implements the same interface as IteratorInput, below.  Such
// a type acts as a pointer to the current input location.  When a parser returns successfully, it
// will have updated the input cursor to point to the position just past the end of what was parsed.
// On failure, the cursor position is unspecified.

38 39
#ifndef KJ_PARSE_COMMON_H_
#define KJ_PARSE_COMMON_H_
40

41 42 43 44 45
#include "../common.h"
#include "../memory.h"
#include "../array.h"
#include "../tuple.h"
#include "../vector.h"
46 47 48 49 50 51

namespace kj {
namespace parse {

template <typename Element, typename Iterator>
class IteratorInput {
52 53
  // A parser input implementation based on an iterator range.

54 55 56
public:
  IteratorInput(Iterator begin, Iterator end)
      : parent(nullptr), pos(begin), end(end), best(begin) {}
57
  explicit IteratorInput(IteratorInput& parent)
58 59 60 61 62 63
      : parent(&parent), pos(parent.pos), end(parent.end), best(parent.pos) {}
  ~IteratorInput() {
    if (parent != nullptr) {
      parent->best = kj::max(kj::max(pos, best), parent->best);
    }
  }
64
  KJ_DISALLOW_COPY(IteratorInput);
65 66 67 68

  void advanceParent() {
    parent->pos = pos;
  }
69 70 71
  void forgetParent() {
    parent = nullptr;
  }
72 73

  bool atEnd() { return pos == end; }
74
  auto current() -> decltype(*instance<Iterator>()) {
75 76 77
    KJ_IREQUIRE(!atEnd());
    return *pos;
  }
78
  auto consume() -> decltype(*instance<Iterator>()) {
79
    KJ_IREQUIRE(!atEnd());
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
    return *pos++;
  }
  void next() {
    KJ_IREQUIRE(!atEnd());
    ++pos;
  }

  Iterator getBest() { return kj::max(pos, best); }

  Iterator getPosition() { return pos; }

private:
  IteratorInput* parent;
  Iterator pos;
  Iterator end;
  Iterator best;  // furthest we got with any sub-input
};

98 99 100 101 102
template <typename T> struct OutputType_;
template <typename T> struct OutputType_<Maybe<T>> { typedef T Type; };
template <typename Parser, typename Input>
using OutputType = typename OutputType_<decltype(instance<Parser&>()(instance<Input&>()))>::Type;
// Synonym for the output type of a parser, given the parser type and the input type.
103 104 105 106

// =======================================================================================

template <typename Input, typename Output>
107 108 109 110 111
class ParserRef {
  // Acts as a reference to some other parser, with simplified type.  The referenced parser
  // is polymorphic by virtual call rather than templates.  For grammars of non-trivial size,
  // it is important to inject refs into the grammar here and there to prevent the parser types
  // from becoming ridiculous.  Using too many of them can hurt performance, though.
112 113

public:
114 115 116 117 118 119
  ParserRef(): parser(nullptr), wrapper(nullptr) {}
  ParserRef(const ParserRef&) = default;
  ParserRef(ParserRef&&) = default;
  ParserRef& operator=(const ParserRef& other) = default;
  ParserRef& operator=(ParserRef&& other) = default;

120
  template <typename Other>
121 122 123 124 125 126 127 128 129 130 131 132
  constexpr ParserRef(Other&& other)
      : parser(&other), wrapper(&WrapperImplInstance<Decay<Other>>::instance) {
    static_assert(kj::isReference<Other>(), "ParseRef should not be assigned to a temporary.");
  }

  template <typename Other>
  inline ParserRef& operator=(Other&& other) {
    static_assert(kj::isReference<Other>(), "ParseRef should not be assigned to a temporary.");
    parser = &other;
    wrapper = &WrapperImplInstance<Decay<Other>>::instance;
    return *this;
  }
133

134 135 136
  KJ_ALWAYS_INLINE(Maybe<Output> operator()(Input& input) const) {
    // Always inline in the hopes that this allows branch prediction to kick in so the virtual call
    // doesn't hurt so much.
137
    return wrapper->parse(parser, input);
138 139 140
  }

private:
141 142 143 144 145 146 147
  struct Wrapper {
    virtual Maybe<Output> parse(const void* parser, Input& input) const = 0;
  };
  template <typename ParserImpl>
  struct WrapperImpl: public Wrapper {
    Maybe<Output> parse(const void* parser, Input& input) const override {
      return (*reinterpret_cast<const ParserImpl*>(parser))(input);
148
    }
Kenton Varda's avatar
Kenton Varda committed
149 150 151 152
  };
  template <typename ParserImpl>
  struct WrapperImplInstance {
    static constexpr WrapperImpl<ParserImpl> instance = WrapperImpl<ParserImpl>();
153 154
  };

155
  const void* parser;
156
  const Wrapper* wrapper;
157 158
};

Kenton Varda's avatar
Kenton Varda committed
159 160 161 162 163
template <typename Input, typename Output>
template <typename ParserImpl>
constexpr ParserRef<Input, Output>::WrapperImpl<ParserImpl>
ParserRef<Input, Output>::WrapperImplInstance<ParserImpl>::instance;

164
template <typename Input, typename ParserImpl>
Kenton Varda's avatar
Kenton Varda committed
165
constexpr ParserRef<Input, OutputType<ParserImpl, Input>> ref(ParserImpl& impl) {
166 167
  // Constructs a ParserRef.  You must specify the input type explicitly, e.g.
  // `ref<MyInput>(myParser)`.
168

169 170
  return ParserRef<Input, OutputType<ParserImpl, Input>>(impl);
}
171

172
// -------------------------------------------------------------------
173
// any
174 175 176 177 178
// Output = one token

class Any_ {
public:
  template <typename Input>
179
  Maybe<Decay<decltype(instance<Input>().consume())>> operator()(Input& input) const {
180 181 182
    if (input.atEnd()) {
      return nullptr;
    } else {
183
      return input.consume();
184 185 186 187
    }
  }
};

188 189
constexpr Any_ any = Any_();
// A parser which matches any token and simply returns it.
190

191
// -------------------------------------------------------------------
192
// exactly()
193
// Output = Tuple<>
194

195 196
template <typename T>
class Exactly_ {
197
public:
Kenton Varda's avatar
Kenton Varda committed
198
  explicit constexpr Exactly_(T&& expected): expected(expected) {}
199

200 201
  template <typename Input>
  Maybe<Tuple<>> operator()(Input& input) const {
202 203 204 205
    if (input.atEnd() || input.current() != expected) {
      return nullptr;
    } else {
      input.next();
206
      return Tuple<>();
207 208 209 210
    }
  }

private:
211
  T expected;
212 213
};

214
template <typename T>
Kenton Varda's avatar
Kenton Varda committed
215
constexpr Exactly_<T> exactly(T&& expected) {
216 217 218 219
  // Constructs a parser which succeeds when the input is exactly the token specified.  The
  // result is always the empty tuple.

  return Exactly_<T>(kj::fwd<T>(expected));
220 221
}

Kenton Varda's avatar
Kenton Varda committed
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
// -------------------------------------------------------------------
// exactlyConst()
// Output = Tuple<>

template <typename T, T expected>
class ExactlyConst_ {
public:
  explicit constexpr ExactlyConst_() {}

  template <typename Input>
  Maybe<Tuple<>> operator()(Input& input) const {
    if (input.atEnd() || input.current() != expected) {
      return nullptr;
    } else {
      input.next();
      return Tuple<>();
    }
  }
};

template <typename T, T expected>
constexpr ExactlyConst_<T, expected> exactlyConst() {
  // Constructs a parser which succeeds when the input is exactly the token specified.  The
  // result is always the empty tuple.  This parser is templated on the token value which may cause
  // it to perform better -- or worse.  Be sure to measure.

  return ExactlyConst_<T, expected>();
}

// -------------------------------------------------------------------
// constResult()

template <typename SubParser, typename Result>
class ConstResult_ {
public:
  explicit constexpr ConstResult_(SubParser&& subParser, Result&& result)
      : subParser(kj::fwd<SubParser>(subParser)), result(kj::fwd<Result>(result)) {}

  template <typename Input>
  Maybe<Result> operator()(Input& input) const {
    if (subParser(input) == nullptr) {
      return nullptr;
    } else {
      return result;
    }
  }

private:
  SubParser subParser;
  Result result;
};

template <typename SubParser, typename Result>
constexpr ConstResult_<SubParser, Result> constResult(SubParser&& subParser, Result&& result) {
  // Constructs a parser which returns exactly `result` if `subParser` is successful.
  return ConstResult_<SubParser, Result>(kj::fwd<SubParser>(subParser), kj::fwd<Result>(result));
}

280 281 282 283 284 285
template <typename SubParser>
constexpr ConstResult_<SubParser, Tuple<>> discard(SubParser&& subParser) {
  // Constructs a parser which wraps `subParser` but discards the result.
  return constResult(kj::fwd<SubParser>(subParser), Tuple<>());
}

286
// -------------------------------------------------------------------
287
// sequence()
288 289
// Output = Flattened Tuple of outputs of sub-parsers.

290
template <typename... SubParsers> class Sequence_;
291

292 293
template <typename FirstSubParser, typename... SubParsers>
class Sequence_<FirstSubParser, SubParsers...> {
294 295
public:
  template <typename T, typename... U>
Kenton Varda's avatar
Kenton Varda committed
296
  explicit constexpr Sequence_(T&& firstSubParser, U&&... rest)
297 298
      : first(kj::fwd<T>(firstSubParser)), rest(kj::fwd<U>(rest)...) {}

299
  template <typename Input>
300 301
  auto operator()(Input& input) const ->
      Maybe<decltype(tuple(
302 303
          instance<OutputType<FirstSubParser, Input>>(),
          instance<OutputType<SubParsers, Input>>()...))> {
304 305 306
    return parseNext(input);
  }

307
  template <typename Input, typename... InitialParams>
308 309 310
  auto parseNext(Input& input, InitialParams&&... initialParams) const ->
      Maybe<decltype(tuple(
          kj::fwd<InitialParams>(initialParams)...,
311 312
          instance<OutputType<FirstSubParser, Input>>(),
          instance<OutputType<SubParsers, Input>>()...))> {
313 314 315 316 317 318 319 320 321 322
    KJ_IF_MAYBE(firstResult, first(input)) {
      return rest.parseNext(input, kj::fwd<InitialParams>(initialParams)...,
                            kj::mv(*firstResult));
    } else {
      return nullptr;
    }
  }

private:
  FirstSubParser first;
323
  Sequence_<SubParsers...> rest;
324 325
};

326 327
template <>
class Sequence_<> {
328
public:
329
  template <typename Input>
330
  Maybe<Tuple<>> operator()(Input& input) const {
331 332 333
    return parseNext(input);
  }

334
  template <typename Input, typename... Params>
335 336 337 338 339 340
  auto parseNext(Input& input, Params&&... params) const ->
      Maybe<decltype(tuple(kj::fwd<Params>(params)...))> {
    return tuple(kj::fwd<Params>(params)...);
  }
};

341
template <typename... SubParsers>
Kenton Varda's avatar
Kenton Varda committed
342
constexpr Sequence_<SubParsers...> sequence(SubParsers&&... subParsers) {
343 344
  // Constructs a parser that executes each of the parameter parsers in sequence and returns a
  // tuple of their results.
345

346 347
  return Sequence_<SubParsers...>(kj::fwd<SubParsers>(subParsers)...);
}
348 349

// -------------------------------------------------------------------
350
// many()
351
// Output = Array of output of sub-parser, or just a uint count if the sub-parser returns Tuple<>.
352 353

template <typename SubParser, bool atLeastOne>
354
class Many_ {
355 356
  template <typename Input, typename Output = OutputType<SubParser, Input>>
  struct Impl;
357
public:
Kenton Varda's avatar
Kenton Varda committed
358
  explicit constexpr Many_(SubParser&& subParser)
359
      : subParser(kj::fwd<SubParser>(subParser)) {}
360

361
  template <typename Input>
362 363 364 365 366 367 368 369 370 371 372
  auto operator()(Input& input) const
      -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input));

private:
  SubParser subParser;
};

template <typename SubParser, bool atLeastOne>
template <typename Input, typename Output>
struct Many_<SubParser, atLeastOne>::Impl {
  static Maybe<Array<Output>> apply(const SubParser& subParser, Input& input) {
373
    typedef Vector<OutputType<SubParser, Input>> Results;
374 375 376
    Results results;

    while (!input.atEnd()) {
377
      Input subInput(input);
378 379 380 381 382 383 384 385 386 387 388 389 390

      KJ_IF_MAYBE(subResult, subParser(subInput)) {
        subInput.advanceParent();
        results.add(kj::mv(*subResult));
      } else {
        break;
      }
    }

    if (atLeastOne && results.empty()) {
      return nullptr;
    }

391
    return results.releaseAsArray();
392
  }
393
};
394

395 396 397
template <typename SubParser, bool atLeastOne>
template <typename Input>
struct Many_<SubParser, atLeastOne>::Impl<Input, Tuple<>> {
398 399
  // If the sub-parser output is Tuple<>, just return a count.

400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
  static Maybe<uint> apply(const SubParser& subParser, Input& input) {
    uint count = 0;

    while (!input.atEnd()) {
      Input subInput(input);

      KJ_IF_MAYBE(subResult, subParser(subInput)) {
        subInput.advanceParent();
        ++count;
      } else {
        break;
      }
    }

    if (atLeastOne && count == 0) {
      return nullptr;
    }

    return count;
  }
420 421
};

422 423 424 425 426 427 428
template <typename SubParser, bool atLeastOne>
template <typename Input>
auto Many_<SubParser, atLeastOne>::operator()(Input& input) const
    -> decltype(Impl<Input>::apply(instance<const SubParser&>(), input)) {
  return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, input);
}

429
template <typename SubParser>
Kenton Varda's avatar
Kenton Varda committed
430
constexpr Many_<SubParser, false> many(SubParser&& subParser) {
431
  // Constructs a parser that repeatedly executes the given parser until it fails, returning an
432
  // Array of the results (or a uint count if `subParser` returns an empty tuple).
433
  return Many_<SubParser, false>(kj::fwd<SubParser>(subParser));
434 435 436
}

template <typename SubParser>
Kenton Varda's avatar
Kenton Varda committed
437
constexpr Many_<SubParser, true> oneOrMore(SubParser&& subParser) {
438 439
  // Like `many()` but the parser must parse at least one item to be successful.
  return Many_<SubParser, true>(kj::fwd<SubParser>(subParser));
440 441
}

442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517
// -------------------------------------------------------------------
// times()
// Output = Array of output of sub-parser, or Tuple<> if sub-parser returns Tuple<>.

template <typename SubParser>
class Times_ {
  template <typename Input, typename Output = OutputType<SubParser, Input>>
  struct Impl;
public:
  explicit constexpr Times_(SubParser&& subParser, uint count)
      : subParser(kj::fwd<SubParser>(subParser)), count(count) {}

  template <typename Input>
  auto operator()(Input& input) const
      -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input));

private:
  SubParser subParser;
  uint count;
};

template <typename SubParser>
template <typename Input, typename Output>
struct Times_<SubParser>::Impl {
  static Maybe<Array<Output>> apply(const SubParser& subParser, uint count, Input& input) {
    auto results = heapArrayBuilder<OutputType<SubParser, Input>>(count);

    while (results.size() < count) {
      if (input.atEnd()) {
        return nullptr;
      } else KJ_IF_MAYBE(subResult, subParser(input)) {
        results.add(kj::mv(*subResult));
      } else {
        return nullptr;
      }
    }

    return results.finish();
  }
};

template <typename SubParser>
template <typename Input>
struct Times_<SubParser>::Impl<Input, Tuple<>> {
  // If the sub-parser output is Tuple<>, just return a count.

  static Maybe<Tuple<>> apply(const SubParser& subParser, uint count, Input& input) {
    uint actualCount = 0;

    while (actualCount < count) {
      if (input.atEnd()) {
        return nullptr;
      } else KJ_IF_MAYBE(subResult, subParser(input)) {
        ++actualCount;
      } else {
        return nullptr;
      }
    }

    return tuple();
  }
};

template <typename SubParser>
template <typename Input>
auto Times_<SubParser>::operator()(Input& input) const
    -> decltype(Impl<Input>::apply(instance<const SubParser&>(), instance<uint>(), input)) {
  return Impl<Input, OutputType<SubParser, Input>>::apply(subParser, count, input);
}

template <typename SubParser>
constexpr Times_<SubParser> times(SubParser&& subParser, uint count) {
  // Constructs a parser that repeats the subParser exactly `count` times.
  return Times_<SubParser>(kj::fwd<SubParser>(subParser), count);
}

518
// -------------------------------------------------------------------
519
// optional()
520 521 522
// Output = Maybe<output of sub-parser>

template <typename SubParser>
523
class Optional_ {
524
public:
Kenton Varda's avatar
Kenton Varda committed
525
  explicit constexpr Optional_(SubParser&& subParser)
526
      : subParser(kj::fwd<SubParser>(subParser)) {}
527

528 529 530
  template <typename Input>
  Maybe<Maybe<OutputType<SubParser, Input>>> operator()(Input& input) const {
    typedef Maybe<OutputType<SubParser, Input>> Result;
531

532 533
    Input subInput(input);
    KJ_IF_MAYBE(subResult, subParser(subInput)) {
534 535
      subInput.advanceParent();
      return Result(kj::mv(*subResult));
536 537
    } else {
      return Result(nullptr);
538 539 540 541 542 543 544 545
    }
  }

private:
  SubParser subParser;
};

template <typename SubParser>
Kenton Varda's avatar
Kenton Varda committed
546
constexpr Optional_<SubParser> optional(SubParser&& subParser) {
547 548 549
  // Constructs a parser that accepts zero or one of the given sub-parser, returning a Maybe
  // of the sub-parser's result.
  return Optional_<SubParser>(kj::fwd<SubParser>(subParser));
550 551 552
}

// -------------------------------------------------------------------
553
// oneOf()
554 555 556
// All SubParsers must have same output type, which becomes the output type of the
// OneOfParser.

557 558
template <typename... SubParsers>
class OneOf_;
559

560 561
template <typename FirstSubParser, typename... SubParsers>
class OneOf_<FirstSubParser, SubParsers...> {
562
public:
563 564
  explicit constexpr OneOf_(FirstSubParser&& firstSubParser, SubParsers&&... rest)
      : first(kj::fwd<FirstSubParser>(firstSubParser)), rest(kj::fwd<SubParsers>(rest)...) {}
565

566 567
  template <typename Input>
  Maybe<OutputType<FirstSubParser, Input>> operator()(Input& input) const {
568 569
    {
      Input subInput(input);
570
      Maybe<OutputType<FirstSubParser, Input>> firstResult = first(subInput);
571 572 573 574 575 576 577 578 579 580 581 582 583

      if (firstResult != nullptr) {
        subInput.advanceParent();
        return kj::mv(firstResult);
      }
    }

    // Hoping for some tail recursion here...
    return rest(input);
  }

private:
  FirstSubParser first;
584
  OneOf_<SubParsers...> rest;
585 586
};

587 588
template <>
class OneOf_<> {
589
public:
590 591
  template <typename Input>
  decltype(nullptr) operator()(Input& input) const {
592 593 594 595
    return nullptr;
  }
};

596
template <typename... SubParsers>
Kenton Varda's avatar
Kenton Varda committed
597
constexpr OneOf_<SubParsers...> oneOf(SubParsers&&... parsers) {
598 599 600 601
  // Constructs a parser that accepts one of a set of options.  The parser behaves as the first
  // sub-parser in the list which returns successfully.  All of the sub-parsers must return the
  // same type.
  return OneOf_<SubParsers...>(kj::fwd<SubParsers>(parsers)...);
602 603 604
}

// -------------------------------------------------------------------
605
// transform()
606 607 608 609 610 611
// Output = Result of applying transform functor to input value.  If input is a tuple, it is
// unpacked to form the transformation parameters.

template <typename Position>
struct Span {
public:
612 613
  inline const Position& begin() const { return begin_; }
  inline const Position& end() const { return end_; }
614 615

  Span() = default;
Kenton Varda's avatar
Kenton Varda committed
616
  inline constexpr Span(Position&& begin, Position&& end): begin_(mv(begin)), end_(mv(end)) {}
617 618 619 620 621 622

private:
  Position begin_;
  Position end_;
};

623
template <typename Position>
Kenton Varda's avatar
Kenton Varda committed
624
constexpr Span<Decay<Position>> span(Position&& start, Position&& end) {
625 626
  return Span<Decay<Position>>(kj::fwd<Position>(start), kj::fwd<Position>(end));
}
627

628 629 630
template <typename SubParser, typename TransformFunc>
class Transform_ {
public:
Kenton Varda's avatar
Kenton Varda committed
631
  explicit constexpr Transform_(SubParser&& subParser, TransformFunc&& transform)
632 633
      : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}

634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
  template <typename Input>
  Maybe<decltype(kj::apply(instance<TransformFunc&>(),
                           instance<OutputType<SubParser, Input>&&>()))>
      operator()(Input& input) const {
    KJ_IF_MAYBE(subResult, subParser(input)) {
      return kj::apply(transform, kj::mv(*subResult));
    } else {
      return nullptr;
    }
  }

private:
  SubParser subParser;
  TransformFunc transform;
};

650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670
template <typename SubParser, typename TransformFunc>
class TransformOrReject_ {
public:
  explicit constexpr TransformOrReject_(SubParser&& subParser, TransformFunc&& transform)
      : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}

  template <typename Input>
  decltype(kj::apply(instance<TransformFunc&>(), instance<OutputType<SubParser, Input>&&>()))
      operator()(Input& input) const {
    KJ_IF_MAYBE(subResult, subParser(input)) {
      return kj::apply(transform, kj::mv(*subResult));
    } else {
      return nullptr;
    }
  }

private:
  SubParser subParser;
  TransformFunc transform;
};

671 672 673 674 675 676
template <typename SubParser, typename TransformFunc>
class TransformWithLocation_ {
public:
  explicit constexpr TransformWithLocation_(SubParser&& subParser, TransformFunc&& transform)
      : subParser(kj::fwd<SubParser>(subParser)), transform(kj::fwd<TransformFunc>(transform)) {}

677 678 679 680 681
  template <typename Input>
  Maybe<decltype(kj::apply(instance<TransformFunc&>(),
                           instance<Span<Decay<decltype(instance<Input&>().getPosition())>>>(),
                           instance<OutputType<SubParser, Input>&&>()))>
      operator()(Input& input) const {
682 683
    auto start = input.getPosition();
    KJ_IF_MAYBE(subResult, subParser(input)) {
684
      return kj::apply(transform, Span<decltype(start)>(kj::mv(start), input.getPosition()),
685
                       kj::mv(*subResult));
686 687 688 689 690 691 692
    } else {
      return nullptr;
    }
  }

private:
  SubParser subParser;
693
  TransformFunc transform;
694 695
};

696
template <typename SubParser, typename TransformFunc>
Kenton Varda's avatar
Kenton Varda committed
697 698
constexpr Transform_<SubParser, TransformFunc> transform(
    SubParser&& subParser, TransformFunc&& functor) {
699 700 701 702 703
  // Constructs a parser which executes some other parser and then transforms the result by invoking
  // `functor` on it.  Typically `functor` is a lambda.  It is invoked using `kj::apply`,
  // meaning tuples will be unpacked as arguments.
  return Transform_<SubParser, TransformFunc>(
      kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
704 705
}

706 707 708 709 710 711 712 713 714
template <typename SubParser, typename TransformFunc>
constexpr TransformOrReject_<SubParser, TransformFunc> transformOrReject(
    SubParser&& subParser, TransformFunc&& functor) {
  // Like `transform()` except that `functor` returns a `Maybe`.  If it returns null, parsing fails,
  // otherwise the parser's result is the content of the `Maybe`.
  return TransformOrReject_<SubParser, TransformFunc>(
      kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
}

715 716 717
template <typename SubParser, typename TransformFunc>
constexpr TransformWithLocation_<SubParser, TransformFunc> transformWithLocation(
    SubParser&& subParser, TransformFunc&& functor) {
718 719 720
  // Like `transform` except that `functor` also takes a `Span` as its first parameter specifying
  // the location of the parsed content.  The span's position type is whatever the parser input's
  // getPosition() returns.
721 722 723 724 725 726 727 728 729 730 731
  return TransformWithLocation_<SubParser, TransformFunc>(
      kj::fwd<SubParser>(subParser), kj::fwd<TransformFunc>(functor));
}

// -------------------------------------------------------------------
// notLookingAt()
// Fails if the given parser succeeds at the current location.

template <typename SubParser>
class NotLookingAt_ {
public:
732 733
  explicit constexpr NotLookingAt_(SubParser&& subParser)
      : subParser(kj::fwd<SubParser>(subParser)) {}
734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756

  template <typename Input>
  Maybe<Tuple<>> operator()(Input& input) const {
    Input subInput(input);
    subInput.forgetParent();
    if (subParser(subInput) == nullptr) {
      return Tuple<>();
    } else {
      return nullptr;
    }
  }

private:
  SubParser subParser;
};

template <typename SubParser>
constexpr NotLookingAt_<SubParser> notLookingAt(SubParser&& subParser) {
  // Constructs a parser which fails at any position where the given parser succeeds.  Otherwise,
  // it succeeds without consuming any input and returns an empty tuple.
  return NotLookingAt_<SubParser>(kj::fwd<SubParser>(subParser));
}

757
// -------------------------------------------------------------------
758
// endOfInput()
759
// Output = Tuple<>, only succeeds if at end-of-input
760

761
class EndOfInput_ {
762
public:
763
  template <typename Input>
764
  Maybe<Tuple<>> operator()(Input& input) const {
765
    if (input.atEnd()) {
766
      return Tuple<>();
767 768 769 770 771 772
    } else {
      return nullptr;
    }
  }
};

773 774
constexpr EndOfInput_ endOfInput = EndOfInput_();
// A parser that succeeds only if it is called with no input.
775 776 777 778

}  // namespace parse
}  // namespace kj

779
#endif  // KJ_PARSE_COMMON_H_