logic-expression-parser

This library provide generic boolean expression parser to go structures.

Installation

$ go get -u github.com/mgudov/logic-expression-parser

(optional) Run unit tests

$ make test

(optional) Run benchmarks

$ make bench

Examples

package main

import (
	"github.com/davecgh/go-spew/spew"
	lep "github.com/mgudov/logic-expression-parser"
)

func main() {
	expression := `a=false && b>=c && (d<1000 || e in [1,2,3])`

	result, err := lep.ParseExpression(expression)
	if err != nil {
		panic(err)
	}

	dump := spew.NewDefaultConfig()
	dump.DisablePointerAddresses = true
	dump.DisableMethods = true
	dump.Dump(result)
}

This library would parse the expression and return the following struct:

(*lep.AndX)({
  Conjuncts: ([]lep.Expression) (len=3 cap=4) {
    (*lep.EqualsX)({
      Param: (*lep.ParamX)({
        Name: (string) (len=1) "a"
      }),
      Value: (*lep.BooleanX)({
        Val: (bool) false
      })
    }),
    (*lep.GreaterThanEqualX)({
      Param: (*lep.ParamX)({
        Name: (string) (len=1) "b"
      }),
      Value: (*lep.ParamX)({
        Name: (string) (len=1) "c"
      })
    }),
    (*lep.OrX)({
      Disjunctions: ([]lep.Expression) (len=2 cap=2) {
        (*lep.LessThanX)({
          Param: (*lep.ParamX)({
            Name: (string) (len=1) "d"
          }),
          Value: (*lep.IntegerX)({
            Val: (int64) 1000
          })
        }),
        (*lep.InSliceX)({
          Param: (*lep.ParamX)({
            Name: (string) (len=1) "e"
          }),
          Slice: (*lep.SliceX)({
            Values: ([]lep.Value) (len=3 cap=4) {
              (*lep.IntegerX)({
                Val: (int64) 1
              }),
              (*lep.IntegerX)({
                Val: (int64) 2
              }),
              (*lep.IntegerX)({
                Val: (int64) 3
              })
            }
          })
        })
      }
    })
  }
})

Use can also create expression string from code:

package main

import (
	"fmt"
	lep "github.com/mgudov/logic-expression-parser"
)

func main() {
	expression := lep.And(
		lep.Equals(lep.Param("a"), lep.Boolean(false)),
		lep.GreaterThanEqual(lep.Param("b"), lep.Param("c")),
		lep.Or(
			lep.LessThan(lep.Param("d"), lep.Integer(1000)),
			lep.InSlice(
				lep.Param("e"),
				lep.Slice(lep.Integer(1), lep.Integer(2), lep.Integer(3)),
			),
		),
	)

	fmt.Println(expression.String())
}

a=false && b>=c && (d<1000 || e in [1,2,3])

Real life examples

package main

import (
	"fmt"
	"github.com/davecgh/go-spew/spew"
	sb "github.com/huandu/go-sqlbuilder"
	lep "github.com/mgudov/logic-expression-parser"
)

func traverse(sql *sb.SelectBuilder, expr lep.Expression) (string, error) {
	switch e := expr.(type) {
	default:
		return "", fmt.Errorf("not implemented: %T", e)
	case *lep.OrX:
		var args []string
		for _, disjunction := range e.Disjunctions {
			arg, err := traverse(sql, disjunction)
			if err != nil {
				return "", err
			}
			args = append(args, arg)
		}
		return sql.Or(args...), nil
	case *lep.AndX:
		var args []string
		for _, conjunct := range e.Conjuncts {
			arg, err := traverse(sql, conjunct)
			if err != nil {
				return "", err
			}
			args = append(args, arg)
		}
		return sql.And(args...), nil
	case *lep.EqualsX:
		value := e.Value.Value()
		if value == nil {
			return sql.IsNotNull(e.Param.String()), nil
		}
		return sql.Equal(e.Param.String(), value), nil
	case *lep.NotEqualsX:
		value := e.Value.Value()
		if value == nil {
			return sql.IsNotNull(e.Param.String()), nil
		}
		return sql.NotEqual(e.Param.String(), value), nil
	case *lep.GreaterThanX:
		return sql.GreaterThan(e.Param.String(), e.Value.Value()), nil
	case *lep.InSliceX:
		var items []interface{}
		for _, value := range e.Slice.Values {
			items = append(items, value.Value())
		}
		return sql.In(e.Param.String(), items...), nil

		// TODO: other cases
	}
}

func main() {
	query := `active=true && email!=null && (last_login>dt:"2010-01-01" || role in ["client","customer"])`

	expr, err := lep.ParseExpression(query)
	if err != nil {
		panic(err)
	}

	sql := sb.Select("*").From("users")
	where, err := traverse(sql, expr)
	if err != nil {
		panic(err)
	}
	sql.Where(where)

	spew.Dump(sql.Build())
}

(string) (len=99) "SELECT * FROM users WHERE (active = ? AND email IS NOT NULL AND (last_login > ? OR role IN (?, ?)))"
([]interface {}) (len=4 cap=4) {
 (bool) true,
 (time.Time) 2010-01-01 00:00:00 +0000 UTC,
 (string) (len=6) "client",
 (string) (len=8) "customer"
}

Operators and types

• Comparators: = != > >= < <= (left - param, right - param or value)
• Logical operations: || && (left, right - any statements)
• Numeric constants: integer 64-bit (12345678), float 64-bit with floating point (12345.678)
• String constants (double quotes: "foo bar", "foo "bar"")
• String operations: starts_with, ends_with (left - param, right - param or string)
• Regexp operations: =~ (match regexp a =~ /[a-z]+/), !~ (not match b !~ /[0-9]+/)
• Date constants (double quotes after dt:): dt:"2020-03-04 10:20:30" (for parsing datetime used dateparse)
• Arrays (any values separated by , within square bracket: [1,2,"foo",dt:"1999-09-09"])
• Array operations: in not_in (a in [1,2,3])
• Boolean constants: true false
• Null constant: null

Benchmarks

Here are the results output from a benchmark run on a Macbook Pro 2018:

go test -benchmem -bench=.
goos: darwin
goarch: amd64
pkg: github.com/mgudov/logic-expression-parser
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkSmallQuery-16                     26547             45293 ns/op           19353 B/op        332 allocs/op
BenchmarkMediumQuery-16                    10000            106334 ns/op           42931 B/op        807 allocs/op
BenchmarkLargeQuery-16                      3268            331438 ns/op          114500 B/op       2385 allocs/op
BenchmarkSmallQueryWithMemo-16             14696             79791 ns/op           82590 B/op        276 allocs/op
BenchmarkMediumQueryWithMemo-16             4924            246504 ns/op          257072 B/op        746 allocs/op
BenchmarkLargeQueryWithMemo-16              2071            590092 ns/op          594584 B/op       1627 allocs/op
PASS
ok      github.com/mgudov/logic-expression-parser       8.744s

Used Libraries

For parsing string the pigeon parser generator is used (Licensed under BSD 3-Clause).