// The correlated-subquery DFS walk: level-by-level candidate generation
// over a shaped pattern (anchored endpoints, lazily compiled matchers,
// the quantified-hop reach) -- the evaluation half of subquery.go's
// shape/count entry points.
package eval

import (
	
	
	
)

// dfs enumerates the pattern's matches level by level, invoking onMatch at
// each full assignment; onMatch returning true stops the search (the
// EXISTS fast path). Level candidates fill the shape's per-level scratch.
func ( *subqueryShape) ( *Ctx,  int,  func() bool) bool {
	if  == len(.nodes) {
		return ()
	}
	 := .nodes[]
	 := .nodeSlots[]
	 := .cand[][:0]
	if  == 0 {
		if .anchored[0] {
			if ,  := .row[].AsNode();  && .G.NodeMatcherAccepts(.nodeMatcherFor(, 0), ) {
				 = append(, )
			}
		} else {
			 = append(, .existsScan(, )...)
		}
	} else {
		 := &.pattern.Hops[-1].Rel
		,  := .row[.nodeSlots[-1]].AsNode()
		if ! {
			return false
		}
		var  graph.NodeID
		 := false
		if .anchored[] {
			,  := .row[].AsNode()
			if ! {
				// An outer variable bound to null (e.g. an unmatched
				// OPTIONAL MATCH variable) cannot match any node.
				return false
			}
			,  = , true
		}
		switch {
		case .Length == nil && :
			// Both endpoints bound: count the matching relationships
			// directly instead of enumerating a candidate set, appending
			// the bound node once per relationship so match multiplicity
			// (COUNT forms) is preserved exactly.
			if .G.NodeMatcherAccepts(.nodeMatcherFor(, ), ) {
				 := .G.CountNeighborsMatched(, , engineDir(.Dir), .matcherFor(, -1))
				for range  {
					 = append(, )
				}
			}
		default:
			if .Length != nil {
				 = .existsReach(, , , -1, )
			} else {
				 = .G.AppendNeighborsMatched(, , engineDir(.Dir), .matcherFor(, -1))
			}
			// Filter the appended tail in place: endpoint binding and the
			// pattern node's own constraints.
			 := .nodeMatcherFor(, )
			 := [:0]
			for ,  := range  {
				if (! ||  == ) && .G.NodeMatcherAccepts(, ) {
					 = append(, )
				}
			}
			 = 
		}
	}
	.cand[] = 
	for ,  := range  {
		.row[] = value.Node()
		if .(, +1, ) {
			return true
		}
	}
	return false
}

// existsScan is the level-0 candidate source for an unanchored start
// node: the first label's index set (or the whole id space with no
// label), filtered by the full pattern-node match. The result is
// evaluation-invariant, memoized on the shape.
func ( *subqueryShape) ( *Ctx,  *ast.NodePat) []graph.NodeID {
	if .scan0Done {
		return .scan0
	}
	 := .nodeMatcherFor(, 0)
	if len(.Labels) > 0 {
		if  := .G.NodesWithLabel(.Labels[0]);  != nil {
			for  := range .Iter() {
				if .G.NodeMatcherAccepts(, ) {
					.scan0 = append(.scan0, )
				}
			}
		}
	} else {
		// A sparse id space contains gap ids that are not nodes; the
		// existence oracle keeps them out (same rule as the exec fresh
		// scan's all-nodes arm).
		for  := graph.NodeID(0);  < .G.IDSpace(); ++ {
			if .G.NodeExists() && .G.NodeMatcherAccepts(, ) {
				.scan0 = append(.scan0, )
			}
		}
	}
	.scan0Done = true
	return .scan0
}

// existsReach is a quantified hop's candidate set inside a subquery: the
// distinct nodes reachable in min..=max hops appended to dst (dedup'd BFS;
// min 0 includes the start, a nil max is unbounded). An existence test
// needs the reachable set, not per-path enumeration -- the same collapse
// varReach applies in the main pipeline. BFS state reuses the shape's
// scratch.
// nodeMatcherFor lazily compiles (once per shape) level i's node matcher;
// the shape is Ctx-cached and single-threaded, so plain lazy fill is safe.
func ( *subqueryShape) ( *Ctx,  int) *graph.NodeMatcher {
	if .nodeMatchers == nil {
		.nodeMatchers = make([]*graph.NodeMatcher, len(.nodes))
	}
	if .nodeMatchers[] == nil {
		 := .nodes[]
		 := make([]graph.PropSpec, len(.Props))
		for ,  := range .Props {
			[] = graph.PropSpec{Key: .Key, Val: LitValue(, .Val)}
		}
		.nodeMatchers[] = .G.CompileNodeMatcher(.Labels, )
	}
	return .nodeMatchers[]
}

// matcherFor lazily resolves (once per shape) hop i's rel matcher; the
// shape is Ctx-cached and single-threaded, so plain lazy fill is safe.
func ( *subqueryShape) ( *Ctx,  int) *graph.RelMatcher {
	if .matchers == nil {
		.matchers = make([]*graph.RelMatcher, len(.pattern.Hops))
	}
	if .matchers[] == nil {
		.matchers[] = .G.CompileRelMatcher(.pattern.Hops[].Rel.Types)
	}
	return .matchers[]
}

func ( *subqueryShape) ( *Ctx,  graph.NodeID,  *ast.RelPat,  int,  []graph.NodeID) []graph.NodeID {
	var  uint64
	if .Length.Min != nil {
		 = *.Length.Min
	}
	 := uint64(1<<63 - 1)
	if .Length.Max != nil {
		 = *.Length.Max
	}
	if .expanded == nil {
		.expanded = map[graph.NodeID]struct{}{}
		.emitted = map[graph.NodeID]struct{}{}
	} else {
		clear(.expanded)
		clear(.emitted)
	}
	 := engineDir(.Dir)
	.expanded[] = struct{}{}
	if  == 0 {
		.emitted[] = struct{}{}
		 = append(, )
	}
	 := append(.frontier[:0], )
	 := .next[:0]
	for  := uint64(0); len() > 0 &&  < ; ++ {
		 :=  + 1
		 = [:0]
		for ,  := range  {
			.reach = .G.AppendNeighborsMatched(.reach[:0], , , .matcherFor(, ))
			for ,  := range .reach {
				if  >=  {
					if ,  := .emitted[]; ! {
						.emitted[] = struct{}{}
						 = append(, )
					}
				}
				if ,  := .expanded[]; ! {
					.expanded[] = struct{}{}
					 = append(, )
				}
			}
		}
		,  = , 
	}
	.frontier, .next = , 
	return 
}