Go轻量级表达式执行引擎

Bioit in ShenZhen

2023-03-17

写在前面

需求：工作中有个业务需要用到千人千面的规则判定，即对于用户，会经常对不同的群体执行不同的逻辑，业务中就把这块逻辑抽出来用表达式执行来执行，只需要圈定用户远程配置中配置表达式即可, 也随时可以在远程配置中修改表达式
属于造轮子吗？是也不是, 写之前搜索了已有的使用人数较多的几个go表达式执行引擎, 功能都基本较为完善, 但是和我们的使用场景配合起来需要强行拓展, 代码拓展后速度上也就不是特别快了, 所以借鉴并写了个完全符合我们业务需求, 基本没有冗余功能的引擎
不巧的是刚写完业务就从Go转C++了..., C++有基于JIT的表达式引擎，性能非常强悍
本项目代码地址 (opens new window)
参考项目地址 (opens new window)：一些逻辑或者优化参考此项目

# 一、功能介绍

# 1、支持的操作符：

注：与go语言中用法不同或者增加的都予以注明

三元操作符: ? :(与其他语言中用法一致, eg：逻辑表达式？表达式1 : 表达式2)（注意表达式1与表达式2的执行结果类型可以不同）
二元操作符:
- 逻辑操作符: ||、&&
- 比较操作符: ==、!=、<、<=、>、>=、in（可以类比sql中的in, 用法例子: 1 in [1, 2, 3]，其将返回true）
- 运算操作符: +、-、*、/、%、**(幂)
- 位运算操作符: |、^（按位异或，注意在引擎中其不能作为按位取反, 按位取反为~）、&、&^、<<、>>
一元操作符：
- ++, --, 注意自增与自减只支持前缀, eg: ++2, 而2++是不被允许的, 因为表达式引擎只是运行一个表达式, 后缀的自增自减毫无意义
- !（逻辑反）、~(位取反, 注意不是^)、-(负)
操作符优先级：按由低至高顺序排列，可以加括号方便表达式书写
- ? 与 ：，注意这其实是2个二元操作符组成的三元操作符，它们优先级最低
- ||
- &&
- ==、!=、<、<=、>、>=、in
- +、-、 |、^
- *、/、%、&、&^、<<、>>
- **
- 一元操作符

# 2、支持的数据类型：

数值: 表达式中所有数值使用go中的float64, 表达式中数值书写可以写成1、1.0等都是允许的, 数值只支持10进制, 且不支持指数的表示方式（一是我不想写，二是真的有人平时开发会用到各种各样的数据表示形式吗）

注：使用函数时, 如果函数中返回数值,需要明确的为float64类型（这一点当然也可以改为支持任何数值类型，但是笔者觉得没必要）

布尔: 书写为 true、false、t、f、True等部分或全部大写
字符串: 用小引号包裹, eg: 'go_expression', 支持转义。特别的, 如要表示小引号需要转义（eg："a == 'ssss1234\\'567' ")

# 3、支持变量：

变量在表达式执行时以map[string]any形式传入

注：

变量的类型不为函数参数的时候，只能传第二点中所述的三种类型（数值、布尔、字符串），且传入的参数为数值类型时, 类型需要为float64

变量作为函数的参数时，可以传入任意类型

非函数参数的变量不支持结构体访问（eg：user.a），原因是如果支持，将要利用反射，性能将降低，笔者的应用场景需要较高的性能

注意变量在运算过程中是否改变, 不同使用场景有不同结果:

场景1: ++a == 1 && a == 2。注意, 此时如果执行时传入a的值为0, 那么 ++a == 1将为true, 但是当运行到 a == 2时, a还是等于0, 这有点反直觉, 当然也可以优化, 目前暂时不优化
场景2: func1(a) == 1 && func2(a) == 2, 如果a为非值类型, 比如是个map, 那么func1中对a的操作func2将会感知到, 这需要使用者知道

最后, 附简单的使用例子：

// 第一个参数为表达式字符串，第二个参数为执行时期是否进行类型检查, 当确定自己使用无误测试环境测试无问题后可设置为false加快执行
// 第三个参数为函数, 将在下一节介绍
exp, err := goexpression.NewExpression("a == 1 && b == true", true, nil)
if err != nil {
	// ...
}
ret = exp.Bool(map[string]any{
	"a": float64(1), // 非函数参数，数值类型一律为 float64
	"b": true,
})
// ...

# 4、支持函数：

函数的类型定义如下：

type Function func(params ...any) (any, error)

