Should we remove the package version from flag/stanza variables in the solver?

[sebright]

Here is an example of the current behavior:

$ cabal install --dry-run thorn --max-backjumps -1 -v3
[...]
[__4] fail (backjumping, conflict set: base, comonad, transformers)
[__3] rejecting: comonad-1.1.0 (conflict: base==4.9.0.0/installed-4.9..., comonad => base>=4 && <4.4)
[__3] rejecting: comonad-1.0.3, comonad-1.0.2, comonad-1.0.1, comonad-1.0, comonad-0.9.0.1, comonad-0.9.0, comonad-0.7.0, comonad-0.6.2.1, comonad-0.6.2, comonad-0.6.1.2, comonad-0.6.1.1, comonad-0.6.1, comonad-0.6.0, comonad-0.5.0, comonad-0.4.0, comonad-0.3.0, comonad-0.1.1, comonad-0.1.0 (conflict: profunctors => comonad>=1.1 && <1.2)
[__3] fail (backjumping, conflict set: base, comonad, profunctors, transformers)
[__2] fail (backjumping, conflict set: base, bifunctors, comonad, profunctors, semigroupoids, thorn, transformers, transformers-compat, semigroupoids-4.0.3:flag, semigroupoids-4.0.4:flag, semigroupoids-4.2:flag)
[__1] rejecting: base-4.9.0.0, base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1, base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0, base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2, base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2, base-3.0.3.1 (constraint from non-upgradeable package requires installed instance)
[__0] fail (backjumping, conflict set: base, bifunctors, comonad, profunctors, semigroupoids, thorn, transformers, transformers-compat, semigroupoids-4.0.3:flag, semigroupoids-4.0.4:flag, semigroupoids-4.2:flag)
[...]

The final conflict set contains semigroupoids-4.0.3:flag, semigroupoids-4.0.4:flag, semigroupoids-4.2:flag.

As I understand it, the version information has no effect on backjumping, because backjumping never uses variables that were assigned below the current node. And the only way for a conflict set to have more than one version of a flag is for that flag to have been assigned multiple times, which can only happen on multiple branches below the current node.

Some reasons to remove the version:

• Treating all versions of a flag as the same variable could improve conflict counting. If a flag causes a conflict in one version of a package, then it is more likely to cause a conflict in the next version, and the solver should try to assign the flag sooner.

• It would simplify the final conflict set when we display it for Print final conflict set when dependency solver fails after an exhaustive search #3570.

• Flag variables would be more consistent with variables for setup dependencies, which contain the name, but not the version, of the package that has the setup script.

Does it make sense to remove the version info? If we remove it, should we remove it from the Var type, or just remove it when we add variables to the conflict set?

/cc @kosmikus @edsko @fmthoma

[kosmikus]

I think I'm in favour of this. I'm just wondering if we always had the version number in flag goals, and why. Perhaps I'm overlooking a reason why this was done in the first place.

For conflict counting, it most definitely makes sense, because heuristically, the roles of flags change rarely across versions, so if a flag is causing trouble, it should be preferred independently of the selected version.

[sebright]

I think I'm in favour of this. I'm just wondering if we always had the version number in flag goals, and why. Perhaps I'm overlooking a reason why this was done in the first place.

As far as I can tell, the version is only used in two places:

1. Linking.hs uses the version contained in a flag/stanza choice node to look up the package's dependencies in the index. Validate.hs also needs to access the package's dependencies, but it doesn't need to use the same version field because it maintains a map of dependencies in the Reader environment that is keyed by QPN.
2. The solver prints the version in log messages. For example, it prints the package name and version when it chooses flags for the package, when the package introduces goals, and when the package is part of a conflict.

We could leave the version information in the choice nodes for (1), even if we removed it from the Var type.

Do you think it is okay to only print the version number in the log when the solver first chooses a package? I think we could safely remove the other version information, because every time the solver prints a message about a package in the summarized log, it should also include the message about choosing that package's version, since the package should be in the conflict set.

[phadej]

For conflict counting, it most definitely makes sense, because heuristically, the roles of flags change rarely across versions, so if a flag is causing trouble, it should be preferred independently of the selected version.

solver will still work correctly if the flag semantics are flipped? (e.g. if was semantically wrong way, humans make mistakes). Just to be sure.

[sebright]

If a flag causes conflicts in one version of a package, it should be just as likely to cause conflicts if the meaning of true and false are flipped (especially if the default is also flipped). But even if the flag's meaning changed completely in the next version, and it stopped causing the same conflicts, it would only cause a decrease in performance with the proposed change.