# Lowering pass 1: Macro expansion, simple normalizations and quote expansion

# One per pass.  Current scope layer is managed separately.
struct MacroExpansionContext{Attrs} <: AbstractLoweringContext
    graph::SyntaxGraph{Attrs}
    bindings::Bindings
    scope_layers::Vector{ScopeLayer}
    expr_compat_mode::Bool
    macro_world::UInt
end

parent_layer(ctx::MacroExpansionContext, sl, err_ex) =
    is_base_layer(sl) ?
    throw(MacroExpansionError(err_ex, "`escape` node in outer context")) :
    ctx.scope_layers[sl.parent_id]

function MacroExpansionContext(graph::SyntaxGraph, mod::Module,
                               expr_compat_mode::Bool, world::UInt)
    base_layer = ScopeLayer(1, mod, 0, false, false)
    MacroExpansionContext(
        graph, Bindings(), ScopeLayer[base_layer], expr_compat_mode, world)
end

#--------------------------------------------------
# Expansion of quoted expressions
function collect_unquoted!(ctx, unquoted, ex, depth)
    if kind(ex) == K"$" && depth == 0
        # children(ex) is usually length 1, but for double interpolation it may
        # be longer and the children may contain K"..." expressions. Wrapping
        # in a tuple groups the arguments together correctly in those cases.
        push!(unquoted, @ast ctx ex [K"tuple" children(ex)...])
    else
        inner_depth = kind(ex) == K"quote" ? depth + 1 :
                      kind(ex) == K"$"     ? depth - 1 :
                      depth
        for e in children(ex)
            collect_unquoted!(ctx, unquoted, e, inner_depth)
        end
    end
    return unquoted
end

function expand_quote(ctx, ex)
    unquoted = SyntaxList(ctx)
    collect_unquoted!(ctx, unquoted, ex, 0)
    # Unlike user-defined macro expansion, we don't call append_sourceref! for
    # the entire expression produced by `quote` expansion. We could, but it
    # seems unnecessary for `quote` because the surface syntax is a transparent
    # representation of the expansion process. However, it's useful to add the
    # extra srcref in a more targeted way for $ interpolations inside
    # interpolate_ast, so we do that there.
    #
    # In principle, particular user-defined macros could opt into a similar
    # mechanism.
    #
    # TODO: Should we try adding a srcref to the `quote` node only for the
    # extra syntax generated by expand_quote so srcref essentially becomes
    # (ex, @HERE) ?
    if is_expr_value(ex)
        @jl_assert isempty(unquoted) ex
        ex
    elseif kind(ex) === K"Identifier" && !hasattr(ex, :mod)
        @jl_assert isempty(unquoted) ex
        # not just an optimization; expected e.g. in (. mod (quote field))
        @ast ctx ex [(ctx.expr_compat_mode ? K"inert" : K"inert_syntaxtree") ex]
    elseif ctx.expr_compat_mode
        @ast ctx ex [K"call"
            interpolate_ast::K"Value"
            Expr::K"Value"
            [K"inert" ex]
            unquoted...
        ]
    else
        @ast ctx ex [K"call"
            interpolate_ast::K"Value"
            SyntaxTree::K"Value"
            [K"inert_syntaxtree" ex]
            unquoted...
        ]
    end
end

#--------------------------------------------------
struct MacroContext <: AbstractLoweringContext
    graph::SyntaxGraph
    macrocall::Union{SyntaxTree,LineNumberNode,SourceRef}
    scope_layer::ScopeLayer # of outer context
    expr_compat_mode::Bool
end

function adopt_scope(ex, ctx::MacroContext)
    adopt_scope(ex, ctx.scope_layer.id)
end

struct MacroExpansionError <: Exception
    context::Union{Nothing,MacroContext}
    ex::SyntaxTree
    msg::String
    "The source position relative to the node - may be `:begin` or `:end` or `:all`"
    position::Symbol
    "Error that occurred inside the macro function call (`nothing` if no inner exception)"
    err
    MacroExpansionError(
        context::Union{Nothing,MacroContext}, ex::SyntaxTree, msg::AbstractString, position::Symbol,
        @nospecialize err = nothing
    ) = new(context, ex, msg, position, err)
