Details

Type: Enhancement

Status: Closed

Priority: Major

Resolution: Completed

Affects Version/s: None

Fix Version/s: None

Component/s: None

Labels:None

Patch:Code
Description
The function clojure.tools.namespace.dependency/transitive takes exponential time for cases where there are an exponential number of paths in the DAG (directed acyclic graph) of dependencies. I discovered this when using tools.namespace on the namespaces of project core.typed, where the total time for finding a topological order was several minutes on a reasonably fast machine.
It is easy to calculate transitive dependents/dependencies in linear time in the worst case (linear in the number of dependency arcs in the DAG).
Patch demoexponentialalgo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.