This project is mirrored from Pull mirroring updated .
  1. 05 Jan, 2017 2 commits
  2. 03 Jan, 2017 5 commits
  3. 02 Jan, 2017 1 commit
  4. 01 Jan, 2017 2 commits
  5. 31 Dec, 2016 6 commits
  6. 30 Dec, 2016 1 commit
  7. 27 Dec, 2016 5 commits
    • Edward Z. Yang's avatar
      Refactor Backpack data structures to be less flexible. · 28af355b
      Edward Z. Yang authored and Edward Z. Yang's avatar Edward Z. Yang committed
      There were a number of fields in 'LinkedComponent' which
      were "too" flexible, in that they were fully determined by
      other fields in the structure.  This refactor deletes those
      fields and replaces them with functions that refer to the
      fields directly.
      I also introduce a new type, ComponentInclude, to take
      the place of tuples which were used to represent includes
      (mixins) in Backpack.
      There's also more documentation for lots of bits.
      Signed-off-by: default avatarEdward Z. Yang <>
    • kristenk's avatar
      Fix build with GHC 7.8.4. · 3d88a3ec
      kristenk authored and Edward Z. Yang's avatar Edward Z. Yang committed
    • kristenk's avatar
      Add a test for incremental cycle detection. · 3aee78dd
      kristenk authored and Edward Z. Yang's avatar Edward Z. Yang committed
    • kristenk's avatar
      Solver: Check for cycles after every step. · f4f57f24
      kristenk authored and Edward Z. Yang's avatar Edward Z. Yang committed
      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.
    • kristenk's avatar
      Remove unnecessary uses of QGoalReason. · dedec725
      kristenk authored and Edward Z. Yang's avatar Edward Z. Yang committed
  8. 24 Dec, 2016 2 commits
  9. 22 Dec, 2016 4 commits
  10. 21 Dec, 2016 2 commits
  11. 20 Dec, 2016 1 commit
  12. 18 Dec, 2016 4 commits
  13. 17 Dec, 2016 1 commit
  14. 14 Dec, 2016 1 commit
  15. 13 Dec, 2016 3 commits