你好，我是小X。

曹大最近開 Go 課程了，小X 正在和曹大學(xué) Go。

這個(gè)系列會(huì)講一些從課程中學(xué)到的讓人醍醐灌頂?shù)臇|西，撥云見日，帶你重新認(rèn)識(shí) Go。

抽象語法樹是編譯過程中的一個(gè)中間產(chǎn)物，一般簡(jiǎn)單了解一下就行了。但我們可以把 Go 語言的整個(gè) parser 和 ast 包直接拿來用，在一些場(chǎng)景下有很大的威力。

什么是 ast 呢，我從維基百科上摘錄了一段：

在計(jì)算機(jī)科學(xué)中，抽象語法樹（Abstract Syntax Tree，AST），或簡(jiǎn)稱語法樹（Syntax tree），是源代碼語法結(jié)構(gòu)的一種抽象表示。它以樹狀的形式表現(xiàn)編程語言的語法結(jié)構(gòu)，樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。

核心就是說 ast 能以一種樹的形式表示代碼結(jié)構(gòu)。有了樹結(jié)構(gòu)，就可以對(duì)它做遍歷，能干很多事。

假定一個(gè)場(chǎng)景

假定一個(gè)場(chǎng)景：我們可以從司機(jī)平臺(tái)的某個(gè)接口獲取司機(jī)的各種特征，例如：年齡、訂單數(shù)、收入、每天駕駛時(shí)長(zhǎng)、駕齡、平均車速、被投訴次數(shù)……數(shù)據(jù)一般采用 json 來傳遞。

司機(jī)平臺(tái)的運(yùn)營小姐姐經(jīng)常需要搞一些活動(dòng)，例如選出：

• 訂單數(shù)超過 10000，且駕齡超過 5 年的老司機(jī)
• 每天駕駛時(shí)小于 3 小時(shí)，且收入超過 500 的高效司機(jī)
• 年齡大于 40，且平均速度大于 70 的“狂野”司機(jī)
• ……

這些規(guī)則并不是固定的，經(jīng)常在變化，但總歸是各種司機(jī)特征的組合。

為了簡(jiǎn)化，我們選取 2 個(gè)特征，并用一個(gè) Driver 結(jié)構(gòu)體來表示：

type Driver struct {
 Orders         int
 DrivingYears   int
}

為了配合運(yùn)營搞活動(dòng)，我們需要根據(jù)運(yùn)營給的規(guī)則來判斷一個(gè)司機(jī)是否符合要求。

如果公司人多，可以安排一個(gè) rd 專門伺候運(yùn)營小姐姐，每次做活動(dòng)都來手動(dòng)修改代碼，也不是不可以。并且其實(shí)挺簡(jiǎn)單，我們來寫一個(gè)示例代碼：

// 從第三方獲取司機(jī)特征，json 表示
func getDriverRemote() []byte {
 return []byte(`{"orders":100000,"driving_years":18}`)
}

// 判斷是否為老司機(jī)
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 獲取一個(gè)司機(jī)的特征數(shù)據(jù)，用 json 表示。接著 json.Unmarshal 來反序列化 Driver 結(jié)構(gòu)體。最后調(diào)用 isOldDriver 函數(shù)來判斷此司機(jī)是否符合運(yùn)營的規(guī)則。

isOldDriver 根據(jù) Driver 結(jié)構(gòu)體的 2 個(gè)字段使用 if 語句來判斷此司機(jī)是否為老司機(jī)。

確實(shí)還挺簡(jiǎn)單。

但是每次更新規(guī)則還得經(jīng)過一次完整的上線流程，也挺麻煩的。有沒有更簡(jiǎn)單的辦法呢？使得我們可以直接解析運(yùn)營小組姐給我們的一個(gè)用字符串表示的規(guī)則，并直接返回一個(gè) bool 型的值，表示是否滿足條件。

有的！

接下來就是本文的核心內(nèi)容，如何使用 ast 來完成同樣的功能。

直觀地理解如何用 ast 解析規(guī)則

使用 ast 包提供的一些函數(shù)，我們可以非常方便地將如下的規(guī)則字符串：

orders > 10000 && driving_years > 5

解析成一棵這樣的二叉樹：

其中，ast.BinaryExpr 代表一個(gè)二元表達(dá)式，它由 X 和 Y 以及符號(hào) OP 三部分組成。最上面的一個(gè) BinaryExpr 表示規(guī)則的左半部分和右半部分相與。

很明顯，左半部分就是：orders > 10000，而右半部分則是：driving_years > 5。神奇的是，左半部分和右半部分恰好又都是一個(gè)二元表達(dá)式。

