-- A hook system that iterates using a doubly linked list
-- This allows for efficient removal without having to make
-- any adjustments to the iteration process
-- There are three types of hooks: pre-listeners, returning hooks, and post-listeners
-- Only returning hooks can affect the values returned by hook.Call
-- while listeners are passive hooks that cannot interrupt one another
-- Aditionally, post-listeners receive a read-only table and count of all returns
-- All hook types have an optional priority argument that can be used to guarantee call order
-- The highest priority is called first, making the iteration order [inf -> -inf]

local gmod = gmod
local select = select
local newproxy = newproxy
local ErrorNoHalt = ErrorNoHalt
local setmetatable = setmetatable
local table_insert = table.insert
local table_remove = table.remove

hook = {}

--- Event object structure

-- Root of the linked list
local PRE_HOOK_ROOT = 1
local MAIN_HOOK_ROOT = 2
local POST_HOOK_ROOT = 3

-- Hashtable to find hook objects by identifier
-- Key = any identifier
-- Value = hook object
local PRE_ID_TO_INDEX = 4
local MAIN_ID_TO_INDEX = 5
local POST_ID_TO_INDEX = 6

-- Lookup hashtable for tails of every active priority
-- This allows for quick insertion given an active priority number
-- Key = Number[-inf, inf] priority
-- Value = hook object
local PRE_PRIORITY_LOOKUP = 7
local MAIN_PRIORITY_LOOKUP = 8
local POST_PRIORITY_LOOKUP = 9

-- Sorted array (from highest to lowest) of active priorities
-- This is needed as hashtables don't have explicit ordering
-- thus inserting a priority with no active hooks requires
-- finding a hole between two other priorities
-- Key = Number[1, inf) index
-- Value = Number[-inf, inf] priority
local PRE_PRIORITY_LIST = 10
local MAIN_PRIORITY_LIST = 11
local POST_PRIORITY_LIST = 12

-- Number[0, inf) of active priorities
-- This is the length of the *_PRIORITY_LIST array
local PRE_PRIORITY_COUNT = 13
local MAIN_PRIORITY_COUNT = 14
local POST_PRIORITY_COUNT = 15


--- Hook object structure

local HOOK_PREV = 1 -- Previous hook object in the list
local HOOK_NEXT = 2 -- Next hook object in the list
local HOOK_PRIORITY = 3 -- Number[-inf, inf] priority of the hook

local Hooks = {}

local function TestValid(obj)
    return obj.IsValid
end

local function CreateHookObject(func, priority)
    return setmetatable({
        [HOOK_PREV] = nil,
        [HOOK_NEXT] = nil,
        [HOOK_PRIORITY] = priority
    }, {__call = func})
end