简单的使用例子，例子中忽略错误与类型转换错误与参数个数检查等错误，由例子可以看出，函数支持嵌套

exp, _ := NewExpression("age(get(ctx)) == 1", true, map[string]Function{
	"age": func(params ...any) (any, error) {
		return params[0].(float64), nil
	},
	"get": func(params ...any) (any, error) {
		ctx := params[0].(context.Context)
		return float64(ctx.Value("age").(int)), nil
	},
})
ret = exp.Bool(map[string]any{
	"ctx": context.WithValue(context.Background(), "age", 1),
})

# 二、笔者的使用场景

注：举的例子是实际用法经过处理与精简，不代表业务中一模一样的用法，比如真实的表达式长达几十个子布尔表达式

对于一个用户，当满足其a字段值>=70 且<80，并且b字段值>14时有50%的概率进行一些操作

注：

如果只有这一个需求，那么也没必要搞个表达式引擎了，但是如果针对不同用户有不同的表达式且表达式的值易变，才适用。核心点就是多且易变

代码实现：


func init() {
	rand.Seed(time.Now().Unix())
}

type User struct {
	A int
	B int
}

func main() {
    // 实际使用中，表达式的值肯定是远程配置的
	exp, _ := goexpression.NewExpression(`IntUserA(user) >= 70 && IntUserA(user) < 80 &&
            IntUserB(user) > 14 && IntRand() < 50`, true, map[string]goexpression.Function{
		"IntUserA": IntUserA,
		"IntUserB": IntUserB,
		"IntRand":  IntRand,
	})
	// 显然，业务中运行的时候，User肯定是个运行时传入的
	ret, _ := exp.Bool(map[string]any{
		"user": User{A: 71, B: 15},
	})
	fmt.Println(ret)
}

func IntUserA(params ...any) (any, error) {
	user := params[0].(User)
	return float64(user.A), nil
}

func IntUserB(params ...any) (any, error) {
	user := params[0].(User)
	return float64(user.B), nil
}

func IntRand(params ...any) (any, error) {
	return float64(rand.Intn(100)), nil
}

还有一点笔者需要强调，实际使用中A字段与B字段可能不是User结构体中自带的，它们可能是由C、D、E等字段计算得到的，比如计算用户两个切片特征的交集大小，我们使用函数传参而不使用结构体不但可以省略反射，还能让计算延迟，避免不必要的计算（用户的表达式的中包含的函数才会**可能（由于逻辑表达式短路不一定会执行）**运行，eg：UserA(user) > 10 && UserB(user) == 1，当UserA(user) > 10 为假时UserB(user)不执行，用结构体需要提前计算所有值

当然，例子中用了值传递，User结构体很大时将有影响（较小的时候可以自行测试，可能值传递效率还更高），我们可以将其放入ctx中等方法

实际使用中，由于编译较为耗时，我们可以使用一个全局map（选用并发安全map或者读写锁 + map等等），key为string格式的表达式，value为编译好的表达式。这样只会在远程配置变动的时候会有一定量的编译，当有一个协程编译好并放入map后，后续的所有协程都将从map中取用

# 三、原理简介

首先，编译原理不熟悉的同学可以看笔者之前的两篇文章：简析Go词法分析 (opens new window)、简析Go语法分析 (opens new window)

我们需要实现的只是一个功能不完备的表达式执行，所以代码其实很简单，笔者主要强调其中的一些地方

# 0、词法分析：

词法分析没啥好说的，由上面的代码演示我们可以看到编译的时候需要传入函数map，可以在词法分析阶段区分函数与变量：

// 当词法分析遇到字符，可能是：关键字，函数名，变量名
if unicode.IsLetter(char) {
  name := l.letters(char) // 获取连续字符
  if ok := l.isKeyLetter(name); ok { // 关键字优先级最大, 把true，in这些看做关键字
    continue
  }
  if f, ok := functions[name]; ok { // 注册的函数
    l.addToken(f, Func, false)
    continue
  }
  l.addToken(name, Var, false) // 最后才是变量
  continue
}

关于负号与减号的处理：减号与自减和其它如&与&&一样的容易处理，以&&与&为例，解析规则为：&&解析为逻辑与，&解析为按位与& &解析为两个按位与，因为其有空格，&&&解析为&&与&。当然& &和&&&的写法都是错误的表达式
- 但是负号与减号的区分不应该词法分析阶段来做，放入语法分析阶段将更加符合场景，所以词法阶段 “-” 一律被解析为减号Token

