| // Copyright 2012 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| // This file implements syntax tree walking. |
| |
| package syntax |
| |
| import "fmt" |
| |
| // Walk traverses a syntax in pre-order: It starts by calling f(root); |
| // root must not be nil. If f returns false (== "continue"), Walk calls |
| // f recursively for each of the non-nil children of that node; if f |
| // returns true (== "stop"), Walk does not traverse the respective node's |
| // children. |
| // Some nodes may be shared among multiple parent nodes (e.g., types in |
| // field lists such as type T in "a, b, c T"). Such shared nodes are |
| // walked multiple times. |
| // TODO(gri) Revisit this design. It may make sense to walk those nodes |
| // only once. A place where this matters is types2.TestResolveIdents. |
| func Walk(root Node, f func(Node) bool) { |
| w := walker{f} |
| w.node(root) |
| } |
| |
| type walker struct { |
| f func(Node) bool |
| } |
| |
| func (w *walker) node(n Node) { |
| if n == nil { |
| panic("invalid syntax tree: nil node") |
| } |
| |
| if w.f(n) { |
| return |
| } |
| |
| switch n := n.(type) { |
| // packages |
| case *File: |
| w.node(n.PkgName) |
| w.declList(n.DeclList) |
| |
| // declarations |
| case *ImportDecl: |
| if n.LocalPkgName != nil { |
| w.node(n.LocalPkgName) |
| } |
| w.node(n.Path) |
| |
| case *ConstDecl: |
| w.nameList(n.NameList) |
| if n.Type != nil { |
| w.node(n.Type) |
| } |
| if n.Values != nil { |
| w.node(n.Values) |
| } |
| |
| case *TypeDecl: |
| w.node(n.Name) |
| w.fieldList(n.TParamList) |
| w.node(n.Type) |
| |
| case *VarDecl: |
| w.nameList(n.NameList) |
| if n.Type != nil { |
| w.node(n.Type) |
| } |
| if n.Values != nil { |
| w.node(n.Values) |
| } |
| |
| case *FuncDecl: |
| if n.Recv != nil { |
| w.node(n.Recv) |
| } |
| w.node(n.Name) |
| w.fieldList(n.TParamList) |
| w.node(n.Type) |
| if n.Body != nil { |
| w.node(n.Body) |
| } |
| |
| // expressions |
| case *BadExpr: // nothing to do |
| case *Name: // nothing to do |
| case *BasicLit: // nothing to do |
| |
| case *CompositeLit: |
| if n.Type != nil { |
| w.node(n.Type) |
| } |
| w.exprList(n.ElemList) |
| |
| case *KeyValueExpr: |
| w.node(n.Key) |
| w.node(n.Value) |
| |
| case *FuncLit: |
| w.node(n.Type) |
| w.node(n.Body) |
| |
| case *ParenExpr: |
| w.node(n.X) |
| |
| case *SelectorExpr: |
| w.node(n.X) |
| w.node(n.Sel) |
| |
| case *IndexExpr: |
| w.node(n.X) |
| w.node(n.Index) |
| |
| case *SliceExpr: |
| w.node(n.X) |
| for _, x := range n.Index { |
| if x != nil { |
| w.node(x) |
| } |
| } |
| |
| case *AssertExpr: |
| w.node(n.X) |
| w.node(n.Type) |
| |
| case *TypeSwitchGuard: |
| if n.Lhs != nil { |
| w.node(n.Lhs) |
| } |
| w.node(n.X) |
| |
| case *Operation: |
| w.node(n.X) |
| if n.Y != nil { |
| w.node(n.Y) |
| } |
| |
| case *CallExpr: |
| w.node(n.Fun) |
| w.exprList(n.ArgList) |
| |
| case *ListExpr: |
| w.exprList(n.ElemList) |
| |
| // types |
| case *ArrayType: |
| if n.Len != nil { |
| w.node(n.Len) |
| } |
| w.node(n.Elem) |
| |
| case *SliceType: |
| w.node(n.Elem) |
| |
| case *DotsType: |
| w.node(n.Elem) |
| |
| case *StructType: |
| w.fieldList(n.FieldList) |
| for _, t := range n.TagList { |
| if t != nil { |
| w.node(t) |
| } |
| } |
| |
| case *Field: |
| if n.Name != nil { |
| w.node(n.Name) |
| } |
| w.node(n.Type) |
| |
| case *InterfaceType: |
| w.fieldList(n.MethodList) |
| |
| case *FuncType: |
| w.fieldList(n.ParamList) |
| w.fieldList(n.ResultList) |
| |
| case *MapType: |
| w.node(n.Key) |
| w.node(n.Value) |
| |
| case *ChanType: |
| w.node(n.Elem) |
| |
| // statements |
| case *EmptyStmt: // nothing to do |
| |
| case *LabeledStmt: |
| w.node(n.Label) |
| w.node(n.Stmt) |
| |
| case *BlockStmt: |
| w.stmtList(n.List) |
| |
| case *ExprStmt: |
| w.node(n.X) |
| |
| case *SendStmt: |
| w.node(n.Chan) |
| w.node(n.Value) |
| |
| case *DeclStmt: |
| w.declList(n.DeclList) |
| |
| case *AssignStmt: |
| w.node(n.Lhs) |
| if n.Rhs != nil { |
| w.node(n.Rhs) |
| } |
| |
| case *BranchStmt: |
| if n.Label != nil { |
| w.node(n.Label) |
| } |
| // Target points to nodes elsewhere in the syntax tree |
| |
| case *CallStmt: |
| w.node(n.Call) |
| |
| case *ReturnStmt: |
| if n.Results != nil { |
| w.node(n.Results) |
| } |
| |
| case *IfStmt: |
| if n.Init != nil { |
| w.node(n.Init) |
| } |
| w.node(n.Cond) |
| w.node(n.Then) |
| if n.Else != nil { |
| w.node(n.Else) |
| } |
| |
| case *ForStmt: |
| if n.Init != nil { |
| w.node(n.Init) |
| } |
| if n.Cond != nil { |
| w.node(n.Cond) |
| } |
| if n.Post != nil { |
| w.node(n.Post) |
| } |
| w.node(n.Body) |
| |
| case *SwitchStmt: |
| if n.Init != nil { |
| w.node(n.Init) |
| } |
| if n.Tag != nil { |
| w.node(n.Tag) |
| } |
| for _, s := range n.Body { |
| w.node(s) |
| } |
| |
| case *SelectStmt: |
| for _, s := range n.Body { |
| w.node(s) |
| } |
| |
| // helper nodes |
| case *RangeClause: |
| if n.Lhs != nil { |
| w.node(n.Lhs) |
| } |
| w.node(n.X) |
| |
| case *CaseClause: |
| if n.Cases != nil { |
| w.node(n.Cases) |
| } |
| w.stmtList(n.Body) |
| |
| case *CommClause: |
| if n.Comm != nil { |
| w.node(n.Comm) |
| } |
| w.stmtList(n.Body) |
| |
| default: |
| panic(fmt.Sprintf("internal error: unknown node type %T", n)) |
| } |
| } |
| |
| func (w *walker) declList(list []Decl) { |
| for _, n := range list { |
| w.node(n) |
| } |
| } |
| |
| func (w *walker) exprList(list []Expr) { |
| for _, n := range list { |
| w.node(n) |
| } |
| } |
| |
| func (w *walker) stmtList(list []Stmt) { |
| for _, n := range list { |
| w.node(n) |
| } |
| } |
| |
| func (w *walker) nameList(list []*Name) { |
| for _, n := range list { |
| w.node(n) |
| } |
| } |
| |
| func (w *walker) fieldList(list []*Field) { |
| for _, n := range list { |
| w.node(n) |
| } |
| } |
