Forge
search
csharpdeeb25a2
1#nullable enable
2using CascadeIDE.Cockpit.Graph;
3using CascadeIDE.Models;
4
5namespace CascadeIDE.Features.WorkspaceNavigation.Application;
6
7/// <summary>Сжатие control-flow subgraph на карте (ADR 0053): glance и перегруженный multibranch в normal.</summary>
8internal static class CodeNavigationMapControlFlowDeclutter
9{
10 /// <summary>Glance: убрать все multibranch-рёбра и недостижимое от якоря.</summary>
11 private const int NormalFanOutCollapseThreshold = 4;
12
13 /// <summary>Normal: при веере ≥ порога оставить столько значимых исходов + агрегат «+N».</summary>
14 private const int NormalFanOutKeepCount = 3;
15
16 public static GraphDocument? TryTransform(in CodeNavigationMapPipelineState state)
17 {
18 if (!string.Equals(state.MapLevel, CodeNavigationMapLevelKind.ControlFlow, StringComparison.Ordinal))
19 return null;
20
21 return state.DetailLevel switch
22 {
23 CodeNavigationMapDetailLevel.Glance => TryStripAllMultiBranch(state.Subgraph),
24 CodeNavigationMapDetailLevel.Normal => TryCompressMultiBranchFanOut(state.Subgraph),
25 _ => null
26 };
27 }
28
29 private static GraphDocument? TryStripAllMultiBranch(GraphDocument doc)
30 {
31 var edgesWithoutMulti = doc.Edges.Where(e => !IsMultibranchEdge(e)).ToList();
32 if (edgesWithoutMulti.Count == doc.Edges.Count)
33 return null;
34
35 var anchorId = FindAnchorNodeId(doc);
36 var reachable = ReachableForward(anchorId, edgesWithoutMulti);
37 var nodes = doc.Nodes.Where(n => reachable.Contains(n.Id)).ToList();
38 var kept = new HashSet<string>(reachable, StringComparer.OrdinalIgnoreCase);
39 var finalEdges = edgesWithoutMulti.Where(e => kept.Contains(e.FromId) && kept.Contains(e.ToId)).ToList();
40
41 return new GraphDocument
42 {
43 AnchorPath = doc.AnchorPath,
44 Kind = doc.Kind,
45 Nodes = nodes,
46 Edges = finalEdges
47 };
48 }
49
50 private static GraphDocument? TryCompressMultiBranchFanOut(GraphDocument doc)
51 {
52 var nodeById = doc.Nodes.ToDictionary(n => n.Id, StringComparer.OrdinalIgnoreCase);
53 var multiByFrom = doc.Edges
54 .Where(IsMultibranchEdge)
55 .GroupBy(e => e.FromId, StringComparer.OrdinalIgnoreCase)
56 .Where(g => g.Count() >= NormalFanOutCollapseThreshold)
57 .ToList();
58 if (multiByFrom.Count == 0)
59 return null;
60
61 var removedEdgeKeys = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
62 var extraNodes = new List<GraphNode>();
63 var extraEdges = new List<GraphEdge>();
64 var nextAgg = 0;
65
66 foreach (var group in multiByFrom)
67 {
68 var ordered = group
69 .OrderBy(e => TargetPriority(nodeById.GetValueOrDefault(e.ToId)))
70 .ThenBy(e => e.ToId, StringComparer.OrdinalIgnoreCase)
71 .ToList();
72 var keep = ordered.Take(NormalFanOutKeepCount).ToList();
73 var drop = ordered.Skip(NormalFanOutKeepCount).ToList();
74 if (drop.Count == 0)
75 continue;
76
77 foreach (var e in drop)
78 removedEdgeKeys.Add(EdgeKey(e));
79
80 var hub = nodeById.GetValueOrDefault(group.Key);
81 var aggId = $"mbr_agg_{group.Key}_{nextAgg++}";
82 extraNodes.Add(new GraphNode
83 {
84 Id = aggId,
85 Path = hub?.Path ?? doc.AnchorPath,
86 Kind = "condition_step",
87 Label = $"+{drop.Count}",
88 LineStart = hub?.LineStart
89 });
90 extraEdges.Add(new GraphEdge
91 {
92 FromId = group.Key,
93 ToId = aggId,
94 Kind = "MultiBranch",
95 RelationKind = "collapsed_branches"
96 });
97 }
98
99 if (removedEdgeKeys.Count == 0)
100 return null;
101
102 var edges = doc.Edges.Where(e => !removedEdgeKeys.Contains(EdgeKey(e))).Concat(extraEdges).ToList();
103 var nodeIds = new HashSet<string>(edges.SelectMany(e => new[] { e.FromId, e.ToId }), StringComparer.OrdinalIgnoreCase);
104 var nodes = doc.Nodes.Where(n => nodeIds.Contains(n.Id)).Concat(extraNodes).ToList();
105
106 return new GraphDocument
107 {
108 AnchorPath = doc.AnchorPath,
109 Kind = doc.Kind,
110 Nodes = nodes,
111 Edges = edges
112 };
113 }
114
115 private static int TargetPriority(GraphNode? node)
116 {
117 if (node is null)
118 return 4;
119 if (string.Equals(node.Kind, "call_step", StringComparison.OrdinalIgnoreCase)
120 || string.Equals(node.Kind, "loop_step", StringComparison.OrdinalIgnoreCase))
121 return 0;
122 if (string.Equals(node.Kind, "exit_step", StringComparison.OrdinalIgnoreCase))
123 return 1;
124 if (string.Equals(node.Kind, "condition_step", StringComparison.OrdinalIgnoreCase))
125 return 2;
126 return 3;
127 }
128
129 private static string EdgeKey(GraphEdge e) => $"{e.FromId}->{e.ToId}";
130
131 private static bool IsMultibranchEdge(GraphEdge e) =>
132 !string.IsNullOrWhiteSpace(e.Kind)
133 && e.Kind.Contains("multibranch", StringComparison.OrdinalIgnoreCase);
134
135 private static string FindAnchorNodeId(GraphDocument doc)
136 {
137 var anchor = doc.Nodes.FirstOrDefault(n => string.Equals(n.Kind, "anchor", StringComparison.OrdinalIgnoreCase));
138 if (anchor is not null)
139 return anchor.Id;
140 var n0 = doc.Nodes.FirstOrDefault(n => n.Id.Equals("n0", StringComparison.OrdinalIgnoreCase));
141 if (n0 is not null)
142 return n0.Id;
143 return doc.Nodes[0].Id;
144 }
145
146 private static HashSet<string> ReachableForward(string anchorId, IReadOnlyList<GraphEdge> edges)
147 {
148 var outgoing = new Dictionary<string, List<string>>(StringComparer.OrdinalIgnoreCase);
149 foreach (var e in edges)
150 {
151 if (!outgoing.TryGetValue(e.FromId, out var list))
152 {
153 list = [];
154 outgoing[e.FromId] = list;
155 }
156
157 list.Add(e.ToId);
158 }
159
160 var seen = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { anchorId };
161 var queue = new Queue<string>();
162 queue.Enqueue(anchorId);
163 while (queue.Count > 0)
164 {
165 var id = queue.Dequeue();
166 if (!outgoing.TryGetValue(id, out var next))
167 continue;
168 foreach (var t in next)
169 {
170 if (seen.Add(t))
171 queue.Enqueue(t);
172 }
173 }
174
175 return seen;
176 }
177}
178
View only · write via MCP/CIDE