| | | 1 | | using System.Reflection; |
| | | 2 | | |
| | | 3 | | namespace Elsa.Common.Helpers; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// Sorts tasks based on their dependencies using topological ordering. |
| | | 7 | | /// </summary> |
| | | 8 | | public static class TopologicalTaskSorter |
| | | 9 | | { |
| | | 10 | | /// <summary> |
| | | 11 | | /// Sorts tasks in topological order based on their TaskDependencyAttribute declarations. |
| | | 12 | | /// </summary> |
| | | 13 | | /// <param name="tasks">The tasks to sort.</param> |
| | | 14 | | /// <typeparam name="T">The task type.</typeparam> |
| | | 15 | | /// <returns>A list of tasks sorted in dependency order.</returns> |
| | | 16 | | /// <exception cref="InvalidOperationException">Thrown when a circular dependency is detected.</exception> |
| | | 17 | | public static IReadOnlyList<T> Sort<T>(IEnumerable<T> tasks) where T : ITask |
| | | 18 | | { |
| | 29 | 19 | | var taskList = tasks.ToList(); |
| | 212 | 20 | | var taskTypes = taskList.Select(t => t.GetType()).ToList(); |
| | 29 | 21 | | var dependencyGraph = BuildDependencyGraph(taskTypes); |
| | 29 | 22 | | var sortedTypes = TopologicalSort(dependencyGraph); |
| | | 23 | | |
| | | 24 | | // Map sorted types back to original task instances, preserving multiples |
| | 511 | 25 | | var taskGroups = taskList.GroupBy(t => t.GetType()).ToDictionary(g => g.Key, g => g.ToList()); |
| | 27 | 26 | | var result = new List<T>(); |
| | | 27 | | |
| | 358 | 28 | | foreach (var type in sortedTypes.Where(taskGroups.ContainsKey)) |
| | | 29 | | { |
| | 152 | 30 | | var group = taskGroups[type]; |
| | 152 | 31 | | result.AddRange(group); |
| | | 32 | | } |
| | | 33 | | |
| | 27 | 34 | | return result; |
| | | 35 | | } |
| | | 36 | | |
| | | 37 | | private static Dictionary<Type, List<Type>> BuildDependencyGraph(IEnumerable<Type> taskTypes) |
| | | 38 | | { |
| | 29 | 39 | | var graph = new Dictionary<Type, List<Type>>(); |
| | | 40 | | |
| | 424 | 41 | | foreach (var taskType in taskTypes) |
| | | 42 | | { |
| | 183 | 43 | | if (!graph.ContainsKey(taskType)) |
| | 155 | 44 | | graph[taskType] = new(); |
| | | 45 | | |
| | 183 | 46 | | var dependencies = taskType.GetCustomAttributes<TaskDependencyAttribute>() |
| | 23 | 47 | | .Select(attr => attr.DependencyTaskType) |
| | 183 | 48 | | .ToList(); |
| | | 49 | | |
| | 183 | 50 | | graph[taskType].AddRange(dependencies); |
| | | 51 | | } |
| | | 52 | | |
| | 29 | 53 | | return graph; |
| | | 54 | | } |
| | | 55 | | |
| | | 56 | | private static List<Type> TopologicalSort(Dictionary<Type, List<Type>> graph) |
| | | 57 | | { |
| | 29 | 58 | | var sorted = new List<Type>(); |
| | 29 | 59 | | var visited = new HashSet<Type>(); |
| | 29 | 60 | | var visiting = new HashSet<Type>(); |
| | | 61 | | |
| | 364 | 62 | | foreach (var node in graph.Keys) |
| | | 63 | | { |
| | 154 | 64 | | if (!visited.Contains(node)) |
| | 147 | 65 | | Visit(node, graph, visited, visiting, sorted); |
| | | 66 | | } |
| | | 67 | | |
| | 27 | 68 | | return sorted; |
| | | 69 | | } |
| | | 70 | | |
| | | 71 | | private static void Visit(Type node, Dictionary<Type, List<Type>> graph, HashSet<Type> visited, HashSet<Type> visiti |
| | | 72 | | { |
| | 170 | 73 | | if (visiting.Contains(node)) |
| | 2 | 74 | | throw new InvalidOperationException($"Circular dependency detected involving task type: {node.Name}"); |
| | | 75 | | |
| | 168 | 76 | | if (visited.Contains(node)) |
| | 13 | 77 | | return; |
| | | 78 | | |
| | 155 | 79 | | visiting.Add(node); |
| | | 80 | | |
| | 155 | 81 | | if (graph.TryGetValue(node, out var dependencies)) |
| | | 82 | | { |
| | 353 | 83 | | foreach (var dependency in dependencies) |
| | | 84 | | { |
| | 23 | 85 | | Visit(dependency, graph, visited, visiting, sorted); |
| | | 86 | | } |
| | | 87 | | } |
| | | 88 | | |
| | 152 | 89 | | visiting.Remove(node); |
| | 152 | 90 | | visited.Add(node); |
| | 152 | 91 | | sorted.Add(node); |
| | 152 | 92 | | } |
| | | 93 | | } |