// Fixed-hop expansion: one relationship step from a bound node, plus the
// bound-target rebind semijoin (probe a memoized reverse-neighbor set
// instead of re-expanding per row).
package exec

import (
	

	
	
	
	
)

// expandCandidates appends the endpoints of one relationship hop from the
// row's bound from-node, filtered by the op's matcher and (for a rebind)
// the already-bound target; a named relationship also records each rel's
// CSR position parallel to the node.
func expandCandidates( *eval.Ctx,  *plan.BindOp,  *graph.NodeMatcher,  *graph.RelMatcher,  []value.Value,  *[]graph.NodeID,  *[]uint32) {
	,  := [.From].AsNode()
	if ! {
		return
	}
	var  graph.NodeID
	 := false
	if .Rebind {
		,  = [.To].AsNode()
		if ! {
			return
		}
	}
	 := func( graph.NodeID) bool {
		return (! ||  == ) && .G.NodeMatcherAccepts(, )
	}
	// A native graph filters the appended tail through one batch call (the
	// hot single-dense-label matcher runs as a hoisted bitmap loop with no
	// per-candidate dispatch); the bound-target compaction stays ahead of
	// it, and non-native graphs keep the per-candidate closure.
	,  := .G.(*graph.SnapshotGraph)
	// Batch-append the hop into the pooled buffers, then filter the
	// appended tail in place (the iter.Seq forms would heap-allocate their
	// closures on every row -- see Graph.AppendNeighborsMatched). A named
	// relationship variable captures each rel's position alongside its
	// neighbor.
	 := len(*)
	if .RelSlot != plan.NoSlot {
		// Bound-both-endpoints named expand: the target is fixed, so match it
		// once and seek the (from, bound) relationship positions directly --
		// scanning the lower-degree endpoint -- instead of enumerating from's
		// whole degree and filtering to bound. Each parallel relationship is
		// one appended position (the named side of the enumeration/existence
		// boundary keeps per-relationship bindings observable).
		if  &&  {
			if !.G.NodeMatcherAccepts(, ) {
				return
			}
			boundPairSeeks++
			 := len(*)
			* = .AppendRelsBetween(*, , , .Dir, )
			for range (*)[:] {
				* = append(*, )
			}
			return
		}
		 := len(*)
		*, * = .G.AppendRelationshipsMatched(*, *, , .Dir, )
		if  {
			*, * = .FilterMatchedTail(, *, , *, )
			return
		}
		 := 
		for ,  := range (*)[:] {
			if () {
				(*)[] = 
				(*)[+(-)] = (*)[+]
				++
			}
		}
		* = (*)[:]
		* = (*)[:+(-)]
		return
	}
	* = .G.AppendNeighborsMatched(*, , .Dir, )
	if  {
		if  {
			 := 
			for ,  := range (*)[:] {
				if  ==  {
					(*)[] = 
					++
				}
			}
			* = (*)[:]
		}
		*, _ = .FilterMatchedTail(, *, , nil, 0)
		return
	}
	 := 
	for ,  := range (*)[:] {
		if () {
			(*)[] = 
			++
		}
	}
	* = (*)[:]
}

// semiCache memoizes per-target reverse-neighbor sets for one semijoin op,
// so a constant target builds its set once for the whole stage. Each set is
// a sorted id slice probed by binary search -- one allocation per target,
// versus a roaring bitmap's per-range containers for the same membership.
type semiCache map[graph.NodeID][]uint32

// semijoinSetBuilds counts reverse-neighbor-set materializations -- the
// build-once oracle for the semijoin memo: a stage of N rows probing one
// constant target must build exactly ONE set (the invariant neighborhood
// materialized once, membership per row); N builds means the memo is dead.
var semijoinSetBuilds int

// boundPairSeeks counts bound-both-endpoints named-expand position seeks --
// the dispatch oracle for the seek path: a named rebind expand over a bound
// target must reach the seek (this counter climbs) rather than fall back to
// enumerating the from-node's whole degree. A stage of N such rows registers
// N seeks; 0 means the seek is not firing.
var boundPairSeeks int

// buildSemijoins recognizes each bound-target rebind expand with no named
// relationship as an existence semijoin: probe from's membership in
// neighbors(to, flip(dir), types) O(1) per row. Multiplicity-identical to
// the expand on a simple graph; a named relationship keeps the expand so
// per-relationship bindings stay observable.
func buildSemijoins( []plan.BindOp) []semiCache {
	 := make([]semiCache, len())
	for  := range  {
		if [].Kind == plan.OpExpand && [].Rebind && [].RelSlot == plan.NoSlot {
			[] = semiCache{}
		}
	}
	return 
}

