Skip to content

Parser combinators creating functions for DSL execution

by Frank Sauer on April 21st, 2015

Last year in August I wrote about creating an Alerting DSL using Scala parser combinators. We are currently in the process of upgrading our metrics collection and alerting system to InfluxDB 0.9 which introduced tags and the need for us to compare a set of tag values in order to decide whether to fire an alert or not. Previously all information to make this decision was encoded in the series name, but now series names are very simple. They are just the name of the measurements, for example HeapSize. All the information about where the measurement came from is now encoded in tags like , host, process, etc.

Comparing the values in a set of tags with constants written in a rule sounds a lot like something we all know very well: SQL where clauses… So let’s see how we can parse a where clause into a function that we can evaluate on a set of tag values. We would also like to support complex logical expressions using AND and OR as well as the SQL “like” operator, which in our case does a regular expression match.

Let’s start with the test case demonstrating the resulting API:

"AlertRule" should {
    "include a filter when a where clause is present" in new AlertFixture {
      val rule: Seq[AlertRule] = AlertRule("""
          Rule1: 
            when /somemeasurement.*/ > 1000 MB 
            for 30 seconds
            where name="bla" and whatever like /foo.*/ 
            alert (name="boo")
      """)

      rule.length shouldEqual(1) // we specified a single rule in the DSL  
      rule(0).filter match {     // it has a where clause so there must be a filter
        case Some(filter) => // execute the filter on some good and bad data
          filter(Map("name" -> "bla", "whatever"->"fooBar")) shouldEqual(true)
          filter(Map("name" -> "bla", "whatever"->"goober")) shouldEqual(false)
          filter(Map("name" -> "boo", "whatever"->"fooBar")) shouldEqual(false)
        case _ => failure("filter should have been defined with a given where clause")
      }
    }
}

What this test case shows us is that if we have a rule with a where clause (they’re optional) then the resulting AlertRule should contains a filter function and this filter function takes a Map of tags as its parameter and applying it results in a Boolean which is true if the set of tags makes the entire where clause evaluate to true. Please refer to the previous post for details on the rest of the DSL and the AlertRule case class and parser.

Let’s see how we parse this where clause from the top down, ignoring the where keyword itself. The expression that follows it is defined by this rule:

    // combine where-clause conjunctions with logical or
    def disjunction: Parser[(Map[String,String])=>Boolean] = 
        conjunction ~ ("or" ~> conjunction).* ^^ {
          case head ~ tail =>  tail.foldLeft(head) {
            case (left,right) => (tags:Map[String,String]) => left(tags) || right(tags)
        }
    }

What we see here is that the top level expression combines 1 or more conjunctions using a logical ‘or’ operator and the result is a boolean function that accepts a Map with tags. Note that left and right (the conjunctions) are also parsers that return a boolean function so the result is simply a function that takes tags and combines left and right using || and propagating the tag collection to both. The foldLeft repeats this for every conjunction in the list.

Conjunctions look very similar, except they use && to combine left and right:

    // combine where clause relations with and
    def conjunction: Parser[(Map[String,String])=>Boolean] = 
        relation ~ ("and" ~> relation).* ^^ {
           case head ~ tail =>  tail.foldLeft(head) {
              case (left,right) => (tags: Map[String,String]) => left(tags) && right(tags)
      }
    }

Separating the parsing into disjunctions and conjunctions will give the proper precedence to the and and or operators. At the lowest level in our where-clause parse tree we find relations. This is where the actual comparison of tags takes place:

    def relEq:Parser[(Map[String,String])=>Boolean] = ident ~ "=" ~ stringLiteral ^^ {
      case left ~ "=" ~ right =>
        (tags: Map[String,String]) => {  
          val k = tags.get(left)         
          k match {
            // if left-hand side not found in the tags, the result is false, 
            // otherwise v has to be equal to value specified in rule after dropping 
            // leading and trailing double quote we get from using stringLiteral
            case Some(v) => v == right.drop(1).dropRight(1)   
            case _ => false
          }
        }
    }

    // reuse the regex parser we already had back in August
    def relLike:Parser[(Map[String,String])=>Boolean] = ident ~ "like" ~ regex ^^ {
      case left ~ "like" ~ right =>
        (tags: Map[String,String]) => {
          val k = tags.get(left)
          k match {  
            // if left-hand side not found in the tags, the result is false, 
            // otherwise v has to be match the regex specified in rule
            case Some(v) => right.findFirstMatchIn(v).nonEmpty
            case _ => false
          }
        }

    }

    // parses a simple comparison in a where clause (tag = "value" or tag like /regex/)
    def relation: Parser[(Map[String,String])=>Boolean] = relEq | relLike    
    

There are two cases here, one for simple comparison (relEq) and one for the like operator (relLike). They both have to also deal with the case where the tag key specified in the DSL is not actually found in the set of tags being evaluated. I’m sure there’s a nice refactoring hiding in here somewhere…

Once again I hope I’ve demonstrated the incredible power and versatility of the Scala parser combinators. I especially like parsers that build functions as shown here. The way conjunctions and disjunctions combine simple comparisons into bigger and bigger logical expressions that can be evaluated later when we’re streaming measurements through the rules is just the coolest thing ever.

From → programming, scala

No comments yet

Leave a Reply

You must be logged in to post a comment.