1 files changed, 386 insertions, 0 deletions
diff --git a/src/go/ast/walk.go b/src/go/ast/walk.go
new file mode 100644
index 000000000..73ac38647
--- /dev/null
+++ b/src/go/ast/walk.go
@@ -0,0 +1,386 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ast
+
+import "fmt"
+
+// A Visitor's Visit method is invoked for each node encountered by Walk.
+// If the result visitor w is not nil, Walk visits each of the children
+// of node with the visitor w, followed by a call of w.Visit(nil).
+type Visitor interface {
+	Visit(node Node) (w Visitor)
+}
+
+// Helper functions for common node lists. They may be empty.
+
+func walkIdentList(v Visitor, list []*Ident) {
+	for _, x := range list {
+		Walk(v, x)
+	}
+}
+
+func walkExprList(v Visitor, list []Expr) {
+	for _, x := range list {
+		Walk(v, x)
+	}
+}
+
+func walkStmtList(v Visitor, list []Stmt) {
+	for _, x := range list {
+		Walk(v, x)
+	}
+}
+
+func walkDeclList(v Visitor, list []Decl) {
+	for _, x := range list {
+		Walk(v, x)
+	}
+}
+
+// TODO(gri): Investigate if providing a closure to Walk leads to
+//            simpler use (and may help eliminate Inspect in turn).
+
+// Walk traverses an AST in depth-first order: It starts by calling
+// v.Visit(node); node must not be nil. If the visitor w returned by
+// v.Visit(node) is not nil, Walk is invoked recursively with visitor
+// w for each of the non-nil children of node, followed by a call of
+// w.Visit(nil).
+//
+func Walk(v Visitor, node Node) {
+	if v = v.Visit(node); v == nil {
+		return
+	}
+
+	// walk children
+	// (the order of the cases matches the order
+	// of the corresponding node types in ast.go)
+	switch n := node.(type) {
+	// Comments and fields
+	case *Comment:
+		// nothing to do
+
+	case *CommentGroup:
+		for _, c := range n.List {
+			Walk(v, c)
+		}
+
+	case *Field:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		walkIdentList(v, n.Names)
+		Walk(v, n.Type)
+		if n.Tag != nil {
+			Walk(v, n.Tag)
+		}
+		if n.Comment != nil {
+			Walk(v, n.Comment)
+		}
+
+	case *FieldList:
+		for _, f := range n.List {
+			Walk(v, f)
+		}
+
+	// Expressions
+	case *BadExpr, *Ident, *BasicLit:
+		// nothing to do
+
+	case *Ellipsis:
+		if n.Elt != nil {
+			Walk(v, n.Elt)
+		}
+
+	case *FuncLit:
+		Walk(v, n.Type)
+		Walk(v, n.Body)
+
+	case *CompositeLit:
+		if n.Type != nil {
+			Walk(v, n.Type)
+		}
+		walkExprList(v, n.Elts)
+
+	case *ParenExpr:
+		Walk(v, n.X)
+
+	case *SelectorExpr:
+		Walk(v, n.X)
+		Walk(v, n.Sel)
+
+	case *IndexExpr:
+		Walk(v, n.X)
+		Walk(v, n.Index)
+
+	case *SliceExpr:
+		Walk(v, n.X)
+		if n.Low != nil {
+			Walk(v, n.Low)
+		}
+		if n.High != nil {
+			Walk(v, n.High)
+		}
+		if n.Max != nil {
+			Walk(v, n.Max)
+		}
+
+	case *TypeAssertExpr:
+		Walk(v, n.X)
+		if n.Type != nil {
+			Walk(v, n.Type)
+		}
+
+	case *CallExpr:
+		Walk(v, n.Fun)
+		walkExprList(v, n.Args)
+
+	case *StarExpr:
+		Walk(v, n.X)
+
+	case *UnaryExpr:
+		Walk(v, n.X)
+
+	case *BinaryExpr:
+		Walk(v, n.X)
+		Walk(v, n.Y)
+
+	case *KeyValueExpr:
+		Walk(v, n.Key)
+		Walk(v, n.Value)
+
+	// Types
+	case *ArrayType:
+		if n.Len != nil {
+			Walk(v, n.Len)
+		}
+		Walk(v, n.Elt)
+
+	case *StructType:
+		Walk(v, n.Fields)
+
+	case *FuncType:
+		if n.Params != nil {
+			Walk(v, n.Params)
+		}
+		if n.Results != nil {
+			Walk(v, n.Results)
+		}
+
+	case *InterfaceType:
+		Walk(v, n.Methods)
+
+	case *MapType:
+		Walk(v, n.Key)
+		Walk(v, n.Value)
+
+	case *ChanType:
+		Walk(v, n.Value)
+
+	// Statements
+	case *BadStmt:
+		// nothing to do
+
+	case *DeclStmt:
+		Walk(v, n.Decl)
+
+	case *EmptyStmt:
+		// nothing to do
+
+	case *LabeledStmt:
+		Walk(v, n.Label)
+		Walk(v, n.Stmt)
+
+	case *ExprStmt:
+		Walk(v, n.X)
+
+	case *SendStmt:
+		Walk(v, n.Chan)
+		Walk(v, n.Value)
+
+	case *IncDecStmt:
+		Walk(v, n.X)
+
+	case *AssignStmt:
+		walkExprList(v, n.Lhs)
+		walkExprList(v, n.Rhs)
+
+	case *GoStmt:
+		Walk(v, n.Call)
+
+	case *DeferStmt:
+		Walk(v, n.Call)
+
+	case *ReturnStmt:
+		walkExprList(v, n.Results)
+
+	case *BranchStmt:
+		if n.Label != nil {
+			Walk(v, n.Label)
+		}
+
+	case *BlockStmt:
+		walkStmtList(v, n.List)
+
+	case *IfStmt:
+		if n.Init != nil {
+			Walk(v, n.Init)
+		}
+		Walk(v, n.Cond)
+		Walk(v, n.Body)
+		if n.Else != nil {
+			Walk(v, n.Else)
+		}
+
+	case *CaseClause:
+		walkExprList(v, n.List)
+		walkStmtList(v, n.Body)
+
+	case *SwitchStmt:
+		if n.Init != nil {
+			Walk(v, n.Init)
+		}
+		if n.Tag != nil {
+			Walk(v, n.Tag)
+		}
+		Walk(v, n.Body)
+
+	case *TypeSwitchStmt:
+		if n.Init != nil {
+			Walk(v, n.Init)
+		}
+		Walk(v, n.Assign)
+		Walk(v, n.Body)
+
+	case *CommClause:
+		if n.Comm != nil {
+			Walk(v, n.Comm)
+		}
+		walkStmtList(v, n.Body)
+
+	case *SelectStmt:
+		Walk(v, n.Body)
+
+	case *ForStmt:
+		if n.Init != nil {
+			Walk(v, n.Init)
+		}
+		if n.Cond != nil {
+			Walk(v, n.Cond)
+		}
+		if n.Post != nil {
+			Walk(v, n.Post)
+		}
+		Walk(v, n.Body)
+
+	case *RangeStmt:
+		if n.Key != nil {
+			Walk(v, n.Key)
+		}
+		if n.Value != nil {
+			Walk(v, n.Value)
+		}
+		Walk(v, n.X)
+		Walk(v, n.Body)
+
+	// Declarations
+	case *ImportSpec:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		if n.Name != nil {
+			Walk(v, n.Name)
+		}
+		Walk(v, n.Path)
+		if n.Comment != nil {
+			Walk(v, n.Comment)
+		}
+
+	case *ValueSpec:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		walkIdentList(v, n.Names)
+		if n.Type != nil {
+			Walk(v, n.Type)
+		}
+		walkExprList(v, n.Values)
+		if n.Comment != nil {
+			Walk(v, n.Comment)
+		}
+
+	case *TypeSpec:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		Walk(v, n.Name)
+		Walk(v, n.Type)
+		if n.Comment != nil {
+			Walk(v, n.Comment)
+		}
+
+	case *BadDecl:
+		// nothing to do
+
+	case *GenDecl:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		for _, s := range n.Specs {
+			Walk(v, s)
+		}
+
+	case *FuncDecl:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		if n.Recv != nil {
+			Walk(v, n.Recv)
+		}
+		Walk(v, n.Name)
+		Walk(v, n.Type)
+		if n.Body != nil {
+			Walk(v, n.Body)
+		}
+
+	// Files and packages
+	case *File:
+		if n.Doc != nil {
+			Walk(v, n.Doc)
+		}
+		Walk(v, n.Name)
+		walkDeclList(v, n.Decls)
+		// don't walk n.Comments - they have been
+		// visited already through the individual
+		// nodes
+
+	case *Package:
+		for _, f := range n.Files {
+			Walk(v, f)
+		}
+
+	default:
+		fmt.Printf("ast.Walk: unexpected node type %T", n)
+		panic("ast.Walk")
+	}
+
+	v.Visit(nil)
+}
+
+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
+// for all the non-nil children of node, recursively.
+//
+func Inspect(node Node, f func(Node) bool) {
+	Walk(inspector(f), node)
+}