/* sbt -- Simple Build Tool
 * Copyright 2008, 2010, 2011  Mark Harrah
 */
package sbt.complete

	import Parser._
	import sbt.Types.{left, right, some}
	import sbt.Util.{makeList,separate}

/** A String parser that provides semi-automatic tab completion.
* A successful parse results in a value of type `T`.
* The methods in this trait are what must be implemented to define a new Parser implementation, but are not typically useful for common usage.
* Instead, most useful methods for combining smaller parsers into larger parsers are implicitly added by the [[RichParser]] type.
*/
sealed trait Parser[+T]
{
	def derive(i: Char): Parser[T]
	def resultEmpty: Result[T]
	def result: Option[T]
	def completions(level: Int): Completions
	def failure: Option[Failure]
	def isTokenStart = false
	def ifValid[S](p: => Parser[S]): Parser[S]
	def valid: Boolean
}
sealed trait RichParser[A]
{
	/** Apply the original Parser and then apply `next` (in order).  The result of both is provides as a pair. */
	def ~[B](next: Parser[B]): Parser[(A,B)]

	/** Apply the original Parser one or more times and provide the non-empty sequence of results.*/
	def + : Parser[Seq[A]]

	/** Apply the original Parser zero or more times and provide the (potentially empty) sequence of results.*/
	def * : Parser[Seq[A]]

	/** Apply the original Parser zero or one times, returning None if it was applied zero times or the result wrapped in Some if it was applied once.*/
	def ? : Parser[Option[A]]

	/** Apply either the original Parser or `b`.*/
	def |[B >: A](b: Parser[B]): Parser[B]

	/** Apply either the original Parser or `b`.*/
	def ||[B](b: Parser[B]): Parser[Either[A,B]]

	/** Apply the original Parser to the input and then apply `f` to the result.*/
	def map[B](f: A => B): Parser[B]

	/** Returns the original parser.  This is useful for converting literals to Parsers.
	* For example, `'c'.id` or `"asdf".id`*/
	def id: Parser[A]

	/** Apply the original Parser, but provide `value` as the result if it succeeds. */
	def ^^^[B](value: B): Parser[B]

	/** Apply the original Parser, but provide `alt` as the result if it fails.*/
	def ??[B >: A](alt: B): Parser[B]

	/** Produces a Parser that applies the original Parser and then applies `next` (in order), discarding the result of `next`.
	* (The arrow point in the direction of the retained result.)*/
	def <~[B](b: Parser[B]): Parser[A]

	/** Produces a Parser that applies the original Parser and then applies `next` (in order), discarding the result of the original parser.
	* (The arrow point in the direction of the retained result.)*/
	def ~>[B](b: Parser[B]): Parser[B]

	/** Uses the specified message if the original Parser fails.*/
	def !!!(msg: String): Parser[A]

	/** If an exception is thrown by the original Parser,
	* capture it and fail locally instead of allowing the exception to propagate up and terminate parsing.*/
	def failOnException: Parser[A]

	@deprecated("Use `not` and explicitly provide the failure message", "0.12.2")
	def unary_- : Parser[Unit]

	/** Apply the original parser, but only succeed if `o` also succeeds.
	* Note that `o` does not need to consume the same amount of input to satisfy this condition.*/
	def & (o: Parser[_]): Parser[A]

	@deprecated("Use `and` and `not` and explicitly provide the failure message", "0.12.2")
	def - (o: Parser[_]): Parser[A]

	/** Explicitly defines the completions for the original Parser.*/
	def examples(s: String*): Parser[A]

	/** Explicitly defines the completions for the original Parser.*/
	def examples(s: Set[String], check: Boolean = false): Parser[A]

	/**
	 * @param exampleSource the source of examples when displaying completions to the user.
	 * @param maxNumberOfExamples limits the number of examples that the source of examples should return. This can
	 *                            prevent lengthy pauses and avoids bad interactive user experience.
	 * @param removeInvalidExamples indicates whether completion examples should be checked for validity (against the
	 *                              given parser). Invalid examples will be filtered out and only valid suggestions will
	 *                              be displayed.
	 * @return a new parser with a new source of completions.
	 */
	def examples(exampleSource: ExampleSource, maxNumberOfExamples: Int, removeInvalidExamples: Boolean): Parser[A]

	/**
	 * @param exampleSource the source of examples when displaying completions to the user.
	 * @return a new parser with a new source of completions. It displays at most 25 completion examples and does not
	 *         remove invalid examples.
	 */
	def examples(exampleSource: ExampleSource): Parser[A] = examples(exampleSource, maxNumberOfExamples = 25, removeInvalidExamples = false)

	/** Converts a Parser returning a Char sequence to a Parser returning a String.*/
	def string(implicit ev: A <:< Seq[Char]): Parser[String]

	/** Produces a Parser that filters the original parser.
	* If 'f' is not true when applied to the output of the original parser, the Parser returned by this method fails.
	* The failure message is constructed by applying `msg` to the String that was successfully parsed by the original parser. */
	def filter(f: A => Boolean, msg: String => String): Parser[A]

