Provide edge source information in cyclic interaction errors

[Ortham]

This is necessary for loot/loot#999. This would involve adding an attribute to edges that indicates what type of source they have, which could be an enum:

enum EdgeType {
  hardcoded,
  masterFlag,
  master,
  masterlistRequirement,
  userRequirement,
  masterlistLoadAfter,
  userLoadAfter,
  masterlistGroup,
  userGroup,
  overlap,
  tieBreak,
}

This would then be exposed through CyclicInteractionError through some kind of structure that gives the plugins in the cycle and the types of interaction between them.

[Ortham]

I've run into a bit of trouble trying to meaningfully distinguish between "masterlist group" and "userlist group" edges. A group edge is added when one plugin belongs to a group that loads after a group that another plugin belongs to, so there are two levels of metadata at work. Consider this metadata:

# masterlist
groups:
- name: A
- name: B
  after: [ A ]
plugins:
- name: A.esp
  group: A
- name: C.esp
- name: BB.esp
  group: B

# userlist
groups:
- name: default
  after: [ B ]
plugin:
- name: B.esp
  group: B

Where does the group edge between A.esp and B.esp come from? Is it because:

• A.esp belongs to group A, in which case EdgeType could be masterlistGroup?
• B.esp belongs to group B, in which case EdgeType could be userGroup?
• B loads after A, in which case the EdgeType could be masterlistGroup?

That's a simple case. Now consider the transitive group edge between A.esp and C.esp.

• A.esp belongs to group A, in which case the EdgeType could be masterlistGroup?
• C.esp belongs to group default, which wasn't specified, so an implicitDefaultGroup variant would be needed.
• default doesn't load directly after A, instead it loads after B which loads after A. However, default loading after B is due to user metadata, and B loading after A is due to masterlist metadata. How should this be represented, a masterlistAndUserGroup variant?

Even if the example metadata above was all in the masterlist, knowing that isn't very helpful, because you have A.esp -[masterlist group]-> B.esp, but that tells you nothing about where group metadata comes from, because it could be:

• The plugins' group fields.
• The plugins' groups' after fields.
• The after fields of groups in the path from one plugin's group to the other's, which could contain any number of groups.

Whatever the case, you're going to have to dig around the log or the masterlist and possibly userlist a bit to find out what's actually going on. Contrast this with A.esp -[masterlist load after]-> B.esp, where you can immediately tell that there's a masterlist entry for B.esp that has an after entry for A.esp.

The only reasonable approach I can see that ends up with something useful is to use userGroup if there is any user metadata involved in the group edge existing (and possibly rename it to groupInvolvingUserlist or something to make that clearer), and masterlistGroup otherwise. Applying this logic to the example above, the group edges are:

• A.esp -[userlist group]-> B.esp
• A.esp -[masterlist group]-> BB.esp
• A.esp -[userlist group]-> C.esp
• B.esp -[userlist group]-> C.esp
• BB.esp -[userlist group]-> C.esp

At least then it's easy to see if user metadata is involved.

[TanninOne]

Man, this stuff is complex...

First of all, as I was reading this, before I got to the end I had the same thought as you: As soon as it involves the userlist the edge should be tagged as userlist/userlistgroup.

Coming from the user perspective (the following is a bit of rambling tbh), I guess there are 3 possible states an edge can be in:

• this edge is required, you can't change it at all ("master of" relation, hard coded load order, plugin masterlist rule)
• this edge is a default, you can change it but it may not be a good idea (masterlist group assignment, default group assignment)
• this edge is custom, you created/influenced it yourself, you can change it of course (userlist group assignment, userlist group rule, userlist plugin rule)

If it is a "required" edge, it will be interesting for the user why it's enforced, so the distinction "master of", "hard coded", "masterlist plugin rule" is important. I believe these tend to be very "direct" edges so they should be easy to understand (a is a master of b so b has to load after a, that's simple enough)

With "custom" edges, very frequently users don't realize what consequences their changes have and these can get very complicated, as you demonstrated. In the case of A.esp and C.esp we would be showing an edge between A.esp and C.esp as "userlist group" but the user hasn't done any customisation on either of those plugins and didn't assign a group to C. It's just not enough information for the user to understand how his adjustments caused this edge. To really give the user a chance to understand we'd have to say "C.esp is in group default, which you changed, it's now connected to group B and group B is connected to group A, of which A.esp is a part and that's why you now have an edge between A.esp and C.esp"

Imho the perfect way to show these edges to the user would be something like: A.esp@group A --> B.esp@group B A.esp@group A --> BB.esp@group B C.esp@group default --- via group B --> A.esp@group A B.esp@group B --> C.esp@group default BB.esp@group B --> C.esp@group default

