一、出师之名
提到规定引擎，大部分人都会先想到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，三下五除二就实现了规定判断。
不同的规定函数：
// IRuletype IRule interface { Match(req *http.Request) bool}// HeaderMatch 匹配headerfunc HeaderMatch(key, value string) bool { ... return false}// CookieMatch 匹配Cookiefunc 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 mainimport ( "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 mainimport ( "go/ast" "go/parser" "go/token")func main() { src := `package mainfunc 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)实现判断，如下是简略的判断实现：
// Parsefunc 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 编译链接过程概述