Store multi-output build edges once instead of cloning them per output

[leynos]

Summary

The IR indexes a multi-output target by cloning its complete BuildEdge once for each explicit output.

This remains present on main at ac10b783f33661a0af27bd8f5d19065f095f98db:

1. manifest lowering creates one outputs: Vec<Utf8PathBuf> of length N;
2. the vector becomes BuildEdge::explicit_outputs;
3. insert_edge_for_outputs() inserts edge.clone() for every output except the last;
4. cloning BuildEdge clones its full explicit_outputs vector and every contained path.

One target with N distinct outputs therefore stores approximately N edges each containing N output paths: O(N²) path storage and clone work before recipe execution.

The original finding noted that the affected conversion was not yet wired into the CLI at its introducing commit. That limiting condition no longer applies: the current generation path loads the manifest and calls BuildGraph::from_manifest_for_shell() during ordinary build/generate operations.

Impact

A compact manifest target with a large output list can amplify into substantial CPU and memory consumption during IR construction. The impact is local/CI availability rather than privilege escalation, but the representation also imposes avoidable costs on legitimate generated manifests and forces downstream consumers to recognize duplicate copies of the same logical edge.

Required change

Represent edge identity separately from output lookup so each logical build edge is owned once.

Suitable models include:

• an edge arena/vector plus output -> EdgeId index;
• an interned edge map plus stable edge identifiers;
• shared immutable ownership such as Arc<BuildEdge> where that does not damage serialization, equality, or public API semantics.

The chosen model should preserve:

• efficient lookup from any explicit output to its producing edge;
• one canonical explicit-output vector per logical edge;
• deterministic iteration and Ninja generation;
• duplicate-output rejection before mutation of the graph;
• cycle and missing-dependency analysis across every output alias;
• clear ownership suitable for future dyndep/implicit-output work.

Prefer a representation that lets Ninja generation iterate canonical edges directly rather than deduplicating values recovered from the output index.

Acceptance criteria

• A manifest target with N outputs creates one canonical BuildEdge, not N independently owned clones.
• Total stored path entries attributable to that target grow O(N), with a structural test that does not depend solely on timing.
• Every output still resolves to the same producer in O(1)-average or equivalently bounded lookup time.
• Ninja generation emits exactly one build statement containing all explicit outputs.
• Duplicate outputs within one target and across targets retain deterministic diagnostics.
• Cycle detection, missing-dependency reporting, graph/help views, dyndep generation, equality tests, and action deduplication retain their current semantics.
• A stress or benchmark case with thousands of outputs demonstrates linear allocation/work and would fail under the previous cloned-edge representation.
• The public IR API and design documentation describe canonical edge identity and output indexing.
• make check-fmt, make lint, make test, and the bounded Kani/property suites pass.

References

• Codex finding: https://chatgpt.com/codex/cloud/security/findings/a6ba002990b081919bd92dcc2fde36db?repo=https%3A%2F%2Fgithub.com%2Fleynos%2Fnetsuke&sev=low
• Current manifest-to-IR lowering: https://github.com/leynos/netsuke/blob/ac10b783f33661a0af27bd8f5d19065f095f98db/src/ir/from_manifest.rs
• Current per-output edge insertion: https://github.com/leynos/netsuke/blob/ac10b783f33661a0af27bd8f5d19065f095f98db/src/ir/from_manifest_support.rs
• Current edge model: https://github.com/leynos/netsuke/blob/ac10b783f33661a0af27bd8f5d19065f095f98db/src/ir/graph.rs
• Current CLI generation path: https://github.com/leynos/netsuke/blob/ac10b783f33661a0af27bd8f5d19065f095f98db/src/runner/mod.rs

[leynos]

@CodeRabbit plan

[coderabbitai]

Coding Plan

Summary

Own each BuildEdge once in a Vec<BuildEdge> arena, and map every explicit output to a stable EdgeId in BuildGraph.targets.

Rewrite insert_edge_for_outputs to push one edge and index all outputs, removing the clone-per-output loop.