	/** Applies the original parser, applies `f` to the result to get the next parser, and applies that parser and uses its result for the overall result. */
	def flatMap[B](f: A => Parser[B]): Parser[B]
}

/** Contains Parser implementation helper methods not typically needed for using parsers. */
object Parser extends ParserMain
{
	sealed abstract class Result[+T] {
		def isFailure: Boolean
		def isValid: Boolean
		def errors: Seq[String]
		def or[B >: T](b: => Result[B]): Result[B]
		def either[B](b: => Result[B]): Result[Either[T,B]]
		def map[B](f: T => B): Result[B]
		def flatMap[B](f: T => Result[B]): Result[B]
		def &&(b: => Result[_]): Result[T]
		def filter(f: T => Boolean, msg: => String): Result[T]
		def seq[B](b: => Result[B]): Result[(T,B)] = app(b)( (m,n) => (m,n) )
		def app[B,C](b: => Result[B])(f: (T, B) => C): Result[C]
		def toEither: Either[() => Seq[String], T]
	}
	final case class Value[+T](value: T) extends Result[T] {
		def isFailure = false
		def isValid: Boolean = true
		def errors = Nil
		def app[B,C](b: => Result[B])(f: (T, B) => C): Result[C] = b match {
			case fail: Failure => fail
			case Value(bv) => Value(f(value, bv))
		}
		def &&(b: => Result[_]): Result[T] = b match { case f: Failure => f; case _ => this }
		def or[B >: T](b: => Result[B]): Result[B] = this
		def either[B](b: => Result[B]): Result[Either[T,B]] = Value(Left(value))
		def map[B](f: T => B): Result[B] = Value(f(value))
		def flatMap[B](f: T => Result[B]): Result[B] = f(value)
		def filter(f: T => Boolean, msg: => String): Result[T] = if(f(value)) this else mkFailure(msg)
		def toEither = Right(value)
	}
	final class Failure private[sbt](mkErrors: => Seq[String], val definitive: Boolean) extends Result[Nothing] {
		lazy val errors: Seq[String] = mkErrors
		def isFailure = true
		def isValid = false
		def map[B](f: Nothing => B) = this
		def flatMap[B](f: Nothing => Result[B]) = this
		def or[B](b: => Result[B]): Result[B] = b match {
			case v: Value[B] => v
			case f: Failure => if(definitive) this else this ++ f
		}
		def either[B](b: => Result[B]): Result[Either[Nothing,B]] = b match {
			case Value(v) => Value(Right(v))
			case f: Failure => if(definitive) this else this ++ f
		}
		def filter(f: Nothing => Boolean, msg: => String) = this
		def app[B,C](b: => Result[B])(f: (Nothing, B) => C): Result[C] = this
		def &&(b: => Result[_]) = this
		def toEither = Left(() => errors)

		private[sbt] def ++(f: Failure) = mkFailures(errors ++ f.errors)
	}
	def mkFailures(errors: => Seq[String], definitive: Boolean = false): Failure = new Failure(errors.distinct, definitive)
	def mkFailure(error: => String, definitive: Boolean = false): Failure = new Failure(error :: Nil, definitive)

	@deprecated("This method is deprecated and will be removed in the next major version. Use the parser directly to check for invalid completions.", since = "0.13.2")
	def checkMatches(a: Parser[_], completions: Seq[String])
	{
		val bad = completions.filter( apply(a)(_).resultEmpty.isFailure)
		if(!bad.isEmpty) sys.error("Invalid example completions: " + bad.mkString("'", "', '", "'"))
	}

	def tuple[A,B](a: Option[A], b: Option[B]): Option[(A,B)] =
		(a,b) match { case (Some(av), Some(bv)) => Some((av, bv)); case _ => None }

	def mapParser[A,B](a: Parser[A], f: A => B): Parser[B] =
		a.ifValid {
			a.result match
			{
				case Some(av) => success( f(av) )
				case None => new MapParser(a, f)
			}
		}

	def bindParser[A,B](a: Parser[A], f: A => Parser[B]): Parser[B] =
		a.ifValid {
			a.result match
			{
				case Some(av) => f(av)
				case None => new BindParser(a, f)
			}
		}

	def filterParser[T](a: Parser[T], f: T => Boolean, seen: String, msg: String => String): Parser[T] =
		a.ifValid {
			a.result match
			{
				case Some(av) if f(av) => success( av )
				case _ => new Filter(a, f, seen, msg)
			}
		}

	def seqParser[A,B](a: Parser[A], b: Parser[B]): Parser[(A,B)] =
		a.ifValid { b.ifValid {
			(a.result, b.result) match {
				case (Some(av), Some(bv)) => success( (av, bv) )
				case (Some(av), None) => b map { bv => (av, bv) }
				case (None, Some(bv)) => a map { av => (av, bv) }
				case (None, None) => new SeqParser(a,b)
			}
		}}

