LOOT’s Sorting Algorithm

LOOT’s sorting algorithm consists of the following stages:

Load plugin data

In this first stage, the plugins to be sorted are parsed and their record IDs (which are FormIDs for all games apart from Morrowind) are stored. When parsing plugins, all subrecords are skipped over for efficiency, apart from the subrecords of the TES4 header record.

Loading plugin data also involves loading any metadata that the plugin may have in the masterlist and userlist.

Create plugin graph vertices

Once the plugins have been loaded, they are sorted into lexicographical order.

After that, two graphs are created, and the plugins are added to them as vertices in their sorted order. Plugins that have their master flag set go in one graph, and plugins that do not have the flag set go in the other.

Two graphs are used because master-flagged plugins must always load before non-master-flagged plugins, and it’s much more efficient to sort them separately and then combine their load orders than to enforce those relationships within a single graph.

A consequence of using two separate graphs is that any plugin data or metadata that involves a pair of plugins with and without their master flag set will be silently ignored. For example: if plugin A is master-flagged and plugin B is not, and plugin A has metadata saying it must load after plugin B, then that metadata will be ignored because the two plugins are sorted independently, as if the other plugin is not installed.

Create plugin graph edges

The steps described in this section are run on both graphs independently.

In this section, the terms vertex and plugin are used interchangeably, and the iteration order ‘for each plugin’ is the order in which the vertices were added to the graph.

For each plugin:

  1. If the plugin is a master file, add edges going to all non-master files. If the plugin is a non-master file, add edges coming from all master files. This shouldn’t result in any edges being added, since masters and non-masters are sorted in separate graphs, but is done for completeness.

  2. Add edges coming from all the plugin’s masters. Missing masters have no edges added.

  3. Add edges coming from all the plugin’s requirements. Missing requirements have no edges added.

  4. Add edges coming from all the plugin’s load after files that are installed plugins.

Hardcoded edges

Some games hardcode certain plugins to load in certain positions, and this section adds edges in the correct order between those plugins, and between those plugins and the rest of the plugins in the graph.

Group edges

For each plugin, the plugins that are members of groups that the current plugin’s group loads after are iterated over and individually checked to see if adding an edge from the other group’s plugin to the current plugin would cause a cycle. If not, the edge is queued for addition. If it would cause a cycle and one of the plugins is in the default group and the other group’s plugin is master-flagged or the current plugin is not master flagged, then the plugin in the default group is recorded as one to skip adding edges to or from when the prospective edge involves any of the groups in the path from the other plugin to the current plugin.

Once all the plugins have been iterated over, all the queued edges are added, skipping those edges identified in the earlier loop.

At this point the plugin graph is checked for cycles, and an error is thrown if any are encountered, so that metadata (or indeed plugin data) that cause them can be corrected.

Overlap edges

Plugin overlap edges are then added. Two plugins overlap if they contain the same record, i.e. if they both edit the same record or if one edits a record the other plugin adds. Plugins also overlap if they both load one or more BSAs (BA2s for Fallout 4) and the BSAs loaded by one plugin contain data for a file path that is also included in the BSAs loaded by the other plugin.

For each plugin, skip it if it overrides no records, otherwise iterate over all other plugins.

  • If the plugin and other plugin override the same number of records and the same number of assets, or do not overlap, skip the other plugin.

  • Otherwise, add an edge from the plugin which overrides more records to the plugin that overrides fewer records, unless that edge would cause a cycle. If the plugins don’t have overlapping records or override the same number of records, the edge is added from the plugin that loads more assets via its BSAs to the plugin that loads fewer assets.

For Morrowind, identifying which records override others requires all of a plugin’s masters to be installed, so if a plugin has missing masters, its total record count is used in place of its override record count. Morrowind plugins also can’t load BSAs, so they can’t have overlapping assets.

Tie-break edges

Finally, tie-break edges are added to ensure that sorting is consistent. The graph’s vertices are sorted into their current load order:

  • If both plugins have positions in the current load order, the function preserves their existing relative order.

  • If one plugin has a position and the other does not, the plugin with a position goes before the plugin without a position.

  • If neither plugin has a load order position, a case-insensitive lexicographical comparison of their filenames without file extensions is used to decide their order. If they are equal, a case-insensitive lexicographical comparison of their file extensions is used.

Once sorted, they are iterated over. Each loop looks at the current vertex and the next one following it (e.g. the first iteration is for vertices 0 and 1, the second is for 1 and 2, etc.).

For each (current, next) pair of vertices, try to find a path from next to current.

If sorting makes no changes, then there won’t be any paths found and it’ll therefore be possible to add an edge from current to next without causing a cycle, producing the old load order.

If no path is found then that means the old load order can be used for those two plugins. If the current vertex has not already been processed (which will be the case unless it appeared in a path found earlier and had its position pinned, see below), append it to a list representing the new load order and record the vertex as having been processed.

If no path is found but the current vertex has been processed and is not the last vertex in the new load order list, pin the position of the next vertex (see below).

If a path is found then that means the old load order for those two plugins (which is current before next) can’t be used. If current is the first vertex in the iteration order, then next is simply treated as the start of the new load order. If current is not the first vertex, iterate over the vertices in the path found, going from next to current, and pin each vertex’s position.

Pinning vertex positions

A vertex’s position needs to be pinned when it must go somewhere before the last plugin in the new load order list, because although it has a fixed position relative to that last plugin, it doesn’t necessarily have a fixed position relative to the plugins that come before the last plugin. I.e. it needs to load earlier, but how much earlier?

To pin a vertex’s position, iterate over the new load order list in reverse order, going from the last vertex towards the first, and stop at the first load order vertex for which there is no path going from the unpinned vertex to the load order vertex. This is equivalent to finding the last plugin that the unpinned vertex’s plugin can load after (which is not necessarily the same as the last plugin it must load after).

If such a load order vertex is found, add an edge going from it to the unpinned vertex. If the found vertex is not the last vertex in the load order list, also add an edge going from the unpinned vertex to the vertex after the found vertex. Then record the unpinned vertex’s new position in the new load order list: the vertex is now pinned.

Topologically sort the plugin graphs

This is done for both graphs independently.

Note that edges for explicit interdependencies are the only edges allowed to create cycles. However, the graph is again checked for cycles to guard against potential logic bugs, and if a cycle is encountered an error is thrown.

Once the graph is confirmed to be cycle-free, a topological sort is performed on the graph, outputting a list of plugins in their newly-sorted load order.

Combine the two load orders

Finally, the sorted load order for non-master-flagged plugins is appended to the sorted load order for master-flagged plugins to give the complete sorted load order.