Retarget cycle detection, Ninja and dyndep generation, graph views, and telemetry to iterate canonical edges and resolve outputs through the index, removing the value-recovery deduplication.

Prove the O(N) property with a structural test and a stress benchmark, update the Kani model, and document canonical edge identity.

Design Choices

Design Choice 1: Which canonical edge representation do we adopt?

Options Considered:

1. Edge arena (Vec<BuildEdge>) plus an output -> EdgeId index map. Ninja generation iterates the arena directly. Downstream dedup logic is removed.
2. Arc<BuildEdge> as the map value type. Edges are owned once, but multiple output keys still reference the same edge, so iteration still requires deduplication.
3. An interned edge map keyed by a content hash, analogous to register_action. This adds hashing cost per edge and offers no benefit over the arena for iteration.

Chosen Option: 1

Rationale: The ticket lists three suitable models. The exploration confirms all three are viable, but the ticket states a preference that Ninja generation iterate canonical edges directly rather than deduplicate values recovered from the output index. The arena plus index model owns each edge once, gives O(1)-average output lookup, and lets Ninja generation iterate canonical edges directly, which matches the ticket's stated preference.

💡 User Tips

Regenerate the plan with different choices with @coderabbitai <feedback>.

Implementation Steps

Phase 1: Redefine the canonical edge storage model

Establish the new data shape in the IR core. Own each BuildEdge once in an arena, and index every output path to a stable edge identifier. Provide accessor methods so consumers do not depend on the internal field layout.

Task 1: Introduce the edge arena and identifier type

Define the canonical storage and its public identity type.

• Add a public EdgeId newtype (wrapping usize) in src/ir/graph.rs, and derive Debug, Clone, Copy, PartialEq, Eq, Hash.
• Change BuildGraph in src/ir/graph.rs to hold edges: Vec<BuildEdge> (the arena) and targets: IrHashMap<Utf8PathBuf, EdgeId> (output path to edge identifier).
• Keep actions and default_targets unchanged.
• Retain BuildEdge's existing fields and its Debug, Clone, PartialEq derives, because no Serialize, Eq, or Hash is required.
• Re-export EdgeId from src/ir/mod.rs alongside BuildEdge and BuildGraph.

Task 2: Add insertion and lookup accessors on BuildGraph

Provide a stable API so consumers do not access raw fields for common operations.

• Add a method on BuildGraph that pushes one BuildEdge into edges and maps each entry in its explicit_outputs to the new EdgeId. This replaces the fan-out clone behaviour.
• Add a lookup accessor that resolves an output &Utf8Path to (&Utf8Path, &BuildEdge) via the index and arena, preserving the canonical stored key semantics used by cycle detection.
• Add an iterator accessor over canonical edges (the arena) for Ninja generation, dyndep, and graph views.
• Add an iterator accessor over output paths (the index keys) for cycle-node enumeration.

🤖 Prompt for AI agents

Implement Phase 1: redefine the canonical edge storage model in the IR core. The
goal is to own each `BuildEdge` once in an arena and index every output path to
a stable edge identifier, replacing the current per-output clone model.

- In `src/ir/graph.rs`, add a public `EdgeId` newtype that wraps `usize`. Derive
`Debug, Clone, Copy, PartialEq, Eq, Hash` on it.
- Change `BuildGraph` so it holds `edges: Vec<BuildEdge>` as the arena, and
`targets: IrHashMap<Utf8PathBuf, EdgeId>` as the output-to-edge index. Leave
`actions` and `default_targets` unchanged.
- Keep `BuildEdge`'s existing fields and its `Debug, Clone, PartialEq` derives
unchanged; do not add `Serialize`, `Eq`, or `Hash` to it.
- Re-export `EdgeId` from `src/ir/mod.rs` alongside the existing `BuildEdge` and
`BuildGraph` exports.
- Add a `BuildGraph` method that pushes one `BuildEdge` into `edges` and maps
every path in its `explicit_outputs` to the resulting `EdgeId`. This method
replaces the fan-out clone behaviour used previously.
- Add a lookup accessor that takes an output `&Utf8Path` and resolves it through
the index and arena to `(&Utf8Path, &BuildEdge)`, preserving the canonical
stored key semantics relied on by cycle detection.
- Add an iterator accessor over the canonical edges in the arena, for use by
Ninja generation, dyndep generation, and graph views.
- Add an iterator accessor over the output paths in the index, for use by
cycle-node enumeration.

