// Copyright 2017 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 astutil

import (
	
	
	
	
)

// An ApplyFunc is invoked by Apply for each node n, even if n is nil,
// before and/or after the node's children, using a Cursor describing
// the current node and providing operations on it.
//
// The return value of ApplyFunc controls the syntax tree traversal.
// See Apply for details.
type ApplyFunc func(*Cursor) bool

// Apply traverses a syntax tree recursively, starting with root,
// and calling pre and post for each node as described below.
// Apply returns the syntax tree, possibly modified.
//
// If pre is not nil, it is called for each node before the node's
// children are traversed (pre-order). If pre returns false, no
// children are traversed, and post is not called for that node.
//
// If post is not nil, and a prior call of pre didn't return false,
// post is called for each node after its children are traversed
// (post-order). If post returns false, traversal is terminated and
// Apply returns immediately.
//
// Only fields that refer to AST nodes are considered children;
// i.e., token.Pos, Scopes, Objects, and fields of basic types
// (strings, etc.) are ignored.
//
// Children are traversed in the order in which they appear in the
// respective node's struct definition. A package's files are
// traversed in the filenames' alphabetical order.
func ( ast.Node, ,  ApplyFunc) ( ast.Node) {
	 := &struct{ ast.Node }{}
	defer func() {
		if  := recover();  != nil &&  != abort {
			panic()
		}
		 = .
	}()
	 := &application{pre: , post: }
	.apply(, "Node", nil, )
	return
}

var abort = new(int) // singleton, to signal termination of Apply

// A Cursor describes a node encountered during Apply.
// Information about the node and its parent is available
// from the Node, Parent, Name, and Index methods.
//
// If p is a variable of type and value of the current parent node
// c.Parent(), and f is the field identifier with name c.Name(),
// the following invariants hold:
//
//	p.f            == c.Node()  if c.Index() <  0
//	p.f[c.Index()] == c.Node()  if c.Index() >= 0
//
// The methods Replace, Delete, InsertBefore, and InsertAfter
// can be used to change the AST without disrupting Apply.
//
// This type is not to be confused with [inspector.Cursor] from
// package [golang.org/x/tools/go/ast/inspector], which provides
// stateless navigation of immutable syntax trees.
type Cursor struct {
	parent ast.Node
	name   string
	iter   *iterator // valid if non-nil
	node   ast.Node
}

// Node returns the current Node.
func ( *Cursor) () ast.Node { return .node }

// Parent returns the parent of the current Node.
func ( *Cursor) () ast.Node { return .parent }

// Name returns the name of the parent Node field that contains the current Node.
// If the parent is a *ast.Package and the current Node is a *ast.File, Name returns
// the filename for the current Node.
func ( *Cursor) () string { return .name }

// Index reports the index >= 0 of the current Node in the slice of Nodes that
// contains it, or a value < 0 if the current Node is not part of a slice.
// The index of the current node changes if InsertBefore is called while
// processing the current node.
func ( *Cursor) () int {
	if .iter != nil {
		return .iter.index
	}
	return -1
}

// field returns the current node's parent field value.
func ( *Cursor) () reflect.Value {
	return reflect.Indirect(reflect.ValueOf(.parent)).FieldByName(.name)
}

// Replace replaces the current Node with n.
// The replacement node is not walked by Apply.
func ( *Cursor) ( ast.Node) {
	if ,  := .node.(*ast.File);  {
		,  := .(*ast.File)
		if ! {
			panic("attempt to replace *ast.File with non-*ast.File")
		}
		.parent.(*ast.Package).Files[.name] = 
		return
	}

	 := .field()
	if  := .Index();  >= 0 {
		 = .Index()
	}
	.Set(reflect.ValueOf())
}

// Delete deletes the current Node from its containing slice.
// If the current Node is not part of a slice, Delete panics.
// As a special case, if the current node is a package file,
// Delete removes it from the package's Files map.
func ( *Cursor) () {
	if ,  := .node.(*ast.File);  {
		delete(.parent.(*ast.Package).Files, .name)
		return
	}

	 := .Index()
	if  < 0 {
		panic("Delete node not contained in slice")
	}
	 := .field()
	 := .Len()
	reflect.Copy(.Slice(, ), .Slice(+1, ))
	.Index( - 1).Set(reflect.Zero(.Type().Elem()))
	.SetLen( - 1)
	.iter.step--
}