	def choiceParser[A,B](a: Parser[A], b: Parser[B]): Parser[Either[A,B]] =
		if(a.valid)
			if(b.valid) new HetParser(a,b) else a.map( left.fn )
		else
			b.map( right.fn )

	def opt[T](a: Parser[T]): Parser[Option[T]] =
		if(a.valid) new Optional(a) else success(None)

	def onFailure[T](delegate: Parser[T], msg: String): Parser[T] =
		if(delegate.valid) new OnFailure(delegate, msg) else failure(msg)
	def trapAndFail[T](delegate: Parser[T]): Parser[T] =
		delegate.ifValid( new TrapAndFail(delegate) )

	def zeroOrMore[T](p: Parser[T]): Parser[Seq[T]] = repeat(p, 0, Infinite)
	def oneOrMore[T](p: Parser[T]): Parser[Seq[T]] = repeat(p, 1, Infinite)

	def repeat[T](p: Parser[T], min: Int = 0, max: UpperBound = Infinite): Parser[Seq[T]] =
		repeat(None, p, min, max, Nil)
	private[complete] def repeat[T](partial: Option[Parser[T]], repeated: Parser[T], min: Int, max: UpperBound, revAcc: List[T]): Parser[Seq[T]] =
	{
		assume(min >= 0, "Minimum must be greater than or equal to zero (was " + min + ")")
		assume(max >= min, "Minimum must be less than or equal to maximum (min: " + min + ", max: " + max + ")")

		def checkRepeated(invalidButOptional: => Parser[Seq[T]]): Parser[Seq[T]] =
			repeated match
			{
				case i: Invalid if min == 0 => invalidButOptional
				case i: Invalid => i
				case _ =>
					repeated.result match
					{
						case Some(value) => success(revAcc reverse_::: value :: Nil) // revAcc should be Nil here
						case None => if(max.isZero) success(revAcc.reverse) else new Repeat(partial, repeated, min, max, revAcc)
					}
			}

		partial match
		{
			case Some(part) =>
				part.ifValid {
					part.result match
					{
						case Some(value) => repeat(None, repeated, min, max, value :: revAcc)
						case None => checkRepeated(part.map(lv => (lv :: revAcc).reverse))
					}
				}
			case None => checkRepeated(success(Nil))
		}
	}

	@deprecated("Explicitly call `and` and `not` to provide the failure message.", "0.12.2")
	def sub[T](a: Parser[T], b: Parser[_]): Parser[T]  =  and(a, not(b))

	def and[T](a: Parser[T], b: Parser[_]): Parser[T]  =  a.ifValid( b.ifValid( new And(a, b) ))
}
trait ParserMain
{
	/** Provides combinators for Parsers.*/
	implicit def richParser[A](a: Parser[A]): RichParser[A] = new RichParser[A]
	{
		def ~[B](b: Parser[B]) = seqParser(a, b)
		def ||[B](b: Parser[B]) = choiceParser(a,b)
		def |[B >: A](b: Parser[B]) = homParser(a,b)
		def ? = opt(a)
		def * = zeroOrMore(a)
		def + = oneOrMore(a)
		def map[B](f: A => B) = mapParser(a, f)
		def id = a

		def ^^^[B](value: B): Parser[B] = a map { _ => value }
		def ??[B >: A](alt: B): Parser[B] = a.? map { _ getOrElse alt }
		def <~[B](b: Parser[B]): Parser[A] = (a ~ b) map { case av ~ _ => av }
		def ~>[B](b: Parser[B]): Parser[B] = (a ~ b) map { case _ ~ bv => bv }
		def !!!(msg: String): Parser[A] = onFailure(a, msg)
		def failOnException: Parser[A] = trapAndFail(a)

		def unary_- = not(a)
		def & (o: Parser[_]) = and(a, o)
		def - (o: Parser[_]) = sub(a, o)
		def examples(s: String*): Parser[A] = examples(s.toSet)
		def examples(s: Set[String], check: Boolean = false): Parser[A] = examples(new FixedSetExamples(s), s.size, check)
		def examples(s: ExampleSource, maxNumberOfExamples: Int, removeInvalidExamples: Boolean): Parser[A] = Parser.examples(a, s, maxNumberOfExamples, removeInvalidExamples)
		def filter(f: A => Boolean, msg: String => String): Parser[A] = filterParser(a, f, "", msg)
		def string(implicit ev: A <:< Seq[Char]): Parser[String] = map(_.mkString)
		def flatMap[B](f: A => Parser[B]) = bindParser(a, f)
	}

	implicit def literalRichCharParser(c: Char): RichParser[Char] = richParser(c)
	implicit def literalRichStringParser(s: String): RichParser[String] = richParser(s)

