using w4c_workflows.Models.Nodes;

namespace w4c_workflows.Services.Nodes;

/// <summary>
/// Loop support for the node graph. An edge that closes a cycle is a
/// <b>loop-back</b> edge: it must target a node whose blueprint declares
/// <see cref="NodeBlueprint.LoopBack"/> (currently <c>core.splitInBatches</c>),
/// and at run time it re-triggers that node for the next iteration instead of
/// counting toward its readiness.
///
/// Classification is derived from the edge set, not from traversal order: an edge
/// <c>u → v</c> is a loop-back exactly when it lies on a cycle (the target
/// <c>v</c> can reach <c>u</c>) and <c>v</c> is loop-capable. This is
/// order-independent, so the compiler and a rebuilt persisted graph always agree
/// regardless of task declaration order.
/// </summary>
public static class NodeGraphLinks
{
    /// <summary>
    /// Returns the edges with <see cref="NodeGraphEdge.IsLoopBack"/> set, or an
    /// error when a cycle does not pass through a loop-capable node.
    /// </summary>
    public static (List<NodeGraphEdge> Edges, string? Error) MarkLoopBackEdges(
        IReadOnlyList<NodeGraphNode> nodes, IReadOnlyList<NodeGraphEdge> edges)
    {
        var byId = nodes.ToDictionary(n => n.Id, StringComparer.Ordinal);

        var adjacency = new Dictionary<string, List<string>>(StringComparer.Ordinal);
        foreach (var edge in edges)
        {
            if (!adjacency.TryGetValue(edge.FromNodeId, out var outgoing))
                adjacency[edge.FromNodeId] = outgoing = new List<string>();
            outgoing.Add(edge.ToNodeId);
        }

        // reach[v] = every node reachable from v via one or more edges. Edge u→v
        // closes a cycle iff u is reachable from v.
        var reach = new Dictionary<string, HashSet<string>>(StringComparer.Ordinal);
        foreach (var node in nodes)
        {
            var seen = new HashSet<string>(StringComparer.Ordinal);
            var stack = new Stack<string>();
            stack.Push(node.Id);
            while (stack.Count > 0)
            {
                var current = stack.Pop();
                if (!adjacency.TryGetValue(current, out var next))
                    continue;
                foreach (var target in next)
                {
                    if (seen.Add(target))
                        stack.Push(target);
                }
            }
            reach[node.Id] = seen;
        }

        bool ClosesCycle(NodeGraphEdge edge)
            => reach.TryGetValue(edge.ToNodeId, out var fromTarget)
               && fromTarget.Contains(edge.FromNodeId);

        var marked = new List<NodeGraphEdge>(edges.Count);
        foreach (var edge in edges)
        {
            var isLoopBack = ClosesCycle(edge) && byId[edge.ToNodeId].Blueprint.LoopBack;
            marked.Add(edge with { IsLoopBack = isLoopBack });
        }

        // A cycle is only valid when it re-enters a loop-capable node. Group the
        // mutually-reachable nodes into SCCs and require a loop node in every
        // cyclic component; otherwise the graph would deadlock or spin.
        var error = ValidateCyclesHaveLoopNodes(nodes, adjacency, reach, byId);
        return (marked, error);
    }

    private static string? ValidateCyclesHaveLoopNodes(
        IReadOnlyList<NodeGraphNode> nodes,
        IReadOnlyDictionary<string, List<string>> adjacency,
        IReadOnlyDictionary<string, HashSet<string>> reach,
        IReadOnlyDictionary<string, NodeGraphNode> byId)
    {
        var ids = nodes.Select(n => n.Id).ToList();
        var assigned = new HashSet<string>(StringComparer.Ordinal);

        foreach (var id in ids)
        {
            if (!assigned.Add(id))
                continue;

            var members = new List<string> { id };
            foreach (var other in ids)
            {
                if (other == id || assigned.Contains(other))
                    continue;
                if (reach[id].Contains(other) && reach[other].Contains(id))
                {
                    members.Add(other);
                    assigned.Add(other);
                }
            }

            var isCyclic = members.Count > 1
                || adjacency.TryGetValue(id, out var self) && self.Contains(id);
            if (!isCyclic)
                continue;

            if (members.Any(m => byId[m].Blueprint.LoopBack))
                continue;

            return $"a cycle involving {string.Join(", ", members)} is not allowed: " +
                   "none of these nodes is a loop node (e.g. core.splitInBatches)";
        }

        return null;
    }
}