// Heuristic forward cardinality estimates for EXPLAIN/PROFILE (port of
// the Rust estimate.rs): one estimated output row-count per operator,
// propagated from the anchor's exact leaf cardinality through each
// expand's average fan-out, plus the reconstructed [anchor: ...] note for
// each anchored MATCH stage. Estimates describe the shape of cardinality
// growth, not a guarantee; they render unconditionally here (the planner
// is always cost-based).
package plan

import (
	
	

	
	
	
)

// whereSel is the flat selectivity applied per stage WHERE (a predicate
// keeps ~half the rows).
const whereSel = 0.5

// untypedFanout is the fan-out assumed for an untyped expand.
const untypedFanout = 3.0

// unwindFanout is the rows assumed per FOR over a list of unseen length.
const unwindFanout = 4.0

// Estimates holds per-segment estimates in branch-major order.
type Estimates struct {
	Segs []SegEst
}

// SegEst estimates one segment; mirrors the profiler's segment shape so
// the renderer can zip them.
type SegEst struct {
	Stages []StageEst
	// ProjRows is the estimated rows after projection; nil when aggregated
	// (group count not estimated).
	ProjRows *uint64
	// PostWhereRows is the estimated rows after a boundary WHERE, if any.
	PostWhereRows *uint64
	// AnchorNotes has one entry per stage: the [anchor: ...] note for a
	// stage that made a cost anchor choice, else "".
	AnchorNotes []string
}

// StageEst estimates one stage: Match holds one estimate per op plus a
// trailing one for the stage WHERE; Single is a one-output stage.
type StageEst struct {
	Match  []uint64
	Single *uint64
}

// rnd rounds a possibly-infinite float estimate to a row count, saturating.
func rnd( float64) uint64 {
	if math.IsNaN() ||  < 0 {
		return 0
	}
	if math.IsInf(, 1) ||  >= float64(math.MaxUint64) {
		return math.MaxUint64
	}
	return uint64(math.Round())
}

// Estimate computes every segment's estimates for a planned query.
func ( *Plan,  graph.Graph) *Estimates {
	 := &Estimates{}
	for ,  := range .Branches {
		for ,  := range  {
			.Segs = append(.Segs, segEst(, ))
		}
	}
	return 
}

func segEst( *Segment,  graph.Graph) SegEst {
	 := stageNames()
	 := 1.0 // one seed row enters the first stage
	 := make([]StageEst, 0, len(.Stages))
	 := make([]string, 0, len(.Stages))
	for ,  := range .Stages {
		switch s := .(type) {
		case *MatchStage:
			,  := matchEst(, , )
			 = 
			 = append(, StageEst{Match: })
			 = append(, anchorNote(, , ))
		case *UnwindStage:
			 *= unwindFanout
			 := rnd()
			 = append(, StageEst{Single: &})
			 = append(, "")
		case *HashJoinStage:
			// Probe hits per row bounded by both the probe expansion's
			// fan-out and the built branch's size; the moved cross-branch
			// conjuncts filter like a stage WHERE.
			 := 1.0
			for ,  := range .Build {
				_,  = matchEst(, , )
			}
			 *= math.Min(fanout(.Probe.Types, .Probe.Dir, ), math.Max(, 1))
			if .Where != nil {
				 *= whereSel
			}
			 := rnd()
			 = append(, StageEst{Single: &})
			 = append(, "")
		default:
			// Shortest path, CALL, CALL subquery: no cardinality model --
			// carry the running estimate.
			 := rnd()
			 = append(, StageEst{Single: &})
			 = append(, "")
		}
	}
	 := SegEst{Stages: , AnchorNotes: }
	.ProjRows = projEst(&.Proj, )
	if .PostWhere != nil && .ProjRows != nil {
		 := rnd(float64(*.ProjRows) * whereSel)
		.PostWhereRows = &
	}
	return 
}

// projEst is the estimated rows after a segment's projection; nil when
// aggregated, otherwise the row count clamped by LIMIT.
func projEst( *ProjPlan,  float64) *uint64 {
	if .Aggregated {
		return nil
	}
	 := 
	if .Limit != nil {
		 = math.Min(, float64(*.Limit))
	}
	 := rnd()
	return &
}

// matchEst estimates each operator of a MATCH stage, threading the running
// row count; returns the per-op estimates (plus a trailing one for the
// stage WHERE) and the rows leaving the stage.
func matchEst( *MatchStage,  float64,  graph.Graph) ([]uint64, float64) {
	return matchEstAnchored(, , , nil)
}