	/** Construct a parser that is valid, but has no valid result.  This is used as a way
	* to provide a definitive Failure when a parser doesn't match empty input.  For example,
	* in `softFailure(...) | p`, if `p` doesn't match the empty sequence, the failure will come
	* from the Parser constructed by the `softFailure` method. */
	private[sbt] def softFailure(msg: => String, definitive: Boolean = false): Parser[Nothing] =
		SoftInvalid( mkFailures(msg :: Nil, definitive) )

	/** Defines a parser that always fails on any input with messages `msgs`.
	* If `definitive` is `true`, any failures by later alternatives are discarded.*/
	def invalid(msgs: => Seq[String], definitive: Boolean = false): Parser[Nothing] = Invalid(mkFailures(msgs, definitive))

	/** Defines a parser that always fails on any input with message `msg`.
	* If `definitive` is `true`, any failures by later alternatives are discarded.*/
	def failure(msg: => String, definitive: Boolean = false): Parser[Nothing] = invalid(msg :: Nil, definitive)

	/** Defines a parser that always succeeds on empty input with the result `value`.*/
	def success[T](value: T): Parser[T] = new ValidParser[T] {
		override def result = Some(value)
		def resultEmpty = Value(value)
		def derive(c: Char) = Parser.failure("Expected end of input.")
		def completions(level: Int) = Completions.empty
		override def toString = "success(" + value + ")"
	}

	/** Presents a Char range as a Parser.  A single Char is parsed only if it is in the given range.*/
	implicit def range(r: collection.immutable.NumericRange[Char]): Parser[Char] =
		charClass(r contains _).examples(r.map(_.toString) : _*)

	/** Defines a Parser that parses a single character only if it is contained in `legal`.*/
	def chars(legal: String): Parser[Char] =
	{
		val set = legal.toSet
		charClass(set, "character in '" + legal + "'") examples(set.map(_.toString))
	}

	/** Defines a Parser that parses a single character only if the predicate `f` returns true for that character.
	* If this parser fails, `label` is used as the failure message. */
	def charClass(f: Char => Boolean, label: String = "<unspecified>"): Parser[Char] = new CharacterClass(f, label)

	/** Presents a single Char `ch` as a Parser that only parses that exact character. */
	implicit def literal(ch: Char): Parser[Char] = new ValidParser[Char] {
		def result = None
		def resultEmpty = mkFailure( "Expected '" + ch + "'" )
		def derive(c: Char) = if(c == ch) success(ch) else new Invalid(resultEmpty)
		def completions(level: Int) = Completions.single(Completion.suggestStrict(ch.toString))
		override def toString = "'" + ch + "'"
	}
	/** Presents a literal String `s` as a Parser that only parses that exact text and provides it as the result.*/
	implicit def literal(s: String): Parser[String] = stringLiteral(s, 0)

	/** See [[unapply]]. */
	object ~ {
		/** Convenience for destructuring a tuple that mirrors the `~` combinator.*/
		def unapply[A,B](t: (A,B)): Some[(A,B)] = Some(t)
	}

	/** Parses input `str` using `parser`.  If successful, the result is provided wrapped in `Right`.  If unsuccesful, an error message is provided in `Left`.*/
	def parse[T](str: String, parser: Parser[T]): Either[String, T] =
		Parser.result(parser, str).left.map { failures =>
			val (msgs,pos) = failures()
			ProcessError(str, msgs, pos)
		}

	/** Convenience method to use when developing a parser.
	* `parser` is applied to the input `str`.
	* If `completions` is true, the available completions for the input are displayed.
	* Otherwise, the result of parsing is printed using the result's `toString` method.
	* If parsing fails, the error message is displayed.
	*
	* See also [[sampleParse]] and [[sampleCompletions]]. */
	def sample(str: String, parser: Parser[_], completions: Boolean = false): Unit =
		if(completions) sampleCompletions(str, parser) else sampleParse(str, parser)

	/** Convenience method to use when developing a parser.
	* `parser` is applied to the input `str` and the result of parsing is printed using the result's `toString` method.
	* If parsing fails, the error message is displayed. */
	def sampleParse(str: String, parser: Parser[_]): Unit =
		parse(str, parser) match {
			case Left(msg) => println(msg)
			case Right(v) => println(v)
		}

	/** Convenience method to use when developing a parser.
	* `parser` is applied to the input `str` and the available completions are displayed on separate lines.
	* If parsing fails, the error message is displayed. */
	def sampleCompletions(str: String, parser: Parser[_], level: Int = 1): Unit =
		Parser.completions(parser, str, level).get foreach println

	// intended to be temporary pending proper error feedback
	def result[T](p: Parser[T], s: String): Either[() => (Seq[String],Int), T] =
	{
		def loop(i: Int, a: Parser[T]): Either[() => (Seq[String],Int), T] =
			a match
			{
				case Invalid(f) => Left( () => (f.errors, i) )
				case _ =>
					val ci = i+1
					if(ci >= s.length)
						a.resultEmpty.toEither.left.map { msgs0 => () =>
							val msgs = msgs0()
							val nonEmpty = if(msgs.isEmpty) "Unexpected end of input" :: Nil else msgs
							(nonEmpty, ci)
						}
					else
						loop(ci, a derive s(ci) )
			}
		loop(-1, p)
	}

