Source file src/pkg/go/ast/walk.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package ast
     6	
     7	import "fmt"
     8	
     9	// A Visitor's Visit method is invoked for each node encountered by Walk.
    10	// If the result visitor w is not nil, Walk visits each of the children
    11	// of node with the visitor w, followed by a call of w.Visit(nil).
    12	type Visitor interface {
    13		Visit(node Node) (w Visitor)
    14	}
    15	
    16	// Helper functions for common node lists. They may be empty.
    17	
    18	func walkIdentList(v Visitor, list []*Ident) {
    19		for _, x := range list {
    20			Walk(v, x)
    21		}
    22	}
    23	
    24	func walkExprList(v Visitor, list []Expr) {
    25		for _, x := range list {
    26			Walk(v, x)
    27		}
    28	}
    29	
    30	func walkStmtList(v Visitor, list []Stmt) {
    31		for _, x := range list {
    32			Walk(v, x)
    33		}
    34	}
    35	
    36	func walkDeclList(v Visitor, list []Decl) {
    37		for _, x := range list {
    38			Walk(v, x)
    39		}
    40	}
    41	
    42	// TODO(gri): Investigate if providing a closure to Walk leads to
    43	//            simpler use (and may help eliminate Inspect in turn).
    44	
    45	// Walk traverses an AST in depth-first order: It starts by calling
    46	// v.Visit(node); node must not be nil. If the visitor w returned by
    47	// v.Visit(node) is not nil, Walk is invoked recursively with visitor
    48	// w for each of the non-nil children of node, followed by a call of
    49	// w.Visit(nil).
    50	//
    51	func Walk(v Visitor, node Node) {
    52		if v = v.Visit(node); v == nil {
    53			return
    54		}
    55	
    56		// walk children
    57		// (the order of the cases matches the order
    58		// of the corresponding node types in ast.go)
    59		switch n := node.(type) {
    60		// Comments and fields
    61		case *Comment:
    62			// nothing to do
    63	
    64		case *CommentGroup:
    65			for _, c := range n.List {
    66				Walk(v, c)
    67			}
    68	
    69		case *Field:
    70			if n.Doc != nil {
    71				Walk(v, n.Doc)
    72			}
    73			walkIdentList(v, n.Names)
    74			Walk(v, n.Type)
    75			if n.Tag != nil {
    76				Walk(v, n.Tag)
    77			}
    78			if n.Comment != nil {
    79				Walk(v, n.Comment)
    80			}
    81	
    82		case *FieldList:
    83			for _, f := range n.List {
    84				Walk(v, f)
    85			}
    86	
    87		// Expressions
    88		case *BadExpr, *Ident, *BasicLit:
    89			// nothing to do
    90	
    91		case *Ellipsis:
    92			if n.Elt != nil {
    93				Walk(v, n.Elt)
    94			}
    95	
    96		case *FuncLit:
    97			Walk(v, n.Type)
    98			Walk(v, n.Body)
    99	
   100		case *CompositeLit:
   101			if n.Type != nil {
   102				Walk(v, n.Type)
   103			}
   104			walkExprList(v, n.Elts)
   105	
   106		case *ParenExpr:
   107			Walk(v, n.X)
   108	
   109		case *SelectorExpr:
   110			Walk(v, n.X)
   111			Walk(v, n.Sel)
   112	
   113		case *IndexExpr:
   114			Walk(v, n.X)
   115			Walk(v, n.Index)
   116	
   117		case *SliceExpr:
   118			Walk(v, n.X)
   119			if n.Low != nil {
   120				Walk(v, n.Low)
   121			}
   122			if n.High != nil {
   123				Walk(v, n.High)
   124			}
   125	
   126		case *TypeAssertExpr:
   127			Walk(v, n.X)
   128			if n.Type != nil {
   129				Walk(v, n.Type)
   130			}
   131	
   132		case *CallExpr:
   133			Walk(v, n.Fun)
   134			walkExprList(v, n.Args)
   135	
   136		case *StarExpr:
   137			Walk(v, n.X)
   138	
   139		case *UnaryExpr:
   140			Walk(v, n.X)
   141	
   142		case *BinaryExpr:
   143			Walk(v, n.X)
   144			Walk(v, n.Y)
   145	
   146		case *KeyValueExpr:
   147			Walk(v, n.Key)
   148			Walk(v, n.Value)
   149	
   150		// Types
   151		case *ArrayType:
   152			if n.Len != nil {
   153				Walk(v, n.Len)
   154			}
   155			Walk(v, n.Elt)
   156	
   157		case *StructType:
   158			Walk(v, n.Fields)
   159	
   160		case *FuncType:
   161			Walk(v, n.Params)
   162			if n.Results != nil {
   163				Walk(v, n.Results)
   164			}
   165	
   166		case *InterfaceType:
   167			Walk(v, n.Methods)
   168	
   169		case *MapType:
   170			Walk(v, n.Key)
   171			Walk(v, n.Value)
   172	
   173		case *ChanType:
   174			Walk(v, n.Value)
   175	
   176		// Statements
   177		case *BadStmt:
   178			// nothing to do
   179	
   180		case *DeclStmt:
   181			Walk(v, n.Decl)
   182	
   183		case *EmptyStmt:
   184			// nothing to do
   185	
   186		case *LabeledStmt:
   187			Walk(v, n.Label)
   188			Walk(v, n.Stmt)
   189	
   190		case *ExprStmt:
   191			Walk(v, n.X)
   192	
   193		case *SendStmt:
   194			Walk(v, n.Chan)
   195			Walk(v, n.Value)
   196	
   197		case *IncDecStmt:
   198			Walk(v, n.X)
   199	
   200		case *AssignStmt:
   201			walkExprList(v, n.Lhs)
   202			walkExprList(v, n.Rhs)
   203	
   204		case *GoStmt:
   205			Walk(v, n.Call)
   206	
   207		case *DeferStmt:
   208			Walk(v, n.Call)
   209	
   210		case *ReturnStmt:
   211			walkExprList(v, n.Results)
   212	
   213		case *BranchStmt:
   214			if n.Label != nil {
   215				Walk(v, n.Label)
   216			}
   217	
   218		case *BlockStmt:
   219			walkStmtList(v, n.List)
   220	
   221		case *IfStmt:
   222			if n.Init != nil {
   223				Walk(v, n.Init)
   224			}
   225			Walk(v, n.Cond)
   226			Walk(v, n.Body)
   227			if n.Else != nil {
   228				Walk(v, n.Else)
   229			}
   230	
   231		case *CaseClause:
   232			walkExprList(v, n.List)
   233			walkStmtList(v, n.Body)
   234	
   235		case *SwitchStmt:
   236			if n.Init != nil {
   237				Walk(v, n.Init)
   238			}
   239			if n.Tag != nil {
   240				Walk(v, n.Tag)
   241			}
   242			Walk(v, n.Body)
   243	
   244		case *TypeSwitchStmt:
   245			if n.Init != nil {
   246				Walk(v, n.Init)
   247			}
   248			Walk(v, n.Assign)
   249			Walk(v, n.Body)
   250	
   251		case *CommClause:
   252			if n.Comm != nil {
   253				Walk(v, n.Comm)
   254			}
   255			walkStmtList(v, n.Body)
   256	
   257		case *SelectStmt:
   258			Walk(v, n.Body)
   259	
   260		case *ForStmt:
   261			if n.Init != nil {
   262				Walk(v, n.Init)
   263			}
   264			if n.Cond != nil {
   265				Walk(v, n.Cond)
   266			}
   267			if n.Post != nil {
   268				Walk(v, n.Post)
   269			}
   270			Walk(v, n.Body)
   271	
   272		case *RangeStmt:
   273			Walk(v, n.Key)
   274			if n.Value != nil {
   275				Walk(v, n.Value)
   276			}
   277			Walk(v, n.X)
   278			Walk(v, n.Body)
   279	
   280		// Declarations
   281		case *ImportSpec:
   282			if n.Doc != nil {
   283				Walk(v, n.Doc)
   284			}
   285			if n.Name != nil {
   286				Walk(v, n.Name)
   287			}
   288			Walk(v, n.Path)
   289			if n.Comment != nil {
   290				Walk(v, n.Comment)
   291			}
   292	
   293		case *ValueSpec:
   294			if n.Doc != nil {
   295				Walk(v, n.Doc)
   296			}
   297			walkIdentList(v, n.Names)
   298			if n.Type != nil {
   299				Walk(v, n.Type)
   300			}
   301			walkExprList(v, n.Values)
   302			if n.Comment != nil {
   303				Walk(v, n.Comment)
   304			}
   305	
   306		case *TypeSpec:
   307			if n.Doc != nil {
   308				Walk(v, n.Doc)
   309			}
   310			Walk(v, n.Name)
   311			Walk(v, n.Type)
   312			if n.Comment != nil {
   313				Walk(v, n.Comment)
   314			}
   315	
   316		case *BadDecl:
   317			// nothing to do
   318	
   319		case *GenDecl:
   320			if n.Doc != nil {
   321				Walk(v, n.Doc)
   322			}
   323			for _, s := range n.Specs {
   324				Walk(v, s)
   325			}
   326	
   327		case *FuncDecl:
   328			if n.Doc != nil {
   329				Walk(v, n.Doc)
   330			}
   331			if n.Recv != nil {
   332				Walk(v, n.Recv)
   333			}
   334			Walk(v, n.Name)
   335			Walk(v, n.Type)
   336			if n.Body != nil {
   337				Walk(v, n.Body)
   338			}
   339	
   340		// Files and packages
   341		case *File:
   342			if n.Doc != nil {
   343				Walk(v, n.Doc)
   344			}
   345			Walk(v, n.Name)
   346			walkDeclList(v, n.Decls)
   347			for _, g := range n.Comments {
   348				Walk(v, g)
   349			}
   350			// don't walk n.Comments - they have been
   351			// visited already through the individual
   352			// nodes
   353	
   354		case *Package:
   355			for _, f := range n.Files {
   356				Walk(v, f)
   357			}
   358	
   359		default:
   360			fmt.Printf("ast.Walk: unexpected node type %T", n)
   361			panic("ast.Walk")
   362		}
   363	
   364		v.Visit(nil)
   365	}
   366	
   367	type inspector func(Node) bool
   368	
   369	func (f inspector) Visit(node Node) Visitor {
   370		if f(node) {
   371			return f
   372		}
   373		return nil
   374	}
   375	
   376	// Inspect traverses an AST in depth-first order: It starts by calling
   377	// f(node); node must not be nil. If f returns true, Inspect invokes f
   378	// for all the non-nil children of node, recursively.
   379	//
   380	func Inspect(node Node, f func(Node) bool) {
   381		Walk(inspector(f), node)
   382	}