[Suggestion] Allow easier content editing/Add partial order to mod API calling

[RageLeague]

You would think that you can actually replace anything in lua, but today I realized that you cannot. You cannot replace local functions in another file, for example.

I'm working on a mod that Topo sorts the mods, so that mods can depend on other mods being loaded. I've already written the algorithm, but I realized that there's no way for me to call it before any mod APIs are called. The first, obvious step is to replace the InvokeModAPI function so that it Topo sorts the mods before doing anything, but you soon realize a problem: the OnLoad function calls the InvokeModAPI function defined locally, and there's no way to change that. The second logical step is to replace the OnLoad function, but the you realize that OnLoad is already called when a mod is mounted, so replacing it wouldn't do much good.

Here's my suggestion: rewrite the content.lua file so that instead of functions referencing local functions, those functions reference a function in a table("Content", for example), so that if I replace the function in content, I don't have to update all other functions in content so that they reference the new function instead.

Or, implement a partial mod order system(or a well order system with a priority number, but I wouldn't recommend it because it relies on other mods not changing their priority number) so that I don't need to make a mod to allow partial mod order. What I mean is after all the mods are mounted, sort the mod tables so that mods that depends on other mods are sorted to the back of the line, and mods that loads before other mods are sorted to an earlier index.

Here's the algorithm that I wrote.

Spoiler

-- check if check_table contains an alias of mod_table
-- if no alias is provided for mod, fall back to its id.
local function TableContainAlias(check_table, mod_table)
    return check_table and (check_table == (mod_table.alias or mod_table.id) or table.arraycontains(check_table, mod_table.alias or mod_table.id))
end

-- Takes in a list of mods and re-order them in place. Hopefully.
-- Each mod table may contain two fields: load_before, load_after
-- Each is a list of mod aliases.
-- This function uses Kahn’s Algorithm, except it is stable(tries to preserve original order).
local function TopoSortMods(mod_list)
    -- a list that keeps track of edges so we can do topo sort later
    local edge_list = {}
    for i, mod_table in ipairs(mod_list) do
        -- contains the node for this mod
        local this_mod_node = {
            mod_table = mod_table, 
            load_before = {}, 
            load_after = {}, 
            preloads = 0,
        }
        table.insert(edge_list, this_mod_node)
        -- check dependencies for other mods.
        for j, other_table in ipairs(mod_list) do
            if other_table ~= mod_table then
                if TableContainAlias(mod_table.load_before, other_table) or TableContainAlias(other_table.load_after, mod_table) then
                    -- if not this_mod_node.load_before[j] then
                    --     this_mod_node.edges = this_mod_node.edges + 1
                    -- end
                    this_mod_node.load_before[j] = true
                end
                if TableContainAlias(mod_table.load_after, other_table) or TableContainAlias(other_table.load_before, mod_table) then
                    if not this_mod_node.load_after[j] then
                        this_mod_node.preloads = this_mod_node.preloads + 1
                    end
                    this_mod_node.load_after[j] = true
                end
            end
        end
    end
    -- use a heap to optimize the inserting from O(n) to O(log(n))
    -- this keeps track of which index has all their prereqs loaded already.
    local no_preloads = Heap(function(a,b)return a < b end)
    for i, edge_table in ipairs(edge_list) do
        if edge_table.preloads == 0 then
            no_preloads:push(i)
        end
    end

    local sorted_list = {}
    -- while you still have unassigned items, repeat the following
    while #sorted_list < #edge_list do
        if no_preloads:isempty() then
            -- assert(false, "Topo Sort Error: Circular requirement.")
            return false, "Topo Sort Error: Circular requirement."
        end
        local selected_index = no_preloads:pop()
        table.insert(sorted_list, selected_index)
        for idx, val in pairs(edge_list[selected_index].load_before) do
            edge_list[idx].preloads = edge_list[idx].preloads - 1
            if edge_list[idx].preloads == 0 then
                no_preloads:push(idx)
            end
        end
    end
    -- TheGame:GetDebug():CreatePanel(DebugTable(edge_list))
    -- TheGame:GetDebug():CreatePanel(DebugTable(sorted_list))

    table.clear(mod_list)
    for i, idx in ipairs(sorted_list) do
        table.insert(mod_list, edge_list[idx].mod_table)
    end
    -- TheGame:GetDebug():CreatePanel(DebugTable(mod_list))
    return true
end

TopoSortMod takes in a list of all mod tables and sort them with stable Kahn's Algorithm. It modifies the original table as a side effect. It returns true if the mods are successfully sorted, or false if failed to sort due to circular requirements(in which case nothing will change).

A mod table can have two fields here: load_before and load_after, which are either a string or a table of strings, indicating that this mod should be loaded before/after another mod(s) with the indicated alias, or - if that mod has no alias for some reason - the mod's ID.

Since there are possibly multiple configuration of mod order, this algorithm will try to preserve the original order(ie. if a mod A is before another mod B originally and they do not depend on each other, then A is still before B). This will slow the algorithm, but unless you have like hundreds of thousands of mods installed, the change shouldn't be noticeable.

This function should be called after all mods are mounted, but before any other mod APIs are called so that the modifications from earlier mods can be accessed by later mods.

[rooks]

Nice work!

I think it'd be good if the mod sorting was built-in to the game.  Do you have any issues if I put your function into the game directly, possibly with edits if required?

 

[RageLeague]

I don't have any issues.

The fact that I actually helped Klei with writing the code is good enough for me.

[Wumpus the 19th]

56 minutes ago, RageLeague said:

The fact that I actually helped Klei with writing the code is good enough for me.

I believe the elusive title fairy needs to visit after a dev at klei entertainment came to you and asked for code.