flang/lib/Parser/basic-parsers.h

   1 //===-- lib/Parser/basic-parsers.h ------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef FORTRAN_PARSER_BASIC_PARSERS_H_
  10 #define FORTRAN_PARSER_BASIC_PARSERS_H_
  11
  12 // Let a "parser" be an instance of any class that supports this
  13 // type definition and member (or static) function:
  14 //
  15 //   using resultType = ...;
  16 //   std::optional<resultType> Parse(ParseState &) const;
  17 //
  18 // which either returns a value to signify a successful recognition or else
  19 // returns {} to signify failure.  On failure, the state cannot be assumed
  20 // to still be valid, in general -- see below for exceptions.
  21 //
  22 // This header defines the fundamental parser class templates and helper
  23 // template functions.  See parser-combinators.txt for documentation.
  24
  25 #include "flang/Common/Fortran-features.h"
  26 #include "flang/Common/idioms.h"
  27 #include "flang/Common/indirection.h"
  28 #include "flang/Parser/char-block.h"
  29 #include "flang/Parser/message.h"
  30 #include "flang/Parser/parse-state.h"
  31 #include "flang/Parser/provenance.h"
  32 #include "flang/Parser/user-state.h"
  33 #include <cstring>
  34 #include <functional>
  35 #include <list>
  36 #include <memory>
  37 #include <optional>
  38 #include <string>
  39 #include <tuple>
  40 #include <type_traits>
  41 #include <utility>
  42
  43 namespace Fortran::parser {
  44
  45 // fail<A>("..."_err_en_US) returns a parser that never succeeds.  It reports an
  46 // error message at the current position.  The result type is unused,
  47 // but might have to be specified at the point of call to satisfy
  48 // the type checker.  The state remains valid.
  49 template <typename A> class FailParser {
  50 public:
  51   using resultType = A;
  52   constexpr FailParser(const FailParser &) = default;
  53   constexpr explicit FailParser(MessageFixedText t) : text_{t} {}
  54   std::optional<A> Parse(ParseState &state) const {
  55     state.Say(text_);
  56     return std::nullopt;
  57   }
  58
  59 private:
  60   const MessageFixedText text_;
  61 };
  62
  63 template <typename A = Success> inline constexpr auto fail(MessageFixedText t) {
  64   return FailParser<A>{t};
  65 }
  66
  67 // pure(x) returns a parser that always succeeds, does not advance the
  68 // parse, and returns a captured value x whose type must be copy-constructible.
  69 //
  70 // pure<A>() is essentially pure(A{}); it returns a default-constructed A{},
  71 // and works even when A is not copy-constructible.
  72 template <typename A> class PureParser {
  73 public:
  74   using resultType = A;
  75   constexpr PureParser(const PureParser &) = default;
  76   constexpr explicit PureParser(A &&x) : value_(std::move(x)) {}
  77   std::optional<A> Parse(ParseState &) const { return value_; }
  78
  79 private:
  80   const A value_;
  81 };
  82
  83 template <typename A> inline constexpr auto pure(A x) {
  84   return PureParser<A>(std::move(x));
  85 }
  86
  87 template <typename A> class PureDefaultParser {
  88 public:
  89   using resultType = A;
  90   constexpr PureDefaultParser(const PureDefaultParser &) = default;
  91   constexpr PureDefaultParser() {}
  92   std::optional<A> Parse(ParseState &) const { return std::make_optional<A>(); }
  93 };
  94
  95 template <typename A> inline constexpr auto pure() {
  96   return PureDefaultParser<A>();
  97 }
  98
  99 // If a is a parser, attempt(a) is the same parser, but on failure
 100 // the ParseState is guaranteed to have been restored to its initial value.
 101 template <typename A> class BacktrackingParser {
 102 public:
 103   using resultType = typename A::resultType;
 104   constexpr BacktrackingParser(const BacktrackingParser &) = default;
 105   constexpr BacktrackingParser(const A &parser) : parser_{parser} {}
 106   std::optional<resultType> Parse(ParseState &state) const {
 107     Messages messages{std::move(state.messages())};
 108     ParseState backtrack{state};
 109     std::optional<resultType> result{parser_.Parse(state)};
 110     if (result) {
 111       state.messages().Annex(std::move(messages));
 112     } else {
 113       state = std::move(backtrack);
 114       state.messages() = std::move(messages);
 115     }
 116     return result;
 117   }
 118
 119 private:
 120   const A parser_;
 121 };
 122
 123 template <typename A> inline constexpr auto attempt(const A &parser) {
 124   return BacktrackingParser<A>{parser};
 125 }
 126
 127 // For any parser x, the parser returned by !x is one that succeeds when
 128 // x fails, returning a useless (but present) result.  !x fails when x succeeds.
 129 template <typename PA> class NegatedParser {
 130 public:
 131   using resultType = Success;
 132   constexpr NegatedParser(const NegatedParser &) = default;
 133   constexpr NegatedParser(PA p) : parser_{p} {}
 134   std::optional<Success> Parse(ParseState &state) const {
 135     ParseState forked{state};
 136     forked.set_deferMessages(true);
 137     if (parser_.Parse(forked)) {
 138       return std::nullopt;
 139     }
 140     return Success{};
 141   }
 142
 143 private:
 144   const PA parser_;
 145 };
 146
 147 template <typename PA, typename = typename PA::resultType>
 148 constexpr auto operator!(PA p) {
 149   return NegatedParser<PA>(p);
 150 }
 151
 152 // For any parser x, the parser returned by lookAhead(x) is one that succeeds
 153 // or fails if x does, but the state is not modified.
 154 template <typename PA> class LookAheadParser {
 155 public:
 156   using resultType = Success;
 157   constexpr LookAheadParser(const LookAheadParser &) = default;
 158   constexpr LookAheadParser(PA p) : parser_{p} {}
 159   std::optional<Success> Parse(ParseState &state) const {
 160     ParseState forked{state};
 161     forked.set_deferMessages(true);
 162     if (parser_.Parse(forked)) {
 163       return Success{};
 164     }
 165     return std::nullopt;
 166   }
 167
 168 private:
 169   const PA parser_;
 170 };
 171
 172 template <typename PA> inline constexpr auto lookAhead(PA p) {
 173   return LookAheadParser<PA>{p};
 174 }
 175
 176 // If a is a parser, inContext("..."_en_US, a) runs it in a nested message
 177 // context.
 178 template <typename PA> class MessageContextParser {
 179 public:
 180   using resultType = typename PA::resultType;
 181   constexpr MessageContextParser(const MessageContextParser &) = default;
 182   constexpr MessageContextParser(MessageFixedText t, PA p)
 183       : text_{t}, parser_{p} {}
 184   std::optional<resultType> Parse(ParseState &state) const {
 185     state.PushContext(text_);
 186     std::optional<resultType> result{parser_.Parse(state)};
 187     state.PopContext();
 188     return result;
 189   }
 190
 191 private:
 192   const MessageFixedText text_;
 193   const PA parser_;
 194 };
 195
 196 template <typename PA>
 197 inline constexpr auto inContext(MessageFixedText context, PA parser) {
 198   return MessageContextParser{context, parser};
 199 }
 200
 201 // If a is a parser, withMessage("..."_en_US, a) runs it unchanged if it
 202 // succeeds, and overrides its messages with a specific one if it fails and
 203 // has matched no tokens.
 204 template <typename PA> class WithMessageParser {
 205 public:
 206   using resultType = typename PA::resultType;
 207   constexpr WithMessageParser(const WithMessageParser &) = default;
 208   constexpr WithMessageParser(MessageFixedText t, PA p)
 209       : text_{t}, parser_{p} {}
 210   std::optional<resultType> Parse(ParseState &state) const {
 211     if (state.deferMessages()) { // fast path
 212       std::optional<resultType> result{parser_.Parse(state)};
 213       if (!result) {
 214         state.set_anyDeferredMessages();
 215       }
 216       return result;
 217     }
 218     Messages messages{std::move(state.messages())};
 219     bool hadAnyTokenMatched{state.anyTokenMatched()};
 220     state.set_anyTokenMatched(false);
 221     std::optional<resultType> result{parser_.Parse(state)};
 222     bool emitMessage{false};
 223     if (result) {
 224       messages.Annex(std::move(state.messages()));
 225       if (hadAnyTokenMatched) {
 226         state.set_anyTokenMatched();
 227       }
 228     } else if (state.anyTokenMatched()) {
 229       emitMessage = state.messages().empty();
 230       messages.Annex(std::move(state.messages()));
 231     } else {
 232       emitMessage = true;
 233       if (hadAnyTokenMatched) {
 234         state.set_anyTokenMatched();
 235       }
 236     }
 237     state.messages() = std::move(messages);
 238     if (emitMessage) {
 239       state.Say(text_);
 240     }
 241     return result;
 242   }
 243
 244 private:
 245   const MessageFixedText text_;
 246   const PA parser_;
 247 };
 248
 249 template <typename PA>
 250 inline constexpr auto withMessage(MessageFixedText msg, PA parser) {
 251   return WithMessageParser{msg, parser};
 252 }
 253
 254 // If a and b are parsers, then a >> b returns a parser that succeeds when
 255 // b succeeds after a does so, but fails when either a or b does.  The
 256 // result is taken from b.  Similarly, a / b also succeeds if both a and b
 257 // do so, but the result is that returned by a.
 258 template <typename PA, typename PB> class SequenceParser {
 259 public:
 260   using resultType = typename PB::resultType;
 261   constexpr SequenceParser(const SequenceParser &) = default;
 262   constexpr SequenceParser(PA pa, PB pb) : pa_{pa}, pb2_{pb} {}
 263   std::optional<resultType> Parse(ParseState &state) const {
 264     if (pa_.Parse(state)) {
 265       return pb2_.Parse(state);
 266     } else {
 267       return std::nullopt;
 268     }
 269   }
 270
 271 private:
 272   const PA pa_;
 273   const PB pb2_;
 274 };
 275
 276 template <typename PA, typename PB>
 277 inline constexpr auto operator>>(PA pa, PB pb) {
 278   return SequenceParser<PA, PB>{pa, pb};
 279 }
 280
 281 template <typename PA, typename PB> class FollowParser {
 282 public:
 283   using resultType = typename PA::resultType;
 284   constexpr FollowParser(const FollowParser &) = default;
 285   constexpr FollowParser(PA pa, PB pb) : pa_{pa}, pb_{pb} {}
 286   std::optional<resultType> Parse(ParseState &state) const {
 287     if (std::optional<resultType> ax{pa_.Parse(state)}) {
 288       if (pb_.Parse(state)) {
 289         return ax;
 290       }
 291     }
 292     return std::nullopt;
 293   }
 294
 295 private:
 296   const PA pa_;
 297   const PB pb_;
 298 };
 299
 300 template <typename PA, typename PB>
 301 inline constexpr auto operator/(PA pa, PB pb) {
 302   return FollowParser<PA, PB>{pa, pb};
 303 }
 304
 305 template <typename PA, typename... Ps> class AlternativesParser {
 306 public:
 307   using resultType = typename PA::resultType;
 308   constexpr AlternativesParser(PA pa, Ps... ps) : ps_{pa, ps...} {}
 309   constexpr AlternativesParser(const AlternativesParser &) = default;
 310   std::optional<resultType> Parse(ParseState &state) const {
 311     Messages messages{std::move(state.messages())};
 312     ParseState backtrack{state};
 313     std::optional<resultType> result{std::get<0>(ps_).Parse(state)};
 314     if constexpr (sizeof...(Ps) > 0) {
 315       if (!result) {
 316         ParseRest<1>(result, state, backtrack);
 317       }
 318     }
 319     state.messages().Annex(std::move(messages));
 320     return result;
 321   }
 322
 323 private:
 324   template <int J>
 325   void ParseRest(std::optional<resultType> &result, ParseState &state,
 326       ParseState &backtrack) const {
 327     ParseState prevState{std::move(state)};
 328     state = backtrack;
 329     result = std::get<J>(ps_).Parse(state);
 330     if (!result) {
 331       state.CombineFailedParses(std::move(prevState));
 332       if constexpr (J < sizeof...(Ps)) {
 333         ParseRest<J + 1>(result, state, backtrack);
 334       }
 335     }
 336   }
 337
 338   const std::tuple<PA, Ps...> ps_;
 339 };
 340
 341 template <typename... Ps> inline constexpr auto first(Ps... ps) {
 342   return AlternativesParser<Ps...>{ps...};
 343 }
 344
 345 template <typename PA, typename PB>
 346 inline constexpr auto operator||(PA pa, PB pb) {
 347   return AlternativesParser<PA, PB>{pa, pb};
 348 }
 349
 350 // If a and b are parsers, then recovery(a,b) returns a parser that succeeds if
 351 // a does so, or if a fails and b succeeds.  If a succeeds, b is not attempted.
 352 // All messages from the first parse are retained.
 353 // The two parsers must return values of the same type.
 354 template <typename PA, typename PB> class RecoveryParser {
 355 public:
 356   using resultType = typename PA::resultType;
 357   static_assert(std::is_same_v<resultType, typename PB::resultType>);
 358   constexpr RecoveryParser(const RecoveryParser &) = default;
 359   constexpr RecoveryParser(PA pa, PB pb) : pa_{pa}, pb_{pb} {}
 360   std::optional<resultType> Parse(ParseState &state) const {
 361     bool originallyDeferred{state.deferMessages()};
 362     ParseState backtrack{state};
 363     if (!originallyDeferred && state.messages().empty() &&
 364         !state.anyErrorRecovery()) {
 365       // Fast path.  There are no messages or recovered errors in the incoming
 366       // state.  Attempt to parse with messages deferred, expecting that the
 367       // parse will succeed silently.
 368       state.set_deferMessages(true);
 369       if (std::optional<resultType> ax{pa_.Parse(state)}) {
 370         if (!state.anyDeferredMessages() && !state.anyErrorRecovery()) {
 371           state.set_deferMessages(false);
 372           return ax;
 373         }
 374       }
 375       state = backtrack;
 376     }
 377     Messages messages{std::move(state.messages())};
 378     if (std::optional<resultType> ax{pa_.Parse(state)}) {
 379       state.messages().Annex(std::move(messages));
 380       return ax;
 381     }
 382     messages.Annex(std::move(state.messages()));
 383     bool hadDeferredMessages{state.anyDeferredMessages()};
 384     bool anyTokenMatched{state.anyTokenMatched()};
 385     state = std::move(backtrack);
 386     state.set_deferMessages(true);
 387     std::optional<resultType> bx{pb_.Parse(state)};
 388     state.messages() = std::move(messages);
 389     state.set_deferMessages(originallyDeferred);
 390     if (anyTokenMatched) {
 391       state.set_anyTokenMatched();
 392     }
 393     if (hadDeferredMessages) {
 394       state.set_anyDeferredMessages();
 395     }
 396     if (bx) {
 397       // Error recovery situations must also produce messages.
 398       CHECK(state.anyDeferredMessages() || state.messages().AnyFatalError());
 399       state.set_anyErrorRecovery();
 400     }
 401     return bx;
 402   }
 403
 404 private:
 405   const PA pa_;
 406   const PB pb_;
 407 };
 408
 409 template <typename PA, typename PB>
 410 inline constexpr auto recovery(PA pa, PB pb) {
 411   return RecoveryParser<PA, PB>{pa, pb};
 412 }
 413
 414 // If x is a parser, then many(x) returns a parser that always succeeds
 415 // and whose value is a list, possibly empty, of the values returned from
 416 // repeated application of x until it fails or does not advance the parse.
 417 template <typename PA> class ManyParser {
 418   using paType = typename PA::resultType;
 419
 420 public:
 421   using resultType = std::list<paType>;
 422   constexpr ManyParser(const ManyParser &) = default;
 423   constexpr ManyParser(PA parser) : parser_{parser} {}
 424   std::optional<resultType> Parse(ParseState &state) const {
 425     resultType result;
 426     auto at{state.GetLocation()};
 427     while (std::optional<paType> x{parser_.Parse(state)}) {
 428       result.emplace_back(std::move(*x));
 429       if (state.GetLocation() <= at) {
 430         break; // no forward progress, don't loop
 431       }
 432       at = state.GetLocation();
 433     }
 434     return {std::move(result)};
 435   }
 436
 437 private:
 438   const BacktrackingParser<PA> parser_;
 439 };
 440
 441 template <typename PA> inline constexpr auto many(PA parser) {
 442   return ManyParser<PA>{parser};
 443 }
 444
 445 // If x is a parser, then some(x) returns a parser that succeeds if x does
 446 // and whose value is a nonempty list of the values returned from repeated
 447 // application of x until it fails or does not advance the parse.  In other
 448 // words, some(x) is a variant of many(x) that has to succeed at least once.
 449 template <typename PA> class SomeParser {
 450   using paType = typename PA::resultType;
 451
 452 public:
 453   using resultType = std::list<paType>;
 454   constexpr SomeParser(const SomeParser &) = default;
 455   constexpr SomeParser(PA parser) : parser_{parser} {}
 456   std::optional<resultType> Parse(ParseState &state) const {
 457     auto start{state.GetLocation()};
 458     if (std::optional<paType> first{parser_.Parse(state)}) {
 459       resultType result;
 460       result.emplace_back(std::move(*first));
 461       if (state.GetLocation() > start) {
 462         result.splice(result.end(), many(parser_).Parse(state).value());
 463       }
 464       return {std::move(result)};
 465     }
 466     return std::nullopt;
 467   }
 468
 469 private:
 470   const PA parser_;
 471 };
 472
 473 template <typename PA> inline constexpr auto some(PA parser) {
 474   return SomeParser<PA>{parser};
 475 }
 476
 477 // If x is a parser, skipMany(x) is equivalent to many(x) but with no result.
 478 template <typename PA> class SkipManyParser {
 479 public:
 480   using resultType = Success;
 481   constexpr SkipManyParser(const SkipManyParser &) = default;
 482   constexpr SkipManyParser(PA parser) : parser_{parser} {}
 483   std::optional<Success> Parse(ParseState &state) const {
 484     for (auto at{state.GetLocation()};
 485          parser_.Parse(state) && state.GetLocation() > at;
 486          at = state.GetLocation()) {
 487     }
 488     return Success{};
 489   }
 490
 491 private:
 492   const BacktrackingParser<PA> parser_;
 493 };
 494
 495 template <typename PA> inline constexpr auto skipMany(PA parser) {
 496   return SkipManyParser<PA>{parser};
 497 }
 498
 499 // If x is a parser, skipManyFast(x) is equivalent to skipMany(x).
 500 // The parser x must always advance on success and never invalidate the
 501 // state on failure.
 502 template <typename PA> class SkipManyFastParser {
 503 public:
 504   using resultType = Success;
 505   constexpr SkipManyFastParser(const SkipManyFastParser &) = default;
 506   constexpr SkipManyFastParser(PA parser) : parser_{parser} {}
 507   std::optional<Success> Parse(ParseState &state) const {
 508     while (parser_.Parse(state)) {
 509     }
 510     return Success{};
 511   }
 512
 513 private:
 514   const PA parser_;
 515 };
 516
 517 template <typename PA> inline constexpr auto skipManyFast(PA parser) {
 518   return SkipManyFastParser<PA>{parser};
 519 }
 520
 521 // If x is a parser returning some type A, then maybe(x) returns a
 522 // parser that returns std::optional<A>, always succeeding.
 523 template <typename PA> class MaybeParser {
 524   using paType = typename PA::resultType;
 525
 526 public:
 527   using resultType = std::optional<paType>;
 528   constexpr MaybeParser(const MaybeParser &) = default;
 529   constexpr MaybeParser(PA parser) : parser_{parser} {}
 530   std::optional<resultType> Parse(ParseState &state) const {
 531     if (resultType result{parser_.Parse(state)}) {
 532       // permit optional<optional<...>>
 533       return {std::move(result)};
 534     }
 535     return resultType{};
 536   }
 537
 538 private:
 539   const BacktrackingParser<PA> parser_;
 540 };
 541
 542 template <typename PA> inline constexpr auto maybe(PA parser) {
 543   return MaybeParser<PA>{parser};
 544 }
 545
 546 // If x is a parser, then defaulted(x) returns a parser that always
 547 // succeeds.  When x succeeds, its result is that of x; otherwise, its
 548 // result is a default-constructed value of x's result type.
 549 template <typename PA> class DefaultedParser {
 550 public:
 551   using resultType = typename PA::resultType;
 552   constexpr DefaultedParser(const DefaultedParser &) = default;
 553   constexpr DefaultedParser(PA p) : parser_{p} {}
 554   std::optional<resultType> Parse(ParseState &state) const {
 555     std::optional<std::optional<resultType>> ax{maybe(parser_).Parse(state)};
 556     if (ax.value()) { // maybe() always succeeds
 557       return std::move(*ax);
 558     }
 559     return resultType{};
 560   }
 561
 562 private:
 563   const BacktrackingParser<PA> parser_;
 564 };
 565
 566 template <typename PA> inline constexpr auto defaulted(PA p) {
 567   return DefaultedParser<PA>(p);
 568 }
 569
 570 // If a is a parser, and f is a function mapping an rvalue of a's result type
 571 // to some other type T, then applyFunction(f, a) returns a parser that succeeds
 572 // iff a does, and whose result value ax has been passed through the function;
 573 // the final result is that returned by the call f(std::move(ax)).
 574 //
 575 // Function application is generalized to functions with more than one
 576 // argument with applyFunction(f, a, b, ...) succeeding if all of the parsers
 577 // a, b, &c. do so, and the result is the value of applying f to their
 578 // results.
 579 //
 580 // applyLambda(f, ...) is the same concept extended to std::function<> functors.
 581 // It is not constexpr.
 582 //
 583 // Member function application is supported by applyMem(f, a).  If the
 584 // parser a succeeds and returns some value ax, the result is that returned
 585 // by ax.f().  Additional parser arguments can be specified to supply their
 586 // results to the member function call, so applyMem(f, a, b) succeeds if
 587 // both a and b do so and returns the result of calling ax.f(std::move(bx)).
 588
 589 // Runs a sequence of parsers until one fails or all have succeeded.
 590 // Collects their results in a std::tuple<std::optional<>...>.
 591 template <typename... PARSER>
 592 using ApplyArgs = std::tuple<std::optional<typename PARSER::resultType>...>;
 593
 594 template <typename... PARSER, std::size_t... J>
 595 inline bool ApplyHelperArgs(const std::tuple<PARSER...> &parsers,
 596     ApplyArgs<PARSER...> &args, ParseState &state, std::index_sequence<J...>) {
 597   return (... &&
 598       (std::get<J>(args) = std::get<J>(parsers).Parse(state),
 599           std::get<J>(args).has_value()));
 600 }
 601
 602 // Applies a function to the arguments collected by ApplyHelperArgs.
 603 template <typename RESULT, typename... PARSER>
 604 using ApplicableFunctionPointer = RESULT (*)(typename PARSER::resultType &&...);
 605 template <typename RESULT, typename... PARSER>
 606 using ApplicableFunctionObject =
 607     const std::function<RESULT(typename PARSER::resultType &&...)> &;
 608
 609 template <template <typename...> class FUNCTION, typename RESULT,
 610     typename... PARSER, std::size_t... J>
 611 inline RESULT ApplyHelperFunction(FUNCTION<RESULT, PARSER...> f,
 612     ApplyArgs<PARSER...> &&args, std::index_sequence<J...>) {
 613   return f(std::move(*std::get<J>(args))...);
 614 }
 615
 616 template <template <typename...> class FUNCTION, typename RESULT,
 617     typename... PARSER>
 618 class ApplyFunction {
 619   using funcType = FUNCTION<RESULT, PARSER...>;
 620
 621 public:
 622   using resultType = RESULT;
 623   constexpr ApplyFunction(const ApplyFunction &) = default;
 624   constexpr ApplyFunction(funcType f, PARSER... p)
 625       : function_{f}, parsers_{p...} {}
 626   std::optional<resultType> Parse(ParseState &state) const {
 627     ApplyArgs<PARSER...> results;
 628     using Sequence = std::index_sequence_for<PARSER...>;
 629     if (ApplyHelperArgs(parsers_, results, state, Sequence{})) {
 630       return ApplyHelperFunction<FUNCTION, RESULT, PARSER...>(
 631           function_, std::move(results), Sequence{});
 632     } else {
 633       return std::nullopt;
 634     }
 635   }
 636
 637 private:
 638   const funcType function_;
 639   const std::tuple<PARSER...> parsers_;
 640 };
 641
 642 template <typename RESULT, typename... PARSER>
 643 inline constexpr auto applyFunction(
 644     ApplicableFunctionPointer<RESULT, PARSER...> f, const PARSER &...parser) {
 645   return ApplyFunction<ApplicableFunctionPointer, RESULT, PARSER...>{
 646       f, parser...};
 647 }
 648
 649 template <typename RESULT, typename... PARSER>
 650 inline /* not constexpr */ auto applyLambda(
 651     ApplicableFunctionObject<RESULT, PARSER...> f, const PARSER &...parser) {
 652   return ApplyFunction<ApplicableFunctionObject, RESULT, PARSER...>{
 653       f, parser...};
 654 }
 655
 656 // Member function application
 657 template <typename OBJPARSER, typename... PARSER> class AMFPHelper {
 658   using resultType = typename OBJPARSER::resultType;
 659
 660 public:
 661   using type = void (resultType::*)(typename PARSER::resultType &&...);
 662 };
 663 template <typename OBJPARSER, typename... PARSER>
 664 using ApplicableMemberFunctionPointer =
 665     typename AMFPHelper<OBJPARSER, PARSER...>::type;
 666
 667 template <typename OBJPARSER, typename... PARSER, std::size_t... J>
 668 inline auto ApplyHelperMember(
 669     ApplicableMemberFunctionPointer<OBJPARSER, PARSER...> mfp,
 670     ApplyArgs<OBJPARSER, PARSER...> &&args, std::index_sequence<J...>) ->
 671     typename OBJPARSER::resultType {
 672   ((*std::get<0>(args)).*mfp)(std::move(*std::get<J + 1>(args))...);
 673   return std::get<0>(std::move(args));
 674 }
 675
 676 template <typename OBJPARSER, typename... PARSER> class ApplyMemberFunction {
 677   using funcType = ApplicableMemberFunctionPointer<OBJPARSER, PARSER...>;
 678
 679 public:
 680   using resultType = typename OBJPARSER::resultType;
 681   constexpr ApplyMemberFunction(const ApplyMemberFunction &) = default;
 682   constexpr ApplyMemberFunction(funcType f, OBJPARSER o, PARSER... p)
 683       : function_{f}, parsers_{o, p...} {}
 684   std::optional<resultType> Parse(ParseState &state) const {
 685     ApplyArgs<OBJPARSER, PARSER...> results;
 686     using Sequence1 = std::index_sequence_for<OBJPARSER, PARSER...>;
 687     using Sequence2 = std::index_sequence_for<PARSER...>;
 688     if (ApplyHelperArgs(parsers_, results, state, Sequence1{})) {
 689       return ApplyHelperMember<OBJPARSER, PARSER...>(
 690           function_, std::move(results), Sequence2{});
 691     } else {
 692       return std::nullopt;
 693     }
 694   }
 695
 696 private:
 697   const funcType function_;
 698   const std::tuple<OBJPARSER, PARSER...> parsers_;
 699 };
 700
 701 template <typename OBJPARSER, typename... PARSER>
 702 inline constexpr auto applyMem(
 703     ApplicableMemberFunctionPointer<OBJPARSER, PARSER...> mfp,
 704     const OBJPARSER &objParser, PARSER... parser) {
 705   return ApplyMemberFunction<OBJPARSER, PARSER...>{mfp, objParser, parser...};
 706 }
 707
 708 // As is done with function application via applyFunction() above, class
 709 // instance construction can also be based upon the results of successful
 710 // parses.  For some type T and zero or more parsers a, b, &c., the call
 711 // construct<T>(a, b, ...) returns a parser that succeeds if all of
 712 // its argument parsers do so in succession, and whose result is an
 713 // instance of T constructed upon the values they returned.
 714 // With a single argument that is a parser with no usable value,
 715 // construct<T>(p) invokes T's default nullary constructor (T(){}).
 716 // (This means that "construct<T>(Foo >> Bar >> ok)" is functionally
 717 // equivalent to "Foo >> Bar >> construct<T>()", but I'd like to hold open
 718 // the opportunity to make construct<> capture source provenance all of the
 719 // time, and the first form will then lead to better error positioning.)
 720
 721 template <typename RESULT, typename... PARSER, std::size_t... J>
 722 inline RESULT ApplyHelperConstructor(
 723     ApplyArgs<PARSER...> &&args, std::index_sequence<J...>) {
 724   return RESULT{std::move(*std::get<J>(args))...};
 725 }
 726
 727 template <typename RESULT, typename... PARSER> class ApplyConstructor {
 728 public:
 729   using resultType = RESULT;
 730   constexpr ApplyConstructor(const ApplyConstructor &) = default;
 731   constexpr explicit ApplyConstructor(PARSER... p) : parsers_{p...} {}
 732   std::optional<resultType> Parse(ParseState &state) const {
 733     if constexpr (sizeof...(PARSER) == 0) {
 734       return RESULT{};
 735     } else {
 736       if constexpr (sizeof...(PARSER) == 1) {
 737         return ParseOne(state);
 738       } else {
 739         ApplyArgs<PARSER...> results;
 740         using Sequence = std::index_sequence_for<PARSER...>;
 741         if (ApplyHelperArgs(parsers_, results, state, Sequence{})) {
 742           return ApplyHelperConstructor<RESULT, PARSER...>(
 743               std::move(results), Sequence{});
 744         }
 745       }
 746       return std::nullopt;
 747     }
 748   }
 749
 750 private:
 751   std::optional<resultType> ParseOne(ParseState &state) const {
 752     if constexpr (std::is_same_v<Success, typename PARSER::resultType...>) {
 753       if (std::get<0>(parsers_).Parse(state)) {
 754         return RESULT{};
 755       }
 756     } else if (auto arg{std::get<0>(parsers_).Parse(state)}) {
 757       return RESULT{std::move(*arg)};
 758     }
 759     return std::nullopt;
 760   }
 761
 762   const std::tuple<PARSER...> parsers_;
 763 };
 764
 765 template <typename RESULT, typename... PARSER>
 766 inline constexpr auto construct(PARSER... p) {
 767   return ApplyConstructor<RESULT, PARSER...>{p...};
 768 }
 769
 770 // For a parser p, indirect(p) returns a parser that builds an indirect
 771 // reference to p's return type.
 772 template <typename PA> inline constexpr auto indirect(PA p) {
 773   return construct<common::Indirection<typename PA::resultType>>(p);
 774 }
 775
 776 // If a and b are parsers, then nonemptySeparated(a, b) returns a parser
 777 // that succeeds if a does.  If a succeeds, it then applies many(b >> a).
 778 // The result is the list of the values returned from all of the applications
 779 // of a.
 780 template <typename T>
 781 common::IfNoLvalue<std::list<T>, T> prepend(T &&head, std::list<T> &&rest) {
 782   rest.push_front(std::move(head));
 783   return std::move(rest);
 784 }
 785
 786 template <typename PA, typename PB> class NonemptySeparated {
 787 private:
 788   using paType = typename PA::resultType;
 789
 790 public:
 791   using resultType = std::list<paType>;
 792   constexpr NonemptySeparated(const NonemptySeparated &) = default;
 793   constexpr NonemptySeparated(PA p, PB sep) : parser_{p}, separator_{sep} {}
 794   std::optional<resultType> Parse(ParseState &state) const {
 795     return applyFunction<std::list<paType>>(
 796         prepend<paType>, parser_, many(separator_ >> parser_))
 797         .Parse(state);
 798   }
 799
 800 private:
 801   const PA parser_;
 802   const PB separator_;
 803 };
 804
 805 template <typename PA, typename PB>
 806 inline constexpr auto nonemptySeparated(PA p, PB sep) {
 807   return NonemptySeparated<PA, PB>{p, sep};
 808 }
 809
 810 // ok is a parser that always succeeds.  It is useful when a parser
 811 // must discard its result in order to be compatible in type with other
 812 // parsers in an alternative, e.g. "x >> ok || y >> ok" is type-safe even
 813 // when x and y have distinct result types.
 814 struct OkParser {
 815   using resultType = Success;
 816   constexpr OkParser() {}
 817   static constexpr std::optional<Success> Parse(ParseState &) {
 818     return Success{};
 819   }
 820 };
 821 constexpr OkParser ok;
 822
 823 // A variant of recovery() above for convenience.
 824 template <typename PA, typename PB>
 825 inline constexpr auto localRecovery(MessageFixedText msg, PA pa, PB pb) {
 826   return recovery(withMessage(msg, pa), pb >> pure<typename PA::resultType>());
 827 }
 828
 829 // nextCh is a parser that succeeds if the parsing state is not
 830 // at the end of its input, returning the next character location and
 831 // advancing the parse when it does so.
 832 struct NextCh {
 833   using resultType = const char *;
 834   constexpr NextCh() {}
 835   std::optional<const char *> Parse(ParseState &state) const {
 836     if (std::optional<const char *> result{state.GetNextChar()}) {
 837       return result;
 838     }
 839     state.Say("end of file"_err_en_US);
 840     return std::nullopt;
 841   }
 842 };
 843
 844 constexpr NextCh nextCh;
 845
 846 // If a is a parser for some nonstandard language feature LF, extension<LF>(a)
 847 // is a parser that optionally enabled, sets a strict conformance violation
 848 // flag, and may emit a warning message, if those are enabled.
 849 template <LanguageFeature LF, typename PA> class NonstandardParser {
 850 public:
 851   using resultType = typename PA::resultType;
 852   constexpr NonstandardParser(const NonstandardParser &) = default;
 853   constexpr NonstandardParser(PA parser, MessageFixedText msg)
 854       : parser_{parser}, message_{msg} {}
 855   std::optional<resultType> Parse(ParseState &state) const {
 856     if (UserState * ustate{state.userState()}) {
 857       if (!ustate->features().IsEnabled(LF)) {
 858         return std::nullopt;
 859       }
 860     }
 861     auto at{state.GetLocation()};
 862     auto result{parser_.Parse(state)};
 863     if (result) {
 864       state.Nonstandard(
 865           CharBlock{at, std::max(state.GetLocation(), at + 1)}, LF, message_);
 866     }
 867     return result;
 868   }
 869
 870 private:
 871   const PA parser_;
 872   const MessageFixedText message_;
 873 };
 874
 875 template <LanguageFeature LF, typename PA>
 876 inline constexpr auto extension(MessageFixedText feature, PA parser) {
 877   return NonstandardParser<LF, PA>(parser, feature);
 878 }
 879
 880 // If a is a parser for some deprecated or deleted language feature LF,
 881 // deprecated<LF>(a) is a parser that is optionally enabled, sets a strict
 882 // conformance violation flag, and may emit a warning message, if enabled.
 883 template <LanguageFeature LF, typename PA> class DeprecatedParser {
 884 public:
 885   using resultType = typename PA::resultType;
 886   constexpr DeprecatedParser(const DeprecatedParser &) = default;
 887   constexpr DeprecatedParser(PA parser) : parser_{parser} {}
 888   std::optional<resultType> Parse(ParseState &state) const {
 889     if (UserState * ustate{state.userState()}) {
 890       if (!ustate->features().IsEnabled(LF)) {
 891         return std::nullopt;
 892       }
 893     }
 894     auto at{state.GetLocation()};
 895     auto result{parser_.Parse(state)};
 896     if (result) {
 897       state.Nonstandard(CharBlock{at, state.GetLocation()}, LF,
 898           "deprecated usage"_port_en_US);
 899     }
 900     return result;
 901   }
 902
 903 private:
 904   const PA parser_;
 905 };
 906
 907 template <LanguageFeature LF, typename PA>
 908 inline constexpr auto deprecated(PA parser) {
 909   return DeprecatedParser<LF, PA>(parser);
 910 }
 911
 912 // Parsing objects with "source" members.
 913 template <typename PA> class SourcedParser {
 914 public:
 915   using resultType = typename PA::resultType;
 916   constexpr SourcedParser(const SourcedParser &) = default;
 917   constexpr SourcedParser(PA parser) : parser_{parser} {}
 918   std::optional<resultType> Parse(ParseState &state) const {
 919     const char *start{state.GetLocation()};
 920     auto result{parser_.Parse(state)};
 921     if (result) {
 922       const char *end{state.GetLocation()};
 923       for (; start < end && start[0] == ' '; ++start) {
 924       }
 925       for (; start < end && end[-1] == ' '; --end) {
 926       }
 927       result->source = CharBlock{start, end};
 928     }
 929     return result;
 930   }
 931
 932 private:
 933   const PA parser_;
 934 };
 935
 936 template <typename PA> inline constexpr auto sourced(PA parser) {
 937   return SourcedParser<PA>{parser};
 938 }
 939 } // namespace Fortran::parser
 940 #endif // FORTRAN_PARSER_BASIC_PARSERS_H_