Most of the complexity is handled by libloadorder, but it's worth noting that:
- The game path is OpenMW's install path, not Morrowind's
- OpenMW doesn't force master-flagged plugins to load before others
- OpenMW doesn't provide a way to record the load order of inactive plugins
- .omwgame and .omwaddon plugins are equivalent to .esm and .esp respectively, while .omwscripts plugins have a completely different format with none of the metadata that libloot uses.
- OpenMW effectively relies on additional data paths to load Morrowind's (and mods') files, and the last directory listed that contains a given filename is used to load a file with that filename, with the main data path effectively being the first listed.
- I've disabled support for ghosted plugins for OpenMW because it makes the multi-path stuff more confusing and may not provide any benefit.
The new logic is conceptually simpler, with fewer special cases to
handle. Unlike the old implementation, the new approach avoids cycles.
It basically does depth-first searches through the group graph, adding
edges from each group's plugins to the plugins in the group's
successors.
This involved reversing the direction of edges in the group graph, as
this switches the logic from trying to find predecessors to trying to
successors: the new direction matches that of plugin graph edges, so
it's less confusing.
I can't think of a situation in which the iteration order of plugins
within a group matters. I tested it manually with my test load order of
~1600 plugins, and saw no difference when the order was randomly
shuffled. I've added a test case but it's a relatively simple scenario
and there may be a more complex scenario where it would matter that I
haven't thought of.
A buffer is used to hold the plugins in the previous groups in the
current path, because that's noticeably faster than just recording the
path and looking up the plugins for each group in the path. It does
duplicate the group vectors, but that's an insignificant amount of
memory used.
The new approach has a negative performance impact, with sorting now 15%
slower than before.
A more efficient solution could be to implement a custom DFS algorithm
that doesn't stop when it reaches a vertex it's already visited (which
would be fine since the graph has already been validated to be acyclic),
as then only the root vertices would need to be searched from.
For vertices in the plugin graph. This is so that the group and overlap
edges are evaluated in an order that does not depend on the current load
order. Tie-breaking still uses the current load order.
This is necessary because if the group and overlap edges that get added
depend on the current load order, sorting and applying changes the
current load order, so sorting again may give different results even
even though no plugin data or metadata has changed.
Rather than storing them in PluginSortingData, which is now immutable.
This also means the predecessor groups plugins map can use vertices
instead of plugin names, which is a
little simpler.
All master-flagged plugins must load before all non-master-flaggeg
plugins, and this means that most of the edges added in the graph
(about 2/3rds in large load orders) are just enforcing this.
Having lots of edges negatively impacts the performance of checking for
paths, and adding overlap edges is O(n^2), so instead of having one
graph containing all plugins, create one graph for masters and another
for plugins, and sort them independently, then append the non-masters
order to the masters order.
This speeds up my 1619 plugin sort from 44s to 34s, and larger load
orders should see more benefit.
This does introduce some behavioural changes though:
- any requirement or load after metadata that tries to put a master
after a non-master will now be ignored instead of causing a cyclic
interaction error. A master-flagged plugin that has a
non-master-flagged plugin will also no longer cause a cyclic
interaction error, but that scenario is much less likely.
- The resulting load order may differ slightly. When tie-breaking finds
a path that contradicts the old load order, it pins the positions of
plugins in the path. However, the lack of master flag edges causes
later edges to be added or skipped differently. This is all ultimately
down to the order of edge iteration mattering during path discovery
(since it stops at the first path discovered), so even though the two
approaches result in graphs that enforce the same relationships
between plugins at the point that tie-breaking starts, ties may be
broken differently due to differences in the edges enforcing those
relationships.
Instead of brute-forcing the existence of a Hamiltonian path, attempt
to create one by adding edges between each pair of adjacent vertices
in the old load order wherever possible without introducing a cycle,
and otherwise move plugins as necessary.
The bidirectional BFS has been refactored to use a visitor so that
the implementation can be shared between checking if a path exists and
finding a path without always incurring the cost of the latter.
This may result in a different sorted load order than the previous
method, but that shouldn't make a practical difference as tie-break edges
are only added between unrelated plugins.
For a load order containing 1619 plugins, this reduces the time taken
to sort them from around 400s to around 51s.
They're used by Fallout 4.
BA2 file and folder hashes are 32-bit, so collisions are much more
likely than with BSAs, which use 64-bit hashes. I put in some logging
to check the likelihood of collisions, and found that the largest
number of assets loaded was by Fallout4.esm (no surprise), which loaded
371182 files across 5746 folders, with the most files in one folder
being 124871. That puts the probability of a hash collision within that
folder at above 80%.
I did see different Fallout4 -*.ba2 files contain files with the same
combination of folder and file hashes, and similar for
DLCUltraHighResolution -*.ba2 files, so I'm going to try calculating
64-bit hashes from the file paths stored in the BA2 files.
This supports BSAs used from:
* Oblivion
* Fallout 3
* Fallout: New Vegas
* Skyrim
* Skyrim: Special Edition
If Skyrim VR uses the same BSA format as Skyrim SE, that's also supported.
Morrowind BSAs are intentionally not supported because they cannot be
loaded by plugins and so are of no interest to LOOT.
The BSA parsing code has been adapted from my abandoned libbsa library.
This doesn't bother reading folder and file names as hash collisions
seem pretty unlikely (2^64 possible folder hashes, and 2^64 possible
file hashes per folder).
The code checks and requires that BSAs use little-endian numbers, as
while big-endian BSAs are apparently possible I've never seen one,
and I don't want to try adding support without one to test against.
If a plugin's masters are all present, this makes the sorting logic for
Morrowind match the other supported games. If a plugin's masters are
missing, use the plugin's total record count as the override record
count.
Plugins with missing masters cannot be loaded by the game, reducing the
impact (if any) of the probably-inflated record counts. It's better for
LOOT to be able to sort a slightly wonky load order if there are missing
masters than for it to fail completely, as such plugins may be present
for development and testing reasons.
Sorting doesn't work as for other games, because esplugin can't tell if
a plugin contains override records, so returns 0 for their count, so no
overlap edges get added.
Skip adding an edge between a pair of plugins if all the following
conditions are met:
- the edge is to be added due to group membership
- adding the edge would introduce a cycle in the absence of any
other group membership edges.
Oliver Hamlet
Oliver HamletandOliver Hamlet
Oliver Hamlet