一、出師之名

提到規則引擎，大部分人都會先想到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 編譯鏈接過程概述