SolidityのparserをGoで作ってみる

uji

Goのparserや

gqlgenなどでお馴染みのvektah氏のgqlparserが色々参考になりそう
https://github.com/vektah/gqlparser

ast周りから作っていくか

uji

~~js実装のSolidity parser~~
~~https://github.com/ConsenSysMesh/solidity-parser~~

~~PEG.jsというJavaScript用Parser Generatorが使われてるっぽい~~
~~https://pegjs.org/documentation~~

solhintとかで使われてるのはこっちだった

ANTLR(アントラー)という構文解析ツールが使われているっぽい
https://www.antlr.org/

uji

小さくゴールを設けた方がモチベを維持しやすそうなので、HelloWorldの実装のparseを最初のゴールに

pragma solidity ^0.8.13;

contract HelloWorld {
    
    function hello() public pure returns (string) {
        return "Hello World!!";
    }
}

uji

ANTLR公式が出している Solidity.g4(solidity-parser/antlrにあるものと多分一緒)からTypeScriptのファイルが生成されてそう

ethereum/solidity公式からもgrammerが公開されている

このあたりをGoのコードに落とし込んでいければ良さそう

uji

フューチャー株式会社さんが技術ブログでANTLRの記事を投稿されていてわかりやすかった

uji

Goのコードも生成できるみたい
https://github.com/antlr/antlr4
生成ツールのDockerFikeもあったのでローカルでビルドして使ってみる

公式からDockerHubとかのRegistoryにpullして欲しいな…

uji

生成ファイルに antlr/antlr4/runtime/Go/antlr への依存が生まれ、細部の挙動が制御しづらくなる
go/ast の仕組みから乖離してしまう
parser開発の勉強にならない

などの理由から、ANTLRを使うアプローチを一旦やめることにした

