Commits

pchiusano committed a3cac9c

greatly simplified code by moving to final encoding of commit and block combinators

Comments (0)

Files changed (2)

src/main/scala/nomo/Parser.scala

 import util._
 import util.Trampoline._
 
-trait Status[E,A]
-case class Success[E,A](a: A) extends Status[E,A]
-case class Failure[E,A](e: E) extends Status[E,A]
-case class Error[E,A](e: E) extends Status[E,A]
+sealed trait Status[+E,+A] { 
+  def right: Option[A] = this match { 
+    case Success(a) => Some(a)
+    case _ => None
+  }
+  def left: Option[E] = this match {
+    case Failure(e) => Some(e)
+    case Error(e) => Some(e)
+    case _ => None
+  }
+  def map[B](f: A => B): Status[E,B] = this match {
+    case Success(a) => Success(f(a))
+    case e@Failure(_) => e
+    case e@Error(_) => e
+  }
+  def mapL[E2,A2>:A](f: E => E2): Status[E2,A2] = this match {
+    case Failure(e) => Failure(f(e))
+    case Error(e) => Error(f(e))
+    case a@Success(_) => a
+  }
+  def flatMap[E2>:E,B](f: A => Status[E2,B]): Status[E2,B] = this match {
+    case Success(a) => f(a)
+    case e@Failure(_) => e
+    case e@Error(_) => e
+  }
+  def flatMapL[E2,A2>:A](f: E => Status[E2,A2]): Status[E2,A2] = this match {
+    case Failure(e) => f(e)
+    case Error(e) => f(e)
+    case a@Success(_) => a
+  }
+}
+case class Success[A](a: A) extends Status[Nothing,A]
+case class Failure[E](e: E) extends Status[E,Nothing]
+case class Error[E](e: E) extends Status[E,Nothing]
 
 /** The result of a parse. Contains the status (either an error
   * or the successful result) and the position. */
