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
|
require_relative 'partial_solution'
require_relative 'term'
require_relative 'incompatibility'
require_relative 'solve_failure'
module Bundler::PubGrub
class VersionSolver
attr_reader :logger
attr_reader :source
attr_reader :solution
def initialize(source:, root: Package.root, logger: Bundler::PubGrub.logger)
@logger = logger
@source = source
# { package => [incompatibility, ...]}
@incompatibilities = Hash.new do |h, k|
h[k] = []
end
@seen_incompatibilities = {}
@solution = PartialSolution.new
add_incompatibility Incompatibility.new([
Term.new(VersionConstraint.any(root), false)
], cause: :root)
propagate(root)
end
def solved?
solution.unsatisfied.empty?
end
# Returns true if there is more work to be done, false otherwise
def work
return false if solved?
next_package = choose_package_version
propagate(next_package)
if solved?
logger.info { "Solution found after #{solution.attempted_solutions} attempts:" }
solution.decisions.each do |package, version|
next if Package.root?(package)
logger.info { "* #{package} #{version}" }
end
false
else
true
end
end
def solve
work until solved?
solution.decisions
end
alias_method :result, :solve
private
def propagate(initial_package)
changed = [initial_package]
while package = changed.shift
@incompatibilities[package].reverse_each do |incompatibility|
result = propagate_incompatibility(incompatibility)
if result == :conflict
root_cause = resolve_conflict(incompatibility)
changed.clear
changed << propagate_incompatibility(root_cause)
elsif result # should be a Package
changed << result
end
end
changed.uniq!
end
end
def propagate_incompatibility(incompatibility)
unsatisfied = nil
incompatibility.terms.each do |term|
relation = solution.relation(term)
if relation == :disjoint
return nil
elsif relation == :overlap
# If more than one term is inconclusive, we can't deduce anything
return nil if unsatisfied
unsatisfied = term
end
end
if !unsatisfied
return :conflict
end
logger.debug { "derived: #{unsatisfied.invert}" }
solution.derive(unsatisfied.invert, incompatibility)
unsatisfied.package
end
def next_package_to_try
solution.unsatisfied.min_by do |term|
package = term.package
range = term.constraint.range
matching_versions = source.versions_for(package, range)
higher_versions = source.versions_for(package, range.upper_invert)
[matching_versions.count <= 1 ? 0 : 1, higher_versions.count]
end.package
end
def choose_package_version
if solution.unsatisfied.empty?
logger.info "No packages unsatisfied. Solving complete!"
return nil
end
package = next_package_to_try
unsatisfied_term = solution.unsatisfied.find { |t| t.package == package }
version = source.versions_for(package, unsatisfied_term.constraint.range).first
logger.debug { "attempting #{package} #{version}" }
if version.nil?
add_incompatibility source.no_versions_incompatibility_for(package, unsatisfied_term)
return package
end
conflict = false
source.incompatibilities_for(package, version).each do |incompatibility|
if @seen_incompatibilities.include?(incompatibility)
logger.debug { "knew: #{incompatibility}" }
next
end
@seen_incompatibilities[incompatibility] = true
add_incompatibility incompatibility
conflict ||= incompatibility.terms.all? do |term|
term.package == package || solution.satisfies?(term)
end
end
unless conflict
logger.info { "selected #{package} #{version}" }
solution.decide(package, version)
else
logger.info { "conflict: #{conflict.inspect}" }
end
package
end
def resolve_conflict(incompatibility)
logger.info { "conflict: #{incompatibility}" }
new_incompatibility = false
while !incompatibility.failure?
most_recent_term = nil
most_recent_satisfier = nil
difference = nil
previous_level = 1
incompatibility.terms.each do |term|
satisfier = solution.satisfier(term)
if most_recent_satisfier.nil?
most_recent_term = term
most_recent_satisfier = satisfier
elsif most_recent_satisfier.index < satisfier.index
previous_level = [previous_level, most_recent_satisfier.decision_level].max
most_recent_term = term
most_recent_satisfier = satisfier
difference = nil
else
previous_level = [previous_level, satisfier.decision_level].max
end
if most_recent_term == term
difference = most_recent_satisfier.term.difference(most_recent_term)
if difference.empty?
difference = nil
else
difference_satisfier = solution.satisfier(difference.inverse)
previous_level = [previous_level, difference_satisfier.decision_level].max
end
end
end
if previous_level < most_recent_satisfier.decision_level ||
most_recent_satisfier.decision?
logger.info { "backtracking to #{previous_level}" }
solution.backtrack(previous_level)
if new_incompatibility
add_incompatibility(incompatibility)
end
return incompatibility
end
new_terms = []
new_terms += incompatibility.terms - [most_recent_term]
new_terms += most_recent_satisfier.cause.terms.reject { |term|
term.package == most_recent_satisfier.term.package
}
if difference
new_terms << difference.invert
end
incompatibility = Incompatibility.new(new_terms, cause: Incompatibility::ConflictCause.new(incompatibility, most_recent_satisfier.cause))
new_incompatibility = true
partially = difference ? " partially" : ""
logger.info { "! #{most_recent_term} is#{partially} satisfied by #{most_recent_satisfier.term}" }
logger.info { "! which is caused by #{most_recent_satisfier.cause}" }
logger.info { "! thus #{incompatibility}" }
end
raise SolveFailure.new(incompatibility)
end
def add_incompatibility(incompatibility)
logger.debug { "fact: #{incompatibility}" }
incompatibility.terms.each do |term|
package = term.package
@incompatibilities[package] << incompatibility
end
end
end
end
|