// 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 

// 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 Node) (w Visitor)
}

// Helper functions for common node lists. They may be empty.

func walkIdentList( Visitor,  []*Ident) {
	for ,  := range  {
		Walk(, )
	}
}

func walkExprList( Visitor,  []Expr) {
	for ,  := range  {
		Walk(, )
	}
}

func walkStmtList( Visitor,  []Stmt) {
	for ,  := range  {
		Walk(, )
	}
}

func walkDeclList( Visitor,  []Decl) {
	for ,  := range  {
		Walk(, )
	}
}

// TODO(gri): Investigate if providing a closure to Walk leads to
//            simpler use (and may help eliminate Inspect in turn).

// Walk traverses an AST in depth-first order: It starts by calling
// v.Visit(node); node must not be nil. If the visitor w returned by
// v.Visit(node) is not nil, Walk is invoked recursively with visitor
// w for each of the non-nil children of node, followed by a call of
// w.Visit(nil).
//
func ( Visitor,  Node) {
	if  = .Visit();  == nil {
		return
	}

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

	case *CommentGroup:
		for ,  := range .List {
			(, )
		}

	case *Field:
		if .Doc != nil {
			(, .Doc)
		}
		walkIdentList(, .Names)
		(, .Type)
		if .Tag != nil {
			(, .Tag)
		}
		if .Comment != nil {
			(, .Comment)
		}

	case *FieldList:
		for ,  := range .List {
			(, )
		}

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

	case *Ellipsis:
		if .Elt != nil {
			(, .Elt)
		}

	case *FuncLit:
		(, .Type)
		(, .Body)

	case *CompositeLit:
		if .Type != nil {
			(, .Type)
		}
		walkExprList(, .Elts)

	case *ParenExpr:
		(, .X)

	case *SelectorExpr:
		(, .X)
		(, .Sel)

	case *IndexExpr:
		(, .X)
		(, .Index)

	case *SliceExpr:
		(, .X)
		if .Low != nil {
			(, .Low)
		}
		if .High != nil {
			(, .High)
		}
		if .Max != nil {
			(, .Max)
		}

	case *TypeAssertExpr:
		(, .X)
		if .Type != nil {
			(, .Type)
		}

	case *CallExpr:
		(, .Fun)
		walkExprList(, .Args)

	case *StarExpr:
		(, .X)

	case *UnaryExpr:
		(, .X)

	case *BinaryExpr:
		(, .X)
		(, .Y)

	case *KeyValueExpr:
		(, .Key)
		(, .Value)

	// Types
	case *ArrayType:
		if .Len != nil {
			(, .Len)
		}
		(, .Elt)

	case *StructType:
		(, .Fields)

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

	case *InterfaceType:
		(, .Methods)

	case *MapType:
		(, .Key)
		(, .Value)

	case *ChanType:
		(, .Value)

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

	case *DeclStmt:
		(, .Decl)

	case *EmptyStmt:
		// nothing to do

	case *LabeledStmt:
		(, .Label)
		(, .Stmt)

	case *ExprStmt:
		(, .X)

	case *SendStmt:
		(, .Chan)
		(, .Value)

	case *IncDecStmt:
		(, .X)

	case *AssignStmt:
		walkExprList(, .Lhs)
		walkExprList(, .Rhs)

	case *GoStmt:
		(, .Call)

	case *DeferStmt:
		(, .Call)

	case *ReturnStmt:
		walkExprList(, .Results)

	case *BranchStmt:
		if .Label != nil {
			(, .Label)
		}

	case *BlockStmt:
		walkStmtList(, .List)

	case *IfStmt:
		if .Init != nil {
			(, .Init)
		}
		(, .Cond)
		(, .Body)
		if .Else != nil {
			(, .Else)
		}

	case *CaseClause:
		walkExprList(, .List)
		walkStmtList(, .Body)

	case *SwitchStmt:
		if .Init != nil {
			(, .Init)
		}
		if .Tag != nil {
			(, .Tag)
		}
		(, .Body)

	case *TypeSwitchStmt:
		if .Init != nil {
			(, .Init)
		}
		(, .Assign)
		(, .Body)

	case *CommClause:
		if .Comm != nil {
			(, .Comm)
		}
		walkStmtList(, .Body)

	case *SelectStmt:
		(, .Body)

	case *ForStmt:
		if .Init != nil {
			(, .Init)
		}
		if .Cond != nil {
			(, .Cond)
		}
		if .Post != nil {
			(, .Post)
		}
		(, .Body)

	case *RangeStmt:
		if .Key != nil {
			(, .Key)
		}
		if .Value != nil {
			(, .Value)
		}
		(, .X)
		(, .Body)

	// Declarations
	case *ImportSpec:
		if .Doc != nil {
			(, .Doc)
		}
		if .Name != nil {
			(, .Name)
		}
		(, .Path)
		if .Comment != nil {
			(, .Comment)
		}

	case *ValueSpec:
		if .Doc != nil {
			(, .Doc)
		}
		walkIdentList(, .Names)
		if .Type != nil {
			(, .Type)
		}
		walkExprList(, .Values)
		if .Comment != nil {
			(, .Comment)
		}

	case *TypeSpec:
		if .Doc != nil {
			(, .Doc)
		}
		(, .Name)
		(, .Type)
		if .Comment != nil {
			(, .Comment)
		}

	case *BadDecl:
		// nothing to do

	case *GenDecl:
		if .Doc != nil {
			(, .Doc)
		}
		for ,  := range .Specs {
			(, )
		}

	case *FuncDecl:
		if .Doc != nil {
			(, .Doc)
		}
		if .Recv != nil {
			(, .Recv)
		}
		(, .Name)
		(, .Type)
		if .Body != nil {
			(, .Body)
		}

	// Files and packages
	case *File:
		if .Doc != nil {
			(, .Doc)
		}
		(, .Name)
		walkDeclList(, .Decls)
		// don't walk n.Comments - they have been
		// visited already through the individual
		// nodes

	case *Package:
		for ,  := range .Files {
			(, )
		}

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

	.Visit(nil)
}

type inspector func(Node) bool

func ( inspector) ( Node) Visitor {
	if () {
		return 
	}
	return nil
}

// Inspect traverses an AST in depth-first order: It starts by calling
// f(node); node must not be nil. If f returns true, Inspect invokes f
// recursively for each of the non-nil children of node, followed by a
// call of f(nil).
//
func ( Node,  func(Node) bool) {
	Walk(inspector(), )
}