// matchEstAnchored is matchEst with cross-stage anchor resolution: an
// expand whose From slot was proven at plan time to hold exactly one
// concrete node prices that hop at the node's REAL degree instead of the
// type average -- fact over an immutable snapshot, immune to
// average-degree lies in either direction (a hub anchor on a sparse
// type, a sparse anchor on a hub-heavy type). Parameter seeks never
// resolve: a cached template plan must not embed one parameter value's
// degree.
func matchEstAnchored( *MatchStage,  float64,  graph.Graph,  map[int]graph.NodeID) ([]uint64, float64) {
	 := 
	 := make([]uint64, 0, len(.Ops)+1)
	// The anchor's first hop fans out by the anchor's RESOLVED local
	// degree (the hub-aware signal), not the global average; later hops
	// fall back to avg_degree -- except a hop from a resolved single-node
	// slot, which prices exactly.
	,  := anchorFirstHopDegree(, )
	for  := range .Ops {
		var  *float64
		if  == 1 &&  {
			 = &
		} else if  != nil {
			 := &.Ops[]
			if .Kind == OpExpand || .Kind == OpVarExpand {
				if ,  := [.From];  {
					 := resolvedDegree([]graph.NodeID{}, true, .Types, .Dir, )
					 := float64(.val)
					 = &
				}
			}
		}
		 = opEst(&.Ops[], , , )
		 = append(, rnd())
	}
	if .Where != nil {
		 *= whereSel
		 = append(, rnd())
	}
	return , 
}

// anchorFirstHopDegree is the anchor's resolved first-hop degree (exact,
// when the anchor is a concrete seek with a hop).
func anchorFirstHopDegree( *MatchStage,  graph.Graph) (float64, bool) {
	if len(.Ops) < 2 || .Ops[0].Kind != OpScan {
		return 0, false
	}
	 := &.Ops[0]
	 := &.Ops[1]
	if .Kind != OpExpand && .Kind != OpVarExpand {
		return 0, false
	}
	,  := resolveScanNodes(&.Source, .Labels, .Props, )
	if ! || len() == 0 {
		return 0, false
	}
	 := resolvedDegree(, true, .Types, .Dir, )
	return float64(.val), true
}

// opEst applies one operator to the running row estimate; firstHopDeg
// overrides the hop's average fan-out with the anchor's resolved degree.
func opEst( *BindOp,  float64,  *float64,  graph.Graph) float64 {
	switch .Kind {
	case OpScan:
		return  * float64(scanCard(&.Source, .Props, ))
	case OpExpand:
		 := targetPop(.Labels, )
		 := fanout(.Types, .Dir, )
		if  != nil {
			 = *
		}
		if .Rebind {
			// Joining into a bound node: an existence check, output <=
			// input, scaled by the chance a matching rel exists.
			return  * math.Min(/math.Max(, 1), 1)
		}
		return  * 
	default: // OpVarExpand
		 := fanout(.Types, .Dir, )
		if  != nil {
			 = *
		}
		 := targetPop(.Labels, )
		var  float64
		if .Max != nil {
			// Bounded trail: sum the per-hop path counts d^min .. d^max.
			 := 0.0
			for  := .Min;  <= *.Max; ++ {
				 += math.Pow(, float64())
			}
			 =  * 
		} else {
			// Unbounded reachable set ~ the whole target population.
			 = 
		}
		if .DedupEndpoints || .Max == nil {
			return math.Min(, math.Max(, 1))
		}
		return 
	}
}

// scanCard is the exact leaf cardinality of a scan source (the same
// quantity the planner's anchorCard uses).
func scanCard( *ScanSource,  []ast.PropEntry,  graph.Graph) uint64 {
	switch .Kind {
	case ScanProperty:
		if isConcrete(.Value) {
			return seekCard(, .Label, .Key, semantics.LitValue(.Value))
		}
		return .LabelCardinality(.Label)
	case ScanLabel:
		// A label scan with extra concrete inline props narrows;
		// approximate that filter.
		 := float64(.LabelCardinality(.Label))
		return rnd( * propSel())
	case ScanTextMatch:
		return .LabelCardinality(.Label)
	case ScanExistsSeed:
		// Estimate as the base label scan so join ordering is unchanged
		// by the seeding -- the narrowing is purely an execution-time
		// candidate source (like ScanTextMatch's contract).
		if .Label != "" {
			return .LabelCardinality(.Label)
		}
		return uint64(.NodeCount())
	case ScanNodeID, ScanNodeIDVar, ScanArg:
		return 1
	default: // ScanAll
		return uint64(.NodeCount())
	}
}

// fanout is the combined average fan-out for a hop over types in dir.
func fanout( []string,  graph.Direction,  graph.Graph) float64 {
	if len() == 0 {
		return untypedFanout
	}
	 := 0.0
	for ,  := range  {
		 += .AvgDegree(, )
	}
	return 
}

// targetPop is the population of the target label (or all nodes).
func targetPop( []string,  graph.Graph) float64 {
	if len() > 0 {
		return float64(.LabelCardinality([0]))
	}
	return float64(.NodeCount())
}

// propSel is the selectivity of concrete inline props beyond the scan key.
func propSel( []ast.PropEntry) float64 {
	 := 0
	for  := range  {
		if isConcrete([].Val) {
			++
		}
	}
	return math.Max(math.Pow(0.1, float64()), math.SmallestNonzeroFloat64)
}

func isConcrete( ast.Literal) bool {
	return .Kind != ast.LitParam && .Kind != ast.LitNamedParam && .Kind != ast.LitNull
}

// stageNames is the slot -> variable-name map for a segment.
func stageNames( *Segment) []string {
	 := make([]string, .RowWidth)
	for ,  := range .Slots {
		if  < len() {
			[] = 
		}
	}
	return 
}