// semijoinCandidates yields the already-bound target once PER qualifying
// relationship from the row's from-node (parallel rels are adjacent
// duplicates in the sorted set, so multiplicity costs one forward walk on
// a hit and nothing on simple graphs), else nothing. Collapsing parallels
// here while the enumerated rebind expand multiplies them made the
// semijoin rewrite result-visible on multigraphs. An empty set
// also stands in for a target failing its own constraints.
func semijoinCandidates( *eval.Ctx,  *plan.BindOp,  *graph.NodeMatcher,  *graph.RelMatcher,  semiCache,  []value.Value,  *[]graph.NodeID,  *[]graph.NodeID) {
	,  := [.From].AsNode()
	,  := [.To].AsNode()
	if ! || ! {
		return
	}
	 := semiSetFor(, , , , , , )
	if ,  := slices.BinarySearch(, uint32());  {
		for  := ;  < len() && [] == uint32(); ++ {
			* = append(*, )
		}
	}
}

// semiSetFor resolves (building and memoizing on first sight) the
// target's reverse-neighbor membership set for one semijoin op.
func semiSetFor( *eval.Ctx,  *plan.BindOp,  *graph.NodeMatcher,  *graph.RelMatcher,  semiCache,  graph.NodeID,  *[]graph.NodeID) []uint32 {
	,  := []
	if ! {
		if .G.NodeMatcherAccepts(, ) {
			semijoinSetBuilds++
			 = reverseNeighborSet(, , .Dir, , )
		}
		[] = 
	}
	return 
}

// semijoinLookaheadPrunes counts fill-time lookahead sweeps that removed
// at least one candidate -- the engagement oracle: a level followed by a
// rebind semijoin over a bound target must prune doomed candidates
// BEFORE they bind, not enumerate rows the next level then discards.
var semijoinLookaheadPrunes int

// disableSemijoinLookahead pins result identity in tests: the un-pruned
// enumeration must produce exactly the rows the pruned walk does.
var disableSemijoinLookahead bool

// pruneSemijoinLookahead sweeps a freshly filled node-candidate level
// against the NEXT op's semijoin membership: a candidate with no
// qualifying relationship to the (already bound) target cannot survive
// the next level, so it never binds -- the pruned subtree produced no
// rows, and its relationship-uniqueness pushes were scoped to that
// subtree, so removal is invisible to every other candidate. Var-length
// levels keep their fill (their parallel per-trail buffers don't
// compact); the semijoin level itself still runs, serving multiplicity
// and profile exactly as before over the survivors.
func pruneSemijoinLookahead( *eval.Ctx,  []plan.BindOp,  *stageComp,  int,  []value.Value,  *genScratch) {
	 :=  + 1
	if disableSemijoinLookahead ||  >= len() || .semijoins[] == nil {
		return
	}
	 := &[]
	if .Kind == plan.OpVarExpand {
		return
	}
	 := &[]
	if .From != slotOf() {
		return
	}
	,  := [.To].AsNode()
	if ! {
		return
	}
	 := semiSetFor(, , .matchers[], .relMatchers[], .semijoins[], , &.semiBuf)
	 := .cand[]
	 := .candRel[]
	 := len() == len() && len() > 0
	 := 0
	for ,  := range  {
		if ,  := slices.BinarySearch(, uint32());  {
			[] = 
			if  {
				[] = []
			}
			++
		}
	}
	if  < len() {
		semijoinLookaheadPrunes++
	}
	.cand[] = [:]
	if  {
		.candRel[] = [:]
	}
}

// reverseNeighborSet is the set of nodes with a matching relationship to c
// over dir -- c's neighbors looking back along the flipped direction
// (matchers are direction-independent), collected into a reused buffer and
// returned as a sorted id slice for O(log n) membership probes.
func reverseNeighborSet( *eval.Ctx,  graph.NodeID,  graph.Direction,  *graph.RelMatcher,  *[]graph.NodeID) []uint32 {
	* = .G.AppendNeighborsMatched((*)[:0], , flipDir(), )
	 := make([]uint32, len(*))
	copy(, *)
	slices.Sort()
	return 
}

// flipDir is the direction seen when traversing a relationship the other
// way.
func flipDir( graph.Direction) graph.Direction {
	switch  {
	case graph.Outgoing:
		return graph.Incoming
	case graph.Incoming:
		return graph.Outgoing
	}
	return graph.Both
}