using Editor.Prism.Core;

namespace Editor.Prism.Model;

/// <summary>
/// Read-only analysis of a document: reachability, topological order, real cycle detection,
/// dependency subtrees and orphan detection.
/// <para>
/// Every traversal here is iterative rather than recursive, so a pathological graph produces a
/// diagnostic instead of a stack overflow, and <b>every traversal includes reroute nodes</b>. The
/// built-in editor exempts reroutes from its cycle check, which is why a reroute loop can hang it;
/// treating every node identically is both simpler and correct.
/// </para>
/// </summary>
public static class GraphQueries
{
	/// <summary>The node a port reference points at. Null when it does not resolve.</summary>
	public static PrismNode NodeOf( IPrismGraph graph, PortRef reference ) => graph?.FindNode( reference.Node );

	/// <summary>Resolve a port reference to a live port.</summary>
	public static bool TryGetPort( IPrismGraph graph, PortRef reference, out Port port )
	{
		port = graph?.FindNode( reference.Node )?.FindPort( reference.Port );
		return port is not null;
	}

	/// <summary>Every edge terminating on a node.</summary>
	public static IEnumerable<Edge> IncomingEdges( IPrismGraph graph, NodeId node )
	{
		if ( graph?.Edges is null ) yield break;

		foreach ( var edge in graph.Edges )
		{
			if ( edge is not null && edge.ToNode == node ) yield return edge;
		}
	}

	/// <summary>Every edge leaving a node.</summary>
	public static IEnumerable<Edge> OutgoingEdges( IPrismGraph graph, NodeId node )
	{
		if ( graph?.Edges is null ) yield break;

		foreach ( var edge in graph.Edges )
		{
			if ( edge is not null && edge.FromNode == node ) yield return edge;
		}
	}

	/// <summary>Every node that directly feeds this one.</summary>
	public static IEnumerable<NodeId> Predecessors( IPrismGraph graph, NodeId node ) =>
		IncomingEdges( graph, node ).Select( x => x.FromNode ).Distinct();

	/// <summary>Every node this one directly feeds.</summary>
	public static IEnumerable<NodeId> Successors( IPrismGraph graph, NodeId node ) =>
		OutgoingEdges( graph, node ).Select( x => x.ToNode ).Distinct();

	/// <summary>
	/// The nodes a compile starts from: registered output nodes when there are any, otherwise every
	/// node with no outgoing edge. The fallback is what makes a half-built graph still previewable.
	/// </summary>
	public static IReadOnlyList<NodeId> OutputNodes( IPrismGraph graph )
	{
		if ( graph?.Nodes is null ) return Array.Empty<NodeId>();

		var outputs = new List<NodeId>();

		foreach ( var node in graph.Nodes )
		{
			if ( node is null ) continue;
			if ( !IsOutputNode( node ) ) continue;

			outputs.Add( node.Id );
		}

		if ( outputs.Count > 0 ) return outputs;

		return TerminalNodes( graph );
	}

	/// <summary>True when a node looks like a graph terminal: an output-category node with no outputs.</summary>
	public static bool IsOutputNode( PrismNode node )
	{
		if ( node is null ) return false;
		if ( node.Outputs.Count > 0 ) return false;

		var id = node.Descriptor?.Id;

		if ( !string.IsNullOrEmpty( id ) && id.StartsWith( "prism.output.", StringComparison.OrdinalIgnoreCase ) )
		{
			return true;
		}

		var category = node.Descriptor?.Category;

		return !string.IsNullOrEmpty( category ) &&
			category.StartsWith( "Output", StringComparison.OrdinalIgnoreCase );
	}

