Is there a circular reference in a set of template substitutions?

I have a configuration engine that allows the user to specify a dictionary with text templates (read from a JSON file) where each placeholder like {x} can be substituted for a value found under a key with the same name e.g. x.

var constants = new Dictionary
{
    { "x", "foo {y} baz" },
    { "y", "bar {x} qux" },
};

These are just two sample strings to show how it can look like. The real configuration contains connection strings, email lists, user names, sql etc.

They are resolved at runtime with this method

public static string FormatAll(this string text, Dictionary values)
{
    while (text.ToString() != (text = text.Format(values))) ;
    return text;
}

where Format is a more advanced version of my question about string interpolation.

As you can probably see in the example, there is a danger that someone creates a circular template path and the formatting runs forever.

In order to prevent this from happening, I thought I validate the template dictionary before I let the formating method work with it. This is what I've come up with.

The ValidateIsNotCircular extension runs over the reference dictionary and checks each path for recursiveness and as soon as it finds one that is circular, it throws an exception that contains the path. I wanted it to work without recursion so I used a Stack.

Sidenote: This time I'm confined to C# < 6 so no fancy code here :-(

```
public static void ValidateIsNotCircular(this Dictionary> values)
{
var visitedKeys = new HashSet();

var stack = new Stack>>();

var currentRef = new Func(() => stack.Peek().Item2.Current);
var currentRefs = new Func>(() => stack.Peek().Item2);

foreach (var item in values)
{
if (!visitedKeys.Add(item.Key)) continue;

stack.Push(Tuple.Create(item.Key, item.Value.GetEnumerator()));
do
{
while (currentRefs().MoveNext())
{
if (stack.Any(x => currentRef() == x.Item1))

If you convert your dictionary into directed graph, you should be able to do a topological sorting. Kahn's algorithm works fairly well, and is easy to implement, especially if you drop all the stuff related to actual sorting.

static void ValidateIsNotCircular(Dictionary> dict)
{
    var edges = dict.SelectMany(x => x.Value.Select(y => Tuple.Create(x.Key, y))).ToList();
    var topLevelNodes = new Stack(dict.Keys.Where(n => !edges.Any(e => e.Item2.Equals(n))));

    while (topLevelNodes.Any())
    {
        var node = topLevelNodes.Pop();
        var outgoingEdges = edges.Where(e => e.Item1.Equals(node)).ToArray();
        foreach(var edge in outgoingEdges)
        {
            edges.Remove(edge);
            var childNode = edge.Item2;
            var childHasIncomingEdges = edges.Any(e => e.Item2.Equals(childNode));
            if (!childHasIncomingEdges)
            {
                topLevelNodes.Push(childNode);
            }
        }
    }

    if (edges.Any()) 
    {
        throw new CircularPathException(edges.Select(e => e.Item1).Distinct());
    } 
}

This way you don't have to deal with iterators.

StackExchange Code Review Q#156603, answer score: 6