Re: [pkg.m] Load order of dependencies

[Andrew Janke]

Sorry if this is a re-send; my mail client screwed up when I was
originally writing this.

On 12/10/19 11:57 AM, PhilipNienhuis wrote:
> apjanke-floss wrote
>> On 12/9/19 3:39 PM, PhilipNienhuis wrote:> JuanPi wrote
>>
>> 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?

Circular dependencies; ouch. I've done some work on package managers,
and my view is that they're an insoluble problem. Probably, build-time
circular dependencies need to be prohibited, and run-time circulars,
well, just pick an arbitrary order based on what you find during the
dependency graph traversal, prune the traversal when you hit a cycle,
and hope it works.

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

Agreed. You need that 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.

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

I don't think this is correct. The order you get now from the recursive
loading is a "pre-order" traversal of the dependency graph. Reversing
that list gives you _a_ "post-order" solution. But it doesn't
necessarily handle the case of indirect dependencies which might have
complex dependencies between them. You need to do a modified post-order
traversal *with backtracking* to handle the case of dependencies between
indirect dependencies. It's non-trivial.

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

Cheers,
Andrew