	/// <summary>Every node with no outgoing edge.</summary>
	public static IReadOnlyList<NodeId> TerminalNodes( IPrismGraph graph )
	{
		if ( graph?.Nodes is null ) return Array.Empty<NodeId>();

		var hasOutgoing = new HashSet<NodeId>();

		foreach ( var edge in graph.Edges ?? Array.Empty<Edge>() )
		{
			if ( edge is not null ) hasOutgoing.Add( edge.FromNode );
		}

		var result = new List<NodeId>();

		foreach ( var node in graph.Nodes )
		{
			if ( node is null || hasOutgoing.Contains( node.Id ) ) continue;

			result.Add( node.Id );
		}

		return result;
	}

	/// <summary>
	/// Every node reachable by walking <em>backwards</em> from the given roots — that is, everything
	/// that contributes to the roots' values. Disabled nodes stop the walk, because a disabled node
	/// falls back to inline values and its inputs are not evaluated.
	/// </summary>
	public static IReadOnlyCollection<NodeId> Reachable( IPrismGraph graph, IEnumerable<NodeId> roots,
		bool stopAtDisabled = true )
	{
		var visited = new HashSet<NodeId>();

		if ( graph is null || roots is null ) return visited;

		var stack = new Stack<NodeId>();

		foreach ( var root in roots )
		{
			if ( root.IsValid && visited.Add( root ) ) stack.Push( root );
		}

		var incoming = BuildIncomingMap( graph );

		while ( stack.Count > 0 )
		{
			var current = stack.Pop();

			if ( stopAtDisabled && IsDisabled( graph, current ) ) continue;
			if ( !incoming.TryGetValue( current, out var sources ) ) continue;

			foreach ( var source in sources )
			{
				if ( visited.Add( source ) ) stack.Push( source );
			}
		}

		return visited;
	}

	/// <summary>Every node reachable backwards from the graph's output nodes.</summary>
	public static IReadOnlyCollection<NodeId> ReachableFromOutputs( IPrismGraph graph ) =>
		Reachable( graph, OutputNodes( graph ) );

	/// <summary>
	/// Nodes that contribute to nothing: not reachable backwards from any output and not an output
	/// themselves. Purely informational — an orphan is a perfectly legal work in progress.
	/// </summary>
	public static IReadOnlyList<NodeId> Orphans( IPrismGraph graph, IEnumerable<NodeId> roots = null )
	{
		if ( graph?.Nodes is null ) return Array.Empty<NodeId>();

		var reachable = Reachable( graph, roots ?? OutputNodes( graph ), false );
		var result = new List<NodeId>();

		foreach ( var node in graph.Nodes )
		{
			if ( node is null || reachable.Contains( node.Id ) ) continue;

			result.Add( node.Id );
		}

		return result;
	}

	/// <summary>
	/// Every node the given node depends on, including itself, in dependency-first order. This is the
	/// subtree a "compile just this node" preview needs.
	/// </summary>
	public static IReadOnlyList<NodeId> DependencySubtree( IPrismGraph graph, NodeId node )
	{
		var subtree = Reachable( graph, new[] { node }, false );

		return TopologicalOrder( graph, new[] { node } ).Where( subtree.Contains ).ToArray();
	}

	/// <summary>Every node that depends, directly or transitively, on the given node.</summary>
	public static IReadOnlyList<NodeId> Dependents( IPrismGraph graph, NodeId node )
	{
		var visited = new HashSet<NodeId>();

		if ( graph is null || !node.IsValid ) return Array.Empty<NodeId>();

		var outgoing = BuildOutgoingMap( graph );
		var stack = new Stack<NodeId>();
		stack.Push( node );

		while ( stack.Count > 0 )
		{
			var current = stack.Pop();

			if ( !outgoing.TryGetValue( current, out var targets ) ) continue;

			foreach ( var target in targets )
			{
				if ( visited.Add( target ) ) stack.Push( target );
			}
		}

		return visited.ToArray();
	}