Phase 2: Update manifest lowering

Build the canonical model during lowering. Own each edge once, and keep duplicate-output rejection before any mutation of the graph.

Task 1: Rewrite per-output insertion

Remove the clone-per-output loop.

• Rewrite insert_edge_for_outputs in src/ir/from_manifest_support.rs to push the edge once and map every explicit output to the resulting EdgeId, using the new BuildGraph insertion accessor.
• Preserve one canonical explicit_outputs vector per logical edge.

Task 2: Preserve duplicate-output detection order

Keep diagnostics deterministic and unchanged.

• Keep duplicate_output_error and find_duplicates in src/ir/from_manifest_support.rs operating before insertion, so the graph is not mutated when a duplicate output is found.
• Update find_duplicates to accept the new targets: IrHashMap<Utf8PathBuf, EdgeId> type for the cross-target contains_key check. The within-target seen scan is unaffected.
• Leave register_action unchanged; its content-hash dedup already owns each Action once.

🤖 Prompt for AI agents

Implement Phase 2: update manifest lowering to build the canonical edge model,
while keeping duplicate-output rejection working exactly as before.

- In `src/ir/from_manifest_support.rs`, rewrite `insert_edge_for_outputs` to
push the edge once into the arena and map every explicit output to the resulting
`EdgeId`, using the new `BuildGraph` insertion accessor added in Phase 1. Remove
the old clone-per-output loop.
- Preserve exactly one canonical `explicit_outputs` vector per logical edge; do
not duplicate it.
- Keep `duplicate_output_error` and `find_duplicates` running before insertion,
so the graph is never mutated when a duplicate output is detected.
- Update `find_duplicates` to accept the new `targets: IrHashMap<Utf8PathBuf,
EdgeId>` type for its cross-target `contains_key` check. Leave the within-target
`seen` scan logic unaffected by this type change.
- Leave `register_action` unchanged, since its content-hash dedup already owns
each `Action` once.

Phase 3: Update downstream consumers

Retarget every reader of the old storage model to the new arena and index. Remove the value-recovery deduplication that the old model forced.

Task 1: Retarget cycle and missing-dependency analysis

Preserve cycle detection across every output alias.

• Update CycleDetector in src/ir/cycle_detector.rs to borrow both the index map and the edge arena, or to borrow &BuildGraph.
• Update target_entry_for_path in src/ir/cycle_support.rs to resolve an output path to EdgeId, then index the arena, returning (&Utf8Path, &BuildEdge).
• Enumerate cycle nodes from the output-path index keys, so every output alias remains a graph node.
• Update the cycle::analyse call site in src/ir/from_manifest.rs to pass the new inputs.

Task 2: Emit Ninja and dyndep from canonical edges

Iterate the arena directly and remove the path_key deduplication.

• Update generate_into_with_shell in src/ninja_gen/mod.rs to iterate the canonical edge arena. Remove the HashSet<String> dedup keyed by path_key.
• Sort edges by path_key(&edge.explicit_outputs) to preserve deterministic output order.
• Apply the same change in render_edges in src/ninja_gen/dyndep.rs, and keep parent_identity and validation scans working against canonical edges.
• Confirm that exactly one build statement is emitted per canonical edge containing all explicit outputs.

Task 3: Update graph view, help, and telemetry

Remove the workaround dedup and correct the count semantics.

• Update collect_unique_edges in src/graph_view/mod.rs to iterate the canonical edge arena directly, removing the sorted-output BTreeMap dedup.
• Update instrument_bundle_generation in src/runner/dyndep_generation_telemetry.rs so target_count and the dependency_count sum are computed over canonical edges, not over duplicated output entries.
• Verify runner/help_query.rs still only uses BuildGraph::from_manifest for validation side effects; no field change is needed there.

