# This file is a part of Julia. License is MIT: https://julialang.org/license

module Types

export VersionInterval, VersionSet, Requires, Available, Fixed, merge_requires!, satisfies,
       ResolveBacktraceItem, ResolveBacktrace
import Base: show, isempty, in, intersect, union!, union, ==, hash, copy, deepcopy_internal, push!

struct VersionInterval
    lower::VersionNumber
    upper::VersionNumber
end
VersionInterval(lower::VersionNumber) = VersionInterval(lower,typemax(VersionNumber))
VersionInterval() = VersionInterval(typemin(VersionNumber))

show(io::IO, i::VersionInterval) = print(io, "[$(i.lower),$(i.upper))")
isempty(i::VersionInterval) = i.upper <= i.lower
in(v::VersionNumber, i::VersionInterval) = i.lower <= v < i.upper
intersect(a::VersionInterval, b::VersionInterval) = VersionInterval(max(a.lower,b.lower), min(a.upper,b.upper))
==(a::VersionInterval, b::VersionInterval) = a.lower == b.lower && a.upper == b.upper
hash(i::VersionInterval, h::UInt) = hash((i.lower, i.upper), h + (0x0f870a92db508386 % UInt))

function normalize!(ivals::Vector{VersionInterval})
    # VersionSet internal normalization:
    # removes empty intervals and fuses intervals without gaps
    # e.g.:
    #     [0.0.0,1.0.0) ∪ [1.0.0,1.5.0) ∪ [1.6.0,1.6.0) ∪ [2.0.0,∞)
    # becomes:
    #     [0.0.0,1.5.0) ∪ [2.0.0,∞)
    # (still assumes that lower bounds are sorted, and intervals do
    # not overlap)
    l = length(ivals)
    l == 0 && return ivals

    lo, up, k0 = ivals[1].lower, ivals[1].upper, 1
    fusing = false
    for k = 2:l
        lo1, up1 = ivals[k].lower, ivals[k].upper
        if lo1 == up
            up = up1
            fusing = true
            continue
        end
        if lo < up
            # The only purpose of the "fusing" check is to avoid
            # extra allocations
            ivals[k0] = fusing ? VersionInterval(lo, up) : ivals[k-1]
            k0 += 1
        end
        fusing = false
        lo, up = lo1, up1
    end
    if lo < up
        ivals[k0] = fusing ? VersionInterval(lo, up) : ivals[l]
        k0 += 1
    end
    resize!(ivals, k0 - 1)
    return ivals
end

struct VersionSet
    intervals::Vector{VersionInterval}
    VersionSet(intervals::Vector{VersionInterval}) = new(normalize!(intervals))
    # copy is defined inside the struct block to call `new` directly
    # without going through `normalize!`
    Base.copy(vset::VersionSet) = new(copy(vset.intervals))
end
function VersionSet(versions::Vector{VersionNumber})
    intervals = VersionInterval[]
    if isempty(versions)
        push!(intervals, VersionInterval())
    else
        isodd(length(versions)) && push!(versions, typemax(VersionNumber))
        while !isempty(versions)
            push!(intervals, VersionInterval(popfirst!(versions), popfirst!(versions)))
        end
    end
    VersionSet(intervals)
end
VersionSet(versions::VersionNumber...) = VersionSet(VersionNumber[versions...])

const empty_versionset = VersionSet(VersionInterval[])

# Windows console doesn't like Unicode
const _empty_symbol = @static Sys.iswindows() ? "empty" : "∅"
const _union_symbol = @static Sys.iswindows() ? " or " : " ∪ "
show(io::IO, s::VersionSet) = isempty(s) ? print(io, _empty_symbol) :
                                           join(io, s.intervals, _union_symbol)
isempty(s::VersionSet) = all(isempty, s.intervals)
in(v::VersionNumber, s::VersionSet) = any(i->in(v,i), s.intervals)
function intersect(A::VersionSet, B::VersionSet)
    (isempty(A) || isempty(B)) && return copy(empty_versionset)
    ivals = [intersect(a,b) for a in A.intervals for b in B.intervals]
    sort!(ivals, by=i->i.lower)
    VersionSet(ivals)
end

union(A::VersionSet, B::VersionSet) = union!(copy(A), B)
function union!(A::VersionSet, B::VersionSet)
    A == B && return A
    ivals = A.intervals
    for intB in B.intervals
        lB, uB = intB.lower, intB.upper
        k0 = findfirst(i->(i.upper > lB), ivals)
        if k0 === nothing
            push!(ivals, intB)
            continue
        end
        lB = min(lB, ivals[k0].lower)
        for k1 = k0:length(ivals)
            intA = ivals[k1]
            if uB < intA.lower
                splice!(ivals, k0:(k1-1), (VersionInterval(lB, uB),))
                break
            elseif uB ∈ intA || k1 == length(ivals)
                splice!(ivals, k0:k1, (VersionInterval(lB, max(uB, intA.upper)),))
                break
            end
        end
    end
    normalize!(ivals)
    return A
end

==(A::VersionSet, B::VersionSet) = A.intervals == B.intervals
hash(s::VersionSet, h::UInt) = hash(s.intervals, h + (0x2fd2ca6efa023f44 % UInt))
deepcopy_internal(vs::VersionSet, ::IdDict) = copy(vs)