	/// <summary>
	/// Dependency-first order over the nodes reachable from <paramref name="roots"/>, or over the whole
	/// document when roots are omitted. Nodes involved in a cycle are appended at the end rather than
	/// dropped, so a cyclic graph still produces a usable ordering for the UI.
	/// </summary>
	public static IReadOnlyList<NodeId> TopologicalOrder( IPrismGraph graph, IEnumerable<NodeId> roots = null )
	{
		if ( graph?.Nodes is null ) return Array.Empty<NodeId>();

		var scope = roots is null
			? new HashSet<NodeId>( graph.Nodes.Where( x => x is not null ).Select( x => x.Id ) )
			: new HashSet<NodeId>( Reachable( graph, roots, false ) );

		if ( scope.Count == 0 ) return Array.Empty<NodeId>();

		var incoming = BuildIncomingMap( graph );
		var order = new List<NodeId>( scope.Count );
		var state = new Dictionary<NodeId, byte>( scope.Count );

		// Iterative post-order DFS. 0 = unvisited, 1 = on the stack (grey), 2 = emitted (black).
		var work = new Stack<(NodeId Node, int Index)>();

		foreach ( var root in Ordered( graph, scope ) )
		{
			if ( state.TryGetValue( root, out var seen ) && seen == 2 ) continue;

			work.Push( (root, 0) );
			state[root] = 1;

			while ( work.Count > 0 )
			{
				var (node, index) = work.Pop();
				var sources = incoming.TryGetValue( node, out var list ) ? list : s_noIds;

				if ( index < sources.Count )
				{
					work.Push( (node, index + 1) );

					var source = sources[index];

					if ( !scope.Contains( source ) ) continue;

					state.TryGetValue( source, out var sourceState );

					if ( sourceState == 0 )
					{
						state[source] = 1;
						work.Push( (source, 0) );
					}

					continue;
				}

				state[node] = 2;
				order.Add( node );
			}
		}

		// Anything still grey belongs to a cycle: emit it so callers see every node exactly once.
		foreach ( var node in Ordered( graph, scope ) )
		{
			if ( state.TryGetValue( node, out var seen ) && seen == 2 ) continue;

			order.Add( node );
			state[node] = 2;
		}

		return order;
	}

	/// <summary>
	/// Find one cycle, reporting the full path in traversal order. Reroutes participate exactly like
	/// any other node. Returns false when the document is acyclic.
	/// </summary>
	public static bool TryFindCycle( IPrismGraph graph, out IReadOnlyList<NodeId> cycle )
	{
		var cycles = FindCycles( graph, 1 );

		cycle = cycles.Count > 0 ? cycles[0] : Array.Empty<NodeId>();

		return cycles.Count > 0;
	}

	/// <summary>
	/// Find up to <paramref name="limit"/> distinct cycles, each reported as the full node path with
	/// the entry node repeated at the end so the loop reads naturally in a diagnostic.
	/// </summary>
	public static IReadOnlyList<IReadOnlyList<NodeId>> FindCycles( IPrismGraph graph, int limit = 8 )
	{
		var found = new List<IReadOnlyList<NodeId>>();

		if ( graph?.Nodes is null ) return found;

		var outgoing = BuildOutgoingMap( graph );
		var state = new Dictionary<NodeId, byte>();
		var path = new List<NodeId>();
		var onPath = new HashSet<NodeId>();
		var seenCycles = new HashSet<string>();

		foreach ( var start in graph.Nodes.Where( x => x is not null ).Select( x => x.Id ) )
		{
			if ( state.TryGetValue( start, out var seen ) && seen == 2 ) continue;
			if ( found.Count >= limit ) break;

			var work = new Stack<(NodeId Node, int Index)>();
			work.Push( (start, 0) );

			while ( work.Count > 0 )
			{
				var (node, index) = work.Pop();

				if ( index == 0 )
				{
					state[node] = 1;
					path.Add( node );
					onPath.Add( node );
				}

				var targets = outgoing.TryGetValue( node, out var list ) ? list : s_noIds;

				if ( index < targets.Count )
				{
					work.Push( (node, index + 1) );

					var next = targets[index];

					if ( onPath.Contains( next ) )
					{
						var at = path.LastIndexOf( next );

						if ( at >= 0 && found.Count < limit )
						{
							var loop = new List<NodeId>( path.Count - at + 1 );

							for ( int i = at; i < path.Count; i++ )
							{
								loop.Add( path[i] );
							}

							loop.Add( next );

							var key = string.Join( ">", loop.Select( x => x.Value ).OrderBy( x => x, StringComparer.Ordinal ) );

							if ( seenCycles.Add( key ) ) found.Add( loop );
						}

						continue;
					}

					state.TryGetValue( next, out var nextState );

					if ( nextState == 0 ) work.Push( (next, 0) );

					continue;
				}

				state[node] = 2;
				onPath.Remove( node );

				if ( path.Count > 0 && path[^1] == node ) path.RemoveAt( path.Count - 1 );
			}

			path.Clear();
			onPath.Clear();
		}

		return found;
	}

