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

View as plain text