Task 4: Update the Kani model and harnesses

Keep the bounded proofs valid under the new storage shape.

• Update src/ir/graph_kani_map.rs so the bounded map supports the IrHashMap<Utf8PathBuf, EdgeId> index, and add a bounded arena representation for edges if required by the harnesses.
• Update the edge(...) helpers and IrHashMap<Utf8PathBuf, BuildEdge> signatures in src/ir/cycle_verification.rs (and any duplicated helper in src/ir/cycle_tests.rs) to build the arena plus index and to bound the arena length.
• Keep IrMapKeyEq correct for EdgeId value comparison, which is trivial for a usize newtype.

🤖 Prompt for AI agents

Implement Phase 3: retarget every downstream consumer of the old
per-output-clone storage to the new arena plus index model, and remove the
value-recovery deduplication the old model forced.

Cycle and missing-dependency analysis:
- Update `CycleDetector` in `src/ir/cycle_detector.rs` to borrow both the index
map and the edge arena, or to borrow `&BuildGraph` directly.
- Update `target_entry_for_path` in `src/ir/cycle_support.rs` to resolve an
output path to `EdgeId` first, then index the arena, returning `(&Utf8Path,
&BuildEdge)`.
- Enumerate cycle nodes from the output-path index keys, so every output alias
remains a graph node.
- Update the `cycle::analyse` call site in `src/ir/from_manifest.rs` to pass the
new inputs.

Ninja and dyndep generation:
- Update `generate_into_with_shell` in `src/ninja_gen/mod.rs` to iterate the
canonical edge arena directly. Remove the `HashSet<String>` dedup keyed by
`path_key`.
- Sort edges by `path_key(&edge.explicit_outputs)` to preserve deterministic
output order.
- Apply the equivalent change in `render_edges` in `src/ninja_gen/dyndep.rs`,
keeping `parent_identity` and validation scans working correctly against
canonical edges.
- Confirm that exactly one `build` statement is emitted per canonical edge, and
that it contains all explicit outputs for that edge.

Graph view, help, and telemetry:
- Update `collect_unique_edges` in `src/graph_view/mod.rs` to iterate the
canonical edge arena directly, removing the sorted-output `BTreeMap` dedup
workaround.
- Update `instrument_bundle_generation` in
`src/runner/dyndep_generation_telemetry.rs` so `target_count` and the
`dependency_count` sum are computed over canonical edges, not over duplicated
output entries.
- Verify `runner/help_query.rs` still only uses `BuildGraph::from_manifest` for
validation side effects; make no field change there.

Kani model and harnesses:
- Update `src/ir/graph_kani_map.rs` so the bounded map supports the
`IrHashMap<Utf8PathBuf, EdgeId>` index, and add a bounded arena representation
for `edges` if the harnesses require it.
- Update the `edge(...)` helpers and `IrHashMap<Utf8PathBuf, BuildEdge>`
signatures in `src/ir/cycle_verification.rs`, and any duplicated helper in
`src/ir/cycle_tests.rs`, to build the arena plus index and to bound the arena
length.
- Keep `IrMapKeyEq` correct for `EdgeId` value comparison; this is trivial for a
`usize` newtype.

Phase 4: Tests, benchmark, and documentation

Prove the linear storage property, keep every consumer test green, and describe the new model.

Task 1: Add a structural linearity test

Prove O(N) storage without depending on timing.

• Add a test that lowers a manifest target with N explicit outputs and asserts the arena holds exactly one BuildEdge.
• Assert that the canonical edge holds one explicit_outputs vector of length N, and that the index holds N entries all resolving to the same EdgeId.
• Place this test with the IR lowering tests in tests/ir_from_manifest_tests.rs.

Task 2: Update fixtures and count assertions

Reconcile the two divergent notions of "count".

