So that any data or metadata contradicting master flags will cause
a cyclic interaction error as they did before the plugin graph was split
in 232202c17e.
Most of the existing tests ave been rewritten as PluginGraphTest tests,
because the tests can be simpler, faster, clearer and more tightly
scoped to the functionality that's actually being tested.
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.
GCC 8 doesn't support C++17's parallel algorithms, which I'd like to
use, and GCC 10 is the newest major version available from Ubuntu
20.04's repositories.
This commit removes a Linux-only std::filesystem::path constructor test,
which fails due to a thrown exception when compiled with GCC 10. The
failure isn't important, because libloot avoids that particular
constructor: in a sense an exception is a bit better because it would
make any usage more obvious.
If a group edge exists due to the presence of some user metadata,
distinguish that from when the edge exists only due to masterlist
metadata.
The logic for detecting when a path between two groups involves user
metadata gives results that are stable but that do not consistently
paths that only consist of masterlist metadata. If there are multiple
paths between two groups and some involve user metadata, the same path
will be picked every time, but the path picked depends on the structure
of the groups graph.
In practice this shouldn't be much of a problem because the paths are
only exposed when there's a cycle, and in that case all paths between
the two groups need to be removed/broken anyway.
The use of FormIDs doesn't apply to Morrowind and it's really the
records that are significant - FormIDs are an implementation detail.
This also aligns with other use of records in names.
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.
Oliver Hamlet