	/** Applies parser `p` to input `s`. */
	def apply[T](p: Parser[T])(s: String): Parser[T] =
		(p /: s)(derive1)

	/** Applies parser `p` to a single character of input. */
	def derive1[T](p: Parser[T], c: Char): Parser[T] =
		if(p.valid) p.derive(c) else p

	/** Applies parser `p` to input `s` and returns the completions at verbosity `level`.
	* The interpretation of `level` is up to parser definitions, but 0 is the default by convention,
	* with increasing positive numbers corresponding to increasing verbosity.  Typically no more than
	* a few levels are defined. */
	def completions(p: Parser[_], s: String, level: Int): Completions =
		// The x Completions.empty removes any trailing token completions where append.isEmpty
		apply(p)(s).completions(level) x Completions.empty

	def examples[A](a: Parser[A], completions: Set[String], check: Boolean = false): Parser[A] =
		examples(a, new FixedSetExamples(completions), completions.size, check)

	/**
	 * @param a the parser to decorate with a source of examples. All validation and parsing is delegated to this parser,
	 *          only [[Parser.completions]] is modified.
	 * @param completions the source of examples when displaying completions to the user.
	 * @param maxNumberOfExamples limits the number of examples that the source of examples should return. This can
	 *                            prevent lengthy pauses and avoids bad interactive user experience.
	 * @param removeInvalidExamples indicates whether completion examples should be checked for validity (against the given parser). An
	 *                              exception is thrown if the example source contains no valid completion suggestions.
	 * @tparam A the type of values that are returned by the parser.
	 * @return
	 */
	def examples[A](a: Parser[A], completions: ExampleSource, maxNumberOfExamples: Int, removeInvalidExamples: Boolean): Parser[A] =
		if(a.valid) {
			a.result match
			{
				case Some(av) => success( av )
				case None =>
					new ParserWithExamples(a, completions, maxNumberOfExamples, removeInvalidExamples)
			}
		}
		else a

	def matched(t: Parser[_], seen: Vector[Char] = Vector.empty, partial: Boolean = false): Parser[String] =
		t match
		{
			case i: Invalid => if(partial && !seen.isEmpty) success(seen.mkString) else i
			case _ =>
				if(t.result.isEmpty)
					new MatchedString(t, seen, partial)
				else
					success(seen.mkString)
		}

	/** Establishes delegate parser `t` as a single token of tab completion.
	* When tab completion of part of this token is requested, the completions provided by the delegate `t` or a later derivative are appended to
	* the prefix String already seen by this parser. */
	def token[T](t: Parser[T]): Parser[T] = token(t, TokenCompletions.default)

	/** Establishes delegate parser `t` as a single token of tab completion.
	* When tab completion of part of this token is requested, no completions are returned if `hide` returns true for the current tab completion level.
	* Otherwise, the completions provided by the delegate `t` or a later derivative are appended to the prefix String already seen by this parser.*/
	def token[T](t: Parser[T], hide: Int => Boolean): Parser[T] = token(t, TokenCompletions.default.hideWhen(hide))

	/** Establishes delegate parser `t` as a single token of tab completion.
	* When tab completion of part of this token is requested, `description` is displayed for suggestions and no completions are ever performed. */
	def token[T](t: Parser[T], description: String): Parser[T] = token(t, TokenCompletions.displayOnly(description))

	/** Establishes delegate parser `t` as a single token of tab completion.
	* When tab completion of part of this token is requested, `display` is used as the printed suggestion, but the completions from the delegate
	* parser `t` are used to complete if unambiguous. */
	def tokenDisplay[T](t: Parser[T], display: String): Parser[T] =
		token(t, TokenCompletions.overrideDisplay(display))

	def token[T](t: Parser[T], complete: TokenCompletions): Parser[T] =
		mkToken(t, "", complete)

	@deprecated("Use a different `token` overload.", "0.12.1")
	def token[T](t: Parser[T], seen: String, track: Boolean, hide: Int => Boolean): Parser[T] =
	{
		val base = if(track) TokenCompletions.default else TokenCompletions.displayOnly(seen)
		token(t, base.hideWhen(hide))
	}

	private[sbt] def mkToken[T](t: Parser[T], seen: String, complete: TokenCompletions): Parser[T] =
		if(t.valid && !t.isTokenStart)
			if(t.result.isEmpty) new TokenStart(t, seen, complete) else t
		else
			t

	def homParser[A](a: Parser[A], b: Parser[A]): Parser[A] = (a,b) match {
		case (Invalid(af), Invalid(bf)) => Invalid(af ++ bf)
		case (Invalid(_), bv) => bv
		case (av, Invalid(_)) => av
		case (av, bv) => new HomParser(a, b)
	}

