Skip to content

Commit e2a049f

Browse files
thymikeeclaude
andcommitted
fix(depgraph): keep value-cycle diagnostics and affected working
Transitive marking ran inside buildGraph and threw on a value-import cycle, so `pnpm depgraph affected` failed and the report could no longer show the R4 cycle it exists to show. Marking now runs only in the report (its sole consumer) and only when the graph has no value cycle; the summary says the count is not computed instead. The library's reduction already rejects cycles, so the separate acyclicity pass is gone. typeInversionsByPair now dedups with the shared importEdgeId identity. Co-Authored-By: Claude Opus 5.5 (1M context) <[email protected]>
1 parent f1a64ef commit e2a049f

5 files changed

Lines changed: 69 additions & 50 deletions

File tree

‎scripts/depgraph/README.md‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,9 +46,9 @@ gate rejects value-import cycles (R4) and spine back-edges (R5); the graph addit
4646
a module's side effects run, and a direct import is often deliberately clearer than reaching
4747
through a barrel. Deciding whether any given edge can go needs symbol-level analysis this does
4848
not attempt. ~2300 of them: a place to look, never a work list. They are exactly the value
49-
edges the transitive reduction drops, so the report refuses to run when a value-import cycle
50-
(an R4 failure) makes the reduction undefined; fix the cycle first.
51-
- **type-only and dynamic cycles** — 8 of them, all outside R4 by design (a type-only import is
49+
edges the transitive reduction drops. A value-import cycle (an R4 failure) makes the reduction
50+
undefined, so the report then lists the cycle and leaves this count uncomputed.
51+
- **type-only and dynamic cycles** — 23 of them, all outside R4 by design (a type-only import is
5252
free at runtime, a dynamic one is a deliberate cold-start seam). Worth reading when a module
5353
feels hard to reason about.
5454

‎scripts/depgraph/build.ts‎

Lines changed: 35 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ import { pathToFileURL } from 'node:url';
1818
import { zoneRank } from '../layering/model.ts';
1919
import { runAffected } from './affected-run.ts';
2020
import { loadGraph } from './load.ts';
21-
import { computeLevels, type GraphData } from './model.ts';
21+
import { computeLevels, markTransitivelyReachableEdges, type GraphData } from './model.ts';
2222

2323
const repoRoot = execFileSync('git', ['rev-parse', '--show-toplevel'], {
2424
encoding: 'utf8',
@@ -79,8 +79,14 @@ function edgeFlags(edge: GraphData['edges'][number]): number {
7979
);
8080
}
8181

82+
/** Transitive reachability is undefined on a value cycle; the report then lists the cycle instead. */
83+
function hasValueCycle(graph: Pick<GraphData, 'cycles'>): boolean {
84+
return graph.cycles.some((cycle) => cycle.kind === 'value');
85+
}
86+
8287
function buildPayload(): Payload {
8388
const graph = loadGraph(repoRoot);
89+
if (!hasValueCycle(graph)) markTransitivelyReachableEdges(graph.edges);
8490
const levels = computeLevels(graph.nodes, graph.edges);
8591

8692
const zoneIndex = new Map(graph.zones.map((zone, index) => [zone.id, index]));
@@ -115,6 +121,33 @@ function buildPayload(): Payload {
115121
};
116122
}
117123

124+
/** The text summary printed after the JSON is written; every count is read back from `payload`. */
125+
function formatSummary(payload: Payload, jsonPath: string): string {
126+
const valueCycles = payload.cycles.filter((cycle) => cycle.kind === 'value').length;
127+
const otherCycles = payload.cycles.length - valueCycles;
128+
const backEdges = payload.edges.filter(([, , , flags]) => flags & 1).length;
129+
const transitivelyReachable =
130+
valueCycles > 0
131+
? 'not computed while a value-import cycle exists'
132+
: payload.edges.filter(([, , , flags]) => flags & 2).length;
133+
const typeInversions = Object.values(payload.typeInversions).reduce((sum, n) => sum + n, 0);
134+
const authorityCounts = Object.entries(payload.authorityCounts)
135+
.map(([label, count]) => `${label}=${count}`)
136+
.join(', ');
137+
return (
138+
`Dependency graph: ${payload.generated.files} files, ${payload.generated.edges} edges, ` +
139+
`${payload.zones.length} zones\n` +
140+
` value-import cycles (R4): ${valueCycles}\n` +
141+
` type-only/dynamic cycles (not gate-rejected): ${otherCycles}\n` +
142+
` spine back-edges (R5): ${backEdges}\n` +
143+
` type-only spine inversions (R6): ${typeInversions}\n` +
144+
` value edges whose target is also reachable at distance >= 2: ${transitivelyReachable}\n` +
145+
` declared-authority labels: ${authorityCounts}\n` +
146+
` (reachability only — not a removability claim, see scripts/depgraph/README.md)\n` +
147+
` wrote ${path.relative(repoRoot, jsonPath)}\n`
148+
);
149+
}
150+
118151
async function main(argv: readonly string[]): Promise<number> {
119152
// `affected` is the query subcommand (scripts/depgraph/affected-run.ts); with no subcommand
120153
// this stays the whole-graph report.
@@ -130,26 +163,7 @@ async function main(argv: readonly string[]): Promise<number> {
130163
fs.mkdirSync(path.dirname(jsonPath), { recursive: true });
131164
fs.writeFileSync(jsonPath, `${JSON.stringify(payload, null, 2)}\n`);
132165

133-
const valueCycles = payload.cycles.filter((cycle) => cycle.kind === 'value').length;
134-
const otherCycles = payload.cycles.length - valueCycles;
135-
const backEdges = payload.edges.filter(([, , , flags]) => flags & 1).length;
136-
const transitivelyReachable = payload.edges.filter(([, , , flags]) => flags & 2).length;
137-
const typeInversions = Object.values(payload.typeInversions).reduce((sum, n) => sum + n, 0);
138-
const authorityCounts = Object.entries(payload.authorityCounts)
139-
.map(([label, count]) => `${label}=${count}`)
140-
.join(', ');
141-
process.stdout.write(
142-
`Dependency graph: ${payload.generated.files} files, ${payload.generated.edges} edges, ` +
143-
`${payload.zones.length} zones\n` +
144-
` value-import cycles (R4): ${valueCycles}\n` +
145-
` type-only/dynamic cycles (not gate-rejected): ${otherCycles}\n` +
146-
` spine back-edges (R5): ${backEdges}\n` +
147-
` type-only spine inversions (R6): ${typeInversions}\n` +
148-
` value edges whose target is also reachable at distance >= 2: ${transitivelyReachable}\n` +
149-
` declared-authority labels: ${authorityCounts}\n` +
150-
` (reachability only — not a removability claim, see scripts/depgraph/README.md)\n` +
151-
` wrote ${path.relative(repoRoot, jsonPath)}\n`,
152-
);
166+
process.stdout.write(formatSummary(payload, jsonPath));
153167
return 0;
154168
}
155169

‎scripts/depgraph/import-graph.test.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ test('importGraph adds explicit files that no kept edge touches', () => {
4444
);
4545
});
4646

47-
test('importGraph keeps distinct file pairs distinct even when a path contains the arrow', () => {
47+
test('importGraph gives every distinct file pair its own edge id', () => {
4848
const pair = (from: string, to: string) => ({ ...edges[0]!, from, to });
4949
const graph = importGraph(
5050
[pair('src/a -> b.ts', 'src/c.ts'), pair('src/a', 'b.ts -> src/c.ts')],

‎scripts/depgraph/model.test.ts‎

Lines changed: 24 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -243,17 +243,31 @@ test('flags only value edges whose target is already reachable at distance >= 2'
243243
assert.deepEqual(flagged, ['src/core/a.ts -> src/core/c.ts']);
244244
});
245245

246-
test('transitive marking refuses a value cycle instead of guessing', () => {
247-
const edges = collapseEdges(
248-
resolveImportEdges(
249-
sources({
250-
'src/core/a.ts': "import { b } from './b.ts';\nexport const a = b;",
251-
'src/core/b.ts': "import { a } from './a.ts';\nexport const b = a;",
252-
}),
253-
),
254-
);
246+
function valueCycleFixture(): Map<string, string> {
247+
return sources({
248+
'src/core/a.ts': "import { b } from './b.ts';\nexport const a = b;",
249+
'src/core/b.ts': "import { a } from './a.ts';\nexport const b = a;",
250+
});
251+
}
252+
253+
test('transitive marking is undefined on a value cycle', () => {
254+
const edges = collapseEdges(resolveImportEdges(valueCycleFixture()));
255255

256-
assert.throws(() => markTransitivelyReachableEdges(edges), /value-import cycle present/);
256+
assert.throws(() => markTransitivelyReachableEdges(edges), /cycle/);
257+
});
258+
259+
test('buildGraph still reports a value cycle and leaves edges unmarked', () => {
260+
const files = valueCycleFixture();
261+
const graph = buildGraph(files, resolveImportEdges(files));
262+
263+
assert.deepEqual(
264+
graph.cycles.map((cycle) => cycle.kind),
265+
['value'],
266+
);
267+
assert.deepEqual(
268+
graph.edges.filter((edge) => edge.transitivelyReachable),
269+
[],
270+
);
257271
});
258272

259273
test('a type-only shortcut is never flagged against a value path', () => {

‎scripts/depgraph/model.ts‎

Lines changed: 6 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ import {
1515
type ResolvedImportEdge,
1616
} from '../layering/model.ts';
1717
import { ARCHITECTURE_OWNERSHIP, matchesDeclaredRoot } from '../layering/architecture-ownership.ts';
18-
import { genPostorder, getSuccessors, getTransitiveReduction, isAcyclic } from '@statelyai/graph';
18+
import { genPostorder, getSuccessors, getTransitiveReduction } from '@statelyai/graph';
1919
import { importEdgeId, importGraph, VALUE_EDGES } from './import-graph.ts';
2020

2121
export type EdgeKind = 'value' | 'type' | 'dynamic';
@@ -226,16 +226,11 @@ export function collapseEdges(edges: readonly ResolvedImportEdge[]): GraphEdge[]
226226
* whether any given edge can go needs symbol-level analysis this does not attempt.
227227
*
228228
* On a DAG, the edges with a longer alternative path are exactly the ones the transitive
229-
* reduction drops. R4 keeps the value subgraph acyclic; a value cycle makes the reduction
230-
* undefined, and the report says so rather than inventing a partial answer.
229+
* reduction drops. The reduction is undefined on a cycle, so callers mark only when the graph has
230+
* no `value` cycle (R4); the library throws otherwise.
231231
*/
232232
export function markTransitivelyReachableEdges(edges: GraphEdge[]): void {
233233
const valueGraph = importGraph(edges, VALUE_EDGES);
234-
if (!isAcyclic(valueGraph)) {
235-
throw new Error(
236-
'value-import cycle present; transitive reachability needs the DAG R4 guarantees — run pnpm check:layering',
237-
);
238-
}
239234
const kept = new Set(getTransitiveReduction(valueGraph).edges.map((edge) => edge.id));
240235
for (const edge of edges) {
241236
if (edge.kind !== 'value') continue;
@@ -390,7 +385,7 @@ export function typeInversionsByPair(edges: readonly ResolvedImportEdge[]): Reco
390385
for (const edge of edges) {
391386
const pair = typeInversionPair(edge);
392387
if (!pair) continue;
393-
const identity = `${edge.file} -> ${edge.target}`;
388+
const identity = importEdgeId(edge.file, edge.target);
394389
if (seen.has(identity)) continue;
395390
seen.add(identity);
396391
byPair.set(pair, (byPair.get(pair) ?? 0) + 1);
@@ -403,7 +398,6 @@ export function buildGraph(
403398
edges: readonly ResolvedImportEdge[],
404399
): GraphData {
405400
const collapsed = collapseEdges(edges);
406-
markTransitivelyReachableEdges(collapsed);
407401
const edgeAuthorities = collapsed.map(({ authorities }) =>
408402
authorityLabelsForDeclared(authorities),
409403
);
@@ -423,11 +417,8 @@ export function buildGraph(
423417
}
424418

425419
/**
426-
* Longest distance from each node to a sink over value edges. The layering gate rejects
427-
* production value-import cycles (R4), so that subgraph is a DAG and the height is
428-
* well-defined. Postorder visits every successor before its importer; a back-edge in a future
429-
* cycle reaches a node with no height yet and contributes nothing, so the walk degrades rather
430-
* than looping.
420+
* Longest distance from each node to a sink over value edges. R4 keeps that subgraph a DAG; on a
421+
* value cycle the edge that closes the loop adds no height, so levels stay finite.
431422
*/
432423
export function computeLevels(
433424
nodes: readonly GraphNode[],

0 commit comments

Comments
 (0)