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 demo-exponential-algo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.
Patch linear-time-no-debug.patch is one way to implement transitive dependencies in linear time. It also introduces additional protocol functions, which may not be desired. I am definitely open to suggestions on what kind of change you would like to see here (assuming you want any changes at all).
This is a valuable improvement — thanks, Andy!
I don't want to add more methods to the protocol, but I don't see any way to avoid it right now. Ideally, transitive-dependencies would change to take a set, but that breaks backwards-compatibility.
I'll give it a week or so to think about naming:
transitive-dependencies-of-node-set is too long
Included in release 0.2.6