Tree Search Language (TSL)

Tree Search Language (TSL) is a wonderful search language, With similar grammar to SQL's where part. implementing query based search engines was never that easy.

[ awesome image by gophers... ]

The TSL language grammar is similar to SQL syntax.

Syntax examples

Operator precedence

name like '%joe%' and (city = 'paris' or city = 'milan')

Operators with multiple arguments

name in ('joe', 'jane') and grade not between 0 and 50

Math operators

memory.total - memory.cache > 2000 and cpu.usage > 50

More math operators

(net.rx + net.tx) / 1000 > 3 or net.rx / 1000 > 6

For code examples see the cli tools in the /cmd direcotry.

ParseTSL

The TSL package include the ParseTSL method for parsing TSL into a search tree:

tree, err := tsl.ParseTSL("name in ('joe', 'jane') and grade not between 0 and 50")

After parsing the TSL tree will look like this (image created using the tsl_parser cli utility using .dot output option):

SquirrelWalk

The TSL package include a helper SquirrelWalk method that adds search to squirrel's SelectBuilder object:

// Prepare squirrel filter.
filter, err := tsl.SquirrelWalk(tree)

// Create an SQL query.
sql, args, err := sq.Select("name", "city", "state").
    From("users").
    Where(filter).
    ToSql()

After SQL generation the sql and args vars will be:

SELECT name, city, state FROM users WHERE (name IN (?,?) AND grade NOT BETWEEN ? AND ?)

["joe", "jane", 0, 50]

BSONWalk

The TSL package include a helper BSONWalk method that adds search bson filter to mongo-go-driver:

// Prepare a bson filter.
filter, err = tsl.BSONWalk(tree)

// Run query.
cur, err := collection.Find(ctx, bson.NewDocument(filter))

GraphvizWalk

The TSL package include a helper GraphvizWalk method that exports .dot file nodes :

// Prepare .dot file nodes as a string.
s, err = tsl.GraphvizWalk("", tree, "")

// Wrap the nodes in a digraph wrapper.
s = fmt.Sprintf("digraph {\n%s\n}\n", s)

Cli tools

tls_parser, tls_mongo and tsl_sqlite are example cli tools showcasing the TSL language and TSL golang package.

tls_parser

$ ./tsl_parser -h
Usage of ./tls_parser:
  -i string
    	the tsl string to parse (e.g. "animal = 'kitty'")
  -o string
    	output format [json/yaml/prettyjson/sql/dot] (default "json")

$ ./tsl_parser -i "(name = 'joe' or name = 'jane') and city = 'rome'" -o sql

sql:  SELECT * FROM table_name WHERE ((name = ? OR name = ?) AND city = ?)
args: [joe jane rome]

./tsl_parser -i "(name = 'joe' or name = 'jane') and city = 'rome'" -o prettyjson

{
  "func": "$and",
  "left": {
    "func": "$or",
    "left": {
      "func": "$eq",
      "left": {
        "func": "$ident",
        "left": "name"
      },
      "right": {
        "func": "$string",
        "left": "joe"
      }
    },
    "right": {
      "func": "$eq",
      "left": {
        "func": "$ident",
        "left": "name"
      },
      "right": {
        "func": "$string",
        "left": "jane"
      }
    }
  },
  "right": {
    "func": "$eq",
    "left": {
      "func": "$ident",
      "left": "city"
    },
    "right": {
      "func": "$string",
      "left": "rome"
    }
  }
}

./tsl_parser -i "city = 'rome'" -o dot

digraph {
root [shape=box color=black label="$eq"]
XVlB [shape=record color=red label="$ident | 'city'" ]
zgba [shape=record color=blue label="$string | 'rome'" ]
root -> { XVlB, zgba }
}

tsl_mongo

tsl_mongo include an example using BSONWalk method, for building a mongo bson filter.

$ ./tsl_mongo -h
Usage of ./tsl_mongo:
  -c string
    	collection name to query on (default "books")
  -d string
    	db name to connect to (default "tsl")
  -i string
    	the tsl string to parse (e.g. "author = 'Jane'") (default "title is not null")
  -p	prepare a book collection for queries
  ...
  -u string
    	url for mongo server (default "mongodb://localhost:27017")

$ ./tsl_mongo -p -i "title is not null" | jq

{
  "_id": {
    "$oid": "5b8999c0f678c456481f7baf"
  },
  "title": "Book",
  "author": "Joe",
  "spec": {
    "pages": {
      "$numberLong": "100"
    },
    "Rating": {
      "$numberLong": "4"
    }
  }
}

$ ./tsl_mongo -i "title ~= 'Other' and spec.rating > 1" | jq

{
  "_id": {
    "$oid": "5b899a6c3707c8ba0b00b656"
  },
  "title": "Other Book",
  "author": "Jane",
  "spec": {
    "pages": {
      "$numberLong": "200"
    },
    "Rating": {
      "$numberLong": "3"
    }
  }
}

tsl_sqlite

./tsl_sqlite -h
Usage of ./tsl_sqlite:
  -f string
    	the sqlite database file name (default "./sqlite.db")
  -i string
    	the tsl string to parse (e.g. "Title = 'Book'")
  -p	prepare a book collection for queries

$ SQL="Title like '%Book%' and Pages > 100"
$ ./tsl_sqlite -i "$SQL" -p

Creating table.
Insert demo books.
{2 Other Book Jane 200 3}
{5 Good Book Joe 150 4}

Grammar

Antlr4 grammar

TSL is generated using Antlr4 tool, the antlr4 grammar file is TSL.g4.

Keywords

and or not is null like between in

Operators

= <= >= != ~= ~! <> + - * / %

Examples

name = 'Joe'

city in ('paris', 'rome', 'milan') or sate = 'spain'

(name = 'joe' or city = 'rome') and state = 'italy'

net.tx + net.rx > 2000 or mem.total - mem.usage < 1000

Code snippets

import "github.com/yaacov/tsl/pkg/tsl"

ParseTSL

ParseTSL takes a string input and generate a search tree object, the function returns the root Node of the tree.

...
// Set a TSL input string.
input = "name='joe' or name='jane'"

// Parse input string into a TSL tree.
tree, err := tsl.ParseTSL(input)
...

SquirrelWalk

SquirrelWalk and BSONWalk are example methods the demonstrate traversing ( walk ) the search tree.

SquirrelWalk takes the base Node ( tree ) of the search tree, and return a Squirrel SQL filter object.

import (
    ...
    sq "github.com/Masterminds/squirrel"
    "github.com/yaacov/tsl/pkg/tsl"
    ...
)
...
// Set filter.
filter, err := tsl.SquirrelWalk(tree)

// Convert TSL tree into SQL string using squirrel select builder.
sql, args, err := sq.Select("name, city, state").
    From("users").
    Where(filter).
    ToSql()
...

BSONWalk

BSONWalk takes the base Node ( tree ) of the search tree, and return a MongoDB BSON object.

...
// Prepare a bson filter.
filter, err = tsl.BSONWalk(tree)

// Run query.
cur, err := collection.Find(ctx, bson.NewDocument(filter))
defer cur.Close(ctx)

// Loop on query elements.
for cur.Next(ctx) {
    ...