package tools;

/** Parsers class with Parser combinators from <cite>Scala by
 * Example</cite> by Martin Odersky.  This is also found in the
 * examples/Parsers.scala file in the Scala distribution.
 */
abstract class Parsers {

  /** The input is assumed to have this type. */
  type inputType;

  /** Basic parsing machinery */
  trait Parser[a] {

    /** Parsing results are either None or Some(Pair(ast, left)),
     *  where ast is an abstract syntax tree and left is what input remains
     * to parse. */
    type Result = Option[Pair[a, inputType]];

    /** Parse the input (a hook to coordinating with the input). */
    def apply(in: inputType): Result;

    /** Succeed if the predicate matches after parsing the input.
     * Used to define for-comprehension style parsing. */
    def filter(pred: a => boolean) = new Parser[a] {
      def apply(in: inputType): Result = Parser.this.apply(in) match {
        case None => None
        case Some(Pair(x, in1)) => if (pred(x)) Some(Pair(x, in1)) else None
      }
    }

    /** Apply f to the result of parsing the input.
     *  Used to define for-comprehension style parsing. */
    def map[b](f: a => b) = new Parser[b] {
      def apply(in: inputType): Result = Parser.this.apply(in) match {
        case None => None
        case Some(Pair(x, in1)) => Some(Pair(f(x), in1))
      }
    }

    /** Apply the parser f to the result of parsing the input.
     *  Used to define for-comprehension style parsing. */
    def flatMap[b](f: a => Parser[b]) = new Parser[b] {
      def apply(in: inputType): Result = Parser.this.apply(in) match {
        case None => None
        case Some(Pair(x, in1)) => f(x).apply(in1)
      }
    }
    
    /** alternation (in left to right order) of parsers. */
    def ||| (p: => Parser[a]) = new Parser[a] {
      def apply(in: inputType): Result = Parser.this.apply(in) match {
        case None => p(in)
        case s => s
      }
    }

    /** Sequential combination of this with the parser p. */
    def &&& [b](p: => Parser[b]): Parser[b] = 
      for (val _ <- this; val x <- p) yield x;
  }

  /** Succeed without touching the input,
   *  placing the parse tree x in the result. */
  def succeed[a](x: a) = new Parser[a] {
    def apply(in: inputType): Result = Some(Pair(x, in))
  }

  /** Parse zero or more occurrences of p from the input,
   *  returning a list of the ASTs generated. */
  def rep[a](p: Parser[a]): Parser[List[a]] =
    rep1(p) ||| succeed(List());

  /** Parse one or more occurrences of p from the input,
   *  returning a list of the ASTs generated. */
  def rep1[a](p: Parser[a]): Parser[List[a]] =
    for (val x <- p; val xs <- rep(p)) yield x :: xs;

  /** Parse one or zero occurences of p from the input,
   *  returning an list of the AST generated or an empty list. */
  def opt[a](p: Parser[a]): Parser[List[a]] =
    (for (val x <- p) yield List(x)) ||| succeed(List());
}