[BUG] Dependency ordered is incorrect

[breriksenms]

Existing rule

No response

Description of the issue

The algorithm that is being used to sort the resources in a deployment is a simple array sort with a custom IComparer.

namespace PSRule.Rules.Azure
{
    internal sealed class ResourceDependencyComparer : IComparer<IResourceValue>
    {
        public int Compare(IResourceValue x, IResourceValue y)
        {
            if (x.DependsOn(y, out var xc))
                return 1;

            if (y.DependsOn(x, out var yc))
                return -1;

            if (xc == 0 && yc == 0)
                return 0;

            if (yc == 0) return 1;
            if (xc == 0) return -1;

            return 0;

            //return xc == 0 && yc == 0 ? 0 : yc == 0 || yc > 0 ? -1 : 1;
        }
    }
}

This can lead to issues in some templates, because once the algorithm finds that 2 elements are of equal order, then their positions can become set without traversing the rest of the elements in the array to find if dependencies exist.

The correct algorithm to use is some sort of topological sort on a graph of the resources as nodes and their dependencies as vertices.

Error messages

No response

Reproduction

repro.zip

The test.bicep template in the zip file runs into the sorting issue. It sorts the subnet3 resource after the dep_subnet3_1 resource even though dep_subnet3_1 depends on subnet3.

Version of PSRule

2.9.0

Version of PSRule for Azure

1.31.3

Additional context

No response

[BernieWhite]

@breriksenms Thanks for reporting the issue.