walk.go

     1  // Copyright 2012 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  // This file implements syntax tree walking.
     6  
     7  package syntax
     8  
     9  import "fmt"
    10  
    11  // Inspect traverses an AST in pre-order: It starts by calling
    12  // f(node); node must not be nil. If f returns true, Inspect invokes f
    13  // recursively for each of the non-nil children of node, followed by a
    14  // call of f(nil).
    15  //
    16  // See Walk for caveats about shared nodes.
    17  func Inspect(root Node, f func(Node) bool) {
    18  	Walk(root, inspector(f))
    19  }
    20  
    21  type inspector func(Node) bool
    22  
    23  func (v inspector) Visit(node Node) Visitor {
    24  	if v(node) {
    25  		return v
    26  	}
    27  	return nil
    28  }
    29  
    30  // Crawl traverses a syntax in pre-order: It starts by calling f(root);
    31  // root must not be nil. If f returns false (== "continue"), Crawl calls
    32  // f recursively for each of the non-nil children of that node; if f
    33  // returns true (== "stop"), Crawl does not traverse the respective node's
    34  // children.
    35  //
    36  // See Walk for caveats about shared nodes.
    37  //
    38  // Deprecated: Use Inspect instead.
    39  func Crawl(root Node, f func(Node) bool) {
    40  	Inspect(root, func(node Node) bool {
    41  		return node != nil && !f(node)
    42  	})
    43  }
    44  
    45  // Walk traverses an AST in pre-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  // Some nodes may be shared among multiple parent nodes (e.g., types in
    52  // field lists such as type T in "a, b, c T"). Such shared nodes are
    53  // walked multiple times.
    54  // TODO(gri) Revisit this design. It may make sense to walk those nodes
    55  //           only once. A place where this matters is types2.TestResolveIdents.
    56  func Walk(root Node, v Visitor) {
    57  	walker{v}.node(root)
    58  }
    59  
    60  // A Visitor's Visit method is invoked for each node encountered by Walk.
    61  // If the result visitor w is not nil, Walk visits each of the children
    62  // of node with the visitor w, followed by a call of w.Visit(nil).
    63  type Visitor interface {
    64  	Visit(node Node) (w Visitor)
    65  }
    66  
    67  type walker struct {
    68  	v Visitor
    69  }
    70  
    71  func (w walker) node(n Node) {
    72  	if n == nil {
    73  		panic("nil node")
    74  	}
    75  
    76  	w.v = w.v.Visit(n)
    77  	if w.v == nil {
    78  		return
    79  	}
    80  
    81  	switch n := n.(type) {
    82  	// packages
    83  	case *File:
    84  		w.node(n.PkgName)
    85  		w.declList(n.DeclList)
    86  
    87  	// declarations
    88  	case *ImportDecl:
    89  		if n.LocalPkgName != nil {
    90  			w.node(n.LocalPkgName)
    91  		}
    92  		w.node(n.Path)
    93  
    94  	case *ConstDecl:
    95  		w.nameList(n.NameList)
    96  		if n.Type != nil {
    97  			w.node(n.Type)
    98  		}
    99  		if n.Values != nil {
   100  			w.node(n.Values)
   101  		}
   102  
   103  	case *TypeDecl:
   104  		w.node(n.Name)
   105  		w.fieldList(n.TParamList)
   106  		w.node(n.Type)
   107  
   108  	case *VarDecl:
   109  		w.nameList(n.NameList)
   110  		if n.Type != nil {
   111  			w.node(n.Type)
   112  		}
   113  		if n.Values != nil {
   114  			w.node(n.Values)
   115  		}
   116  
   117  	case *FuncDecl:
   118  		if n.Recv != nil {
   119  			w.node(n.Recv)
   120  		}
   121  		w.node(n.Name)
   122  		w.fieldList(n.TParamList)
   123  		w.node(n.Type)
   124  		if n.Body != nil {
   125  			w.node(n.Body)
   126  		}
   127  
   128  	// expressions
   129  	case *BadExpr: // nothing to do
   130  	case *Name: // nothing to do
   131  	case *BasicLit: // nothing to do
   132  
   133  	case *CompositeLit:
   134  		if n.Type != nil {
   135  			w.node(n.Type)
   136  		}
   137  		w.exprList(n.ElemList)
   138  
   139  	case *KeyValueExpr:
   140  		w.node(n.Key)
   141  		w.node(n.Value)
   142  
   143  	case *FuncLit:
   144  		w.node(n.Type)
   145  		w.node(n.Body)
   146  
   147  	case *ParenExpr:
   148  		w.node(n.X)
   149  
   150  	case *SelectorExpr:
   151  		w.node(n.X)
   152  		w.node(n.Sel)
   153  
   154  	case *IndexExpr:
   155  		w.node(n.X)
   156  		w.node(n.Index)
   157  
   158  	case *SliceExpr:
   159  		w.node(n.X)
   160  		for _, x := range n.Index {
   161  			if x != nil {
   162  				w.node(x)
   163  			}
   164  		}
   165  
   166  	case *AssertExpr:
   167  		w.node(n.X)
   168  		w.node(n.Type)
   169  
   170  	case *TypeSwitchGuard:
   171  		if n.Lhs != nil {
   172  			w.node(n.Lhs)
   173  		}
   174  		w.node(n.X)
   175  
   176  	case *Operation:
   177  		w.node(n.X)
   178  		if n.Y != nil {
   179  			w.node(n.Y)
   180  		}
   181  
   182  	case *CallExpr:
   183  		w.node(n.Fun)
   184  		w.exprList(n.ArgList)
   185  
   186  	case *ListExpr:
   187  		w.exprList(n.ElemList)
   188  
   189  	// types
   190  	case *ArrayType:
   191  		if n.Len != nil {
   192  			w.node(n.Len)
   193  		}
   194  		w.node(n.Elem)
   195  
   196  	case *SliceType:
   197  		w.node(n.Elem)
   198  
   199  	case *DotsType:
   200  		w.node(n.Elem)
   201  
   202  	case *StructType:
   203  		w.fieldList(n.FieldList)
   204  		for _, t := range n.TagList {
   205  			if t != nil {
   206  				w.node(t)
   207  			}
   208  		}
   209  
   210  	case *Field:
   211  		if n.Name != nil {
   212  			w.node(n.Name)
   213  		}
   214  		w.node(n.Type)
   215  
   216  	case *InterfaceType:
   217  		w.fieldList(n.MethodList)
   218  
   219  	case *FuncType:
   220  		w.fieldList(n.ParamList)
   221  		w.fieldList(n.ResultList)
   222  
   223  	case *MapType:
   224  		w.node(n.Key)
   225  		w.node(n.Value)
   226  
   227  	case *ChanType:
   228  		w.node(n.Elem)
   229  
   230  	// statements
   231  	case *EmptyStmt: // nothing to do
   232  
   233  	case *LabeledStmt:
   234  		w.node(n.Label)
   235  		w.node(n.Stmt)
   236  
   237  	case *BlockStmt:
   238  		w.stmtList(n.List)
   239  
   240  	case *ExprStmt:
   241  		w.node(n.X)
   242  
   243  	case *SendStmt:
   244  		w.node(n.Chan)
   245  		w.node(n.Value)
   246  
   247  	case *DeclStmt:
   248  		w.declList(n.DeclList)
   249  
   250  	case *AssignStmt:
   251  		w.node(n.Lhs)
   252  		if n.Rhs != nil {
   253  			w.node(n.Rhs)
   254  		}
   255  
   256  	case *BranchStmt:
   257  		if n.Label != nil {
   258  			w.node(n.Label)
   259  		}
   260  		// Target points to nodes elsewhere in the syntax tree
   261  
   262  	case *CallStmt:
   263  		w.node(n.Call)
   264  
   265  	case *ReturnStmt:
   266  		if n.Results != nil {
   267  			w.node(n.Results)
   268  		}
   269  
   270  	case *IfStmt:
   271  		if n.Init != nil {
   272  			w.node(n.Init)
   273  		}
   274  		w.node(n.Cond)
   275  		w.node(n.Then)
   276  		if n.Else != nil {
   277  			w.node(n.Else)
   278  		}
   279  
   280  	case *ForStmt:
   281  		if n.Init != nil {
   282  			w.node(n.Init)
   283  		}
   284  		if n.Cond != nil {
   285  			w.node(n.Cond)
   286  		}
   287  		if n.Post != nil {
   288  			w.node(n.Post)
   289  		}
   290  		w.node(n.Body)
   291  
   292  	case *SwitchStmt:
   293  		if n.Init != nil {
   294  			w.node(n.Init)
   295  		}
   296  		if n.Tag != nil {
   297  			w.node(n.Tag)
   298  		}
   299  		for _, s := range n.Body {
   300  			w.node(s)
   301  		}
   302  
   303  	case *SelectStmt:
   304  		for _, s := range n.Body {
   305  			w.node(s)
   306  		}
   307  
   308  	// helper nodes
   309  	case *RangeClause:
   310  		if n.Lhs != nil {
   311  			w.node(n.Lhs)
   312  		}
   313  		w.node(n.X)
   314  
   315  	case *CaseClause:
   316  		if n.Cases != nil {
   317  			w.node(n.Cases)
   318  		}
   319  		w.stmtList(n.Body)
   320  
   321  	case *CommClause:
   322  		if n.Comm != nil {
   323  			w.node(n.Comm)
   324  		}
   325  		w.stmtList(n.Body)
   326  
   327  	default:
   328  		panic(fmt.Sprintf("internal error: unknown node type %T", n))
   329  	}
   330  
   331  	w.v.Visit(nil)
   332  }
   333  
   334  func (w walker) declList(list []Decl) {
   335  	for _, n := range list {
   336  		w.node(n)
   337  	}
   338  }
   339  
   340  func (w walker) exprList(list []Expr) {
   341  	for _, n := range list {
   342  		w.node(n)
   343  	}
   344  }
   345  
   346  func (w walker) stmtList(list []Stmt) {
   347  	for _, n := range list {
   348  		w.node(n)
   349  	}
   350  }
   351  
   352  func (w walker) nameList(list []*Name) {
   353  	for _, n := range list {
   354  		w.node(n)
   355  	}
   356  }
   357  
   358  func (w walker) fieldList(list []*Field) {
   359  	for _, n := range list {
   360  		w.node(n)
   361  	}
   362  }
   363
View as plain text