walk.go

Documentation: cmd/compile/internal/syntax

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