• Update tests and fixtures that call graph.targets.insert(path, BuildEdge{...}) to use the new BuildGraph insertion accessor. This affects tests/ir_tests.rs, src/runner/tests.rs, test_support/src/ninja_gen.rs, and the ninja_gen unit, property, and integration test files.
• Update tests/bdd/steps/ir.rs so the Then the graph has {count} targets step and the graph.targets/graph.targets.values() lookups resolve through the new accessors, and decide whether "targets" counts output aliases or canonical edges. Keep the chosen meaning consistent with the Gherkin scenarios.
• Update count assertions in tests/ir_from_manifest_tests.rs and tests/ir_from_manifest_tests/dependency_order.rs to match the new semantics.

Task 3: Add an IR-construction stress benchmark

Demonstrate linear work at scale.

• Add benches/ir_construction.rs following the existing #![feature(test)] / extern crate test; / Bencher / black_box pattern used in benches/config_load_cached_merge.rs.
• Build, outside the timed closure, a NetsukeManifest with a target that has thousands of outputs.
• Time BuildGraph::from_manifest inside bencher.iter. No new dependency is required; Cargo autobench discovery picks up the file.

Task 4: Update the design documentation

Describe canonical edge identity and output indexing.

• Update docs/netsuke-design.md §5.2 code sample and Mermaid class diagram to show the edge arena and the output -> EdgeId index.
• Rewrite the §5.3 transformation narrative that states the edge is "attached to every explicit output" to describe one canonical edge referenced by many output aliases.
• Revise the §5.5 bullet about generator-side dedup to state that canonical identity now removes the need for it.

🤖 Prompt for AI agents

Implement Phase 4: prove the O(N) storage property, keep every consumer test
green under the new semantics, add a stress benchmark, and update the design
documentation.

Structural linearity test:
- Add a test that lowers a manifest target with `N` explicit outputs and asserts
the arena holds exactly one `BuildEdge`.
- Assert the canonical edge holds one `explicit_outputs` vector of length `N`,
and that the index holds `N` entries, all resolving to the same `EdgeId`.
- Place this test alongside the IR lowering tests in
`tests/ir_from_manifest_tests.rs`.

Fixtures and count assertions:
- Update tests and fixtures that call `graph.targets.insert(path,
BuildEdge{...})` to use the new `BuildGraph` insertion accessor instead. This
affects `tests/ir_tests.rs`, `src/runner/tests.rs`,
`test_support/src/ninja_gen.rs`, and the `ninja_gen` unit, property, and
integration test files.
- Update `tests/bdd/steps/ir.rs` so the `Then the graph has {count} targets`
step, and the `graph.targets`/`graph.targets.values()` lookups, resolve through
the new accessors. Decide whether "targets" counts output aliases or canonical
edges, and keep the chosen meaning consistent with the Gherkin scenarios.
- Update count assertions in `tests/ir_from_manifest_tests.rs` and
`tests/ir_from_manifest_tests/dependency_order.rs` to match the new semantics.

Stress benchmark:
- Add `benches/ir_construction.rs`, following the existing `#![feature(test)]` /
`extern crate test;` / `Bencher` / `black_box` pattern used in
`benches/config_load_cached_merge.rs`.
- Build a `NetsukeManifest` with a target that has thousands of outputs outside
the timed closure.
- Time `BuildGraph::from_manifest` inside `bencher.iter`. Do not add a new
dependency; Cargo autobench discovery picks up the file automatically.

Design documentation:
- Update `docs/netsuke-design.md` §5.2 code sample and Mermaid class diagram to
show the edge arena and the `output -> EdgeId` index.
- Rewrite the §5.3 transformation narrative that states the edge is "attached to
every explicit output", to instead describe one canonical edge referenced by
many output aliases.
- Revise the §5.5 bullet about generator-side dedup, to state that canonical
identity now removes the need for it.

Research

The IR lives under src/ir/. graph.rs defines BuildGraph and BuildEdge. BuildGraph.targets is a public IrHashMap<Utf8PathBuf, BuildEdge> keyed by output path. from_manifest.rs builds one BuildEdge per manifest target, and from_manifest_support.rs::insert_edge_for_outputs clones that edge once per explicit output.

