apache / apache/maven-dependency-tree
SerializingDependencyNodeVisitor is O(N * depth^2) / O(N^3) for deep graphs
- Dominant language
- Java
- Stars
- 27
- Forks
- 31
- Avg merge
- 5h 53m
- Merged PRs (30d)
- 1
Description
## Summary
`SerializingDependencyNodeVisitor` re-derives ancestor “is last sibling” state on every node by walking back up the tree, making output linear in node count only for shallow graphs and roughly cubic for deep chains.
## Affected code
`src/main/java/org/apache/maven/shared/dependency/graph/traversal/SerializingDependencyNodeVisitor.java`
- `indent(...)` calls `isLast(node, i)` for every ancestor level: lines 161-169
- `isLast(node, i)` walks up `(depth - i)` parents each time: lines 202-212
- `isLast(node)` scans `siblings.indexOf(node)`: lines 177-193
## Impact
Per-node work is ~depth², so a deep chain of N nodes costs ~N³ pointer walks (a 10k-deep chain is on the order of 10¹² steps). Wide trees degrade to quadratic via `indexOf` on long sibling lists. This is the dominant cost when printing `mvn dependency:tree`.
## Suggested fix
Maintain the ancestor fill-indent state incrementally during the pre-order walk (push/pop “is last” per level) instead of recomputing it per node, and avoid `siblings.indexOf` by tracking the last-visited sibling index.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with src/main/java/org/apache/maven/shared/dependency/graph/traversal/SerializingDependencyNodeVisitor.java, reading indent(...) and isLast(...) at the cited lines. Trace the pre-order walk and existing output behavior, then verify that ancestor state and sibling positions are maintained incrementally without repeated deep walks or scans, while serialized output remains unchanged.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- build-system
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 58/100