关于go:如何用Go快速实现规则引擎

一、出师之名

提到规定引擎，大部分人都会先想到 DSL(Domain Specific Language)，进而联想令人生畏的 编译原理、递归降落、LL 或 LR。但规定引擎有大有小，它们在不同场景的存在不一样，并不一定都要这么简单。

比方在一个小型领取零碎的简略风控场景里，产品同学想设置一些规定防止用户的银行卡被盗刷或者商户被薅羊毛：

• 24 小时内领取总金额超 10w 的用户
• 1 小时应用信用卡领取金额超 5w 的用户
• 1 小时被发动退款金额超 10w 的商户
• 30 分钟内频繁领取又退款超过 10 次的用户
• ……

为了疾速实现需求，咱们开发一个独自的规定类或者库，类外面有不同规定判断函数。规定一直减少，规定函数就一直扩大，这个收缩的规定类库就是一个渺小的规定引擎。尽管在业务调用的中央会有很多 switch 或者 if…else..，但这个渺小的规定引擎并不需要引入 DSL，一样能好好工作。

而在另外一些业务零碎，比方贷款零碎，同样是风控场景，产品同学也会设置一些规定做不同的金额审批决策：

• 征信评分达到 650，申请金额 2000 元以下能够间接审批
• 征信评分达到 650，申请金额在 5000 以下，如果月均生产达到 2000 块能够间接审批
• 征信评分在 550~600 之间，申请金额在 5000 以下的三四线城市用户，如果月均生产达到 1000 块还须要其余生产评估，如果月支出未达到 1w 须要工资流水证实
• ……

在这些规定未增多之前，咱们发现单单写规定类库，业务方通过调用不同函数判断，就曾经痛不欲生。这些风控规定相比上文来说，波及的用户属性多，判断条件简单，而且还有不同的优先级。如果没有更好的规定形象，代码复杂度只会越来越高，这时就须要设计一套 DSL 来满足更多的规定判断。

所以，在咱们真正要实现一个规定引擎之前，下定决心设计 DSL 与编译原理拉扯之前，咱们首先看简略的规定类库是否就已满足需要。

二、需要背景

咱们组用 Go 自研了一个 API 网关，作为一个网关，网关必不可少的能力是路由转发，精细化路由更是高频需要。业务须要依据不同需要场景做不同的路由配置，比方灰度公布、A/B 测试、限流、负载平衡等。

但网关现有的转发规定只能基于申请 Method 和 URL(Host/Path/Query)作简略配置，欠缺依据申请 Header、Cookie、CIP(Client IP)/VIP 等更多申请属性配置，与及这些属性规定的组合配置，比方业务须要配置 API 的读写拆散，并且灰度测试，就须要配置申请 Method 和申请 Header 这样的并集规定。

三、Json 实现

我最开始没有往 DSL 的方向想，写几个像上面的简略的规定函数，用 json 格局定义规定，再用 Go 的反射库解析 json，三下五除二就实现了规定判断。
不同的规定函数：

// IRule
type IRule interface {Match(req *http.Request) bool
}

// HeaderMatch 匹配 header
func HeaderMatch(key, value string) bool {
    ...
    return false
}

// CookieMatch 匹配 Cookie
func CookieMatch(key, value string) bool {
    ...
    return false
}

...

规定定义：

{
    "op":"AND",
    "matcher":[
        "header",
        "cookie"
    ],
    "header":{
        "key":"X-APP-ID",
        "value":"xx"
    },
    "cookie":{
        "name":"feature",
        "value":"dev/kyrie/qualify-rule"
    }
}

规定解析框架(非反射库版)：

// 遍历判断规定
for _, matcher := range matchers {var m map[string]interface{}
        err := json.Unmarshal([]byte(data["mather"]), &m)
        if err != nil {log.Fatal(err)
        }

        switch matcher {
        case "header":
            ...
             result[matcher] = HeaderMatch(rule.key, rule.Vaule)
        case "coolkie":
            ...
             result[matcher] = CookieMatch(rule.name, rule.Vaule)
        }
        ...
    }
...
// 综合计算规定后果
switch op {
case "AND":
  ...
case "OR"
...
}
....

下面是一个常见的二元表达式规定，从规定定义到规定解析能够看出，用 Json 的形式实现十分不便，曾经满足简略的规定场景。不好的中央就是解析的代码太灵便，一条龙的 switch case，如果退出更多逻辑，复杂度就会回升，维护性也只会越来越差。

