Skip to content

Solver: Add individual flags to conflict sets. #4391

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
grayjay opened this issue Mar 12, 2017 · 1 comment
Closed

Solver: Add individual flags to conflict sets. #4391

grayjay opened this issue Mar 12, 2017 · 1 comment
Assignees
@grayjay
Labels
cabal-install: solver type: enhancement

Comments

@grayjay
Copy link
Collaborator

grayjay commented Mar 12, 2017

Currently, the solver uses one conflict set variable to represent all flags in a single package. Say package pkg-1.0 has two flags, flagA and flagB. If either flagA or flagB introduces an unsatisfiable dependency, then the solver adds the variable pkg-1.0:flag to the conflict set. Since pkg-1.0:flag represents all of pkg's flags, the solver must backtrack and try flipping both flagA and flagB, even though only one of them introduced the dependency.

I think it would be nice to keep track of the flags that introduce each dependency and then put individual flags in conflict sets. It would reduce the search space for the solver. (This is related to #1890.)

Another benefit of tracking individual flags is that it would allow us to change the order of flag goals without having a large impact on performance. Right now, the solver chooses flags relatively efficiently by solving for them in the order that they appear in the trees of conditionals. For example, the solver chooses A and D first for this package, since they are in top level conditionals:

name: example
version: 1.0
build-type: Simple

flag A
flag B
flag C
flag D
flag E
flag F

library
  if flag(A)
    build-depends: unknown
    if flag(B)
      build-depends: base
    if flag(C)
      build-depends: mtl
  else
    build-depends: unknown2

  if flag(D)
    build-depends: unknown3
    if flag(E)
      build-depends: base
    if flag(F)
      build-depends: mtl

The flag order allows it to discover the dependencies on unknown, unknown2, and unknown3 as soon as possible and determine that there is no solution. If the solver instead chose flags in the order B, C, E, F, A, it wouldn't find the first unknown dependency until it had made five flag choices. At that point, it would need to backtrack and try all combinations for B, C, E, and F. So, we need to be careful when changing the order of flag goals. Some goal orders can cause the solver to get stuck trying too many combinations. However, if we added individual flags to conflict sets, the order B, C, E, F, A would work just as well as the current order. When the solver tried to choose a value for A and discovered the dependencies on unknown and unknown2, it would only add A to the conflict set. It could immediately backtrack past B, C, E, and F, since they didn't contribute to the conflict.

Making the solver perform well even after bad goal choices might increase the effectiveness of some goal order heuristics, such as randomization.

A third benefit of tracking individual flags is that we could treat stanza choices similarly to flags and fix issues like #3930 and #4390.
@grayjay grayjay self-assigned this Jun 10, 2017
grayjay added a commit to grayjay/cabal that referenced this issue Jun 12, 2017
@grayjay
Refactor Validate.hs.
8a35940 
This just moves some functions and types into Validate.hs in preparation for
haskell#4391.
grayjay added a commit to grayjay/cabal that referenced this issue Jun 12, 2017
@grayjay
Solver: Add individual flags to conflict sets.
053c363 
This commit changes the way that the solver tracks the variables that introduce
dependencies, in order to fix some bugs that prevented the solver from tracking
individual flags.  I refactored Dep, the type that represents a build-depends or
build-tool-depends dependency, so that it stores the package, flag, and stanza
choices that introduced the dependency.  That information is stored in a field
of type DependencyReason.  The DependencyReason is available to any solver phase
that needs to create conflict sets, such as "build" or "validation".  Whenever
there is a conflict involving a dependency, the solver creates a conflict set
and a log message using the dependency's DependencyReason.  This means that the
solver only needs to calculate the dependency reasons once, in
IndexConversion.hs, rather than every time they are used, i.e., in Builder.hs
(for goal reasons), Validate.hs, and Linking.hs.

Another difference between this commit and master is the dependencies between
solver variables.  On master, each dependency or variable is introduced by
exactly one other variable.  For example, if package x has a flag y, which
controls a dependency on package z, then the three variables depend on each
other in a chain, x -> y -> z.  If z can't be satisfied, the solver backjumps
to its cause, y, and if flipping y doesn't help, it continues backjumping to y's
cause, which is x.  In contrast, this commit allows each dependency to be
introduced by a package and any number of flags and stanzas.  So z's
DependencyReason would contain both x and y.

Storing all flags that introduced a dependency allows the solver to correctly
calculate conflict sets when there are nested conditionals.  We no longer need
to combine each package's flags into a single conflict set variable.  This
commit removes the 'simplifyVar' function and adds flag variables directly to
conflict sets.  See issue haskell#4391.

This commit makes another minor change.  In this commit and master, if a
dependency appears in the if and else blocks of a conditional, the solver lifts
it out of the conditional.  Previously, the solver behaved as if the flag did
not introduce the dependency.  This commit adds the flag variable to the
conflict set or error message if the dependency is involved in a conflict.  This
change doesn't affect correctness, but I think it improves the error messages,
since it gives the whole reason that each dependency was introduced.
grayjay added a commit to grayjay/cabal that referenced this issue Jun 12, 2017
@grayjay
Refactor Validate.hs.
a568aeb 
This just moves some functions and types into Validate.hs in preparation for
haskell#4391.
grayjay added a commit to grayjay/cabal that referenced this issue Jun 12, 2017
@grayjay
Solver: Add individual flags to conflict sets.
e6bf663 
This commit changes the way that the solver tracks the variables that introduce
dependencies, in order to fix some bugs that prevented the solver from tracking
individual flags.  I refactored Dep, the type that represents a build-depends or
build-tool-depends dependency, so that it stores the package, flag, and stanza
choices that introduced the dependency.  That information is stored in a field
of type DependencyReason.  The DependencyReason is available to any solver phase
that needs to create conflict sets, such as "build" or "validation".  Whenever
there is a conflict involving a dependency, the solver creates a conflict set
and a log message using the dependency's DependencyReason.  This means that the
solver only needs to calculate the dependency reasons once, in
IndexConversion.hs, rather than every time they are used, i.e., in Builder.hs
(for goal reasons), Validate.hs, and Linking.hs.

Another difference between this commit and master is the dependencies between
solver variables.  On master, each dependency or variable is introduced by
exactly one other variable.  For example, if package x has a flag y, which
controls a dependency on package z, then the three variables depend on each
other in a chain, x -> y -> z.  If z can't be satisfied, the solver backjumps
to its cause, y, and if flipping y doesn't help, it continues backjumping to y's
cause, which is x.  In contrast, this commit allows each dependency to be
introduced by a package and any number of flags and stanzas.  So z's
DependencyReason would contain both x and y.

Storing all flags that introduced a dependency allows the solver to correctly
calculate conflict sets when there are nested conditionals.  We no longer need
to combine each package's flags into a single conflict set variable.  This
commit removes the 'simplifyVar' function and adds flag variables directly to
conflict sets.  See issue haskell#4391.

This commit makes another minor change.  In this commit and master, if a
dependency appears in the if and else blocks of a conditional, the solver lifts
it out of the conditional.  Previously, the solver behaved as if the flag did
not introduce the dependency.  This commit adds the flag variable to the
conflict set or error message if the dependency is involved in a conflict.  This
change doesn't affect correctness, but I think it improves the error messages,
since it gives the whole reason that each dependency was introduced.
grayjay added a commit to grayjay/cabal that referenced this issue Jun 12, 2017
@grayjay
Solver: Add individual flags to conflict sets.
d7b4f5f 
This commit changes the way that the solver tracks the variables that introduce
dependencies, in order to fix some bugs that prevented the solver from tracking
individual flags.  I refactored Dep, the type that represents a build-depends or
build-tool-depends dependency, so that it stores the package, flag, and stanza
choices that introduced the dependency.  That information is stored in a field
of type DependencyReason.  The DependencyReason is available to any solver phase
that needs to create conflict sets, such as "build" or "validation".  Whenever
there is a conflict involving a dependency, the solver creates a conflict set
and a log message using the dependency's DependencyReason.  This means that the
solver only needs to calculate the dependency reasons once, in
IndexConversion.hs, rather than every time they are used, i.e., in Builder.hs
(for goal reasons), Validate.hs, and Linking.hs.

Another difference between this commit and master is the dependencies between
solver variables.  On master, each dependency or variable is introduced by
exactly one other variable.  For example, if package x has a flag y, which
controls a dependency on package z, then the three variables depend on each
other in a chain, x -> y -> z.  If z can't be satisfied, the solver backjumps
to its cause, y, and if flipping y doesn't help, it continues backjumping to y's
cause, which is x.  In contrast, this commit allows each dependency to be
introduced by a package and any number of flags and stanzas.  So z's
DependencyReason would contain both x and y.

Storing all flags that introduced a dependency allows the solver to correctly
calculate conflict sets when there are nested conditionals.  We no longer need
to combine each package's flags into a single conflict set variable.  This
commit removes the 'simplifyVar' function and adds flag variables directly to
conflict sets.  See issue haskell#4391.

This commit makes another minor change.  In this commit and master, if a
dependency appears in the if and else blocks of a conditional, the solver lifts
it out of the conditional.  Previously, the solver behaved as if the flag did
not introduce the dependency.  This commit adds the flag variable to the
conflict set or error message if the dependency is involved in a conflict.  This
change doesn't affect correctness, but I think it improves the error messages,
since it gives the whole reason that each dependency was introduced.
@grayjay grayjay mentioned this issue Jun 12, 2017
Merged
grayjay added a commit to grayjay/cabal that referenced this issue Jun 14, 2017
@grayjay
Refactor Validate.hs.
bff554e 
This just moves some functions and types into Validate.hs in preparation for
haskell#4391.
grayjay added a commit to grayjay/cabal that referenced this issue Jun 14, 2017
@grayjay
Solver: Refactor Validate.hs.
83fd91f 
This just moves some functions and types into Validate.hs in preparation for
haskell#4391.
@grayjay grayjay mentioned this issue Jun 14, 2017
Merged
grayjay added a commit to grayjay/cabal that referenced this issue Jun 17, 2017
@grayjay
Solver: Add individual flags to conflict sets.
1d01657 
This commit changes the way that the solver tracks the variables that introduce
dependencies, in order to fix some bugs that prevented the solver from tracking
individual flags.  I refactored Dep, the type that represents a build-depends or
build-tool-depends dependency, so that it stores the package, flag, and stanza
choices that introduced the dependency.  That information is stored in a field
of type DependencyReason.  The DependencyReason is available to any solver phase
that needs to create conflict sets, such as "build" or "validation".  Whenever
there is a conflict involving a dependency, the solver creates a conflict set
and a log message using the dependency's DependencyReason.  This means that the
solver only needs to calculate the dependency reasons once, in
IndexConversion.hs, rather than every time they are used, i.e., in Builder.hs
(for goal reasons), Validate.hs, and Linking.hs.

Another difference between this commit and master is the dependencies between
solver variables.  On master, each dependency or variable is introduced by
exactly one other variable.  For example, if package x has a flag y, which
controls a dependency on package z, then the three variables depend on each
other in a chain, x -> y -> z.  If z can't be satisfied, the solver backjumps
to its cause, y, and if flipping y doesn't help, it continues backjumping to y's
cause, which is x.  In contrast, this commit allows each dependency to be
introduced by a package and any number of flags and stanzas.  So z's
DependencyReason would contain both x and y.

Storing all flags that introduced a dependency allows the solver to correctly
calculate conflict sets when there are nested conditionals.  We no longer need
to combine each package's flags into a single conflict set variable.  This
commit removes the 'simplifyVar' function and adds flag variables directly to
conflict sets.  See issue haskell#4391.

This commit makes another minor change.  In this commit and master, if a
dependency appears in the if and else blocks of a conditional, the solver lifts
it out of the conditional.  Previously, the solver behaved as if the flag did
not introduce the dependency.  This commit adds the flag variable to the
conflict set or error message if the dependency is involved in a conflict.  This
change doesn't affect correctness, but I think it improves the error messages,
since it gives the whole reason that each dependency was introduced.
@grayjay
Copy link
Collaborator Author

grayjay commented Jul 7, 2017

This was implemented in #4562.

@grayjay grayjay closed this as completed Jul 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@grayjay grayjay

Labels
cabal-install: solver type: enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@grayjay