binding.jl

"""
Heuristic for showing completions.  A binding is relevant when all are true:
- it isn't generated by the compiler
- if nonglobal, it's defined before the cursor
- (if global) it doesn't contain or immediately precede the cursor
"""
function is_relevant(ctx::JL.AbstractLoweringContext,
                     binding::JL.BindingInfo,
                     cursor::Int)
    (;start, stop) = JS.byte_range(JL.binding_ex(ctx, binding.id))
    !binding.is_internal &&
        !in(cursor, start:(stop+1)) &&
        (binding.kind === :global
         # || we could relax this for locals defined before the end of the
         #    largest for/while containing the cursor
         || cursor > start)
end

let lowering_module = Module()
    global function jl_lower_for_scope_resolution2(st0)
        ctx1, st1 = JL.expand_forms_1(lowering_module, remove_macrocalls(st0));
        ctx2, st2 = JL.expand_forms_2(ctx1, st1);
        ctx3, st3 = JL.resolve_scopes(ctx2, st2);
        return ctx3, st2
    end
    global function jl_lower_for_scope_resolution3(st0)
        ctx1, st1 = JL.expand_forms_1(lowering_module, remove_macrocalls(st0));
        ctx2, st2 = JL.expand_forms_2(ctx1, st1);
        ctx3, st3 = JL.resolve_scopes(ctx2, st2);
        @assert !isnothing(st3)
        return ctx3, st3
    end
end

"""
Find the list of (BindingInfo, SyntaxTree, distance::Int) to suggest as
completions given a parsed SyntaxTree and a cursor position.

JuliaLowering throws away the mapping from scopes to bindings (scopes are stored
as an ephemeral stack.)  We work around this by taking all available bindings
and filtering out any that aren't declared in a scope containing the cursor.
"""
function cursor_bindings(st0_top::JL.SyntaxTree, b_top::Int)
    st0, b = greatest_local(st0_top, b_top)
    if isnothing(st0)
        return nothing # nothing we can lower
    end
    ctx3, st2 = try
        jl_lower_for_scope_resolution2(st0)
    catch # err
        # JETLS_DEV_MODE && @warn "Error in lowering" err
        return nothing # lowering failed, e.g. because of incomplete input
    end

    # Note that ctx.bindings are only available after resolve_scopes, and
    # scope-blocks are not present in st3 after resolve_scopes.
    binfos = filter(binfo -> is_relevant(ctx3, binfo, b), ctx3.bindings.info)

    # for each binding: binfo, all syntaxtrees containing it, and the scope it belongs to
    bscopeinfos = Tuple{JL.BindingInfo, JL.SyntaxList, Union{JL.SyntaxTree, Nothing}}[]
    for binfo in binfos
        # TODO: find tree parents instead of byte parents?
        bas = byte_ancestors(st2, JS.byte_range(JL.binding_ex(ctx3, binfo.id)))
        # find the innermost hard scope containing this binding decl.  we shouldn't
        # be in multiple overlapping scopes that are not direct ancestors; that
        # should indicate a provenance failure
        i = findfirst(ba -> JS.kind(ba) in JS.KSet"scope_block lambda module toplevel", bas)
        push!(bscopeinfos, (binfo, bas, isnothing(i) ? nothing : bas[i]))
    end

    cursor_scopes = byte_ancestors(st2, b)

    # ignore scopes we aren't in
    filter!(((_, _, bs),) -> isnothing(bs) || bs._id in cursor_scopes.ids,
            bscopeinfos)

    # Now eliminate duplicates by name.
    # - Prefer any local binding belonging to a tighter scope (lower bdistance)
    # - If a static parameter and a local of the same name exist in the same
    #   scope (impossible in julia), the local is internal and should be ignored
    bdistances = map(((_, _, bs),) -> if isnothing(bs)
                         lastindex(cursor_scopes.ids) + 1
                     else
                         findfirst(cs -> bs._id === cs, cursor_scopes.ids)
                     end,
                     bscopeinfos)

    seen = Dict{String, Int}()
    for i in eachindex(bscopeinfos)
        (binfo, _, _) = bscopeinfos[i]

        prev = get(seen, binfo.name, nothing)
        if (isnothing(prev)
            || bdistances[i] < bdistances[prev]
            || binfo.kind === :static_parameter)
            seen[binfo.name] = i
        elseif JETLS_DEV_MODE
            @info "Found two bindings with the same name:" binfo bscopeinfos[prev][1]
        end
    end

    return map(values(seen)) do i
        (binfo, _, _) = bscopeinfos[i]
        # distance from the cursor
        dist = abs(b - JS.last_byte(JL.binding_ex(ctx3, binfo.id)))
        return (binfo, JL.binding_ex(ctx3, binfo.id), dist)
    end
