Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/parse/common.h @ 69:33d812a61356

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