-
-
Notifications
You must be signed in to change notification settings - Fork 5.5k
/
resolve.jl
142 lines (116 loc) · 4.16 KB
/
resolve.jl
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
# This file is a part of Julia. License is MIT: https://julialang.org/license
module Resolve
include("resolve/versionweight.jl")
include("resolve/interface.jl")
include("resolve/maxsum.jl")
using ..Types, ..Query, .PkgToMaxSumInterface, .MaxSum
import ...Pkg.PkgError
export resolve, sanity_check
# Use the max-sum algorithm to resolve packages dependencies
function resolve(reqs::Requires, deps::Dict{String,Dict{VersionNumber,Available}})
# init interface structures
interface = Interface(reqs, deps)
# attempt trivial solution first
ok, sol = greedysolver(interface)
if !ok
# trivial solution failed, use maxsum solver
graph = Graph(interface)
msgs = Messages(interface, graph)
try
sol = maxsum(graph, msgs)
catch err
if isa(err, UnsatError)
p = interface.pkgs[err.info]
msg = "unsatisfiable package requirements detected: " *
"no feasible version could be found for package: $p"
if msgs.num_nondecimated != graph.np
msg *= "\n (you may try increasing the value of the" *
"\n JULIA_PKGRESOLVE_ACCURACY environment variable)"
end
throw(PkgError(msg))
end
rethrow(err)
end
# verify solution (debug code) and enforce its optimality
@assert verify_solution(sol, interface)
enforce_optimality!(sol, interface)
end
# return the solution as a Dict mapping package_name => sha1
return compute_output_dict(sol, interface)
end
# Scan dependencies for (explicit or implicit) contradictions
function sanity_check(deps::Dict{String,Dict{VersionNumber,Available}},
pkgs::Set{String} = Set{String}())
isempty(pkgs) || (deps = Query.undirected_dependencies_subset(deps, pkgs))
deps, eq_classes = Query.prune_versions(deps)
ndeps = Dict{String,Dict{VersionNumber,Int}}()
for (p,depsp) in deps
ndeps[p] = ndepsp = Dict{VersionNumber,Int}()
for (vn,a) in depsp
ndepsp[vn] = length(a.requires)
end
end
vers = Array(Tuple{String,VersionNumber,VersionNumber}, 0)
for (p,d) in deps, vn in keys(d)
lvns = VersionNumber[filter(vn2->(vn2>vn), keys(d))...]
nvn = isempty(lvns) ? typemax(VersionNumber) : minimum(lvns)
push!(vers, (p,vn,nvn))
end
sort!(vers, by=pvn->(-ndeps[pvn[1]][pvn[2]]))
nv = length(vers)
svdict = (Tuple{String,VersionNumber}=>Int)[ vers[i][1:2]=>i for i = 1:nv ]
checked = falses(nv)
problematic = Array(Tuple{String,VersionNumber,String},0)
i = 1
psl = 0
for (p,vn,nvn) in vers
if ndeps[p][vn] == 0
break
end
if checked[i]
i += 1
continue
end
sub_reqs = Dict{String,VersionSet}(p=>VersionSet([vn, nvn]))
sub_deps = Query.filter_dependencies(sub_reqs, deps)
interface = Interface(sub_reqs, sub_deps)
red_pkgs = interface.pkgs
red_np = interface.np
red_spp = interface.spp
red_pvers = interface.pvers
ok, sol = greedysolver(interface)
if !ok
try
graph = Graph(interface)
msgs = Messages(interface, graph)
sol = maxsum(graph, msgs)
ok = verify_solution(sol, interface)
@assert ok
catch err
isa(err, UnsatError) || rethrow(err)
pp = red_pkgs[err.info]
for vneq in eq_classes[p][vn]
push!(problematic, (p, vneq, pp))
end
end
end
if ok
let
p0 = interface.pdict[p]
svn = red_pvers[p0][sol[p0]]
@assert svn == vn
end
for p0 = 1:red_np
s0 = sol[p0]
if s0 != red_spp[p0]
j = svdict[(red_pkgs[p0], red_pvers[p0][s0])]
checked[j] = true
end
end
checked[i] = true
end
i += 1
end
return sort!(problematic)
end
end # module