// Correlated-subquery decorrelation setup: recognizing a cheap bound-pair
// EXISTS probe, computing a subquery's outer-slot memo key, and marking a
// COUNT{} decorrelatable when it is a fixed linear chain between two
// outer-bound endpoints with no other outer dependency (evaluated once per
// anchor instead of a DFS per row). Split from compile.go, which holds the
// compiled-node types and the expression compiler.
package compile

import 

// cheapExistsProbe reports the subquery shape whose evaluation is a
// near-constant-time bound-pair probe: one fixed-length hop, both
// endpoint variables bound in the outer scope, no inner WHERE.
func cheapExistsProbe( *ast.Pattern,  ast.Expr,  map[string]int) bool {
	if  != nil || len(.Hops) != 1 || .Hops[0].Rel.Length != nil {
		return false
	}
	 := .Start.Var != "" && hasSlot(, .Start.Var)
	 := .Hops[0].Node.Var != "" && hasSlot(, .Hops[0].Node.Var)
	return  && 
}

func hasSlot( map[string]int,  string) bool {
	,  := []
	return 
}

// correlatedSlots is the outer slots a correlated subquery reads -- its
// memo key. ok=false when the dependency set can't be fully determined (a
// nested subquery), which disables memoization (still correct, evaluated
// per row).
func correlatedSlots( *ast.Pattern,  ast.Expr,  map[string]int) ([]int, bool) {
	 := map[int]struct{}{}
	 := func( string) {
		if  == "" {
			return
		}
		if ,  := [];  {
			[] = struct{}{}
		}
	}
	(.Start.Var)
	for  := range .Hops {
		(.Hops[].Rel.Var)
		(.Hops[].Node.Var)
	}
	 := true
	if  != nil {
		 = collectOuterSlots(, , )
	}
	 := make([]int, 0, len())
	for  := range  {
		 = append(, )
	}
	// Deterministic key order.
	for  := 1;  < len(); ++ {
		for  := ;  > 0 && [] < [-1]; -- {
			[], [-1] = [-1], []
		}
	}
	if ! {
		return nil, false
	}
	return , true
}

// setupDecor marks cs decorrelatable and records its endpoints when the
// COUNT{} is a linear chain whose two endpoints are BOTH bound to outer
// variables and whose only outer dependencies are those endpoints. Such a
// subquery is a per-endpoint aggregate over an anchored set: it can be
// evaluated once per distinct anchor value (grouped by the other endpoint)
// instead of a DFS per outer row (task 084). Conservative -- any structure the
// single-scan rewrite would not reproduce exactly (an inner node that is
// itself an outer variable, a bound relationship variable, a variable-length
// hop, or a WHERE that reads an outer variable other than the two endpoints)
// leaves cs on the existing per-row path.
func setupDecor( *cSubquery,  *ast.Pattern,  ast.Expr,  map[string]int) {
	if len(.Hops) < 1 {
		return
	}
	 := .Start.Var
	 := .EndNode().Var
	if  == "" ||  == "" ||  ==  {
		return
	}
	,  := []
	,  := []
	if ! || ! {
		return
	}
	// Inner nodes must be subquery-local, and no relationship variable may be
	// outer-bound: the single grouped scan enumerates every inner element, so
	// an outer-anchored inner would change which matches it produces.
	for  := range .Hops {
		if .Hops[].Rel.Length != nil {
			return // variable-length hop: v1 handles fixed chains only
		}
		if  := .Hops[].Rel.Var;  != "" {
			if ,  := [];  {
				return
			}
		}
		if  < len(.Hops)-1 { // inner node (not the end endpoint)
			if  := .Hops[].Node.Var;  != "" {
				if ,  := [];  {
					return
				}
			}
		}
	}
	// The WHERE may read only the two endpoints (and inner, subquery-local
	// variables). Any other outer variable would make the table depend on a
	// value not captured by the anchor key, so it could not be shared across
	// rows. collectOuterSlots reports false for an unenumerable dependency.
	if  != nil {
		 := false
		 := collectOuterSlots(, , func( string) {
			if ,  := [];  &&  !=  &&  !=  {
				 = true
			}
		})
		if ! ||  {
			return
		}
	}
	.decorOK = true
	.decorStartVar, .decorEndVar = , 
	.decorStartSlot, .decorEndSlot = , 
}

// collectOuterSlots adds the outer slots e references; returns false when
// e contains a construct whose outer dependencies can't be enumerated (a
// nested EXISTS/COUNT, or a pattern comprehension's correlation).
func collectOuterSlots( ast.Expr,  map[string]int,  func(string)) bool {
	switch n := .(type) {
	case *ast.Lit:
		return true
	case *ast.Var:
		(.Name)
		return true
	case *ast.Prop:
		(.Var)
		return true
	case *ast.Cost:
		(.From)
		(.To)
		return true
	case *ast.Unary:
		return (.Expr, , )
	case *ast.IsNull:
		return (.Expr, , )
	case *ast.Binary:
		return (.LHS, , ) && (.RHS, , )
	case *ast.In:
		return (.Expr, , ) && (.List, , )
	case *ast.ListPred:
		return (.List, , ) && (.Pred, , )
	case *ast.Reduce:
		return (.Init, , ) &&
			(.List, , ) &&
			(.Body, , )
	case *ast.ListComp:
		 := (.List, , )
		if .Filter != nil {
			 = (.Filter, , ) && 
		}
		if .Map != nil {
			 = (.Map, , ) && 
		}
		return 
	case *ast.ListExpr:
		for ,  := range .Elems {
			if !(, , ) {
				return false
			}
		}
		return true
	case *ast.PatternComp:
		// The comprehension's correlation structure isn't modeled here;
		// collect what the filter/proj reference, then report incomplete.
		if .Where != nil {
			(.Where, , )
		}
		(.Proj, , )
		return false
	case *ast.Func:
		for ,  := range .Args {
			if !(, , ) {
				return false
			}
		}
		return true
	case *ast.Case:
		 := true
		if .Operand != nil {
			 = (.Operand, , )
		}
		for ,  := range .Whens {
			 = (.Cond, , ) && 
			 = (.Result, , ) && 
		}
		if .Else != nil {
			 = (.Else, , ) && 
		}
		return 
	case *ast.Index:
		return (.Base, , ) && (.Idx, , )
	case *ast.Slice:
		 := (.Base, , )
		if .From != nil {
			 = (.From, , ) && 
		}
		if .To != nil {
			 = (.To, , ) && 
		}
		return 
	case *ast.PropOf:
		return (.Base, , )
	case *ast.MapProj:
		(.Var)
		for ,  := range .Entries {
			if .Kind == ast.MapProjField && !(.Expr, , ) {
				return false
			}
		}
		return true
	case *ast.MapLit:
		for ,  := range .Fields {
			if !(.Val, , ) {
				return false
			}
		}
		return true
	case *ast.HasLabelExpr:
		(.Var)
		return true
	default:
		// A nested subquery's correlated reads aren't enumerated -> no memo.
		return false
	}
}