package plan

import (
	"fmt"
	"sort"
)

type loopBodyScope struct {
	owner             *Node
	nodes             map[string]bool
	boundaries        map[string][]*Edge
	foreignBoundaries []*Edge
	reachedEnd        bool
}

// loopScopeAnalysis is captured by the loop validation traversal and handed
// to lowering. It is deliberately source-free: edge and node IDs are the
// complete lexical boundary the runtime needs for iteration lineage.
type loopScopeAnalysis struct {
	ownerID        string
	parentLoopID   string
	members        []string
	bodyEntryEdges []string
	continueEdges  []string
	breakEdges     []string
	doneEdges      []string
	failedEdges    []string
}

func (v *validator) validateLoopScopes(outgoing, incoming map[string]map[string][]*Edge) {
	loops := make([]*Node, 0)
	for _, node := range v.nodes {
		if node.Type == NodeLoop && node.Loop != nil {
			loops = append(loops, node)
		}
	}
	if len(loops) == 0 {
		return
	}
	sort.Slice(loops, func(i, j int) bool { return loops[i].ID < loops[j].ID })
	reachable := v.reachableNodes()
	dominators := v.dominators(reachable)
	scopes := map[string]*loopBodyScope{}
	for _, loop := range loops {
		scopes[loop.ID] = v.exploreLoopBody(loop, outgoing)
	}

	nested := v.validateLoopScopeOverlap(loops, scopes, dominators)
	for _, loop := range loops {
		scope := scopes[loop.ID]
		path := fmt.Sprintf("graph.nodes[%d].loop", v.nodeIndexes[loop.ID])
		if !reachable[loop.ID] {
			v.error("loop.unreachable_owner", path, fmt.Sprintf("loop %q is not reachable from entry", loop.ID), loop.ID, "")
		}
		for nodeID := range scope.nodes {
			if !dominators[nodeID][loop.ID] {
				v.error("loop.undominated_body", fmt.Sprintf("graph.nodes[%d]", v.nodeIndexes[nodeID]), fmt.Sprintf("loop %q does not dominate body node %q", loop.ID, nodeID), loop.ID, "")
			}
		}
		if scope.reachedEnd || len(scope.boundaries["continue"]) == 0 {
			v.error("loop.open_body", path, fmt.Sprintf("every body path of loop %q must close at its continue or break boundary", loop.ID), loop.ID, "")
		}
		v.validateLoopBoundaryMembership(loop, scope, incoming, dominators)
		v.validateLoopForeignBoundaries(loop, scope, scopes, nested)
		v.validateLoopExitOverlap(loop, scope, outgoing)
		v.recordLoopScope(loop, scope, loops, nested, outgoing)
	}
}

func (v *validator) recordLoopScope(loop *Node, scope *loopBodyScope, loops []*Node, nested map[string]map[string]bool, outgoing map[string]map[string][]*Edge) {
	snapshot := loopScopeAnalysis{
		ownerID: loop.ID, members: []string{}, bodyEntryEdges: []string{},
		continueEdges: []string{}, breakEdges: []string{}, doneEdges: []string{}, failedEdges: []string{},
	}
	for nodeID := range scope.nodes {
		snapshot.members = append(snapshot.members, nodeID)
	}
	for _, edge := range outgoing[loop.ID]["body"] {
		snapshot.bodyEntryEdges = append(snapshot.bodyEntryEdges, edge.ID)
	}
	for _, edge := range scope.boundaries["continue"] {
		snapshot.continueEdges = append(snapshot.continueEdges, edge.ID)
	}
	for _, edge := range scope.boundaries["break"] {
		snapshot.breakEdges = append(snapshot.breakEdges, edge.ID)
	}
	for _, edge := range outgoing[loop.ID]["done"] {
		snapshot.doneEdges = append(snapshot.doneEdges, edge.ID)
	}
	for _, edge := range outgoing[loop.ID]["failed"] {
		snapshot.failedEdges = append(snapshot.failedEdges, edge.ID)
	}

	// Choose the closest enclosing loop. validateLoopScopeOverlap records every
	// containment pair, so an immediate parent has no middle owner between it
	// and this loop.
	for _, candidate := range loops {
		if candidate.ID == loop.ID || !nested[candidate.ID][loop.ID] {
			continue
		}
		immediate := true
		for _, middle := range loops {
			if middle.ID != candidate.ID && middle.ID != loop.ID && nested[candidate.ID][middle.ID] && nested[middle.ID][loop.ID] {
				immediate = false
				break
			}
		}
		if immediate {
			snapshot.parentLoopID = candidate.ID
			break
		}
	}

	for _, values := range [][]string{snapshot.members, snapshot.bodyEntryEdges, snapshot.continueEdges, snapshot.breakEdges, snapshot.doneEdges, snapshot.failedEdges} {
		sort.Strings(values)
	}
	v.loopScopes = append(v.loopScopes, snapshot)
}