# 1、语法分析：参考Go编译器源码，性能上与正确性上都能得到保障，可以去简析Go语法分析 (opens new window)中了解Go是如何解析表达式的（核心点还是结合性与优先级的处理）

语法分析后为一颗抽象语法树，树节点结构体如下：

type astNode struct {
	left, right *astNode  // 左右子节点
	op          Operator  // 节点是操作符时记录操作符，执行优化时用到
	opFunc      opFunc    // 节点执行函数
	typeCheck   typeCheck // 类型检查函数
}

type opFunc func(l any, r any, params map[string]any) (any, error)

type typeCheck func(left, right any) bool

以 1 + 1这个表达式来展示下解析后的抽象语法树

抽象语法树AST

其中，三个节点的执行函数为：

// + 节点的执行函数
func addFunc(left, right any, _ map[string]any) (any, error) {
	if IsString(left) && IsString(right) {
		return left.(string) + right.(string), nil
	}
	return left.(float64) + right.(float64), nil
}

// 语法解析的时候传入lit为1，从而返回两个1的执行函数
func makeLitFunc(lit any) opFunc {
	return func(l any, r any, params map[string]any) (any, error) {
		return lit, nil
	}
}

+节点的类型检查函数为如下（代表左右子节点调用计算函数的返回值必须满足同时为float64或者同时为string），显然的，字面量不需要类型检查函数：

func canCmp(left, right any) bool {
	return IsFloat64(left) && IsFloat64(right) || IsString(left) && IsString(right)
}

显然的只有操作符需要类型检查函数

比较特殊的三个Token的执行函数如下：

// 获取变量Token的执行函数，如 a + 1，中a获取执行函数时调用makeVarFunc("a")
func makeVarFunc(name string) opFunc {
	return func(l, r any, params map[string]any) (any, error) {
		ret, ok := params[name]
		if !ok {
			return nil, fmt.Errorf("execute: %s param not in the passed parameter list", name)
		}
		return ret, nil
	}
}

// 获取函数Token的执行函数
func makeFuncFunc(function Function) opFunc {
	return func(left, right any, params map[string]any) (any, error) {
		if right == nil {
			return function()
		}
		switch right.(type) {
		case []any:
			return function(right.([]any)...)
		default:
			return function(right)
		}
	}
}

// ","Token 执行函数，函数参数或者数组列表需要用到 "," (如[1, 2, 3]这种)
func commaFunc(left, right any, _ map[string]any) (any, error) {
	var ret []any

	switch left.(type) {
	case []any:
		ret = append(left.([]any), right)
	default:
		ret = []any{left, right}
	}
	return ret, nil
}

比较特殊的是对于类似于 [1, 2, 3]，funcName(4, 5, 6)这两者的处理，有兴趣的同学可以打开源码查看。其中 [1, 2, 3]与(4, 5, 6)都将被解析为一颗树（见下图），这个树执行结果为数组（上面提到了commaFunc这个函数），(4, 5, 6)这颗树将作为funcName这个函数节点的右子树。 [1, 2, 3]可能作为单独的一个表达式，即一颗树或者作为in操作符的右子树

解析结果

# 2、表达式执行：执行即DFS方式遍历抽象语法树的树根，调用左右子节点的计算函数opFunc与类型检查函数typeCheck

主要执行加速在于逻辑表达式的熔断与类型检查可关闭（初始化表达式的时候的第二个参数）

func (e *Expression) executeASTNode(root *astNode, params map[string]any) (any, error) {
	if root == nil {
		return nil, nil
	}
	var (
		left, right any
		err         error
	)
	// 先调用左子节点，计算左子树的最终计算结果
	if left, err = e.executeASTNode(root.left, params); err != nil {
		return nil, err
	}

	// 左边结果可能可以直接决定结果的，eg：true || 2 == 3, 这个2 == 3就没必要执行了
	switch root.op {
	case AndAnd: // &&
		if left == false {
			return false, nil
		}
	case OrOr: // || 
		if left == true {
			return true, nil
		}
	case TernaryT: // ?
		if left == false {
			return nil, nil
		}
	case TernaryF: // :
		if left != nil {
			return left, nil
		}
	default:
	}
	// 计算右子树计算结果
	if right, err = e.executeASTNode(root.right, params); err != nil {
		return nil, err
	}
	// 如果开启了类型检查, 检查左右子树计算结果是否符合预期
	if e.NeedCheck && root.typeCheck != nil {
		if !root.typeCheck(left, right) {
			return nil, fmt.Errorf("execute: type check error")
		}
	}
	// 调用自身的计算函数并返回结果
	return root.opFunc(left, right, params)
}