// Copyright 2025 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 inspector

import (
	"fmt"
	"go/ast"
	"go/token"
	"iter"
	"reflect"

	"golang.org/x/tools/go/ast/edge"
)

// A Cursor represents an [ast.Node]. It is immutable.
//
// Two Cursors compare equal if they represent the same node.
//
// The zero value of Cursor is not valid.
//
// Call [Inspector.Root] to obtain a cursor for the virtual root node
// of the traversal. This is the sole valid cursor for which [Cursor.Node]
// returns nil.
//
// Use the following methods to navigate efficiently around the tree:
//   - for ancestors, use [Cursor.Parent] and [Cursor.Enclosing];
//   - for children, use [Cursor.Child], [Cursor.Children],
//     [Cursor.FirstChild], and [Cursor.LastChild];
//   - for siblings, use [Cursor.PrevSibling] and [Cursor.NextSibling];
//   - for descendants, use [Cursor.FindByPos], [Cursor.FindNode],
//     [Cursor.Inspect], and [Cursor.Preorder].
//
// Use the [Cursor.ChildAt] and [Cursor.ParentEdge] methods for
// information about the edges in a tree: which field (and slice
// element) of the parent node holds the child.
type Cursor struct {
	in    *Inspector
	index int32 // index of push node; -1 for virtual root node
}

// Root returns a valid cursor for the virtual root node,
// whose children are the files provided to [New].
//
// Its [Cursor.Node] method return nil.
func (in *Inspector) Root() Cursor {
	return Cursor{in, -1}
}

// At returns the cursor at the specified index in the traversal,
// which must have been obtained from [Cursor.Index] on a Cursor
// belonging to the same Inspector (see [Cursor.Inspector]).
func (in *Inspector) At(index int32) Cursor {
	if index < 0 {
		panic("negative index")
	}
	if int(index) >= len(in.events) {
		panic("index out of range for this inspector")
	}
	if in.events[index].index < index {
		panic("invalid index") // (a push, not a pop)
	}
	return Cursor{in, index}
}

// Valid reports whether the cursor is valid.
// The zero value of cursor is invalid.
// Unless otherwise documented, it is not safe to call
// any other method on an invalid cursor.
func (c Cursor) Valid() bool {
	return c.in != nil
}

// Inspector returns the cursor's Inspector.
// It returns nil if the Cursor is not valid.
func (c Cursor) Inspector() *Inspector { return c.in }

// Index returns the index of this cursor position within the package.
//
// Clients should not assume anything about the numeric Index value
// except that it increases monotonically throughout the traversal.
// It is provided for use with [Inspector.At].
//
// Index must not be called on the Root node.
func (c Cursor) Index() int32 {
	if c.index < 0 {
		panic("Index called on Root node")
	}
	return c.index
}

// Node returns the node at the current cursor position,
// or nil for the cursor returned by [Inspector.Root].
func (c Cursor) Node() ast.Node {
	if c.index < 0 {
		return nil
	}
	return c.in.events[c.index].node
}

// String returns information about the cursor's node, if any.
func (c Cursor) String() string {
	if !c.Valid() {
		return "(invalid)"
	}
	if c.index < 0 {
		return "(root)"
	}
	return reflect.TypeOf(c.Node()).String()
}

// indices return the [start, end) half-open interval of event indices.
func (c Cursor) indices() (int32, int32) {
	if c.index < 0 {
		return 0, int32(len(c.in.events)) // root: all events
	} else {
		return c.index, c.in.events[c.index].index + 1 // just one subtree
	}
}

// Preorder returns an iterator over the nodes of the subtree
// represented by c in depth-first order. Each node in the sequence is
// represented by a Cursor that allows access to the Node, but may
// also be used to start a new traversal, or to obtain the stack of
// nodes enclosing the cursor.
//
// The traversal sequence is determined by [ast.Inspect]. The types
// argument, if non-empty, enables type-based filtering of events. The
// function f if is called only for nodes whose type matches an
// element of the types slice.
//
// If you need control over descent into subtrees,
// or need both pre- and post-order notifications, use [Cursor.Inspect]
func (c Cursor) Preorder(types ...ast.Node) iter.Seq[Cursor] {
	mask := maskOf(types)

	return func(yield func(Cursor) bool) {
		events := c.in.events

		for i, limit := c.indices(); i < limit; {
			ev := events[i]
			if ev.index > i { // push?
				if ev.typ&mask != 0 && !yield(Cursor{c.in, i}) {
					break
				}
				pop := ev.index
				if events[pop].typ&mask == 0 {
					// Subtree does not contain types: skip.
					i = pop + 1
					continue
				}
			}
			i++
		}
	}
}

