Re: [pkg.m] Load order of dependencies

[Andrew Janke]

On 12/10/19 11:57 AM, PhilipNienhuis wrote:
> apjanke-floss wrote
>> On 12/9/19 3:39 PM, PhilipNienhuis wrote:> JuanPi wrote
>>> Philip
>>
>> I would think that the dependencies of package A should be loaded before
>> A, because A's startup/teardown code (in PKG_ADD or PKG_DEL) might use
>> functions/classes provided by its dependencies?
> 
> Sure, that feels like the obvious. But pkg.m as it stands just doesn't work
> that way.
> 
> Moreover, dependencies aren't always so "linear".
> ISTR there were (or are?) circular dependencies. Or mutual exclusive
> dependencies (example: package A depends on release "X" of package B, but
> package C won't work with release "X" and depends on another release of B). 
> And maybe someone loaded package D that also depends on package C and thus
> implicitly loaded it, and now wants to also use package A. What should pkg.m
> do then?
> In short, there could be an almost infinite number of scenario's for
> interdependencies that all need to be catered for (if only by informing
> users of incompatibilities) in a proper package management system.

Circular dependencies, ouch. I've done a fair amount of work with
package managers, and my view is that circular dependencies are
fundamentally an insoluble problem. Build-time circular dependencies
probably need to be prohibited. Run-time circular dependencies, just
load them in the order you find them doing a depth-first search through
the dependency graph, pruning the search and issuing a warning when you
get to a circularity.

> IMO the "-nodeps" flag is a rough but indispensable escape to somehow deal
> with this.

Agreed. You need to have a back door for cases like this.

> Anyway, from what I learned recently when I dived in pkg.m, it is quite a
> cleverly written piece of code, but apparently it never got completely
> polished. Several small gotchas and corner case issues are still hidden here
> and there. My guess is that the cause lies partly in the complexity I
> touched upon above.
> 
> As to the problem at hand:
> AFAICS (but correct me if I'm wrong) "loading" a package involves nothing
> more than just adding its code directories (.m, .oct/.mex) to the path.
> PKG_ADD code automatically takes care of the package init scripts.
> So, this whole issue of JuanPi it is really just about the order in which
> package directories *happen* to be added to the path.

This is correct AFAIK, too.

> Now, load_packages_and_directories.m first adds the directory of a package
> to that list and only then dives in the dependencies and adds them one by
> one, if needed recursively if dependencies themselves also happen to have
> dependencies, and so on.  So *I think* merely reversing the final list
> before handing it to the code that adds the package dirs to the path would
> solve it in one fell swoop, so to say.
> Again, I could be wrong - it just needs to be tried and I only have time for
> that later this week or weekend.

This doesn't quite work, I think. The list you get now is a "pre-order"
traversal of the dependency graph. Reversing it gives you _a_
"post-order" solution, but it doesn't guarantee the correct ordering of
indirect dependencies which themselves might have dependencies on each
other. To get a proper "all dependencies first" load order, you need to
do a traversal through the dependency graph *with backtracking* to
handle dependencies between indirect dependencies. It's non-trivial.

One (incomplete) approach looks like this:
https://github.com/apjanke/octave-packajoozle/blob/efa4ac816bfcc51a674a0e426efb1417d4133896/inst/%2Bpackajoozle/%2Binternal/DependencyResolver.m#L75

Cheers,
Andrew