Downstream consumers (cycle_detector.rs, ninja_gen/mod.rs, ninja_gen/dyndep.rs, graph_view/mod.rs) each iterate targets.values() and re-derive a canonical identity from explicit_outputs to remove the duplicates.

Kani harnesses in cycle_verification.rs and the bounded map in graph_kani_map.rs model the current IrHashMap<Utf8PathBuf, BuildEdge> shape.

Benchmarks under benches/ use the built-in nightly test harness.

BuildEdge/BuildGraph derive no Serialize and are never compared whole with assert_eq!.

---

🚀 Next Steps

🤖 All AI agent prompts combined

Task: 1

Implement Phase 1: redefine the canonical edge storage model in the IR core. The
goal is to own each `BuildEdge` once in an arena and index every output path to
a stable edge identifier, replacing the current per-output clone model.

- In `src/ir/graph.rs`, add a public `EdgeId` newtype that wraps `usize`. Derive
`Debug, Clone, Copy, PartialEq, Eq, Hash` on it.
- Change `BuildGraph` so it holds `edges: Vec<BuildEdge>` as the arena, and
`targets: IrHashMap<Utf8PathBuf, EdgeId>` as the output-to-edge index. Leave
`actions` and `default_targets` unchanged.
- Keep `BuildEdge`'s existing fields and its `Debug, Clone, PartialEq` derives
unchanged; do not add `Serialize`, `Eq`, or `Hash` to it.
- Re-export `EdgeId` from `src/ir/mod.rs` alongside the existing `BuildEdge` and
`BuildGraph` exports.
- Add a `BuildGraph` method that pushes one `BuildEdge` into `edges` and maps
every path in its `explicit_outputs` to the resulting `EdgeId`. This method
replaces the fan-out clone behaviour used previously.
- Add a lookup accessor that takes an output `&Utf8Path` and resolves it through
the index and arena to `(&Utf8Path, &BuildEdge)`, preserving the canonical
stored key semantics relied on by cycle detection.
- Add an iterator accessor over the canonical edges in the arena, for use by
Ninja generation, dyndep generation, and graph views.
- Add an iterator accessor over the output paths in the index, for use by
cycle-node enumeration.
===============================================================================

Task: 2

Implement Phase 2: update manifest lowering to build the canonical edge model,
while keeping duplicate-output rejection working exactly as before.

- In `src/ir/from_manifest_support.rs`, rewrite `insert_edge_for_outputs` to
push the edge once into the arena and map every explicit output to the resulting
`EdgeId`, using the new `BuildGraph` insertion accessor added in Phase 1. Remove
the old clone-per-output loop.
- Preserve exactly one canonical `explicit_outputs` vector per logical edge; do
not duplicate it.
- Keep `duplicate_output_error` and `find_duplicates` running before insertion,
so the graph is never mutated when a duplicate output is detected.
- Update `find_duplicates` to accept the new `targets: IrHashMap<Utf8PathBuf,
EdgeId>` type for its cross-target `contains_key` check. Leave the within-target
`seen` scan logic unaffected by this type change.
- Leave `register_action` unchanged, since its content-hash dedup already owns
each `Action` once.
===============================================================================

Task: 3

Implement Phase 3: retarget every downstream consumer of the old
per-output-clone storage to the new arena plus index model, and remove the
value-recovery deduplication the old model forced.

Cycle and missing-dependency analysis:
- Update `CycleDetector` in `src/ir/cycle_detector.rs` to borrow both the index
map and the edge arena, or to borrow `&BuildGraph` directly.
- Update `target_entry_for_path` in `src/ir/cycle_support.rs` to resolve an
output path to `EdgeId` first, then index the arena, returning `(&Utf8Path,
&BuildEdge)`.
- Enumerate cycle nodes from the output-path index keys, so every output alias
remains a graph node.
- Update the `cycle::analyse` call site in `src/ir/from_manifest.rs` to pass the
new inputs.

