Order GetAttributes returns attributes is not deterministic

[YairHalberstadt]

Version Used: VS 16.8 preview 1

Steps to Reproduce:

Create a compilation containing the following code:

public class GenerateAttribute : System.Attribute
{
    public GenerateAttribute (string name) => Name = name;
    public string Name { get; }
}
[Generate("a")]
[Generate("b")]
public partial class A
{
}

then call GetAttributes on the type symbol for A.

Recreate the compilation and repeat.

Sometimes it will return [Generate("a")] first and then [Generate("b")] and sometimes the other way round.

Impact on Source Generators

This has a significant adverse affect on deterministic output of source generators, which are often attribute driven. For example, let's say Generate is used by a source generator to create fields. Then sometimes the generator will generate:

public partial class A
{
    public string a;
    public string b;
}

And sometimes it will generate:

public partial class A
{
    public string b;
    public string a;
}

In practice this non-determinism is causing unit test failures in my StrongInject source generator: https://github.com/YairHalberstadt/stronginject/runs/999682771

Whilst attributes are unordered, and therefore the order of the attributes can be arbitrary, it should be deterministic between runs.

[CyrusNajmabadi]

As attributes have no way to go back to source (or from source to data), i don't see any way for @YairHalberstadt to be able to enumerate these in a consistent order. Tagging @jasonmalinowski @chsienki for visibility here.

Ignore this. AttributeData has ApplicationSyntaxReference that can be used to get back to syntax for ordering purposes.

[YairHalberstadt]

This is the code I'm using to order attributes that are defined in metadata:

        private class AttributeComparer : IComparer<AttributeData>
        {
            private AttributeComparer() { }

            public static AttributeComparer Instance = new();
            public int Compare(AttributeData x, AttributeData y)
            {
                Debug.Assert(
                    x.AttributeClass is { ContainingNamespace: { Name: "StrongInject" } }
                    && y.AttributeClass is { ContainingNamespace: { Name: "StrongInject" } });

                var compareClass = string.CompareOrdinal(x.AttributeClass?.Name, y.AttributeClass?.Name);
                if (compareClass != 0)
                    return compareClass;

                return CompareArrays(x.ConstructorArguments, y.ConstructorArguments);
            }

            private static int CompareArrays(ImmutableArray<TypedConstant> arrayX, ImmutableArray<TypedConstant> arrayY)
            {
                var compareLength = arrayX.Length.CompareTo(arrayY.Length);
                if (compareLength != 0)
                    return compareLength;

                for (var i = 0; i < arrayX.Length; i++)
                {
                    var argX = arrayX[i];
                    var argY = arrayY[i];

                    var compareKinds = argX.Kind.CompareTo(argY.Kind);
                    if (compareKinds != 0)
                        return compareKinds;

                    if (argX.Kind != TypedConstantKind.Enum)
                    {
                        var compareTypes = string.CompareOrdinal(argX.Type?.Name, argY.Type?.Name);
                        if (compareTypes != 0)
                            return compareTypes;
                    }
                    else
                    {
                        var compareTypes = CompareTypes(argX.Type!, argY.Type!);
                        if (compareTypes != 0)
                            return compareTypes;
                    }

                    var compareIsNull = argX.IsNull.CompareTo(argY.IsNull);
                    if (compareIsNull != 0)
                        return compareIsNull;

                    var compareValues = argX.Kind switch
                    {
                        TypedConstantKind.Primitive or TypedConstantKind.Enum => argX.Value is string
                            ? StringComparer.Ordinal.Compare(argX.Value, argY.Value)
                            : Comparer.Default.Compare(argX.Value, argY.Value),
                        TypedConstantKind.Error => 0,
                        TypedConstantKind.Type => CompareTypes((ITypeSymbol)argX.Value!, (ITypeSymbol)argY.Value!),
                        TypedConstantKind.Array => CompareArrays(argX.Values, argY.Values),
                        _ => throw new InvalidOperationException("This location is thought to be impossible"),
                    };
                    if (compareValues != 0)
                        return compareValues;
                }

                return 0;
            }

            private static int CompareTypes(ITypeSymbol typeX, ITypeSymbol typeY)
            {
                var compareTypeNames = string.CompareOrdinal(typeX.Name, typeY.Name);
                if (compareTypeNames != 0)
                    return compareTypeNames;

                var namespaceX = typeX.ContainingNamespace;
                var namespaceY = typeY.ContainingNamespace;

                while (!namespaceX.IsGlobalNamespace && !namespaceY.IsGlobalNamespace)
                {
                    var compareNamespaces = string.CompareOrdinal(namespaceX.Name, namespaceY.Name);
                    if (compareNamespaces != 0)
                        return compareNamespaces;

                    namespaceX = namespaceX.ContainingNamespace;
                    namespaceY = namespaceY.ContainingNamespace;
                }

                return namespaceX.IsGlobalNamespace.CompareTo(namespaceY.IsGlobalNamespace);
            }
        }
    }

As you can see it's long, non-trivial, and expensive.

Having this in roslyn would provide a number of benefits:

1. Roslyn could do this much more cheaply as it has access to metadata order, and so could sort by that.
2. This wouldn't have to be duplicated/reinvented in multiple libraries.
3. Attribute order would be deterministic by default, meaning a source generator wont ship, and only then people realize there's bugs where the source generator is non-deterministic.