比方，一开始的规定条件只有等值匹配，接着减少范畴匹配，非匹配，正则匹配等，前面再在这些根底上退出规定优先级，就得须要引入更多的 json 定义，规定解析框架也要相应地笼罩更多的形象维度。

那有没有形象度更高、实现也不简单的解析实现形式呢？就是说，有没有比 Json 形式更好地表白这些规定的存在？

答案必定是有的，不然怎么写下去🐶。

如果仔细分析下面的规定，能够发现这些规定通过一波计算后只需失去一个布尔值，与其余算术表达式、关系表达式不同，这些规定都是 布尔表达式。

网上理解到，国内出名 Go 领域专家曹大 (Xargin) 在基于 Go 的内置 Parser 打造轻量级规定引擎 一文中提到：Go 的 ast 语法树能够完满表白布尔表达式，应用 Go 的内置 parser 库能够实现一个根本规定引擎的框架。

于是，我开始尝试应用 Go 自带的 ast 库及 parser 库实现转发规定的解析。

四、AST 实现

4.1 Go 的编译过程

Go 的 ast 库和 parser 库都是 Go 编译过程中的工具库，Go 的编译过程跟大部分高级语言的编译过程一样，分为 6 步：词法剖析、语法分析、语义剖析、两头码生成、代码优化和机器码生成。

援用《程序员的自我涵养》外面的图，就是上面这一串流程：

每步的输入输出，具体做的事件总体如下表：

咱们要拿来做规定引擎的就是后面两步的产物：词法剖析失去的 Token 和语法分析的 AST。

4.2 Token(记号)

Token 是高级语言中最小的词法单元，Go 次要有标识符、关键字、运算符和分隔符等 Token，更多的 token 定义参考 token 文件。

比方咱们扫描println(”Hello World”)，失去以下 token：

扫描代码：

package main

import (
    "fmt"
    "go/scanner"
    "go/token"
)

func main() {var src = []byte(`println("Hello World!")`)

    var fset = token.NewFileSet()
    var file = fset.AddFile("hello.go", fset.Base(), len(src))

    var s scanner.Scanner
    s.Init(file, src, nil, scanner.ScanComments)

    for {pos, tok, lit := s.Scan()
        if tok == token.EOF {break}
        fmt.Printf("%s\\t%s\\t%q\\n", fset.Position(pos), tok, lit)
    }
}

扫描后果：

hello.go:1:1    IDENT    "println"
hello.go:1:8    (    ""hello.go:1:9    STRING"\\"Hello World!\\""
hello.go:1:23    )    ""hello.go:1:24    ;"\\n"

其中 println 是标识符 (IDENT)Token，Hello World 则是字符串 Token。

4.3 AST(形象语法树)

有了 Scanner 扫描进去的 Token 序列，到语法分析这一步，就能够进一步结构 AST，但如果看具体的 AST，会发现 AST 中不止有 Token，比方同样是这段println(”Hello World”)，它的 AST 如下：

解析代码：

package main

import (
    "go/ast"
    "go/parser"
    "go/token"
)

func main() {
    src := `
package main
func main() {println("Hello, World!")
}
`
    // Create the AST by parsing src.
    fset := token.NewFileSet() // positions are relative to fset
    f, err := parser.ParseFile(fset, "", src, 0)
    if err != nil {panic(err)
    }

    // Print the AST.
    ast.Print(fset, f)

}

