1require 'rubygems' 2require 'rubygems/dependency' 3require 'rubygems/exceptions' 4 5require 'uri' 6require 'net/http' 7 8module Gem 9 10 # Raised when a DependencyConflict reaches the toplevel. 11 # Indicates which dependencies were incompatible. 12 # 13 class DependencyResolutionError < Gem::Exception 14 def initialize(conflict) 15 @conflict = conflict 16 a, b = conflicting_dependencies 17 18 super "unable to resolve conflicting dependencies '#{a}' and '#{b}'" 19 end 20 21 attr_reader :conflict 22 23 def conflicting_dependencies 24 @conflict.conflicting_dependencies 25 end 26 end 27 28 # Raised when a dependency requests a gem for which there is 29 # no spec. 30 # 31 class UnsatisfiableDepedencyError < Gem::Exception 32 def initialize(dep) 33 super "unable to find any gem matching dependency '#{dep}'" 34 35 @dependency = dep 36 end 37 38 attr_reader :dependency 39 end 40 41 # Raised when dependencies conflict and create the inability to 42 # find a valid possible spec for a request. 43 # 44 class ImpossibleDependenciesError < Gem::Exception 45 def initialize(request, conflicts) 46 s = conflicts.size == 1 ? "" : "s" 47 super "detected #{conflicts.size} conflict#{s} with dependency '#{request.dependency}'" 48 @request = request 49 @conflicts = conflicts 50 end 51 52 def dependency 53 @request.dependency 54 end 55 56 attr_reader :conflicts 57 end 58 59 # Given a set of Gem::Dependency objects as +needed+ and a way 60 # to query the set of available specs via +set+, calculates 61 # a set of ActivationRequest objects which indicate all the specs 62 # that should be activated to meet the all the requirements. 63 # 64 class DependencyResolver 65 66 # Represents a specification retrieved via the rubygems.org 67 # API. This is used to avoid having to load the full 68 # Specification object when all we need is the name, version, 69 # and dependencies. 70 # 71 class APISpecification 72 attr_reader :set # :nodoc: 73 74 def initialize(set, api_data) 75 @set = set 76 @name = api_data[:name] 77 @version = Gem::Version.new api_data[:number] 78 @dependencies = api_data[:dependencies].map do |name, ver| 79 Gem::Dependency.new name, ver.split(/\s*,\s*/) 80 end 81 end 82 83 attr_reader :name, :version, :dependencies 84 85 def == other # :nodoc: 86 self.class === other and 87 @set == other.set and 88 @name == other.name and 89 @version == other.version and 90 @dependencies == other.dependencies 91 end 92 93 def full_name 94 "#{@name}-#{@version}" 95 end 96 end 97 98 # The global rubygems pool, available via the rubygems.org API. 99 # Returns instances of APISpecification. 100 # 101 class APISet 102 def initialize 103 @data = Hash.new { |h,k| h[k] = [] } 104 @dep_uri = URI 'https://rubygems.org/api/v1/dependencies' 105 end 106 107 # Return data for all versions of the gem +name+. 108 # 109 def versions(name) 110 if @data.key?(name) 111 return @data[name] 112 end 113 114 uri = @dep_uri + "?gems=#{name}" 115 str = Gem::RemoteFetcher.fetcher.fetch_path uri 116 117 Marshal.load(str).each do |ver| 118 @data[ver[:name]] << ver 119 end 120 121 @data[name] 122 end 123 124 # Return an array of APISpecification objects matching 125 # DependencyRequest +req+. 126 # 127 def find_all(req) 128 res = [] 129 130 versions(req.name).each do |ver| 131 if req.dependency.match? req.name, ver[:number] 132 res << APISpecification.new(self, ver) 133 end 134 end 135 136 res 137 end 138 139 # A hint run by the resolver to allow the Set to fetch 140 # data for DependencyRequests +reqs+. 141 # 142 def prefetch(reqs) 143 names = reqs.map { |r| r.dependency.name } 144 needed = names.find_all { |d| !@data.key?(d) } 145 146 return if needed.empty? 147 148 uri = @dep_uri + "?gems=#{needed.sort.join ','}" 149 str = Gem::RemoteFetcher.fetcher.fetch_path uri 150 151 Marshal.load(str).each do |ver| 152 @data[ver[:name]] << ver 153 end 154 end 155 end 156 157 # Represents a possible Specification object returned 158 # from IndexSet. Used to delay needed to download full 159 # Specification objects when only the +name+ and +version+ 160 # are needed. 161 # 162 class IndexSpecification 163 def initialize(set, name, version, source, plat) 164 @set = set 165 @name = name 166 @version = version 167 @source = source 168 @platform = plat 169 170 @spec = nil 171 end 172 173 attr_reader :name, :version, :source 174 175 def full_name 176 "#{@name}-#{@version}" 177 end 178 179 def spec 180 @spec ||= @set.load_spec(@name, @version, @source) 181 end 182 183 def dependencies 184 spec.dependencies 185 end 186 end 187 188 # The global rubygems pool represented via the traditional 189 # source index. 190 # 191 class IndexSet 192 def initialize 193 @f = Gem::SpecFetcher.fetcher 194 195 @all = Hash.new { |h,k| h[k] = [] } 196 197 list, _ = @f.available_specs(:released) 198 list.each do |uri, specs| 199 specs.each do |n| 200 @all[n.name] << [uri, n] 201 end 202 end 203 204 @specs = {} 205 end 206 207 # Return an array of IndexSpecification objects matching 208 # DependencyRequest +req+. 209 # 210 def find_all(req) 211 res = [] 212 213 name = req.dependency.name 214 215 @all[name].each do |uri, n| 216 if req.dependency.match? n 217 res << IndexSpecification.new(self, n.name, n.version, 218 uri, n.platform) 219 end 220 end 221 222 res 223 end 224 225 # No prefetching needed since we load the whole index in 226 # initially. 227 # 228 def prefetch(gems) 229 end 230 231 # Called from IndexSpecification to get a true Specification 232 # object. 233 # 234 def load_spec(name, ver, source) 235 key = "#{name}-#{ver}" 236 @specs[key] ||= source.fetch_spec(Gem::NameTuple.new(name, ver)) 237 end 238 end 239 240 # A set which represents the installed gems. Respects 241 # all the normal settings that control where to look 242 # for installed gems. 243 # 244 class CurrentSet 245 def find_all(req) 246 req.dependency.matching_specs 247 end 248 249 def prefetch(gems) 250 end 251 end 252 253 # Create DependencyResolver object which will resolve 254 # the tree starting with +needed+ Depedency objects. 255 # 256 # +set+ is an object that provides where to look for 257 # specifications to satisify the Dependencies. This 258 # defaults to IndexSet, which will query rubygems.org. 259 # 260 def initialize(needed, set=IndexSet.new) 261 @set = set || IndexSet.new # Allow nil to mean IndexSet 262 @needed = needed 263 264 @conflicts = nil 265 end 266 267 # Provide a DependencyResolver that queries only against 268 # the already installed gems. 269 # 270 def self.for_current_gems(needed) 271 new needed, CurrentSet.new 272 end 273 274 # Contains all the conflicts encountered while doing resolution 275 # 276 attr_reader :conflicts 277 278 # Proceed with resolution! Returns an array of ActivationRequest 279 # objects. 280 # 281 def resolve 282 @conflicts = [] 283 284 needed = @needed.map { |n| DependencyRequest.new(n, nil) } 285 286 res = resolve_for needed, [] 287 288 if res.kind_of? DependencyConflict 289 raise DependencyResolutionError.new(res) 290 end 291 292 res 293 end 294 295 # Used internally to indicate that a dependency conflicted 296 # with a spec that would be activated. 297 # 298 class DependencyConflict 299 def initialize(dependency, activated, failed_dep=dependency) 300 @dependency = dependency 301 @activated = activated 302 @failed_dep = failed_dep 303 end 304 305 attr_reader :dependency, :activated 306 307 # Return the Specification that listed the dependency 308 # 309 def requester 310 @failed_dep.requester 311 end 312 313 def for_spec?(spec) 314 @dependency.name == spec.name 315 end 316 317 # Return the 2 dependency objects that conflicted 318 # 319 def conflicting_dependencies 320 [@failed_dep.dependency, @activated.request.dependency] 321 end 322 end 323 324 # Used Internally. Wraps a Depedency object to also track 325 # which spec contained the Dependency. 326 # 327 class DependencyRequest 328 def initialize(dep, act) 329 @dependency = dep 330 @requester = act 331 end 332 333 attr_reader :dependency, :requester 334 335 def name 336 @dependency.name 337 end 338 339 def matches_spec?(spec) 340 @dependency.matches_spec? spec 341 end 342 343 def to_s 344 @dependency.to_s 345 end 346 347 def ==(other) 348 case other 349 when Dependency 350 @dependency == other 351 when DependencyRequest 352 @dependency == other.dependency && @requester == other.requester 353 else 354 false 355 end 356 end 357 end 358 359 # Specifies a Specification object that should be activated. 360 # Also contains a dependency that was used to introduce this 361 # activation. 362 # 363 class ActivationRequest 364 def initialize(spec, req, others_possible=true) 365 @spec = spec 366 @request = req 367 @others_possible = others_possible 368 end 369 370 attr_reader :spec, :request 371 372 # Indicate if this activation is one of a set of possible 373 # requests for the same Dependency request. 374 # 375 def others_possible? 376 @others_possible 377 end 378 379 # Return the ActivationRequest that contained the dependency 380 # that we were activated for. 381 # 382 def parent 383 @request.requester 384 end 385 386 def name 387 @spec.name 388 end 389 390 def full_name 391 @spec.full_name 392 end 393 394 def version 395 @spec.version 396 end 397 398 def full_spec 399 Gem::Specification === @spec ? @spec : @spec.spec 400 end 401 402 def download(path) 403 if @spec.respond_to? :source 404 source = @spec.source 405 else 406 source = Gem.sources.first 407 end 408 409 Gem.ensure_gem_subdirectories path 410 411 source.download full_spec, path 412 end 413 414 def ==(other) 415 case other 416 when Gem::Specification 417 @spec == other 418 when ActivationRequest 419 @spec == other.spec && @request == other.request 420 else 421 false 422 end 423 end 424 425 ## 426 # Indicates if the requested gem has already been installed. 427 428 def installed? 429 this_spec = full_spec 430 431 Gem::Specification.any? do |s| 432 s == this_spec 433 end 434 end 435 end 436 437 def requests(s, act) 438 reqs = [] 439 s.dependencies.each do |d| 440 next unless d.type == :runtime 441 reqs << DependencyRequest.new(d, act) 442 end 443 444 @set.prefetch(reqs) 445 446 reqs 447 end 448 449 # The meat of the algorithm. Given +needed+ DependencyRequest objects 450 # and +specs+ being a list to ActivationRequest, calculate a new list 451 # of ActivationRequest objects. 452 # 453 def resolve_for(needed, specs) 454 until needed.empty? 455 dep = needed.shift 456 457 # If there is already a spec activated for the requested name... 458 if existing = specs.find { |s| dep.name == s.name } 459 460 # then we're done since this new dep matches the 461 # existing spec. 462 next if dep.matches_spec? existing 463 464 # There is a conflict! We return the conflict 465 # object which will be seen by the caller and be 466 # handled at the right level. 467 468 # If the existing activation indicates that there 469 # are other possibles for it, then issue the conflict 470 # on the dep for the activation itself. Otherwise, issue 471 # it on the requester's request itself. 472 # 473 if existing.others_possible? 474 conflict = DependencyConflict.new(dep, existing) 475 else 476 depreq = existing.request.requester.request 477 conflict = DependencyConflict.new(depreq, existing, dep) 478 end 479 @conflicts << conflict 480 481 return conflict 482 end 483 484 # Get a list of all specs that satisfy dep 485 possible = @set.find_all(dep) 486 487 case possible.size 488 when 0 489 # If there are none, then our work here is done. 490 raise UnsatisfiableDepedencyError.new(dep) 491 when 1 492 # If there is one, then we just add it to specs 493 # and process the specs dependencies by adding 494 # them to needed. 495 496 spec = possible.first 497 act = ActivationRequest.new(spec, dep, false) 498 499 specs << act 500 501 # Put the deps for at the beginning of needed 502 # rather than the end to match the depth first 503 # searching done by the multiple case code below. 504 # 505 # This keeps the error messages consistent. 506 needed = requests(spec, act) + needed 507 else 508 # There are multiple specs for this dep. This is 509 # the case that this class is built to handle. 510 511 # Sort them so that we try the highest versions 512 # first. 513 possible = possible.sort_by { |s| s.version } 514 515 # We track the conflicts seen so that we can report them 516 # to help the user figure out how to fix the situation. 517 conflicts = [] 518 519 # To figure out which to pick, we keep resolving 520 # given each one being activated and if there isn't 521 # a conflict, we know we've found a full set. 522 # 523 # We use an until loop rather than #reverse_each 524 # to keep the stack short since we're using a recursive 525 # algorithm. 526 # 527 until possible.empty? 528 s = possible.pop 529 530 # Recursively call #resolve_for with this spec 531 # and add it's dependencies into the picture... 532 533 act = ActivationRequest.new(s, dep) 534 535 try = requests(s, act) + needed 536 537 res = resolve_for(try, specs + [act]) 538 539 # While trying to resolve these dependencies, there may 540 # be a conflict! 541 542 if res.kind_of? DependencyConflict 543 # The conflict might be created not by this invocation 544 # but rather one up the stack, so if we can't attempt 545 # to resolve this conflict (conflict isn't with the spec +s+) 546 # then just return it so the caller can try to sort it out. 547 return res unless res.for_spec? s 548 549 # Otherwise, this is a conflict that we can attempt to fix 550 conflicts << [s, res] 551 552 # Optimization: 553 # 554 # Because the conflict indicates the dependency that trigger 555 # it, we can prune possible based on this new information. 556 # 557 # This cuts down on the number of iterations needed. 558 possible.delete_if { |x| !res.dependency.matches_spec? x } 559 else 560 # No conflict, return the specs 561 return res 562 end 563 end 564 565 # We tried all possibles and nothing worked, so we let the user 566 # know and include as much information about the problem since 567 # the user is going to have to take action to fix this. 568 raise ImpossibleDependenciesError.new(dep, conflicts) 569 end 570 end 571 572 specs 573 end 574 end 575end 576