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  		if n.Type != nil {
    75  			Walk(v, n.Type)
    76  		}
    77  		if n.Tag != nil {
    78  			Walk(v, n.Tag)
    79  		}
    80  		if n.Comment != nil {
    81  			Walk(v, n.Comment)
    82  		}
    83  
    84  	case *FieldList:
    85  		for _, f := range n.List {
    86  			Walk(v, f)
    87  		}
    88  
    89  	// Expressions
    90  	case *BadExpr, *Ident, *BasicLit:
    91  		// nothing to do
    92  
    93  	case *Ellipsis:
    94  		if n.Elt != nil {
    95  			Walk(v, n.Elt)
    96  		}
    97  
    98  	case *FuncLit:
    99  		Walk(v, n.Type)
   100  		Walk(v, n.Body)
   101  
   102  	case *CompositeLit:
   103  		if n.Type != nil {
   104  			Walk(v, n.Type)
   105  		}
   106  		walkExprList(v, n.Elts)
   107  
   108  	case *ParenExpr:
   109  		Walk(v, n.X)
   110  
   111  	case *SelectorExpr:
   112  		Walk(v, n.X)
   113  		Walk(v, n.Sel)
   114  
   115  	case *IndexExpr:
   116  		Walk(v, n.X)
   117  		Walk(v, n.Index)
   118  
   119  	case *IndexListExpr:
   120  		Walk(v, n.X)
   121  		for _, index := range n.Indices {
   122  			Walk(v, index)
   123  		}
   124  
   125  	case *SliceExpr:
   126  		Walk(v, n.X)
   127  		if n.Low != nil {
   128  			Walk(v, n.Low)
   129  		}
   130  		if n.High != nil {
   131  			Walk(v, n.High)
   132  		}
   133  		if n.Max != nil {
   134  			Walk(v, n.Max)
   135  		}
   136  
   137  	case *TypeAssertExpr:
   138  		Walk(v, n.X)
   139  		if n.Type != nil {
   140  			Walk(v, n.Type)
   141  		}
   142  
   143  	case *CallExpr:
   144  		Walk(v, n.Fun)
   145  		walkExprList(v, n.Args)
   146  
   147  	case *StarExpr:
   148  		Walk(v, n.X)
   149  
   150  	case *UnaryExpr:
   151  		Walk(v, n.X)
   152  
   153  	case *BinaryExpr:
   154  		Walk(v, n.X)
   155  		Walk(v, n.Y)
   156  
   157  	case *KeyValueExpr:
   158  		Walk(v, n.Key)
   159  		Walk(v, n.Value)
   160  
   161  	// Types
   162  	case *ArrayType:
   163  		if n.Len != nil {
   164  			Walk(v, n.Len)
   165  		}
   166  		Walk(v, n.Elt)
   167  
   168  	case *StructType:
   169  		Walk(v, n.Fields)
   170  
   171  	case *FuncType:
   172  		if n.TypeParams != nil {
   173  			Walk(v, n.TypeParams)
   174  		}
   175  		if n.Params != nil {
   176  			Walk(v, n.Params)
   177  		}
   178  		if n.Results != nil {
   179  			Walk(v, n.Results)
   180  		}
   181  
   182  	case *InterfaceType:
   183  		Walk(v, n.Methods)
   184  
   185  	case *MapType:
   186  		Walk(v, n.Key)
   187  		Walk(v, n.Value)
   188  
   189  	case *ChanType:
   190  		Walk(v, n.Value)
   191  
   192  	// Statements
   193  	case *BadStmt:
   194  		// nothing to do
   195  
   196  	case *DeclStmt:
   197  		Walk(v, n.Decl)
   198  
   199  	case *EmptyStmt:
   200  		// nothing to do
   201  
   202  	case *LabeledStmt:
   203  		Walk(v, n.Label)
   204  		Walk(v, n.Stmt)
   205  
   206  	case *ExprStmt:
   207  		Walk(v, n.X)
   208  
   209  	case *SendStmt:
   210  		Walk(v, n.Chan)
   211  		Walk(v, n.Value)
   212  
   213  	case *IncDecStmt:
   214  		Walk(v, n.X)
   215  
   216  	case *AssignStmt:
   217  		walkExprList(v, n.Lhs)
   218  		walkExprList(v, n.Rhs)
   219  
   220  	case *GoStmt:
   221  		Walk(v, n.Call)
   222  
   223  	case *DeferStmt:
   224  		Walk(v, n.Call)
   225  
   226  	case *ReturnStmt:
   227  		walkExprList(v, n.Results)
   228  
   229  	case *BranchStmt:
   230  		if n.Label != nil {
   231  			Walk(v, n.Label)
   232  		}
   233  
   234  	case *BlockStmt:
   235  		walkStmtList(v, n.List)
   236  
   237  	case *IfStmt:
   238  		if n.Init != nil {
   239  			Walk(v, n.Init)
   240  		}
   241  		Walk(v, n.Cond)
   242  		Walk(v, n.Body)
   243  		if n.Else != nil {
   244  			Walk(v, n.Else)
   245  		}
   246  
   247  	case *CaseClause:
   248  		walkExprList(v, n.List)
   249  		walkStmtList(v, n.Body)
   250  
   251  	case *SwitchStmt:
   252  		if n.Init != nil {
   253  			Walk(v, n.Init)
   254  		}
   255  		if n.Tag != nil {
   256  			Walk(v, n.Tag)
   257  		}
   258  		Walk(v, n.Body)
   259  
   260  	case *TypeSwitchStmt:
   261  		if n.Init != nil {
   262  			Walk(v, n.Init)
   263  		}
   264  		Walk(v, n.Assign)
   265  		Walk(v, n.Body)
   266  
   267  	case *CommClause:
   268  		if n.Comm != nil {
   269  			Walk(v, n.Comm)
   270  		}
   271  		walkStmtList(v, n.Body)
   272  
   273  	case *SelectStmt:
   274  		Walk(v, n.Body)
   275  
   276  	case *ForStmt:
   277  		if n.Init != nil {
   278  			Walk(v, n.Init)
   279  		}
   280  		if n.Cond != nil {
   281  			Walk(v, n.Cond)
   282  		}
   283  		if n.Post != nil {
   284  			Walk(v, n.Post)
   285  		}
   286  		Walk(v, n.Body)
   287  
   288  	case *RangeStmt:
   289  		if n.Key != nil {
   290  			Walk(v, n.Key)
   291  		}
   292  		if n.Value != nil {
   293  			Walk(v, n.Value)
   294  		}
   295  		Walk(v, n.X)
   296  		Walk(v, n.Body)
   297  
   298  	// Declarations
   299  	case *ImportSpec:
   300  		if n.Doc != nil {
   301  			Walk(v, n.Doc)
   302  		}
   303  		if n.Name != nil {
   304  			Walk(v, n.Name)
   305  		}
   306  		Walk(v, n.Path)
   307  		if n.Comment != nil {
   308  			Walk(v, n.Comment)
   309  		}
   310  
   311  	case *ValueSpec:
   312  		if n.Doc != nil {
   313  			Walk(v, n.Doc)
   314  		}
   315  		walkIdentList(v, n.Names)
   316  		if n.Type != nil {
   317  			Walk(v, n.Type)
   318  		}
   319  		walkExprList(v, n.Values)
   320  		if n.Comment != nil {
   321  			Walk(v, n.Comment)
   322  		}
   323  
   324  	case *TypeSpec:
   325  		if n.Doc != nil {
   326  			Walk(v, n.Doc)
   327  		}
   328  		Walk(v, n.Name)
   329  		if n.TypeParams != nil {
   330  			Walk(v, n.TypeParams)
   331  		}
   332  		Walk(v, n.Type)
   333  		if n.Comment != nil {
   334  			Walk(v, n.Comment)
   335  		}
   336  
   337  	case *BadDecl:
   338  		// nothing to do
   339  
   340  	case *GenDecl:
   341  		if n.Doc != nil {
   342  			Walk(v, n.Doc)
   343  		}
   344  		for _, s := range n.Specs {
   345  			Walk(v, s)
   346  		}
   347  
   348  	case *FuncDecl:
   349  		if n.Doc != nil {
   350  			Walk(v, n.Doc)
   351  		}
   352  		if n.Recv != nil {
   353  			Walk(v, n.Recv)
   354  		}
   355  		Walk(v, n.Name)
   356  		Walk(v, n.Type)
   357  		if n.Body != nil {
   358  			Walk(v, n.Body)
   359  		}
   360  
   361  	// Files and packages
   362  	case *File:
   363  		if n.Doc != nil {
   364  			Walk(v, n.Doc)
   365  		}
   366  		Walk(v, n.Name)
   367  		walkDeclList(v, n.Decls)
   368  		// don't walk n.Comments - they have been
   369  		// visited already through the individual
   370  		// nodes
   371  
   372  	case *Package:
   373  		for _, f := range n.Files {
   374  			Walk(v, f)
   375  		}
   376  
   377  	default:
   378  		panic(fmt.Sprintf("ast.Walk: unexpected node type %T", n))
   379  	}
   380  
   381  	v.Visit(nil)
   382  }
   383  
   384  type inspector func(Node) bool
   385  
   386  func (f inspector) Visit(node Node) Visitor {
   387  	if f(node) {
   388  		return f
   389  	}
   390  	return nil
   391  }
   392  
   393  // Inspect traverses an AST in depth-first order: It starts by calling
   394  // f(node); node must not be nil. If f returns true, Inspect invokes f
   395  // recursively for each of the non-nil children of node, followed by a
   396  // call of f(nil).
   397  //
   398  func Inspect(node Node, f func(Node) bool) {
   399  	Walk(inspector(f), node)
   400  }
   401
View as plain text