解析后果：

     0  *ast.File {
     1  .  Package: 2:1
     2  .  Name: *ast.Ident {
     3  .  .  NamePos: 2:9
     4  .  .  Name: "main"
     5  .  }
     6  .  Decls: []ast.Decl (len = 1) {
     7  .  .  0: *ast.FuncDecl {
     8  .  .  .  Name: *ast.Ident {
     9  .  .  .  .  NamePos: 3:6
    10  .  .  .  .  Name: "main"
    11  .  .  .  .  Obj: *ast.Object {
    12  .  .  .  .  .  Kind: func
    13  .  .  .  .  .  Name: "main"
    14  .  .  .  .  .  Decl: *(obj @ 7)
    15  .  .  .  .  }
    16  .  .  .  }
    17  .  .  .  Type: *ast.FuncType {
    18  .  .  .  .  Func: 3:1
    19  .  .  .  .  Params: *ast.FieldList {
    20  .  .  .  .  .  Opening: 3:10
    21  .  .  .  .  .  Closing: 3:11
    22  .  .  .  .  }
    23  .  .  .  }
    24  .  .  .  Body: *ast.BlockStmt {
    25  .  .  .  .  Lbrace: 3:13
    26  .  .  .  .  List: []ast.Stmt (len = 1) {
    27  .  .  .  .  .  0: *ast.ExprStmt {
    28  .  .  .  .  .  .  X: *ast.CallExpr {
    29  .  .  .  .  .  .  .  Fun: *ast.Ident {
    30  .  .  .  .  .  .  .  .  NamePos: 4:2
    31  .  .  .  .  .  .  .  .  Name: "println"
    32  .  .  .  .  .  .  .  }
    33  .  .  .  .  .  .  .  Lparen: 4:9
    34  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {
    35  .  .  .  .  .  .  .  .  0: *ast.BasicLit {
    36  .  .  .  .  .  .  .  .  .  ValuePos: 4:10
    37  .  .  .  .  .  .  .  .  .  Kind: STRING
    38  .  .  .  .  .  .  .  .  .  Value: "\\"Hello, World!\\""
    39  .  .  .  .  .  .  .  .  }
    40  .  .  .  .  .  .  .  }
    41  .  .  .  .  .  .  .  Ellipsis: -
    42  .  .  .  .  .  .  .  Rparen: 4:25
    43  .  .  .  .  .  .  }
    44  .  .  .  .  .  }
    45  .  .  .  .  }
    46  .  .  .  .  Rbrace: 5:1
    47  .  .  .  }
    48  .  .  }
    49  .  }
    50  .  Scope: *ast.Scope {51  .  .  Objects: map[string]*ast.Object (len = 1) {52  .  .  .  "main": *(obj @ 11)
    53  .  .  }
    54  .  }
    55  .  Unresolved: []*ast.Ident (len = 1) {56  .  .  0: *(obj @ 29)
    57  .  }
    58  }

整个 AST 包含 Package、Name、Decls、Scope 跟 Unresolved，其中核心内容在 Decls 里边（第 6 行～49 行）。

Decls 是申明 declaration 的汇合，里边有 FuncDecl(函数申明)，有BlockStmt(块语句)，还有CallExpr(表达式) 等。深刻 ast 库，能够发现 这三个正是 AST 节点的次要类型，它们都实现了 Node(节点)接口，就是说，AST 这颗树挂的都是这三个玩意。

// ----------------------------------------------------------------------------
// Interfaces
//
// There are 3 main classes of nodes: Expressions and type nodes,
// statement nodes, and declaration nodes. The node names usually
// match the corresponding Go spec production names to which they
// correspond. The node fields correspond to the individual parts
// of the respective productions.
//
// All nodes contain position information marking the beginning of
// the corresponding source text segment; it is accessible via the
// Pos accessor method. Nodes may contain additional position info
// for language constructs where comments may be found between parts
// of the construct (typically any larger, parenthesized subpart).
// That position information is needed to properly position comments
// when printing the construct.

