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']!"