Parser.scala

package foo

sealed trait ParsingError extends Any {
  def error: String
  override def toString: String = s"Parsing error: $error"
}
case object NoInputError extends ParsingError {
  override def error: String = "No more input"
}
final case class WrongMatch[A](expected: A, found: A) extends ParsingError {
  override def error: String = s"Expecting '$expected'. Got '$found' instead"
}


/** A parser may be viewed as a function from a string of symbols to a result value. Since a parser
  * might not consume the entire string, part of this result will be a suffix of the input string.
  *
  * {{{
  *   type Parser[A] = String => Either[ParsingError, (A, String)]
  * }}}
  *
  * Sometimes a parser may not be able to produce a result at all, in this case a `Left(error)` value
  * is returned.
  *
  * In case of success a `Right((v, xs))` is returned, where `v` is the parsed value and `xs` the
  * unconsumed input.
  */
object Parser { self =>

  type ParsingResult[A] = Either[ParsingError, (A, String)]
  type Parser[A] = String => Either[ParsingError, (A, String)]

  implicit class ParserSyntax[A](val p: Parser[A]) extends AnyVal {
    def and(p2: => Parser[A]): Parser[(A, A)] = {
      self.and(p, p2)
    }

    def or(p2: => Parser[A]): Parser[A] = {
      self.or(p, p2)
    }

    /** Run the parser. On success, transform the parsed value using the provided
      * function. Otherwise, return the failure.
      */
    def map[B](f: A => B): Parser[B] = {
      (input: String) =>
        p(input) match {
          case Left(err)       => Left(err)
          case Right((v, rem)) => Right((f(v), rem))
        }
    }

    /** The parser `p.flatMap(f)` fails if the application of the parser `p` to the input
      * string fails, and otherwise applies the function `f` to the result value to give a
      * second parser, which is then applied to the output string to give the final result.
      */
    def flatMap[B](f: A => Parser[B]): Parser[B] = {
      (input: String) =>
        {
          p(input) match {
            case Left(err) => Left(err)
            case Right((v, rem)) =>
              f(v)(rem)
          }
        }
    }
  }

  /** Takes a predicate and yields a parser that consumes a single character
    * if it satisfies the predicate, and fails otherwise.
    */
  def satisfy(p: Char => Boolean): Parser[Char] = {
    item.flatMap(x => {
      if (p(x)) {
        succeed(x)
      } else {
        fail(NoParseError)
      }
    })
  }

  /** Run the first parser. On success, return the parsed value, along with the
    * remaining input. Otherwise, on failure, run the second parser with the original input
    * and in this case, return (success or failure) from the second parser.
    */
  def and[A](p1: Parser[A], p2: => Parser[A]): Parser[(A, A)] = {
    for {
      x <- p1
      y <- p2
    } yield (x, y)
  }

  def or[A](p1: Parser[A], p2: => Parser[A]): Parser[A] = {
    (input: String) =>
      {
        p1(input) match {
          case res @ Right(_) =>
            res
          case _ =>
            p2(input) match {
              case res @ Right(_) =>
                res
              case err =>
                err
            }
        }
      }
  }

  def apply[A](f: String => ParsingResult[A]): Parser[A] = {
    (input: String) => f(input)
  }

  def run[A](p: Parser[A]): String => ParsingResult[A] = {
    (input: String) => p(input)
  }

  /** The succeed parser always succeeds, without actually consuming any of the input string.
    * Since the outcome of succeed does not depend upon its input, its result
    * value must be pre–determined, so is included as an extra parameter
    */
  def succeed[A](v: A): Parser[A] = {
    (input: String) => Right((v, input))
  }

  /** It always fails, regardless of the input string.
    */
  def fail[A](error: ParsingError): Parser[A] = {
    (_: String) => Left(error)
  }

  def item: Parser[Char] = {
    (input: String) =>
      if (input.isEmpty) {
        Left(NoInputError)
      } else {
        val (first, remaining) = splitAtHead(input)
        Right((first, remaining))
      }
  }

  def word: Parser[String] = {
    def neWord: Parser[String] = for {
      x <- letter
      xs <- word
    } yield s"$x$xs"

    neWord or succeed("")
  }

  def char(charToMatch: Char): Parser[Char] = {
    satisfy(_ == charToMatch)
  }

  def digit: Parser[Char] = {
    satisfy(_.isDigit)
  }

  def lower: Parser[Char] = {
    satisfy(_.isLower)
  }

  def upper: Parser[Char] = {
    satisfy(_.isUpper)
  }

  def letter: Parser[Char] = {
    lower or upper
  }

  def alphanum: Parser[Char] = {
    letter or digit
  }

  private def splitAtHead(s: String): (Char, String) = {
    (s.take(1).head, s.drop(1))
  }
}