end

function MacroExpansionError(ex::SyntaxTree, msg::AbstractString; position=:all)
    MacroExpansionError(nothing, ex, msg, position)
end

function Base.showerror(io::IO, exc::MacroExpansionError)
    print(io, "MacroExpansionError")
    ctx = exc.context
    if !isnothing(ctx)
        # Use `Expr` formatting to pretty print the macro name for now -
        # there's quite a lot of special cases. We could alternatively consider
        # calling sourcetext() though that won't work well if it's a
        # synthetically-generated macro name path.
        macname_str = string(Expr(
            :macrocall, est_to_expr(ctx.macrocall[1]), nothing))
        print(io, " while expanding ", macname_str,
              " in module ", ctx.scope_layer.mod)
    end
    print(io, ":\n")
    # TODO: Display niceties:
    # * Show the full provenance tree somehow, in addition to the primary
    #   source location we're showing here?
    # * What if the expression doesn't arise from a source file?
    # * How to deal with highlighting trivia? Could provide a token kind or
    #   child position within the raw tree? How to abstract this??
    src = sourceref(exc.ex)
    if src isa LineNumberNode
        highlight(io, src, note=exc.msg)
    else
        fb = first_byte(src)
        lb = last_byte(src)
        pos = exc.position
        byterange = pos == :all     ? (fb:lb)   :
            pos == :begin   ? (fb:fb-1) :
            pos == :end     ? (lb+1:lb) :
            error("Unknown position $pos")
        highlight(io, src.file[], byterange, note=exc.msg)
    end
    if !isnothing(exc.err)
        print(io, "\nCaused by:\n")
        showerror(io, exc.err)
    end
end

function _eval_dot(world::UInt, mod, ex::SyntaxTree)
    if kind(ex) === K"."
        mod = _eval_dot(world, mod, ex[1])
        ex = ex[2]
    end
    if kind(ex) === K"inert"
        ex = ex[1]
    end
    kind(ex) in KSet"Identifier Symbol" && mod isa Module ?
        Base.invoke_in_world(world, getproperty, mod, Symbol(ex.name_val)) :
        nothing
end

# If macroexpand(ex[1]) is an identifier or dot-expression, we can simply grab
# it from the scope layer's module in ctx.macro_world.  Otherwise, we need to
# eval arbitrary code (which, TODO: does not use the correct world age, and it
# isn't clear the language is meant to support this).
function eval_macro_name(ctx, mctx::MacroContext, ex0::SyntaxTree, sl)
    mod = sl.mod
    ex = expand_forms_1(ctx, ex0, sl)
    try
        if kind(ex) === K"Value"
            ex.value
        elseif kind(ex) === K"Identifier"
            # module from globalref, or some expansion, or default
            if hasattr(ex, :mod)
                mod = ex.mod::Module
            elseif hasattr(ex, :scope_layer)
                mod = ctx.scope_layers[ex.scope_layer::LayerId].mod
            end
            Base.invoke_in_world(ctx.macro_world, getproperty,
                                 mod, Symbol(ex.name_val))
        elseif kind(ex) === K"." &&
                (ed = _eval_dot(ctx.macro_world, mod, ex); !isnothing(ed))
            ed
        else
            # `ex` might contain a nontrivial mix of scope layers so we can't
            # just `eval()` it, as it's already been partially lowered by this
            # point.  Instead, we repeat the latter parts of `lower()` here.
             ctx2, ex2 = expand_forms_2(ctx, ex)
             ctx3, ex3 = resolve_scopes(ctx2, ex2)
             ctx4, ex4 = convert_closures(ctx3, ex3)
            _ctx5, ex5 = linearize_ir(ctx4, ex4)
            expr_form  = to_lowered_expr(ex5)
            ccall(:jl_toplevel_eval, Any, (Any, Any), mod, expr_form)
        end
    catch err
        throw(MacroExpansionError(mctx, ex, "Macro not found", :all, err))
    end
end

