[Rubygems-developers] Dependency Resolution

Trans transfire at gmail.com
Wed Aug 4 02:31:18 EDT 2010

On Aug 3, 5:25 am, James Tucker <jftuc... at gmail.com> wrote:
> On 2 Aug 2010, at 18:01, Trans wrote:
> > Hi--
> > I wrote up some code for doing dependency resolution. Right now I am
> > using my own Version class to do the constraint comparisons, but it
> > shouldn't too hard to adapt to RubyGems'.
> > With a bit of tweaking perhaps this can get into the RubyGems?
> I'd like to see a runtime dependency tree resolver in RubyGems, but if we are to include one, I would like it to resolve some complex graphs:
>  - Cycles
>  - Troughs
>  - Traps
> A completely linear resolver I don't think can do this. You might want to read through the comments in the resolver in bundler, and it's test suite, to see what I'm talking about.

I'll take a look, thanks.

The resolver I wrote recurses through the dependency tree adding each
dependency to a flat 'request' list, unless an entry already exists
with the same exact name and constraint, in which case the recursion
backtracks. At the same time it collects every available version of a
gem by that name. It then works through the request list rejecting
versions that don't conform, leaving in the final result only the
viable versions (or an empty list if none). I've thought about a good
bit, and I can't think of a way in which that wouldn't work. Perhaps b/
c it is a two-pass solution, it mitigates that fact that it is linear?
But yea, I could be missing something. I'll read up and write some
tests to be sure.

> > While I am on the subject, the Gemdo::Version class I'm using can
> > handle version constraints in these formats:
> >  1.0+   (same as >= 1.0)
> >  1.0-    (same as < 1.0)
> >  1.0~   (same as ~> 1.0)
> I like this, I would say though, adding this could have quite a marked effect on performance with the current design, as Gem::Version is created and parsed all the time.

I wouldn't think it would be any more difficult to parse than the
currently accepted formats, but then I'm not sure how it's coded, so
you might be right. Even so I wouldn't expect it be too much overhead.
One could map it pretty easily. Something like:

  c = { '+'=>">=", ... }

  ver = c[ver[-1,1]] + ver[0...-1] if c.key?(ver[-1,1])

More information about the Rubygems-developers mailing list