	/// <summary>
	/// Would adding this connection close a loop? Answered without mutating the document, so the plug
	/// setter can refuse a drop before anything changes.
	/// </summary>
	public static bool WouldCreateCycle( IPrismGraph graph, PortRef from, PortRef to )
	{
		if ( graph is null ) return false;
		if ( !from.IsValid || !to.IsValid ) return false;
		if ( from.Node == to.Node ) return true;

		// The new edge runs from.Node -> to.Node. It closes a loop when from.Node is already
		// reachable downstream of to.Node.
		var outgoing = BuildOutgoingMap( graph );
		var visited = new HashSet<NodeId> { to.Node };
		var stack = new Stack<NodeId>();
		stack.Push( to.Node );

		while ( stack.Count > 0 )
		{
			var current = stack.Pop();

			if ( current == from.Node ) return true;
			if ( !outgoing.TryGetValue( current, out var targets ) ) continue;

			foreach ( var target in targets )
			{
				if ( visited.Add( target ) ) stack.Push( target );
			}
		}

		return false;
	}

	/// <summary>
	/// How many nodes of a cycle path are named before the description gives up and counts the rest.
	/// A cycle through a thousand nodes is not more informative than a cycle through twenty, and the
	/// text ends up in a diagnostic detail body, a tooltip and a log line.
	/// </summary>
	public const int MaxDescribedCycleNodes = 24;

	/// <summary>
	/// Render a cycle path as <c>Title #id → Title #id → …</c> for a diagnostic detail body. Long cycles
	/// are elided in the middle: the two ends are what identifies the loop, and the length is stated.
	/// </summary>
	public static string DescribeCycle( IPrismGraph graph, IReadOnlyList<NodeId> cycle )
	{
		if ( cycle is null || cycle.Count == 0 ) return string.Empty;

		string Name( NodeId id )
		{
			var node = graph?.FindNode( id );

			var title = node switch
			{
				UnknownNode unknown => unknown.DisplayTitle,
				null => "<missing>",
				_ => node.Descriptor?.Title ?? node.GetType().Name
			};

			return $"{title} #{id}";
		}

		if ( cycle.Count <= MaxDescribedCycleNodes )
		{
			return string.Join( " → ", cycle.Select( Name ) );
		}

		var head = MaxDescribedCycleNodes / 2;
		var tail = MaxDescribedCycleNodes - head;

		var parts = cycle.Take( head ).Select( Name ).ToList();

		parts.Add( $"… {cycle.Count - MaxDescribedCycleNodes} more …" );
		parts.AddRange( cycle.Skip( cycle.Count - tail ).Select( Name ) );

		return string.Join( " → ", parts );
	}