# Record scope layer information for symbols passed to a macro by setting
# scope_layer for each expression and also processing any K"escape" arising
# from previous expansion of old-style macros.
#
# See also set_scope_layer()
function set_macro_arg_hygiene(ctx, ex, sl)
    k = kind(ex)
    sl = ctx.scope_layers[get(ex, :scope_layer, sl.id)]
    if is_leaf(ex)
        setattr!(mkleaf(ex), :scope_layer, sl.id)
    elseif k === K"hygienic-scope"
        set_macro_arg_hygiene(
            ctx, ex[1], new_macro_scope_layer(
                ctx, sl, ex[2].value::Module, sl.hygiene_compat))
    elseif k === K"escape"
        set_macro_arg_hygiene(ctx, ex[1], parent_layer(ctx, sl, ex))
    else
        node = mapchildren(e->set_macro_arg_hygiene(ctx, e, sl), ctx, ex)
        setattr!(node, :scope_layer, sl.id)
    end
end

function prepare_macro_args(ctx, sl, mctx, raw_args)
    macro_args = Any[mctx]
    for arg in raw_args
        # Add hygiene information to be carried along with macro arguments.
        #
        # Macro call arguments may be either
        # * Unprocessed by the macro expansion pass
        # * Previously processed, but spliced into a further macro call emitted by
        #   a macro expansion.
        # In either case, we need to set scope layers before passing the
        # arguments to the macro call.
        push!(macro_args, set_macro_arg_hygiene(ctx, arg, sl))
    end
    return macro_args
end

# TODO: Do we need to handle :scope_layer or multiple escapes here?
# See https://github.com/c42f/JuliaLowering.jl/issues/39
"""
Insert a hygienic-scope around each arg of K"toplevel" returned from a macro.

It isn't correct for macro expansion to recurse into a K"toplevel" expression
since one child may define a macro and the next may use it.  However, not
recursing now means we lose some important context: the module of the macro we
just expanded, which is necessary for resolving the identifiers in the
K"toplevel" AST.  The solution implemented in JuliaLang/julia#53515 was to save
our place and expand later using `Expr(:hygienic-scope toplevel_child mod)`.

Of course, these hygienic-scopes are also necessary because existing user code
contains the corresponding escaping, which would otherwise cause errors. We
already consumed the hygienic-scope that comes with every expansion, but won't
be looking for escapes under :toplevel, so push hygienic-scope under toplevel
"""
function fix_toplevel_expansion(ctx, ex::SyntaxTree, mod::Module, lnn::LineNumberNode)
    if kind(ex) === K"toplevel"
        mapchildren(ctx, ex) do e
            @ast ctx ex [K"hygienic-scope" e mod::K"Value" lnn::K"Value"]
        end
    else
        mapchildren(e->fix_toplevel_expansion(ctx, e, mod, lnn), ctx, ex)
    end
end

