What is the best way to order methods based on a RunBefore attribute in C#

Question

As the title suggests, I'm looking for a way to arrange methods by their attribute values in such a way that they can always be processed before the method specified in an array.

class Program
{
    static void Main()
    {
        var classType = typeof(MethodsTest);
        var methods = classType.GetMethods()
            .Where(
                m => m.Name.StartsWith("Test")
            )
            .OrderBy(/* ??? */)
            .ToArray();
    }
}

class MethodsTest
{
    public void TestUnrelatedMethod() { }

    public void TestMethod() { }

    [RunBefore(nameof(TestMethod))]
    public void TestBeforeMethod() { }

    [RunBefore(nameof(TestBeforeMethod))]
    public void TestBeforeOther() { }
}

public class RunBeforeAttribute : Attribute
{
    public string methodName;
    public string callerName;

    public RunBeforeAttribute(string method, [CallerMemberName] string callerMember = null)
    {
        methodName = method;
        callerName = callerMember;
    }
}

As a result, the MethodInfo array should look like this:

TestBeforeOther
TestBeforeMethod
TestMethod
TestUnrelatedMethod

I'm currently standing here and don't know if this is the right way:

.OrderBy(
    m => m.GetCustomAttributes(typeof(RunBeforeAttribute), false).First(), 
    /* */ )
)

Answer 1

Based on @klaus-gütter comment about Topological Sort, also based on this article with a small modifications (c# 8/9) to make compiler not to trigger warnings:

<TargetFramework>net6.0</TargetFramework>

Added AttributeUsageAttribute to the RunBeforeAttribute

[AttributeUsage(AttributeTargets.Method, AllowMultiple = true)]
public class RunBeforeAttribute : Attribute
{
    public string methodName;
    public string? callerName;

    public RunBeforeAttribute(string method, [CallerMemberName] string? callerMember = null)
    {
        methodName =  method;
        callerName = callerMember;
    }
}

Test class (based on the schema on wiki):

class MethodsTest
{
    public void TestUnrelatedMethod() { }
    public void TestMethod() { }
    [RunBefore(nameof(Test11))]
    public void Test2() { }
    public void Test3() { }
    public void Test5() { }
    public void Test7() { }
    [RunBefore(nameof(Test7)), RunBefore(nameof(Test3))]
    public void Test8() { }
    [RunBefore(nameof(Test8)), RunBefore(nameof(Test11))]
    public void Test9() { }
    [RunBefore(nameof(Test11)), RunBefore(nameof(Test3))]
    public void Test10() { }
    [RunBefore(nameof(Test5)), RunBefore(nameof(Test7))]
    public void Test11() { }
}

Simple Node wrapper:

public class Node<T> where T : notnull
{
    public T Item { get; init; }
    public List<Node<T>> Dependencies { get; init; }

    public Node(T item)
    {
        Item = item;
        Dependencies = new();
    }
}

Topological sorter taken from the article mentioned above

public static class TopologicalSort
{
    public static IList<T> Sort<T>(IEnumerable<T> source, Func<T, IEnumerable<T>> getDependencies) where T : notnull
    {
        var sorted = new List<T>();
        var visited = new Dictionary<T, bool>();

        foreach (var item in source)
        {
            Visit(item, getDependencies, sorted, visited);
        }

        return sorted;
    }

    public static void Visit<T>(T item, Func<T, IEnumerable<T>> getDependencies, List<T> sorted, Dictionary<T, bool> visited) where T : notnull
    {
        var alreadyVisited = visited.TryGetValue(item, out bool inProcess);

        if (alreadyVisited)
        {
            if (inProcess)
            {
                throw new ArgumentException("Cyclic dependency found.");
            }
        }
        else
        {
            visited[item] = true;

            var dependencies = getDependencies(item);
            if (dependencies != null)
            {
                foreach (var dependency in dependencies)
                {
                    Visit(dependency, getDependencies, sorted, visited);
                }
            }

            visited[item] = false;
            sorted.Add(item);
        }
    }
}

Actual main code:

class Program
{
    static void Main()
    {
        var classType = typeof(MethodsTest);
        var methods = classType.GetMethods().Where(m => m.Name.StartsWith("Test")).ToList();
        var methodsWithAttributes = methods
            .Select(x =>
            {
                var runBeforeNames = x.GetCustomAttributes(typeof(RunBeforeAttribute), true)
                    .Select(x => (x as RunBeforeAttribute)?.methodName)
                    .Where(x => !string.IsNullOrWhiteSpace(x))
                    .Distinct()
                    .ToList();
                return new { methodInfo = x, runBeforeNames = runBeforeNames };
            })
            .ToList();
        var nodesUnsorted = methodsWithAttributes.Select(x => new Node<MethodInfo>(x.methodInfo)).ToList();

        nodesUnsorted.ForEach(x =>
        {
            var current = methodsWithAttributes.Single(z => z.methodInfo == x.Item);
            var dependencyNodes = nodesUnsorted.Where(z => current.runBeforeNames.Contains(z.Item.Name)).ToList();
            x.Dependencies.AddRange(dependencyNodes);
        });

        nodesUnsorted.ForEach(x => Console.WriteLine($"Node {x.Item.Name} <= {string.Join(", ", x.Dependencies.Select(z => z.Item.Name))}"));

        var sorted = TopologicalSort.Sort(nodesUnsorted, x => x.Dependencies).ToList();
        Console.WriteLine("Sorted: ");
        sorted.ForEach(x => Console.WriteLine($"Node {x.Item.Name}"));
    }
}

And the output:

Node TestUnrelatedMethod <=
Node TestMethod <=
Node Test2 <= Test11
Node Test3 <=
Node Test5 <=
Node Test7 <=
Node Test8 <= Test3, Test7
Node Test9 <= Test8, Test11
Node Test10 <= Test3, Test11
Node Test11 <= Test5, Test7
Sorted:
Node TestUnrelatedMethod
Node TestMethod
Node Test5
Node Test7
Node Test11
Node Test2
Node Test3
Node Test8
Node Test9
Node Test10