	@deprecated("Explicitly specify the failure message.", "0.12.2")
	def not(p: Parser[_]): Parser[Unit] = not(p, "Excluded.")

	def not(p: Parser[_], failMessage: String): Parser[Unit] = p.result match {
		case None => new Not(p, failMessage)
		case Some(_) => failure(failMessage)
	}

	def oneOf[T](p: Seq[Parser[T]]): Parser[T] = p.reduceLeft(_ | _)
	def seq[T](p: Seq[Parser[T]]): Parser[Seq[T]] = seq0(p, Nil)
	def seq0[T](p: Seq[Parser[T]], errors: => Seq[String]): Parser[Seq[T]] =
	{
		val (newErrors, valid) = separate(p) { case Invalid(f) => Left(f.errors); case ok => Right(ok) }
		def combinedErrors = errors ++ newErrors.flatten
		if(valid.isEmpty) invalid(combinedErrors) else new ParserSeq(valid, combinedErrors)
	}

	def stringLiteral(s: String, start: Int): Parser[String] =
	{
		val len = s.length
		if(len == 0) sys.error("String literal cannot be empty") else if(start >= len) success(s) else new StringLiteral(s, start)
	}
}
sealed trait ValidParser[T] extends Parser[T]
{
	final def valid = true
	final def failure = None
	final def ifValid[S](p: => Parser[S]): Parser[S] = p
}
private final case class Invalid(fail: Failure) extends Parser[Nothing]
{
	def failure = Some(fail)
	def result = None
	def resultEmpty = fail
	def derive(c: Char) = sys.error("Invalid.")
	def completions(level: Int) = Completions.nil
	override def toString = fail.errors.mkString("; ")
	def valid = false
	def ifValid[S](p: => Parser[S]): Parser[S] = this
}

private final case class SoftInvalid(fail: Failure) extends ValidParser[Nothing]
{
	def result = None
	def resultEmpty = fail
	def derive(c: Char) = Invalid(fail)
	def completions(level: Int) = Completions.nil
	override def toString = fail.errors.mkString("; ")
}

private final class TrapAndFail[A](a: Parser[A]) extends ValidParser[A]
{
	def result = try { a.result } catch { case e: Exception => None }
	def resultEmpty = try { a.resultEmpty } catch { case e: Exception => fail(e) }
	def derive(c: Char) = try { trapAndFail(a derive c) } catch { case e: Exception => Invalid(fail(e)) }
	def completions(level: Int) = try { a.completions(level) } catch { case e: Exception => Completions.nil }
	override def toString = "trap(" + a + ")"
	override def isTokenStart = a.isTokenStart
	private[this] def fail(e: Exception): Failure = mkFailure(e.toString)
}

private final class OnFailure[A](a: Parser[A], message: String) extends ValidParser[A]
{
	def result = a.result
	def resultEmpty = a.resultEmpty match { case f: Failure => mkFailure(message); case v: Value[A] => v }
	def derive(c: Char) = onFailure(a derive c, message)
	def completions(level: Int) = a.completions(level)
	override def toString = "(" + a + " !!! \"" + message + "\" )"
	override def isTokenStart = a.isTokenStart
}
private final class SeqParser[A,B](a: Parser[A], b: Parser[B]) extends ValidParser[(A,B)]
{
	lazy val result = tuple(a.result,b.result)
	lazy val resultEmpty = a.resultEmpty seq b.resultEmpty
	def derive(c: Char) =
	{
		val common = a.derive(c) ~ b
		a.resultEmpty match
		{
			case Value(av) => common | b.derive(c).map(br => (av,br))
			case _: Failure => common
		}
	}
	def completions(level: Int) = a.completions(level) x b.completions(level)
	override def toString = "(" + a + " ~ " + b + ")"
}

private final class HomParser[A](a: Parser[A], b: Parser[A]) extends ValidParser[A]
{
	lazy val result = tuple(a.result, b.result) map (_._1)
	def derive(c: Char) = (a derive c) | (b derive c)
	lazy val resultEmpty = a.resultEmpty or b.resultEmpty
	def completions(level: Int) = a.completions(level) ++ b.completions(level)
	override def toString = "(" + a + " | " + b + ")"
}
private final class HetParser[A,B](a: Parser[A], b: Parser[B]) extends ValidParser[Either[A,B]]
{
	lazy val result = tuple(a.result, b.result) map { case (a,b) => Left(a) }
	def derive(c: Char) = (a derive c) || (b derive c)
	lazy val resultEmpty = a.resultEmpty either b.resultEmpty
	def completions(level: Int) = a.completions(level) ++ b.completions(level)
	override def toString = "(" + a + " || " + b + ")"
}
private final class ParserSeq[T](a: Seq[Parser[T]], errors: => Seq[String]) extends ValidParser[Seq[T]]
{
	assert(!a.isEmpty)
	lazy val resultEmpty: Result[Seq[T]] =
	{
		val res = a.map(_.resultEmpty)
		val (failures, values) = separate(res)(_.toEither)
//		if(failures.isEmpty) Value(values) else mkFailures(failures.flatMap(_()) ++ errors)
		if(values.nonEmpty) Value(values) else mkFailures(failures.flatMap(_()) ++ errors)
	}
	def result = {
		val success = a.flatMap(_.result)
		if(success.length == a.length) Some(success) else None
	}
	def completions(level: Int) = a.map(_.completions(level)).reduceLeft(_ ++ _)
	def derive(c: Char) = seq0(a.map(_ derive c), errors)
	override def toString = "seq(" + a + ")"
}