-case class Result[X,E,U,A](status: Either[E,A], position: X, user: U) {
+case class Result[X,E,U,A](status: Status[E,A], position: X, user: U) {
   //lazy val status = statusT.run
   def get: A = status.right.getOrElse(
     sys.error("Parse error(s), position %s:\n%s".format(position,status.left.get)))
   def failure: E = status.left.getOrElse(
     sys.error("Cannot extract failure from successful parse"))
-  def isFailure = status.isLeft
-  def isSuccess = status.isRight
+  def isFailure = status.left.isDefined
+  def isSuccess = status.right.isDefined
 }
 
 object Parsers {
     def feed(i: Input[F,I], a: Accumulator[I,X,U]): Trampoline[(Parser[A], Accumulator[I,X,U])]
 
     /** Transforms the result value of this `Parser` using the given function. */
-    def mapResult[B](f: Result[X,E,U,A] => Either[E,B]): Parser[B] = this match {
+    def mapResult[B](f: Result[X,E,U,A] => Status[E,B]): Parser[B] = this match {
       case Done(r,remainder,ann) => Done(f(Result(r, ann.get, ann.getUser)), remainder, ann)
       case Cont(c,pending) => Cont((i,a) => c(i,a) map { case (p2,a2) => (p2.mapResult(f), a2) }, pending) 
-      case Block(p,h) => block(p.mapResult(f),h)
-      case Commit(p) => p.mapResult(f).commit
     }
 
+    def mapErr[E2](f: E => E): Parser[A] = 
+      mapResult(r => r.status.mapL(f))
+
     /** Sequences this parser with the given `Parser` - if this succeeds,
       * `p` will be run over the remaining `Input`. If `p` is successful, its result
       * is combined with the result of this `Parser` using the given function. */
       
     /** Converts the `Result` of this `Parser` into either an error or another
       * `Parser` to run using the remaining `Input` from this `Parser`. */
-    def flatMapResult[B](g: Result[X,E,U,A] => Either[E,Parser[B]]): Parser[B] = this match {
+    def flatMapResult[B](g: Result[X,E,U,A] => Status[E,Parser[B]]): Parser[B] = this match {
       case Done(get,remainder,ann) => 
         g(Result(get, ann.get, ann.getUser)) match {
-          case Left(e) => Done(Left(e),remainder,ann)
-          case Right(pb) => pb.feedLater(remainder,ann)
+          case Success(pb) => pb.feedLater(remainder,ann)
+          case Failure(e) => Done(Failure(e),remainder,ann)
+          case Error(e) => Done(Error(e),remainder,ann)
         }
       case Cont(c,pending) => Cont(
         (i,a) => c(i,a) map { case (p2,a2) => (p2.flatMapResult(g),a2) },
         pending
       )
-      case Block(p@Done(_,_,_),_) => p.flatMapResult(g)
-      case Block(Commit(p@Done(_,_,_)),h) => p.flatMapResult(g)
-      case Block(p,h) => Cont((i,a) => p.feed(i,a) map { 
-        case (p2,a2) => 
-          if (p2.isDone) (p2.flatMapResult(g), a2)
-          else (block(p2,h).flatMapResult(g), a2)
-      })
-      case Commit(p) => p.flatMapResult(g).commit
     }
 
-    /** Left-biased backtracking choice between `this` and `p`. Alias for `|`. */
+    /** Failure-biased backtracking choice between `this` and `p`. Alias for `|`. */
     def or[B>:A](p: Parser[B]): Parser[B] = this | p
 
     /** `n-ary` verion of `feed`. */
         case _ => this match {
           case Done(r,rem,ann) => Done(r,rem ++ i,a)
           case Cont(f,buf) => Cont(f, buf ++ i)
-          case Block(p,h) => block(p.feedLater(i,a),h)
-          case Commit(p) => p.feedLater(i,a).commit 
         }
       }
     }
 
     /** Tranform the output of this `Parser`. */
-    def map[B](f: A => B): Parser[B] = mapResult(r => r.status.right.map(f))
+    def map[B](f: A => B): Parser[B] = mapResult(r => r.status.map(f))
 
     /** Produce a new `Parser` from the result of this `Parser`, and run that `Parser`
       * using the remaining unconsumed `Input` leftover from running `this`. */
-    def flatMap[B](f: A => Parser[B]): Parser[B] = flatMapResult(r => r.status.right.map(f))
+    def flatMap[B](f: A => Parser[B]): Parser[B] = flatMapResult(r => r.status.map(f))
 
     /** Sequence `this` and `p`, ignoring the result of `this`. */
     def >>[B](p: => Parser[B]): Parser[B] = (this map2 p)((_,b) => b)
     /** Extract a result from this parser, by feeding it EOF. */
     def result(ann: Accumulator[I,X,U]): Result[X,E,U,A] = this.feed(inputs.EOF, ann).run._1 match {
       case Done(r,_,a) => Result(r, a.get, a.getUser)
-      case Commit(Done(r,_,a)) => Result(r, a.get, a.getUser)
-      //case Block(Done(r,_,a),_) => Result(r, a.get, a.getUser)
-      //case Commit(Block(Done(r,_,a),_)) => Result(r, a.get, a.getUser)
-      // case Block(Commit(Done(Left(e),_,a)),handle) => 
-      //  Result(Left(handle(a,e) getOrElse e), a.get, a.getUser) 
-      //case Block(Commit(Done(r,_,a)),_) => Result(r,a.get,a.getUser)
       case p => sys.error("divergent parser did not halt on EOF: " + p)
     }
 
       * consumed any input.
       */
     def scope(f: X => E): Parser[A] =
-      position.flatMap(x => this.mapResult(r => r.status.left.map(e => err.nest(f(x), e))))
+      position.flatMap(x => this.mapResult(r => r.status.mapL(e => err.nest(f(x), e))))
 
     /** Establishes a parent scope for this `Parser` - useful for creating hierarchical errors
       * during and after parsing has occurred. In the case of failure the result is the same
       * `E => E` to construct hierarchical errors at a later time. */
     def scope(f: X => E, g: (E => E, A) => A): Parser[A] =
       position.flatMap(x => this.mapResult(r => r.status match {
-        case Left(e) => Left(err.nest(f(x), e))
-        case Right(a) => Right(g(err.nest(f(x),_), a))
+        case Failure(e) => Failure(err.nest(f(x), e))
+        case Error(e) => Error(err.nest(f(x), e))
+        case Success(a) => Success(g(err.nest(f(x),_), a))
       }))
 
     /** Annotate the result of this `Parser` with the current position. */
     /** Combines the results of this parser and p into a pair. */
     def ++[B](p: => Parser[B]): Parser[(A,B)] = (this map2 p)((a,b) => (a,b))
 
-    /** Left-biased choice between this and p, with backtracking. */
+    /** Failure-biased choice between this and p, with backtracking. */
     def ||[B>:A](p: Parser[B]): Parser[B] = this.asInstanceOf[Parser[B]] or p
   
     // can implement slice - for grabbing the input associated with a parser
   
     def commit: Parser[A] = Parsers.this.commit(this)
 
-    /** Left-biased choice between this and p without backtracking - if this parser consumes any input before
+    /** Failure-biased choice between this and p without backtracking - if this parser consumes any input before
       * failing, we don't try running the parser p.
       */
     def |[B>:A](p: Parser[B]): Parser[B] = {
         Cont((i,a) => p.feed(i,a) flatMap { r =>
           var eof = i match { case EOFInput(_) => true; case _ => false }
           r._1 match { 
-            // commit (error or otherwise) immediately kills the right branch 
-            case Commit(_) => 
-              //println("committing: " + r._1)
-              r 
+            // committed failure on the left kills the right branch 
+            case Done(Error(_),_,_) => r 
             // success on the left also kills the other branch
-            case Done(Right(_),_,_) => r 
+            case Done(Success(_),_,_) => r 
               // uncomitted failure on left switches to right branch
-            case Done(Left(_),_,_) => p2.feedAll(inputs :+ i, acc getOrElse a)
+            case Done(Failure(_),_,_) => p2.feedAll(inputs :+ i, acc getOrElse a)
               //println("failure on left: " + r._1 + " after " + i)
               //println("switching to branch: " + p2 + " with inputs: " + 
                       // (inputs :+ i))
               // todo: anything we should do w/ error reporting here? could mapResult and or the errors
             // commited failure inside a block can switch to right branch (if handler allows it)
-            case Block(Commit(Done(Left(e),rem,ann)),handle) => handle(ann, e) match {
-              case None => p2.feedAll(inputs :+ i, acc getOrElse a)
-              case Some(e2) => suspend(Commit(Done(Left(e2),rem,ann)), r._2) // todo - is this correct? should this be ann?
-            }
             // otherwise keep both branches alive 
             case p12 => 
               if (eof) sys.error("keeping both branches alive on EOF: " + p12)
 
     /** Parser which turns results not matching the given predicate into failures. */
     def filter(f: A => Boolean, onFailure: X => E): Parser[A] =
-      mapResult(r => r.status.right.flatMap(
-        a => if (f(a)) Right(a) else Left(onFailure(r.position))))
+      mapResult(r => r.status.flatMap(
+        a => if (f(a)) Success(a) else Failure(onFailure(r.position))))
 
     /** True if this Parser is already in the Done state. */
     def isDone: Boolean = this match { case Done(_,_,_) => true; case _ => false }
     //  if (isDone) sys.error("cannot take .many of already finished parser: " + this)
     //  def collect(acc: List[A], cur: Parser[A], i: IndexedSeq[Input[F,I]], pos: Accumulator[I,X,U]): (List[A], Parser[A], Accumulator[I,X,U]) =
     //    cur.feedAll(i,pos) match {
-    //      case (d@Done(e@Left(_), rem, pos2), _) => (acc, d, pos2)
-    //      case (Done(Right(a), rem, pos2), _) => collect(a :: acc, this, rem, pos2)
+    //      case (d@Done(e@Failure(_), rem, pos2), _) => (acc, d, pos2)
+    //      case (Done(Success(a), rem, pos2), _) => collect(a :: acc, this, rem, pos2)
     //      case (cont, pos2) => (acc, cont, pos2)
     //    }
     //  def go(acc: List[A], p: Parser[A]): Parser[List[A]] = Cont((i,pos) => {
     //    val (acc2,p2,pos2) = collect(acc, p, IndexedSeq(i), pos)
     //    p2 match {
     //      case Cont(_,_) => (go(acc2, p2), pos2)
-    //      case Done(_,rem,pos2) => (Done(Right(acc2.reverse), rem, pos2), pos2)
+    //      case Done(_,rem,pos2) => (Done(Success(acc2.reverse), rem, pos2), pos2)
     //    }
     //  })
     //  go(List(), this)
     def delimit1(sep: Parser[_]): Parser[List[A]] =
       (this map2 (sep >> this).many)(_ :: _)
 
-    /** A Parser in which a failure, e, becomes a successful parse of Left(e).
+    /** A Parser in which a failure, e, becomes a successful parse of Failure(e).
       * In the case of failure, onFail is run after the failure point purely
       * to consume input up until some recovery point.
       */
-    def recover[C](onFail: Parser[_]): Parser[Either[E,A]] =
+    def recover[C](onFail: Parser[_]): Parser[Status[E,A]] =
       this.flatMapResult(r => r.status match {
-        case Right(a) => Right(unit(Right(a)))
-        case e@Left(_) => Right(onFail >> unit(e))
+        case Success(a) => Success(unit(Success(a)))
+        case e => Success(onFail >> unit(e))
       })
 
     /** Like delimit1, but recovers from errors in this parser and in case of
       */
     def delimit1(sep: Parser[_], onFail: Parser[_]): Parser[List[A]] =
       recover(onFail).delimit1(sep).flatMap(l => {
-        val failures = l.flatMap(_.left.toOption)
-        val successes =  l.flatMap(_.right.toOption)
+        val failures = l.flatMap(_.left)
+        val successes =  l.flatMap(_.right)
         if (failures.isEmpty) unit(successes)
         else fail(failures.reduceLeft(err.sequence))
       })
 
     /** Like many1, but recovers from errors in this parser. See `delimit1`. */
     def many1(onFail: Parser[_]): Parser[List[A]] = recover(onFail).many1.flatMap(l => {
-      val failures = l.flatMap(_.left.toOption)
-      val successes =  l.flatMap(_.right.toOption)
+      val failures = l.flatMap(_.left)
+      val successes =  l.flatMap(_.right)
       if (failures.isEmpty) unit(successes)
       else fail(failures.reduceLeft(err.sequence))
     })
 
   /** Parses the single token given. */
   def single(c: I): Parser[I] = attempt(any mapResult (s =>
-    s.status.right.flatMap(i => if (i == c) Right(i) else Left(err.single(c, s.position)))))
+    s.status.flatMap(i => if (i == c) Success(i) else Failure(err.single(c, s.position)))))
 
   /** Parses any single token. */
   def any: Parser[I] =
     Cont((i,a) => i match {
-      case e@EOFInput(_) => suspend(Done(Left(err.unexpectedEOF(a.get)), IndexedSeq(e), a), a)
+      case e@EOFInput(_) => suspend(Done(Failure(err.unexpectedEOF(a.get)), IndexedSeq(e), a), a)
       case ChunkInput(i2) => {
         if (i2.isEmpty) (any, a)
         else {
           val a2 = a.feedN(1,i2)
-          (Done(Right(i2(0)), IndexedSeq(ChunkInput(i2.slice(1))), a2), a2)
+          (Done(Success(i2(0)), IndexedSeq(ChunkInput(i2.slice(1))), a2), a2)
         }
       }
     })
 
   /** Parses the end of input token. */
   def eof: Parser[Unit] = Cont((i,a) => i match {
-    case EOFInput(_) => (Done(Right(()), IndexedSeq(i), a), a)
+    case EOFInput(_) => (Done(Success(()), IndexedSeq(i), a), a)
     case ChunkInput(chunk) if chunk.isEmpty => (eof, a)
-    case _ => suspend(Done(Left(err.expectedEOF(a.get)), IndexedSeq(i), a), a)
+    case _ => suspend(Done(Failure(err.expectedEOF(a.get)), IndexedSeq(i), a), a)
   })
 
   /** Parser for any of the given tokens. */
       if (s.isEmpty || s.head != a) (false,s)
       else (true,s.tail)).
     mapResult(r =>
-      r.status.right.flatMap { case (w,s) =>
-        if (s.isEmpty) Right(w)
-        else Left(err.single(s.head, r.position))
+      r.status.flatMap { case (w,s) =>
+        if (s.isEmpty) Success(w)
+        else Failure(err.single(s.head, r.position))
       }
     )
   }
   def takeWhile(f: I => Boolean): Parser[MonotypicW[F,I]] = {
     def go(acc: MonotypicW[F,I]): Parser[MonotypicW[F,I]] = Cont((i,a) =>
       i match {
-        case EOF => { val ai = a(i); (Done(Right(acc), IndexedSeq(EOF), ai), ai) }
+        case EOF => { val ai = a(i); (Done(Success(acc), IndexedSeq(EOF), ai), ai) }
         case ChunkInput(chunk) => {
           val (h,t) = chunk.span(f)
           val ah = a(h)
           if (t.isEmpty) (go(acc ++ h), ah)
-          else (Done(Right(acc ++ h), IndexedSeq(ChunkInput(t)), ah), ah)
+          else (Done(Success(acc ++ h), IndexedSeq(ChunkInput(t)), ah), ah)
         }
       })
     go(MonotypicW(container(List()), container))
   def takeUnfold[S](s0: S)(f: (I,S) => (Boolean,S)): Parser[(MonotypicW[F,I],S)] = {
     def go(acc: MonotypicW[F,I], s: S): Parser[(MonotypicW[F,I],S)] = Cont((i,a) =>
       i match {
-        case EOF => { val ai = a(i); (Done(Right((acc,s)), IndexedSeq(EOF), ai), ai) }
+        case EOF => { val ai = a(i); (Done(Success((acc,s)), IndexedSeq(EOF), ai), ai) }
         case ChunkInput(chunk) => {
           val (h,t,s2) = chunk.spanS(s)(f)
           val ah = a(h)
           if (t.isEmpty) (go(acc ++ h, s2), ah)
-          else (Done(Right((acc ++ h,s2)), IndexedSeq(ChunkInput(t)), ah), ah)
+          else (Done(Success((acc ++ h,s2)), IndexedSeq(ChunkInput(t)), ah), ah)
         }
       }
     )
   }
 
   /** Parser which consumes no input but returns the current accumulated position. */
-  def position: Parser[X] = Cont((i,a) => (Done(Right(a.get), IndexedSeq(i), a), a))
+  def position: Parser[X] = Cont((i,a) => (Done(Success(a.get), IndexedSeq(i), a), a))
 
   /** Parser which consumes no input and returns the user state. */
-  def getUser: Parser[U] = Cont((i,a) => (Done(Right(a.getUser), IndexedSeq(i), a), a))
+  def getUser: Parser[U] = Cont((i,a) => (Done(Success(a.getUser), IndexedSeq(i), a), a))
 
   /** Parser which consumes no input and sets the user state. */
   def setUser(u: U): Parser[Unit] = Cont((i, a) =>
-    { val na = a.setUser(u) ; (Done(Right(()), IndexedSeq(i), na), na)})
+    { val na = a.setUser(u) ; (Done(Success(()), IndexedSeq(i), na), na)})
 
   /** Parser which consumes no input and always returns the given A. */
   def unit[A](a: A): Parser[A] = {
-    val p = Cont((i, ann) => (Done(Right(a), IndexedSeq(i), ann), ann))
+    val p = Cont((i, ann) => (Done(Success(a), IndexedSeq(i), ann), ann))
     p.name = "unit("+a+")"
     p
   }
 
   /** Parser which consumes no input and always fails with the given error. */
-  def fail[A](err: E): Parser[A] = Cont((i, ann) => suspend(Done(Left(err), IndexedSeq(i), ann), ann))
+  def fail[A](err: E): Parser[A] = Cont((i, ann) => suspend(Done(Failure(err), IndexedSeq(i), ann), ann))
 
   /** Parser which consumes no input and fails with the error generated from the current position. */
-  def fail[A](f: X => E): Parser[A] = position.mapResult(r => r.status.right.flatMap(x => Left(f(x))))
+  def fail[A](f: X => E): Parser[A] = position.mapResult(r => r.status.flatMap(x => Failure(f(x))))
   
-  def block[A](p: Parser[A], handle: (Accumulator[I,X,U],E) => Option[E] = (a,e) => None): Parser[A] = p match {
-    case Done(_,_,_) => p
-    case _ => Block(p, handle)
+  def block[A](p: Parser[A], handle: (X,E) => Option[E] = (a,e) => None): Parser[A] = p mapResult { r => 
+    r.status match {
+      case Error(e) => handle(r.position, e).
+                       map(e2 => Error(e2)).
+                       getOrElse (Failure(e)) 
+      case _ => r.status
+    }
   }
 
-  def commit[A](p: Parser[A]): Parser[A] = p match {
-    case Commit(_) => p
-    case _ => Commit(p)
-  }
-  
-  case class Commit[A](p: Parser[A]) extends Parser[A] {
-    def feed(i: Input[F,I], ann: Accumulator[I,X,U]): Trampoline[(Parser[A], Accumulator[I,X,U])] = 
-      p.feed(i,ann) map { case (p2,a2) => (p2.commit, a2) }
-  }
-
-  // issue with EOF handling in or combinator
-
-  // give block a function from (Accumulator[I,X,U],E) => Option[E], gives it a chance to add extra info to error if
-  case class Block[A](p: Parser[A], handle: (Accumulator[I,X,U],E) => Option[E]) extends Parser[A] {
-    def feed(i: Input[F,I], ann: Accumulator[I,X,U]): Trampoline[(Parser[A], Accumulator[I,X,U])] =
-      i match {
-        case EOFInput(_) => p.feed(i,ann) map { 
-          case (p2,a2) => (
-            p2.mapResult(r => 
-              r.status.left.map(e => handle(a2,e) getOrElse e).
-                       right.map(a => a)), 
-            a2
-          )
-        }
-        case _ => p.feed(i,ann) map { case (p2,a2) => (block(p2,handle), a2) }
-      }
+  def commit[A](p: Parser[A]): Parser[A] = p mapResult { r => 
+    r.status match {
+      case Failure(e) => Error(e)
+      case r => r 
+    }
   }
 
   case class Cont[A](
 
   // case class Done[A](get: Either[E,A], remainder: IndexedSeq[Input[F,I]], ann: Accumulator[I,X,U]) extends Parser[A] {
 
-  case class Done[A](get: Either[E,A], remainder: IndexedSeq[Input[F,I]], ann: Accumulator[I,X,U]) extends Parser[A] {
+  case class Done[A](get: Status[E,A], remainder: IndexedSeq[Input[F,I]], ann: Accumulator[I,X,U]) extends Parser[A] {
     def annotate(f: Accumulator[I,X,U]) = Done(get, remainder, f)
     def feed(i: Input[F,I], a: Accumulator[I,X,U]): Trampoline[(Parser[A], Accumulator[I,X,U])] =
       (Done(get, remainder :+ i, a), a)

src/test/scala/nomo/ParserSpec.scala

 
   property("many-ex1") = secure {
     val p = P.single('a').many >> P.single(',') >> P.single('a').many
-    p("aa,aa ") ?= Result(Right("aa".toList), Position(5,0,5,5), ())
+    p("aa,aa ") ?= Result(Success("aa".toList), Position(5,0,5,5), ())
   }
 
   property("many-ex2") = secure {
 
   property("position2") = forAll((s: String) =>
     position.feedChunked(s, annotator(()))._1 match {
-      case P.Done(Right(Accumulators.Position(0,0,0,0)), chunks, _) => 
+      case P.Done(Success(Accumulators.Position(0,0,0,0)), chunks, _) => 
         (chunks.map { case ChunkInput(c) => c.get } .mkString ?= s)
       case _ => false: Prop
     })
     val input3 = bs.map(b => if (b) s else s.substring(0,s.length-1)).mkString(",") 
     val successful = bs.forall(b => b)
     if (successful) 
-      (p(input1).status ?= Right(List.fill(bs.length)(s))) &&
-      (p(input2).status ?= Right(List.fill(bs.length)(s))) &&
-      (p(input3).status ?= Right(List.fill(bs.length)(s)))
+      (p(input1).status ?= Success(List.fill(bs.length)(s))) &&
+      (p(input2).status ?= Success(List.fill(bs.length)(s))) &&
+      (p(input3).status ?= Success(List.fill(bs.length)(s)))
     else {
       val errs = bs.flatMap(b => if (b) None else Some(err)).toIndexedSeq
       (p(input1).status.left.get.toSeq.length ?= errs.length) &&