曹大帶我學 Go之初識 Ast 的威力
本文轉載自微信公眾號「碼農桃花源」，作者小X。轉載本文請聯系碼農桃花源公眾號。
你好，我是小X。
曹大最近開 Go 課程了，小X 正在和曹大學 Go。
這個系列會講一些從課程中學到的讓人醍醐灌頂的東西，撥云見日，帶你重新認識 Go。
抽象語法樹是編譯過程中的一個中間產物，一般簡單了解一下就行了。但我們可以把 Go 語言的整個 parser 和 ast 包直接拿來用，在一些場景下有很大的威力。
什么是 ast 呢，我從維基百科上摘錄了一段：
在計算機科學中，抽象語法樹(Abstract Syntax Tree，AST)，或簡稱語法樹(Syntax tree)，是源代碼語法結構的一種抽象表示。它以樹狀的形式表現編程語言的語法結構，樹上的每個節點都表示源代碼中的一種結構。
核心就是說 ast 能以一種樹的形式表示代碼結構。有了樹結構，就可以對它做遍歷，能干很多事。
假定一個場景
假定一個場景：我們可以從司機平臺的某個接口獲取司機的各種特征，例如：年齡、訂單數、收入、每天駕駛時長、駕齡、平均車速、被投訴次數……數據一般采用 json 來傳遞。
司機平臺的運營小姐姐經常需要搞一些活動，例如選出：
- 訂單數超過 10000，且駕齡超過 5 年的老司機
- 每天駕駛時小于 3 小時，且收入超過 500 的高效司機
- 年齡大于 40，且平均速度大于 70 的“狂野”司機
- ……
這些規則并不是固定的，經常在變化，但總歸是各種司機特征的組合。
為了簡化，我們選取 2 個特征，并用一個 Driver 結構體來表示：
- type Driver struct {
- Orders int
- DrivingYears int
- }
為了配合運營搞活動，我們需要根據運營給的規則來判斷一個司機是否符合要求。
如果公司人多，可以安排一個 rd 專門伺候運營小姐姐，每次做活動都來手動修改代碼，也不是不可以。并且其實挺簡單，我們來寫一個示例代碼：
- // 從第三方獲取司機特征，json 表示
- func getDriverRemote() []byte {
- return []byte(`{"orders":100000,"driving_years":18}`)
- }
- // 判斷是否為老司機
- func isOldDriver(d *Driver) bool {
- if d.Orders > 10000 && d.DrivingYears > 5 {
- return true
- }
- return false
- }
- func main() {
- bs := getDriverRemote()
- var d Driver
- json.Unmarshal(bs, &d)
- fmt.Println(isOldDriver(&d))
- }
直接來看 main 函數：getDriverRemote 模擬從第三方 RPC 獲取一個司機的特征數據，用 json 表示。接著 json.Unmarshal 來反序列化 Driver 結構體。最后調用 isOldDriver 函數來判斷此司機是否符合運營的規則。
isOldDriver 根據 Driver 結構體的 2 個字段使用 if 語句來判斷此司機是否為老司機。
確實還挺簡單。
但是每次更新規則還得經過一次完整的上線流程，也挺麻煩的。有沒有更簡單的辦法呢?使得我們可以直接解析運營小組姐給我們的一個用字符串表示的規則，并直接返回一個 bool 型的值，表示是否滿足條件。
有的!
接下來就是本文的核心內容，如何使用 ast 來完成同樣的功能。
直觀地理解如何用 ast 解析規則
使用 ast 包提供的一些函數，我們可以非常方便地將如下的規則字符串：
- orders > 10000 && driving_years > 5
解析成一棵這樣的二叉樹：
規則二叉樹
其中，ast.BinaryExpr 代表一個二元表達式，它由 X 和 Y 以及符號 OP 三部分組成。最上面的一個 BinaryExpr 表示規則的左半部分和右半部分相與。
很明顯，左半部分就是：orders > 10000，而右半部分則是：driving_years > 5。神奇的是，左半部分和右半部分恰好又都是一個二元表達式。
左半部分的 orders > 10000 其實也是最小的葉子節點，它可以算出來一個 bool 值。把它拆開來之后，又可以分成 X、Y、OP。X 是 orders，OP 是 ">"，Y 則是 "10000"。其中 X 表示一個標識符，是 ast.Ident 類型，Y 表示一個基本類型的字面量，例如 int 型、字符串型……是 ast.BasicLit 類型。
右半部分的 driving_years > 18 也可以照此拆分。
然后，從 json 中取出這個司機的 orders 字段的值為 100000，它比 10000 大，所以左半部分算出來為 true。同理，右半部分算出來也為 true。最后，再算最外層的 "&&"，結果仍然為 true。
至此，直接根據規則字符串，我們就可以算出來結果。
如果寫成程序的話，就是一個 dfs 的遍歷過程。如果不是葉子結點，那就是二元表達式結點，那就一定有 X、Y、OP 部分。遞歸地遍歷 X，如果 X 是葉子結點，那就結束遞歸，并計算出 X 的值……
這里再展示一個用 ast 包打印出來的抽象語法樹：
Go 打印 ast
上圖中，1、2、3 表示最外層的二元表達式;4、5、6 則表示左邊這個二元表達式。
結合這張圖，再參考 ast 包的相關結構體 代碼，就非常清晰了。例如 ast.BinaryExpr 的代碼如下：
- // A BinaryExpr node represents a binary expression.
- BinaryExpr struct {
- X Expr // left operand
- OpPos token.Pos // position of Op
- Op token.Token // operator
- Y Expr // right operand
- }
它有 X、Y、OP，甚至還解析出了 Op 的位置，用 OpPos 表示。
如果你還對實現感興趣，那就繼續看下面的原理分析部分，否則可以直接跳到結尾總結部分。
原理分析
還是用上面那個例子，我們直接寫一個表達式：
- orders > 10000 && driving_years > 5
接下來用 ast 來解析規則并判斷真假。
- func main() {
- m := map[string]int64{"orders": 100000, "driving_years": 18}
- rule := `orders > 10000 && driving_years > 5`
- fmt.Println(Eval(m, rule))
- }
為了簡單，我們直接用 map 來代替 json，道理是一樣的，僅僅為了方便。
Eval 函數判斷 rule 的真假：
- // Eval : 計算 expr 的值
- func Eval(m map[string]int64, expr string) (bool, error) {
- exprAst, err := parser.ParseExpr(expr)
- if err != nil {
- return false, err
- }
- // 打印 ast
- fset := token.NewFileSet()
- ast.Print(fset, exprAst)
- return judge(exprAst, m), nil
- }
先將表達式解析成 Expr，接著調用 judge 函數計算結果：
- // dfs
- func judge(bop ast.Node, m map[string]int64) bool {
- // 葉子結點
- if isLeaf(bop) {
- // 斷言成二元表達式
- expr := bop.(*ast.BinaryExpr)
- x := expr.X.(*ast.Ident) // 左邊
- y := expr.Y.(*ast.BasicLit) // 右邊
- // 如果是 ">" 符號
- if expr.Op == token.GTR {
- left := m[x.Name]
- right, _ := strconv.ParseInt(y.Value, 10, 64)
- return left > right
- }
- return false
- }
- // 不是葉子節點那么一定是 binary expression（我們目前只處理二元表達式）
- expr, ok := bop.(*ast.BinaryExpr)
- if !ok {
- println("this cannot be true")
- return false
- }
- // 遞歸地計算左節點和右節點的值
- switch expr.Op {
- case token.LAND:
- return judge(expr.X, m) && judge(expr.Y, m)
- case token.LOR:
- return judge(expr.X, m) || judge(expr.Y, m)
- }
- println("unsupported operator")
- return false
- }
judge 使用 dfs 遞歸地計算表達式的值。
遞歸地終止條件是葉子節點：
- // 判斷是否是葉子節點
- func isLeaf(bop ast.Node) bool {
- expr, ok := bop.(*ast.BinaryExpr)
- if !ok {
- return false
- }
- // 二元表達式的最小單位，左節點是標識符，右節點是值
- _, okL := expr.X.(*ast.Ident)
- _, okR := expr.Y.(*ast.BasicLit)
- if okL && okR {
- return true
- }
- return false
- }
總結
今天這篇文章主要講了如何用 ast 包和 parser 包解析一個二元表達式，并見識到了它的威力，利用它可以做成一個非常簡單的規則引擎。
其實利用 ast 包還可以做更多有意思的事情。例如批量把 thrift 文件轉化成 proto 文件、解析 sql 語句并做一些審計……
想要更深入的學習，可以看曹大這篇《golang 和 ast》[1]，據曹大自己說，他可以在 30 分鐘內完成一個項目的一個 api 的編寫，非常霸氣!不服噴他……
