抽象構文木（AST）をトラバースする #golang

December 31, 2016

この記事はQiitaの記事をエクスポートしたものです。内容が古くなっている可能性があります。

はじめに

筆者が以前書いた「簡単な式の評価機を作ってみる」や「【実践goパッケージ】文字列から複素数型の値をパースする」などの記事では、文字列で表された式から抽象構文木(AST)を取得し、ASTのノードの種類ごとに再帰的に処理する関数を書きました。

この記事では、go/astパッケージに用意されている、ast.Inspect関数やast.Walk関数を使って、ASTをトラバースする方法について解説します。

なお、ASTを取得する方法については、「ASTを取得する方法を調べる」という記事を書いていますので、そちらを参考にしてください。

この記事で扱っているGoのバージョンは1.7.4です。

`ast.Inspect`関数

ast.Inspectは、ASTを深さ優先でトラバースする関数で、以下のようなシグニチャを持ちます。

func Inspect(node Node, f func(Node) bool)

第1引数のnodeは、トラバースするASTのルートノードを表し、第2引数のfはトラバースに使用される関数です。関数fは、引数にast.Node、つまりAST上の任意のノードを取り、戻り値にbool型の値を返します。戻り値がtrueの場合は、子ノードに対して再帰的に関数fを適用していきます。なお、すべてのnilではない子ノードに対して、関数fを適用した後に、f(nil)が実行されます。

たとえば、以下のように1+1のASTに対してast.Inspect関数を呼び出してみましょう（The Go Playgroundで実行する）。

expr, err := parser.ParseExpr(`1+1`)
if err != nil {
	log.Fatalln("Error:", err)
}

ast.Inspect(expr, func(n ast.Node) bool {
	fmt.Printf("%[1]T %[1]v\n", n)
	return true
})

1+1のASTは以下のようになっており、ast.BinaryExprの子ノードとして2つのast.BasicLitが保持されています。

*ast.BinaryExpr (+)
├── *ast.BasicLit (1)
└── *ast.BasicLit (1)

そのため、上記のコードを実行すると以下のような結果が表示されます。

*ast.BinaryExpr &{0x1050e150 2 + 0x1050e160}
*ast.BasicLit &{1 INT 1}
<nil> <nil>
*ast.BasicLit &{3 INT 1}
<nil> <nil>
<nil> <nil>

ast.Inspect関数は、まずルールノードの*ast.BinaryExpr型の値に対して、関数fを適用します。そしてその後、子ノードである2つの*ast.BasicLit型の値に対して、関数fを適用していきます。ここで関数fの適用は、深さ優先で行われるため、*ast.BasicLit型の子ノードについても関数fが適用されようとします。しかし、*ast.BasicLit型のノードには、子ノードが存在しないため、最後にf(nil)が実行され、*ast.BinaryExpr型のノードの処理へ戻ります。*ast.BinaryExpr型のノードのすべての子ノードについて関数fを適用したので、最後にf(nil)を実行し、処理が終了します。

少し分かりづらいかもしれないので、深さによって先頭に適度にスペースを入れる処理を入れてみます（The Go Playgroundで実行する）。

expr, err := parser.ParseExpr(`1+1`)
if err != nil {
	log.Fatalln("Error:", err)
}

var i int
ast.Inspect(expr, func(n ast.Node) bool {
	fmt.Printf("%s%[2]T %[2]v\n", strings.Repeat("  ", i), n)
	if n != nil {
		i++
	} else {
		i--
	}
	return true
})

ここでiは、そのノードの深さを表しています。関数fの引数であるnがnilになる場合は、すべての子要素の処理が終わっているということなので、iの値を引いておき、それ以外は加算しています。

改めて実行すると、以下のような結果が得られます。

*ast.BinaryExpr &{0x1050e150 2 + 0x1050e160}
  *ast.BasicLit &{1 INT 1}
    <nil> <nil>
  *ast.BasicLit &{3 INT 1}
    <nil> <nil>
  <nil> <nil>

さきほどの実行結果より幾分分かりやすくなったんじゃないかと思います。

ast.Inspect関数は、ASTの中から特定のノードを探し出して処理する用途に用いられる事が多く、ast.Walk関数よりも簡易的に用いられます。実際、ast.Inpsect関数の中では、以下のようにast.Walk関数が用いられています。

type inspector func(Node) bool

func (f inspector) Visit(node Node) Visitor {
	if f(node) {
		return f
	}
	return nil
}

// Inspect traverses an AST in depth-first order: It starts by calling
// f(node); node must not be nil. If f returns true, Inspect invokes f
// recursively for each of the non-nil children of node, followed by a
// call of f(nil).
//
func Inspect(node Node, f func(Node) bool) {
	Walk(inspector(f), node)
}

それでは次にast.Walk関数について解説します。

`ast.Walk`関数

ast.Inspect内でast.Walk関数が使われていることから分かるように、子ノードに対する処理の仕方や深さ優先で探索する点は同じです。一方で、ast.Walk関数は、以下のようなシグニチャをとっており、ast.Inspect関数より柔軟です。

func Walk(v Visitor, node Node)

第2引数のnodeに関しては、ast.Inspect関数の第1引数のnodeと同じでトラバースするASTのルートノードを表します。第1引数のast.Visitor型はインタフェースであり、以下のように定義されています。

type Visitor interface {
        Visit(node Node) (w Visitor)
}

Visitメソッドは、ノードに対する処理を記述したメソッドで、引数にast.Node型の値を取り、戻り値にast.Visitorを返します。ast.Walkは各子ノードに対して、このVisitメソッドを適用していき、戻り値のwがnilになった場合にそれより下の子ノードに対しての処理をやめます。

また、各子ノードについては、Visitメソッドが返すast.Visitor型の値が持つVisitメソッドを適用します。こうすることで、以下のようにノードの種類によって処理を分けることができます（The Go Playgroundで実行する）。

package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"log"
)

type visitorFunc func(node ast.Node) (w ast.Visitor)

func (f visitorFunc) Visit(node ast.Node) (w ast.Visitor) {
	return f(node)
}

func main() {
	expr, err := parser.ParseExpr(`1+1`)
	if err != nil {
		log.Fatalln("Error:", err)
	}

	var v1, v2 visitorFunc

	v1 = visitorFunc(func(node ast.Node) (w ast.Visitor) {
		fmt.Printf("%T\n", node)
		switch node.(type) {
		case *ast.BinaryExpr:
			return v2
		}
		return nil
	})

	v2 = visitorFunc(func(node ast.Node) (w ast.Visitor) {
		if node == nil {
			return nil
		}
		lit := node.(*ast.BasicLit)
		fmt.Printf("BasicLit: %s\n", lit.Value)
		return nil
	})

	ast.Walk(v1, expr)
}

このように、v2は*ast.BasicLitの子ノードだけを処理することができます。なお、すべての子ノードの処理が終わった後に、nodeがnilでVisitメソッドが呼ばれるという点については注意しなければいけません。

なお、標準パッケージでは、途中でVisitorを切り替えるような処理は見受けられませんでした。そのため、ノードの種類によって切り替えるということはあまりしないのかもしれません。

おわりに

この記事では、2種類のASTをトラバースする方法について解説しました。 ast.Inspect関数は簡易的にASTをトラバースでき、ast.Walk関数についてはより柔軟性のあるトラバースができます。ぜひ、ASTを処理する際は、自前の再帰呼び出しだけではなく、これらの関数も使ってみてください。

はじめに

ast.Inspect関数

ast.Walk関数

おわりに

`ast.Inspect`関数

`ast.Walk`関数