lib/rubygems/dependency_list.rb

   1 #--
   2 # Copyright 2006 by Chad Fowler, Rich Kilmer, Jim Weirich and others.
   3 # All rights reserved.
   4 # See LICENSE.txt for permissions.
   5 #++
   6
   7 require 'tsort'
   8
   9 class Gem::DependencyList
  10
  11   include TSort
  12
  13   def self.from_source_index(src_index)
  14     deps = new
  15
  16     src_index.each do |full_name, spec|
  17       deps.add spec
  18     end
  19
  20     deps
  21   end
  22
  23   def initialize
  24     @specs = []
  25   end
  26
  27   # Adds +gemspecs+ to the dependency list.
  28   def add(*gemspecs)
  29     @specs.push(*gemspecs)
  30   end
  31
  32   # Return a list of the specifications in the dependency list,
  33   # sorted in order so that no spec in the list depends on a gem
  34   # earlier in the list.
  35   #
  36   # This is useful when removing gems from a set of installed gems.
  37   # By removing them in the returned order, you don't get into as
  38   # many dependency issues.
  39   #
  40   # If there are circular dependencies (yuck!), then gems will be
  41   # returned in order until only the circular dependents and anything
  42   # they reference are left.  Then arbitrary gemspecs will be returned
  43   # until the circular dependency is broken, after which gems will be
  44   # returned in dependency order again.
  45   def dependency_order
  46     sorted = strongly_connected_components.flatten
  47
  48     result = []
  49     seen = {}
  50
  51     sorted.each do |spec|
  52       if index = seen[spec.name] then
  53         if result[index].version < spec.version then
  54           result[index] = spec
  55         end
  56       else
  57         seen[spec.name] = result.length
  58         result << spec
  59       end
  60     end
  61
  62     result.reverse
  63   end
  64
  65   def find_name(full_name)
  66     @specs.find { |spec| spec.full_name == full_name }
  67   end
  68
  69   # Are all the dependencies in the list satisfied?
  70   def ok?
  71     @specs.all? do |spec|
  72       spec.runtime_dependencies.all? do |dep|
  73         @specs.find { |s| s.satisfies_requirement? dep }
  74       end
  75     end
  76   end
  77
  78   # Is is ok to remove a gem from the dependency list?
  79   #
  80   # If removing the gemspec creates breaks a currently ok dependency,
  81   # then it is NOT ok to remove the gem.
  82   def ok_to_remove?(full_name)
  83     gem_to_remove = find_name full_name
  84
  85     siblings = @specs.find_all { |s|
  86       s.name == gem_to_remove.name &&
  87         s.full_name != gem_to_remove.full_name
  88     }
  89
  90     deps = []
  91
  92     @specs.each do |spec|
  93       spec.dependencies.each do |dep|
  94         deps << dep if gem_to_remove.satisfies_requirement?(dep)
  95       end
  96     end
  97
  98     deps.all? { |dep|
  99       siblings.any? { |s|
 100         s.satisfies_requirement? dep
 101       }
 102     }
 103   end
 104
 105   def remove_by_name(full_name)
 106     @specs.delete_if { |spec| spec.full_name == full_name }
 107   end
 108
 109   # Return a hash of predecessors.  <tt>result[spec]</tt> is an
 110   # Array of gemspecs that have a dependency satisfied by the named
 111   # spec.
 112   def spec_predecessors
 113     result = Hash.new { |h,k| h[k] = [] }
 114
 115     specs = @specs.sort.reverse
 116
 117     specs.each do |spec|
 118       specs.each do |other|
 119         next if spec == other
 120
 121         other.dependencies.each do |dep|
 122           if spec.satisfies_requirement? dep then
 123             result[spec] << other
 124           end
 125         end
 126       end
 127     end
 128
 129     result
 130   end
 131
 132   def tsort_each_node(&block)
 133     @specs.each(&block)
 134   end
 135
 136   def tsort_each_child(node, &block)
 137     specs = @specs.sort.reverse
 138
 139     node.dependencies.each do |dep|
 140       specs.each do |spec|
 141         if spec.satisfies_requirement? dep then
 142           begin
 143             yield spec
 144           rescue TSort::Cyclic
 145           end
 146           break
 147         end
 148       end
 149     end
 150   end
 151
 152   private
 153
 154   # Count the number of gemspecs in the list +specs+ that are not in
 155   # +ignored+.
 156   def active_count(specs, ignored)
 157     result = 0
 158     specs.each do |spec|
 159       result += 1 unless ignored[spec.full_name]
 160     end
 161     result
 162   end
 163
 164 end
 165