v.depgraph: fix resolve(), add tests (fix #24075), (fix #23970), (fix #23968), (fix #22391) (#24076)

kbkpbot · web-flow · commit 0c4eed60bb26 · 2025-03-29T08:48:05.000+02:00
diff --git a/vlib/v/depgraph/depgraph.v b/vlib/v/depgraph/depgraph.v
@@ -118,10 +118,8 @@ pub fn (graph &DepGraph) resolve() &DepGraph {
 		node_names.add(node.name, node.deps)
 		node_deps.add(node.name, node.deps)
 	}
-	mut iterations := 0
 	mut resolved := new_dep_graph()
 	for node_deps.size() != 0 {
-		iterations++
 		mut ready_set := []string{}
 		for name in node_deps.keys {
 			deps := node_deps.get(name)
@@ -130,12 +128,11 @@ pub fn (graph &DepGraph) resolve() &DepGraph {
 			}
 		}
 		if ready_set.len == 0 {
-			mut g := new_dep_graph()
-			g.acyclic = false
+			resolved.acyclic = false
 			for name in node_deps.keys {
-				g.add_with_value(name, node_names.get(name), graph.values[name])
+				resolved.add_with_value(name, node_names.get(name), graph.values[name])
 			}
-			return g
+			return resolved
 		}
 		for name in ready_set {
 			node_deps.delete(name)
@@ -156,8 +153,12 @@ pub fn (graph &DepGraph) last_node() DepGraphNode {
 pub fn (graph &DepGraph) display() string {
 	mut out := []string{}
 	for node in graph.nodes {
-		for dep in node.deps {
-			out << ' * ${node.name} -> ${dep}'
+		if node.deps.len == 0 {
+			out << ' * ${node.name}'
+		} else {
+			for dep in node.deps {
+				out << ' * ${node.name} -> ${dep}'
+			}
 		}
 	}
 	return out.join('\n')
diff --git a/vlib/v/depgraph/depgraph_test.v b/vlib/v/depgraph/depgraph_test.v
@@ -0,0 +1,73 @@
+module depgraph
+
+fn test_resolve_has_deps_no_cyclic() {
+	mut g := new_dep_graph()
+	g.add('A', [])
+	g.add('B', [])
+	g.add('X', ['Y', 'G'])
+	g.add('C', [])
+	g.add('D', ['A', 'X'])
+	g.add('E', [])
+	g.add('F', [])
+	g.add('G', ['A'])
+	g.add('H', [])
+	g.add('Y', [])
+	resolved_graph := g.resolve()
+	assert resolved_graph.acyclic
+	assert resolved_graph.display() == ' * A
+ * B
+ * C
+ * E
+ * F
+ * H
+ * Y
+ * G -> A
+ * X -> Y
+ * X -> G
+ * D -> A
+ * D -> X'
+}
+
+fn test_resolve_has_deps_cyclic() {
+	mut g := new_dep_graph()
+	g.add('A', [])
+	g.add('B', [])
+	g.add('X', ['Y', 'G'])
+	g.add('C', [])
+	g.add('D', ['A', 'X'])
+	g.add('E', [])
+	g.add('F', [])
+	g.add('G', ['D'])
+	g.add('H', [])
+	g.add('Y', [])
+	resolved_graph := g.resolve()
+	assert !resolved_graph.acyclic
+	assert resolved_graph.display() == ' * A
+ * B
+ * C
+ * E
+ * F
+ * H
+ * Y
+ * X -> Y
+ * X -> G
+ * D -> A
+ * D -> X
+ * G -> D'
+}
+
+fn test_resolve_no_deps() {
+	mut g := new_dep_graph()
+	g.add('X', [])
+	g.add('A', [])
+	g.add('B', [])
+	g.add('C', [])
+	g.add('D', [])
+	resolved_graph := g.resolve()
+	assert resolved_graph.acyclic
+	assert resolved_graph.display() == ' * X
+ * A
+ * B
+ * C
+ * D'
+}
