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