Revision faf9fe75223dfef2f86958c1ced84be369f4738e authored by Tony Kelman on 17 September 2016, 16:31:22 UTC, committed by Tony Kelman on 17 September 2016, 16:35:31 UTC
* Attempt to fix osx travis We're now getting > Error: You must `brew link autoconf` before staticfloat/julia/julia can be installed Probably because Homebrew officially started supporting 10.12 Sierra, and that broke something. Try to use the 10.10 Travis OSX image instead of the default 10.9 (https://docs.travis-ci.com/user/osx-ci-environment/) * explicitly install cmake on osx travis (cherry picked from commit 45bc17d41b40f271dd5ebb2357e7f3564f969007)
1 parent ea2aaf7
resolve.jl
module Resolve
include("resolve/versionweight.jl")
include("resolve/interface.jl")
include("resolve/maxsum.jl")
using ..Types, ..Query, .PkgToMaxSumInterface, .MaxSum
export resolve, sanity_check
# Use the max-sum algorithm to resolve packages dependencies
function resolve(reqs::Requires, deps::Dict{ByteString,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
error(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{ByteString,Dict{VersionNumber,Available}}, pkgs::Set{ByteString} = Set{ByteString}())
isempty(pkgs) || (deps = Query.undirected_dependencies_subset(deps, pkgs))
deps, eq_classes = Query.prune_versions(deps)
ndeps = (ByteString=>Dict{VersionNumber,Int})[]
for (p,depsp) in deps
ndeps[p] = ndepsp = (VersionNumber=>Int)[]
for (vn,a) in depsp
ndepsp[vn] = length(a.requires)
end
end
vers = Array((ByteString,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 = ((ByteString,VersionNumber)=>Int)[ vers[i][1:2]=>i for i = 1:nv ]
checked = falses(nv)
problematic = Array((ByteString,VersionNumber,ByteString),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 = (ByteString=>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
Computing file changes ...