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
|
require 'rubygems'
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::DependencyResolver
##
# Contains all the conflicts encountered while doing resolution
attr_reader :conflicts
attr_accessor :development
attr_reader :missing
##
# When a missing dependency, don't stop. Just go on and record what was
# missing.
attr_accessor :soft_missing
def self.compose_sets *sets
Gem::DependencyResolver::ComposedSet.new(*sets)
end
##
# Provide a DependencyResolver that queries only against the already
# installed gems.
def self.for_current_gems needed
new needed, Gem::DependencyResolver::CurrentSet.new
end
##
# 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.
def initialize needed, set = nil
@set = set || Gem::DependencyResolver::IndexSet.new
@needed = needed
@conflicts = nil
@development = false
@missing = []
@soft_missing = false
end
def requests s, act, reqs=nil
s.dependencies.reverse_each do |d|
next if d.type == :development and not @development
reqs = Gem::List.new Gem::DependencyResolver::DependencyRequest.new(d, act), reqs
end
@set.prefetch reqs
reqs
end
##
# Proceed with resolution! Returns an array of ActivationRequest objects.
def resolve
@conflicts = []
needed = nil
@needed.reverse_each do |n|
request = Gem::DependencyResolver::DependencyRequest.new n, nil
needed = Gem::List.new request, needed
end
res = resolve_for needed, nil
raise Gem::DependencyResolutionError, res if
res.kind_of? Gem::DependencyResolver::DependencyConflict
res.to_a
end
##
# Finds the State in +states+ that matches the +conflict+ so that we can try
# other possible sets.
def find_conflict_state conflict, states # :nodoc:
until states.empty? do
if conflict.for_spec? states.last.spec
state = states.last
state.conflicts << [state.spec, conflict]
return state
else
states.pop
end
end
nil
end
##
# Extracts the specifications that may be able to fulfill +dependency+
def find_possible dependency # :nodoc:
possible = @set.find_all dependency
select_local_platforms possible
end
def handle_conflict(dep, 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 =
Gem::DependencyResolver::DependencyConflict.new dep, existing
else
depreq = existing.request.requester.request
conflict =
Gem::DependencyResolver::DependencyConflict.new depreq, existing, dep
end
@conflicts << 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 DepedencyRequest 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, DependencyConflict] hit tried to
# activate the state.
#
State = Struct.new(:needed, :specs, :dep, :spec, :possibles, :conflicts)
##
# 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
# The State objects that are used to attempt the activation tree.
states = []
while needed
dep = needed.value
needed = needed.tail
# 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
state = find_conflict_state conflict, states
return conflict unless state
needed, specs = resolve_for_conflict needed, specs, state
next
end
possible = find_possible dep
case possible.size
when 0
resolve_for_zero dep
when 1
needed, specs =
resolve_for_single needed, specs, dep, possible
else
needed, specs =
resolve_for_multiple needed, specs, states, dep, possible
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?
spec = state.possibles.pop
# Retry resolution with this spec and add it's dependencies
act = Gem::DependencyResolver::ActivationRequest.new spec, state.dep
needed = requests spec, act, state.needed
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
# 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.
spec = possible.pop
# 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.
act = Gem::DependencyResolver::ActivationRequest.new spec, dep
states << State.new(needed, specs, dep, spec, possible, [])
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 = possible.first
act = Gem::DependencyResolver::ActivationRequest.new spec, dep, false
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 # :nodoc:
@missing << dep
unless @soft_missing
raise Gem::UnsatisfiableDependencyError, dep
end
end
##
# Returns the gems in +specs+ that match the local platform.
def select_local_platforms specs # :nodoc:
specs.select do |spec|
Gem::Platform.match spec.platform
end
end
end
require 'rubygems/dependency_resolver/api_set'
require 'rubygems/dependency_resolver/api_specification'
require 'rubygems/dependency_resolver/activation_request'
require 'rubygems/dependency_resolver/composed_set'
require 'rubygems/dependency_resolver/current_set'
require 'rubygems/dependency_resolver/dependency_conflict'
require 'rubygems/dependency_resolver/dependency_request'
require 'rubygems/dependency_resolver/index_set'
require 'rubygems/dependency_resolver/index_specification'
require 'rubygems/dependency_resolver/installed_specification'
require 'rubygems/dependency_resolver/installer_set'
|