Allow Users to Specify Update / Init Order of Components

[ilexp]

Summary

Currently, Components are updated by Type, but the actual order of the Types is non-deterministic. Instead, derive the update order from Component requirement attributes and consider allowing a user attribute for changing update order of certain Components globally or relative to each other.

Analysis

• This would help with some edge cases of Component init or update dependencies.
• See also: Component Init-By-Type

[Barsonax]

Unity has the script execution order: https://docs.unity3d.com/Manual/class-ScriptExecution.html. Maybe a idea?

[ilexp]

I think deriving init and update order via Component attributes (a specific one and a fallback based on component requirements) is a better solution for Duality, as it ties in nicely with existing patterns and structures and also keeps this behavior fixed to the actual types, rather than project settings.

[ilexp]

To clarify: I'm currently thinking of the RequiredComponent-derived update and init order more as a fallback for the initially mentioned explicit update order attribute. There are cases where you would want to specify update or init orders without actually requiring another component.

[Barsonax]

A attribute for update order sounds simple to understand and would solve most problems. It would be nice if this was just a default value which you can change if needed.

I think the requiredcomponent derived update is harder to understand and too complex while it only solves some cases.

[ilexp]

Note: Most of the grunt work for this will be making sure iteration order in groups of Components are deterministic at all - visit issue #303 for more info. This issue on the other hand will now specialize on how developers will be able to define and interact with the order that is used internally.

Issue #303: Make sure, there is a deterministic order at all.
Issue #304: Figure out which order to use and how developers are able to adjust it.

[ilexp]

Basics

• Introduce a new ExecutionOrder attribute that allows to specify to be executed before or after another component, which is referred to with a typeof statement.
• Do not allow any global ordering settings, such as a fixed index, or "last" / "first" exec orders, as this requires full knowledge of all components, which does not mix well with a plugin-oriented, modular environment like Duality.
• Use RequiredComponent as a second-class hint that is otherwise equivalent with requesting to execute after the required component type.
  • Only evaluate the actual requirement, not the "create default" option.
• When a requirement or execution order anchor is abstract or an interface, use it as a weak constraint generator for all matching component types.
• For resolving mutually exclusive constraints, there should be priorities derived from how exactly a constraint was defined. These priorities are internal only and will never be exposed to the user directly:
  • Explicit: Stated via ExecutionOrder attribute and referring to a concrete type.
  • ExplicitWeak: Stated via ExecutionOrder attribute and referring to an abstract type.
  • Implicit: Derived from RequiredComponent attribute and referring to a concrete type.
  • ImplicitWeak: Derived from RequiredComponent attribute and referring to an abstract type.

Algorithm

The algorithm can be described in five steps:

1. Gather constraints
2. Create a constraint graph
3. Resolve loops
4. Propagate sort indices
5. Extract scores

1. Gather constraints

• Gather all relevant attributes from the set of known components.
• Transform these attributes into a normalized list of constraints where every constraint follows the form "A before B", assigned with one of the priorities listed above.

2. Create a constraint graph

• Transform the list of constraints into connections of a graph where every known component type is a node. The normalized constraint list can probably remain unchanged for this.
• Prepare this "graph data" for fast access.

3. Resolve loops

• Detect loops in the graph using some graph algorithm (figure this out).
• Resolve loops by removing their lowest-priority connection until there are no more loops present.
• When removing that connection, use priority to determine whether or not to log a warning.

4. Propagate sort indices

• Every node starts with a score of zero.
• Start with the nodes with the least amount of incoming connections (should be zero when there are no loops).
• Traverse its connections and set every connected node's score to max(their.score, this.score + 1)
• Append each connected node to the schedule to traverse.
• Note that this traversal needs to be connection-focused, not node-focused. Traversing a node and the nodes it points to multiple times will be necessary.
• In the end, every node will have a score that corresponds to its sort index.

5. Extract scores

• Sort all components by their node's score in the graph.
• Assign sort indices based on each component's place in the sorted list.
• Note that these indices can change at runtime when new component types become known or loaded.

[ilexp]

Progress

• Implemented the above algorithm to derive component execution order from ExecutionOrderAttribute and RequiredComponentAttribute.
• Added tests to test whether the above attributes have the desired effect, as well as whether error cases (such as loops in the constraint graph) are handled correctly.

Immediate ToDo

• Wrap up issue Deterministic Component Init and Update Order #303

Closing this.