作者：remyliu
針對業(yè)務(wù)問題，本文研究了多種計算引擎實現(xiàn)方案，并基于Clang/LLVM實現(xiàn)了一個C/C++解釋器，同時還探討了相關(guān)的Clang編譯技術(shù)在實現(xiàn)過程中的應(yīng)用。
業(yè)務(wù)面臨的問題
特征計算系統(tǒng)的演進
從工程角度來看，對日志流量進行分析是安全業(yè)務(wù)研發(fā)的重要內(nèi)容。如果將與“壞人”進行安全對抗比作一場長期持久的戰(zhàn)爭，那么特征計算系統(tǒng)就是對抗“壞人”的重要武器系統(tǒng)。該系統(tǒng)的功能是消費日志流，進行分析計算，并輸出特征信息。在傳統(tǒng)模式下，各個特征計算模塊分散、無管理、缺乏標(biāo)準(zhǔn)化，難以與其他武器系統(tǒng)對接，導(dǎo)致特征開發(fā)效率低下，進而使特征計算武器系統(tǒng)的威力不足。
下圖是特征計算模塊的開發(fā)流程：流程漫長費時效率低，滿足不了安全武器系統(tǒng)的快速響應(yīng)打擊“壞人”的需求。
為了解決上述問題，我們研發(fā)了新一代的特征計算系統(tǒng)，架構(gòu)圖如下：
在上述的架構(gòu)中，執(zhí)行引擎執(zhí)行用戶編輯的計算邏輯，如 z = x + y， 對輸入數(shù)據(jù)進行計算，輸出需要的特征，是系統(tǒng)的核心組件。
特征計算引擎探索
執(zhí)行引擎的實現(xiàn)有多種方案可選，如下圖所示的6種方案。每個方案都有各自的優(yōu)劣，實際工程可以根據(jù)需求進行選擇或組合。在業(yè)界，許多選擇使用Python引擎、Lua引擎或兩者的組合來執(zhí)行用戶編輯的Python腳本或Lua腳本。
下面描述了各個方案并列出了各方案的特點：
微信安全采用的是一個自研的DSL引擎，并在此基礎(chǔ)上擴展。原因是性能相對高，并且已被其他重要安全系統(tǒng)使用驗證。
DSL(Domain-Specific Language)是用于特定領(lǐng)域的編程語言，例如SQL就是一種DSL。我們自研DSL引擎，實際上是開發(fā)了一種自定義的編程語言，使用這種編程語言來編寫特征計算邏輯。要實現(xiàn)一種編程語言，當(dāng)然要實現(xiàn)這種語言的編譯器和執(zhí)行器，下面將介紹DSL引擎的實現(xiàn)和存在的問題。
微信特征計算引擎：DSL引擎實現(xiàn)
下圖實現(xiàn)展示了微信自研DSL語言的實現(xiàn)，首先定義了詞法描述文件和語法描述文件，采用 Lex 和 Yacc 生成詞法分析器Lexer和語法解析器Parser， 在這里Parser的輸出逆波蘭表達式，存儲在內(nèi)存中，然后解釋執(zhí)行表達式。整個DSL的引擎可以分為2部分：編譯和執(zhí)行，編譯1次，然后對每條輸入數(shù)據(jù)解釋執(zhí)行編譯后的表達式。
DSL引擎的問題
在業(yè)務(wù)接入和運營過程中發(fā)現(xiàn)3個主要的問題：
DSL新語言推廣學(xué)習(xí)成本高
自研DSL是一門新的語言，業(yè)務(wù)不熟悉使用，業(yè)務(wù)同學(xué)從原來的C++開發(fā)計算特征，轉(zhuǎn)為使用DSL，存在大量疑問，需要大量的研發(fā)支持， 盡管已經(jīng)提供了豐富的文檔支持。這無疑是公司內(nèi)推廣/公司外開源的阻礙，在缺少研發(fā)的大力支持下，大家愿意學(xué)習(xí)新的DSL語言嗎？使用業(yè)務(wù)通用熟悉的語言，可以更好的提升影響力，減少接入阻礙，需要的研發(fā)支持也更少。
前面也提到特征計算系統(tǒng)采用的是一個自研的DSL引擎，并在此基礎(chǔ)上擴展，為什么原來DSL語言不存在上述問題。因為原來DSL用于安全策略場景，主要是做邏輯判斷和條件判斷，例如支持+-*/和< = > if else 等簡單操作即可，很容易上手，反而不需要復(fù)雜的語言特性。
但是特征計算場景，側(cè)重于計算，需要大量的計算函數(shù)，庫函數(shù)，rpc調(diào)用等，需要的語言語法特性復(fù)雜的多，因為擴展的DSL也變得復(fù)雜，由此誕生了上述的問題。
大量重復(fù)實現(xiàn)已有的庫
實現(xiàn)一門可用性好的編程語言，除了實現(xiàn)語言本身，需要需要實現(xiàn)大量的基礎(chǔ)庫，例如需要實現(xiàn)字符串string庫，http庫，protobuf庫，vector和map等數(shù)據(jù)結(jié)構(gòu)，自研DSL也一樣，需要耗費大量精力在重新實現(xiàn)這些庫上，而且隨業(yè)務(wù)需求還一直在更新，不能完備。并且自研的庫函數(shù)使用風(fēng)格也和C++庫使用有較大差別，學(xué)習(xí)成本高。下面是DSL語言和庫與C++的對比， 微信后臺有成熟的C++基建，大家很熟悉C/C++語法。
其他方面的問題
DSL編譯過程中無通用的中間表示，無法使用業(yè)界已有的程序優(yōu)化算法，所以性能仍然不是很高。DSL的編譯報錯提示不友好不準(zhǔn)確，因為語法解析器Parser采用的是Yacc工具生成，Yacc使用的是LALR算法， 該算法缺陷之一是編譯報錯提示不夠準(zhǔn)確友好，實際使用過程中也是如此，業(yè)務(wù)同學(xué)也是常咨詢“這段DSL代碼哪里錯了?”。另外一個是擴展性較差，例如我們想基于DSL的parser 實現(xiàn)一個類似clangd的代碼補全和提示工具，提升DSL腳本開發(fā)體驗，幾乎很難實現(xiàn)，因為DSL的編譯器實現(xiàn)緊耦合沒有模塊化，我們只能基于很原始的字符串匹配來實現(xiàn)代碼補全提示。
探索新引擎方案
C++執(zhí)行引擎
微信后臺主要使用C++作為編程語言，基礎(chǔ)設(shè)施基本是以C++模塊構(gòu)建的，并積累了豐富的C++庫。在安全業(yè)務(wù)中，一開始就選擇了使用C++語言進行特征計算。如果將腳本語言也采用C++，業(yè)務(wù)同學(xué)可以熟練地使用，并且可以兼容現(xiàn)有的C++庫和標(biāo)準(zhǔn)庫，無需重新開發(fā)各種庫。然而，C++是一種靜態(tài)編譯語言，是否能改為解釋執(zhí)行呢？我們進行了調(diào)研，并基于Clang前端和LLVM JIT技術(shù)實現(xiàn)了一個C++執(zhí)行引擎，即一個C++解釋器。其結(jié)構(gòu)如下：
DSL引擎面對的問題C++引擎都可以完美的解決，C/C++語言容易接入學(xué)習(xí)成本低，開源易提升影響力；支持的庫豐富無需重復(fù)開發(fā)；最好的LLVM編譯優(yōu)化和JIT執(zhí)行帶來了和二進制執(zhí)行一樣的高性能， 基于Clang前端因此有世界上最友好的C/C++編譯報錯提示，同樣得益于Clang和LLVM模塊話帶來了極強的擴展性。
舉幾個例子說明C++引擎的擴展性，例如我們可以基于Clang 的前端庫實現(xiàn)類型clangd的代碼補全提示。采用這個結(jié)構(gòu)還能快速的支持其他語言，例如rust語言作為開發(fā)語言；除了JIT執(zhí)行，還能擴展生成WebAssembly，通過v8執(zhí)行。
引擎實現(xiàn)：C/C++解釋器ccint
C/C++是靜態(tài)編譯語言，但C/C++能否解釋執(zhí)行呢？答案是Yes，本文基于Clang和LLVM，不到500行代碼，實現(xiàn)了C/C++解釋器ccint，ccint源代碼在GitHub可獲齲其結(jié)構(gòu)如下圖所示：
C/C++文件被Clang前端經(jīng)過預(yù)處理，詞法分析，語法分析，語義檢查，編譯成LLVM中間表示，即LLVM IR。注意Clang前端并不是Clang二進制程序, 而是Clang編譯器提供的前端庫，LLVM IR經(jīng)過LLVM優(yōu)化器，根據(jù)優(yōu)化級別生成優(yōu)化后的LLVM IR存儲在內(nèi)存中, 常見的優(yōu)化有常量傳播，常量折疊，死代碼刪除，循環(huán)向量化等等。優(yōu)化后的LLVM IR被 LLVM ORC JIT執(zhí)行，輸出結(jié)果。JIT的執(zhí)行使用了LLVM后端代碼生成技術(shù)，輸入LLVM IR 輸出二進制指令到內(nèi)存，然后調(diào)用指定的函數(shù)符號執(zhí)行。
使用ccint解釋器輸出"hello world"
/*main.cpp*/
#include
#include
#include
void
ccint_main(){
std::vector
上面的例子使用標(biāo)準(zhǔn)庫的vector類和string類以及printf函數(shù)，解釋器執(zhí)行函數(shù)ccint_main, 可以看到解釋器很好的支持了C/C++標(biāo)準(zhǔn)庫。
ccint解釋器還有有如下的特性
支持完整的C++11/C++14/C++17語法；支持標(biāo)準(zhǔn)庫/動態(tài)庫/靜態(tài)庫；采用了JIT技術(shù)因此和C/C++二進制有相同的性能；模塊化編譯和執(zhí)行分離，方便使用到業(yè)務(wù)上。
ccint解釋器 在GitHub 還有展示動態(tài)庫靜態(tài)庫 和指定頭文件搜索路徑例子，可以參考。
ccint靈感來源于cling，cling是一個基于Clang和LLVM的交互式C/C++解釋器，由歐洲核子研究中心開發(fā)，用于處理大型強子對撞機LHC的實驗數(shù)據(jù)和驗證實驗?zāi)Ｐ停壳耙烟幚鞥B級別的實驗數(shù)據(jù)。然而直接使用cling并不必要，因為cling自身的代碼已經(jīng)達到了3萬行以上，其中大部分代碼是為了適配物理實驗領(lǐng)域的需求。此外cling對Clang和LLVM進行了較大的修改，并未合并到LLVM主線，這將需要大量的后續(xù)維護投入。參考cling的實現(xiàn)思路，借助于Clang和LLVM這兩個強大的工具，我們只需編寫很少的代碼（幾百行）就能實現(xiàn)功能豐富的C/C++解釋器。
后文將依次具體探討實現(xiàn)C/C++引擎使用到的Clang前端技術(shù)。
初識LLVM
LLVM(Low-Level Virtual Machine)是一個編譯器開發(fā)工具集，和虛擬機(Virtual Machine)沒任何關(guān)系。
LLVM主要包括如下工具和庫：一個源語言無關(guān)，目標(biāo)架構(gòu)無關(guān)的編譯優(yōu)化器，一個目標(biāo)架構(gòu)無關(guān)代碼生成器，C/C++編譯器Clang，LLDB調(diào)試器，LLD連接器，libc++庫等，其中編譯優(yōu)化器和代碼生成器是LLVM的核心。
為什么需要LLVM？LLVM解決了什么問題？
傳統(tǒng)的結(jié)構(gòu)是三段式，由前端，優(yōu)化器，后端組成，并且緊耦合，如果新實現(xiàn)一個編程語言或者新增一個指令集ISA，都需要重新實現(xiàn)這三段，而且優(yōu)化器不獨立，程序優(yōu)化即需要考慮語言特征，又需要考慮機器特性，難以專注優(yōu)化算法本身。
LLVM將傳統(tǒng)的三段式結(jié)構(gòu)中優(yōu)化階段單獨提取出來，并引入了一個通用的代碼中間表示LLVM IR，這樣前端研發(fā)人員只需要關(guān)注Source Code到LLVM IR的過程，專注前端的相關(guān)的算法 如新的parser算法和語義檢查；而編譯優(yōu)化研發(fā)人員只需要專注優(yōu)化算法的開發(fā)，因為中間表示LLVM IR和源代碼無關(guān)，指令集架構(gòu)ISA無關(guān)。后端研發(fā)只需要專注適配新的ISA，優(yōu)化代碼生成框架，優(yōu)化指令選擇，指令調(diào)度，寄存器分配等后端算法。大家術(shù)業(yè)有專攻，極大的繁榮了LLVM 生態(tài)。
如果需要研發(fā)新的編程語言，例如研發(fā)Rust語言，只需要研發(fā)語言的前端，就可以適配所有ISA。如果需要增加新的ISA，例如新指令集架構(gòu)RISC-V， 只需要采用LLVM Target-Independent Code Generator 開發(fā)一個新的后端，RISC-V后端就可以支持所有的語言。如果需要新增新的編譯優(yōu)化算法，只需往Common Optimizer加入新算法，不需要了解語言特征，也不需要了解架構(gòu)特性。
Clang
Clang是LLVM項目中一個C家族語言編譯前端, 支持C, C++, Objective C/C++, OpenCL, CUDA等的編譯，Clang的設(shè)計之初就注重模塊化，各個子模塊都提供了庫，能基于這些庫實現(xiàn)一些非常多個工具，如常用的C++代碼linter工具clang-tidy 代碼補全工具clangd，Clang的報錯提示也非常的友好，這兩方面相對GCC都有巨大的優(yōu)勢。
日常我們使用Clang包含兩方面含義：Clang驅(qū)動器和Clang前端，后續(xù)將分別介紹這兩方面內(nèi)容，并重點討論Clang前端。
Clang驅(qū)動器
日常使用的Clang工具就是一個驅(qū)動器，驅(qū)動整個編譯的流水線，將C/C++編譯成二進制，如下圖Clang驅(qū)動Clang編譯前端Frontend，匯編器Assembler， 連接器Linker等。
以一個例子說明
int
factorial
(
intn){
if(n<=
1)
return
1;
returnn*factorial(n-
1);
}
factorial.cpp
使用-ccc-print-phases打印各個階段的內(nèi)容，如下圖編譯文件factorial.cpp需要0～5總共6個階段，0輸入C++文件，1預(yù)處理，2編譯預(yù)處理后的代碼輸出中間表示IR(Intermediate Representation)， 3然后從IR生成匯編代碼，4匯編器將匯編代碼轉(zhuǎn)成二進制目標(biāo)代碼，5鏈接器將目標(biāo)代碼鏈接成二進制。
$clang-ccc-print-phasesfactorial.cpp
0:input,
"factorial.cpp",c++
1:preprocessor,{0},c++-cpp-output
2:compiler,{1},ir
3:backend,{2},assembler
4:assembler,{3},object
5:linker,{4},image
發(fā)現(xiàn)實際過程中Clang Driver會將各個階段進行合并, 例如前5個階段合并到clang-16程序執(zhí)行，最后的鏈接ld單獨執(zhí)行。
$clang-
###factorial.cpp
clangversion16.0.0
"/usr/local/bin/clang-16"
"-cc1"
"-emit-obj"
"-x"
"c++"
"factorial.cpp"...
"/usr/bin/ld"
"--eh-frame-hdr"
"-m"
"elf_x86_64"
"-o"
"a.out"...
clang_main
是Clang Driver主函數(shù)，定義在文件
tools/driver/driver.cpp
中，如果我們分析Clang的執(zhí)行流程，會發(fā)現(xiàn)有下面的調(diào)用棧
ExecutionAction字面意思是執(zhí)行一個
Action，什么是Action呢？
Action是一個編譯步驟，對應(yīng)Clang Driver流水線中的階段，可參考Clang文檔
整個Clang Driver流水線按從Action角度來看如下：
PreprocessJobAction：將源碼進行預(yù)處理
CompileJobAction ：將預(yù)處理結(jié)果轉(zhuǎn)為 LLVM IR(實際是IR的bitcode形式)
BackendJobAction：將LLVM IR 轉(zhuǎn)為 匯編文件.s
AssembleJobAction：將匯編文件.s轉(zhuǎn)為二進制目標(biāo)文件.o
LinkJobAction：將目標(biāo)文件.o鏈接成可執(zhí)行文件
上圖的調(diào)用棧中
cc1_main調(diào)用
ExectueAction一個
FrontendAction，F(xiàn)rontendAction代表Clang前端相關(guān)的階段
，下面介紹。
Clang前端
Clang前端是Driver的一部分也是編譯的核心，Clang前端負責(zé)將輸入的C/C++代碼編譯成中間表示IR(Intermediate Representation)
前端包括預(yù)處理/詞法解析，語法解析，語義檢查，代碼生成子模塊，Clang提供了命令行選項查看各階段的輸出內(nèi)容:
Lexer詞法解析
預(yù)處理Preprocessor和Lexer是組合一起的，Lexer輸入C/C++源文件，輸出Token流，查看Lexer的輸出：
輸出的Token包括類型和值， "factorial"的類型是identifier，值為"factorial"；左括號類型是l_paren，值是'('。最右邊Loc顯示了Token在文件中的位置，其中"factorial"在第1行第5列。
Token定義在文件
include/clang/Basic/TokenKinds.def 中
文件
include/clang/Parse/Parser.h 中函數(shù)
ConsumeToken和
TryConsumeToken讀取Token并前進到下一個Token：
Parser語法解析
Clang手寫了一個遞歸下降的語法解析器，沒有使用Bison等自動化Parser Generator工具等生成，原因是C++語法復(fù)雜，難以寫成LALR形式，而且LALR Parser的編譯報錯信息不友好，這里有進行相關(guān)的討論 the LALR grammar for C++。
"C++ grammar is ambiguous, context-dependent and potentially requires infinite lookahead to resolve some ambiguities"
要了解語法分析的過程，就需要先了解語法的規(guī)則，以下圖右側(cè)代碼說明，首先每個文件由一系列的申明Decl(Declaration)組成；這份代碼包含2個聲明：VarDecl變量聲明和FunctionDecl函數(shù)聲明，分別對應(yīng)變量
c和函數(shù)
factorial；函數(shù)由參數(shù)列表和函數(shù)體組成，參數(shù)聲明ParmValDecl對應(yīng)參數(shù)
int n，CompoundStmt組合語句就是對應(yīng)函數(shù)
factorial的函數(shù)體；函數(shù)體由一些列的聲明Decl(Declaration)和語句Stmt(Statement)組成，
factorial的函數(shù)體包含一個ValDecl變量聲明，IfStmt
if語句，ReturnStmt 返回語句，ValDecl變量聲明對應(yīng)局部變量
int k， 返回語句對應(yīng) 最后的return，if語句則包含條件表達式語句CondStmt，True分支語句ThenStmt，F(xiàn)alse分支語句ElseStmt，因為代碼中沒有else語句塊，所以圖中未給出ElseStmt，顯然if語句的條件表達式語句CondStmt對應(yīng)
n <= 1，True分支語句ThenStmt對應(yīng)
return 1，這里還能繼續(xù)往下分解語法規(guī)則，不再給出
。
了解語法規(guī)則后，分析下語法解析的過程，下圖展示了右側(cè)代碼的Parse過程，以解析其中
n <= 1為例輸出函數(shù)調(diào)用棧
Call Stack
調(diào)用棧20-15：這5個函數(shù)是Clang Driver函數(shù)，其中
clang_main是Clang Driver主函數(shù)，前面Clang Driver章節(jié)有說明。
調(diào)用棧14-10：
ParseAST函數(shù)是整個Parser的入口函數(shù)，根據(jù)語法規(guī)則，文件由Decl組成，先解析Decl，然后遞歸下降解析到函數(shù)聲明FunctionDecl，對應(yīng)的函數(shù)是
ParseFunctionDefinition，解析例子中的
int factorial (int ) {...}
函數(shù)
調(diào)用棧8：繼續(xù)對函數(shù)定義FunctionDecl遞歸下降解析，函數(shù)定義由參數(shù)列表和函數(shù)體組成，函數(shù)體解析函數(shù)
ParseCompoundStatementBody，解析例子中的函數(shù)
factorial的
函數(shù)體
{...}
調(diào)用棧7：函數(shù)體由聲明Decl和語句Statement組成，解析函數(shù)是
ParseStatemenOrDeclaration，解析一個語句或者聲明，該函數(shù)繼續(xù)遞歸下降解析到函數(shù)體第一條語句
調(diào)用棧5：函數(shù)體第一天語句是if語句，對應(yīng)解析函數(shù)是
ParseIfStatement，解析
if (n <= 1) return 1語句，繼續(xù)往下遞歸
調(diào)用棧4：if語句由條件表達式，true分支語句，false語句組成，首先解析條件表達式，條件表達式被括號包裹，形如'
(expresiion)'，所以這里調(diào)用的是
ParseParenExprOrConditon，解析
(n <= 1)
， 繼續(xù)遞歸
調(diào)用棧3：調(diào)用
ParseExpression解析表達式
n <= 1，繼續(xù)遞歸
調(diào)用棧2：表達式Experssion類型特別多，這里
n <= 1
，是一個assignment expression，所以這里調(diào)用的是ParseAssignmentExpression，繼續(xù)遞歸下降*
調(diào)用棧1:表達式
n <= 1由一個二元操作符*(Binay Operator)
和兩個操作數(shù)構(gòu)成，左邊操作數(shù)LHS(Left Hand Side)右邊操作數(shù)RHS(Right Hand Side)，表達式
n <=1最終被解析到右邊的操作數(shù) 整型字面量1，對應(yīng)的解析函數(shù)
ParseRHSOfBinaryExpression
C++語法是知名的復(fù)雜...語言標(biāo)準(zhǔn)也是非常的厚...好在Clang代碼結(jié)構(gòu)比較清晰，可以對有興趣的部分跟蹤調(diào)試，這里只展示了冰山一角，還不到一角。
Sema語義檢查
語義檢查包括變量或過程未經(jīng)聲明就使用、變量或過程名重復(fù)聲明、運算分量類型不匹配、操作符與操作數(shù)之間的類型不匹配。
Clang的語義檢查與一般方法不同，常規(guī)方案方法是在生成抽象語法樹AST之后，遍歷AST進行檢查。而Clang在AST節(jié)點生成過程中即時檢查語義。語法分析Parser完成語句檢查后，只表示語法正確，語義的正確性還需要檢查，如操作符要求的操作數(shù)類型是否符合。
還是以if條件表達式
n <= 1為例，前一節(jié)語法分析的調(diào)用棧最后調(diào)用到了
ParseRHSOfBinaryExpression函數(shù)，成功解析了表達式的RHS(Right Hand Side)，這時候
n <= 1的語法已經(jīng)正確匹配，在準(zhǔn)備構(gòu)建抽象語法樹AST前，先進入Sema模塊進行語義檢查，Parser和Sema之間的接口一般是ActOn，如圖中的
ActOnBinop，Sema模塊的結(jié)構(gòu)如下圖，首先從語義角度檢查程序正確性，
n <= 1表達式需要左右操作數(shù)(n 和 1)類型都是Arithmetic Type，即char/bool/int/long等等。函數(shù)
CheckMultiplyDivideOperands執(zhí)行這樣的檢查，如果操作數(shù)類型不正確，將調(diào)用
InvalidOperands，該函數(shù)進一步調(diào)用輔助函數(shù)
Diag， Diag處理報錯信息(error, warning, note)，本節(jié)后續(xù)還會解析展開。如果語義正確，最后為這個Binary Expresion創(chuàng)建抽象語法樹。
總結(jié)Sema模塊的工作，如果語義檢查不通過，就輸出報錯信息，通過就輸出AST。
Clang Diagnose子系統(tǒng)用于處理和發(fā)生各種診斷信息給開發(fā)者。Diagnose子系統(tǒng)的調(diào)用來源主要是Sema模塊，
Sema通過輔助函數(shù)
Diag 生成報錯信息(Emit a diagnostic)。
下圖中 編譯這段有問題的代碼，Clang輸出報錯信息。
信息主要由3部分組成：位置信息，如
factorial.cpp:1:1 文件第1行第1列。嚴重等級:
error, warning, note，圖中是error，內(nèi)容：*unknown type name 'intt’。
診斷類型在文件
include/clang/Basic/DiagnosticSemaKinds.td 中定義，上圖
unknown type name的定義如下：
Sema模塊通過DiagnoseUnkownTypename函數(shù)(定義在
lib/Sema/SemaDecl.cpp )發(fā)送
err_unknown_typename類型的診斷信息，使用的是輔助函數(shù)Diag。
AST抽象語法樹
Sema模塊生成抽象語法樹 AST (Abstract Syntax Tree)。和C/C++ 源代碼相比，Clang AST 是更方便分析和操作的程序表示形式，同時 AST 節(jié)點還有源代碼行列數(shù)等屬性。AST結(jié)構(gòu)也可輕易地轉(zhuǎn)換回源代碼，因此Clang AST特別適合用于進行靜態(tài)代碼分析、代碼重構(gòu)等工作，方便在C/C++源代碼層級上進行分析和修改。
實際的代碼產(chǎn)生的 AST結(jié)構(gòu)非常復(fù)雜，我們可以先有個整體印象。
上圖文件的AST結(jié)構(gòu)如下：
從上圖中可以看到，
factorial.cpp文件整個內(nèi)容稱為是翻譯單元
TranslationUnitDecl， 文件只包含一個函數(shù)聲明
FunctionDecl，函數(shù)聲明由參數(shù)聲明
ParmVarDecl和函數(shù)體語句
CompoundStmt組成，函數(shù)體包括一個if語句
IfStmt和返回語句
ReturnStmt。
Clang AST中節(jié)點的類型主要是Decl(聲明)， Stmt(語句) 和 Type(類型)，以及它們的子類。
Dec(聲明)
FunctionDecl(函數(shù)聲明)
VarDecl(變量聲明)
Stmt(語句)
DeclRefExpr(引用表達式)
BinaryOperator(二元運算符)
IntegerLiteral(整形字面量)
CallExpr(函數(shù)調(diào)用表達式)
ifStmt(if語句)
CompoundStmt(復(fù)合語句)
Expr(表達式)
Type(類型)
BuiltInType(內(nèi)置類型)
PointerType(指針類型)
ArrayType(數(shù)組類型)
使用Clang的-ast-dump查看輸出的AST的詳細結(jié)構(gòu)
clang-c-Xclang-ast-dumpfactorial.cpp
輸出如下：
源代碼對應(yīng)的AST結(jié)構(gòu)如圖：
怎么訪問/遍歷/修改AST，如何基于Clang AST實現(xiàn)有趣的工具和功能呢，后面介紹基于Clang開始時展開。
CodeGen代碼生成
CodeGen模塊使用AST visitors以訪問者模式(Visitor Pattern)遍歷AST，然后使用IRBuilder類構(gòu)建中間表示LLVM IR輸出。
以構(gòu)建if語句條件表達式
n <= 1的LLVM IR為例， CodeGen調(diào)用棧
Call Stack如下：
調(diào)用棧19-15： 這5個函數(shù)是Clang Driver函數(shù)
調(diào)用棧13-12：AST的頂層節(jié)點是一個FunctionDecl，對應(yīng)例子中的
int factorial (int ) {...}**函數(shù)，EmitGlobalFunctionDefiniton為函數(shù)factorial輸出LLVM IR，遞歸訪問FunctionDecl的AST子節(jié)點
調(diào)用棧10-8： 函數(shù)定義由參數(shù)列表ParmVarDecl和函數(shù)體CompoundStmt組成，EmitCompoundStmtWithoutScope為函數(shù)體構(gòu)造輸出LLVM IR，繼續(xù)遞歸訪問CompoundStmt的AST節(jié)點
調(diào)用棧7-6：為IfStmt構(gòu)造輸出IR，繼續(xù)遞歸訪問AST子節(jié)點
調(diào)用棧4： 為if語句的條件表達‘n <= 1’式構(gòu)造輸出IR
，繼續(xù)訪問AST子節(jié)點
調(diào)用棧3-2：構(gòu)造二元運算符‘<=’的IR
調(diào)用棧1: 輸出二元運算符‘<=’ 的操作數(shù)字面量1
使用Clang的-emit-llvm選項，可以查看輸出的LLVM IR
clang-S-emit-llvmfactorial.cpp
后文將詳細介紹CodeGen輸出的LLVM IR結(jié)構(gòu)
基于Clang的開發(fā)
Clang設(shè)計之初就被設(shè)計為一系列庫。通過這一系列庫，開發(fā)者可以實現(xiàn)各種各樣強大的功能，玩轉(zhuǎn)編程語言，本章介紹如何基于這些庫做開發(fā)。
Clang開發(fā)示例
在探索Clang的過程中，本人收集和開發(fā)了一些Clang開發(fā)用例llvm-example，主要是AST的遍歷和修改，可以通過GitHub獲取代碼，編譯和運行。
基于Clang開發(fā)
執(zhí)行下面的命令，使用-emit-llvm選項編譯一個cpp文件到LLVM IR，Clang內(nèi)部使用了哪些類和數(shù)據(jù)結(jié)構(gòu)呢，執(zhí)行流程是怎樣的，如果我們想在這個編譯流程上加上自定義的內(nèi)容呢？
clang-S-emit-llvmfactorial.cpp
Clang的編譯流程和數(shù)據(jù)結(jié)構(gòu)設(shè)計，給開發(fā)這預(yù)留了大量的重寫和自定義Hook的地方，下圖展示了從cpp代碼到LLVM IR的內(nèi)部流程。
CompilerInstance類抽象Clang編譯器，它描述了一個編譯器的方方面面，包含了預(yù)處理Preprocessor，ASTContext(抽象語法樹類)，診斷類DiagnosticsEngine等等。編譯器CompilerInstance對象使用ExecuteAction執(zhí)行具體的前端動作FrontendAction，F(xiàn)rontendAction是前端動作的抽象類，開發(fā)者可以重寫FrontendAction類的函數(shù)，執(zhí)行自定義的操作。
如果執(zhí)行的是如下命令，Clang編譯器具體執(zhí)行的是
EmitLLVMOnlyAction，上圖可以看到它和FrontendAction的繼承關(guān)系
。
clang-S-emit-llvmfactorial.cpp
EmitLLVMOnlyAction如它的名字含義一樣，只輸出LLVM IR，F(xiàn)rontendAction還有其他的子類實現(xiàn)，包括
EmitAssemblyAction，Clang具體執(zhí)行哪個由編譯參數(shù)決定，參見代碼
lib/Frontend/CompilerInvocation.cpp 。
如果需要自定義實現(xiàn)FrontendAction，可以繼承該類，并重寫它的幾個函數(shù)，實現(xiàn)需要的邏輯。
示例中clang-funcnames實現(xiàn)了自定義的
MyFrontendAction。
ASTConsumer類是讀取抽象語法樹AST的基礎(chǔ)類，也預(yù)留了大量函數(shù)給開發(fā)者進行重寫，Clang里
ASTConsumer也有多種子類實現(xiàn)如下圖
使用-emit-llvm輸出LLVM IR時， Clang使用的是
BackendConusmer讀取
AST，同樣如果自定義AST處理邏輯，可以重新它的如下等函數(shù)
示例中clang-funcnames實現(xiàn)了自定義的
MyASTConsumer。
RecursiveASTVisitor訪問處理具體AST節(jié)點的基礎(chǔ)類，
ASTConsumer使用它訪問具體的語法樹節(jié)點，它們之間的關(guān)系如下：
RecursiveASTVisitor提供了一些列處理AST節(jié)點的函數(shù)，如訪問表達式
VisitDecl和訪問聲明
VisitDecl，都是可重寫的函數(shù)：
示例中clang-funcnames實現(xiàn)了自定義的MyASTVisitor：
總結(jié)下一下，如果使用Clang進行靜態(tài)代碼分析、代碼重構(gòu)等AST遍歷和編輯工作，主要涉及的基礎(chǔ)類是
FrontendAction，
ASTConsumer和
RecursiveASTVisitor，這三個類非常的龐大，Clang文檔給出了這些類的詳細結(jié)構(gòu)。這幾個類的交互和基本使用方法可參考本人開發(fā)收集的Clang開發(fā)用例llvm-example。
寫在最后
重新引用上圖，實現(xiàn)特征計算引擎有多種方案可選，但沒有一種方案能解決所有問題，每種方案都有各自的優(yōu)劣�？紤]到微信后臺主要使用C/C++語言，因此采用C/C++語言的WebAssembly方案和類C/C++語言的DSL是不錯的選擇，結(jié)合Python和Lua完全能滿足業(yè)務(wù)需求。本文通過探索C/C++解釋執(zhí)行，提出了一種基于Clang/LLVM的方案，具有高性能且能與微信C/C++基建良好兼容，值得進一步研究。
