// 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 recursiveiter defines an Analyzer that checks for mistakes
// in iterators for recursive data structures.
//
// # Analyzer recursiveiter
//
// recursiveiter: check for inefficient recursive iterators
//
// This analyzer reports when a function that returns an iterator
// (iter.Seq or iter.Seq2) calls itself as the operand of a range
// statement, as this is inefficient.
//
// When implementing an iterator (e.g. iter.Seq[T]) for a recursive
// data type such as a tree or linked list, it is tempting to
// recursively range over the iterator for each child element.
//
// Here's an example of a naive iterator over a binary tree:
//
//	type tree struct {
//		value       int
//		left, right *tree
//	}
//
//	func (t *tree) All() iter.Seq[int] {
//		return func(yield func(int) bool) {
//			if t != nil {
//				for elem := range t.left.All() { // "inefficient recursive iterator"
//					if !yield(elem) {
//						return
//					}
//				}
//				if !yield(t.value) {
//					return
//				}
//				for elem := range t.right.All() { // "inefficient recursive iterator"
//					if !yield(elem) {
//						return
//					}
//				}
//			}
//		}
//	}
//
// Though it correctly enumerates the elements of the tree, it hides a
// significant performance problem--two, in fact. Consider a balanced
// tree of N nodes. Iterating the root node will cause All to be
// called once on every node of the tree. This results in a chain of
// nested active range-over-func statements when yield(t.value) is
// called on a leaf node.
//
// The first performance problem is that each range-over-func
// statement must typically heap-allocate a variable, so iteration of
// the tree allocates as many variables as there are elements in the
// tree, for a total of O(N) allocations, all unnecessary.
//
// The second problem is that each call to yield for a leaf of the
// tree causes each of the enclosing range loops to receive a value,
// which they then immediately pass on to their respective yield
// function. This results in a chain of log(N) dynamic yield calls per
// element, a total of O(N*log N) dynamic calls overall, when only
// O(N) are necessary.
//
// A better implementation strategy for recursive iterators is to
// first define the "every" operator for your recursive data type,
// where every(f) reports whether f(x) is true for every element x in
// the data type. For our tree, the every function would be:
//
//	func (t *tree) every(f func(int) bool) bool {
//		return t == nil ||
//			t.left.every(f) && f(t.value) && t.right.every(f)
//	}
//
// Then the iterator can be simply expressed as a trivial wrapper
// around this function:
//
//	func (t *tree) All() iter.Seq[int] {
//		return func(yield func(int) bool) {
//			_ = t.every(yield)
//		}
//	}
//
// In effect, tree.All computes whether yield returns true for each
// element, short-circuiting if it every returns false, then discards
// the final boolean result.
//
// This has much better performance characteristics: it makes one
// dynamic call per element of the tree, and it doesn't heap-allocate
// anything. It is also clearer.
package recursiveiter