CODEWITHSUNDEEP
scalasbt
mpilquist
mpilquist

Reputation: 3855

Repeating dependent parsers with Scala/SBT parser combinators

Parsing a string of the form Value[,Value]+ can be easily accomplished via rep1sep(Value, ','). Is there a way to achieve rep1sep functionality when the Value parser is dependent on the previously parsed Values in the repetition? For example, enforcing a requirement that each value must be unique?

The standard technique for dependent parsers is flatMap, but I am having trouble getting that working. Here's one such attempt:

def Values(soFar: Set[Value]): Parser[Set[Value]] =
  Value(soFar) flatMap { v => (',' ~> Values(soFar + v)).?.map { _ getOrElse soFar } }

def Value(soFar: Set[Value]): Parser[Value] =
  Num+ flatMap { v => if (soFar.contains(v)) failure("%d already appears".format(v)) else success(v) }

Generically, I need a form of rep1sep where the parser argument is a function from Seq[A] to Parser[A]:

def rep1sepDependent(rep: Seq[A] => Parser[A], sep: Parser[Any]): Seq[A] = ???

Note: I realize the use case is questionable here and that validating uniqueness is better handled post parsing. I've encountered this problem while using the SBT parsing combinators for the purpose of tab completion -- specifically, I'd like to present completion options for key/value pairs for only those keys that the user has not already entered. See this parser for a full example and buildable SBT project.

Upvotes: 4

Views: 671

Answers (2)

david.perez
david.perez

Reputation: 7012

Here is a solution for selecting some items with assisted completion, avoiding duplicated items:

def select1(items: Iterable[String], separator: Parser[_] = Space) =
  token(separator ~> StringBasic.examples(FixedSetExamples(items)))

def selectSome(items: Seq[String], separator: Parser[_] = Space): Parser[Seq[String]] = {
   select1(items, separator).flatMap { v ⇒
   val remaining = items filter { _ != v }
   if (remaining.size == 0)
     success(v :: Nil)
   else
     selectSome(remaining).?.map(v +: _.getOrElse(Seq()))
 }

}

Example of use:

val myTask = inputTask[Unit]("Print selected numbers")
myTask := {
  val numbers = selectSome(Seq("One", "Two", "Three", "Four")).parsed
  numbers.foreach{ println _ }
}

Tested with SBT 0.13.9.

Upvotes: 0

Travis Brown
Travis Brown

Reputation: 139028

The following isn't quite as generic as your rep1sepDependent, but it works:

def rep1sepUnique[T](p: => Parser[T], q: => Parser[Any]) = {
  def checkIfSeen(seen: Set[T]): Parser[Set[T]] = q ~> p >> (v =>
    if (seen(v)) failure("Duplicate: %s".format(v)) else checkIfSeen(seen + v)
  ) | success(seen)
  p >> (v => checkIfSeen(Set(v)))
}

For example:

import scala.util.parsing.combinator._

object parseUniqueWords extends RegexParsers {
  def rep1sepUnique[T](p: => Parser[T], q: => Parser[Any]) = {
    def checkIfSeen(seen: Set[T]): Parser[Set[T]] = q ~> p >> (v =>
      if (seen(v)) failure("Duplicate: %s".format(v)) else checkIfSeen(seen + v)
    ) | success(seen)
    p >> (v => checkIfSeen(Set(v)))
  }

  def apply(s: String) = parseAll(rep1sepUnique("\\w+".r, ","), s)
}

Which gives us:

scala> parseUniqueWords("aaa,bb,c")
res0: parseUniqueWords.ParseResult[Set[String]] = [1.9] parsed: Set(aaa, bb, c)

scala> parseUniqueWords("aaa,bb,aaa")
res1: parseUniqueWords.ParseResult[Set[String]] = 
[1.11] failure: Duplicate: aaa

aaa,bb,aaa
          ^

Which is what we want.

Upvotes: 4

Related Questions