.O.
..O Deniz's personal pages
OOO
/home /about

A simple query evaluator

January 27, 2020

For a feature that I’m building I needed to code up a parser that will take in a JSON structured query and run it against a graph of objects to get the ones that match.

The query format is similar to the MongoDB query format and looks something like this:

let input:[String: Any] = [

"p1": 1,

"$or": [["p2": 1], ["$and": [ ["p5": 5], ["p3": 3]]]]

]

This means I need the nodes that have p1 property set to 1 AND either p2 set to 1 or p5 and p3 set to 5 and 3 respectively.

The format of the query is already a AST so just need to traverse it and evaluate the result as we do the traversal.

Here’s an example node

let model:[String: Int] = [

"p1": 1,

"p2": 2,

"p3": 4,

"p5": 5

]

Solution

Here’s the traversal code (simplified for the article but the main idea is there)

func resolve(input: [String: Any], model: [String: Int]) -> [Bool] {

 return _resolve(input: input, model: model).allSatisfy { $0 }

}

func _resolve(input: [String: Any], model: [String: Int]) -> [Bool] {

 var results = [Bool]()

 for (key, value) in input {

  if let value=value as? Int {

   let result = model[key] == value

   results.append(result)

 }

switch key {

case "$and":

 if let value = value as? Array<[String: Any]> {

  let result = value.allSatisfy() {

   _resolve(input: $0, model: model)

  }

  results.append(result)

  } else {

   print("$and needs an array")

   throw Error

  }

case "$or":

 if let value = value as? Array<[String:Any]> {

  let result = value.contains {

   _resolve(input: $0, model: model)

  }

  results.append(result)

 } else {

  print("$or needs an array")

  throw Error

 }

default:

 break

 }

}

return results

}

With the example model the result will be false. But change the query to

let input:[String: Any] = [ "p1": 1, "$or": "p2": 1], ["$and": [ ["p5": 5], ["p3": 4]] ]

and it will be true.

The idea here is to reduce each sub query in the $or/$and keys down to a single boolean value and at the end reduce that down to a single value as the top level predicates have an implied and.

so

let input:[String: Any] = [

"p1": 1,

"$or": [["p2": 1], ["$and": [ ["p5": 5], ["p3": 4]]]]

]

becomes

let input:[String: Any] = [

"p1": true,

"$or": [["p2": 1], ["$and": [ ["p5": 5], ["p3": 4]]]]

]

then

let input:[String: Any] = [

"p1": true,

"$or": [true, ["$and": [ ["p5": 5], ["p3": 4]]]]

]

then

let input:[String: Any] = [

"p1": true,

"$or": [true, true]

]

next

let input:[String: Any] = [

"p1": true,

"$or": true

]

and finally the top level is calculated as true.

Tags: #programming