end

"""
    select_target_binding(ctx3::JL.VariableAnalysisContext, st3::JL.SyntaxTree, offset::Int) -> target_binding::Union{Nothing,JL.SyntaxTree}

For the same purpose as [`select_target_node`](@ref), returns the `target_binding::JL.SyntaxTree`
closest to the cursor at the `offset` position.
Note that `st3::JL.SyntaxTree` has been processed by `JL.resolve_scopes` and corresponds to
`ctx3::JL.VariableAnalysisContext`.
It is guaranteed that `target_binding` satisfies `JS.kind(target_binding) === JS.K"BindingId"`.
"""
function select_target_binding(ctx3::JL.VariableAnalysisContext, st3::JL.SyntaxTree, offset::Int)
    function select(st::JL.SyntaxTree)
        JS.kind(st) === JS.K"BindingId" || return false
        binfo = JL.lookup_binding(ctx3, st)
        return !binfo.is_internal
    end
    bas = byte_ancestors(st3, offset)
    i = findfirst(select, bas)
    if isnothing(i)
        offset > 0 || return nothing
        # Support cases like `var│`, `func│(5)`
        bas = byte_ancestors(st3, offset - 1)
        i = findfirst(select, bas)
        if isnothing(i)
            return nothing
        end
    end
    return bas[i]
end

"""
    select_target_binding_definitions(st0_top::JL.SyntaxTree, offset::Int) ->
        nothing or (binding::JL.SyntaxTree, definitions::JL.SyntaxList)

Find the binding at the cursor position and return all of its definition sites.

Returns `nothing` if lowering fails, no binding is found at the cursor, or the binding
has no definitions. Otherwise returns a tuple of `(binding, definitions)` where:
- `binding` is the `JL.SyntaxTree` node representing the binding at the cursor
- `definitions` is a `JL.SyntaxList` containing all definition sites for that binding
"""
function select_target_binding_definitions(st0_top::JL.SyntaxTree, offset::Int)
    st0, b = greatest_local(st0_top, offset)
    isnothing(st0) && return nothing
    ctx3, st3 = try
        jl_lower_for_scope_resolution3(st0)
    catch
        return nothing
    end
    binding = select_target_binding(ctx3, st3, b)
    isnothing(binding) && return nothing
    binfo = JL.lookup_binding(ctx3, binding)
    definitions = lookup_binding_definitions(st3, binfo)
    isempty(definitions) && return nothing
    return binding, definitions
end

is_same_binding(x::JL.SyntaxTree, id::Int) = JS.kind(x) === JS.K"BindingId" && id == JL._binding_id(x)

"""
    lookup_binding_definitions(st3::JL.SyntaxTree, binfo::JL.BindingInfo) -> definitions::JL.SyntaxList

Find all definition sites for a given binding in the syntax tree. Returns a `JL.SyntaxList`
containing the syntax nodes where the binding may be defined.

This function traverses the syntax tree to collect `definitions` that tracks all the
assignment expressions (`=`) and function declarations where the binding may be defined.
For `:argument` bindings, `definitions` also includes the argument declaration itself.
"""
function lookup_binding_definitions(st3::JL.SyntaxTree, binfo::JL.BindingInfo)
    if binfo.kind === :argument
        sl = JL.SyntaxList(JL.syntax_graph(st3), [binfo.node_id])
    else
        sl = JL.SyntaxList(st3)
    end
    return _lookup_binding_definitions!(sl, st3, binfo.id)
end

function _lookup_binding_definitions!(sl::JL.SyntaxList, st3::JL.SyntaxTree, binding_id::Int)
    traverse(st3) do st::JL.SyntaxTree
        if JS.kind(st) === JS.K"=" && JS.numchildren(st) ≥ 2
            lhs = st[1]
            if is_same_binding(lhs, binding_id)
                push!(sl, lhs)
            end
        elseif JS.kind(st) === JS.K"function_decl" && JS.numchildren(st) ≥ 1
            func = st[1]
            if is_same_binding(func, binding_id)
                push!(sl, func)
            end
        end
    end
    return reverse!(deduplicate_syntaxlist(sl))
end