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

module StackTraces


import Base: hash, ==, show

export StackTrace, StackFrame, stacktrace, catch_stacktrace

"""
    StackFrame

Stack information representing execution context.
"""
immutable StackFrame
    "the name of the function containing the execution context"
    func::Symbol
    "the LambdaInfo containing the execution context (if it could be found)"
    outer_linfo::Nullable{LambdaInfo}
    "the path to the file containing the execution context"
    file::Symbol
    "the line number in the file containing the execution context"
    line::Int
    "the path to the file containing the context for code inlined into the execution context"
    inlined_file::Symbol
    "the line number in the file containing the context for code inlined into the execution context"
    inlined_line::Int
    "true if the code is from C"
    from_c::Bool
    "representation of the pointer to the execution context as returned by `backtrace`"
    pointer::Int64  # Large enough to be read losslessly on 32- and 64-bit machines.
end

StackFrame(func, file, line) = StackFrame(func, Nullable{LambdaInfo}(), file, line, empty_sym, -1, false, 0)

"""
    StackTrace

An alias for `Vector{StackFrame}` provided for convenience; returned by calls to
`stacktrace` and `catch_stacktrace`.
"""
typealias StackTrace Vector{StackFrame}

const empty_sym = symbol("")
const unk_sym = symbol("???")
const UNKNOWN = StackFrame(unk_sym, Nullable{LambdaInfo}(), unk_sym, -1, empty_sym, -1, true, 0) # === lookup(C_NULL)


#=
If the StackFrame has function and line information, we consider two of them the same if
they share the same function/line information. For unknown functions, line == pointer, so we
never actually need to consider the pointer field.
=#
function ==(a::StackFrame, b::StackFrame)
    a.line == b.line && a.from_c == b.from_c && a.func == b.func && a.file == b.file
end

function hash(frame::StackFrame, h::UInt)
    h += 0xf4fbda67fe20ce88 % UInt
    h = hash(frame.line, h)
    h = hash(frame.file, h)
    h = hash(frame.func, h)
end


"""
    lookup(pointer::Union{Ptr{Void}, UInt}) -> StackFrame

Given a pointer to an execution context (usually generated by a call to `backtrace`), looks
up stack frame context information.
"""
function lookup(pointer::Ptr{Void})
    info = ccall(:jl_lookup_code_address, Any, (Ptr{Void}, Cint), pointer - 1, false)
    if length(info) == 8
        is_inlined = (info[4] !== empty_sym)
        return StackFrame(string(info[1]),
            info[6] === nothing ? Nullable{LambdaInfo}() : Nullable{LambdaInfo}(info[6]),
            is_inlined ? info[4] : info[2],
            Int(is_inlined ? info[5] : info[3]),
            is_inlined ? info[2] : "",
            is_inlined ? Int(info[3]) : -1,
            info[7], Int64(info[8]))
    else
        return UNKNOWN
    end
end

lookup(pointer::UInt) = lookup(convert(Ptr{Void}, pointer))

"""
    stacktrace([trace::Vector{Ptr{Void}},] [c_funcs::Bool=false]) -> StackTrace

Returns a stack trace in the form of a vector of `StackFrame`s. (By default stacktrace
doesn't return C functions, but this can be enabled.) When called without specifying a
trace, `stacktrace` first calls `backtrace`.
"""
function stacktrace(trace::Vector{Ptr{Void}}, c_funcs::Bool=false)
    stack = map(lookup, trace)::StackTrace

    # Remove frames that come from C calls.
    if !c_funcs
        filter!(frame -> !frame.from_c, stack)
    end

    # Remove frame for this function (and any functions called by this function).
    remove_frames!(stack, :stacktrace)
end

stacktrace(c_funcs::Bool=false) = stacktrace(backtrace(), c_funcs)

"""
    catch_stacktrace([c_funcs::Bool=false]) -> StackTrace

Returns the stack trace for the most recent error thrown, rather than the current execution
context.
"""
catch_stacktrace(c_funcs::Bool=false) = stacktrace(catch_backtrace(), c_funcs)

"""
    remove_frames!(stack::StackTrace, name::Symbol)

Takes a `StackTrace` (a vector of `StackFrames`) and a function name (a `Symbol`) and
removes the `StackFrame` specified by the function name from the `StackTrace` (also removing
all frames above the specified function). Primarily used to remove `StackTraces` functions
from the `StackTrace` prior to returning it.
"""
function remove_frames!(stack::StackTrace, name::Symbol)
    splice!(stack, 1:findlast(frame -> frame.func == name, stack))
    return stack
end

function remove_frames!(stack::StackTrace, names::Vector{Symbol})
    splice!(stack, 1:findlast(frame -> frame.func in names, stack))
    return stack
end

function show_spec_linfo(io::IO, frame::StackFrame)
    if isnull(frame.outer_linfo)
        print(io, frame.func !== empty_sym ? frame.func : "?")
    else
        linfo = get(frame.outer_linfo)
        if isdefined(linfo, 8)
            params = linfo.(#=specTypes=#8).parameters
            ft = params[1]
            if ft <: Function && isempty(ft.parameters) &&
                    isdefined(ft.name.module, ft.name.mt.name) &&
                    ft == typeof(getfield(ft.name.module, ft.name.mt.name))
                print(io, ft.name.mt.name)
            elseif isa(ft, DataType) && is(ft.name, Type.name) && isleaftype(ft)
                f = ft.parameters[1]
                print(io, f)
            else
                print(io, "(::", ft, ")")
            end
            first = true
            print(io, '(')
            for i = 2:length(params)
                first || print(io, ", ")
                first = false
                print(io, "::", params[i])
            end
            print(io, ')')
        else
            print(io, linfo.name)
        end
    end
end

function show(io::IO, frame::StackFrame; full_path::Bool=false)
    if frame.inlined_file !== empty_sym
        # if we have inlining information, print it first
        inline_info = full_path ? string(frame.inlined_file) : basename(string(frame.inlined_file))
        print(io, " [inlined code] from ", inline_info)
        if frame.inlined_line > 0
            print(io, ":", frame.inlined_line)
        end
        println(io)
    end

    print(io, " in ")
    show_spec_linfo(io, frame)
    file_info = full_path ? string(frame.file) : basename(string(frame.file))
    print(io, " at ", file_info, ":", frame.line)
end

end