<< Back to previous view

[TNS-20] tracker's unload order sometimes incorrect Created: 23/Aug/14  Updated: 20/Sep/14

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

Type: Defect Priority: Major
Reporter: Andy Fingerhut Assignee: Stuart Sierra
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File tns-20-v1.patch     Text File tns-20-v2.patch    

 Description   

The attached patch contains a new test namespace clojure.tools.namespace.load-unload-order-test that demonstrates the incorrect unload order, if you leave out the proposed fix in file track.clj



 Comments   
Comment by Andy Fingerhut [ 23/Aug/14 3:02 PM ]

Patch tns-20-v1.patch contains a test that demonstrates the bug, and contains a proposed fix. Please scrutinize the proposed fix carefully, as I haven't yet convinced myself 100% that it is the right fix.

Also adds one more dependency check in dependency_test.clj that I discovered while reviewing those tests, to model my dependency checking tests on.

Comment by Andy Fingerhut [ 24/Aug/14 4:52 PM ]

I've got some code that checks that the load and unload orders in a tools.namespace tracker are consistent with its dependencies. It is similar to the checks done now in dependencies_test.clj, except it assumes that the dependencies in the tracker are correct and verifies the load and unload orders against those.

If you would be interested in a patch that added these checks to tools.namespace, perhaps along with a debug/consistency-check flag that when true causes these checks to be run every time a tracker is updated, let me know.

Comment by Stuart Sierra [ 07/Sep/14 11:11 AM ]

Thanks for this, Andy. I will need to study it further to convince myself this is the correct behavior.

To help, can you describe what the observed problem would be from a user's point of view?

We cannot assume that the dependencies in the tracker are always correct. I have demonstrable cases where they are wrong. Usually that takes the form of nonexistent namespaces left in the dependency graph from files that were deleted or had an invalid ns declaration.

Comment by Andy Fingerhut [ 07/Sep/14 8:10 PM ]

I have not used tools.namespace for the reload workflow that it was originally developed for, so I can't say with certainty what the effect on a user would be, but I can make some guesses that you can probably confirm more quickly than I can.

The test case in the patch is one where a few Clojure source files are added to a tracker using function c.t.n.dir/scan-all. No other changes are made to the tracker. At that point, the dependencies are completely correct, and the load order calculated from those dependencies honors them, but the unload order does not.

If that tracker were then used in a call to c.t.n.reload/track-reload, track-reload would call remove-lib on a library B before calling remove-lib on a library A, even though A requires or uses B.

I guess your question confuses me a bit. Do you believe tools.namespace should only create trackers that have load and unload orders that honor the dependencies? Or is that a wrong assumption I was making from reading the implementation?

Comment by Andy Fingerhut [ 08/Sep/14 5:52 PM ]

Attaching slightly cleaned up patch tns-20-v2.patch. Identical to tns-20-v1.patch except it avoids copying a function into the new test namespace by adding a dependency on the test namespace where it is defined.

Also updates the name of a deftest I had copied but not renamed in v1 of the patch.

Comment by Stuart Sierra [ 19/Sep/14 4:19 PM ]

I think I'm starting to get a handle on this. There's a lot going on here, and it's been more than two years since I wrote most of this code, so bear with me.

At track.clj line 78 we compute the dependency order for unloading namespaces based on the dependency graph (the local deps) as it existed before the most recent set of changes. I believe that this is correct, or at least the correct intention. If we change a file such that its dependencies are different, the order in which we unload namespaces should reflect the namespaces in memory, as they were before we changed the file.

When using c.t.n.dir/scan to detect and reload changed files this works correctly, at least most of the time.

When adding files to a new tracker for the first time, the old dependency graph is empty, so the unload order is undefined. This is arguably incorrect but effectively meaningless, since those namespaces have not yet been loaded.

In release 0.2.6, there was a bad commit which mistakenly changed c.t.n.dir/scan and scan-all to remove the files which have changed before adding them again. As a result, the dependencies of changed files were removed from the tracker's dependency graph before the unload order could be calculated, so unload order was always undefined. I have reverted that change — thanks for drawing my attention to it!

Now the unload order should be "correct" after scan or scan-all, except for the first time files are added to the tracker, when unload order is undefined.

The tracker doesn't currently have a way to distinguish between changed files which need unload+load and new files which only need load. Even if there were a way to distinguish between new and changed files, we can't be certain that a namespace has not been loaded by other means (e.g. require at the REPL) so it's safest to unload everything before reloading.

In general, unload order shouldn't matter at all. Clojure doesn't care when namespaces are removed: the Vars are still referenced from wherever they are used.

Comment by Andy Fingerhut [ 20/Sep/14 1:08 PM ]

OK, makes sense. Is it already documented anywhere that the unload order is independent of the dependencies after scan-all (and perhaps other calls)? I can create a separate ticket for that if you think it is worth adding such documentation.

It sounds like for the application I had in mind, the reverse of the load order is always defined, and is a correct unload order. You are welcome to close this ticket.





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

Status: Closed
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.

Comment by Stuart Sierra [ 19/Sep/14 9:08 AM ]

Included in release 0.2.6





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

Status: Closed
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.

Comment by Stuart Sierra [ 19/Sep/14 9:08 AM ]

Included in release 0.2.6





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

Status: Closed
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.

Comment by Stuart Sierra [ 19/Sep/14 9:08 AM ]

Included in release 0.2.6





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

Status: Closed
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.

Comment by Stuart Sierra [ 19/Sep/14 9:08 AM ]

Included in release 0.2.6





[TNS-25] A few doc string typos Created: 09/Sep/14  Updated: 19/Sep/14  Resolved: 19/Sep/14

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

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

Attachments: Text File tns-25-v1.patch    
Patch: Code

 Description   

Attached patch corrects a few misspellings in tools.namespace doc strings



 Comments   
Comment by Stuart Sierra [ 19/Sep/14 9:06 AM ]

Applied in https://github.com/clojure/tools.namespace/commit/09e1e1fd81faed4e24399bf68bf78e87b32eb68b

Thanks.





Generated at Tue Sep 23 15:39:12 CDT 2014 using JIRA 4.4#649-r158309.