-
Notifications
You must be signed in to change notification settings - Fork 42
/
naive_resolver.rb
48 lines (44 loc) · 1.85 KB
/
naive_resolver.rb
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
# frozen_string_literal: true
# rubocop:disable Metrics/CyclomaticComplexity
# rubocop:disable Metrics/LineLength
# rubocop:disable Style/Semicolon
module Molinillo
class NaiveResolver
def self.resolve(index, dependencies)
activated = Molinillo::DependencyGraph.new
level = 0
dependencies.each { |d| activated.add_child_vertex(d.name, nil, [nil], d) }
activated.tag(level)
possibilities_by_level = {}
loop do
vertex = activated.find { |a| !a.requirements.empty? && a.payload.nil? }
break unless vertex
possibilities = possibilities_by_level[level] ||= index.search_for(Gem::Dependency.new(vertex.name, '>= 0.0.0-a'))
possibilities.select! do |spec|
vertex.requirements.all? { |r| r.requirement.satisfied_by?(spec.version) && (!spec.version.prerelease? || index.send(:dependency_prerelease?, r)) } &&
spec.dependencies.all? { |d| v = activated.vertex_named(d.name); !v || !v.payload || d.satisfied_by?(v.payload.version) }
end
warn "level = #{level} possibilities = #{possibilities.map(&:to_s)} requirements = #{vertex.requirements.map(&:to_s)}"
if spec = possibilities.pop
warn "trying #{spec}"
activated.set_payload(vertex.name, spec)
spec.dependencies.each do |d|
activated.add_child_vertex(d.name, nil, [spec.name], d)
end
level += 1
warn "tagging level #{level}"
activated.tag(level)
next
end
level = possibilities_by_level.reverse_each.find(proc { [-1, nil] }) { |_l, p| !p.empty? }.first
warn "going back to level #{level}"
possibilities_by_level.reject! { |l, _| l > level }
return nil if level < 0
activated.rewind_to(level)
activated.tag(level)
end
activated
end
def self.warn(*); end
end
end