func (v *validator) exploreLoopBody(loop *Node, outgoing map[string]map[string][]*Edge) *loopBodyScope {
	scope := &loopBodyScope{
		owner: loop, nodes: map[string]bool{},
		boundaries: map[string][]*Edge{"continue": {}, "break": {}},
	}
	queue := make([]string, 0)
	process := func(edge *Edge) {
		if edge == nil {
			return
		}
		target := v.nodes[edge.Target.NodeID]
		if target == nil {
			return
		}
		if target.ID == loop.ID && (edge.Target.Port == "continue" || edge.Target.Port == "break") {
			scope.boundaries[edge.Target.Port] = append(scope.boundaries[edge.Target.Port], edge)
			return
		}
		if target.Type == NodeLoop && target.ID != loop.ID && (edge.Target.Port == "continue" || edge.Target.Port == "break") {
			scope.foreignBoundaries = append(scope.foreignBoundaries, edge)
		}
		queue = append(queue, target.ID)
	}
	for _, edge := range outgoing[loop.ID]["body"] {
		process(edge)
	}
	for len(queue) != 0 {
		current := queue[0]
		queue = queue[1:]
		if scope.nodes[current] {
			continue
		}
		scope.nodes[current] = true
		node := v.nodes[current]
		if node == nil {
			continue
		}
		if node.Type == NodeEnd {
			scope.reachedEnd = true
			continue
		}
		ports := make([]string, 0, len(outgoing[current]))
		for port := range outgoing[current] {
			ports = append(ports, port)
		}
		sort.Strings(ports)
		for _, port := range ports {
			edges := append([]*Edge(nil), outgoing[current][port]...)
			sort.Slice(edges, func(i, j int) bool { return edges[i].ID < edges[j].ID })
			for _, edge := range edges {
				process(edge)
			}
		}
	}
	for port := range scope.boundaries {
		sort.Slice(scope.boundaries[port], func(i, j int) bool {
			return scope.boundaries[port][i].ID < scope.boundaries[port][j].ID
		})
	}
	sort.Slice(scope.foreignBoundaries, func(i, j int) bool {
		return scope.foreignBoundaries[i].ID < scope.foreignBoundaries[j].ID
	})
	return scope
}

func (v *validator) validateLoopBoundaryMembership(loop *Node, scope *loopBodyScope, incoming map[string]map[string][]*Edge, dominators map[string]map[string]bool) {
	discovered := map[string]bool{}
	for _, port := range []string{"continue", "break"} {
		for _, edge := range scope.boundaries[port] {
			discovered[edge.ID] = true
		}
		edges := append([]*Edge(nil), incoming[loop.ID][port]...)
		sort.Slice(edges, func(i, j int) bool { return edges[i].ID < edges[j].ID })
		for _, edge := range edges {
			directBody := edge.Source.NodeID == loop.ID && edge.Source.Port == "body"
			inside := scope.nodes[edge.Source.NodeID] && dominators[edge.Source.NodeID][loop.ID]
			if !discovered[edge.ID] || (!directBody && !inside) {
				v.error("loop.outside_boundary", fmt.Sprintf("graph.edges[%d]", v.edgeIndexes[edge.ID]), fmt.Sprintf("edge source %q reaches loop %q %s from outside its body scope", edge.Source.NodeID, loop.ID, port), loop.ID, edge.ID)
			}
		}
	}
}

