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