function expand_macro(ctx, ex, outer_sl)
    @jl_assert kind(ex) == K"macrocall" ex

    macname = ex[1]
    # TODO: should this be base_layer(ctx, outer_sl)?
    mctx = MacroContext(ctx.graph, ex, outer_sl, ctx.expr_compat_mode)
    macfunc = eval_macro_name(ctx, mctx, macname, outer_sl)
    raw_args = ex[3:end]
    macro_loc = if kind(ex[2]) === K"Value"
        loc = ex[2].value
        if loc isa MacroSource
            loc
        elseif loc isa LineNumberNode
            # Some macros, e.g. @cmd, don't play nicely with file == nothing
            isnothing(loc.file) ? LineNumberNode(loc.line, :none) : loc
        else
            LineNumberNode(0, :none)
        end
    elseif kind(ex[2]) === K"VERSION"
        loc = source_location(LineNumberNode, ex)
        isdefined(Core, :MacroSource) ? Core.MacroSource(loc, ex[2].value) : loc
    else
        LineNumberNode(0, :none)
    end
    # We use a specific well defined world age for the next checks and macro
    # expansion invocations. This avoids inconsistencies if the latest world
    # age changes concurrently.
    #
    # TODO: Allow this to be passed in
    # TODO: hasmethod always returns false for our `typemax(UInt)` meaning
    # "latest world," which we shouldn't be using.
    has_new_macro = ctx.macro_world === typemax(UInt) ?
        hasmethod(macfunc, Tuple{typeof(mctx), typeof.(raw_args)...}) :
        hasmethod(macfunc, Tuple{typeof(mctx), typeof.(raw_args)...}; world=ctx.macro_world)

    if has_new_macro
        macro_args = prepare_macro_args(ctx, outer_sl, mctx, raw_args)
        expanded = try
            Base.invoke_in_world(ctx.macro_world, macfunc, macro_args...)
        catch exc
            newexc = exc isa MacroExpansionError ?
                MacroExpansionError(mctx, exc.ex, exc.msg, exc.position, exc.err) :
                MacroExpansionError(mctx, ex, "Error expanding macro", :all, exc)
            # TODO: We can delete this rethrow when we move to AST-based error propagation.
            rethrow(newexc)
        end
        if expanded isa SyntaxTree
            if expanded._graph !== ctx.graph
                # If the macro has produced syntax outside the macro context,
                # copy it over. TODO: Do we expect this always to happen?  What
                # is the API for access to the macro expansion context?
                expanded = copy_ast(ctx, expanded)
            end
        else
            expanded = @ast ctx ex expanded::K"Value"
        end
    else
        # Compat: attempt to invoke an old-style macro if there's no applicable
        # method for new-style macro arguments.
        macro_args = Any[macro_loc, base_layer(ctx, outer_sl).mod]

        for arg in raw_args
            @jl_assert kind(arg) !== K"VERSION" arg # handled in EST conversion
            # For hygiene in old-style macros, we omit any additional scope
            # layer information from macro arguments. Old-style macros will
            # handle that using manual escaping in the macro itself.
            #
            # Note that there's one slight incompatibility here for identifiers
            # interpolated into the `raw_args` from outer macro expansions of
            # new-style macros which call old-style macros. Instead of seeing
            # `Expr(:escape)` in such situations, old-style macros will now see
            # `Expr(:scope_layer)` inside `macro_args`.
            push!(macro_args, est_to_expr(arg))
        end
        expanded = try
            Base.invoke_in_world(ctx.macro_world, macfunc, macro_args...)
        catch exc
            if exc isa MethodError && exc.f === macfunc
                if !isempty(methods_in_world(
                    macfunc, Tuple{typeof(mctx), Vararg{Any}},
                    ctx.macro_world, ex))
                    # If the macro has at least some methods implemented in the
                    # new style, assume the user meant to call one of those
                    # rather than any old-style macro methods which might exist
                    exc = MethodError(
                        macfunc,
                        (prepare_macro_args(ctx, outer_sl, mctx, raw_args)..., ),
                        ctx.macro_world)
                end
            end
            rethrow(MacroExpansionError(mctx, ex, "Error expanding macro", :all, exc))
        end
        macro_lnn = macro_loc isa MacroSource ? macro_loc.lno : macro_loc
        expanded = expr_to_est(ex._graph, expanded, macro_lnn)
    end

    expanded = append_sourceref!(ctx, expanded, ex._id)
    if kind(expanded) != K"Value"
        # Module scope for the returned AST is the module where this particular
        # method was defined (may be different from `parentmodule(macfunc)`)
        mod_for_ast = lookup_method_instance(macfunc, macro_args,
                                             ctx.macro_world).def.module
        expanded = expand_forms_1(
            ctx, expanded,
            new_macro_scope_layer(ctx, outer_sl, mod_for_ast, !has_new_macro))
    end
    return expanded
end

function append_sourceref!(ctx, ex, id::NodeId)
    @jl_assert ex._id != id ex
    setattr!(ex, :macro_source, id)
    for c in children(ex)
        append_sourceref!(ctx, c, id)
    end
    ex
end

function remove_scope_layer!(ex)
    if !is_leaf(ex)
        for c in children(ex)
            remove_scope_layer!(c)
        end
    end
    JuliaSyntax.deleteattr!(ex, :scope_layer)
    ex
end

function remove_scope_layer(ctx, ex)
    remove_scope_layer!(mktree(ex))
end