vektah/gqlparser でもANTLRは使われていなかった
(GraphQLも .g4 はある https://github.com/antlr/grammars-v4/blob/master/graphql/GraphQL.g4)

uji

antlrを試したbranch https://github.com/uji/solparser/tree/antlr4

uji

go/astはPackage structをルートに抽象構文木が表現されている

同じようにSolidity.g4を参考にしながら抽象構文機をstructで表現していく

// ここはSolidity.g4のpragmaDirective 
pragma solidity ^0.8.13;

// ここはSolidity.g4のcontractDefinition
contract HelloWorld {
    
    function hello() public pure returns (string) { 
        return "Hello World!!";
    }
}

とりあえずHelloWorldのスクリプトだけ表現できるように最小限に実装した

uji

parserの設計について情報を集めていたところ、先日開催されたGoCouference 2022 Springのyouheimutaさんのセッションでprotobufのparserの話をされていたのを思い出した

今一番求めていた内容がそこにはあった
parserとlexerに分けて実装するアプローチについて詳しく解説されていてためになった

YouTubeのvideoIDが不正ですhttps://youtu.be/mknMioJ1hMk?t=268

uji

lexer(字句解析器)から実装を進めていく
bufio.Scannerとか使うのが良さそうかな

Split() に渡す関数を実装してやれば、やりたいことが出来そうな気がする

↓bufio.Scannerで遊んだコード
https://go.dev/play/p/gYbagX2IRaH

色々他のparserのコードを巡ったところ、bufio.Scannerを使ってるのものはあまりなく、bufio.ReaderからScannerを独自実装しているパターンが多かった
必要に応じて独自実装に切り替えるのがよさそう

uji

字句解析にTokenの定義が必要になるので
Tokenの型を最低限定義した

Solidity、keyword意外と多くて全部対応しきるの大変そう

uji

lexerの実装
bufio.Scanner のSplit関数に渡すことができるように関数を実装した

このSplit関数は公式から提供されているものがいくつかある
その中でbufio.ScanWordsという関数が、単語ごとにSplitする関数で、今回の字句ごとのSplitと処理が近い
https://pkg.go.dev/bufio#ScanWords

bufio.ScanWords をコピーしてSolidityのTokenの処理を追加する改良を加え、それっぽい挙動が確認できた

string→TokenTypeのキャストとかをswitchで書いたけどmap使った方がパフォーマンス良さそうだなと後から思った

uji

parserの実装に入っていく
parseの処理は可読性やテスタビリティを考慮して関数を細かく分けて実装する

まずは骨組みだけ

uji

試しにPragmaDirectiveのparseを実装してみた
実装したlexerを使ってシンプルな実装で抽象構文木のstructを返すことができた

// input
"pragma solidity ^0.8.13;"

// output
&ast.PragmaDirective{
  PragmaName: "solidity",
  PragmaValue: ast.PragmaValue{
    Version:    "0.8.13",
    Expression: "^",
  }
}

uji

parseでerrorがあった場合は、どこの字句に問題があるのかを出したいのでtokenに位置情報を持たせることを検討する

go/astではtokenはNodeというインターフェースを満たすように実装されており、位置情報を表すtoken.Posを返すようにされていたので真似しようかな

他で参考にしているparserも似たようなことをやってそう

tenntennさんにもアドバイスをもらえた

uji

token.FileSetも見てみた

baseにオフセット情報が入るっぽい

token.Posを引数に、FileSetからFileを取ってくる処理を見ると、baseとtoken.Posを比較して取ってきている

なんとなくtoken.Posの使われ方がわかった

uji

bufio.scannerの利用を断念

offsetの管理がされてないのでposを作ろうとしたときにスペースや改行を残したSplitが必要でコードが複雑になりそう
Scan()のインターフェースが微妙。errorがあった場合Scannerのfieldに格納され、それを読み取る必要がある

https://pkg.go.dev/bufio#Scanner

uji

一旦登場人物の責務と発生するイベントを整理

token
- 言語的に意味のある最小単位
- 文字列、種類、位置情報を持つ
parser
- lexerを使ってtokenを取得しながら構文チェック
- 構文チェックに引っかかった場合はtokenの位置情報を使ってエラー生成
lexer
- scannerを使ってtokenになりうる文字列を取ってくる
- 取得した文字列と位置情報からtokenを生成しparserに返す
scanner
- 読み込みが完了している位置を管理
- 対象をtokenになりうる文字列に分割してposと共につずつlexerに返す
- tokenに含まれないスペースはスキップする

uji

公式Docにgrammerの図が公開されていて参考になった

top level となるsource unit のルールを見るとpragma, contract-definition, function-definition のparseを実装できれば最初のゴールはみたせそう

uji

parserでの分岐処理を書きやすくするために、lexerにトークンを1つ先読み(look ahead)できる機能であるPeekを実装した
PeekはScanの時のように読み込み位置が進まないようになっている

以下の例のように先読みした結果をつかってparserの分岐を実装することができる

if !p.lexer.Peek() {
  // 読み込みが終了していた場合の処理
}
 
// PeekToken()で次のTokenが取得できる
switch p.lexer.PeekToken().TokenType {
case lexer.Pragma:
  // pragma のparse処理
case lexer.Abstract, lexer.Contract:
  // contract-definition
case lexer.Function:
  // function-definition
}

トークンを先読みして処理を分岐する手法はLALR法と呼ばれており、yaccなどでも使われているらしい

LALR法(wikipedia)

uji

どの粒度の構文ルールをTokenとして扱うかを考える

ethereum/solidityのToken listはこれ

StringLiteralやCommentLiteralなどのLiteralもTokenとして定義されているのでこれに合わせる
Lexerのgrammarと定義がずれている部分があったが、便宜上Token.hに準ずるようにした
(例えば、Token.hにあるStringLiteralはgrammerではNonEmptyStringLiteralとEmptyStringLiteralに分けて定義されている
https://github.com/ethereum/solidity/blob/develop/docs/grammar/SolidityLexer.g4#L164-L171)

Scannerでとってきた文字列群をLexerでToken群に整理してParserに渡す

uji

path のParseを実装しているとNonEmptyStringLiteralかどうかを見る必要があったのでToken.hに準ずる作戦はやめてgrammerに寄せるようにした

uji

<<= や ++ など複数の記号からなる演算子を最小の単位としてscanするようにscannerに実装を加えた
先読みして switch, ifで処理を分岐するかなり愚直に実装になっている

もっとスマートに実装出来る気がするけどこのまま進める。完成重視

uji

Lexer に StringLiteral tokenのparseを実装
quoteを検出して次のquoteが見つかるまで文字列を結合し返却する

uji

StringLiteralが解析できるようになったので、

function hello() public pure returns (string) {
    return "Hello World!!";
}

を解析できるようにしたい

ここはgrammarで定義されているfunction-definitionに該当する

赤線を引いているところがサンプルコードで使われている要素なのでここを優先的に対応していく

uji

一番深いblockから対応を進める

expressionがとても複雑...

とりあえずliteralをexpressionとして扱えるようにする

literal -> expression -> statement -> block と愚直に実装を進めた

uji

愚直に実装を進めてsampleコードはastに展開できるように

func Example() {
	input := `
pragma solidity ^0.8.13;

contract HelloWorld {
    function hello() public pure returns (string) {
        return "Hello World!!";
    }
}`

	parser := solparser.New(strings.NewReader(input))

	got, err := parser.Parse()
	if err != nil {
		fmt.Println(err)
		return
	}

	fmt.Println(got.ContractDefinition.Identifier.Value)
	fmt.Println(got.ContractDefinition.ContractBodyElements[0].(*ast.FunctionDefinition).FunctionDescriptor.Value)

	// Output:
	// HelloWorld
	// hello
}