private final class BindParser[A,B](a: Parser[A], f: A => Parser[B]) extends ValidParser[B]
{
	lazy val result = a.result flatMap { av => f(av).result }
	lazy val resultEmpty = a.resultEmpty flatMap { av => f(av).resultEmpty }
	def completions(level: Int) =
		a.completions(level) flatMap { c =>
			apply(a)(c.append).resultEmpty match {
				case _: Failure => Completions.strict(Set.empty + c)
				case Value(av) => c x f(av).completions(level)
			}
		}

	def derive(c: Char) =
	{
		val common = a derive c flatMap f
		a.resultEmpty match
		{
			case Value(av) => common | derive1(f(av), c)
			case _: Failure => common
		}
	}
	override def isTokenStart = a.isTokenStart
	override def toString = "bind(" + a + ")"
}
private final class MapParser[A,B](a: Parser[A], f: A => B) extends ValidParser[B]
{
	lazy val result = a.result map f
	lazy val resultEmpty = a.resultEmpty map f
	def derive(c: Char) = (a derive c) map f
	def completions(level: Int) = a.completions(level)
	override def isTokenStart = a.isTokenStart
	override def toString = "map(" + a + ")"
}
private final class Filter[T](p: Parser[T], f: T => Boolean, seen: String, msg: String => String) extends ValidParser[T]
{
	def filterResult(r: Result[T]) = r.filter(f, msg(seen))
	lazy val result = p.result filter f
	lazy val resultEmpty = filterResult(p.resultEmpty)
	def derive(c: Char) = filterParser(p derive c, f, seen + c, msg)
	def completions(level: Int) = p.completions(level) filterS { s => filterResult(apply(p)(s).resultEmpty).isValid }
	override def toString = "filter(" + p + ")"
	override def isTokenStart = p.isTokenStart
}
private final class MatchedString(delegate: Parser[_], seenV: Vector[Char], partial: Boolean) extends ValidParser[String]
{
	lazy val seen = seenV.mkString
	def derive(c: Char) = matched(delegate derive c, seenV :+ c, partial)
	def completions(level: Int) = delegate.completions(level)
	def result = if(delegate.result.isDefined) Some(seen) else None
	def resultEmpty = delegate.resultEmpty match { case f: Failure if !partial => f; case _ => Value(seen) }
	override def isTokenStart = delegate.isTokenStart
	override def toString = "matched(" + partial + ", " + seen + ", " + delegate + ")"
}
private final class TokenStart[T](delegate: Parser[T], seen: String, complete: TokenCompletions) extends ValidParser[T]
{
	def derive(c: Char) = mkToken( delegate derive c, seen + c, complete)
	def completions(level: Int) = complete match {
		case dc: TokenCompletions.Delegating => dc.completions(seen, level, delegate.completions(level))
		case fc: TokenCompletions.Fixed => fc.completions(seen, level)
	}
	def result = delegate.result
	def resultEmpty = delegate.resultEmpty
	override def isTokenStart = true
	override def toString = "token('" + complete + ", " + delegate + ")"
}
private final class And[T](a: Parser[T], b: Parser[_]) extends ValidParser[T]
{
	lazy val result = tuple(a.result,b.result) map { _._1 }
	def derive(c: Char) = (a derive c) & (b derive c)
	def completions(level: Int) = a.completions(level).filterS(s => apply(b)(s).resultEmpty.isValid )
	lazy val resultEmpty = a.resultEmpty && b.resultEmpty
	override def toString = "(%s) && (%s)".format(a,b)
}

private final class Not(delegate: Parser[_], failMessage: String) extends ValidParser[Unit]
{
	def derive(c: Char) = if(delegate.valid) not(delegate derive c, failMessage) else this
	def completions(level: Int) = Completions.empty
	def result = None
	lazy val resultEmpty = delegate.resultEmpty match {
		case f: Failure => Value(())
		case v: Value[_] => mkFailure(failMessage)
	}
	override def toString = " -(%s)".format(delegate)
}

