Mai 

I'm trying to understand / implement dependency resolving using the pubgrub algorithm (to use in my buildsystem nitto). But I keep running into bugs; The newset one:

Suppose we have the following state:
```
root 1.0.0 -> foo ^1.0.0, bar ^1.0.0
foo 1.1.0 -> bar ^2.0.0
foo 1.0.0 -> n/a
bar 1.0.0 -> n/a
bar 1.1.0 -> n/a
bar 2.0.0 -> n/a
```

Now after avoiding a conflict and by choosing to not select `foo 1.1.0` and deriving `not foo 1.1.0` from `{foo 1.1.0, not bar ^2.0.0}`, it derives `foo ^1.0.0` from `{root 1.0.0, not foo ^1.0.0}` even tho it is already an derivation term in the assignments! Aparentily it relates `not foo ^1.0.0` as as overlapping, and wants to add it again to the partial solution...

#pubgrub #packagemanager #packagemanagement #dependencyresolution #programming #developing #coding #softwaredevelopment #foss #floss

Feb 26 at 11:59pmWeb
Show threadMai Feb 27
So aparenlty "just check if we have it and ignore it then" dosn't work out, it end up in an endless loop (the same thing as when I do nothing to stop it). Maybe the decision is wrong since it's a single version and therefor dosn't cover enough ground? The positive union constraint also looks like this: `foo >=1.0.0 <1.1.0 or >1.1.0 <2.0.0`, so maybe it needs to derive `not foo >=1.1.0` instead of just the one version...
Show threadMai Feb 27
Hmm... so it now derives successfully not foo >=1.1.0 (from {foo >=1.1.0, not bar ^2.0.0}), but it stily relates not foo ^1.0.0 against foo >=1.0.0 <1.1.0 and tries to re-add it... maybe I should let it do it and hope it dosnt endless-loop again? Only one way to find out...!
Show threadMai Feb 27
Nope still enlessly tries to add foo ^1.0.0 and not foo >=1.1.0 as derivations to the partial solution...
Show threadMai Feb 27

Huh.... so now it thinks that the terms not foo ^1.0.0 and foo >=1.0.0 <1.1.0 are overlapping....

And I'm bad in visualizing this in my head so I even created an VERY crude tool for this purpose...

(Ik this dosn't support inverse ranges yet, so just invert the magenta line in your head for the time being...)

It should detect it as disjoint not overlapping, so something is wrong with the relation code (again).

Show threadMai Feb 27

sigh ofc its the damn version primitives.

So aparently, I had an copy-and-paste error in my implementation of allowsHigher, which compares two range's maximum version with each other. This led to the allowAll method on a version range not reporting correctly that indeed all versions in >=1.0.0 <1.1.0 are allowed in the range ^1.0.0. In the buggy version, it would only allow if the max was the same (i.e. >=1.x.x <2.0.0)...

Hate such bugs; it now recognizes the terms from earlier (i.e. foo >=1.0.0 <1.1.0 and not foo ^1.0.0) as being disjoint.

However, it now goes back to looping endlessly while trying to do unit propagation, which I shoudln't happen...

Show threadMai Feb 27

Haaaa! It still tries to select foo 1.1.0 since it figures that the next unsatisfied term (the only one left really) has to be foo ^1.0.0, which ofc is nonsense if we figured out that we actually need foo >=1.0.0 <1.1.0 in the partial solution.

This is due to me previously just storing all assignments plainly in the partial solution to keep it simple while learning, and then later needing to unfiy the terms in the assignment thus using an extra list that keeps foo >=1.0.0 <1.1.0 and others. However, I missed to update the code that figures out the unsatisfied terms for the next decision.

.... And after switching from

@assignments.filter_map{|a|
next a[0] if a[0].is_positive?
next nil
}.filter{|term| !@decisions.has_key?(term.name)}

to a simple @positive.values.filter{|term| !@decisions.has_key?(term.name)}, it solves the problem without ever needing to do conflict resolution:

Successfully solved:
- root: 1.0.0
- bar: 1.1.0
- foo: 1.0.0

Im so happy it works now :3333

Next thing would only be to add proper conflict solving and backtracking... And ofc porting it all from ruby to java so I can use it in my buildsystem... propably make it a library tho, if I ever need it again lol