func (v *validator) validateLoopScopeOverlap(loops []*Node, scopes map[string]*loopBodyScope, dominators map[string]map[string]bool) map[string]map[string]bool {
	nested := map[string]map[string]bool{}
	for _, outer := range loops {
		nested[outer.ID] = map[string]bool{}
	}
	for i, left := range loops {
		for _, right := range loops[i+1:] {
			leftScope, rightScope := scopes[left.ID], scopes[right.ID]
			leftContainsRight := leftScope.nodes[right.ID] && setContains(leftScope.nodes, rightScope.nodes) && dominators[right.ID][left.ID]
			rightContainsLeft := rightScope.nodes[left.ID] && setContains(rightScope.nodes, leftScope.nodes) && dominators[left.ID][right.ID]
			switch {
			case leftContainsRight && !rightContainsLeft:
				nested[left.ID][right.ID] = true
			case rightContainsLeft && !leftContainsRight:
				nested[right.ID][left.ID] = true
			case setsOverlap(leftScope.nodes, rightScope.nodes):
				v.error("loop.scope_overlap", "graph.nodes", fmt.Sprintf("loop scopes %q and %q overlap without valid nesting", left.ID, right.ID), left.ID, "")
			}
		}
	}
	return nested
}

func (v *validator) validateLoopForeignBoundaries(loop *Node, scope *loopBodyScope, scopes map[string]*loopBodyScope, nested map[string]map[string]bool) {
	for _, edge := range scope.foreignBoundaries {
		targetLoop := v.nodes[edge.Target.NodeID]
		if targetLoop == nil {
			continue
		}
		allowedNested := nested[loop.ID][targetLoop.ID]
		targetScope := scopes[targetLoop.ID]
		sourceInsideNested := targetScope != nil && (targetScope.nodes[edge.Source.NodeID] || edge.Source.NodeID == targetLoop.ID && edge.Source.Port == "body")
		if !allowedNested || !sourceInsideNested {
			v.error("loop.cross_loop_boundary", fmt.Sprintf("graph.edges[%d]", v.edgeIndexes[edge.ID]), fmt.Sprintf("loop %q body crosses %q boundary of loop %q", loop.ID, edge.Target.Port, targetLoop.ID), loop.ID, edge.ID)
		}
	}
}

func (v *validator) validateLoopExitOverlap(loop *Node, scope *loopBodyScope, outgoing map[string]map[string][]*Edge) {
	exitNodes := map[string]bool{}
	queue := make([]string, 0)
	for _, port := range []string{"done", "failed"} {
		for _, edge := range outgoing[loop.ID][port] {
			if v.isLoopBodyBoundary(edge) {
				continue
			}
			queue = append(queue, edge.Target.NodeID)
		}
	}
	for len(queue) != 0 {
		current := queue[0]
		queue = queue[1:]
		if exitNodes[current] {
			continue
		}
		exitNodes[current] = true
		for _, edges := range outgoing[current] {
			for _, edge := range edges {
				if v.isLoopBodyBoundary(edge) {
					continue
				}
				queue = append(queue, edge.Target.NodeID)
			}
		}
	}
	overlaps := make([]string, 0)
	for nodeID := range scope.nodes {
		if exitNodes[nodeID] {
			overlaps = append(overlaps, nodeID)
		}
	}
	sort.Strings(overlaps)
	if len(overlaps) != 0 {
		v.error("loop.body_exit_overlap", fmt.Sprintf("graph.nodes[%d].loop", v.nodeIndexes[loop.ID]), fmt.Sprintf("loop %q body overlaps its done/failed continuation at nodes %v", loop.ID, overlaps), loop.ID, "")
	}
}

// A loop continuation is a lexical control boundary. Following an inner
// loop's done/failed path across an enclosing continue/break would make that
// enclosing body look like part of the inner loop's exit continuation.
func (v *validator) isLoopBodyBoundary(edge *Edge) bool {
	if edge == nil {
		return false
	}
	target := v.nodes[edge.Target.NodeID]
	return target != nil && target.Type == NodeLoop &&
		(edge.Target.Port == "continue" || edge.Target.Port == "break")
}

func setContains(outer, inner map[string]bool) bool {
	for value := range inner {
		if !outer[value] {
			return false
		}
	}
	return true
}

func setsOverlap(left, right map[string]bool) bool {
	for value := range left {
		if right[value] {
			return true
		}
	}
	return false
}