/*
 * Copyright (c) 2019, Daniel Spiewak
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the copyright holder nor the names of its contributors
 *    may be used to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

import com.codecommit.gll._

import org.specs2.ScalaCheck
import org.specs2.mutable._
import org.specs2.specification.SpecificationFeatures

object CompoundSpecs extends Spec
    with SpecificationFeatures
    with Parsers
    with ScalaCheck {

  import StreamUtils._

  "compound non-terminal parsers" should {
    "parse an unambiguous right-recursive grammar" in {
      lazy val p: Parser[String] = (
          "a" ~ p ^^ { _ + _ }
        | "a"
      )

      // assumes data =~ /a+/
      def check(data: String) = p(data) must beLike { case Success(`data`, LineStream()) #:: SNil => ok }

      p must not(throwA[Throwable])

      check("a")
      check("aa")
      check((0 to 256).foldLeft("") { (s, _) => s + "a" })
      check("aaaaa")
    }

    "parse an LL(1) right-recursive grammar" in {
      lazy val p: Parser[String] = (
          "a" ~ p ^^ { _ + _ }
        | "b"
      )

      // assumes data =~ /a+/
      def check(data: String) = p(data) must beLike { case Success(`data`, LineStream()) #:: SNil => ok }

      p must not(throwA[Throwable])

      check("b")
      check("ab")
      check((0 to 256).foldLeft("") { (s, _) => s + "a" } + "b")
      check("aaaab")
    }

    "parse an unambiguous left-recursive grammar (recursive-major)" in {
      lazy val p: Parser[String] = (
          p ~ "a" ^^ { _ + _ }
        | "a"
      )

      // assumes data =~ /a+/
      def check(data: String) = p(data) must beLike { case Success(`data`, LineStream()) #:: SNil => ok }

      p must not(throwA[Throwable])

      check("a")
      check("aa")
      check((0 to 256).foldLeft("") { (s, _) => s + "a" })
      check("aaaaa")
    }

    "parse an unambiguous left-recursive grammar (recursive-minor)" in {
      lazy val p: Parser[String] = (
          "a"
        | p ~ "a" ^^ { _ + _ }
      )

      // assumes data =~ /a+/
      def check(data: String) = p(data) must beLike { case Success(`data`, LineStream()) #:: SNil => ok }

      p must not(throwA[Throwable])

      check("a")
      check("aa")
      check((0 to 256).foldLeft("") { (s, _) => s + "a" })
      check("aaaaa")
    }

    "parse Gamma_1" in {
      val b = "" | "a"

      lazy val c: Parser[String] = (
          "b"
        | b ~ c ~ "b" ^^ { _ + _ + _ }
        | "b" ~ "b"  ^^^ "bb"
      )

      val s = (
          c ~ "a" ^^ { _ + _ }
        | "d"
      )

      // assumes data =~ /a+/
      def check(data: String) = s(data) must beLike { case Success(`data`, LineStream()) #:: _ => ok }    // we don't care how many derivations, just that it works

      s must not(throwA[Throwable])

      check("abba")
      check("bbbbbbba")
      check("d")
      check("aaaaaaaabbbbbbbbba")

      val prefix = (0 to 20).foldLeft("") { (str, _) => str + "a" }
      val suffix = (0 to 50).foldLeft("") { (str, _) => str + "b" }
      check(prefix + suffix + "a")

      check("bba")
    }

    "parse Gamma_2" in {
      lazy val s: Parser[String] = (
          "b"
        | s ~ s     ^^ { _ + _ }
        | s ~ s ~ s ^^ { _ + _ + _ }
      )

      // assumes data =~ /a+/
      def check(data: String) = s(data) must beLike { case Success(`data`, LineStream()) #:: _ => ok }    // we don't care how many derivations, just that it works

      s must not(throwA[Throwable])

      check("b")
      check("bb")
      check((0 to 50).foldLeft("") { (str, _) => str + "b" })
      check("bbbbb")
    }

    "parse Gamma_2*" in {
      lazy val s: Parser[String] = (
          "b"
        | s ~ s ~ (s | "") ^^ { _ + _ + _ }
      )

      // assumes data =~ /a+/
      def check(data: String) = {
        s(data) must beLike {
          case Success(`data`, LineStream()) #:: _ => ok     // we don't care how many derivations, just that it works
        }
      }

      s must not(throwA[Throwable])

      check("b")
      check("bb")
      check((0 to 50).foldLeft("") { (str, _) => str + "b" })
      check("bbbbb")
    }

    "parse an unambiguous arithmetic grammar" in {
      object MathParser extends RegexParsers {
        lazy val expr: Parser[Int] = (
            expr ~ "+" ~ term     ^^ { (e1, _, e2) => e1 + e2 }
          | expr ~ "-" ~ term     ^^ { (e1, _, e2) => e1 - e2 }
          | term
        )

        lazy val term: Parser[Int] = (
            term ~ "*" ~ factor   ^^ { (e1, _, e2) => e1 * e2 }
          | term ~ "/" ~ factor   ^^ { (e1, _, e2) => e1 / e2 }
          | factor
        )

        lazy val factor: Parser[Int] = (
            "(" ~> expr <~ ")"
          | "-" ~> factor         ^^ { -_ }
          | """\d+""".r           ^^ { _.toInt }
        )
      }

      val input = """1 + 6 / 3 * 2
                     - -2 + 3 /

                     (1 + 2)"""

      MathParser.expr(input) must beLike {
        case Success(8, LineStream()) #:: SNil => ok
      }
    }

    "produce all possible results with recursive ambiguity" in {
      object ConfigParser extends RegexParsers {
        override val whitespace = """[ \t]+"""r  // process newlines separately

        lazy val parser = """\s*""".r ~> config <~ """\s*""".r     // allow leading/trailing whitespace

        private lazy val config = (pairs <~ newline).? ~ sections ^^ { _.getOrElse(Map()) ++ _ }

        private lazy val sections: Parser[Map[String, String]] = (
            sections ~ newline ~ section  ^^ { (map1, _, map2) => map1 ++ map2 }
          | section
          | ""                            ^^^ Map()
        )

        private lazy val section = ("[" ~> id <~ "]") ~ newline ~ config ^^ { (id, _, map) =>
          val back = for ((key, value) <- map) yield (id + '.' + key) -> value
          back.foldLeft(Map[String, String]()) { _ + _ }
        }

        private lazy val pairs: Parser[Map[String, String]] = (
            pairs ~ newline ~ pair    ^^ { (map, _, tuple) => map + tuple }
          | pair                      ^^ { Map(_) }
        )

        private lazy val pair = id ~ "=" ~ data    ^^ { (key, _, value) => key -> value }

        private val id = """\w+"""r
        private val data = """[^\s]+"""r
        private val newline = """(\n\r|\r\n|\n|\r)"""r
      }

      val input = """
[core]
    version = 0
    filemode = true

[remote]
    url = hero
    fetch = boo
"""

      ConfigParser.parser(input) must beLike {
        case Success(map1, _) #:: Success(map2, _) #:: SNil => {
          if (map1 contains "core.remote.url") {
            map1 must haveKey("core.filemode")
            map1 must haveKey("core.remote.fetch")
            map1 must not(haveKey("remote.url"))

            map2 must haveKey("remote.url")
            map2 must haveKey("core.filemode")
            map2 must not(haveKey("core.remote.fetch"))
          } else {
            map1 must haveKey("remote.url")
            map1 must haveKey("core.filemode")
            map1 must not(haveKey("core.remote.fetch"))

            map2 must haveKey("core.filemode")
            map2 must haveKey("core.remote.fetch")
            map2 must not(haveKey("remote.url"))
          }
        }
      }
    }

    "avoid greedy matching on a local ambiguity" in {
      sealed trait Expr

      case class Binding(formals: Vector[String]) extends Expr
      case class TicVar(id: String) extends Expr
      case class Dispatch(actuals: Vector[Expr]) extends Expr

      object TestParser extends RegexParsers {
        lazy val expr: Parser[Expr] = (
            "(" ~ formals ~ ")" ~ ":=" ^^ { (_, fs, _, _) => Binding(fs) }
          | "(" ~ expr ~ ")" ^^ { (_, as, _) => Dispatch(Vector(as)) }
          | ticId ^^ TicVar
        )

        lazy val formals: Parser[Vector[String]] = (
            formals ~ "," ~ ticId ^^ { (fs, _, f) => fs :+ f }
          | ticId                 ^^ { Vector(_) }
        )

        val ticId = "a"
      }

      TestParser.expr("(a) :=") must not(throwA[ClassCastException])
    }

    "compute FIRST for nested left-recursion" in {
      object ComplexParser extends RegexParsers {
        lazy val exp: Parser[Any] = (
            n
          | "(" ~ commaExps ~ ")"
          | exp ~ exp
        ) ^^^ null

        lazy val commaExps: Parser[Any] = (
            exp
          | commaExps ~ "," ~ exp
        )

        val n = """\d+"""r
      }

      ComplexParser.exp.first must containAllOf(List('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ' ', '\t', '\n', '\r', '('))
    }

    "handle nested left-recursion" in {
      object ComplexParser extends RegexParsers {
        lazy val exp: Parser[Any] = (
            n
          | "(" ~ commaExps ~ ")"
          | exp ~ exp
        ) ^^^ null

        lazy val commaExps: Parser[Any] = (
            exp
          | commaExps ~ "," ~ exp
        )

        val n = """\d+"""r
      }

      import ComplexParser._

      exp("(0,0) 2") must beLike {
        case Success(_, LineStream()) #:: SNil => ok
      }
    }

    "negate using a terminal parser" in {
      val p1 = "test" \ "test"

      p1("test") must beLike {
        case Failure(SyntaxError, LineStream(tail @ _*)) #:: SNil =>
          tail.mkString mustEqual "test"
      }

      val p2 = "test" \ "ing"

      p2("test") must beLike {
        case Success("test", LineStream()) #:: SNil => ok
      }
    }

    "negate within a sequence" in {
      import RegexParsers._

      // Formerly:
      // val p = ("a|b".r \ "a") ~ "c" ^^ (_ + _)
      //
      // The explicit call to RegexParsers.funSyntax2 is necessary in 2.10 to
      // deal with the consequences of implicit ambiguity: we are in a class
      // which inherits from Parsers (and so inherits an implicit funSyntax2)
      // but within a nested scope, importing RegexParsers._ brings in another
      // implicit funSyntax2, and that's the one we need.
      //
      // The change in 2.10, which is at least ostensibly a bug fix, is to
      // consistently apply the rule that if a method cannot be called explicitly,
      // then it cannot be called implicitly. And indeed in both 2.9 and 2.10,
      // an attempt to call funSyntax2 without qualification is an error:
      //
      // [error] CompoundSpecs.scala:359: reference to funSyntax2 is ambiguous;
      // [error] it is both defined in trait Parsers and imported subsequently by
      // [error] import RegexParsers._
      // [error]       val p = /*RegexParsers.*/funSyntax2(("a|b".r \ "a") ~ "c") ^^ (_ + _)
      // [error]                                ^
      //
      // Unfortunately rather than reporting the ambiguity, it reports its
      // confusion at trying to type "_ + _" when it wasn't able to work out
      // what method is being called with that as an argument. So it would
      // articulate the issue like this:
      //
      // [error] CompoundSpecs.scala:359: missing parameter type for expanded function ((x$53, x$54) => x$53.$plus(x$54))
      // [error]       val p = ("a|b".r \ "a") ~ "c" ^^ (_ + _)
      // [error]                                         ^
      //
      // The fully qualified, works in 2.9 and 2.10 formulation:
      val p = RegexParsers.funSyntax2(("a|b".r \ "a") ~ "c") ^^ (_ + _)

      p("bc") must beLike {
        case Success("bc", LineStream()) #:: SNil => ok
      }

      p("ac") must beLike {
        case Failure(SyntaxError, _) #:: _ => ok
      }
    }

    "correctly globally disambiguate a local sequence ambiguity" in {
      lazy val expr: Parser[Any] = (
          id ~ ":=" ~ expr ~ expr
        | num
      )

      lazy val id = "a" | "b" | "c"
      lazy val num = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"

      expr("a:=1c:=23") must beLike {
        case Success(_, LineStream()) #:: SNil => ok
      }
    }

    "successfully process a peculiar mutual left-recursion" in {
      lazy val expr: Parser[Any] = (
          prefix ~ "b"
        | "a"
        | expr ~ "+"
      )

      lazy val prefix: Parser[Any] = (
          prefix ~ ","
        | expr ~ ","
      )

      expr("") must not(beEmpty)
    }
  }

  "repeated non-terminal parsers" should {
    "repeat 0..n times" in {
      val p = literal("123")*

      p("123") must beLike {
        case Success(List("123"), LineStream()) #:: SNil => ok
      }

      p("123123123123123123123123123123123") must beLike {
        case Success(List("123", "123", "123", "123", "123", "123", "123", "123", "123", "123", "123"), LineStream()) #:: SNil => ok
      }

      p(LineStream()) must beLike {
        case Success(Nil, LineStream()) #:: SNil => ok
      }
    }
    "repeat 0..n times with separator" in {
      val p = literal("123") * ","

      p("123") must beLike {
        case Success(List("123"), LineStream()) #:: SNil => ok
      }

      p("123,123,123,123,123,123,123,123,123,123,123") must beLike {
        case Success(List("123", "123", "123", "123", "123", "123", "123", "123", "123", "123", "123"), LineStream()) #:: SNil => ok
      }

      p(LineStream()) must beLike {
        case Success(Nil, LineStream()) #:: SNil => ok
      }
    }

    "repeat 1..n times" in {
      val p = literal("123")+

      p("123") must beLike {
        case Success(List("123"), LineStream()) #:: SNil => ok
      }

      p("123123123123123123123123123123123") must beLike {
        case Success(List("123", "123", "123", "123", "123", "123", "123", "123", "123", "123", "123"), LineStream()) #:: SNil => ok
      }
    }

    "repeat 1..n times with separator" in {
      val p = literal("123") + ","

      p("123") must beLike {
        case Success(List("123"), LineStream()) #:: SNil => ok
      }

      p("123,123,123,123,123,123,123,123,123,123,123") must beLike {
        case Success(List("123", "123", "123", "123", "123", "123", "123", "123", "123", "123", "123"), LineStream()) #:: SNil => ok
      }
    }

    "repeat 0..1 times" in {
      val p = literal("123")?

      p("123") must beLike {
        case Success(Some("123"), LineStream()) #:: SNil => ok
      }

      p(LineStream()) must beLike {
        case Success(None, LineStream()) #:: SNil => ok
      }
    }

    "repeat 1..n times with optional parser as first component" in {
      val p = ("-".? ~> "1")+

      p("11") must beLike {
        case Success(List("1", "1"), LineStream()) #:: SNil => ok
      }
      p("-11") must beLike {
        case Success(List("1", "1"), LineStream()) #:: SNil => ok
      }
      p("1-1") must beLike {
        case Success(List("1", "1"), LineStream()) #:: SNil => ok
      }
      p("-1-1") must beLike {
        case Success(List("1", "1"), LineStream()) #:: SNil => ok
      }
      p("1-1-1") must beLike {
        case Success(List("1", "1", "1"), LineStream()) #:: SNil => ok
      }
    }
  }

  "monadic parsers" should {
    "compose using bind" in {
      val p = literal("a") flatMap { _ => literal("b") }

      p(LineStream('a', 'b')) must beLike {
        case Success("b", LineStream()) #:: SNil => ok
      }

      p(LineStream('a', 'c')) must beLike {
        case Failure(ExpectedLiteral("b", "c"), LineStream('c')) #:: SNil => ok
      }

      p.first mustEqual Set('a')
    }

    "compose using map" in {
      val p = literal("1") map { _.toInt }

      p(LineStream('1')) must beLike {
        case Success(1, LineStream()) #:: SNil => ok
      }

      p(LineStream('2')) must beLike {
        case Failure(ExpectedLiteral("1", "2"), LineStream('2')) #:: SNil => ok
      }

      p.first mustEqual Set('1')
    }

    "compose using orElse" in {
      val p = literal("a") orElse literal("b")

      p(LineStream('a')) must beLike {
        case Success("a", LineStream()) #:: SNil => ok
      }

      p(LineStream('b')) must beLike {
        case Success("b", LineStream()) #:: SNil => ok
      }

      p(LineStream('c')) must beLike {
        case Failure(UnexpectedChars("c"), LineStream('c')) #:: SNil => ok
      }

      p.first mustEqual Set('a', 'b')
    }

    "filter" in {
      val p = ("a" | "b") filter { _ == "a" }

      p(LineStream('a')) must beLike {
        case Success("a", LineStream()) #:: SNil => ok
      }

      p(LineStream('b')) must beLike {
        case Failure(SyntaxError, LineStream('b')) #:: SNil => ok
      }

      p(LineStream('c')) must beLike {
        case Failure(UnexpectedChars("c"), LineStream('c')) #:: SNil => ok
      }

      p.first mustEqual Set('a', 'b')
    }
  }
}
