Support a different/better dependency solver WAS Add ability to generate stack.yml with a dependency solver

[ndmitchell]

It seems if either of the stackage LTS things fail, or you have non-Stackage dependencies, you are a little bit stuck and have to do a lot more work than Cabal. Why not fall back to running cabal configure, stealing the dependencies they compute, and writing those into the .yaml file? That way you can still use stack for all the other benefits, and hopefully it means you can avoid adding a dependency solver to stack.

[snoyberg]

I had planned on something like this but didn't get around to it yet. We're definitely set up for it. In the future we'll hopefully have access to a sat based solver, but using cabal in the short term is pragmatic.

[NathanHowell]

@ndmitchell I've been working on a constraint solver for a while, but it has a dependency on Z3... so having a fallback on cabal-install might be a good idea long term too, just in case Z3 isn't installed.

wip is here: https://github.com/HakeIO/hake-solver/blob/master/src/Development/Hake/Solver.hs

[tomjaguarpaw]

I have a proof-of-concept cabal solver that uses minisat. What are the requirements of integrating such a thing into stack? If it needs a native Haskell solver I can try to test some of them for speed, but I'm not particularly optimistic that they'll get close to external solver speeds.

[ndmitchell]

@tomjaguarpaw - do you have benchmarks? How easy would it be to switch in https://hackage.haskell.org/package/incremental-sat-solver and see if it is too slow?

[tomjaguarpaw]

I discovered that Haskell toysolver is about 60 times slower than minisat. They were the only two I tried. minisat seemed promising but toysolver not. The API of incremental-sat-solver seems nice and neat so I should be able to benchmark it fairly quickly when I get a moment.

[snoyberg]

We have different options here, from including the SAT solver in the stack codebase, to making it a library dependency, to making it an external tool that stack calls out to. Given that we have at least three solvers we may consider (Nathan's, Tom's, and cabal-install), I'm leaning towards the third option, and just having a hard-coded list of executables to try using in stack. If we go that route, then there are no requirements for how the tool is implemented.

[tomjaguarpaw]

I just remembered why I didn't try incremental-sat-solver: it doesn't natively handle integers, so I'd have to write an encoding. That'll take a bit longer ... I guess I could just use it as a backend to ersatz.

[acowley]

Out of curiosity, can you ballpark what kinds of times are we talking about here, @tomjaguarpaw ? If it's 60 times a really small number, that might be fine.

[tomjaguarpaw]

minisat was 0.5s per iteration, toysolver 30s. I need several iterations to converge to a result, so I couldn't continue with toysolver. Don't take any of this too seriously though, as I haven't tried to optimize anything yet.

[gregwebs]

I think this is where @NathanHowell solver is https://github.com/HakeIO/hake-solver/blob/master/src/Development/Hake/Solver.hs

[NathanHowell]

@tomjaguarpaw Is your PoC available somewhere? I'm planning on working on mine this weekend at Bayhac, would be nice to see some other implementations.

[tomjaguarpaw]

I'll see if I can upload it this weekend so you can look at it.

[tomjaguarpaw]

Here's my proof-of-concept: https://github.com/tomjaguarpaw/solver-example

[snoyberg]

I've just implemented a first version of this feature on top of cabal-install. If people have projects that were not working out of the box with a snapshot, please give it a shot. I'd still rather use a different dependency solver in the future, especially one that could be snapshot-aware and therefore not force everything into extra-deps. But this is a good first step IMO.

I'm going to keep this issue open for the "better dependency solver" aspect, but move the issue to a later milestone.

[snoyberg]

Is there anyone out there who's still interested in this? I personally almost never use a dependency solver.

[hesselink]

We currently use the solver to update custom snapshots to newer versions: we temporarily disable the snapshot and run the solver, then compare the output of that to the snapshot. The problem we currently have is that the solver enables tests, also for packages marked with 'extra-dep: true'. This causes it to not find a plan, since the test suites of some forks we have, have very old dependencies.

With a custom solver stack might implement logic for this, fixing this issue. However, since it's such a small use case I'm not sure that alone is worth it.

[bitemyapp]

@snoyberg I don't, generally, but it's possible people will gripe about manually updating extra deps.

[NathanHowell]

The Z3 based solver has some unit tests now ;-) implementation is still incomplete, one of these weekends I'll try to get the last major bits plugged in.

https://github.com/HakeIO/hake-solver/blob/master/tests/UnitTests.hs

[tomjaguarpaw]

@NathanHowell How is the performance? That's the area I found difficult with a generic solver.

[NathanHowell]

@tomjaguarpaw Hard to guess how performance will be once it's feature complete but I hope it will remain sub-second. Earlier tests were giving times in the 10-100ms range.

The original idea for the solver was to be fast enough that it can be hosted on a server (the static Hackage poc I had put together w/ Hakyll), and alleviate the need to store a package list on the client or do constraint solving there.

[snoyberg]

Just wanted to point out that even with a server-based solver, we'll still
need to download the package index locally to deal with revised cabal files.

On Thu, Oct 1, 2015, 1:01 AM Nathan Howell notifications@github.com wrote:

@tomjaguarpaw https://github.com/tomjaguarpaw Hard to guess how
performance will be once it's feature complete but I hope it will remain
sub-second. Earlier tests were giving times in the 10-100ms range.

The original idea for the solver was to be fast enough that it can be
hosted on a server (the static Hackage poc I had put together w/ Hakyll),
and alleviate the need to store a package list on the client or do
constraint solving there.

—
Reply to this email directly or view it on GitHub
#116 (comment)
.

[tomjaguarpaw]

@NathanHowell Could you make a minimal example showing how your solver works? The test cases are currently failing on Hackage. I downloaded the package and did some fiddling to try to get it to work but it certainly didn't work in less than one second!

[NathanHowell]

@tomjaguarpaw I'm assuming you're talking about the tests that parse all of Hackage... yes that does take a while. It's failing due to an incomplete implementation of default flags and multiple goals so I've disabled it. The unit tests don't exercise this functionality so they pass and complete in <5ms on my laptop, but these only test some simple constraints.

As far as examples go I'd point you towards the unit tests (tests/UnitTests.hs) for now. Once the flag stuff is fixed the preferred entrypoint will be getInstallationPlan https://github.com/HakeIO/hake-solver/blob/master/src/Development/Hake/Solver.hs#L467.

[harendra-kumar]

I implemented a number of improvements to the solver via #1583 . Major changes include:

• Use the best snapshot (with least dep errors) as a resolver and add extra deps on top of that
• Use the right (compatible with the constraints) compiler automatically and install the compiler via --install-ghc if needed

Does that fix this issue?

[mgsloan]

Yeah, I think it's safe to close this issue.

Of course, folks should feel free to implement a fancy new solver! (but open a new issue / PR about it)