// InsertAfter inserts n after the current Node in its containing slice.
// If the current Node is not part of a slice, InsertAfter panics.
// Apply does not walk n.
func ( *Cursor) ( ast.Node) {
	 := .Index()
	if  < 0 {
		panic("InsertAfter node not contained in slice")
	}
	 := .field()
	.Set(reflect.Append(, reflect.Zero(.Type().Elem())))
	 := .Len()
	reflect.Copy(.Slice(+2, ), .Slice(+1, ))
	.Index( + 1).Set(reflect.ValueOf())
	.iter.step++
}

// InsertBefore inserts n before the current Node in its containing slice.
// If the current Node is not part of a slice, InsertBefore panics.
// Apply will not walk n.
func ( *Cursor) ( ast.Node) {
	 := .Index()
	if  < 0 {
		panic("InsertBefore node not contained in slice")
	}
	 := .field()
	.Set(reflect.Append(, reflect.Zero(.Type().Elem())))
	 := .Len()
	reflect.Copy(.Slice(+1, ), .Slice(, ))
	.Index().Set(reflect.ValueOf())
	.iter.index++
}

// application carries all the shared data so we can pass it around cheaply.
type application struct {
	pre, post ApplyFunc
	cursor    Cursor
	iter      iterator
}

func ( *application) ( ast.Node,  string,  *iterator,  ast.Node) {
	// convert typed nil into untyped nil
	if  := reflect.ValueOf(); .Kind() == reflect.Pointer && .IsNil() {
		 = nil
	}

	// avoid heap-allocating a new cursor for each apply call; reuse a.cursor instead
	 := .cursor
	.cursor.parent = 
	.cursor.name = 
	.cursor.iter = 
	.cursor.node = 

	if .pre != nil && !.pre(&.cursor) {
		.cursor = 
		return
	}

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

	// Comments and fields
	case *ast.Comment:
		// nothing to do

	case *ast.CommentGroup:
		if  != nil {
			.applyList(, "List")
		}

	case *ast.Field:
		.(, "Doc", nil, .Doc)
		.applyList(, "Names")
		.(, "Type", nil, .Type)
		.(, "Tag", nil, .Tag)
		.(, "Comment", nil, .Comment)

	case *ast.FieldList:
		.applyList(, "List")

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

	case *ast.Ellipsis:
		.(, "Elt", nil, .Elt)

	case *ast.FuncLit:
		.(, "Type", nil, .Type)
		.(, "Body", nil, .Body)

	case *ast.CompositeLit:
		.(, "Type", nil, .Type)
		.applyList(, "Elts")

	case *ast.ParenExpr:
		.(, "X", nil, .X)

	case *ast.SelectorExpr:
		.(, "X", nil, .X)
		.(, "Sel", nil, .Sel)

	case *ast.IndexExpr:
		.(, "X", nil, .X)
		.(, "Index", nil, .Index)

	case *ast.IndexListExpr:
		.(, "X", nil, .X)
		.applyList(, "Indices")

	case *ast.SliceExpr:
		.(, "X", nil, .X)
		.(, "Low", nil, .Low)
		.(, "High", nil, .High)
		.(, "Max", nil, .Max)

	case *ast.TypeAssertExpr:
		.(, "X", nil, .X)
		.(, "Type", nil, .Type)

	case *ast.CallExpr:
		.(, "Fun", nil, .Fun)
		.applyList(, "Args")

	case *ast.StarExpr:
		.(, "X", nil, .X)

	case *ast.UnaryExpr:
		.(, "X", nil, .X)

	case *ast.BinaryExpr:
		.(, "X", nil, .X)
		.(, "Y", nil, .Y)

	case *ast.KeyValueExpr:
		.(, "Key", nil, .Key)
		.(, "Value", nil, .Value)

	// Types
	case *ast.ArrayType:
		.(, "Len", nil, .Len)
		.(, "Elt", nil, .Elt)

	case *ast.StructType:
		.(, "Fields", nil, .Fields)

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

	case *ast.InterfaceType:
		.(, "Methods", nil, .Methods)

	case *ast.MapType:
		.(, "Key", nil, .Key)
		.(, "Value", nil, .Value)

	case *ast.ChanType:
		.(, "Value", nil, .Value)

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

	case *ast.DeclStmt:
		.(, "Decl", nil, .Decl)

	case *ast.EmptyStmt:
		// nothing to do

	case *ast.LabeledStmt:
		.(, "Label", nil, .Label)
		.(, "Stmt", nil, .Stmt)

	case *ast.ExprStmt:
		.(, "X", nil, .X)

	case *ast.SendStmt:
		.(, "Chan", nil, .Chan)
		.(, "Value", nil, .Value)

	case *ast.IncDecStmt:
		.(, "X", nil, .X)

	case *ast.AssignStmt:
		.applyList(, "Lhs")
		.applyList(, "Rhs")

	case *ast.GoStmt:
		.(, "Call", nil, .Call)

	case *ast.DeferStmt:
		.(, "Call", nil, .Call)

	case *ast.ReturnStmt:
		.applyList(, "Results")

	case *ast.BranchStmt:
		.(, "Label", nil, .Label)

	case *ast.BlockStmt:
		.applyList(, "List")

	case *ast.IfStmt:
		.(, "Init", nil, .Init)
		.(, "Cond", nil, .Cond)
		.(, "Body", nil, .Body)
		.(, "Else", nil, .Else)

	case *ast.CaseClause:
		.applyList(, "List")
		.applyList(, "Body")

	case *ast.SwitchStmt:
		.(, "Init", nil, .Init)
		.(, "Tag", nil, .Tag)
		.(, "Body", nil, .Body)

	case *ast.TypeSwitchStmt:
		.(, "Init", nil, .Init)
		.(, "Assign", nil, .Assign)
		.(, "Body", nil, .Body)

	case *ast.CommClause:
		.(, "Comm", nil, .Comm)
		.applyList(, "Body")

	case *ast.SelectStmt:
		.(, "Body", nil, .Body)

	case *ast.ForStmt:
		.(, "Init", nil, .Init)
		.(, "Cond", nil, .Cond)
		.(, "Post", nil, .Post)
		.(, "Body", nil, .Body)

	case *ast.RangeStmt:
		.(, "Key", nil, .Key)
		.(, "Value", nil, .Value)
		.(, "X", nil, .X)
		.(, "Body", nil, .Body)

	// Declarations
	case *ast.ImportSpec:
		.(, "Doc", nil, .Doc)
		.(, "Name", nil, .Name)
		.(, "Path", nil, .Path)
		.(, "Comment", nil, .Comment)

	case *ast.ValueSpec:
		.(, "Doc", nil, .Doc)
		.applyList(, "Names")
		.(, "Type", nil, .Type)
		.applyList(, "Values")
		.(, "Comment", nil, .Comment)

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

	case *ast.BadDecl:
		// nothing to do

	case *ast.GenDecl:
		.(, "Doc", nil, .Doc)
		.applyList(, "Specs")

	case *ast.FuncDecl:
		.(, "Doc", nil, .Doc)
		.(, "Recv", nil, .Recv)
		.(, "Name", nil, .Name)
		.(, "Type", nil, .Type)
		.(, "Body", nil, .Body)

	// Files and packages
	case *ast.File:
		.(, "Doc", nil, .Doc)
		.(, "Name", nil, .Name)
		.applyList(, "Decls")
		// Don't walk n.Comments; they have either been walked already if
		// they are Doc comments, or they can be easily walked explicitly.

	case *ast.Package:
		// collect and sort names for reproducible behavior
		var  []string
		for  := range .Files {
			 = append(, )
		}
		sort.Strings()
		for ,  := range  {
			.(, , nil, .Files[])
		}

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

	if .post != nil && !.post(&.cursor) {
		panic(abort)
	}

	.cursor = 
}

// An iterator controls iteration over a slice of nodes.
type iterator struct {
	index, step int
}

func ( *application) ( ast.Node,  string) {
	// avoid heap-allocating a new iterator for each applyList call; reuse a.iter instead
	 := .iter
	.iter.index = 0
	for {
		// must reload parent.name each time, since cursor modifications might change it
		 := reflect.Indirect(reflect.ValueOf()).FieldByName()
		if .iter.index >= .Len() {
			break
		}

		// element x may be nil in a bad AST - be cautious
		var  ast.Node
		if  := .Index(.iter.index); .IsValid() {
			 = .Interface().(ast.Node)
		}

		.iter.step = 1
		.apply(, , &.iter, )
		.iter.index += .iter.step
	}
	.iter = 
}