Class: Gem::Resolver

Inherits:
Object
  • Object
show all
Defined in:
lib/rubygems/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, BestSet, ComposedSet, Conflict, CurrentSet, DependencyRequest, GitSet, GitSpecification, IndexSet, IndexSpecification, InstalledSpecification, InstallerSet, LocalSpecification, LockSet, LockSpecification, RequirementList, Set, SpecSpecification, Specification, State, Stats, VendorSet, VendorSpecification

Constant Summary collapse

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

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

TODO: Remove in RubyGems 3

Gem::Resolver::Conflict

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(needed, set = nil) ⇒ Resolver

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.



109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/rubygems/resolver.rb', line 109

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

Instance Attribute Details

#conflicts ⇒ Object (readonly)

Contains all the conflicts encountered while doing resolution



28
29
30
 
# File 'lib/rubygems/resolver.rb', line 28

def conflicts
  @conflicts
end

#development ⇒ Object

Set to true if all development dependencies should be considered.



33
34
35
 
# File 'lib/rubygems/resolver.rb', line 33

def development
  @development
end

#development_shallow ⇒ Object

Set to true if immediate development dependencies should be considered.



38
39
40
 
# File 'lib/rubygems/resolver.rb', line 38

def development_shallow
  @development_shallow
end

#ignore_dependencies ⇒ Object

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



43
44
45
 
# File 'lib/rubygems/resolver.rb', line 43

def ignore_dependencies
  @ignore_dependencies
end

#missing ⇒ Object (readonly)

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



48
49
50
 
# File 'lib/rubygems/resolver.rb', line 48

def missing
  @missing
end

#skip_gems ⇒ Object

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



56
57
58
 
# File 'lib/rubygems/resolver.rb', line 56

def skip_gems
  @skip_gems
end

#soft_missing ⇒ Object

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



62
63
64
 
# File 'lib/rubygems/resolver.rb', line 62

def soft_missing
  @soft_missing
end

#stats ⇒ Object (readonly)

Returns the value of attribute stats.



50
51
52
 
# File 'lib/rubygems/resolver.rb', line 50

def stats
  @stats
end

Class Method Details

.compose_sets(*sets) ⇒ Object

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.



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/rubygems/resolver.rb', line 69

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

.for_current_gems(needed) ⇒ Object

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



97
98
99
 
# File 'lib/rubygems/resolver.rb', line 97

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

Instance Method Details

#activation_request(dep, possible) ⇒ Object

Creates an ActivationRequest for the given dep and the last possible specification.

Returns the Specification and the ActivationRequest



144
145
146
147
148
149
150
151
152
153
154
 
# File 'lib/rubygems/resolver.rb', line 144

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

#explain(stage, *data) ⇒ Object

:nodoc:



123
124
125
126
127
128
 
# File 'lib/rubygems/resolver.rb', line 123

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

#explain_list(stage) ⇒ Object

:nodoc:



130
131
132
133
134
135
136
 
# File 'lib/rubygems/resolver.rb', line 130

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

#find_possible(dependency) ⇒ Object

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



208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/rubygems/resolver.rb', line 208

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

#handle_conflict(dep, existing) ⇒ Object

:nodoc:



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
 
# File 'lib/rubygems/resolver.rb', line 224

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

#requests(s, act, reqs = nil) ⇒ Object

:nodoc:



156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/rubygems/resolver.rb', line 156

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

#resolve ⇒ Object

Proceed with resolution! Returns an array of ActivationRequest objects.

Raises:



182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
# File 'lib/rubygems/resolver.rb', line 182

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

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



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
 
# File 'lib/rubygems/resolver.rb', line 294

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

#resolve_for_conflict(needed, specs, state) ⇒ Object

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



367
368
369
370
371
372
373
374
375
376
377
378
379
380
 
# File 'lib/rubygems/resolver.rb', line 367

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

#resolve_for_multiple(needed, specs, states, dep, possible) ⇒ Object

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



387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
 
# File 'lib/rubygems/resolver.rb', line 387

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

#resolve_for_single(needed, specs, dep, possible) ⇒ Object

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



414
415
416
417
418
419
420
421
422
423
424
425
426
427
 
# File 'lib/rubygems/resolver.rb', line 414

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

#resolve_for_zero(dep, platform_mismatch) ⇒ Object

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



432
433
434
435
436
437
438
439
440
441
 
# File 'lib/rubygems/resolver.rb', line 432

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

#select_local_platforms(specs) ⇒ Object

Returns the gems in specs that match the local platform.



446
447
448
449
450
 
# File 'lib/rubygems/resolver.rb', line 446

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