"""
Lowering pass 1

This pass expands macros and quote (interpolations).  It also annotates every
identifier with the expansion it came from.
"""
function expand_forms_1(ctx::MacroExpansionContext, ex::SyntaxTree, sl::ScopeLayer)
    k = kind(ex)
    expr_sl = ctx.scope_layers[get(ex, :scope_layer, sl.id)]
    if k == K"Identifier"
        hasattr(ex, :scope_layer) ?
            ex : setattr!(mkleaf(ex), :scope_layer, sl.id)
    elseif k == K"escape"
        if numchildren(ex) !== 1
            throw(LoweringError(ex, "`escape` requires one argument"))
        end
        expand_forms_1(ctx, ex[1], parent_layer(ctx, expr_sl, ex))
    elseif k == K"hygienic-scope"
        if !(2 <= numchildren(ex) <= 3 && ex[2].value isa Module)
            throw(LoweringError(ex,"`hygienic-scope` requires an AST and a module"))
        end
        expand_forms_1(
            ctx, ex[1],
            new_macro_scope_layer(
                ctx, expr_sl, ex[2].value::Module, expr_sl.hygiene_compat))
    elseif k == K"quote"
        if numchildren(ex) !== 1
            throw(LoweringError(ex,"`quote` expects one argument"))
        end
        expand_forms_1(ctx, expand_quote(ctx, ex[1]), sl)
    elseif k == K"macrocall"
        expand_macro(ctx, ex, expr_sl)
    elseif k == K"toplevel" && !is_base_layer(expr_sl)
        fix_toplevel_expansion(
            ctx, ex, expr_sl.mod, source_location(LineNumberNode, ex))
    elseif k == K"module" || k == K"toplevel" || k == K"inert" || k == K"inert_syntaxtree"
        # Remove scope layer information from any inert syntax which survives
        # macro expansion so that it doesn't contaminate lowering passes which
        # are later run against the quoted code. TODO: This works as a first
        # approximation but is incorrect in general. We need to revisit such
        # "deferred hygiene" situations (see https://github.com/c42f/JuliaLowering.jl/issues/111)
        remove_scope_layer(ctx, ex)
    elseif k in KSet"<: >: --> ' unknown_head"
        # if this is a form that requires resolving some identifier, add the
        # scope layer.  if this is an unknown form to be cleaned up by AST
        # conversion, save the scope layer just in case.
        setattr(mapchildren(e->expand_forms_1(ctx,e,sl), ctx, ex),
                :scope_layer, expr_sl.id)
    elseif is_leaf(ex)
        ex
    elseif (k == K"do" && numchildren(ex) == 2 && kind(ex[1]) == K"macrocall" &&
        kind(ex[2]) == K"->")
        mac_ex = @ast ctx ex [
            K"macrocall"
            ex[1][1] # mac name
            ex[1][2] # loc
            ex[2]    # do-lambda
            children(ex[1])[3:end]...
        ]
        expand_macro(ctx, mac_ex, expr_sl)
    else
        mapchildren(e->expand_forms_1(ctx,e,sl), ctx, ex)
    end
end

function ensure_macro_attributes!(graph)
    g2 = ensure_attributes!(
        graph;
        var_id=IdTag,
        scope_layer=LayerId,
        macro_source=NodeId,
        __macro_ctx__=Nothing,
        meta=CompileHints)
    DEBUG ? ensure_attributes!(g2; jl_source=LineNumberNode) : g2
end

@fzone "JL: macroexpand" function expand_forms_1(mod::Module, ex::SyntaxTree, expr_compat_mode::Bool, macro_world::UInt)
    graph = ensure_macro_attributes!(copy_attrs(syntax_graph(ex)))
    ex = reparent(graph, ex)
    ctx_out = MacroExpansionContext(graph, mod, expr_compat_mode, macro_world)
    ex_out = expand_forms_1(ctx_out, ex, only(ctx_out.scope_layers))
    graph2 = delete_attributes(ex._graph, :__macro_ctx__)
    # TODO: Returning the context with pass-specific mutable data is a bad way
    # to carry state into the next pass. We might fix this by attaching such
    # data to the graph itself as global attributes?
    ctx2 = MacroExpansionContext(graph2, ctx_out.bindings, ctx_out.scope_layers,
                                 expr_compat_mode, macro_world)
    return ctx2, reparent(ctx2.graph, ex_out)
end
