JuliaLowering/src/scope_analysis.jl - master - githubmirror/julia

JuliaLowering/src/scope_analysis.jl
969 строк39 KB
Keno Fischer
[JuliaLowering] Fix two labeled-break bugs (#62323)
04 авг 2026, 10:59
04 авг 2026, 10:597c5a4e3
# Lowering pass 3: scope and variable analysis

"""
Key to use when transforming names into bindings
"""
struct NameKey
    name::String
    layer::ScopeLayer
end

function NameKey(ex::SyntaxTree)
    @jl_assert kind(ex) === K"Identifier" ex
    NameKey(syntax_name(ex), (ex.context::SyntaxContext).layer)
end

struct ScopeInfo
    # index into ctx.scopes
    id::ScopeId
    # 0 if top-level thunk
    parent_id::ScopeId
    # Own ID if lambda, else some parent ID
    lambda_id::ScopeId
    # Tree introducing this scope
    node_id::SyntaxTree
    # True in the top-level scope, and any neutral scope nested within it not
    # protected by a hard scope.  Becomes soft if `ctx.enable_soft_scopes`.
    is_permeable::Bool
    # True for K"method_defs" and its non-lambda children where all new locals
    # should participate in standard scope resolution, but then be associated
    # with the top-level thunk by the end of this pass.
    is_lifted::Bool
    binding_assignments::Dict{IdTag, SyntaxTree}
    assignments::Dict{NameKey, SyntaxTree}
    # Map from variable names to binding IDs for resolution.  Includes all
    # locals, args, sparams, and explicit globals belonging to this scope.
    # Variables captured from an outer scope are not included.  The top-level
    # scope also contains all globals for resolution to fall back to.
    vars::Dict{NameKey,IdTag}
    # See `LambdaBindings`. Nothing if not a lambda scope.  This is the final
    # collecting place for locals going in to closure conversion.
    locals_capt::Union{Nothing, Dict{IdTag,Bool}}
end

function ScopeInfo(ctx, parent_id, ex::SyntaxTree)
    id = length(ctx.scopes) + 1
    k = kind(ex)
    if parent_id == 0
        @jl_assert k in KSet"lambda toplevel_lambda generated_lambda" ex
        lambda_id = id
        is_permeable = k == K"toplevel_lambda"
        is_lifted = false
        lambda_bindings = Dict{IdTag, Bool}()
    else
        @jl_assert k in KSet"lambda method_defs scope_block" ex
        parent = ctx.scopes[parent_id]
        lambda_id = k === K"lambda" ? id : parent.lambda_id
        is_permeable = (k === K"scope_block" &&
            kind(ex[1]) === K"neutral_scope" &&
            parent_id != 0 && parent.is_permeable)
        is_lifted = k === K"method_defs" ||
            (k !== K"lambda" && parent.is_lifted)
        lambda_bindings = k === K"lambda" ? Dict{IdTag, Bool}() : nothing
    end
    s = ScopeInfo(
        id, parent_id, lambda_id, ex, is_permeable, is_lifted,
        Dict{IdTag, SyntaxTree}(), Dict{NameKey, SyntaxTree}(),
        Dict{NameKey,IdTag}(), lambda_bindings)
    push!(ctx.scopes, s)
    return s
end

mutable struct ScopeResolutionContext <: AbstractLoweringContext
    const layer::ScopeLayer
    const bindings::Bindings
    # Purely for display and deterministic ordering of scope layers
    const layer_ids::Dict{ScopeLayer, Int}
    # Every lexical scope, indexed by ScopeId
    const scopes::Vector{ScopeInfo}
    # Current stack of scopes to look for names in, innermost scope last
    const scope_stack::Vector{ScopeId}
    # Usually, globals in the top scope are ignored.  This is a subset that may
    # be assigned to without the `global` keyword in soft scopes due to being
    # assigned to at top level, or passing the defined-and-owned-global check.
    const soft_assignable_globals::Set{NameKey}
    # Every static parameter corresponds to some typevar (top-level local)
    # required to create this method
    const sp_typevars::Dict{IdTag, IdTag}
    # Typevars referenced in each typevar's bounds.  Closures capturing a static
    # parameter must also capture the sparams of its typevar's dependencies
    const tv_deps::Dict{IdTag, Vector{IdTag}}
    const enable_soft_scopes::Bool
    const world::UInt
end

function contains_softscope_marker(ex)
    kind(ex) == K"softscope"  && return true
    needs_resolution(ex) && for c in children(ex)
        contains_softscope_marker(c) && return true
    end
    return false
end

top_scope(ctx) = ctx.scopes[1]
is_top_scope(scope::ScopeInfo) = scope.parent_id === 0
enclosing_lambda(ctx, scope::ScopeInfo) = ctx.scopes[scope.lambda_id]
parent(ctx, scope::ScopeInfo) = is_top_scope(scope) ? nothing :
    ctx.scopes[scope.parent_id]

_var_str(v) = v === :local ? "local variable" :
    v === :global ? "global variable" :
    v === :argument ? "argument" :
    v === :destructured_arg ? "destructured argument" :
    v === :typevar ? "typevar" :
    v === :static_parameter ? "static parameter" : "unknown"

# Declare `ex` in `scope`, unless a binding already exists with the same name in
# scope, or anywhere.  Throw an error if a name conflict occurs.  The rules
# for conflict: declaring a local (or global) twice with the same name is a
# no-op, but doing so with an argument or static parameter is an error.  A
# variable usually can't be two things in one scope, but flisp has quirks.
function explicit_declare_in_scope!(ctx, scope::ScopeInfo, ex, new_k::Symbol)
    if kind(ex) === K"BindingId"
        bid = syntax_id(ex)
        b = get_binding(ctx, bid)
        @jl_assert b.kind === new_k ex
        @jl_assert b.lambda_id == 0 (ex, "cannot declare a BindingId in multiple scopes")
        add_lambda_local!(ctx, scope, b)
        return bid
    elseif kind(ex) === K"Placeholder"
        return nothing
    end
    bid = get(scope.vars, NameKey(ex), nothing)
    old_k = isnothing(bid) ? nothing : get_binding(ctx, bid).kind
    if isnothing(old_k)
        if new_k === :argument
            declare_in_scope!(ctx, scope, ex, :argument;
                              is_nospecialize=getmeta(ex, :nospecialize, false))
        else
            real_k = new_k === :destructured_arg ? :local : new_k
            declare_in_scope!(ctx, scope, ex, real_k)
        end
    elseif old_k === new_k
        (new_k === :global || new_k === :local) && return bid
        throw(LoweringError(ex, "function $(_var_str(new_k)) name not unique"))
    # See note in test/scopes.jl: "globals may overlap args or sparams"
    # elseif new_k === :global && old_k in (:argument, :static_parameter)
    #     declare_in_scope!(ctx, scope, ex, :global)
    else
        throw(LoweringError(ex, """
        $(_var_str(new_k)) name `$(NameKey(ex).name)` conflicts with an \
        existing $(_var_str(old_k)) from the same scope"""))
    end
end

# globals are added to both `scope` and the top scope (mainly so we can get the
# same binding for many unrelated global references).
function declare_in_scope!(ctx, scope::ScopeInfo, ex, bk::Symbol;
                           is_nospecialize::Bool=false,
                           is_ambiguous_local::Bool=false)
    nk = NameKey(ex)
    if bk === :global
        mod = syntax_module(ex)
        declaration_scope = top_scope(ctx)
    else
        declaration_scope = scope
        mod = ex.mod isa Module ?
            throw(LoweringError(ex, "cannot use GlobalRef as local identifier")) : nothing
    end
    is_internal = (ex.context::SyntaxContext).internal ||
        getmeta(ex, :is_internal, false)::Bool
    b = _new_binding(ctx.bindings, ex, nk.name, bk;
                     mod, is_internal, is_nospecialize, is_ambiguous_local)
    declaration_scope.vars[nk] = b.id
    scope.vars[nk] = b.id
    add_lambda_local!(ctx, scope, b)
    return b.id
end

function add_lambda_local!(ctx, scope::ScopeInfo, b)
    if b.kind === :global || b.is_ssa
        return
    end
    lam = scope.is_lifted ? top_scope(ctx) : enclosing_lambda(ctx, scope)
    b.kind == :typevar && @jl_assert scope.is_lifted binding_ex(ctx, b)
    @jl_assert !haskey(lam.locals_capt, b.id) (
        binding_ex(ctx, b), "adding lambda local twice")
    lam.locals_capt[b.id] = false
    b.lambda_id = lam.id
    nothing
end

function ensure_captured!(ctx, scope::ScopeInfo, b)
    if b.kind === :global || b.kind === :typevar || b.is_ssa
        return
    end
    lam = enclosing_lambda(ctx, scope)
    if !haskey(lam.locals_capt, b.id)
        # assert is opaque closure, or b not static_parameter
        b.is_captured = true
        lam.locals_capt[b.id] = true
        s2 = parent(ctx, lam)
        @jl_assert !isnothing(s2) (
            binding_ex(ctx, b),
            "tried to capture local before declaration in any parent")
        ensure_captured!(ctx, s2, b)
    end
    nothing
end

function needs_resolution(ex)
    kind(ex) === K"Identifier" ||
        !is_leaf(ex) && !is_quoted(ex) && !(kind(ex) in KSet"toplevel module")
end

function resolve_name(ctx, ex; exclude_toplevel_globals=false)
    # TODO: probably want to cache these lookups
    nk = NameKey(ex)
    for sid in Iterators.reverse(ctx.scope_stack)
        bid = get(ctx.scopes[sid].vars, nk, nothing)
        isnothing(bid) && continue
        b = get_binding(ctx, bid)
        if b.kind === :typevar
            # only visible to lifted scopes in the same lambda (we should only
            # hit this when we filter sparams with `used_typevars`)
            s0 = ctx.scopes[ctx.scope_stack[end]]
            s0.is_lifted && ctx.scopes[sid].lambda_id == s0.lambda_id || continue
        end
        if !exclude_toplevel_globals || sid !== top_scope(ctx).id || b.kind !== :global
            return b
        end
    end
    return nothing
end

# Collect typevar bindings referenced in `ex` (a resolved typevar bound)
function _typevar_refs!(out, ctx, ex)
    k = kind(ex)
    if k == K"BindingId"
        b = get_binding(ctx, ex)
        b.kind === :typevar && !(b.id in out) && push!(out, b.id)
    elseif !is_leaf(ex) && needs_resolution(ex)
        foreach(e->_typevar_refs!(out, ctx, e), children(ex))
    end
end

function _record_layer!(ctx, ex)
    ex.context isa SyntaxContext || return
    sl = ex.context.layer
    get!(ctx.layer_ids, sl, length(ctx.layer_ids)+1)
end

function _find_scope_decls!(ctx, scope, ex)
    k = kind(ex)
    _record_layer!(ctx, ex)
    if k === K"local" && kind(ex[1]) === K"Identifier"
        var_k = getmeta(ex, :is_destructured_arg, false) ?
            :destructured_arg : :local
        explicit_declare_in_scope!(ctx, scope, ex[1], var_k)
    elseif k === K"global" && kind(ex[1]) === K"Identifier"
        explicit_declare_in_scope!(ctx, scope, ex[1], :global)
    elseif k === K"function_decl"
        k1 = kind(ex[1])
        _record_layer!(ctx, ex[1])
        if k1 === K"BindingId"
            b = get_binding(ctx, ex[1])
            @jl_assert b.is_ssa || b.kind === :global (
                ex, "allow local BindingId as function name?")
            get!(scope.binding_assignments, b.id, ex[1])
        elseif k1 === K"Identifier"
            ex[1].mod isa Module &&
                explicit_declare_in_scope!(ctx, scope, ex[1], :global)
            get!(scope.assignments, NameKey(ex[1]), ex[1])
            get!(ctx.layer_ids, (ex[1].context::SyntaxContext).layer,
                 length(ctx.layer_ids)+1)
        else
            @jl_assert false (ex, "unknown kind in assignment")
        end
    elseif k in KSet"= constdecl assign_or_constdecl_if_global"
        k1 = kind(ex[1])
        _record_layer!(ctx, ex[1])
        sc = ex[1].context::SyntaxContext
        if k === K"constdecl" && is_flisp_compat(ex[1]) &&
            is_top_scope(scope) && sc.layer !== ctx.layer
            # hack: flisp declares a mangled global in expansion; we must not error
            explicit_declare_in_scope!(ctx, scope, ex[1], :global)
        elseif k1 === K"BindingId"
            b = get_binding(ctx, ex[1])
            get!(scope.binding_assignments, b.id, ex[1])
        elseif k1 === K"Identifier"
            ex[1].mod === nothing &&
                get!(scope.assignments, NameKey(ex[1]), ex[1])
        elseif k1 === K"Placeholder"
            # nothing to declare
        else
            @jl_assert false (ex, "unknown kind in assignment")
        end
        if !(k == K"constdecl" && numchildren(ex) == 1)
            _find_scope_decls!(ctx, scope, ex[2])
        end
    elseif needs_resolution(ex) && !(k in KSet"scope_block lambda method_defs")
        for e in children(ex)
            _find_scope_decls!(ctx, scope, e)
        end
    end
    nothing
end

# Produce a complete ScopeInfo and add it to the stack of active scopes.  This
# means finding all variables declared and used in the scope `ex` and generating
# the (identifier,layer)=>binding_id mapping `scope.vars`
function enter_scope!(ctx, ex)
    @jl_assert kind(ex) in KSet"lambda scope_block method_defs toplevel_lambda generated_lambda" ex
    # Note that generated functions produce lambdas with this false
    is_toplevel_thunk = kind(ex) === K"toplevel_lambda"
    parent_id = (is_toplevel_thunk || isempty(ctx.scope_stack)) ?
        0 : ctx.scopes[ctx.scope_stack[end]].id
    scope = ScopeInfo(ctx, parent_id, ex)

    #---------------------------------------------------------------------------
    # Find explicit decls that may influence assignment assignment resolution
    if kind(ex) in KSet"lambda toplevel_lambda generated_lambda"
        for c in children(ex[1])
            @jl_assert kind(c) in KSet"Identifier BindingId Placeholder" c
            explicit_declare_in_scope!(ctx, scope, c, :argument)
        end
        for c in children(ex[2])
            kind(c) === K"Placeholder" && continue
            @jl_assert kind(c) === K"Identifier" c
            sp_id = explicit_declare_in_scope!(ctx, scope, c, :static_parameter)
            p = parent(ctx, scope)
            if !isnothing(p) # usually true, false for generated functions
                ctx.sp_typevars[sp_id] = p.vars[NameKey(c)]
            end
        end
        for c in children(ex)[3:end]
            _find_scope_decls!(ctx, scope, c)
        end
    else
        for c in children(ex)
            _find_scope_decls!(ctx, scope, c)
        end
    end
    push!(ctx.scope_stack, scope.id) # influences resolution below

    #---------------------------------------------------------------------------
    # Find assignment targets, possibly introducing implicit locals and globals
    for (bid, _node_id) in sort!(collect(scope.binding_assignments); by=first)
        # Mutable nameless bindings may be introduced in desugaring.  These
        # should be capturable, and may be local to the nearest lambda or
        # global.  Desugaring should ensure these are never used undef.
        b = get_binding(ctx, bid)
        b.lambda_id != 0 || add_lambda_local!(ctx, scope, b)
    end
    for (vk, node_id) in sort!(collect(scope.assignments);
                               by=x->let nk=x[1]; (nk.name, ctx.layer_ids[nk.layer]); end)
        local ex = node_id
        b = resolve_name(ctx, ex)
        if b === nothing
            sc = ex.context::SyntaxContext
            # Top-level assignments are locals in hygienic expansions.  We may
            # need to adjust this, as flisp makes them name-mangled globals.
            hygienic_toplevel = !is_base_layer(sc) && sc.layer !== ctx.layer
            if is_toplevel_thunk && !hygienic_toplevel
                # top-level assignments in no scope and no expansion
                push!(ctx.soft_assignable_globals, vk)
                declare_in_scope!(ctx, top_scope(ctx), ex, :global)
            elseif scope.is_permeable && !hygienic_toplevel &&
                is_defined_and_owned_global(
                    syntax_module(sc), Symbol(vk.name), ctx.world)
                # special soft scope rules: existing global variables are assigned to
                if ctx.enable_soft_scopes
                    push!(ctx.soft_assignable_globals, vk)
                    declare_in_scope!(ctx, top_scope(ctx), ex, :global)
                else
                    declare_in_scope!(ctx, scope, ex, :local; is_ambiguous_local=true)
                end
            else
                declare_in_scope!(ctx, scope, ex, :local)
            end
        elseif b.kind === :global
            if is_toplevel_thunk
                # assign-existing and make visible to soft scope
                push!(ctx.soft_assignable_globals, vk)
            elseif !isnothing(resolve_name(ctx, ex; exclude_toplevel_globals=true)) ||
                (ctx.enable_soft_scopes && scope.is_permeable &&
                vk in ctx.soft_assignable_globals)
                # assign-existing-global if this is an explicit global that
                # isn't at top level, or if the soft scope exception applies
            else
                declare_in_scope!(ctx, scope, ex, :local; is_ambiguous_local = scope.is_permeable)
            end
        elseif b.kind === :static_parameter
            throw(LoweringError(ex, "cannot overwrite a static parameter"))
        elseif b.kind === :local || b.kind === :argument
            # unambiguous assignment to existing variable
        end
    end

    return scope
end

function add_local_decls!(ctx, stmts, srcref, scope)
    # Add local decls to start of block so that closure conversion can
    # initialize if necessary.
    for id in sort!(collect(values(scope.vars)))
        binfo = get_binding(ctx, id)
        if binfo.kind == :local
            push!(stmts, @ast ctx srcref [K"local" binding_ex(ctx, id)])
        end
    end
end

function _resolve_scopes(ctx::ScopeResolutionContext, ex::SyntaxTree,
                         @nospecialize(scope::Union{Nothing, ScopeInfo}))
    k = kind(ex)
    @jl_assert scope isa ScopeInfo || k === K"lambda" ||
        k === K"toplevel_lambda" || k === K"generated_lambda" ex
    if k == K"Identifier"
        if (mod = ex.mod; !isnothing(mod))
            return new_global_binding(ctx, ex, syntax_name(ex), mod)
        end
        b = resolve_name(ctx, ex)
        # Unresolved names are assumed global
        if isnothing(b)
            gid = declare_in_scope!(ctx, top_scope(ctx), ex, :global)
            b = get_binding(ctx, gid)
        end
        # Body-level @nospecialize sets :nospecialize metadata on identifiers.
        # Propagate this to the binding so the slot gets the nospecialize flag.
        if getmeta(ex, :nospecialize, false) && b.kind === :argument
            b.is_nospecialize = true
        end
        newleaf(ex, K"BindingId", b.id)
    elseif k === K"BindingId"
        ex
    elseif k == K"softscope"
        newleaf(ex, K"TOMBSTONE")
    elseif !needs_resolution(ex)
        ex
    elseif k == K"local"
        # Local declarations have a value of `nothing` according to flisp
        # lowering.
        # TODO: Should local decls be disallowed in value position?
        @ast ctx ex (::K"nothing")
    elseif k == K"decl"
        ex_out = mapchildren(e->_resolve_scopes(ctx, e, scope), ex)
        name = ex_out[1]
        if kind(name) != K"Placeholder"
            binfo = get_binding(ctx, name)
            if binfo.kind == :global && !is_top_scope(enclosing_lambda(ctx, scope))
                throw(LoweringError(ex, "type declarations for global variables must be at top level, not inside a function"))
            end
        end
        id = ex_out[1]
        if kind(id) != K"Placeholder"
            binfo = get_binding(ctx, id)
            if !isnothing(binfo.type) && binfo.kind !== :global
                throw(LoweringError(ex, "multiple type declarations found for `$(binfo.name)`"))
            end
            binfo.type = ex_out[2]
        end
        ex_out
    elseif k == K"always_defined"
        resolve_name(ctx, ex[1]).is_always_defined = true
        newleaf(ex, K"TOMBSTONE")
    elseif k in KSet"lambda toplevel_lambda generated_lambda"
        # opaque closures are the exception
        # scope isa ScopeInfo && @jl_assert scope.is_lifted ex
        newscope = enter_scope!(ctx, ex)
        arg_bindings = _resolve_scopes(ctx, ex[1], newscope)
        sparam_bindings = SyntaxList()
        for sp in children(ex[2])
            kind(sp) === K"Placeholder" && continue
            push!(sparam_bindings, _resolve_scopes(ctx, sp, newscope))
        end
        self_id = if numchildren(arg_bindings) === 0
            0
        elseif getmeta(ex[1][1], :is_kwcall_self, false)
            syntax_id(arg_bindings[3])
        else
            syntax_id(arg_bindings[1])
        end
        body_stmts = SyntaxList()
        add_local_decls!(ctx, body_stmts, ex, newscope)
        body = _resolve_scopes(ctx, ex[3], newscope)
        if kind(body) == K"block"
            append!(body_stmts, children(body))
        else
            push!(body_stmts, body)
        end
        ret_var = numchildren(ex) == 4 ?
            _resolve_scopes(ctx, ex[4], newscope) : nothing
        pop!(ctx.scope_stack)
        @ast ctx ex [k
            LambdaBindings(self_id, newscope.id, newscope.locals_capt)::K"LambdaBindings"
            arg_bindings
            [K"block" sparam_bindings...]
            [K"block" body_stmts...]
            ret_var
        ]
    elseif k == K"scope_block"
        newscope = enter_scope!(ctx, ex)
        stmts = SyntaxList()
        add_local_decls!(ctx, stmts, ex, newscope)
        for e in children(ex)[2:end]
            push!(stmts, _resolve_scopes(ctx, e, newscope))
        end
        pop!(ctx.scope_stack)
        @ast ctx ex [K"block" stmts...]
    elseif k == K"method_defs"
        newscope = enter_scope!(ctx, ex)
        mname = _resolve_scopes(ctx, ex[1], scope)
        tvs = SyntaxList()
        for tv in children(ex[2]) # hack. flisp: replace-vars
            rhs = _resolve_scopes(ctx, tv[2], newscope)
            if kind(tv[1]) === K"Placeholder"
                @ast ctx tv [K"=" tv[1] rhs]
            else
                bid = declare_in_scope!(ctx, newscope, tv[1], :typevar)
                get_binding(ctx, bid).is_always_defined = true
                deps = Vector{IdTag}()
                _typevar_refs!(deps, ctx, rhs)
                isempty(deps) || (ctx.tv_deps[bid] = deps)
                push!(tvs, @ast ctx tv [K"=" binding_ex(ctx, bid) rhs])
            end
        end
        stmts = SyntaxList()
        add_local_decls!(ctx, stmts, ex, newscope)
        push!(stmts, _resolve_scopes(ctx, ex[3], newscope))
        pop!(ctx.scope_stack)
        @ast ctx ex [K"method_defs" mname [K"block" tvs...] [K"block" stmts...]]
    elseif k == K"islocal"
        e1 = ex[1]
        islocal = kind(e1) == K"Identifier" &&
            let b = resolve_name(ctx, e1)
                !isnothing(b) && b.kind !== :global
            end
        @ast ctx ex islocal::K"Bool"
    elseif k == K"isglobal"
        e1 = ex[1]
        isglobal = kind(e1) == K"Identifier" &&
            let b = resolve_name(ctx, e1)
                isnothing(b) || b.kind === :global
            end
        @ast ctx ex isglobal::K"Bool"
    elseif k == K"locals"
        stmts = SyntaxList()
        locals_dict = ssavar(ctx, ex, "locals_dict")
        push!(stmts, @ast ctx ex [K"="
            locals_dict
            [K"call"
                [K"call"
                    "apply_type"::K"core"
                    "Dict"::K"top"
                    "Symbol"::K"core"
                    "Any"::K"core"
                ]
            ]
        ])
        for sid in ctx.scope_stack
            for id in sort!(collect(values(ctx.scopes[sid].vars)))
                binfo = get_binding(ctx, id)
                if binfo.kind == :global || binfo.is_internal ||
                    binfo.kind == :typevar
                    continue
                end
                binding = binding_ex(ctx, id)
                push!(stmts, @ast ctx ex [K"if"
                    [K"isdefined" binding]
                    [K"call"
                        "setindex!"::K"top"
                        locals_dict
                        binding
                        binfo.name::K"Symbol"
                    ]
                ])
            end
        end
        push!(stmts, locals_dict)
        newnode(ex, K"block", stmts)
    elseif k == K"thisfunction"
        lam = enclosing_lambda(ctx, scope::ScopeInfo).node_id
        self_arg = lam[1][1]
        for a in children(lam[1])
            getmeta(a, :thisfunction_original, false) && (self_arg = a)
        end
        return _resolve_scopes(ctx, self_arg, scope)
    elseif k == K"assert"
        etype = extension_type(ex)
        if etype == "require_existing_locals"
            for v in ex[2:end]
                b = resolve_name(ctx, v)
                if isnothing(b) || !(b.kind in (:local, :argument))
                    throw(LoweringError(v, "`outer` annotations must match with a local variable in an outer scope but no such variable was found"))
                end
            end
        elseif etype == "global_toplevel_only"
            if !is_top_scope(scope)
                e = ex[2][1]
                throw(LoweringError(e, "$(kind(e)) is only allowed in global scope"))
            end
        elseif etype == "toplevel_only"
            if !is_top_scope(enclosing_lambda(ctx, scope))
                e = ex[2][1]
                throw(LoweringError(e, "this syntax is only allowed in top level code"))
            end
        else
            @jl_assert false (ex, "unknown syntax assertion")
        end
        newleaf(ex, K"TOMBSTONE")
    elseif k === K"relayered_global"
        bid = get(scope.vars, NameKey(ex[1]), nothing)
        !isnothing(bid) && let b = get_binding(ctx, bid)
            b.kind !== :global && throw(LoweringError(ex, string(
                "unhygienic global name `$(NameKey(ex[1]).name)` conflicts ",
                "with an existing $(_var_str(b.kind))")))
        end
        newleaf(ex, K"TOMBSTONE")
    elseif k == K"function_decl"
        resolved = mapchildren(e->_resolve_scopes(ctx, e, scope), ex)
        name = resolved[1]
        if kind(name) == K"BindingId"
            bk = get_binding(ctx, name).kind
            if bk == :argument
                throw(LoweringError(name, "Cannot add method to a function argument"))
            elseif bk == :global && !is_top_scope(enclosing_lambda(ctx, scope))
                throw(LoweringError(name, """
                    Global method definition needs to be placed at the top \
                    level, or use `eval()`"""))
            end
        end
        resolved
    elseif k == K"constdecl"
        if !is_top_scope(enclosing_lambda(ctx, scope))
            throw(LoweringError(ex, "unsupported `const` inside function"))
        end
        resolved = mapchildren(e->_resolve_scopes(ctx, e, scope), ex)
        if kind(resolved[1]) !== K"Placeholder"
            @jl_assert kind(resolved[1]) === K"BindingId" resolved
            if get_binding(ctx, syntax_id(resolved[1])).kind === :local
                throw(LoweringError(ex, "unsupported `const` declaration on local variable"))
            end
        end
        resolved
    elseif k == K"assign_or_constdecl_if_global"
        @jl_assert numchildren(ex) === 2 ex
        id = _resolve_scopes(ctx, ex[1], scope)
        assignment_kind =
            kind(id) === K"Placeholder" ||
            (get_binding(ctx, id).kind !== :global) ? K"=" : K"constdecl"
        @ast ctx ex _resolve_scopes(ctx, [assignment_kind ex[1] ex[2]], scope)
    elseif k === K"global_if_global"
        out = _resolve_scopes(ctx, ex[1], scope)
        get_binding(ctx, out).kind !== :global ? (@ast ctx ex (::K"TOMBSTONE")) :
            @ast ctx ex [K"global" out]
    else
        mapchildren(e->_resolve_scopes(ctx, e, scope), ex)
    end
end

function _resolve_scopes(ctx::ScopeResolutionContext, exs::AbstractVector, scope)
    out = SyntaxList()
    for e in exs
        push!(out, _resolve_scopes(ctx, e, scope))
    end
    out
end

#-------------------------------------------------------------------------------
# Sub-pass to compute additional information about variable usage as required
# by closure conversion, etc
struct ClosureBindings
    name_stack::Vector{String}      # Names of functions the closure is nested within
    lambdas::Vector{LambdaBindings} # Bindings for each method of the closure
    capt_sp::Set{IdTag}
end

# `binding` is that in `function_decl`, `method_defs[1]`, `method[1]`,
# `function_type[1]` when local
struct ClosureKey
    binding::IdTag
    lam::ScopeId
end

ClosureBindings(name_stack) =
    ClosureBindings(name_stack, Vector{LambdaBindings}(), Set{IdTag}())

mutable struct VariableAnalysisContext <: AbstractLoweringContext
    const layer::ScopeLayer
    const bindings::Bindings
    const scopes::Vector{ScopeInfo}
    const lambda_bindings::LambdaBindings
    const lifted::Bool
    # Stack of method definitions for closure naming
    const method_def_stack::Vector{SyntaxTree}
    const closure_key_stack::Vector{ClosureKey}
    # Collection of information about each closure, principally which methods
    # are part of the closure (and hence captures).
    const closure_bindings::Dict{ClosureKey,ClosureBindings}
    const sp_typevars::Dict{IdTag, IdTag}
    const tv_deps::Dict{IdTag, Vector{IdTag}}
    # Prevents infinite loops when analyzing a binding's type
    const types_in_analysis::Set{IdTag}
end

function init_closure_bindings!(ctx, fname)
    bid = syntax_id(fname)
    ck = closure_key(ctx, fname)
    @jl_assert get_binding(ctx, bid).kind === :local fname
    get!(ctx.closure_bindings, ck) do
        name_stack = Vector{String}()
        for parentname in ctx.method_def_stack
            if kind(parentname) == K"BindingId"
                push!(name_stack, get_binding(ctx, parentname).name)
            end
        end
        push!(name_stack, get_binding(ctx, bid).name)
        ClosureBindings(name_stack)
    end
end

# sparams, globals, and top-level locals interpolated into global methods are OK
# (the last may or may not work intentionally)
function static_eval_disallowed_binding(ctx, ex)
    k = kind(ex)
    if k == K"BindingId"
        b = get_binding(ctx, syntax_id(ex))
        if b.kind != :global && b.kind != :static_parameter
            lam = ctx.scopes[ctx.lambda_bindings.scope_id]
            if is_top_scope(lam) ||
                !(b.lambda_id == top_scope(ctx).id &&
                enclosing_lambda(ctx, parent(ctx, lam)).id == top_scope(ctx).id)
                return ex
            end
        end
    elseif !is_leaf(ex) && !is_quoted(ex)
        for e in children(ex)
            r = static_eval_disallowed_binding(ctx, e)
            if !isnothing(r)
                return r
            end
        end
    end
    return nothing
end

function add_assign!(b::BindingInfo)
    b.is_assigned_once = !b.is_assigned
    b.is_assigned = true
end

# When a closure captures `T` and `T`'s typevar bound references `S`, it must
# capture `S` too
function expand_captured_sp_deps!(ctx, cb::ClosureBindings, scope)
    sps = copy(cb.capt_sp)
    for lb in cb.lambdas, (id, is_capt) in lb.locals_capt
        is_capt && get_binding(ctx, id).kind === :static_parameter && push!(sps, id)
    end
    todo = collect(sps)
    while !isempty(todo)
        sp = pop!(todo)
        owner = ctx.scopes[get_binding(ctx, sp).lambda_id]
        for dep_tv in get(ctx.tv_deps, ctx.sp_typevars[sp], ())
            # The sparam for dep_tv in the same lambda that owns `sp`
            dep_sp = nothing
            for id in keys(owner.locals_capt)
                b = get_binding(ctx, id)
                if b.kind === :static_parameter &&
                        get(ctx.sp_typevars, b.id, IdTag(0)) == dep_tv
                    dep_sp = id
                    break
                end
            end
            isnothing(dep_sp) && throw(LoweringError(
                binding_ex(ctx, dep_tv), "unimplemented capture in sparam bounds"))
            dep_sp in sps && continue
            push!(sps, dep_sp)
            push!(cb.capt_sp, dep_sp)
            ensure_captured!(ctx, scope, get_binding(ctx, dep_sp))
            push!(todo, dep_sp)
        end
    end
end

function closure_key(ctx, ex)
    @jl_assert kind(ex) === K"BindingId" ex
    ClosureKey(syntax_id(ex), ctx.lambda_bindings.scope_id)
end
function current_closure_bindings(ctx)
    isempty(ctx.closure_key_stack) && return nothing
    get(ctx.closure_bindings, ctx.closure_key_stack[end], nothing)
end

# Update ctx.bindings metadata based on binding usage
function analyze_variables!(ctx, ex)
    k = kind(ex)
    if k == K"BindingId"
        b = get_binding(ctx, ex)
        b.is_read = true
        # The type of typed locals is invisible in the previous pass,
        # but is filled in here.
        scope = ctx.scopes[ctx.lambda_bindings.scope_id]
        ensure_captured!(ctx, scope, b)
        # b.kind === :static_parameter && ensure_captured!(ctx, scope, b)
        @jl_assert (b.kind === :global || b.kind === :typevar || b.is_ssa ||
            haskey(ctx.lambda_bindings.locals_capt, b.id)) ex binding_ex(ctx, b.id)
        if b.kind === :static_parameter && ctx.lifted
            cb = current_closure_bindings(ctx)
            isnothing(cb) || push!(cb.capt_sp, b.id)
        end
        if (b.kind === :local || b.kind === :argument) && !isnothing(b.type) &&
            !(b.id in ctx.types_in_analysis)
            push!(ctx.types_in_analysis, b.id)
            analyze_variables!(ctx, binding_type_ex(ctx, b))
            delete!(ctx.types_in_analysis, b.id)
        end
    elseif k == K"Identifier"
        @jl_assert false ex
    elseif !needs_resolution(ex)
        return
    elseif k == K"static_eval" || k == K"foreignsymbol"
        badvar = static_eval_disallowed_binding(ctx, ex[1])
        if !isnothing(badvar)
            default = k == K"foreignsymbol" ?
                "function name and library expression" : "syntax"
            name_hint = getmeta(ex, :name_hint, default)::String
            throw(LoweringError(badvar, "$(name_hint) cannot reference local variable"))
        end
        analyze_variables!(ctx, ex[1])
        return
    elseif k == K"local" || k == K"global"
        # Presence of BindingId within local/global is ignored.
        return
    elseif k == K"="
        lhs = ex[1]
        if kind(lhs) != K"Placeholder"
            b = get_binding(ctx, lhs)
            add_assign!(b)
            scope = ctx.scopes[ctx.lambda_bindings.scope_id]
            ensure_captured!(ctx, scope, b)
            if !isnothing(b.type)
                # Assignments introduce a variable's type later during closure
                # conversion, but we must model that explicitly here.
                analyze_variables!(ctx, binding_type_ex(ctx, b))
            end
        end
        analyze_variables!(ctx, ex[2])
    elseif k == K"function_decl"
        name = ex[1]
        b = get_binding(ctx, name)
        if b.kind === :local
            init_closure_bindings!(ctx, name)
        end
        add_assign!(b)
    elseif k == K"function_type"
        if kind(ex[1]) != K"BindingId" || get_binding(ctx, ex[1]).kind !== :local
            analyze_variables!(ctx, ex[1])
        end
    elseif k == K"constdecl"
        if kind(ex[1]) !== K"Placeholder"
            b = get_binding(ctx, ex[1])
            b.is_const = true
            add_assign!(b)
        end
        analyze_variables!(ctx, ex[2])
    elseif k == K"call"
        name = ex[1]
        if kind(name) == K"BindingId"
            get_binding(ctx, name).is_called = true
        end
        foreach(e->analyze_variables!(ctx, e), children(ex))
    elseif k == K"method_defs"
        push!(ctx.method_def_stack, ex[1])
        is_closure = kind(ex[1]) == K"BindingId" &&
            get_binding(ctx, ex[1]).kind === :local
        ctx2 = VariableAnalysisContext(
            ctx.layer, ctx.bindings, ctx.scopes,
            ctx.lambda_bindings, true, ctx.method_def_stack,
            ctx.closure_key_stack,
            ctx.closure_bindings, ctx.sp_typevars, ctx.tv_deps,
            ctx.types_in_analysis)
        if is_closure
            push!(ctx.closure_key_stack, closure_key(ctx2, ex[1]))
            cb = init_closure_bindings!(ctx2, ex[1])
            scope = ctx.scopes[ctx2.lambda_bindings.scope_id]
        end
        analyze_variables!(ctx2, ex[2])
        analyze_variables!(ctx2, ex[3])
        if is_closure
            # All captures are known now; close them over typevar-bound deps
            expand_captured_sp_deps!(ctx, cb, scope)
            pop!(ctx.closure_key_stack)
        end
        pop!(ctx.method_def_stack)
    elseif k == K"_opaque_closure"
        name = ex[1]
        init_closure_bindings!(ctx, name)
        push!(ctx.method_def_stack, name)
        push!(ctx.closure_key_stack, closure_key(ctx, ex[1]))
        analyze_variables!(ctx, ex[2])
        analyze_variables!(ctx, ex[3])
        analyze_variables!(ctx, ex[4])
        analyze_variables!(ctx, ex[9])
        pop!(ctx.method_def_stack)
        pop!(ctx.closure_key_stack)
    elseif k in KSet"lambda toplevel_lambda generated_lambda"
        lbs = lambda_bindings(ex[1])
        if !isempty(ctx.closure_key_stack)
            # Record all lambdas for the same closure type in one place
            ck = last(ctx.closure_key_stack)
            if get_binding(ctx, ck.binding).kind === :local
                push!(ctx.closure_bindings[ck].lambdas, lbs)
            end
        end
        let ctx2 = VariableAnalysisContext(
            ctx.layer, ctx.bindings, ctx.scopes,
            lbs, false, ctx.method_def_stack,
            ctx.closure_key_stack, ctx.closure_bindings,
            ctx.sp_typevars, ctx.tv_deps, ctx.types_in_analysis)
            foreach(e->analyze_variables!(ctx2, e), ex[4:end])
        end
    else
        for e in children(ex)
            analyze_variables!(ctx, e)
        end
    end
    nothing
end

function resolve_scopes(ctx::ScopeResolutionContext, ex)
    if !(kind(ex) in KSet"lambda toplevel_lambda generated_lambda")
        # Wrap in a top level thunk if we're not already expanding a lambda.
        # (Maybe this should be done elsewhere?)
        ex = @ast ctx ex [K"toplevel_lambda" [K"block"] [K"block"] ex]
    end
    _resolve_scopes(ctx, ex, nothing)
end

"""
This pass analyzes scopes and the names (locals/globals etc) used within them.

Names of kind `K"Identifier"` are transformed into binding identifiers of
kind `K"BindingId"`. The associated `Bindings` table in the context records
metadata about each binding.

This pass also records the set of binding IDs used locally within the
enclosing lambda form and information about variables captured by closures.
"""
@fzone "JL: resolve_scopes" function resolve_scopes(ctx::DesugaringContext, ex;
                                                    soft_scope::Union{Nothing,Bool}=nothing,
                                                    world::UInt=ctx.world)
    enable_soft_scopes = soft_scope !== nothing ? soft_scope : contains_softscope_marker(ex)
    ctx2 = ScopeResolutionContext(ctx.layer, ctx.bindings,
                                  Dict{ScopeLayer, Int}(),
                                  Vector{ScopeInfo}(), Vector{ScopeId}(),
                                  Set{NameKey}(), Dict{IdTag, IdTag}(),
                                  Dict{IdTag, Vector{IdTag}}(),
                                  enable_soft_scopes,
                                  world)
    ex2 = resolve_scopes(ctx2, ex)
    ctx3 = VariableAnalysisContext(ctx2.layer, ctx2.bindings,
                                   ctx2.scopes, lambda_bindings(ex2[1]), true,
                                   SyntaxList(), Vector{ClosureKey}(),
                                   Dict{ClosureKey,ClosureBindings}(),
                                   ctx2.sp_typevars, ctx2.tv_deps, Set{IdTag}())
    analyze_variables!(ctx3, ex2)
    analyze_def_and_use!(ctx3, ex2)
    ctx3, ex2
end