Class: Gem::DependencyResolver

Inherits:
Object
  • Object
show all
Defined in:
lib/rubygems/dependency_resolver.rb

Overview

Given a set of Gem::Dependency objects as needed and a way to query the set of available specs via set, calculates a set of ActivationRequest objects which indicate all the specs that should be activated to meet the all the requirements.

Defined Under Namespace

Classes: APISet, APISpecification, ActivationRequest, CurrentSet, DependencyConflict, DependencyRequest, IndexSet, IndexSpecification

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(needed, set = IndexSet.new) ⇒ DependencyResolver

Create DependencyResolver object which will resolve the tree starting with needed Depedency objects.

set is an object that provides where to look for specifications to satisify the Dependencies. This defaults to IndexSet, which will query rubygems.org.



249
250
251
252
253
254
 
# File 'lib/rubygems/dependency_resolver.rb', line 249

def initialize(needed, set=IndexSet.new)
  @set = set || IndexSet.new # Allow nil to mean IndexSet
  @needed = needed

  @conflicts = nil
end

Instance Attribute Details

#conflicts ⇒ Object (readonly)

Contains all the conflicts encountered while doing resolution



265
266
267
 
# File 'lib/rubygems/dependency_resolver.rb', line 265

def conflicts
  @conflicts
end

Class Method Details

.for_current_gems(needed) ⇒ Object

Provide a DependencyResolver that queries only against the already installed gems.



259
260
261
 
# File 'lib/rubygems/dependency_resolver.rb', line 259

def self.for_current_gems(needed)
  new needed, CurrentSet.new
end

Instance Method Details

#requests(s, act) ⇒ Object 



424
425
426
427
428
429
430
431
432
433
434
 
# File 'lib/rubygems/dependency_resolver.rb', line 424

def requests(s, act)
  reqs = []
  s.dependencies.each do |d|
    next unless d.type == :runtime
    reqs << DependencyRequest.new(d, act)
  end

  @set.prefetch(reqs)

  reqs
end

#resolve ⇒ Object

Proceed with resolution! Returns an array of ActivationRequest objects.



270
271
272
273
274
275
276
277
278
279
280
281
282
 
# File 'lib/rubygems/dependency_resolver.rb', line 270

def resolve
  @conflicts = []

  needed = @needed.map { |n| DependencyRequest.new(n, nil) }

  res = resolve_for needed, []

  if res.kind_of? DependencyConflict
    raise DependencyResolutionError.new(res)
  end

  res
end

#resolve_for(needed, specs) ⇒ Object

The meat of the algorithm. Given needed DependencyRequest objects and specs being a list to ActivationRequest, calculate a new list of ActivationRequest objects.



440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
 
# File 'lib/rubygems/dependency_resolver.rb', line 440

def resolve_for(needed, specs)
  until needed.empty?
    dep = needed.shift

    # If there is already a spec activated for the requested name...
    if existing = specs.find { |s| dep.name == s.name }

      # then we're done since this new dep matches the
      # existing spec.
      next if dep.matches_spec? existing

      # There is a conflict! We return the conflict
      # object which will be seen by the caller and be
      # handled at the right level.

      # If the existing activation indicates that there
      # are other possibles for it, then issue the conflict
      # on the dep for the activation itself. Otherwise, issue
      # it on the requester's request itself.
      #
      if existing.others_possible?
        conflict = DependencyConflict.new(dep, existing)
      else
        depreq = existing.request.requester.request
        conflict = DependencyConflict.new(depreq, existing, dep)
      end
      @conflicts << conflict

      return conflict
    end

    # Get a list of all specs that satisfy dep
    possible = @set.find_all(dep)

    case possible.size
    when 0
      # If there are none, then our work here is done.
      raise UnsatisfiableDepedencyError.new(dep)
    when 1
      # If there is one, then we just add it to specs
      # and process the specs dependencies by adding
      # them to needed.

      spec = possible.first
      act =  ActivationRequest.new(spec, dep, false)

      specs << act

      # Put the deps for at the beginning of needed
      # rather than the end to match the depth first
      # searching done by the multiple case code below.
      #
      # This keeps the error messages consistent.
      needed = requests(spec, act) + needed
    else
      # There are multiple specs for this dep. This is
      # the case that this class is built to handle.

      # Sort them so that we try the highest versions
      # first.
      possible = possible.sort_by { |s| s.version }

      # We track the conflicts seen so that we can report them
      # to help the user figure out how to fix the situation.
      conflicts = []

      # To figure out which to pick, we keep resolving
      # given each one being activated and if there isn't
      # a conflict, we know we've found a full set.
      #
      # We use an until loop rather than #reverse_each
      # to keep the stack short since we're using a recursive
      # algorithm.
      #
      until possible.empty?
        s = possible.pop

        # Recursively call #resolve_for with this spec
        # and add it's dependencies into the picture...

        act = ActivationRequest.new(s, dep)

        try = requests(s, act) + needed

        res = resolve_for(try, specs + [act])

        # While trying to resolve these dependencies, there may
        # be a conflict!

        if res.kind_of? DependencyConflict
          # The conflict might be created not by this invocation
          # but rather one up the stack, so if we can't attempt
          # to resolve this conflict (conflict isn't with the spec +s+)
          # then just return it so the caller can try to sort it out.
          return res unless res.for_spec? s

          # Otherwise, this is a conflict that we can attempt to fix
          conflicts << [s, res]

          # Optimization:
          #
          # Because the conflict indicates the dependency that trigger
          # it, we can prune possible based on this new information.
          #
          # This cuts down on the number of iterations needed.
          possible.delete_if { |x| !res.dependency.matches_spec? x }
        else
          # No conflict, return the specs
          return res
        end
      end

      # We tried all possibles and nothing worked, so we let the user
      # know and include as much information about the problem since
      # the user is going to have to take action to fix this.
      raise ImpossibleDependenciesError.new(dep, conflicts)
    end
  end

  specs
end