This project is mirrored from Pull mirroring updated .
  1. 09 May, 2018 1 commit
    • kristenk's avatar
      Solver: Enforce dependencies on libraries (fixes #779). · 6efb5e23
      kristenk authored
      This commit generalizes the fix for issue #4781
      (e86f8389) by tracking dependencies on
      components instead of dependencies on executables.  That means that the solver
      always checks whether a package contains a library before using it to satisfy a
      build-depends dependency.  If a version of a package doesn't contain a library,
      the solver can try other versions.  Associating each dependency with a component
      also moves towards the design for component-based dependency solving described
      in issue #4087.
  2. 12 Nov, 2017 1 commit
  3. 25 Sep, 2017 1 commit
    • kristenk's avatar
      Remove the package instance from D.Solver.Modular.Var (closes #4142). · e1ca9dcf
      kristenk authored
      This change has several effects:
      - The solver no longer includes the package version in messages that relate to
        a package's flags, stanzas, or dependencies.  However, the solver always
        chooses the package version before choosing any flags, stanzas, or
        dependencies for the package, so it should be easy to find the version
        by looking earlier in the log.
      - In conflict counting, the solver treats flags with the same name in different
        versions of a package as the same flag.  This change in the conflict counting
        heuristic can improve the solver's efficiency when the same flag causes the
        same conflicts in different versions of a package.  The same applies to
        enabling tests or benchmarks.
      - Each flag or stanza can only appear once in a conflict set.  This has no
        effect on behavior, but it simplifies the message containing the final
        conflict set.
      Here is an example of the change in a log message.  It only prints
      hackage-server's version once, when it first chooses the package.  The conflict
      set also has one fewer variable, but that is probably due to the change in
      conflict counting.
       Resolving dependencies...
       cabal: Could not resolve dependencies:
       trying: hackage-server-0.5.0 (user goal)
      -trying: hackage-server-0.5.0:+build-hackage-build
      -trying: unix- (dependency of hackage-server-0.5.0
      +trying: hackage-server:+build-hackage-build
      +trying: unix- (dependency of hackage-server
      -next goal: aeson (dependency of hackage-server-0.5.0 +build-hackage-build)
      +next goal: aeson (dependency of hackage-server +build-hackage-build)
       rejecting: aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-
       (conflict: hackage-server +build-hackage-build => aeson==0.6.1.*)
       rejecting: aeson- (conflict: unix => time==,
       aeson => time<1.5)
       rejecting: aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-,
       aeson-, aeson-, aeson-, aeson-, aeson-
       (conflict: hackage-server +build-hackage-build => aeson==0.6.1.*)
       After searching the rest of the dependency tree exhaustively, these were the
      -goals I've had most trouble fulfilling: aeson, hackage-server,
      -hackage-server-0.4:build-hackage-mirror, template-haskell
      +goals I've had most trouble fulfilling: aeson,
      +hackage-server:build-hackage-build, hackage-server, template-haskell
      I ran hackage-benchmark to compare this commit with master (two commits
      earlier).  I used --min-run-time-percentage-difference-to-rerun=10 to only rerun
      packages if the run times differed by more than 10% in the first trial, and
      defaults for the rest of the options (10 trials, p-value of 0.05, 90 second
      timeout). The index state was "2017-09-24T03:35:06Z".
      1 is master, and 2 is this commit:
      package            result1       result2             mean1       mean2     stddev1     stddev2     speedup
      CC-delcont-ref     Solution      Solution           1.467s      1.505s      0.019s      0.100s      0.975
      ascii-cows         Solution      Solution           1.827s      1.758s      0.159s      0.012s      1.040
      opaleye-classy     NoInstallPlan NoInstallPlan      4.588s      4.070s      0.043s      0.032s      1.127
      range-space        NoInstallPlan NoInstallPlan      2.642s      2.299s      0.016s      0.016s      1.149
      rts                PkgNotFound   PkgNotFound        1.323s      1.327s      0.032s      0.033s      0.997
      servant-auth-docs  Solution      Solution           1.968s      1.998s      0.017s      0.074s      0.985
      thorn              BackjumpLimit NoInstallPlan      4.793s      3.141s      0.050s      0.034s      1.526
      unordered-intmap   Solution      Solution           1.502s      1.511s      0.081s      0.047s      0.994
      I looked at the solver logs for the three packages with the largest changes in
      run time, opaleye-classy, range-space, and thorn.  Each one showed that the
      solver started preferring a flag in an older version of a package after it had
      caused conflicts in a newer version of the package.
  4. 24 Sep, 2017 1 commit
    • kristenk's avatar
      Remove D.Solver.Modular.Var.varPI. · efa85a39
      kristenk authored
      This change is necessary to remove the package instance (I) from Var
      (issue #4142).  One of the main uses of the package instance is when varPI is
      called by the linking phase in order to get the dependencies introduced by flags
      and stanzas.  The validation phase also needs to look up dependencies introduced
      by flags and stanzas, but it does so by looking up the dependencies once when it
      chooses a package and then storing the dependencies in a map.  I refactored the
      linking phase to also store dependencies in a map.
  5. 20 Jun, 2017 1 commit
    • bardur.arantsson's avatar
      Create separate compat-prelude for solver · 34233d76
      bardur.arantsson authored
      The idea here is to break the dependency that has crept in from the
      "Solver" into the "Client". (If there's ever going to be a separate
      solver then the dependency would become a big problem.)
  6. 18 Jun, 2017 1 commit
    • kristenk's avatar
      Don't add flag to conflict set when true and false introduce the same conflict. · 6900c9f4
      kristenk authored
      A DependencyReason contains flags paired with values FlagTrue, FlagFalse, or
      FlagBoth, where FlagBoth means that the dependency was introduced by either
      value of the flag and was lifted out of a conditional.  In the previous commit,
      when a dependency led to a conflict, all flags in the DependencyReason were
      added to the error message and conflict set.  This commit avoids adding flags
      with value FlagBoth to the conflict set, because they can have a negative effect
      on goal order: After the solver encounters a conflict involving such a flag, it
      starts to prefer the flag when choosing goals, due to the solver's conflict
      counting feature.  The solver shouldn't prefer the flag goal because it didn't
      actually need to choose the flag to see the dependency.  Flags with value
      FlagBoth are still useful for error messages, though.
      I measured the performance of the last two commits by comparing commit
      fc3ef2a7 (master) with this commit.  I did all
      testing with GHC 8.0.1 and
      'index-state( = 2017-06-11T02:16:39Z'.  I ran each version
      of cabal (cabal install --dry-run) on each package on Hackage and looked for
      packages with a difference in run time of at least 10%.  Then I reran cabal on
      those packages to narrow down the list further (The results were noisy).  Here
      are the average run times from five runs with the remaining packages:
      package                        master result   master time (seconds)   branch result   branch time (seconds)   speedup
      concraft                       backjump limit   5.67                   backjump limit   4.89                    1.16
      forml                          backjump limit  10.26                   backjump limit   8.85                    1.16
      hack-handler-simpleserver      backjump limit   6.28                   no solution      1.96                    3.21
      hack-middleware-clientsession  backjump limit  17.86                   no solution      1.95                    9.14
      haskore                        backjump limit   5.21                   no solution      1.67                    3.12
      haskore-synthesizer            no solution     23.14                   no solution      2.21                   10.49
      language-gcl                   no solution      3.06                   no solution      2.31                    1.33
      ms                             backjump limit  61.68                   no solution      7.95                    7.76
      nerf                           solution         4.1                    backjump limit   5.87                    0.7
      puzzle-draw                    solution        56.28                   solution         5.31                   10.6
      react-haskell                  backjump limit  44.23                   backjump limit  14.46                    3.06
      reflex-transformers            no solution      2.18                   no solution      1.9                     1.15
      shpider                        backjump limit   7.44                   solution         1.88                    3.95
      thorn                          backjump limit  11.11                   backjump limit   4.44                    2.5
      Both versions of cabal hit the backjump limit in four of the cases, so they
      don't really tell us which version performed better.  All but one of the others
      are improvements.  I looked at a few of the logs, and, as far as I can tell,
      most of the improvements are due to flags being used in conflict counting.  This
      behavior is similar to #4147, which was reverted.  The log for 'nerf', the one
      package that had worse performance, showed that the solver chose some flags
      earlier, but I didn't see any other reason for the slowdown.  The solver found a
      solution when I used '--max-backjumps -1'.
      These differences in run time are caused by differences in goal order and/or
      backjumping, but I also wanted to compare performance when the solver went
      through similar steps on master and the branch.  I found two commands that led
      to very similar -v3 output between the cabal versions.  Presumably, package
      flags didn't cause many conflicts in these runs.
      cabal install --dry-run --max-backjumps -1 gi-glib happstack
      cabal install --dry-run yesod
      I took the average of three runs.  There wasn't a big difference between master
      and the branch.
      packages             result        master time (seconds)   branch time (seconds)   master memory (MB)   branch memory (MB)
      gi-glib, happstack   no solution   30.02                   30.70                   245                  245
      yesod                solution       3.53                    3.55                   239                  239.3
  7. 17 Jun, 2017 1 commit
    • kristenk's avatar
      Solver: Add individual flags to conflict sets. · 1d016574
      kristenk authored
      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 #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.
  8. 01 Apr, 2017 1 commit
    • kristenk's avatar
      Refactor solver goal types. · 2245c9d9
      kristenk authored
      This commit should have no effect on behavior.  It splits the OpenGoal type into
      OpenGoal and PotentialGoal.  Both types are only used when building the search
      tree.  While PotentialGoal can represent any dependency or constraint, OpenGoal
      only represents dependencies that introduce goals (solver variables).  Limiting
      OpenGoal to only represent goals simplifies the code.
      This commit also removes OpenGoal and FlaggedDep's 'comp' type variables.  The
      two types had only been used with 'comp' equal to () or Component.  Now
      FlaggedDep always uses Component, and OpenGoal does not need a Component.
  9. 21 Feb, 2017 2 commits
  10. 20 Feb, 2017 1 commit
    • kristenk's avatar
      Allow the solver to toggle manual flags to match constraints that have any qualifier. · f7f63ab4
      kristenk authored
      This fixes #4299. The change gives the dependency solver the flexibility to link
      dependencies when the user has only set a manual flag on one of them.
      Previously, the solver would force the constrained dependency to have the
      flag value from the constraint and force the unconstrained dependency to have
      the default flag value. In cases where the single instance restriction required
      the dependencies to be linked, the solver couldn't find a solution.
      Qualified constraints can still be used to force different dependencies on a
      package to use different flag values. For example,
      "--constraint 'pkg +flag' --constraint 'pkg2:setup.pkg -flag'" turns the flag on
      for the top-level dependency and off for the setup dependency.
      I also stored flag default values in the search tree to simplify the code.
  11. 10 Feb, 2017 1 commit
  12. 27 Dec, 2016 1 commit
    • kristenk's avatar
      Solver: Check for cycles after every step. · f4f57f24
      kristenk authored
      Previously, the solver only checked for cycles after it had already found a
      solution. That reduced the number of times that it performed the check in the
      common case where there were no cycles. However, when there was a cycle, the
      solver could spend a lot of time searching subtrees that already had a cyclic
      dependency and therefore could not lead to a solution. This is part of
      Changes in this commit:
      - Store the reverse dependency map on all choice nodes in the search tree, so
        that 'detectCyclesPhase' can access it at every step.
      - Check for cycles incrementally at every step. Any new cycle must contain the
        current package, so we just check whether the current package is reachable
        from its neighbors.
      - If there is a cycle, we convert the map to a graph and find a strongly
        connected component, as before.
      - Instead of using the whole strongly connected component as the conflict set,
        we select one cycle. Smaller conflict sets are better for backjumping.
      - The incremental cycle detection automatically fixes a bug where the solver
        filtered out the message about cyclic dependencies when it summarized the full
        log. The bug occurred when the failure message was not immediately after the
        line where the solver chose one of the packages involved in the conflict. See
      I tried several approaches and compared performance when solving for
      packages with different numbers of dependencies. Here are the results. None of
      these runs involved any cycles, so they should have only tested the overhead of
      cycle checking. I turned off assertions when building cabal.
      Index state: index-state( = 2016-12-03T17:22:05Z
      GHC 8.0.1
      Runtime in seconds:
      Packages                    Search tree depth   Trials   master   This PR   #1      #2
      yesod                       343                 3        2.00     2.00      2.13    2.02
      yesod gi-glib leksah        744                 3        3.21     3.31      4.10    3.48
      phooey                      66                  3        3.48     3.54      3.56    3.57
      Stackage nightly snapshot   6791                1        186      193       357     191
      Total memory usage in MB, with '+RTS -s':
      Packages                                        Trials   master    This PR   #1     #2
      yesod                                           1         189       188       188     198
      yesod gi-glib leksah                            1         257       257       263     306
      Stackage nightly snapshot                       1        1288      1338      1432   12699
      #1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after
           every step.
      #2 - Store dependencies in Distribution.Compat.Graph in the search tree, and
           check for cycles containing the current package at every step.
  13. 04 Dec, 2016 1 commit
  14. 22 Nov, 2016 1 commit
  15. 26 Sep, 2016 1 commit
  16. 18 Sep, 2016 1 commit
  17. 04 Sep, 2016 1 commit
  18. 21 Aug, 2016 1 commit
    • Edward Z. Yang's avatar
      Solve for, build, and add to path build-tools dependencies. · c0a48602
      Edward Z. Yang authored
      This fixes #220: new-build now builds, installs and adds executables to
      PATH automatically if they show up in 'build-tools'.  However, there is
      still more that could be done: the new behavior only applies to a
      specific list of 'build-tools' (alex, happy, etc) which Cabal recognizes
      out of the box.  The plan is to introduce a new 'tool-depends' field to
      allow dependencies on other executables as well.
      Signed-off-by: default avatarEdward Z. Yang <>
  19. 31 Jul, 2016 2 commits
    • kristenk's avatar
      Solver: Only link packages to other unlinked packages. · bae78a4a
      kristenk authored
      If 1.A is already linked to 0.A, then linking 2.A to 1.A gives the same result
      as linking 2.A to 0.A. This commit avoids creating options to link to packages
      that are already linked, to reduce the branching factor of the search tree.
    • kristenk's avatar
      Fix typos. · 05c8b143
      kristenk authored
  20. 17 Jul, 2016 1 commit
  21. 26 Jun, 2016 1 commit
  22. 26 Apr, 2016 1 commit
  23. 22 Apr, 2016 4 commits
  24. 21 Apr, 2016 3 commits
    • kristenk's avatar
      Use larger conflict set when solver chooses wrong version for package in link group · 7f480594
      kristenk authored
      This commit replaces a call to 'lgBlame' with a call to 'lgConflictSet'.
      'lgConflictSet' adds the members of the link group to the conflict set. The
      other members are required, for example, when a linked package's version doesn't
      match a constraint, and the solver must try other versions for the linked-to
      All tests now pass.
    • Edsko de Vries's avatar
      Fix bug in link validation · 34bfdf82
      Edsko de Vries authored
      When we are choosing to link a package (`pickLink`), it is possible that that
      package was _already_ linked (because its reverse dependencies got linked).
      Thus, this requires a merge of link groups: it is not correct to simply add the
      package into the target link group.
      This fixes #2842.
    • Andres Löh's avatar
      Remove goal reason chains. · 7995ea2a
      Andres Löh authored
  25. 18 Apr, 2016 1 commit
  26. 17 Apr, 2016 1 commit
    • Edsko de Vries's avatar
      Make ConflictSet abstract · 1a1f1f9b
      Edsko de Vries authored
      This commit is a pure refactoring, no semantic changes. Submitting as separate
      PR at @kosmikus request.
      Tihs moves `ConflictSet` and `Var` into their own modules.
  27. 05 Mar, 2016 1 commit
    • inaki's avatar
      Make the solver aware of pkg-config constraints · c72aa8db
      inaki authored
      When solving, we now discard plans that would involve packages with a
      pkgconfig-depends constraint which is not satisfiable with the current
      set of installed packages (as listed by pkg-config --list-all).
      This fixes
      It is possible (in principle, although it should be basically impossible
      in practice) that "pkg-config --modversion pkg1 pkg2... pkgN" fails to
      execute for various reasons, in particular because N is too large, so
      the command line becomes too long for the operating system limits.
      If this happens, revert to the previous behavior of accepting any
      install plan, regardless of any pkgconfig-depends constraints.
  28. 25 Nov, 2015 1 commit
    • Andres Löh's avatar
      Track language extensions and language flavours in the solver. · fd5e0c65
      Andres Löh authored
      Every package now "depends" on all language extensions
      (default-extensions and other-extensions) and language flavours
      (default-language and other-languages) it declares in its cabal file.
      During solving, we verify that the compiler we use actually
      supports selected extensions and languages. This has to be done
      during solving, because flag choices can influence the declared
      extensions and languages being used.
      There currently is no equivalent check performed on the generated
      install plans. In general, cabal-install performs a sanity check
      on the solver output, checking that the solver e.g. indeed includes
      all the declared dependencies of a package. There is no such
      double-checking for language extensions. This is not really
      problematic, as all that this change does is to make the solver
      more conservative rather than less. However, having a sanity check
      available might ultimately be nice to have.
  29. 01 Jun, 2015 5 commits