// Inspect visits the nodes of the subtree represented by c in
// depth-first order. It calls f(n) for each node n before it
// visits n's children. If f returns true, Inspect invokes f
// recursively for each of the non-nil children of the node.
//
// Each node is represented by a Cursor that allows access to the
// Node, but may also be used to start a new traversal, or to obtain
// the stack of nodes enclosing the cursor.
//
// The complete traversal sequence is determined by [ast.Inspect].
// The types argument, if non-empty, enables type-based filtering of
// events. The function f if is called only for nodes whose type
// matches an element of the types slice.
func (c Cursor) Inspect(types []ast.Node, f func(c Cursor) (descend bool)) {
	mask := maskOf(types)
	events := c.in.events
	for i, limit := c.indices(); i < limit; {
		ev := events[i]
		if ev.index > i {
			// push
			pop := ev.index
			if ev.typ&mask != 0 && !f(Cursor{c.in, i}) ||
				events[pop].typ&mask == 0 {
				// The user opted not to descend, or the
				// subtree does not contain types:
				// skip past the pop.
				i = pop + 1
				continue
			}
		}
		i++
	}
}

// Enclosing returns an iterator over the nodes enclosing the current
// current node, starting with the Cursor itself.
//
// Enclosing must not be called on the Root node (whose [Cursor.Node] returns nil).
//
// The types argument, if non-empty, enables type-based filtering of
// events: the sequence includes only enclosing nodes whose type
// matches an element of the types slice.
func (c Cursor) Enclosing(types ...ast.Node) iter.Seq[Cursor] {
	if c.index < 0 {
		panic("Cursor.Enclosing called on Root node")
	}

	mask := maskOf(types)

	return func(yield func(Cursor) bool) {
		events := c.in.events
		for i := c.index; i >= 0; i = events[i].parent {
			if events[i].typ&mask != 0 && !yield(Cursor{c.in, i}) {
				break
			}
		}
	}
}

// Parent returns the parent of the current node.
//
// Parent must not be called on the Root node (whose [Cursor.Node] returns nil).
func (c Cursor) Parent() Cursor {
	if c.index < 0 {
		panic("Cursor.Parent called on Root node")
	}

	return Cursor{c.in, c.in.events[c.index].parent}
}

// ParentEdge returns the identity of the field in the parent node
// that holds this cursor's node, and if it is a list, the index within it.
//
// For example, f(x, y) is a CallExpr whose three children are Idents.
// f has edge kind [edge.CallExpr_Fun] and index -1.
// x and y have kind [edge.CallExpr_Args] and indices 0 and 1, respectively.
//
// If called on a child of the Root node, it returns ([edge.Invalid], -1).
//
// ParentEdge must not be called on the Root node (whose [Cursor.Node] returns nil).
func (c Cursor) ParentEdge() (edge.Kind, int) {
	if c.index < 0 {
		panic("Cursor.ParentEdge called on Root node")
	}
	events := c.in.events
	pop := events[c.index].index
	return unpackEdgeKindAndIndex(events[pop].parent)
}

// ParentEdgeKind returns the kind component of the result of [Cursor.ParentEdge].
func (c Cursor) ParentEdgeKind() edge.Kind {
	ek, _ := c.ParentEdge()
	return ek
}

// ParentEdgeIndex returns the index component of the result of [Cursor.ParentEdge].
func (c Cursor) ParentEdgeIndex() int {
	_, index := c.ParentEdge()
	return index
}

// ChildAt returns the cursor for the child of the
// current node identified by its edge and index.
// The index must be -1 if the edge.Kind is not a slice.
// The indicated child node must exist.
//
// ChildAt must not be called on the Root node (whose [Cursor.Node] returns nil).
//
// Invariant: c.Parent().ChildAt(c.ParentEdge()) == c.
func (c Cursor) ChildAt(k edge.Kind, idx int) Cursor {
	target := packEdgeKindAndIndex(k, idx)

	// Unfortunately there's no shortcut to looping.
	events := c.in.events
	i := c.index + 1
	for {
		pop := events[i].index
		if pop < i {
			break
		}
		if events[pop].parent == target {
			return Cursor{c.in, i}
		}
		i = pop + 1
	}
	panic(fmt.Sprintf("ChildAt(%v, %d): no such child of %v", k, idx, c))
}