// All node types implement the Node interface.
type Node interface {Pos() token.Pos // position of first character belonging to the node
    End() token.Pos // position of first character immediately after the node}

// All expression nodes implement the Expr interface.
type Expr interface {
    Node
    exprNode()}

// All statement nodes implement the Stmt interface.
type Stmt interface {
    Node
    stmtNode()}

// All declaration nodes implement the Decl interface.
type Decl interface {
    Node
    declNode()}

常见的表达式有：

UnaryExpr 一元表达式
BinaryExpr 二元表达式
ParenExpr 括号表达式, 被括号包裹的表达式
...

常见的语句有：

AssignStmt 赋值语句
SwitchStmt switch 语句
DeferStmt 提早语句
ForStmt for 语句
...

更多定义在 ast 文件中都能够找到，并不难以了解。

4.4 需要实现

意识了 Token 跟 AST 后，咱们看怎么简略实现咱们的规定解析，还是用上文的例子，要判断 http 申请 header 的 key/value 及 cookie 的 name/value 是否满足以下规定：

"header":{"key":"X-APP-ID", "value":"xx"},
"cookie":{"name":"feature","value":"dev/kyrie/qualify-rule"}

以 header 的规定解析 AST 为例，header.key=="X-APP-ID" && header.value=="xx"，打印的 AST 如下，AST 很清晰地示意这条规定是个 BinaryExpr，即二元表达式，二元表达式的右边为 X，左边是 Y，逻辑运算符为 Op。

         0  *ast.BinaryExpr {
     1  .  X: *ast.BinaryExpr {
     2  .  .  X: *ast.SelectorExpr {
     3  .  .  .  X: *ast.Ident {
     4  .  .  .  .  NamePos: -
     5  .  .  .  .  Name: "header"
     6  .  .  .  .  Obj: *ast.Object {
     7  .  .  .  .  .  Kind: bad
     8  .  .  .  .  .  Name: ""
     9  .  .  .  .  }
    10  .  .  .  }
    11  .  .  .  Sel: *ast.Ident {
    12  .  .  .  .  NamePos: -
    13  .  .  .  .  Name: "key"
    14  .  .  .  }
    15  .  .  }
    16  .  .  OpPos: -
    17  .  .  Op: ==
    18  .  .  Y: *ast.BasicLit {
    19  .  .  .  ValuePos: -
    20  .  .  .  Kind: STRING
    21  .  .  .  Value: "\\"X-APP-ID\\""
    22  .  .  }
    23  .  }
    24  .  OpPos: -
    25  .  Op: &&
    26  .  Y: *ast.BinaryExpr {
    27  .  .  X: *ast.SelectorExpr {
    28  .  .  .  X: *ast.Ident {
    29  .  .  .  .  NamePos: -
    30  .  .  .  .  Name: "header"
    31  .  .  .  .  Obj: *(obj @ 6)
    32  .  .  .  }
    33  .  .  .  Sel: *ast.Ident {
    34  .  .  .  .  NamePos: -
    35  .  .  .  .  Name: "value"
    36  .  .  .  }
    37  .  .  }
    38  .  .  OpPos: -
    39  .  .  Op: ==
    40  .  .  Y: *ast.BasicLit {
    41  .  .  .  ValuePos: -
    42  .  .  .  Kind: STRING
    43  .  .  .  Value: "\\"xx\\""
    44  .  .  }
    45  .  }
    46  }

有了 AST 构造，咱们能够别离获取右边 (X) 的 key 值和左边 (Y) 的值依据逻辑运算符 (Op) 实现判断，如下是简略的判断实现：

// Parse
func Parse(expr string, header http.Header) (bool, error) {exprAst, err := parser.ParseExpr(expr)
    if err != nil {return false, err}
    // 打印 ast
    //fset := token.NewFileSet()
    //ast.Print(fset, exprAst)
    return judge(exprAst, header), nil
}

// 判断
func judge(bop ast.Node, header http.Header) bool {
    // 断言成二元表达式
    expr := bop.(*ast.BinaryExpr)
    x := expr.X.(*ast.BinaryExpr)
    key := x.Y.(*ast.BasicLit) // key 值

    y := expr.Y.(*ast.BinaryExpr)
    value := y.Y.(*ast.BasicLit) // value 值

    // 等值匹配
    return header.Get(strings.Trim(key.Value, `"`)) == strings.Trim(value.Value, `"`)
}

五、更进一步

通过以上的简略例子，咱们大略能够利用 go 的 ast 库和 parser 库实现个简略的规定引擎。但这可能还不够，如果要笼罩更简单的规定，不仅仅是只有布尔表达式，就要设计本人的规定原语，比方将 header.key=="X-APP-ID" && header.value=="Ves" 和cookie.name=="feature" && cookie.value=="dev/wynnliu/qualify-rule"设计成`req_header_pair_is("X-APP-ID", "XX") && req_cookie_contain("feature", "dev/kyrie/qualify-rule")。

就要设计本人的规定原语，这时就得引入GoYacc，用 GoYacc 解析本人设计的 BNF/EBNF(巴科斯范式/扩大巴科斯范式，定义语法规定)。GoYacc 整体应用原理根本还是上文提到的编译过程，但波及的细节较多，本文不开展，有趣味的读者敌人能够参考 TiDB SQL Parser，理解 TiDB 的 sql 解析器如何基于 GoYacc 设计实现 sql 解析。

Reference

1. 基于 Go 的内置 Parser 打造轻量级规定引擎

2.Go 编译链接过程概述