/**
 * This class wraps an existing parser (the delegate), and replaces the delegate's completions with examples from
 * the given example source.
 *
 * This class asks the example source for a limited amount of examples (to prevent lengthy and expensive
 * computations and large amounts of allocated data). It then passes these examples on to the UI.
 *
 * @param delegate the parser to decorate with completion examples (i.e., completion of user input).
 * @param exampleSource the source from which this class will take examples (potentially filter them with the delegate
 *                      parser), and pass them to the UI.
 * @param maxNumberOfExamples the maximum number of completions to read from the example source and pass to the UI. This
 *                            limit prevents lengthy example generation and allocation of large amounts of memory.
 * @param removeInvalidExamples indicates whether to remove examples that are deemed invalid by the delegate parser.
 * @tparam T the type of value produced by the parser.
 */
private final class ParserWithExamples[T](delegate: Parser[T], exampleSource: ExampleSource, maxNumberOfExamples: Int, removeInvalidExamples: Boolean) extends ValidParser[T]
{
	def derive(c: Char) =
		examples(delegate derive c, exampleSource.withAddedPrefix(c.toString), maxNumberOfExamples, removeInvalidExamples)

	def result = delegate.result

	lazy val resultEmpty = delegate.resultEmpty

	def completions(level: Int) = {
		if(exampleSource().isEmpty)
			if(resultEmpty.isValid) Completions.nil else Completions.empty
		else {
			val examplesBasedOnTheResult = filteredExamples.take(maxNumberOfExamples).toSet
			Completions(examplesBasedOnTheResult.map(ex => Completion.suggestion(ex)))
		}
	}

	override def toString = "examples(" + delegate + ", " + exampleSource().take(2).toList + ")"

	private def filteredExamples: Iterable[String] = {
		if (removeInvalidExamples)
			exampleSource().filter(isExampleValid)
		else
			exampleSource()
	}

	private def isExampleValid(example: String): Boolean = {
		apply(delegate)(example).resultEmpty.isValid
	}
}
private final class StringLiteral(str: String, start: Int) extends ValidParser[String]
{
	assert(0 <= start && start < str.length)
	def failMsg = "Expected '" + str + "'"
	def resultEmpty = mkFailure(failMsg)
	def result = None
	def derive(c: Char) = if(str.charAt(start) == c) stringLiteral(str, start+1) else new Invalid(resultEmpty)
	def completions(level: Int) = Completions.single(Completion.suggestion(str.substring(start)))
	override def toString = '"' + str + '"'
}
private final class CharacterClass(f: Char => Boolean, label: String) extends ValidParser[Char]
{
	def result = None
	def resultEmpty = mkFailure("Expected " + label)
	def derive(c: Char) = if( f(c) ) success(c) else Invalid(resultEmpty)
	def completions(level: Int) = Completions.empty
	override def toString = "class(" + label + ")"
}
private final class Optional[T](delegate: Parser[T]) extends ValidParser[Option[T]]
{
	def result = delegate.result map some.fn
	def resultEmpty = Value(None)
	def derive(c: Char) = (delegate derive c).map(some.fn)
	def completions(level: Int) = Completion.empty +: delegate.completions(level)
	override def toString = delegate.toString + "?"
}
private final class Repeat[T](partial: Option[Parser[T]], repeated: Parser[T], min: Int, max: UpperBound, accumulatedReverse: List[T]) extends ValidParser[Seq[T]]
{
	assume(0 <= min, "Minimum occurences must be non-negative")
	assume(max >= min, "Minimum occurences must be less than the maximum occurences")

	def derive(c: Char) =
		partial match
		{
			case Some(part) =>
				val partD = repeat(Some(part derive c), repeated, min, max, accumulatedReverse)
				part.resultEmpty match
				{
					case Value(pv) => partD | repeatDerive(c, pv :: accumulatedReverse)
					case _: Failure => partD
				}
			case None => repeatDerive(c, accumulatedReverse)
		}

	def repeatDerive(c: Char, accRev: List[T]): Parser[Seq[T]]  =  repeat(Some(repeated derive c), repeated, (min - 1) max 0, max.decrement, accRev)

	def completions(level: Int) =
	{
		def pow(comp: Completions, exp: Completions, n: Int): Completions =
			if(n == 1) comp else pow(comp x exp, exp, n - 1)

		val repC = repeated.completions(level)
		val fin = if(min == 0) Completion.empty +: repC else pow(repC, repC, min)
		partial match
		{
			case Some(p) => p.completions(level) x fin
			case None => fin
		}
	}
	def result = None
	lazy val resultEmpty: Result[Seq[T]] =
	{
		val partialAccumulatedOption =
			partial match
			{
				case None => Value(accumulatedReverse)
				case Some(partialPattern) => partialPattern.resultEmpty.map(_ :: accumulatedReverse)
			}
		(partialAccumulatedOption app repeatedParseEmpty)(_ reverse_::: _)
	}
	private def repeatedParseEmpty: Result[List[T]] =
	{
		if(min == 0)
			Value(Nil)
		else
			// forced determinism
			for(value <- repeated.resultEmpty) yield
				makeList(min, value)
	}
	override def toString = "repeat(" + min + "," + max +"," + partial + "," + repeated + ")"
}