Search Unity

Showcase How to automatically generate a working script execution order

Discussion in 'Scripting' started by FeXseven, Jan 14, 2024.

  1. FeXseven

    FeXseven

    Joined:
    Feb 13, 2016
    Posts:
    16
    I guess we all know the stuggles of finding a correct order for our scripts.
    With larger projects and larger dependencies, finding a good order is getting increasingly difficult.
    Of course, avoiding dependencies between scripts should be avoided as far as possible, but sometimes it is not entirely possible.

    So I worked on a simple solution to automate that process. Maybe I can help some of you with my approach or maybe you have some further ideas to improve it!

    How to
    1. Create an attribute that marks a class to be considered within your script execution order:
      Code (CSharp):
      1. [AttributeUsage(AttributeTargets.Class, AllowMultiple = true)]
      2. public class ExecutionDependsOnAttribute : Attribute
      3. {
      4.     public ExecutionDependsOnAttribute(Type type)
      5.     {
      6.         Type = type;
      7.     }
      8.  
      9.     public Type Type { get; }
      10. }
    2. Now, create an editor extension to order the executions based on that attribute:

      Code (CSharp):
      1. [MenuItem("My cool custom tools/Reorder Executions")]
      2. public static void ReOrder()
      3. {
      4.     var classToMonoScript = new Dictionary<Type, MonoScript>();
      5.  
      6.     MonoImporter.GetAllRuntimeMonoScripts()
      7.         .Where(script => script.GetClass() != null) // not all scripts have classes
      8.         .ToList()
      9.         .ForEach(script => classToMonoScript.TryAdd(script.GetClass(), script));
      10.  
      11.     // list of classes that have a dependency to at least one other class
      12.     var dependingClasses = classToMonoScript.Keys
      13.         .Where(script =>
      14.             Attribute.GetCustomAttributes(script, typeof(ExecutionDependsOnAttribute)).Any()
      15.         )
      16.         .ToList();
      17.  
      18.     // Build graph. classToDependency is the actual class while dependencyToClass is more like a look-up for backwards checks
      19.     var classToDependency = new Dictionary<Type, HashSet<Type>>();
      20.     var dependencyToClass = new Dictionary<Type, HashSet<Type>>();
      21.     foreach (var dependingClass in dependingClasses)
      22.     {
      23.         // this holds all dependency information
      24.         var attributes = dependingClass.GetCustomAttributes<ExecutionDependsOnAttribute>();
      25.         classToDependency[dependingClass] = new HashSet<Type>();
      26.        
      27.         // add backwards look-up if not already done
      28.         if (!dependencyToClass.ContainsKey(dependingClass))
      29.             dependencyToClass.Add(dependingClass, new HashSet<Type>());
      30.        
      31.         foreach (var attribute in attributes)
      32.             classToDependency[dependingClass].Add(attribute.Type);
      33.        
      34.         foreach (var dependency in classToDependency[dependingClass])
      35.         {
      36.             if (!dependencyToClass.ContainsKey(dependency))
      37.                 dependencyToClass[dependency] = new HashSet<Type>();
      38.             dependencyToClass[dependency].Add(dependingClass);
      39.             if (!classToDependency.ContainsKey(dependency))
      40.                 classToDependency.Add(dependency, new HashSet<Type>());
      41.         }
      42.     }
      43.  
      44.     // now the graph is build. Let's find the order
      45.     var executionOrder = new List<Type>(classToDependency.Count);
      46.     while (classToDependency.Count > 0)
      47.     {
      48.         // find class without unresolved dependency
      49.         var classWithoutDependency =
      50.             classToDependency.Keys.FirstOrDefault(key => classToDependency[key].Count == 0);
      51.        
      52.         if (classWithoutDependency == null)
      53.             throw new ArgumentException("Could not resolve dependency graph! You might have a loop somewhere");
      54.  
      55.         executionOrder.Add(classWithoutDependency);
      56.         foreach (var dependingClass in dependencyToClass[classWithoutDependency])
      57.             classToDependency[dependingClass].Remove(classWithoutDependency);
      58.  
      59.         classToDependency.Remove(classWithoutDependency);
      60.     }
      61.    
      62.     Debug.Log("Setting new execution order:");
      63.     for (var index = 0; index < executionOrder.Count; index++)
      64.     {
      65.         var type = executionOrder[index];
      66.         var monoScript = classToMonoScript[type];
      67.         var currentOrder = MonoImporter.GetExecutionOrder(monoScript);
      68.         var newOrder = index - executionOrder.Count;
      69.         if (currentOrder != newOrder)
      70.             MonoImporter.SetExecutionOrder(monoScript, newOrder);
      71.         Debug.Log($"{newOrder} -- {type.Name}");
      72.     }
      73. }
    3. Now, in the editor, there will be a new tab:
      upload_2024-1-14_11-17-45.png

    How does this work

    Dependencies usually behave like a directed graph where each class can be represented by a node and each dependency from one class to another is represented by an edge from one node to another.
    Take this simple example:
    Code (CSharp):
    1. [ExecutionDependsOn(typeof(ClassB))]
    2. [ExecutionDependsOn(typeof(ClassC))]
    3. class ClassA {}
    4.  
    5. [ExecutionDependsOn(typeof(ClassC))]
    6. class ClassB {}
    7.  
    8. class ClassC {}
    9.  
    upload_2024-1-14_11-27-20.png

    Class A depends on Class B and Class C while Class B also depends on Class C.
    We want a class to be executed after all its dependencies have been executed. So we want to find a path in our graph so that each node will be visited after its adjacent nodes have been visited.
    In our example, we want the order: C, B, A.
    We now flip all our edges:
    upload_2024-1-14_11-29-12.png
    Now, each node points to other nodes that depend on it. Now we can easily see that Class C has no dependencies because the corresponding node has no incoming edges. We know, Class C must be the first node to be executed!
    We remove Class C from our graph:
    upload_2024-1-14_11-31-33.png
    Now, Class B does not have incoming edges because it has no (unresolved) dependencies. Class B must be the next one in order and we remove it as well, leaving us only with class A which is the last class to be executed. We now have found our order!

    Note that if our graph contains a loop (circular dependency), at some time there will be no nodes without incoming edges. Then the dependencies cannot be resolved and an error is thrown.

    Limitations
    1. You cannot automate the dependency graph on builtin classes because you cannot change their source code. However one could create a second attribute like [DependingClass(X)] to not mark the annotated class as depending of X but rather that X depends on the annotated class
    2. Explicitly calling the reoder-function by toolbar was an explicit choice because changing the execution order recompiles your code. You do not want to do this everytime you change something. One could listen to code changes and automatically reorder the code only when an [ExecutionDependsOn]-Attribute has been added, changed or removed though.

    I hope this helps some of you :)
    If you have any improvements for it or problems using the code, let me know!
     

    Attached Files:

    Last edited: Jan 14, 2024
    icauroboros, Nad_B and tsukimi like this.
  2. CodeSmile

    CodeSmile

    Joined:
    Apr 10, 2014
    Posts:
    5,892
    First I like to applaud the effort but then I have to argue against that statement. It is always possible unless you have two independent systems of which you have no control over (ie 3rd party DLL assets) where you may be forced to resolve an issue with script execution order.

    But in your own code base it is always possible to avoid this - provided you are ready to refactor accordingly and more so if you did architecture the game code according to best practices. Execution order can be a quick fix to avoid refactoring a whole lot of the game code where not enough care had been taken to avoid temporal dependencies.
     
    Nad_B likes this.