const Requires = Dict{String,VersionSet}

function merge_requires!(A::Requires, B::Requires)
    for (pkg,vers) in B
        A[pkg] = haskey(A,pkg) ? intersect(A[pkg],vers) : vers
    end
    return A
end

satisfies(pkg::AbstractString, ver::VersionNumber, reqs::Requires) =
    !haskey(reqs, pkg) || in(ver, reqs[pkg])

struct Available
    sha1::String
    requires::Requires
end

==(a::Available, b::Available) = a.sha1 == b.sha1 && a.requires == b.requires
hash(a::Available, h::UInt) = hash((a.sha1, a.requires), h + (0xbc8ae0de9d11d972 % UInt))
copy(a::Available) = Available(a.sha1, copy(a.requires))

show(io::IO, a::Available) = isempty(a.requires) ?
    print(io, "Available(", repr(a.sha1), ")") :
    print(io, "Available(", repr(a.sha1), ",", a.requires, ")")

struct Fixed
    version::VersionNumber
    requires::Requires
end
Fixed(v::VersionNumber) = Fixed(v,Requires())

==(a::Fixed, b::Fixed) = a.version == b.version && a.requires == b.requires
hash(f::Fixed, h::UInt) = hash((f.version, f.requires), h + (0x68628b809fd417ca % UInt))

show(io::IO, f::Fixed) = isempty(f.requires) ?
    print(io, "Fixed(", repr(f.version), ")") :
    print(io, "Fixed(", repr(f.version), ",", f.requires, ")")

# TODO: Available & Fixed are almost the same – merge them?
# Free could include the same information too, it just isn't
# required by anything that processes these things.


const VersionReq = Union{VersionNumber,VersionSet}
const WhyReq = Tuple{VersionReq,Any}

# This is used to keep track of dependency relations when propagating
# requirements, so as to emit useful information in case of unsatisfiable
# conditions.
# The `versionreq` field keeps track of the remaining allowed versions,
# intersecting all requirements.
# The `why` field is a Vector which keeps track of the requirements. Each
# entry is a Tuple of two elements:
# 1) the first element is the version requirement (can be a single VersionNumber
#    or a VersionSet).
# 2) the second element can be either :fixed (for requirements induced by
#    fixed packages), :required (for requirements induced by explicitly
#    required packages), or a Pair p=>backtrace_item (for requirements induced
#    indirectly, where `p` is the package name and `backtrace_item` is
#    another ResolveBacktraceItem.
mutable struct ResolveBacktraceItem
    versionreq::VersionReq
    why::Vector{WhyReq}
    ResolveBacktraceItem() = new(VersionSet(), WhyReq[])
    ResolveBacktraceItem(reason, versionreq::VersionReq) = new(versionreq, WhyReq[(versionreq,reason)])
end

function push!(ritem::ResolveBacktraceItem, reason, versionset::VersionSet)
    if isa(ritem.versionreq, VersionSet)
        ritem.versionreq = ritem.versionreq ∩ versionset
    elseif ritem.versionreq ∉ versionset
        ritem.versionreq = copy(empty_versionset)
    end
    push!(ritem.why, (versionset,reason))
end

function push!(ritem::ResolveBacktraceItem, reason, version::VersionNumber)
    if isa(ritem.versionreq, VersionSet)
        if version ∈ ritem.versionreq
            ritem.versionreq = version
        else
            ritem.versionreq = copy(empty_versionset)
        end
    elseif ritem.versionreq ≠ version
        ritem.versionreq = copy(empty_versionset)
    end
    push!(ritem.why, (version,reason))
end


show(io::IO, ritem::ResolveBacktraceItem) = _show(io, ritem, "", Set{ResolveBacktraceItem}([ritem]))

function _show(io::IO, ritem::ResolveBacktraceItem, indent::String, seen::Set{ResolveBacktraceItem})
    l = length(ritem.why)
    for (i,(vs,w)) in enumerate(ritem.why)
        print(io, indent, (i==l ? '└' : '├'), '─')
        if w ≡ :fixed
            @assert isa(vs, VersionNumber)
            println(io, "version $vs set by fixed requirement (package is checked out, dirty or pinned)")
        elseif w ≡ :required
            @assert isa(vs, VersionSet)
            println(io, "version range $vs set by an explicit requirement")
        else
            @assert isa(w, Pair{<:AbstractString,ResolveBacktraceItem})
            if isa(vs, VersionNumber)
                print(io, "version $vs ")
            else
                print(io, "version range $vs ")
            end
            print(io, "required by package $(w[1]), ")
            if isa(w[2].versionreq, VersionSet)
                println(io, "whose allowed version range is $(w[2].versionreq):")
            else
                println(io, "whose only allowed version is $(w[2].versionreq):")
            end
            if w[2] ∈ seen
                println(io, (i==l ? "  " : "│ ") * indent, "└─[see above for $(w[1]) backtrace]")
                continue
            end
            push!(seen, w[2])
            _show(io, w[2], (i==l ? "  " : "│ ") * indent, seen)
        end
    end
end

const ResolveBacktrace = Dict{AbstractString,ResolveBacktraceItem}

end # module