// Child returns the cursor for n, which must be a direct child of c's Node.
//
// Child must not be called on the Root node (whose [Cursor.Node] returns nil).
func (c Cursor) Child(n ast.Node) Cursor {
	if c.index < 0 {
		panic("Cursor.Child called on Root node")
	}

	if false {
		// reference implementation
		for child := range c.Children() {
			if child.Node() == n {
				return child
			}
		}

	} else {
		// optimized implementation
		events := c.in.events
		for i := c.index + 1; events[i].index > i; i = events[i].index + 1 {
			if events[i].node == n {
				return Cursor{c.in, i}
			}
		}
	}
	panic(fmt.Sprintf("Child(%T): not a child of %v", n, c))
}

// NextSibling returns the cursor for the next sibling node in the same list
// (for example, of files, decls, specs, statements, fields, or expressions) as
// the current node. It returns (zero, false) if the node is the last node in
// the list, or is not part of a list.
//
// NextSibling must not be called on the Root node.
//
// See note at [Cursor.Children].
func (c Cursor) NextSibling() (Cursor, bool) {
	if c.index < 0 {
		panic("Cursor.NextSibling called on Root node")
	}

	events := c.in.events
	i := events[c.index].index + 1 // after corresponding pop
	if i < int32(len(events)) {
		if events[i].index > i { // push?
			return Cursor{c.in, i}, true
		}
	}
	return Cursor{}, false
}

// PrevSibling returns the cursor for the previous sibling node in the
// same list (for example, of files, decls, specs, statements, fields,
// or expressions) as the current node. It returns zero if the node is
// the first node in the list, or is not part of a list.
//
// It must not be called on the Root node.
//
// See note at [Cursor.Children].
func (c Cursor) PrevSibling() (Cursor, bool) {
	if c.index < 0 {
		panic("Cursor.PrevSibling called on Root node")
	}

	events := c.in.events
	i := c.index - 1
	if i >= 0 {
		if j := events[i].index; j < i { // pop?
			return Cursor{c.in, j}, true
		}
	}
	return Cursor{}, false
}

// FirstChild returns the first direct child of the current node,
// or zero if it has no children.
func (c Cursor) FirstChild() (Cursor, bool) {
	events := c.in.events
	i := c.index + 1                                   // i=0 if c is root
	if i < int32(len(events)) && events[i].index > i { // push?
		return Cursor{c.in, i}, true
	}
	return Cursor{}, false
}

// LastChild returns the last direct child of the current node,
// or zero if it has no children.
func (c Cursor) LastChild() (Cursor, bool) {
	events := c.in.events
	if c.index < 0 { // root?
		if len(events) > 0 {
			// return push of final event (a pop)
			return Cursor{c.in, events[len(events)-1].index}, true
		}
	} else {
		j := events[c.index].index - 1 // before corresponding pop
		// Inv: j == c.index if c has no children
		//  or  j is last child's pop.
		if j > c.index { // c has children
			return Cursor{c.in, events[j].index}, true
		}
	}
	return Cursor{}, false
}

// Children returns an iterator over the direct children of the
// current node, if any.
//
// When using Children, NextChild, and PrevChild, bear in mind that a
// Node's children may come from different fields, some of which may
// be lists of nodes without a distinguished intervening container
// such as [ast.BlockStmt].
//
// For example, [ast.CaseClause] has a field List of expressions and a
// field Body of statements, so the children of a CaseClause are a mix
// of expressions and statements. Other nodes that have "uncontained"
// list fields include:
//
//   - [ast.ValueSpec] (Names, Values)
//   - [ast.CompositeLit] (Type, Elts)
//   - [ast.IndexListExpr] (X, Indices)
//   - [ast.CallExpr] (Fun, Args)
//   - [ast.AssignStmt] (Lhs, Rhs)
//
// So, do not assume that the previous sibling of an ast.Stmt is also
// an ast.Stmt, or if it is, that they are executed sequentially,
// unless you have established that, say, its parent is a BlockStmt
// or its [Cursor.ParentEdge] is [edge.BlockStmt_List].
// For example, given "for S1; ; S2 {}", the predecessor of S2 is S1,
// even though they are not executed in sequence.
func (c Cursor) Children() iter.Seq[Cursor] {
	return func(yield func(Cursor) bool) {
		c, ok := c.FirstChild()
		for ok && yield(c) {
			c, ok = c.NextSibling()
		}
	}
}