local function AddHook(event, name, func, priority, hooktbl, HOOK_ROOT, PRIORITY_LIST, PRIORITY_LOOKUP, PRIORITY_COUNT, ID_TO_INDEX)
    if (event == nil) then
        ErrorNoHalt("")
        return
    end

    -- hook.Add("event", function() end, PRIORITY)
    if (priority == nil) then
        if (!isfunction(name)) then
            ErrorNoHalt("")
            return
        end

        -- Shift hook.Add* arguments over one
        priority = func
        func = name
        name = nil
    end

    if (priority == nil) then
        priority = 0
    elseif (!isnumber(priority)) then
        ErrorNoHalt("")
        return
    end

    -- Automatically remove hooks that use an identifier with
    -- an IsValid method when that method is no longer valid
    if (name != nil && !isstring(name)) then
        local success, IsValid = pcall(TestValid, name)

        if (success && isfunction(IsValid)) then
            local oldfunc = func
            func = function(...)
                if (!IsValid(name)) then
                    hook.Remove(event, name)
                    return nil
                end

                return oldfunc(name, ...)
            end
        end
    end

    local hooktbl = Hooks[event]

    if (hooktbl == nil) then
        hooktbl = {
            [PRE_HOOK_ROOT] = nil,
            [MAIN_HOOK_ROOT] = nil,
            [POST_HOOK_ROOT] = nil,

            [PRE_PRIORITY_LIST] = {},
            [MAIN_PRIORITY_LIST] = {},
            [POST_PRIORITY_LIST] = {},
            [PRE_PRIORITY_LOOKUP] = {},
            [MAIN_PRIORITY_LOOKUP] = {},
            [POST_PRIORITY_LOOKUP] = {},
            [PRE_PRIORITY_COUNT] = 0,
            [MAIN_PRIORITY_COUNT] = 0,
            [POST_PRIORITY_COUNT] = 0,

            [PRE_ID_TO_INDEX] = {},
            [MAIN_ID_TO_INDEX] = {},
            [POST_ID_TO_INDEX] = {}
        }

        Hooks[event] = hooktbl
    end

    local hookobj

    if (name == nil) then
        hookobj = CreateHookObject(func, priority)
    else
        hookobj = hooktbl[ID_TO_INDEX][name]

        if (hookobj == nil) then
            hookobj = CreateHookObject(func, priority)
            hooktbl[ID_TO_INDEX][name] = hookobj
        else
            -- Update the function
            getmetatable(hookobj).__call = func
            local prevpriority = hookobj[HOOK_PRIORITY]

            -- If we have the same priority as before
            -- no need to do anything else
            if (priority == prevpriority) then
                return
            end

            hookobj[HOOK_PRIORITY] = priority

            -- The priority has changed, remove the object from the list
            -- and reinsert it as it were new

            local lastobj = hookobj[HOOK_PREV]
            local nextobj = hookobj[HOOK_NEXT]

            -- If we're the root, promote the next object
            if (lastobj == nil) then
                -- If we changed priority but we're the only object in the list
                -- keep our position and exit
                if (nextobj == nil) then
                    return
                end

                hooktbl[HOOK_ROOT] = nextobj
                nextobj[HOOK_PREV] = nil
            else
                lastobj[HOOK_NEXT] = nextobj

                if (nextobj != nil) then
                    nextobj[HOOK_PREV] = lastobj
                end
            end

            -- Remove the previous links
            hookobj[HOOK_PREV] = nil
            hookobj[HOOK_NEXT] = nil
        end
    end

    if (hooktbl[HOOK_ROOT] == nil) then
        -- Only hook in the list
        hooktbl[HOOK_ROOT] = hookobj
        hooktbl[PRIORITY_LOOKUP][priority] = hookobj
        hooktbl[PRIORITY_COUNT] = 1
        hooktbl[PRIORITY_LIST][1] = priority
    else
        local lookup = hooktbl[PRIORITY_LOOKUP]
        local prioritytail = lookup[priority]

        if (prioritytail == nil) then
            local count = hooktbl[PRIORITY_COUNT]

            -- We already know we're gonna have to insert a new priority
            -- Update the count now so we don't have to do the same for multiple branches
            hooktbl[PRIORITY_COUNT] = count + 1

            local prioritylist = hooktbl[PRIORITY_LIST]

            for i = 1, count do
                if (prioritylist[i] < priority) then
                    table_insert(prioritylist, i, priority)

                    -- If we're the highest priority
                    -- insert at the root and exit
                    if (i == 1) then
                        local prevroot = hooktbl[HOOK_ROOT]
                        hookobj[HOOK_NEXT] = prevroot
                        prevroot[HOOK_PREV] = hookobj
                        hooktbl[HOOK_ROOT] = hookobj
                        lookup[priority] = hookobj

                        return
                    end

                    -- Use the closest priority on the lesser end as our insertion point
                    prioritytail = lookup[prioritylist[i - 1]]

                    goto PriorityFound
                end
            end

            -- No lower priority found, we must be the lowest priority
            prioritylist[count + 1] = priority
            prioritytail = lookup[prioritylist[count]]

            ::PriorityFound::
        end

        -- Linked list insertion
        -- prioritytail[HOOK_PREV] -> prioritytail --> hookobj --> prioritytail[HOOK_NEXT]
        hookobj[HOOK_PREV] = prioritytail
        hookobj[HOOK_NEXT] = prioritytail[HOOK_NEXT]
        prioritytail[HOOK_NEXT] = hookobj

        -- Update the priority's tail
        lookup[priority] = hookobj
    end
end

function hook.Add(event, name, func, priority --[[= 0]])
    AddHook(event, name, func, priority, hooktbl, MAIN_HOOK_ROOT, MAIN_PRIORITY_LIST, MAIN_PRIORITY_LOOKUP, MAIN_PRIORITY_COUNT, MAIN_ID_TO_INDEX)
end

function hook.AddPreListener(event, name, func, priority --[[= 0]])
    AddHook(event, name, func, priority, hooktbl, PRE_HOOK_ROOT, PRE_PRIORITY_LIST, PRE_PRIORITY_LOOKUP, PRE_PRIORITY_COUNT, PRE_ID_TO_INDEX)
end

function hook.AddPostListener(event, name, func, priority --[[= 0]])
    AddHook(event, name, func, priority, hooktbl, POST_HOOK_ROOT, POST_PRIORITY_LIST, POST_PRIORITY_LOOKUP, POST_PRIORITY_COUNT, POST_ID_TO_INDEX)
end