左半部分的 orders > 10000 其實(shí)也是最小的葉子節(jié)點(diǎn)，它可以算出來一個(gè) bool 值。把它拆開來之后，又可以分成 X、Y、OP。X 是 orders，OP 是 ">"，Y 則是 "10000"。其中 X 表示一個(gè)標(biāo)識(shí)符，是 ast.Ident 類型，Y 表示一個(gè)基本類型的字面量，例如 int 型、字符串型……是 ast.BasicLit 類型。

右半部分的 driving_years > 18 也可以照此拆分。

然后，從 json 中取出這個(gè)司機(jī)的 orders 字段的值為 100000，它比 10000 大，所以左半部分算出來為 true。同理，右半部分算出來也為 true。最后，再算最外層的 "&&"，結(jié)果仍然為 true。

至此，直接根據(jù)規(guī)則字符串，我們就可以算出來結(jié)果。

如果寫成程序的話，就是一個(gè) dfs 的遍歷過程。如果不是葉子結(jié)點(diǎn)，那就是二元表達(dá)式結(jié)點(diǎn)，那就一定有 X、Y、OP 部分。遞歸地遍歷 X，如果 X 是葉子結(jié)點(diǎn)，那就結(jié)束遞歸，并計(jì)算出 X 的值……

這里再展示一個(gè)用 ast 包打印出來的抽象語法樹：

上圖中，1、2、3 表示最外層的二元表達(dá)式；4、5、6 則表示左邊這個(gè)二元表達(dá)式。

結(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 表示。

如果你還對(duì)實(shí)現(xiàn)感興趣，那就繼續(xù)看下面的原理分析部分，否則可以直接跳到結(jié)尾總結(jié)部分。

原理分析

還是用上面那個(gè)例子，我們直接寫一個(gè)表達(dá)式：

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))
}

為了簡(jiǎn)單，我們直接用 map 來代替 json，道理是一樣的，僅僅為了方便。

Eval 函數(shù)判斷 rule 的真假：

// Eval : 計(jì)算 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
}

先將表達(dá)式解析成 Expr，接著調(diào)用 judge 函數(shù)計(jì)算結(jié)果：

// dfs
func judge(bop ast.Node, m map[string]int64) bool {
    // 葉子結(jié)點(diǎn)
 if isLeaf(bop) {
  // 斷言成二元表達(dá)式
  expr := bop.(*ast.BinaryExpr)
  x := expr.X.(*ast.Ident) // 左邊
  y := expr.Y.(*ast.BasicLit) // 右邊

  // 如果是 ">" 符號(hào)
  if expr.Op == token.GTR {
   left := m[x.Name]
   right, _ := strconv.ParseInt(y.Value, 10, 64)
   return left > right
  }
  return false
 }

 // 不是葉子節(jié)點(diǎn)那么一定是 binary expression（我們目前只處理二元表達(dá)式）
 expr, ok := bop.(*ast.BinaryExpr)
 if !ok {
  println("this cannot be true")
  return false
 }

 // 遞歸地計(jì)算左節(jié)點(diǎn)和右節(jié)點(diǎn)的值
 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 遞歸地計(jì)算表達(dá)式的值。

遞歸地終止條件是葉子節(jié)點(diǎn)：

// 判斷是否是葉子節(jié)點(diǎn)
func isLeaf(bop ast.Node) bool {
 expr, ok := bop.(*ast.BinaryExpr)
 if !ok {
  return false
 }

 // 二元表達(dá)式的最小單位，左節(jié)點(diǎn)是標(biāo)識(shí)符，右節(jié)點(diǎn)是值
 _, okL := expr.X.(*ast.Ident)
 _, okR := expr.Y.(*ast.BasicLit)
 if okL && okR {
  return true
 }

 return false
}

總結(jié)

今天這篇文章主要講了如何用 ast 包和 parser 包解析一個(gè)二元表達(dá)式，并見識(shí)到了它的威力，利用它可以做成一個(gè)非常簡(jiǎn)單的規(guī)則引擎。

其實(shí)利用 ast 包還可以做更多有意思的事情。例如批量把 thrift 文件轉(zhuǎn)化成 proto 文件、解析 sql 語句并做一些審計(jì)……

想要更深入的學(xué)習(xí)，可以看曹大這篇《golang 和 ast》^[1]，據(jù)曹大自己說，他可以在 30 分鐘內(nèi)完成一個(gè)項(xiàng)目的一個(gè) api 的編寫，非常霸氣！不服噴他……

好了，這就是今天全部的內(nèi)容了~ 我是小X，我們下期再見~

參考資料