// Contains reports whether c contains or is equal to c2.
//
// Both Cursors must belong to the same [Inspector];
// neither may be its Root node.
func (c Cursor) Contains(c2 Cursor) bool {
	if c.in != c2.in {
		panic("different inspectors")
	}
	events := c.in.events
	return c.index <= c2.index && events[c2.index].index <= events[c.index].index
}

// FindNode returns the cursor for node n if it belongs to the subtree
// rooted at c. It returns zero if n is not found.
func (c Cursor) FindNode(n ast.Node) (Cursor, bool) {

	// FindNode is equivalent to this code,
	// but more convenient and 15-20% faster:
	if false {
		for candidate := range c.Preorder(n) {
			if candidate.Node() == n {
				return candidate, true
			}
		}
		return Cursor{}, false
	}

	// TODO(adonovan): opt: should we assume Node.Pos is accurate
	// and combine type-based filtering with position filtering
	// like FindByPos?

	mask := maskOf([]ast.Node{n})
	events := c.in.events

	for i, limit := c.indices(); i < limit; i++ {
		ev := events[i]
		if ev.index > i { // push?
			if ev.typ&mask != 0 && ev.node == n {
				return Cursor{c.in, i}, true
			}
			pop := ev.index
			if events[pop].typ&mask == 0 {
				// Subtree does not contain type of n: skip.
				i = pop
			}
		}
	}
	return Cursor{}, false
}

// FindByPos returns the cursor for the innermost node n in the tree
// rooted at c such that n.Pos() <= start && end <= n.End().
// (For an *ast.File, it uses the bounds n.FileStart-n.FileEnd.)
//
// An empty range (start == end) between two adjacent nodes is
// considered to belong to the first node.
//
// It returns zero if none is found.
// Precondition: start <= end.
//
// See also [astutil.PathEnclosingInterval], which
// tolerates adjoining whitespace.
func (c Cursor) FindByPos(start, end token.Pos) (Cursor, bool) {
	if end < start {
		panic("end < start")
	}
	events := c.in.events

	// This algorithm could be implemented using c.Inspect,
	// but it is about 2.5x slower.

	// best is the push-index of the latest (=innermost) node containing range.
	// (Beware: latest is not always innermost because FuncDecl.{Name,Type} overlap.)
	best := int32(-1)
	for i, limit := c.indices(); i < limit; i++ {
		ev := events[i]
		if ev.index > i { // push?
			n := ev.node
			var nodeEnd token.Pos
			if file, ok := n.(*ast.File); ok {
				nodeEnd = file.FileEnd
				// Note: files may be out of Pos order.
				if file.FileStart > start {
					i = ev.index // disjoint, after; skip to next file
					continue
				}
			} else {
				// Edge case: FuncDecl.Name and .Type overlap:
				// Don't update best from Name to FuncDecl.Type.
				//
				// The condition can be read as:
				// - n is FuncType
				// - n.parent is FuncDecl
				// - best is strictly beneath the FuncDecl
				if ev.typ == 1<<nFuncType &&
					events[ev.parent].typ == 1<<nFuncDecl &&
					best > ev.parent {
					continue
				}

				nodeEnd = n.End()
				if n.Pos() > start {
					break // disjoint, after; stop
				}
			}

			// Inv: node.{Pos,FileStart} <= start
			if end <= nodeEnd {
				// node fully contains target range
				best = i

				// Don't search beyond end of the first match.
				// This is important only for an empty range (start=end)
				// between two adjoining nodes, which would otherwise
				// match both nodes; we want to match only the first.
				limit = ev.index
			} else if nodeEnd < start {
				i = ev.index // disjoint, before; skip forward
			}
		}
	}
	if best >= 0 {
		return Cursor{c.in, best}, true
	}
	return Cursor{}, false
}