3 ms·
Okay, so i'm reading the minimal version selection algorithm article [1], and there's either a flaw, or something i don't get. Here's a modified version of the
by twic 9y ago
Okay, so i'm reading the minimal version selection algorithm article [1], and there's either a flaw, or something i don't get.
Here's a modified version of the example graph, written as pidgin DOT [2]:
A -> B1.2
A -> C1.2
B1.2 -> D1.3
C1.2 -> D1.4
D1.3 -> X1.1
D1.4 -> Y1.1
The key thing here is that D1.3 depended on X1.1, but the new D1.4 depends on Y1.1 instead. I guess X is old and busted, and Y is the new hotness.
What is the build list for A?
Russ says:
The rough build list for M is also just the list of all modules reachable in the requirement graph starting at M and following arrows.
And:
Simplify the rough build list to produce the final build list, by keeping only the newest version of any listed module.
The list of all modules reachable from A is B1.2, C1.2, D1.3, D1.4, X1.1, and Y1.1, so that's the rough build list. The list of the newest versions of each module is B1.2, C1.2, D1.4, X1.1, and Y1.1, so that's the build list.
The build list contains X1.1, even though it is not needed.
Really?
[1] https://research.swtch.com/vgo-mvs https://research.swtch.com/vgo-mvs
[2] https://www.graphviz.org/doc/info/lang.html https://www.graphviz.org/doc/info/lang.html
- StefanKarpinski 9y agoI believe that implicit in this scheme is that you cannot remove dependencies. It seems possible to add new dependencies, however. Changing dependencies can be seen as removing one and adding the other, but you can only do one, not the other. This limitation could probably be patched up by resolving a set of versions and then noticing that X1.1 is unreachable and discarding it. The trouble with that fix would be if X1.1 forces some other package to an unnecessarily high version even though it ends up being discarded.