class Parser<A> {
 final _ParseFunction _run;

 Parser(ParseResult<A> f(String s, Position pos)) : this._run = f;

 ParseResult run(String s, [Position pos = const Position(0, 1, 1)]) =>
     _run(s, pos);

 A parse(String s) {
   ParseResult<A> result = run(s);
   if (result.isSuccess) return result.value;
   else throw result.errorMessage;
 }

 /// Monadic bind.
 Parser operator >>(Parser g(A x)) {
   return new Parser((text, pos) {
     ParseResult res = _run(text, pos);
     if (res.isSuccess) {
       final res2 = g(res.value)._run(text, res.position);
       return res2.copy(
           expectations: res.expectations.best(res2.expectations),
           isCommitted: res.isCommitted || res2.isCommitted);
     } else {
       return res;
     }
   });
 }

 Parser expecting(String expected) {
   return new Parser((s, pos) {
     final res = _run(s, pos);
     return res.copy(expectations: _singleExpectation(expected, pos));
   });
 }

 Parser get committed {
   return new Parser((s, pos) {
     final res = _run(s, pos);
     return res.copy(isCommitted: true);
   });
 }

 /// Alias for [:expecting:].
 Parser<A> operator %(String expected) => this.expecting(expected);

 /// Applicative <*>
 Parser operator *(Parser p) => this >> (f) => p >> (x) {
   Function ff = f;
   return success(ff(x));
 };

 /// Applicative *>
 Parser operator >(Parser p) => this >> (_) => p;

 /// Applicative <*
 Parser<A> operator <(Parser p) => this >> ((x) => p > success(x));

 /// Functor map
 Parser map(Object f(A x)) => success(f) * this;

 /// Infix syntax for map
 Parser operator ^(Object f(A x)) => map(f);

 /// Parser sequencing: creates a parser accumulator.
 ParserAccumulator2 operator +(Parser p) => new ParserAccumulator2(this, p);

 /// Alternative
 Parser operator |(Parser p) {
   return new Parser((s, pos) {
     ParseResult<A> res = _run(s, pos);
     if (res.isSuccess || res.isCommitted) {
       return res;
     } else {
       ParseResult res2 = p._run(s, pos);
       return res2.copy(
           expectations: res.expectations.best(res2.expectations));
     }
   });
 }

 /**
  * Parses without consuming any input.
  *
  * Used for defining followedBy, which is probably what you're looking for.
  */
 Parser<A> get lookAhead {
   return new Parser((s, pos) {
     ParseResult res = _run(s, pos);
     return res.isSuccess
         ? _success(res.value, s, pos)
         : res;
   });
 }

 /**
  * Succeeds if and only if [this] succeeds and [p] succeeds on what remains to
  * parse without cosuming it.
  *
  *     string("let").followedBy(space)
  */
 Parser<A> followedBy(Parser p) => this < p.lookAhead;

 /**
  * Fails if and only if [this] succeeds on what's ahead.
  *
  * Used for defining notFollowedBy, which is probably what you're looking for.
  */
 Parser get notAhead {
   return new Parser((s, pos) {
     ParseResult res = _run(s, pos);
     return res.isSuccess
         ? _failure(s, pos)
         : _success(null, s, pos);
   });
 }

 /**
  * Succeeds if and only if [this] succeeds and [p] fails on what remains to
  * parse.
  *
  *     string("let").notFollowedBy(alphanum)
  */
 Parser<A> notFollowedBy(Parser p) => this < p.notAhead;

 /**
  * Parses [this] 0 or more times until [end] succeeds.
  *
  * Returns the list of values returned by [this]. It is useful for parsing
  * comments.
  *
  *     string('/*') > anyChar.manyUntil(string('*/'))
  *
  * The input parsed by [end] is consumed. Use [:end.lookAhead:] if you don't
  * want this.
  */
 Parser<List<A>> manyUntil(Parser end) {
   // Imperative version to avoid stack overflows.
   return new Parser((s, pos) {
     List res = [];
     Position index = pos;
     var exps = _emptyExpectation(pos);
     bool committed = false;
     while(true) {
       final endRes = end._run(s, index);
       exps = exps.best(endRes.expectations);
       if (endRes.isSuccess) {
         return endRes.copy(value: res, expectations: exps,
                            isCommitted: committed);
       } else if (!endRes.isCommitted) {
         final xRes = this._run(s, index);
         exps = exps.best(xRes.expectations);
         committed = committed || xRes.isCommitted;
         if (xRes.isSuccess) {
           res.add(xRes.value);
           index = xRes.position;
         } else {
           return xRes.copy(expectations: exps, isCommitted: committed);
         }
       } else {
         return endRes.copy(expectations: exps, isCommitted: committed);
       }
     }
   });
 }

