Resolve Gem Dependencies

[sam]

We should use Bundler internally to resolve Gem Dependencies. We'll have to figure out how to use our Doubleshot file as the source, and our Doubleshot.lock file.

I'd estimate this is something we can probably knock out in a day or two, move on to documentation, and then shipit!

[sam]

Here's what I've found out so far:

Bundler::Dependency

Stuff like Bundler::Dependency.new("listen", version: ">=0.5.3") shows up in the specs, so it seems version is actually a Requirement, not a Version. That said, in IRB you'll see the following for that:

listen = Bundler::Dependency.new("listen", :version => '0.5.3')
 => <Bundler::Dependency type=:runtime name="listen" requirements=">= 0">

So either the #inspect output is bad, or something else is going on.

Bundler::Resolver

Resolver::resolve(deps, index) takes an Enumerable of Bundler::Dependencies, and an Index of Gems. The specs/helpers/indexes.rb make it really difficult to figure out what an Index is so far since 90% of the code is in Helpers, and there isn't actually much in the way of Unit tests. :-(

Is the list of deps an exhaustive list of all potential dependencies, and the Resolver just resolves through graphing them? Or is the list just your direct dependencies, and the resolver handles fetching dependencies? Dunno yet.

Bundler::Fetcher

Haven't dug into this too much, but Bundler::Installer appears to use it to download actual Gems to pull out their Gem::Specifications. A comment explains that the gemspecs in the http://rubygems.org indexes are sometimes incorrect, so can't be relied upon.

Putting this together, I'm fairly confused at this point since it seems very unlikely that Bundler is downloading the full Marshal.4.8.Z from http://rubygems.org since just un-marshlling that takes about 3 minutes for me. Is it accumulating dependencies through recursion? That would seem simple, except in order to resolve your graph quickly it seems like you'd need every version of a Gem that meets the currently known requirements (the last bit just as an optimization so you don't waste time downloading gems you already know won't allow you to resolve correctly). You still need to fully resolve the graph at the end of it all.

[sam]

Regarding the last comment, what I meant to communicate is that it doesn't appear that the Fetcher does anything more than grab the specific Gem you've asked for. So who was phone?

[ckrailo]

Does Bundler download the latest possible gem, see if it works, and then downloads the next latest if it doesn't (recursively)? I had dug into that a while back but didn't take notes like I should have. :(

[sam]

The short answer is: Dunno.

[ckrailo]

Okay, so... I think this is what's happening (so it's probably wrong) with regards to getting the specs. Note, I haven't figured out the resolver algorithm yet, but it is what pings the spec source(s). When the resolver needs to get a spec, it checks a local cache first (local_search). If it's not in the local search, then it calls search on the source(s). This leads me to think that batching doesn't happen, but caching does.

I had looked in Resolver, Index, and Source.

[ckrailo]

@sam Read this when you get the chance: http://patshaughnessy.net/2011/9/24/how-does-bundler-bundle

[sam]

Honestly, that doesn't really look any different than what we were discussing... Though there's an opportunity to short-circuit equals dependencies certainly.

We should probably evaluate/sort our list by operator type: =,<,~,>

That would give us:

• =: Predetermined, no alternative resolution possible
• <: Always ideal to pick latest possible
• ~: Ditto.

• : Here's where you probably have the most flexibility, so try to get the latest, but know you can go all the way down to the RHS value of the operator ("1.0" in the example ">=1.0") and be assured that the developer presumably tested with that version, so it's perfectly OK to use it if necessary.

Does that make sense to you? So instead of grabbing our DependencyList in declared order, we process it in order of what's most likely to give us the overall highest versions.

On Tue, Oct 23, 2012 at 9:17 PM, Christopher Krailo < notifications@github.com> wrote:

@sam https://github.com/sam Read this when you get the chance: http://patshaughnessy.net/2011/9/24/how-does-bundler-bundle

— Reply to this email directly or view it on GitHubhttps://github.com/sam/doubleshot/issues/7#issuecomment-9725516.

[ckrailo]

I wonder if we'd end up sorting the dependency list too often. Every time we find out a gem has requirements, we'll add them to our dependency list and then sort again. The algorithm should give the latest regardless of sorting, so I'd be interested in building it with no sorting first (since that's easiest) and then timing it against a version with sorting.

Short-cutting equals dependencies should be easy to do regardless of sorting.

[sam]

Sure. Though I think sorting is really no big deal (that's what a PriorityQueue is). But it's certainly not a must have if you think it complicates thangs.

On Tue, Oct 23, 2012 at 10:01 PM, Christopher Krailo < notifications@github.com> wrote:

I wonder if we'd end up sorting the dependency list too often. Every time we find out a gem has requirements, we'll add them to our dependency list and then sort again. The algorithm should give the latest regardless of sorting, so I'd be interested in building it with no sorting first (since that's easiest) and then timing it against a version with sorting.

Short-cutting equals dependencies should be easy to do regardless of sorting.

— Reply to this email directly or view it on GitHubhttps://github.com/sam/doubleshot/issues/7#issuecomment-9726211.

[ckrailo]

Okay, I've played with things... learning a lot about how Bundler does things, too. I think we need to pseudo-code out their algorithm and implement it very closely. The way they use throw/catch is interesting to me. Trying to build our own recursive algorithm to do what Bundler does seems like it would take more time than essentially copying Bundler.

Another option. If we build some interface classes, we could just use Bundler's resolver. You may want to check out their source and double-check me, but I think we just need to deal with Source and Index. Building a Bundler dependency list shouldn't be too hard either. Besides, I think @indirect mentioned a sort of dev API being in the roadmap for Bundler's future (or at least wanted). Once that happens, we could hook into it and get rid of our interfacing.

Personally, I'd vote option 2.

I've saved my playing around in ckrailo/doubleshot@3dad8ee. Most of what I did should be thrown out, though, so don't do anything with it please. I made lots of changes, went down some rabbit holes, and then decided I needed to call it quits so I can wake up for the dentist tomorrow.

[indirect]

A dev API for Bundler is definitely in the roadmap.

One final option that you may want to check out is reset/solve, a ruby project that implements only the dependency/constraints resolver. It has a very nice external-facing API, but I have no idea if it's actually reliable for real-world usage.

I personally would go with option 2 as well, just because Bundler's resolver is currently tested by so edge cases that we've written into the test suite after running into them in real world uses.