local function Pack(...)
    local num = select("#", ...)

    if (num != 0) then
        return {...}, num
    end

    return nil
end

local function noop()
end

local function noopret()
    return nil
end

function hook.Call(event, GM, ...)
    local hooktbl = Hooks[event]
    local hashooks = hooktbl != nil
    local hasrets = false
    local rets, num

    if (hashooks) then
        -- Pre-listeners
        local curhook = hooktbl[PRE_HOOK_ROOT]

        while (curhook != nil) do
            curhook(...)
            curhook = curhook[HOOK_NEXT]
        end

        curhook = hooktbl[MAIN_HOOK_ROOT]

        -- Main hooks
        while (curhook != nil) do
            rets, num = Pack(curhook(...))

            if (rets != nil) then
                hasrets = true
                break
            end

            curhook = curhook[HOOK_NEXT]
        end
    end

    -- Gamemode function
    if (!hasrets) then
        local GMfunc = GM[event]

        if (GMfunc != nil) then
            rets, num = Pack(GMFunc(...))
        end
    end

    if (hashooks) then
        -- Post-listeners (no returns from main hooks)
        local curhook = hooktbl[POST_HOOK_ROOT]

        -- Don't create the read-only table unless we have a hook
        if (curhook != nil) then
            local readrets = setmetatable(newproxy(), {__index = hasrets && rets || noopret, __newindex = noop})

            repeat
                curhook(readrets, num, ...)
                curhook = curhook[HOOK_NEXT]
            until (curhook == nil)
        end
    end

    if (hasrets) then
        return unpack(rets, 1, num)
    end

    return nil
end

function hook.Run(name, ...)
    return Call(name, gmod && gmod.GetGamemode() || nil, ...)
end

local function RemoveHook(event, name, HOOK_ROOT, PRIORITY_LIST, PRIORITY_LOOKUP, PRIORITY_COUNT, ID_TO_INDEX)
    if (event == nil) then
        ErrorNoHalt("")
        return
    end

    if (name == nil) then
        ErrorNoHalt("")
        return
    end

    local hooktbl = Hooks[event]

    if (hooktbl == nil) then
        return
    end

    local hookobj = hooktbl[ID_TO_INDEX][name]

    if (hookobj == nil) then
        return
    end

    hooktbl[ID_TO_INDEX][name] = nil

    local lastobj = hookobj[HOOK_PREV]
    local nextobj = hookobj[HOOK_NEXT]
    local priority = hookobj[HOOK_PRIORITY]
    local lookup = hooktbl[PRIORITY_LOOKUP]

    if (lastobj == nil) then
        hooktbl[HOOK_ROOT] = nextobj

        -- No previous hook means the hook being removed
        -- is the only one with its priority, and it's the highest
        -- FIXME: JK I'm dumb, check if the lookup object == this hook

        -- If the hook is the tail of the priority list
        -- then it must be the only priority of this kind
        -- since this is the root hook
        if (lookup[priority] == hookobj) then
            lookup[priority] = nil
            table_remove(hooktbl[PRIORITY_LIST], 1)
            hooktbl[PRIORITY_COUNT] = hooktbl[PRIORITY_COUNT] - 1
        end
    else
        lastobj[HOOK_NEXT] = nextobj

        if (lookup[priority] == hookobj) then
            -- If there's another hook with the same priority
            -- promote it to the tail of the list
            if (lastobj[HOOK_PRIORITY] == priority) then
                lookup[priority] = lastobj
            else
                lookup[priority] = nil
                local count = hooktbl[PRIORITY_COUNT]
                local prioritylist = hooktbl[PRIORITY_LIST]

                for i = 1, count do
                    if (prioritylist[i] == priority) then
                        table_remove(prioritylist, i)
                    end
                end
            end
        end
    end

    if (nextobj != nil) then
        nextobj[HOOK_PREV] = lastobj
    end
end

function hook.Remove(event, name)
    RemoveHook(event, name, MAIN_HOOK_ROOT, MAIN_PRIORITY_LIST, MAIN_PRIORITY_LOOKUP, MAIN_PRIORITY_COUNT, MAIN_ID_TO_INDEX)
end

function hook.RemovePreListener(event, name)
    RemoveHook(event, name, PRE_HOOK_ROOT, PRE_PRIORITY_LIST, PRE_PRIORITY_LOOKUP, PRE_PRIORITY_COUNT, PRE_ID_TO_INDEX)
end

function hook.RemovePostListener(event, name)
    RemoveHook(event, name, POST_HOOK_ROOT, POST_PRIORITY_LIST, POST_PRIORITY_LOOKUP, POST_PRIORITY_COUNT, POST_ID_TO_INDEX)
end