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

Question

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<string, object>
{
    { "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<string, object> 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<string, IEnumerable<string>> values)
{
    var visitedKeys = new HashSet<string>();

    var stack = new Stack<Tuple<string, IEnumerator<string>>>();

    var currentRef = new Func<string>(() => stack.Peek().Item2.Current);
    var currentRefs = new Func<IEnumerator<string>>(() => 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))
                {
                    throw new CircularPathException(stack.Select(x => x.Item1));
                }

                var next = values[currentRef()];
                visitedKeys.Add(currentRef());
                stack.Push(Tuple.Create(currentRef(), next.GetEnumerator()));
            }
            stack.Pop();
        } while (stack.Any());
    }
}

class CircularPathException : Exception
{
    public CircularPathException(IEnumerable<string> path)
        : base(string.Format("Circular path [{0}]!", string.Join(", ", path.Reverse().Select(x => string.Format("'{0}'", x)))))
    { }
}

There is one more method that extracts the placeholders {x} from the templates and builds another dictionary with references (not part of the question), that looks like this:

var values = new Dictionary<string, IEnumerable<string>>
{
    { "c", new string[] {  } },
    { "x", new string[] { "y" } },
    { "y", new string[] { "c", "z" } },
    //{ "y", new string[] { "c", } },
    { "z", new string[] { "x" } },
};

I use this new dictionary to validate the paths:

values.ValidateIsNotCircular();

and this throws (by design):

CircularPathException: "Circular path ['x', 'y', 'z']!"

Answer 1

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<string, IEnumerable<string>> dict)
{
    var edges = dict.SelectMany(x => x.Value.Select(y => Tuple.Create(x.Key, y))).ToList();
    var topLevelNodes = new Stack<string>(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.

Answer 2

This is a great solution @NikitaB. I changed only one thing where I flipped the condition from

!edges.Any(e => e.Item2.Equals(n))

to

edges.All(e => !e.Item2.Equals(n))

---

It turns out that the sorting has its usefulness too so I added it after all and use it to validate whether all nodes have been defined. Now I can be sure that the template/placeholder graph is not circular and nothing is missing.

I added a few comments while I was trying to get at the bottom its logic ;-)

public static void ValidateIsNotCircular2(Dictionary<string, IEnumerable<string>> dict)
{
    // Convert dictionary into directed graph.
    var edges = new HashSet<Tuple<string, string>>(dict.SelectMany(x => x.Value.Select(y => Tuple.Create(x.Key, y))));
    var sorted = new List<string>();

    //First, find a list of "start nodes" which have no incoming edges and insert them into a set S;
    // at least one such node must exist in a non-empty acyclic graph.
    var startNodes = dict.Keys.Where(n => edges.All(e => !e.Item2.Equals(n)));
    var topLevelNodes = new Stack<string>(startNodes);

    while (topLevelNodes.Any())
    {
        var node = topLevelNodes.Pop();
        sorted.Add(node);
        var outgoingEdges = edges.Where(e => e.Item1.Equals(node)).ToList();
        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());
    }

    var missingNodes = sorted.Where(node => !dict.ContainsKey(node)).ToList();
    if (missingNodes.Any())
    {
        throw new MissingNamesException(missingNodes);
    }
}

and the new exception:

class MissingNamesException : Exception
{
    public MissingNamesException(IEnumerable<string> names)
        : base(string.Format("Missing names [{0}]!", string.Join(", ", names.Select(x => string.Format("'{0}'", x)))))
    { }
}