// Copyright 2009 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.

package ast

import "fmt"

// A Visitor's Visit method is invoked for each node encountered by Walk.
// If the result visitor w is not nil, Walk visits each of the children
// of node with the visitor w, followed by a call of w.Visit(nil).
type Visitor interface {
	Visit(node interface{}) (w Visitor)
}


func walkIdent(v Visitor, x *Ident) {
	if x != nil {
		Walk(v, x)
	}
}


func walkCommentGroup(v Visitor, g *CommentGroup) {
	if g != nil {
		Walk(v, g)
	}
}


func walkBlockStmt(v Visitor, b *BlockStmt) {
	if b != nil {
		Walk(v, b)
	}
}


// Walk traverses an AST in depth-first order: If node != nil, it
// invokes v.Visit(node). If the visitor w returned by v.Visit(node) is
// not nil, Walk visits each of the children of node with the visitor w,
// followed by a call of w.Visit(nil).
//
// Walk may be called with any of the named ast node types. It also
// accepts arguments of type []*Field, []*Ident, []Expr, []Stmt and []Decl;
// the respective children are the slice elements.
//
func Walk(v Visitor, node interface{}) {
	if node == nil {
		return
	}
	if v = v.Visit(node); v == nil {
		return
	}

	// walk children
	// (the order of the cases matches the order
	// of the corresponding declaration in ast.go)
	switch n := node.(type) {
	// Comments and fields
	case *Comment:
		// nothing to do

	case *CommentGroup:
		for _, c := range n.List {
			Walk(v, c)
		}

	case *Field:
		walkCommentGroup(v, n.Doc)
		Walk(v, n.Names)
		Walk(v, n.Type)
		Walk(v, n.Tag)
		walkCommentGroup(v, n.Comment)

	case *FieldList:
		for _, f := range n.List {
			Walk(v, f)
		}

	// Expressions
	case *BadExpr, *Ident, *Ellipsis, *BasicLit:
		// nothing to do

	case *FuncLit:
		if n != nil {
			Walk(v, n.Type)
		}
		walkBlockStmt(v, n.Body)

	case *CompositeLit:
		Walk(v, n.Type)
		Walk(v, n.Elts)

	case *ParenExpr:
		Walk(v, n.X)

	case *SelectorExpr:
		Walk(v, n.X)
		walkIdent(v, n.Sel)

	case *IndexExpr:
		Walk(v, n.X)
		Walk(v, n.Index)

	case *SliceExpr:
		Walk(v, n.X)
		Walk(v, n.Index)
		Walk(v, n.End)

	case *TypeAssertExpr:
		Walk(v, n.X)
		Walk(v, n.Type)

	case *CallExpr:
		Walk(v, n.Fun)
		Walk(v, n.Args)

	case *StarExpr:
		Walk(v, n.X)

	case *UnaryExpr:
		Walk(v, n.X)

	case *BinaryExpr:
		Walk(v, n.X)
		Walk(v, n.Y)

	case *KeyValueExpr:
		Walk(v, n.Key)
		Walk(v, n.Value)

	// Types
	case *ArrayType:
		Walk(v, n.Len)
		Walk(v, n.Elt)

	case *StructType:
		Walk(v, n.Fields)

	case *FuncType:
		Walk(v, n.Params)
		if n.Results != nil {
			Walk(v, n.Results)
		}

	case *InterfaceType:
		Walk(v, n.Methods)

	case *MapType:
		Walk(v, n.Key)
		Walk(v, n.Value)

	case *ChanType:
		Walk(v, n.Value)

	// Statements
	case *BadStmt:
		// nothing to do

	case *DeclStmt:
		Walk(v, n.Decl)

	case *EmptyStmt:
		// nothing to do

	case *LabeledStmt:
		walkIdent(v, n.Label)
		Walk(v, n.Stmt)

	case *ExprStmt:
		Walk(v, n.X)

	case *IncDecStmt:
		Walk(v, n.X)

	case *AssignStmt:
		Walk(v, n.Lhs)
		Walk(v, n.Rhs)

	case *GoStmt:
		if n.Call != nil {
			Walk(v, n.Call)
		}

	case *DeferStmt:
		if n.Call != nil {
			Walk(v, n.Call)
		}

	case *ReturnStmt:
		Walk(v, n.Results)

	case *BranchStmt:
		walkIdent(v, n.Label)

	case *BlockStmt:
		Walk(v, n.List)

	case *IfStmt:
		Walk(v, n.Init)
		Walk(v, n.Cond)
		walkBlockStmt(v, n.Body)
		Walk(v, n.Else)

	case *CaseClause:
		Walk(v, n.Values)
		Walk(v, n.Body)

	case *SwitchStmt:
		Walk(v, n.Init)
		Walk(v, n.Tag)
		walkBlockStmt(v, n.Body)

	case *TypeCaseClause:
		Walk(v, n.Types)
		Walk(v, n.Body)

	case *TypeSwitchStmt:
		Walk(v, n.Init)
		Walk(v, n.Assign)
		walkBlockStmt(v, n.Body)

	case *CommClause:
		Walk(v, n.Lhs)
		Walk(v, n.Rhs)
		Walk(v, n.Body)

	case *SelectStmt:
		walkBlockStmt(v, n.Body)

	case *ForStmt:
		Walk(v, n.Init)
		Walk(v, n.Cond)
		Walk(v, n.Post)
		walkBlockStmt(v, n.Body)

	case *RangeStmt:
		Walk(v, n.Key)
		Walk(v, n.Value)
		Walk(v, n.X)
		walkBlockStmt(v, n.Body)

	// Declarations
	case *ImportSpec:
		walkCommentGroup(v, n.Doc)
		walkIdent(v, n.Name)
		Walk(v, n.Path)
		walkCommentGroup(v, n.Comment)

	case *ValueSpec:
		walkCommentGroup(v, n.Doc)
		Walk(v, n.Names)
		Walk(v, n.Type)
		Walk(v, n.Values)
		walkCommentGroup(v, n.Comment)

	case *TypeSpec:
		walkCommentGroup(v, n.Doc)
		walkIdent(v, n.Name)
		Walk(v, n.Type)
		walkCommentGroup(v, n.Comment)

	case *BadDecl:
		// nothing to do

	case *GenDecl:
		walkCommentGroup(v, n.Doc)
		for _, s := range n.Specs {
			Walk(v, s)
		}

	case *FuncDecl:
		walkCommentGroup(v, n.Doc)
		if n.Recv != nil {
			Walk(v, n.Recv)
		}
		walkIdent(v, n.Name)
		if n.Type != nil {
			Walk(v, n.Type)
		}
		walkBlockStmt(v, n.Body)

	// Files and packages
	case *File:
		walkCommentGroup(v, n.Doc)
		walkIdent(v, n.Name)
		Walk(v, n.Decls)
		for _, g := range n.Comments {
			Walk(v, g)
		}

	case *Package:
		for _, f := range n.Files {
			Walk(v, f)
		}

	case []*Ident:
		for _, x := range n {
			Walk(v, x)
		}

	case []Expr:
		for _, x := range n {
			Walk(v, x)
		}

	case []Stmt:
		for _, x := range n {
			Walk(v, x)
		}

	case []Decl:
		for _, x := range n {
			Walk(v, x)
		}

	default:
		fmt.Printf("ast.Walk: unexpected type %T", n)
		panic("ast.Walk")
	}

	v.Visit(nil)
}