apache / apache/maven-dependency-tree

SerializingDependencyNodeVisitor is O(N * depth^2) / O(N^3) for deep graphs

Open
#131 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.