Query and Indexing Performance
The traceability graph SHALL provide forward, reverse, and inverse relationship indexes enabling O(1) lookup by item ID.
Path finding SHALL use BFS with configurable maxDepth.
Result caching SHALL be used with invalidation on mutation to avoid redundant computation during repeated queries within a single processing session.
Source: examples/tracer/modules/ROOT/partials/04-solution-strategy.adoc (ARC-011)
Context
During an Antora build, the traceability graph is queried repeatedly — for link substitution, macro expansion, matrix generation, and validation. For large projects with hundreds of items and thousands of relationships, O(n) lookup per query would make the build unacceptably slow.
Trigger
An Antora build processes a project with hundreds of items. The extension’s graph query methods are invoked thousands of times during macro expansion and matrix generation.
Acceptance Criteria
- O(1) item and relationship lookup
-
Items and relationships are stored in Maps keyed by ID, providing constant-time lookup by ID; source:
TraceabilityGraphimplementation; horizon: every release. - Reverse relationship index
-
An inverse index maps target IDs to their incoming relationships for constant-time reverse lookup; source:
getReverseRelationships()method; horizon: every release. - Configurable BFS depth
-
Path finding via
findPath()accepts an optionalmaxDepthparameter to limit traversal; source:findPath()method; horizon: every release. - Caching with invalidation
-
Computed results (e.g., role index) are cached until the graph is mutated, at which point the cache is invalidated; source:
TraceabilityGraphimplementation; horizon: every release.