A simple query evaluator
January 27, 2020For 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