 /**
  * Parses [this] 0 or more times until [end] succeeds and discards the result.
  *
  * Equivalent to [:this.manyUntil(end) > success(null):] but faster. The input
  * parsed by [end] is consumed. Use [:end.lookAhead:] if you don't want this.
  */
 Parser skipManyUntil(Parser end) {
   // Imperative version to avoid stack overflows.
   return new Parser((s, pos) {
     Position index = pos;
     var exps = _emptyExpectation(pos);
     var commit = false;
     while(true) {
       final endRes = end._run(s, index);
       exps = exps.best(endRes.expectations);
       commit = commit || endRes.isCommitted;
       if (endRes.isSuccess) {
         return endRes.copy(value: null, expectations: exps,
                            isCommitted: commit);
       } else if (!endRes.isCommitted) {
         final xRes = this._run(s, index);
         exps = exps.best(xRes.expectations);
         commit = commit || xRes.isCommitted;
         if (xRes.isSuccess) {
           index = xRes.position;
         } else {
           return xRes.copy(expectations: exps, isCommitted: commit);
         }
       } else {
         return endRes.copy(expectations: exps);
       }
     }
   });
 }

 // Derived combinators, defined here for infix notation

 Parser<A> orElse(A value) => this | success(value);

 Parser<Option<A>> get maybe => this.map(_some).orElse(_none);

 // Imperative version to avoid stack overflows.
 Parser<List<A>> _many(List<A> acc()) {
   return new Parser((s, pos) {
     final res = acc();
     var exps = _emptyExpectation(pos);
     Position index = pos;
     bool committed = false;
     while(true) {
       ParseResult<A> o = this._run(s, index);
       exps = exps.best(o.expectations);
       committed = committed || o.isCommitted;
       if (o.isSuccess) {
         res.add(o.value);
         index = o.position;
       } else if (o.isCommitted) {
         return o.copy(expectations: exps);
       } else {
         return _success(res, s, index, exps, committed);
       }
     }
   });
 }

 Parser<List<A>> get many => _many(() => []);

 Parser<List<A>> get many1 => this >> (x) => _many(() => [x]);

 /**
  * Parses [this] zero or more time, skipping its result.
  *
  * Equivalent to [:this.many > success(null):] but more efficient.
  */
 Parser get skipMany {
   // Imperative version to avoid stack overflows.
   return new Parser((s, pos) {
     Position index = pos;
     var exps = _emptyExpectation(pos);
     bool committed = false;
     while(true) {
       ParseResult<A> o = this._run(s, index);
       exps = exps.best(o.expectations);
       committed = committed || o.isCommitted;
       if (o.isSuccess) {
         index = o.position;
       } else if (o.isCommitted) {
         return o.copy(expectations: exps);
       } else {
         return _success(null, s, index, exps, committed);
       }
     }
   });
 }

 /**
  * Parses [this] one or more time, skipping its result.
  *
  * Equivalent to [:this.many1 > success(null):] but more efficient.
  */
 Parser get skipMany1 => this > this.skipMany;

 Parser<List<A>> sepBy(Parser sep) => sepBy1(sep).orElse([]);

 Parser<List<A>> sepBy1(Parser sep) =>
     this >> (x) => (sep > this)._many(() => [x]);

 Parser<List<A>> endBy(Parser sep) => (this < sep).many;

 Parser<List<A>> endBy1(Parser sep) => (this < sep).many1;

 /**
  * Parses zero or more occurences of [this] separated and optionally ended
  * by [sep].
  */
 Parser<List<A>> sepEndBy(Parser sep) => sepEndBy1(sep).orElse([]);

 /**
  * Parses one or more occurences of [this] separated and optionally ended
  * by [sep].
  */
 Parser<List<A>> sepEndBy1(Parser sep) => sepBy1(sep) < sep.maybe;

 Parser chainl(Parser sep, defaultValue) =>
     chainl1(sep) | success(defaultValue);

 Parser chainl1(Parser sep) {
   rest(acc) {
     return new Parser((s, pos) {
       Position index = pos;
       var exps = _emptyExpectation(pos);
       var commit = false;
       while(true) {
         combine(f) => (x) => f(acc, x);
         final res = (success(combine) * sep * this)._run(s, index);
         exps = exps.best(res.expectations);
         commit = commit || res.isCommitted;
         if (res.isSuccess) {
           acc = res.value;
           index = res.position;
         } else if (res.isCommitted) {
           return res.copy(expectations: exps);
         } else {
           return _success(acc, s, index, exps, commit);
         }
       }
     });
   }
   return this >> rest;
 }

 /// Warning: may lead to stack overflows.
 Parser chainr(Parser sep, defaultValue) =>
     chainr1(sep) | success(defaultValue);

 /// Warning: may lead to stack overflows.
 Parser chainr1(Parser sep) {
   rest(x) => success((f) => (y) => f(x, y)) * sep * chainr1(sep)
            | success(x);
   return this >> rest;
 }

 Parser<A> between(Parser left, Parser right) => left > (this < right);

 /// Returns the substring consumed by [this].
 Parser<String> get record {
   return new Parser((s, pos) {
       final result = run(s, pos);
       if (result.isSuccess) {
         return result.copy(
             value: s.substring(pos.offset, result.position.offset));
       } else {
         return result;
       }
   });
 }

 /**
  * Returns the value parsed by [this] along with the position at which it
  * has been parsed.
  */
 Parser<PointedValue<A>> get withPosition {
   return new Parser((s, pos) {
     return this.map((v) => new PointedValue(v, pos))._run(s, pos);
   });
 }
}