// anchorNote reconstructs the [anchor: ...] note for a MATCH stage whose
// anchor was a real choice between two endpoints: each end's exact leaf
// cardinality and resolved first-hop degree (the hub-aware signal), and
// the inferred decision rung. "" when there is no two-endpoint choice.
func anchorNote( *MatchStage,  []string,  graph.Graph) string {
	if len(.Ops) < 2 || .Ops[0].Kind != OpScan {
		return ""
	}
	 := &.Ops[0]
	if .Source.Kind == ScanArg {
		return "" // anchor was forced (carried-in), not chosen
	}
	 := &.Ops[1]
	if .Kind != OpExpand && .Kind != OpVarExpand {
		return ""
	}
	 := &.Ops[len(.Ops)-1]
	if .Kind != OpExpand && .Kind != OpVarExpand {
		return ""
	}

	 := scanCard(&.Source, .Props, )
	,  := resolveScanNodes(&.Source, .Labels, .Props, )
	 := resolvedDegree(, , .Types, .Dir, )
	 := nodeCard(.Labels, .Props, )
	,  := resolveByProps(.Labels, .Props, )
	 := resolvedDegree(, , .Types, revDir(.Dir), )

	 := endpointDesc(.Slot, , .Labels, .Props)
	 := endpointDesc(.To, , .Labels, .Props)
	var  string
	switch {
	case  < :
		 = "smaller leaf cardinality"
	case  ==  && .val < .val:
		 = "smaller first-hop degree (hub-aware)"
	case  ==  && .val == .val:
		 = "avg-degree tie-break"
	default:
		 = "selectivity tier"
	}
	return fmt.Sprintf("[anchor: %s card=%d, fan-out %s · vs %s card=%d, fan-out %s → %s]",
		, , .render(), , , .render(), )
}

// degree is a first-hop fan-out: exact when the endpoint resolved to
// concrete nodes, else an avg_degree estimate.
type degree struct {
	val   uint64
	exact bool
}

func ( degree) () string {
	if .exact {
		return GroupDigits(.val)
	}
	return "~" + GroupDigits(.val)
}

// resolvedDegree sums the resolved nodes' real degree over types/dir; with
// no resolvable node, falls back to the average degree of the hop type.
func resolvedDegree( []graph.NodeID,  bool,  []string,  graph.Direction,  graph.Graph) degree {
	if ! {
		return degree{val: rnd(fanout(, , ))}
	}
	var  uint64
	for ,  := range  {
		 += countNeighbors(, , , )
	}
	return degree{val: , exact: true}
}

// resolveScanNodes pins a scan's concrete seek to node ids, for an exact
// degree read; ok=false for label-only/text/all sources.
func resolveScanNodes( *ScanSource,  []string,  []ast.PropEntry,  graph.Graph) ([]graph.NodeID, bool) {
	switch .Kind {
	case ScanProperty:
		if isConcrete(.Value) {
			return seekNodes(, .Label, .Key, semantics.LitValue(.Value)), true
		}
		return nil, false
	case ScanLabel:
		return resolveByProps(, , )
	}
	return nil, false
}

// resolveByProps resolves a node from its label plus a concrete inline
// property; ok=false when it has none.
func resolveByProps( []string,  []ast.PropEntry,  graph.Graph) ([]graph.NodeID, bool) {
	if len() == 0 {
		return nil, false
	}
	for  := range  {
		if isConcrete([].Val) {
			return seekNodes(, [0], [].Key, semantics.LitValue([].Val)), true
		}
	}
	return nil, false
}

// nodeCard is the leaf cardinality of a node given only labels + props
// (the rejected endpoint, which has no ScanSource).
func nodeCard( []string,  []ast.PropEntry,  graph.Graph) uint64 {
	if len() == 0 {
		return uint64(.NodeCount())
	}
	for  := range  {
		if isConcrete([].Val) {
			return seekCard(, [0], [].Key, semantics.LitValue([].Val))
		}
	}
	return .LabelCardinality([0])
}

// endpointDesc renders var:Label {k} for an anchor-note endpoint.
func endpointDesc( int,  []string,  []string,  []ast.PropEntry) string {
	 := ""
	if  >= 0 &&  < len() {
		 = []
	}
	 := ""
	if len() > 0 {
		 = ":" + [0]
	}
	 := ""
	for  := range  {
		if isConcrete([].Val) {
			 = " {" + [].Key + "}"
			break
		}
	}
	return  +  + 
}

func revDir( graph.Direction) graph.Direction {
	switch  {
	case graph.Outgoing:
		return graph.Incoming
	case graph.Incoming:
		return graph.Outgoing
	}
	return graph.Both
}

// GroupDigits renders 2860664 as "2,860,664" (shared with the renderer).
func ( uint64) string {
	 := fmt.Sprintf("%d", )
	 := make([]byte, 0, len()+len()/3)
	for  := range len() {
		if  > 0 && (len()-)%3 == 0 {
			 = append(, ',')
		}
		 = append(, [])
	}
	return string()
}