with the bold text signifying which part the user customised in the userlist. The information about which group a plugin belongs to and whether the assignment or the group itself was changed in the userlist can all be provided by the UI, it doesn't have to be part of the CycleError. So as soon as an edge is "userlist group" I'd dig up the groups of the plugins involved, determine which of them was assigned via userlist or which has the load order changed via userlist and then add that info to the error message.

What would be very hard to figure out for the UI is the "via group B" part in the transitive edge though. Is there any change this information could be included in the "Vertex"?

[Ortham]

So as soon as an edge is "userlist group" I'd dig up the groups of the plugins involved, determine which of them was assigned via userlist or which has the load order changed via userlist and then add that info to the error message.

That works for this example, but what if changing group B's metadata caused a cycle between A.esp and C.esp, without changing either plugin's metadata or groups A and C? Then just looking at the user metadata for the affected plugins and their groups wouldn't be enough.

I think more generally you'd have to check the plugins and their groups, then walk the path between the two groups looking for any edges due to user metadata.

Given that EdgeType::masterlistGroup and EdgeType::userGroup don't given sufficient detail, I'd like to drop them in favour of a generic EdgeType::group, as it's much simpler to implement.

What would be very hard to figure out for the UI is the "via group B" part in the transitive edge though. Is there any change this information could be included in the "Vertex"?

I don't think there's anywhere good to provide the group path in the information provided by the CyclicInteractionError if the error is about a plugin graph cycle. Instead, I think having an API function that gives you the path between two groups, e.g. std::vector<Vertex> DatabaseInterface::GetGroupsPath(std::string fromGroupName, std::string toGroupName) should be good enough. The workflow with that would be something like:

1. Catch a CyclicInteractionError.
2. If the cycle is between groups, iterate over CyclicInteractionError::GetCycle() to get the group path. That gives you all necessary information.
3. If the cycle is between plugins, iterate over CyclicInteractionError::GetCycle() to get the plugin path. That gives you all necessary information, unless one or more of the EdgeTypes is group.
4. For an EdgeType::group, check if the plugins' groups are set in user metadata, the masterlist or implicit defaults
5. For an EdgeType::group, also use GetGroupsPath() to get the path from the earlier group to the later group, and check that path to see where the groups' load after metadata came from.

The logic for the iteration in steps 2 and 5 should be identical, which cuts down the complexity a bit.

[TanninOne]

Sounds good to me.

[Ortham]

I think it's also worth mentioning that the GetGroupsPath() described above would be limited to returning a single path between the given groups, when there could be multiple, e.g.

     +-> B ->-+
     |        |
A ->-+        +-> D
     |        |
     +-> C ->-+

It's possible to return all paths, but that's expensive to calculate, difficult to then display to the user (unless you draw the graph out) and probably not very useful. Instead, I'll return the shortest path, with edges weighted such that the preference will be to return the path that involves the fewest group while containing user metadata, and if there is no user metadata involved, just choose the path involving the fewest groups.

This might mean that:

1. a user gets a cycle error with a group path containing user metadata
2. they fix/remove the user metadata, then re-sort
3. they get the same error, with a longer group path containing user metadata
4. repeat steps 2 and 3 a few times
5. they get the same error with a group path containing only masterlist metadata
6. they complain/file an issue.

But I'd personally prefer having a loop like that over being shown a graph of several paths and being told to solve it. It might take longer over all, but it's less likely to be overwhelming. Not to mention that these are probably edge cases anyway.

EDIT: Though I say it's not nice to create or be given a visualised graph, that's what the LOOT UI does for the groups editor and that's fairly straightforward on both counts, so maybe all this detail is overkill...

@TanninOne What would you prefer, having an API function to get the shortest path, or to be left to your own devices?

[TanninOne]

Yes, I completely agree. Having several worksteps of manageable size is better than having one huge confusing error message where technically you might just have one step to fix it but much more likely you get confused.

Regarding the graph - I'm not sure. You do have a point that we could draw it as a graph and in many cases that would probably be nice but I'm not sure that would actually be easier to read than a textual representation. When you have a large cycle and each edge could have multiple paths and different edge types that we'd probably have to represent with color coding or something, that could probably end up one complex graph.

You said above that returning all paths would be expensive to calculate, otherwise I'd say: just return all paths and let the UI figure out which one is the shortest (that still contains user metadata). This gives UIs all the options. But you'd have to make the judgement call whether that's worth the added calculation time and development effort - personally I'll probably (at least initially) go for a textual description showing only the shortest path.

[Ortham]

Done as of 6264b8fa6d10101034e7122e78f348c1cbd2b483.