<< Back to previous view

[TNS-18] Use linear time algorithm to calculate transitive dependencies, instead of current exponential time algorithm Created: 03/Jun/14  Updated: 11/Jul/14  Resolved: 11/Jul/14

Status: Resolved
Project: tools.namespace
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Andy Fingerhut Assignee: Stuart Sierra
Resolution: Completed Votes: 0
Labels: None

Attachments: Text File demo-exponential-algo.patch     Text File linear-time-no-debug.patch    
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).



 Comments   
Comment by Andy Fingerhut [ 03/Jun/14 3:18 PM ]

Patch demo-exponential-algo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.

Comment by Andy Fingerhut [ 03/Jun/14 3:20 PM ]

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).

Comment by Stuart Sierra [ 06/Jun/14 10:27 AM ]

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
  • transitive-dependencies-all ?
  • transitive-dependencies-set ?
  • all-transitive-dependencies ?
Comment by Stuart Sierra [ 11/Jul/14 4:42 PM ]

Merged on master as of commit 3f946380. Will be in release 0.2.5.

New functions are named transitive-dependencies-set and transitive-dependents-set.





[TNS-16] Some tests depend upon Clojure hash for ordering Created: 30/Jan/14  Updated: 31/Jan/14  Resolved: 31/Jan/14

Status: Resolved
Project: tools.namespace
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Andy Fingerhut Assignee: Stuart Sierra
Resolution: Completed Votes: 0
Labels: None

Attachments: File tns-16-v1.diff    

 Description   

In particular there are several that do a topological sort of a dependency graph, and compare the returned node sequence against a single node order. In general there are many correct results for a topological sort, and the implementation's return order depends upon Clojure's hash function, recently changed.



 Comments   
Comment by Andy Fingerhut [ 30/Jan/14 9:40 AM ]

Patch tns-16-v1.diff is one way to make the tests independent of Clojure's hash function. It implements a topo-check function that determines whether a particular node sequence order is in a valid dependency order, i.e. is a subsequence of at least one topological sorting of the nodes.

Comment by Stuart Sierra [ 31/Jan/14 9:09 AM ]

Given that the current tests only use very small, hand-drawn graphs, I'm going to go with the brute-force approach for now.

But thanks for this patch. I'd like to hold on to it for possible future use with generated graphs and/or test.check.





[TNS-19] deps-from-ns-decl can return nil Created: 06/Jun/14  Updated: 11/Jul/14  Resolved: 11/Jul/14

Status: Resolved
Project: tools.namespace
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Ambrose Bonnaire-Sergeant Assignee: Stuart Sierra
Resolution: Completed Votes: 0
Labels: None


 Description   

I expect this to be #{}.

(ns-parse/deps-from-ns-decl '(ns cljs.core.typed "Internal functions for CLJS" (:refer-clojure :exclude [IFn]) (:require-macros [clojure.core.typed.bootstrap-cljs :as boot])))
;=> nil


 Comments   
Comment by Stuart Sierra [ 13/Jun/14 5:04 PM ]

Fixed in commit e9394727 on Git master. Please verify.

Comment by Stuart Sierra [ 11/Jul/14 4:42 PM ]

Merged on Git master; will be in 0.2.5 release.





[TNS-17] doesn't track namespace when ns decl isn't first in file Created: 04/Feb/14  Updated: 11/Jul/14  Resolved: 11/Jul/14

Status: Resolved
Project: tools.namespace
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Trevor Wennblom Assignee: Stuart Sierra
Resolution: Completed Votes: 0
Labels: bug, enhancement


 Description   

This was first filed for ns-tracker https://github.com/weavejester/ns-tracker/issues/15 but I understand it's more specific to tools.namespace.

(I realize this is likely a very low priority, but it'd still be nice to see fixed if possible. Thanks!)


It appears ns-tracker tools.namespace will cease following a namespace when there's non-commented content before the namespace declaration.

works:

;-begin
(ns myproject.core)
(println "hi")
;-end

untracked — (any of the four possibilities when uncommented, for example):

;-begin
1
;;; (println "before ns")
;;; (println "loading" *file*)
;;; :abc
(ns myproject.core)
(println "hi")
;-end


 Comments   
Comment by Stuart Sierra [ 13/Jun/14 4:43 PM ]

What's the use case for having a file in which the ns declaration isn't the first non-comment form?

Comment by Trevor Wennblom [ 13/Jun/14 5:53 PM ]

In the case that triggered the issue for me, it can be useful to see the load-order of files based on the dependencies given in ns for debugging. That is, to print a message before and after the completion of loading the namespace dependencies.

I'm not sure how difficult or involved the issue would be to solve.

Comment by Andy Fingerhut [ 13/Jun/14 6:42 PM ]

Would the :verbose option to require perhaps give you the load-order info you want? Try something like this at a REPL, with a namespace you care about:

(require '[clojure.core.typed :as ct] :verbose)

In general, I think Stuart's concern would be questions like: How many forms would you expect tools.namespace to skip over before giving up? If it is a fixed number of forms before it gives up, why that number and not some other?

If it is based upon some other condition to give up looking for an ns form, what would that condition be?

Or would you expect it to be able to find the ns form in the body of a 'when' or 'if' form, and not at the top level?

The criteria can easily start to sound kind of arbitrary, and/or complex to implement.

Comment by Stuart Sierra [ 11/Jul/14 5:04 PM ]

Fixed on master as of commit 3c08b722. This turned out to be an easy change.

I wouldn't recommend putting anything before the ns declaration, but it's no longer required to be first. A file could also have multiple ns declarations, although clojure.tools.namespace.track will only look at the first one.





Generated at Tue Jul 29 05:46:22 CDT 2014 using JIRA 4.4#649-r158309.