	/// <summary>
	/// The static checks that do not need the type solver: cycles, dangling edges, missing required
	/// inputs, unresolved parameter references and a missing output node. Never throws; a node whose
	/// <c>OnValidate</c> misbehaves is isolated and reported.
	/// </summary>
	public static IReadOnlyList<Diagnostic> Validate( IPrismGraph graph, DiagnosticSink sink = null )
	{
		var target = sink ?? new DiagnosticSink();

		if ( graph is null ) return target.All;

		foreach ( var cycle in FindCycles( graph ) )
		{
			target.Error( DiagnosticCode.Cycle, "This graph contains a cycle",
				GraphRef.ForNode( cycle.Count > 0 ? cycle[0] : NodeId.None ), DescribeCycle( graph, cycle ) );
		}

		foreach ( var edge in graph.Edges ?? Array.Empty<Edge>() )
		{
			if ( edge is null ) continue;

			if ( graph.FindNode( edge.FromNode ) is null || graph.FindNode( edge.ToNode ) is null )
			{
				target.Error( DiagnosticCode.DanglingEdge, "Connection references a node that does not exist",
					GraphRef.ForEdge( edge.Id ), edge.ToString() );
			}
		}

		foreach ( var node in graph.Nodes ?? Array.Empty<PrismNode>() )
		{
			if ( node is null ) continue;

			foreach ( var input in node.Inputs )
			{
				if ( !input.Required ) continue;
				if ( input.IsConnected ) continue;
				if ( input.InlineValue is not null ) continue;

				target.Error( DiagnosticCode.MissingInput,
					$"'{input.DisplayName}' is required and has nothing connected",
					GraphRef.ForPort( node.Id, input.Id ) );
			}

			var scoped = target.Scoped( GraphRef.ForNode( node.Id ) );

			PrismLog.Try( $"Validate node {node.Id}",
				() => node.OnValidate( new ValidationContext( node, graph, scoped ) ),
				target, DiagnosticCode.NodeEmitFailed, GraphRef.ForNode( node.Id ) );
		}

		if ( OutputNodes( graph ).Count == 0 )
		{
			target.Error( DiagnosticCode.NoOutput, "This graph has no output node" );
		}

		return target.All;
	}

	static bool IsDisabled( IPrismGraph graph, NodeId id ) =>
		graph?.FindNode( id ) is { } node && ( node.Flags & NodeFlags.Disabled ) != 0;

	static IEnumerable<NodeId> Ordered( IPrismGraph graph, HashSet<NodeId> scope )
	{
		// Iterate in document order so the result is stable between runs, which is what makes
		// regenerated shader text byte-identical for an unchanged graph.
		foreach ( var node in graph.Nodes ?? Array.Empty<PrismNode>() )
		{
			if ( node is null || !scope.Contains( node.Id ) ) continue;

			yield return node.Id;
		}
	}

	static Dictionary<NodeId, List<NodeId>> BuildIncomingMap( IPrismGraph graph )
	{
		var map = new Dictionary<NodeId, List<NodeId>>();

		foreach ( var edge in graph.Edges ?? Array.Empty<Edge>() )
		{
			if ( edge is null ) continue;

			if ( !map.TryGetValue( edge.ToNode, out var list ) )
			{
				list = new List<NodeId>();
				map[edge.ToNode] = list;
			}

			if ( !list.Contains( edge.FromNode ) ) list.Add( edge.FromNode );
		}

		return map;
	}

	static Dictionary<NodeId, List<NodeId>> BuildOutgoingMap( IPrismGraph graph )
	{
		var map = new Dictionary<NodeId, List<NodeId>>();

		foreach ( var edge in graph.Edges ?? Array.Empty<Edge>() )
		{
			if ( edge is null ) continue;

			if ( !map.TryGetValue( edge.FromNode, out var list ) )
			{
				list = new List<NodeId>();
				map[edge.FromNode] = list;
			}

			if ( !list.Contains( edge.ToNode ) ) list.Add( edge.ToNode );
		}

		return map;
	}

	static readonly List<NodeId> s_noIds = new();
}