Fast, generic, string template pre-processor for templates with variables

Template.cs

public static class Template
{
	public struct Span<T>
	{
		/// <summary>If Literal is not null it should be used and Variable should be ignored</summary>
		public readonly string Literal;
		/// <summary>Variable should only be used if Literal is null</summary>
		public readonly T Variable;
		
		public Span(string literal, T value)
		{
			Literal = literal;
			Variable = value;
		}
		
		/// <summary>Return true and append to StringBuilder if literal is non-null, return false and out alternative if literal is null</summary>
		public bool TryAppendLiteral(StringBuilder sb, out T variable)
		{
			var literal = Literal;
			if (literal != null)
			{
				sb.Append(literal);
				variable = default(T);
				return true;
			}
			
			variable = Variable;
			return false;
		}
	}
	
	private struct Substring<T>
	{
		public int Index;
		public int Count;
		public T Value;
		
		public void GetSpan(string source, out Span<T> span)
		{
			var count = Count;
			if (count > 0)
			{
				span = new Span<T>(source.Substring(Index, count), default(T));
			}
			else
			{
				span = new Span<T>(null, Value);
			}
		}
	}
	
	private static LinkedListNode<T> Node<T>(T value)
	{
		return new LinkedListNode<T>(value);
	}
	
	private static void Split<T>(string source, LinkedList<Substring<T>> nodes, KeyValuePair<string, T> variable)
	{
		var node = nodes.First;
		while (node != null)
		{
			var value = node.Value;

			while (value.Count > 0)
			{
				int index = source.IndexOf(variable.Key, value.Index, value.Count, StringComparison.Ordinal);
				if (index < 0) break;
				
				// match end
				int originalEnd = value.Index + value.Count;
				if (index == originalEnd - variable.Key.Length)
				{
					int stringNodeLength = index - value.Index;
					if (stringNodeLength > 0)
					{
						// insert string node before
						nodes.AddBefore(node, Node(new Substring<T> { Index = value.Index, Count = stringNodeLength }));
					}
					
					// change current to value node
					value.Value = variable.Value;
					value.Count = 0;
					node.Value = value; // mutable struct
					
					break; // match at end, done with current node
				}
				
				// match mid
				if (index > value.Index)
				{
					// insert string node
					nodes.AddBefore(node, Node(new Substring<T> { Index = value.Index, Count = index - value.Index }));
				}
				
				// match start or match mid
				
				// insert value node
				nodes.AddBefore(node, Node(new Substring<T> { Value = variable.Value }));
				
				// shift current node index
				value.Index = index + variable.Key.Length;
				value.Count = originalEnd - value.Index;
				
				node.Value = value; // mutable struct
			}
		
			node = node.Next;
		}
	}
	
	public static Span<T>[] Prepare<T>(string template, IEnumerable<KeyValuePair<string, T>> variables)
	{
		var list = new LinkedList<Substring<T>>();
		list.AddFirst(new Substring<T> { Index = 0, Count = template.Length });
		foreach (var kvp in variables)
		{
			Split(template, list, kvp);
		}
		
		var result = new Span<T>[list.Count];
		int index = 0;
		var node = list.First;
		while (node != null)
		{
			Span<T> span;
			node.Value.GetSpan(template, out span);
			result[index++] = span;
			node = node.Next;
		}
		return result;
	}
}

Usage.cs

// prepare template one time
// *any* type can be used rather than int: an enum, delegate, model, POCO, etc.
var template = Template.Prepare("$foo$ $bar$", new Dictionary<string, int>
{
	{ "$foo$", 1 },
	{ "$bar$", 2 },
});


// use the template many, many times
var result = new StringBuilder();
foreach (var span in template)
{
	int variable;
	if (span.TryAppendLiteral(result, out variable)) continue;
	
	// directly use string builder as appropriate for variable
	result.Append(variable * variable);
}

result.ToString(); // 1 4