{"action":"created","issue":{"url":"https://api.github.com/repos/haskell/cabal/issues/3357","repository_url":"https://api.github.com/repos/haskell/cabal","labels_url":"https://api.github.com/repos/haskell/cabal/issues/3357/labels{/name}","comments_url":"https://api.github.com/repos/haskell/cabal/issues/3357/comments","events_url":"https://api.github.com/repos/haskell/cabal/issues/3357/events","html_url":"https://github.com/haskell/cabal/pull/3357","id":148964176,"number":3357,"title":"Fix construction of conflict sets once and for all (WIP) ","user":{"login":"edsko","id":935288,"avatar_url":"https://avatars.githubusercontent.com/u/935288?v=3","gravatar_id":"","url":"https://api.github.com/users/edsko","html_url":"https://github.com/edsko","followers_url":"https://api.github.com/users/edsko/followers","following_url":"https://api.github.com/users/edsko/following{/other_user}","gists_url":"https://api.github.com/users/edsko/gists{/gist_id}","starred_url":"https://api.github.com/users/edsko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edsko/subscriptions","organizations_url":"https://api.github.com/users/edsko/orgs","repos_url":"https://api.github.com/users/edsko/repos","events_url":"https://api.github.com/users/edsko/events{/privacy}","received_events_url":"https://api.github.com/users/edsko/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/haskell/cabal/labels/solver","name":"solver","color":"009800"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-04-17T15:36:02Z","updated_at":"2016-04-18T03:11:39Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/haskell/cabal/pulls/3357","html_url":"https://github.com/haskell/cabal/pull/3357","diff_url":"https://github.com/haskell/cabal/pull/3357.diff","patch_url":"https://github.com/haskell/cabal/pull/3357.patch"},"body":"At @kosmikus ' request I have started a new `solver` branch in the main repository so that we can push solver fixes to this branch and then once we are happy with them, push them to master.\r\n\r\nI realized that my understanding of conflict sets and goal reason chains was flawed. I think it's not just me though; they badly need explaining and documenting. To this end I started writing a blog post about the relation between conflict sets, pre assignments, constrained instances, and goal reason chains; a first draft can be found at http://www.well-typed.com/blog/preview/backjumping/ . \r\n\r\nOn this branch so far we first have @grayjay 's test case for backjumping after the SIR check. We previously fixed this in #3221, but I now realize the fix there was incorrect. (In my defence, I did mention I was not very convinced.) I hope it is correct now (and if so, this PR will obsolete #3221). In addition we have a fix to the cycle check detection (#3170). That check too was wrong, and for similar reasons. The correct solution is also similar in both cases. Instead of collecting which _packages_ are involved in the conflict, we instead collect `Goals` (packages + goal reason chains). Then to construct the conflict set we construct conflict sets for each of these individual goals and then merge them. This is just a generalization of the process that happens in during validation (described in the aforelinked blog post). For the cycle check this is a tad awkward since we start with the final reverse dependency map which does not include goal reason chains, but we can just record these separately.\r\n\r\nSadly I am running out of time now. I was hoping to get more done today but I cannot. However, I think what needs to happen in the linker is similar (#3327) : instead of trying to construct a separate `lgBlame` set, we instead should collect `Goal`s as members of the link group, and use those to construct the conflict set.  separate `lgBlame` is not necessary (I hope); though perhaps @grayjay will correct me on that. Note that #3268 is (mostly) independent from this, as that one is less about constructing conflict set as it is about constructing the right link groups in the first place. That said, that PR should probably also be rebased to this branch (or at least, my version of it at https://github.com/edsko/cabal/tree/pr/FixLinkDeps ; still on my TODO list). \r\n\r\nIt is somewhat frustrating that this is so difficult, but this is a subtle topic and I think fixing these issues and documenting and writing this up is rather important. \r\n\r\n@grayjay can I ask you for a favour? Can you rebase all your evil solver unit tests that are still missing from `master` and add them to this `solver` branch, even if they are currently failing? That would be very helpful."},"comment":{"url":"https://api.github.com/repos/haskell/cabal/issues/comments/211169497","html_url":"https://github.com/haskell/cabal/pull/3357#issuecomment-211169497","issue_url":"https://api.github.com/repos/haskell/cabal/issues/3357","id":211169497,"user":{"login":"edsko","id":935288,"avatar_url":"https://avatars.githubusercontent.com/u/935288?v=3","gravatar_id":"","url":"https://api.github.com/users/edsko","html_url":"https://github.com/edsko","followers_url":"https://api.github.com/users/edsko/followers","following_url":"https://api.github.com/users/edsko/following{/other_user}","gists_url":"https://api.github.com/users/edsko/gists{/gist_id}","starred_url":"https://api.github.com/users/edsko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edsko/subscriptions","organizations_url":"https://api.github.com/users/edsko/orgs","repos_url":"https://api.github.com/users/edsko/repos","events_url":"https://api.github.com/users/edsko/events{/privacy}","received_events_url":"https://api.github.com/users/edsko/received_events","type":"User","site_admin":false},"created_at":"2016-04-18T03:11:39Z","updated_at":"2016-04-18T03:11:39Z","body":"> Will this branch be merged into 1.24, if there's enough time?\r\n\r\nI really hope so.\r\n\r\n> @edsko I'll cherry-pick my tests and your comments on the tests.  I can also rebase `pr/FixLinkDeps`.\r\n\r\nIf you can rebase pr/FixLinkDeps and push it to this branch, that would be awesome. I am incredibly strapped for time at the moment. \r\n\r\n> > Instead of collecting which packages are involved in the conflict, we instead collect Goals (packages + goal reason chains).\r\n> \r\n> Does this change apply to all conflict sets?  Will the new `ConflictSet` type only allow insertion of `Goal`s?\r\n\r\nI _think_ it would make sense to say that `ConflictSet`s can only be constructed from two operations: from a `Goal`, or by merging other `ConflictSet`s. If that is not the case, then the exceptions would be quite illustrative. But perhaps @kosmikus can comment here as well.\r\n\r\n> > separate lgBlame is not necessary (I hope); though perhaps @grayjay will correct me on that.\r\n> \r\n> Here's the reason that I thought we needed `lgBlame`.  I think it is possible for packages to become linked for reasons other than the actual linking choice or the introduction of the packages' goals.  `lgBlame` stores those other variables so that they can be added to the conflict set if the link group ever leads to a failure.\r\n> \r\n> Say A depends on B and C, and introduces both goals. B also depends on C, but only when flagB is true.  For some dependency problem, the solver has to choose 0.B and 1.B.  If it links 0.B and 1.B and tries +flagB, it will have to link 0.C and 1.C.  `lgBlame` for 0.C and 1.C's link group will contain 0.flagB.  If linking 1.C leads to a failure, the solver should try -flagB.  Without `lgBlame`, the conflict set would only include 0.C, 1.C, 0.A, and 1.A (as well as any packages that introduced 0.A or 1.A).\r\n\r\nYes, it is important that `flagB` will be included in the conflict set here. However, in your example, the dependency on `C` will have a goal reason chain that includes `flagB`; so, we if base this on `Goal`s (packages + goal reason chains), I think this will be okay? I could be wrong though. "}}