cabal uses too much memory when solving for setup dependencies

[sebright]

Some combinations of setup and library dependencies cause the solver to use more and more memory. I ran cabal install --dry-run --max-backjumps -1 with this cabal file for five minutes with about 16GB of memory. I used GHC 7.10.2.

name:                example
version:             0.1.0.0
cabal-version:       >=1.8
build-type:          Custom

custom-setup
  setup-depends:       aeson, hackage-server, yi

library
  build-depends:       aeson, mtl, leksah

My best guess is that it is related to the addLinking function creating linked nodes from existing unlinked nodes. When a node is referenced by a later sibling, it probably isn't garbage collected immediately after it is traversed.

cabal/cabal-install/Distribution/Client/Dependency/Modular/Linking.hs

Line 67 in c5b90c4

return $ PChoice qpn gr (cs' `P.union` P.fromList newCs)

[23Skidoo]

/cc @edsko, @kosmikus

[sebright]

I encountered this issue again while testing with a long-running command: cabal install leksah yesod hackage-server

This uses GHC 8.0.1.

The -v3 log shows that the solver chose to link a setup dependency near the top of the tree (level 8). It didn't return to that level until around the time that the memory usage dropped. When it descended again, it used a different goal order and chose the setup dependencies much farther down in the tree. I think that the spike in memory usage can be explained by the solver retaining the whole subtree starting where it chose the first setup dependency.