Skip to content

Commit 136eb63

Browse files
thymikeeclaude
andauthored
feat(depgraph): dominator, zone-SCC, and cohesion report summaries (#3285)
* feat(depgraph): add dominator, zone-SCC, and cohesion report summaries Adds three report-only fields to `pnpm depgraph` nothing in scripts/layering or scripts/check-affected reads: a dominator-tree summary of one entry's eager-load closure over value edges (default src/daemon.ts, overridable with --dominator-entry), zone-level strongly connected components over value zone pairs, and Louvain community detection scored against declared zones with getModularity, plus a per-zone cohesion share. Each reproduces the numbers #3276 quotes from the earlier ad hoc analysis (621/1837 eager files, the maestro/provider-webdriver dominator branches, the 9-zone cycle, 0.373 vs 0.564 modularity, and the five lowest per-zone cohesion shares) against the current tree. getModularity wants Community<N> (full node objects) but getLouvainCommunities returns bare ids; computeCohesionSummary maps ids back onto the graph's own nodes rather than working around it at every call site. Co-Authored-By: Claude Sonnet 5 <[email protected]> * fix(depgraph): tighten report assertions and empty-flag handling Review findings on #3285: - model.test.ts asserted the SCC/modularity summary lines with shape-only regexes that accepted any count or score, so a CLI line inconsistent with the JSON it was derived from still passed. Compare against the exact payload values instead (planted a wrong modularity value to confirm the test now fails without the fix). - flagValue returned an empty string for `--out ""` / `--dominator-entry ""` verbatim, which bypassed the `?? <default>` fallback (only nullish values trigger it) and resolved --out to the current directory, crashing the write with EISDIR instead of falling back like a missing value does. Fixed at the shared helper, with a regression test for both flags (confirmed both fail against the prior flagValue). - README overstated dominatorSummary.bottlenecks as covering "every reachable file"; the entry itself is excluded by construction. - Clarified the ALL_EDGES doc comment: computeZoneSccSummary builds its own value-only zone graph and never reads this constant, only computeCohesionSummary does. Co-Authored-By: Claude Sonnet 5 <[email protected]> --------- Co-authored-by: Claude Sonnet 5 <[email protected]>
1 parent d32c363 commit 136eb63

7 files changed

Lines changed: 540 additions & 10 deletions

File tree

‎package.json‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -153,7 +153,7 @@
153153
"check:layering": "node --experimental-strip-types scripts/node-test-tmpdir.ts --experimental-strip-types --test scripts/layering/*.test.ts && node --experimental-strip-types scripts/layering/check.ts",
154154
"check:di-seams": "node --experimental-strip-types scripts/node-test-tmpdir.ts --experimental-strip-types --test scripts/di-seams/*.test.ts && node --experimental-strip-types scripts/di-seams/check.ts",
155155
"depgraph": "node --experimental-strip-types scripts/depgraph/build.ts",
156-
"depgraph:test": "node --experimental-strip-types scripts/node-test-tmpdir.ts --experimental-strip-types --test scripts/depgraph/model.test.ts scripts/depgraph/import-graph.test.ts scripts/depgraph/affected.test.ts",
156+
"depgraph:test": "node --experimental-strip-types scripts/node-test-tmpdir.ts --experimental-strip-types --test scripts/depgraph/model.test.ts scripts/depgraph/import-graph.test.ts scripts/depgraph/affected.test.ts scripts/depgraph/structure-summary.test.ts",
157157
"check:production-exports": "fallow dead-code --config fallow-production-exports.json --production --unused-exports --fail-on-issues",
158158
"check:bundle-owner-files": "node --experimental-strip-types scripts/check-bundle-owner-files.ts",
159159
"check:package": "node --experimental-strip-types scripts/check-package.ts",

‎scripts/depgraph/README.md‎

Lines changed: 33 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -107,8 +107,10 @@ Extraction stays with the layering gate; traversal does not. `import-graph.ts` t
107107
edges into a [`@statelyai/graph`](https://stately.ai/docs/packages/graph) graph filtered to the
108108
edge kinds a question needs (value for evaluation order, value + dynamic for what a handler can
109109
run), and the report and `affected` query use its BFS, postorder, and transitive reduction rather
110-
than hand-rolled walks. The library also carries centrality, community, dominator, and layout
111-
algorithms; reach for them in a throwaway probe before writing a new traversal here.
110+
than hand-rolled walks. `structure-summary.ts` additionally uses its dominator tree, strongly
111+
connected components, and Louvain community detection — see "Structural summaries" below. The
112+
library also carries centrality and layout algorithms; reach for them in a throwaway probe before
113+
writing a new traversal here.
112114

113115
## What the JSON carries
114116

@@ -122,6 +124,35 @@ algorithms; reach for them in a throwaway probe before writing a new traversal h
122124
dynamic. Flags bitfield: `1` spine back-edge, `2` target also reachable at distance >= 2, `4` type-only
123125
inversion.
124126
- `cycles[]` — each with `kind` (`value` / `type` / `dynamic`) and its node path.
127+
- `dominatorSummary`, `zoneSccSummary`, `cohesionSummary` — see "Structural summaries" below.
128+
129+
## Structural summaries (report-only)
130+
131+
`scripts/depgraph/structure-summary.ts` adds three fields nothing in `scripts/layering/` or
132+
`scripts/check-affected/` reads. They are the numbers workstream 7 of #3276 asked to keep a
133+
permanent home in the tooling, not a gate.
134+
135+
- **`dominatorSummary`** — the dominator tree of one entry's eager-load closure over VALUE edges
136+
only (dynamic imports are a deliberate cold-start seam, so they never join the closure).
137+
`reachableFiles` is the eager closure size; `bottlenecks` ranks every reachable non-entry file
138+
by how many files become unreachable if it disappeared — the size of the branch moving it
139+
behind `import()` would cut. Defaults to `src/daemon.ts`; override with
140+
`pnpm depgraph --dominator-entry <path>`.
141+
- **`zoneSccSummary`** — strongly connected components of the zone graph, built from VALUE zone
142+
pairs only (`zoneEdges` entries with `valueCount > 0`), the same edge kind R4 keeps acyclic at
143+
file level. R4 is file-level; nothing stops a loop from closing once files collapse into zones —
144+
the guardrail gap workstream 4 of #3276 names. A component with `size > 1` is a live cycle.
145+
- **`cohesionSummary`** — Louvain communities (`getLouvainCommunities`, mixing every edge kind
146+
since community detection treats the graph as undirected) versus declared zones, scored with
147+
`getModularity`, plus a per-zone `cohesionShare`: the share of a zone's files that land in its
148+
largest detected community. Low values are where the folder partition cuts across a cluster the
149+
import graph actually forms.
150+
151+
```sh
152+
pnpm depgraph
153+
pnpm depgraph --dominator-entry src/cli/entry.ts
154+
jq '{dominatorSummary, zoneSccSummary, cohesionSummary}' .tmp/depgraph/graph.json
155+
```
125156

126157
## Declared-authority overlay
127158

‎scripts/depgraph/build.ts‎

Lines changed: 57 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -19,11 +19,25 @@ import { zoneRank } from '../layering/model.ts';
1919
import { runAffected } from './affected-run.ts';
2020
import { loadGraph } from './load.ts';
2121
import { computeLevels, markTransitivelyReachableEdges, type GraphData } from './model.ts';
22+
import {
23+
computeCohesionSummary,
24+
computeDominatorSummary,
25+
computeZoneSccSummary,
26+
type CohesionSummary,
27+
type DominatorSummary,
28+
type ZoneSccSummary,
29+
} from './structure-summary.ts';
2230

2331
const repoRoot = execFileSync('git', ['rev-parse', '--show-toplevel'], {
2432
encoding: 'utf8',
2533
}).trim();
2634

35+
/**
36+
* The daemon is the one process entry point whose eager-load closure is worth asking about by
37+
* default; `--dominator-entry` overrides it for any other file.
38+
*/
39+
const DEFAULT_DOMINATOR_ENTRY = 'src/daemon.ts';
40+
2741
/** Compact wire form. Nodes and edges are index-addressed to keep the payload small. */
2842
type Payload = {
2943
generated: { commit: string; files: number; edges: number };
@@ -49,6 +63,13 @@ type Payload = {
4963
cycles: { kind: string; path: number[] }[];
5064
/** Type-only spine inversions per zone pair, by the gate's counting rule. */
5165
typeInversions: Record<string, number>;
66+
/**
67+
* Report-only structural summaries (scripts/depgraph/structure-summary.ts): no layering or
68+
* check-affected gate reads these fields today.
69+
*/
70+
dominatorSummary: DominatorSummary;
71+
zoneSccSummary: ZoneSccSummary;
72+
cohesionSummary: CohesionSummary;
5273
};
5374

5475
function headCommit(): string {
@@ -84,7 +105,7 @@ function hasValueCycle(graph: Pick<GraphData, 'cycles'>): boolean {
84105
return graph.cycles.some((cycle) => cycle.kind === 'value');
85106
}
86107

87-
function buildPayload(): Payload {
108+
function buildPayload(dominatorEntry: string): Payload {
88109
const graph = loadGraph(repoRoot);
89110
if (!hasValueCycle(graph)) markTransitivelyReachableEdges(graph.edges);
90111
const levels = computeLevels(graph.nodes, graph.edges);
@@ -118,6 +139,9 @@ function buildPayload(): Payload {
118139
path: cycle.path.map((file) => nodeIndex.get(file)!),
119140
})),
120141
typeInversions: graph.typeInversions,
142+
dominatorSummary: computeDominatorSummary(dominatorEntry, graph),
143+
zoneSccSummary: computeZoneSccSummary(graph),
144+
cohesionSummary: computeCohesionSummary(graph),
121145
};
122146
}
123147

@@ -134,6 +158,9 @@ function formatSummary(payload: Payload, jsonPath: string): string {
134158
const authorityCounts = Object.entries(payload.authorityCounts)
135159
.map(([label, count]) => `${label}=${count}`)
136160
.join(', ');
161+
const { dominatorSummary, zoneSccSummary, cohesionSummary } = payload;
162+
const topBottleneck = dominatorSummary.bottlenecks[0];
163+
const leastCohesive = cohesionSummary.zoneCohesion[0];
137164
return (
138165
`Dependency graph: ${payload.generated.files} files, ${payload.generated.edges} edges, ` +
139166
`${payload.zones.length} zones\n` +
@@ -144,22 +171,45 @@ function formatSummary(payload: Payload, jsonPath: string): string {
144171
` value edges whose target is also reachable at distance >= 2: ${transitivelyReachable}\n` +
145172
` declared-authority labels: ${authorityCounts}\n` +
146173
` (reachability only — not a removability claim, see scripts/depgraph/README.md)\n` +
174+
` dominator summary for ${dominatorSummary.entry}: ${dominatorSummary.reachableFiles} of ` +
175+
`${dominatorSummary.totalFiles} files loaded eagerly` +
176+
(topBottleneck
177+
? `, biggest branch ${topBottleneck.file} (${topBottleneck.files} files, ${topBottleneck.loc} loc)\n`
178+
: '\n') +
179+
` zone-level SCCs: ${zoneSccSummary.components.length} cyclic group(s) across ` +
180+
`${zoneSccSummary.zones} zones\n` +
181+
` modularity: declared zones ${cohesionSummary.modularity.declaredZones.toFixed(3)}, ` +
182+
`detected communities ${cohesionSummary.modularity.detectedCommunities.toFixed(3)}` +
183+
(leastCohesive
184+
? `, least cohesive zone ${leastCohesive.zone} (${(leastCohesive.cohesionShare * 100).toFixed(0)}%)\n`
185+
: '\n') +
147186
` wrote ${path.relative(repoRoot, jsonPath)}\n`
148187
);
149188
}
150189

190+
/**
191+
* A flag's value, or `undefined` when the flag is absent, trailing with nothing after it, or
192+
* given an empty string — the last case matters because `?? <default>` only catches nullish
193+
* values, and an empty `--out ""` must fall back the same way a missing one does, not resolve to
194+
* the current directory and crash the subsequent write with EISDIR.
195+
*/
196+
function flagValue(argv: readonly string[], flag: string): string | undefined {
197+
const index = argv.indexOf(flag);
198+
const value = index >= 0 ? argv[index + 1] : undefined;
199+
return value ? value : undefined;
200+
}
201+
151202
async function main(argv: readonly string[]): Promise<number> {
152203
// `affected` is the query subcommand (scripts/depgraph/affected-run.ts); with no subcommand
153204
// this stays the whole-graph report.
154205
if (argv[0] === 'affected') return await runAffected(argv.slice(1), repoRoot);
155206

156-
const outFlag = argv.indexOf('--out');
157-
const jsonPath =
158-
outFlag >= 0 && argv[outFlag + 1]
159-
? path.resolve(argv[outFlag + 1]!)
160-
: path.join(repoRoot, '.tmp/depgraph/graph.json');
207+
const jsonPath = path.resolve(
208+
flagValue(argv, '--out') ?? path.join(repoRoot, '.tmp/depgraph/graph.json'),
209+
);
210+
const dominatorEntry = flagValue(argv, '--dominator-entry') ?? DEFAULT_DOMINATOR_ENTRY;
161211

162-
const payload = buildPayload();
212+
const payload = buildPayload(dominatorEntry);
163213
fs.mkdirSync(path.dirname(jsonPath), { recursive: true });
164214
fs.writeFileSync(jsonPath, `${JSON.stringify(payload, null, 2)}\n`);
165215

‎scripts/depgraph/import-graph.ts‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,15 @@ export const VALUE_EDGES: ReadonlySet<EdgeKind> = new Set(['value']);
1515
*/
1616
export const EXECUTABLE_EDGES: ReadonlySet<EdgeKind> = new Set(['value', 'dynamic']);
1717

18+
/**
19+
* Every collapsed edge kind, for the structural question ("does anything reference this file at
20+
* all") community detection asks (`computeCohesionSummary`). Community algorithms treat the graph
21+
* as undirected regardless of kind, so mixing kinds in is the right input, not a loosening of a
22+
* rule — there is no gate riding on this set. Zone-level cycle reporting (`computeZoneSccSummary`)
23+
* does not use this set: it builds its own zone graph from VALUE zone pairs only, to mirror R4.
24+
*/
25+
export const ALL_EDGES: ReadonlySet<EdgeKind> = new Set(['value', 'type', 'dynamic']);
26+
1827
/**
1928
* Identity of one file pair, shared by `collapseEdges` and the graph's edge ids. NUL cannot occur
2029
* in a file path, so distinct pairs never share an id.

‎scripts/depgraph/model.test.ts‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -435,6 +435,12 @@ test('build.ts writes the default path and a summary consistent with the JSON',
435435
edgeAuthorities: string[][];
436436
authorityCounts: Record<string, number>;
437437
typeInversions: Record<string, number>;
438+
dominatorSummary: { entry: string; reachableFiles: number; totalFiles: number };
439+
zoneSccSummary: { zones: number; components: { zones: string[]; size: number }[] };
440+
cohesionSummary: {
441+
modularity: { declaredZones: number; detectedCommunities: number };
442+
zoneCohesion: { zone: string; cohesionShare: number }[];
443+
};
438444
};
439445

440446
// Wire shape: the fields a consumer queries. A rename here is a breaking change for any script
@@ -447,6 +453,9 @@ test('build.ts writes the default path and a summary consistent with the JSON',
447453
'edges',
448454
'cycles',
449455
'typeInversions',
456+
'dominatorSummary',
457+
'zoneSccSummary',
458+
'cohesionSummary',
450459
]) {
451460
assert.ok(field in payload, `legacy payload field ${field} disappeared`);
452461
}
@@ -461,6 +470,25 @@ test('build.ts writes the default path and a summary consistent with the JSON',
461470
assert.ok(payload.zones.length > 0);
462471
assert.ok(Object.keys(payload.typeInversions).length > 0);
463472

473+
// Report-only fields (#3283): no gate reads these, so this pins only the wire shape.
474+
assert.equal(payload.dominatorSummary.entry, 'src/daemon.ts');
475+
assert.ok(payload.dominatorSummary.reachableFiles > 0);
476+
assert.ok(payload.dominatorSummary.reachableFiles <= payload.dominatorSummary.totalFiles);
477+
assert.ok(payload.zoneSccSummary.zones > 0);
478+
assert.ok(
479+
payload.zoneSccSummary.components.every(
480+
(component) => component.zones.length === component.size,
481+
),
482+
);
483+
assert.ok(payload.cohesionSummary.modularity.declaredZones <= 1);
484+
assert.ok(payload.cohesionSummary.modularity.detectedCommunities <= 1);
485+
for (const { cohesionShare } of payload.cohesionSummary.zoneCohesion) {
486+
assert.ok(
487+
cohesionShare > 0 && cohesionShare <= 1,
488+
`cohesionShare out of range: ${cohesionShare}`,
489+
);
490+
}
491+
464492
// The printed summary must agree with the payload it was derived from.
465493
const inversions = Object.values(payload.typeInversions).reduce((sum, n) => sum + n, 0);
466494
assert.match(
@@ -470,6 +498,44 @@ test('build.ts writes the default path and a summary consistent with the JSON',
470498
assert.match(stdout, new RegExp(`type-only spine inversions \\(R6\\): ${inversions}`));
471499
const reachable = payload.edges.filter(([, , , flags]) => (flags & 2) !== 0).length;
472500
assert.match(stdout, new RegExp(`reachable at distance >= 2: ${reachable}`));
501+
assert.match(
502+
stdout,
503+
new RegExp(
504+
`dominator summary for src/daemon\\.ts: ${payload.dominatorSummary.reachableFiles} of ${payload.dominatorSummary.totalFiles} files loaded eagerly`,
505+
),
506+
);
507+
// Tied to the exact payload numbers (not a shape-only `\d+` regex) so a CLI summary that
508+
// drifts from the JSON it was derived from — wrong count, wrong rounding — fails this test.
509+
assert.ok(
510+
stdout.includes(
511+
`zone-level SCCs: ${payload.zoneSccSummary.components.length} cyclic group(s) across ` +
512+
`${payload.zoneSccSummary.zones} zones`,
513+
),
514+
stdout,
515+
);
516+
assert.ok(
517+
stdout.includes(
518+
`modularity: declared zones ${payload.cohesionSummary.modularity.declaredZones.toFixed(3)}, ` +
519+
`detected communities ${payload.cohesionSummary.modularity.detectedCommunities.toFixed(3)}`,
520+
),
521+
stdout,
522+
);
523+
});
524+
525+
test('build.ts honours --dominator-entry', () => {
526+
const { status, stdout } = runBuild(['--dominator-entry', 'src/cli/entry.ts']);
527+
assert.equal(status, 0, stdout);
528+
const payload = JSON.parse(readFileSync('.tmp/depgraph/graph.json', 'utf8')) as {
529+
dominatorSummary: { entry: string };
530+
};
531+
assert.equal(payload.dominatorSummary.entry, 'src/cli/entry.ts');
532+
assert.match(stdout, /dominator summary for src\/cli\/entry\.ts:/);
533+
});
534+
535+
test('build.ts reports a typed error for a dominator entry outside the graph', () => {
536+
const { status, stderr } = runBuild(['--dominator-entry', 'src/does-not-exist.ts']);
537+
assert.notEqual(status, 0);
538+
assert.match(stderr, /src\/does-not-exist\.ts is not a production source file/);
473539
});
474540

475541
test('build.ts honours --out and reports the path it wrote', () => {
@@ -488,3 +554,18 @@ test('build.ts falls back to the default path when --out has no value', () => {
488554
assert.equal(status, 0, stdout);
489555
assert.ok(stdout.includes('.tmp/depgraph/graph.json'), stdout);
490556
});
557+
558+
test('build.ts falls back to the default path when --out is given an empty string', () => {
559+
// `--out ""` must fall back the same way a missing value does. `flagValue` returning `''`
560+
// instead of `undefined` here would skip the `??` default and resolve to the current
561+
// directory, crashing the write with EISDIR instead of writing the default report.
562+
const { status, stdout } = runBuild(['--out', '']);
563+
assert.equal(status, 0, stdout);
564+
assert.ok(stdout.includes('.tmp/depgraph/graph.json'), stdout);
565+
});
566+
567+
test('build.ts falls back to the default dominator entry when --dominator-entry is given an empty string', () => {
568+
const { status, stdout } = runBuild(['--dominator-entry', '']);
569+
assert.equal(status, 0, stdout);
570+
assert.ok(stdout.includes('dominator summary for src/daemon.ts:'), stdout);
571+
});

0 commit comments

Comments
 (0)