summaryrefslogtreecommitdiff
path: root/lib/rubygems/resolver.rb
blob: ef17d682ac86ceebc868b877107c7649253a9e69 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
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
require 'rubygems/dependency'
require 'rubygems/exceptions'
require 'rubygems/util/list'

require 'uri'
require 'net/http'

##
# 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.

class Gem::Resolver

  ##
  # If the DEBUG_RESOLVER environment variable is set then debugging mode is
  # enabled for the resolver.  This will display information about the state
  # of the resolver while a set of dependencies is being resolved.

  DEBUG_RESOLVER = !ENV['DEBUG_RESOLVER'].nil?

  require 'pp' if DEBUG_RESOLVER

  ##
  # Contains all the conflicts encountered while doing resolution

  attr_reader :conflicts

  ##
  # Set to true if all development dependencies should be considered.

  attr_accessor :development

  ##
  # Set to true if immediate development dependencies should be considered.

  attr_accessor :development_shallow

  ##
  # When true, no dependencies are looked up for requested gems.

  attr_accessor :ignore_dependencies

  ##
  # List of dependencies that could not be found in the configured sources.

  attr_reader :missing

  attr_reader :stats

  ##
  # Hash of gems to skip resolution.  Keyed by gem name, with arrays of
  # gem specifications as values.

  attr_accessor :skip_gems

  ##
  # When a missing dependency, don't stop. Just go on and record what was
  # missing.

  attr_accessor :soft_missing

  ##
  # Combines +sets+ into a ComposedSet that allows specification lookup in a
  # uniform manner.  If one of the +sets+ is itself a ComposedSet its sets are
  # flattened into the result ComposedSet.

  def self.compose_sets *sets
    sets.compact!

    sets = sets.map do |set|
      case set
      when Gem::Resolver::BestSet then
        set
      when Gem::Resolver::ComposedSet then
        set.sets
      else
        set
      end
    end.flatten

    case sets.length
    when 0 then
      raise ArgumentError, 'one set in the composition must be non-nil'
    when 1 then
      sets.first
    else
      Gem::Resolver::ComposedSet.new(*sets)
    end
  end

  ##
  # Creates a Resolver that queries only against the already installed gems
  # for the +needed+ dependencies.

  def self.for_current_gems needed
    new needed, Gem::Resolver::CurrentSet.new
  end

  ##
  # Create Resolver object which will resolve the tree starting
  # with +needed+ Dependency objects.
  #
  # +set+ is an object that provides where to look for specifications to
  # satisfy the Dependencies. This defaults to IndexSet, which will query
  # rubygems.org.

  def initialize needed, set = nil
    @set = set || Gem::Resolver::IndexSet.new
    @needed = needed

    @conflicts           = []
    @development         = false
    @development_shallow = false
    @ignore_dependencies = false
    @missing             = []
    @skip_gems           = {}
    @soft_missing        = false
    @stats               = Gem::Resolver::Stats.new
  end

  def explain stage, *data # :nodoc:
    return unless DEBUG_RESOLVER

    d = data.map { |x| x.pretty_inspect }.join(", ")
    $stderr.printf "%10s %s\n", stage.to_s.upcase, d
  end

  def explain_list stage # :nodoc:
    return unless DEBUG_RESOLVER

    data = yield
    $stderr.printf "%10s (%d entries)\n", stage.to_s.upcase, data.size
    PP.pp data, $stderr unless data.empty?
  end

  ##
  # Creates an ActivationRequest for the given +dep+ and the last +possible+
  # specification.
  #
  # Returns the Specification and the ActivationRequest

  def activation_request dep, possible # :nodoc:
    spec = possible.pop

    explain :activate, [spec.full_name, possible.size]
    explain :possible, possible

    activation_request =
      Gem::Resolver::ActivationRequest.new spec, dep, possible

    return spec, activation_request
  end

  def requests s, act, reqs=nil # :nodoc:
    return reqs if @ignore_dependencies

    s.fetch_development_dependencies if @development

    s.dependencies.reverse_each do |d|
      next if d.type == :development and not @development
      next if d.type == :development and @development_shallow and
              act.development?
      next if d.type == :development and @development_shallow and
              act.parent

      reqs.add Gem::Resolver::DependencyRequest.new(d, act)
      @stats.requirement!
    end

    @set.prefetch reqs

    @stats.record_requirements reqs

    reqs
  end

  ##
  # Proceed with resolution! Returns an array of ActivationRequest objects.

  def resolve
    @conflicts = []

    needed = Gem::Resolver::RequirementList.new

    @needed.reverse_each do |n|
      request = Gem::Resolver::DependencyRequest.new n, nil

      needed.add request
      @stats.requirement!
    end

    @stats.record_requirements needed

    res = resolve_for needed, nil

    raise Gem::DependencyResolutionError, res if
      res.kind_of? Gem::Resolver::Conflict

    res.to_a
  end

  ##
  # Extracts the specifications that may be able to fulfill +dependency+ and
  # returns those that match the local platform and all those that match.

  def find_possible dependency # :nodoc:
    all = @set.find_all dependency

    if (skip_dep_gems = skip_gems[dependency.name]) && !skip_dep_gems.empty?
      matching = all.select do |api_spec|
        skip_dep_gems.any? { |s| api_spec.version == s.version }
      end

      all = matching unless matching.empty?
    end

    matching_platform = select_local_platforms all

    return matching_platform, all
  end

  def handle_conflict(dep, existing) # :nodoc:
    # 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 dependency for the activation itself.
    # Otherwise, if there was a requester, issue it on the requester's
    # request itself.
    # Finally, if the existing request has no requester (toplevel) unwind to
    # it anyway.

    if existing.others_possible?
      conflict =
        Gem::Resolver::Conflict.new dep, existing
    elsif dep.requester
      depreq = dep.requester.request
      conflict =
        Gem::Resolver::Conflict.new depreq, existing, dep
    elsif existing.request.requester.nil?
      conflict =
        Gem::Resolver::Conflict.new dep, existing
    else
      raise Gem::DependencyError, "Unable to figure out how to unwind conflict"
    end

    @conflicts << conflict unless @conflicts.include? conflict

    return conflict
  end

  # Contains the state for attempting activation of a set of possible specs.
  # +needed+ is a Gem::List of DependencyRequest objects that, well, need
  # to be satisfied.
  # +specs+ is the List of ActivationRequest that are being tested.
  # +dep+ is the DependencyRequest that was used to generate this state.
  # +spec+ is the Specification for this state.
  # +possible+ is List of DependencyRequest objects that can be tried to
  # find a  complete set.
  # +conflicts+ is a [DependencyRequest, Conflict] hit tried to
  # activate the state.
  #
  State = Struct.new(:needed, :specs, :dep, :spec, :possibles, :conflicts) do
    def summary # :nodoc:
      nd = needed.map { |s| s.to_s }.sort if nd

      if specs then
        ss = specs.map { |s| s.full_name }.sort
        ss.unshift ss.length
      end

      d = dep.to_s
      d << " from #{dep.requester.full_name}" if dep.requester

      ps = possibles.map { |p| p.full_name }.sort
      ps.unshift ps.length

      cs = conflicts.map do |(s, c)|
        [s.full_name, c.conflicting_dependencies.map { |cd| cd.to_s }]
      end

      { :needed => nd, :specs => ss, :dep => d, :spec => spec.full_name,
        :possibles => ps, :conflicts => cs }
    end
  end

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

  def resolve_for needed, specs # :nodoc:
    # The State objects that are used to attempt the activation tree.
    states = []

    while !needed.empty?
      @stats.iteration!

      dep = needed.remove
      explain :try, [dep, dep.requester ? dep.requester.request : :toplevel]
      explain_list(:next5) { needed.next5 }
      explain_list(:specs) { Array(specs).map { |x| x.full_name }.sort }

      # If there is already a spec activated for the requested name...
      if specs && 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

        conflict = handle_conflict dep, existing

        return conflict unless dep.requester

        explain :conflict, dep, :existing, existing.full_name

        depreq = dep.requester.request

        state = nil
        until states.empty?
          x = states.pop

          i = existing.request.requester
          explain :consider, x.spec.full_name, [depreq.name, dep.name, i ? i.name : :top]

          if x.spec.name == depreq.name or
              x.spec.name == dep.name or
              (i && (i.name == x.spec.name))
            explain :found, x.spec.full_name
            state = x
            break
          end
        end

        return conflict unless state

        @stats.backtracking!

        needed, specs = resolve_for_conflict needed, specs, state

        states << state unless state.possibles.empty?

        next
      end

      matching, all = find_possible dep

      case matching.size
      when 0
        resolve_for_zero dep, all
      when 1
        needed, specs =
          resolve_for_single needed, specs, dep, matching
      else
        needed, specs =
          resolve_for_multiple needed, specs, states, dep, matching
      end
    end

    specs
  end

  ##
  # Rewinds +needed+ and +specs+ to a previous state in +state+ for a conflict
  # between +dep+ and +existing+.

  def resolve_for_conflict needed, specs, state # :nodoc:
    # We exhausted the possibles so it's definitely not going to work out,
    # bail out.
    raise Gem::ImpossibleDependenciesError.new state.dep, state.conflicts if
      state.possibles.empty?

    # Retry resolution with this spec and add it's dependencies
    spec, act = activation_request state.dep, state.possibles

    needed = requests spec, act, state.needed.dup
    specs = Gem::List.prepend state.specs, act

    return needed, specs
  end

  ##
  # There are multiple +possible+ specifications for this +dep+.  Updates
  # +needed+, +specs+ and +states+ for further resolution of the +possible+
  # choices.

  def resolve_for_multiple needed, specs, states, dep, possible # :nodoc:
    # Sort them so that we try the highest versions first.
    possible = possible.sort_by do |s|
      [s.source, s.version, s.platform == Gem::Platform::RUBY ? -1 : 1]
    end

    spec, act = activation_request dep, possible

    # We may need to try all of +possible+, so we setup state to unwind back
    # to current +needed+ and +specs+ so we can try another. This is code is
    # what makes conflict resolution possible.
    states << State.new(needed.dup, specs, dep, spec, possible, [])

    @stats.record_depth states

    explain :states, states.map { |s| s.dep }

    needed = requests spec, act, needed
    specs = Gem::List.prepend specs, act

    return needed, specs
  end

  ##
  # Add the spec from the +possible+ list to +specs+ and process the spec's
  # dependencies by adding them to +needed+.

  def resolve_for_single needed, specs, dep, possible # :nodoc:
    spec, act = activation_request dep, possible

    specs = Gem::List.prepend 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

    return needed, specs
  end

  ##
  # When there are no possible specifications for +dep+ our work is done.

  def resolve_for_zero dep, platform_mismatch # :nodoc:
    @missing << dep

    unless @soft_missing
      exc = Gem::UnsatisfiableDependencyError.new dep, platform_mismatch
      exc.errors = @set.errors

      raise exc
    end
  end

  ##
  # Returns the gems in +specs+ that match the local platform.

  def select_local_platforms specs # :nodoc:
    specs.select do |spec|
      Gem::Platform.installable? spec
    end
  end

end

##
# TODO remove in RubyGems 3

Gem::DependencyResolver = Gem::Resolver # :nodoc:

require 'rubygems/resolver/activation_request'
require 'rubygems/resolver/conflict'
require 'rubygems/resolver/dependency_request'
require 'rubygems/resolver/requirement_list'
require 'rubygems/resolver/stats'

require 'rubygems/resolver/set'
require 'rubygems/resolver/api_set'
require 'rubygems/resolver/composed_set'
require 'rubygems/resolver/best_set'
require 'rubygems/resolver/current_set'
require 'rubygems/resolver/git_set'
require 'rubygems/resolver/index_set'
require 'rubygems/resolver/installer_set'
require 'rubygems/resolver/lock_set'
require 'rubygems/resolver/vendor_set'

require 'rubygems/resolver/specification'
require 'rubygems/resolver/spec_specification'
require 'rubygems/resolver/api_specification'
require 'rubygems/resolver/git_specification'
require 'rubygems/resolver/index_specification'
require 'rubygems/resolver/installed_specification'
require 'rubygems/resolver/local_specification'
require 'rubygems/resolver/lock_specification'
require 'rubygems/resolver/vendor_specification'