WorkspaceGraph.java
package network.ike.workspace;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Graph operations over a workspace {@link Manifest}.
*
* <p>All algorithms operate on the subproject dependency graph defined
* by {@code depends-on} entries in workspace.yaml. The graph is small
* (typically < 20 nodes) so simple implementations are preferred
* over library dependencies.
*/
public final class WorkspaceGraph {
private final Manifest manifest;
/** Forward edges: subproject → subprojects it depends on. */
private final Map<String, List<String>> forward;
/** Reverse edges: subproject → subprojects that depend on it. */
private final Map<String, List<String>> reverse;
/**
* Build a graph from the given manifest.
* @param manifest parsed workspace manifest
*/
public WorkspaceGraph(Manifest manifest) {
this.manifest = manifest;
this.forward = buildForwardEdges();
this.reverse = buildReverseEdges();
}
/**
* Return the underlying manifest.
*
* @return the parsed workspace manifest
*/
public Manifest manifest() {
return manifest;
}
// ── Topological Sort ────────────────────────────────────────────
/**
* Topological sort of the given subprojects (or all if none specified).
* Dependencies outside the target set are ignored.
*
* @param targetNames subprojects to include; empty means all
* @return subprojects in dependency order (dependencies first)
* @throws ManifestException if a cycle is detected
*/
public List<String> topologicalSort(Set<String> targetNames) {
Set<String> targets = targetNames.isEmpty()
? manifest.subprojects().keySet()
: targetNames;
// Kahn's algorithm
Map<String, Integer> inDegree = new LinkedHashMap<>();
for (String name : targets) {
inDegree.put(name, 0);
}
for (String name : targets) {
for (String dep : depsInSet(name, targets)) {
inDegree.merge(dep, 0, Integer::sum); // ensure dep exists
inDegree.merge(name, 1, Integer::sum);
}
}
Deque<String> queue = new ArrayDeque<>();
for (Map.Entry<String, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0) {
queue.add(entry.getKey());
}
}
List<String> sorted = new ArrayList<>();
while (!queue.isEmpty()) {
String current = queue.poll();
sorted.add(current);
for (String name : targets) {
if (depsInSet(name, targets).contains(current)) {
int remaining = inDegree.merge(name, -1, Integer::sum);
if (remaining == 0) {
queue.add(name);
}
}
}
}
if (sorted.size() < targets.size()) {
Set<String> missing = new LinkedHashSet<>(targets);
missing.removeAll(sorted);
throw new ManifestException("Dependency cycle involving: " + missing);
}
return Collections.unmodifiableList(sorted);
}
/**
* Topological sort of all subprojects.
*
* @return subproject names in dependency order (leaves first)
*/
public List<String> topologicalSort() {
return topologicalSort(Set.of());
}
// ── Cascade Analysis ────────────────────────────────────────────
/**
* Compute the propagation set: all subprojects that transitively
* depend on the given subproject (BFS on reverse edges).
*
* <p>The result does NOT include the starting subproject itself.
*
* @param subprojectName the changed subproject
* @return subprojects affected by a change, in BFS discovery order
* @throws ManifestException if the subproject does not exist
*/
public List<String> cascade(String subprojectName) {
if (!manifest.subprojects().containsKey(subprojectName)) {
throw new ManifestException(
"Unknown subproject: " + subprojectName);
}
List<String> result = new ArrayList<>();
Set<String> visited = new LinkedHashSet<>();
visited.add(subprojectName);
Deque<String> queue = new ArrayDeque<>();
queue.add(subprojectName);
while (!queue.isEmpty()) {
String current = queue.poll();
List<String> dependents = reverse.getOrDefault(current, List.of());
for (String dep : dependents) {
if (visited.add(dep)) {
result.add(dep);
queue.add(dep);
}
}
}
return Collections.unmodifiableList(result);
}
// ── Cycle Detection ─────────────────────────────────────────────
/**
* Detect dependency cycles. Returns the first cycle found as a
* list of subproject names forming the cycle, or an empty list
* if no cycles exist.
*
* @return cycle path, or empty list if acyclic
*/
public List<String> detectCycle() {
// DFS with three-color marking: WHITE=unvisited, GRAY=in-stack, BLACK=done
Set<String> white = new LinkedHashSet<>(manifest.subprojects().keySet());
Set<String> gray = new LinkedHashSet<>();
Map<String, String> parent = new LinkedHashMap<>();
for (String start : manifest.subprojects().keySet()) {
if (!white.contains(start)) continue;
Deque<String> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
String current = stack.peek();
if (white.remove(current)) {
gray.add(current);
for (String dep : forwardDeps(current)) {
if (gray.contains(dep)) {
// Found cycle — reconstruct path
return reconstructCycle(parent, current, dep);
}
if (white.contains(dep)) {
parent.put(dep, current);
stack.push(dep);
}
}
} else {
stack.pop();
gray.remove(current);
}
}
}
return List.of();
}
private List<String> reconstructCycle(Map<String, String> parent,
String from, String to) {
List<String> cycle = new ArrayList<>();
cycle.add(to);
String current = from;
while (!current.equals(to)) {
cycle.add(current);
current = parent.getOrDefault(current, to);
}
cycle.add(to);
Collections.reverse(cycle);
return Collections.unmodifiableList(cycle);
}
// ── Manifest Verification ───────────────────────────────────────
/**
* Verify manifest consistency. Returns a list of error messages;
* an empty list means the manifest is valid.
*
* @return error messages, or empty list if valid
*/
public List<String> verify() {
List<String> errors = new ArrayList<>();
// Check 1: all dependency targets exist as subprojects
for (Subproject subproject : manifest.subprojects().values()) {
for (Dependency dep : subproject.dependsOn()) {
if (!manifest.subprojects().containsKey(dep.subproject())) {
errors.add(subproject.name() + " depends on unknown subproject: "
+ dep.subproject());
}
}
}
// Check 2: no dependency cycles
List<String> cycle = detectCycle();
if (!cycle.isEmpty()) {
errors.add("Dependency cycle: " + String.join(" → ", cycle));
}
// Type validity is enforced at parse time by SubprojectType.fromYamlName,
// so by the time we reach verify() every subproject.type() is a valid
// enum value — no additional check needed here.
return Collections.unmodifiableList(errors);
}
// ── Internal ────────────────────────────────────────────────────
private List<String> forwardDeps(String name) {
return forward.getOrDefault(name, List.of());
}
private Set<String> depsInSet(String name, Set<String> targetSet) {
Set<String> result = new LinkedHashSet<>();
for (String dep : forwardDeps(name)) {
if (targetSet.contains(dep)) {
result.add(dep);
}
}
return result;
}
private Map<String, List<String>> buildForwardEdges() {
Map<String, List<String>> edges = new LinkedHashMap<>();
for (Subproject subproject : manifest.subprojects().values()) {
List<String> deps = new ArrayList<>();
for (Dependency dep : subproject.dependsOn()) {
deps.add(dep.subproject());
}
edges.put(subproject.name(), Collections.unmodifiableList(deps));
}
return Collections.unmodifiableMap(edges);
}
private Map<String, List<String>> buildReverseEdges() {
Map<String, List<String>> edges = new LinkedHashMap<>();
for (String name : manifest.subprojects().keySet()) {
edges.put(name, new ArrayList<>());
}
for (Subproject subproject : manifest.subprojects().values()) {
for (Dependency dep : subproject.dependsOn()) {
edges.computeIfAbsent(dep.subproject(), k -> new ArrayList<>())
.add(subproject.name());
}
}
// Make immutable
Map<String, List<String>> immutable = new LinkedHashMap<>();
for (Map.Entry<String, List<String>> entry : edges.entrySet()) {
immutable.put(entry.getKey(),
Collections.unmodifiableList(entry.getValue()));
}
return Collections.unmodifiableMap(immutable);
}
}