Paket downgrades direct dependency without reason #3103

Description

Paket resolves a direct dependency to a lower version than available, even though the latest version is also a valid resolution, with the same transitive dependency solution.

I would really like to give a reproduction sample here, but unfortunately, I only had this bug happen using our internal artifact server and packages. Instead, please try to follow my reasoning through this log, which is the result of running paket update -v on a paket.dependencies file with a single (nuget) entry : delphi-tf-latest-convert: https://gist.github.com/auxym/5b87b8cd92ab80b75a68addf65492e68

Here is what I understand is happening:

1. L43: The latest available version of delphi-tf-latest-convert is found from the feed: 0.0.75. This is the desired version.

2. L91. We resolved an additional transitive dependency : Taxdoc, to the latest available. So far so good.

3. L153 This is where things get weird. Since L91, paket found a conflict in the dependencies of taxdoc and latest-calc. To fix this, it decided to downgrade our direct dependency, delphi-tf-latest-convert, to 0.0.74. This is even though the transitive dependencies of 0.0.74 and 0.0.75 are absolutely identical.

4. L332 Final resolution solution: we have delphi-tf-latest-convert v 0.0.74, even though the latest version (0.0.75), would be valid with the exact same resolution.

Repro steps

See above, unfortunately I cannot provide a repro example using external projects.

Expected behavior

Given a valid solution to version resolution, I would expect our direct dependencies to be resolved to the highest possible version.

Actual behavior

Paket seems to always resolve to exactly one version behind.

Known workarounds

Right now, taxdoc is resolved first (see step 2 above). I understand that this is because of alphabetical order, as none of the transitive dependencies have any version constraint on them (from what I understand of Paket Resolution Algorithm).

We are working around the issue by adding a very loose version constraint to tf-latest-calc, which forces paket to attempt resolving it first, before TaxDoc. This results in correctly resolving delphi-tf-latest-convert to the latest version (0.0.75).