Ninja and dyndep generation:
- Update `generate_into_with_shell` in `src/ninja_gen/mod.rs` to iterate the
canonical edge arena directly. Remove the `HashSet<String>` dedup keyed by
`path_key`.
- Sort edges by `path_key(&edge.explicit_outputs)` to preserve deterministic
output order.
- Apply the equivalent change in `render_edges` in `src/ninja_gen/dyndep.rs`,
keeping `parent_identity` and validation scans working correctly against
canonical edges.
- Confirm that exactly one `build` statement is emitted per canonical edge, and
that it contains all explicit outputs for that edge.

Graph view, help, and telemetry:
- Update `collect_unique_edges` in `src/graph_view/mod.rs` to iterate the
canonical edge arena directly, removing the sorted-output `BTreeMap` dedup
workaround.
- Update `instrument_bundle_generation` in
`src/runner/dyndep_generation_telemetry.rs` so `target_count` and the
`dependency_count` sum are computed over canonical edges, not over duplicated
output entries.
- Verify `runner/help_query.rs` still only uses `BuildGraph::from_manifest` for
validation side effects; make no field change there.

Kani model and harnesses:
- Update `src/ir/graph_kani_map.rs` so the bounded map supports the
`IrHashMap<Utf8PathBuf, EdgeId>` index, and add a bounded arena representation
for `edges` if the harnesses require it.
- Update the `edge(...)` helpers and `IrHashMap<Utf8PathBuf, BuildEdge>`
signatures in `src/ir/cycle_verification.rs`, and any duplicated helper in
`src/ir/cycle_tests.rs`, to build the arena plus index and to bound the arena
length.
- Keep `IrMapKeyEq` correct for `EdgeId` value comparison; this is trivial for a
`usize` newtype.
===============================================================================

Task: 4

Implement Phase 4: prove the O(N) storage property, keep every consumer test
green under the new semantics, add a stress benchmark, and update the design
documentation.

Structural linearity test:
- Add a test that lowers a manifest target with `N` explicit outputs and asserts
the arena holds exactly one `BuildEdge`.
- Assert the canonical edge holds one `explicit_outputs` vector of length `N`,
and that the index holds `N` entries, all resolving to the same `EdgeId`.
- Place this test alongside the IR lowering tests in
`tests/ir_from_manifest_tests.rs`.

Fixtures and count assertions:
- Update tests and fixtures that call `graph.targets.insert(path,
BuildEdge{...})` to use the new `BuildGraph` insertion accessor instead. This
affects `tests/ir_tests.rs`, `src/runner/tests.rs`,
`test_support/src/ninja_gen.rs`, and the `ninja_gen` unit, property, and
integration test files.
- Update `tests/bdd/steps/ir.rs` so the `Then the graph has {count} targets`
step, and the `graph.targets`/`graph.targets.values()` lookups, resolve through
the new accessors. Decide whether "targets" counts output aliases or canonical
edges, and keep the chosen meaning consistent with the Gherkin scenarios.
- Update count assertions in `tests/ir_from_manifest_tests.rs` and
`tests/ir_from_manifest_tests/dependency_order.rs` to match the new semantics.

Stress benchmark:
- Add `benches/ir_construction.rs`, following the existing `#![feature(test)]` /
`extern crate test;` / `Bencher` / `black_box` pattern used in
`benches/config_load_cached_merge.rs`.
- Build a `NetsukeManifest` with a target that has thousands of outputs outside
the timed closure.
- Time `BuildGraph::from_manifest` inside `bencher.iter`. Do not add a new
dependency; Cargo autobench discovery picks up the file automatically.

Design documentation:
- Update `docs/netsuke-design.md` §5.2 code sample and Mermaid class diagram to
show the edge arena and the `output -> EdgeId` index.
- Rewrite the §5.3 transformation narrative that states the edge is "attached to
every explicit output", to instead describe one canonical edge referenced by
many output aliases.
- Revise the §5.5 bullet about generator-side dedup, to state that canonical
identity now removes the need for it.

💡 Iterate on the plan with: `@coderabbitai` <feedback>

Example Feedback
- `@coderabbitai` You can skip phase 3. Add a simple unit test case for phase 2.
- `@coderabbitai` For design choice 1 go ahead with option 3 and replan.

---