Regex and Faster

PerformanceResults.md

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000 Intel Core i5-1035G4 CPU 1.10GHz, 1 CPU, 8 logical and 4 physical cores .NET SDK=7.0.100-alpha.1.22053.1 [Host] : .NET 7.0.0 (7.0.21.63101), X64 RyuJIT DefaultJob : .NET 7.0.0 (7.0.21.63101), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Allocated
Solution0	7,494.9 ns	298.81 ns	866.91 ns	3.6850	11 KB
Solution1	24,029.0 ns	763.83 ns	2,252.18 ns	8.4381	26 KB
Solution2	1,681.4 ns	79.69 ns	234.97 ns	0.8831	3 KB
Solution3	1,047.4 ns	12.76 ns	11.94 ns	0.8831	3 KB
Solution4	540.8 ns	10.81 ns	10.62 ns	1.0071	3 KB
Solution5	360.4 ns	7.13 ns	9.99 ns	0.3490	1 KB
Solution6	387.4 ns	7.29 ns	7.16 ns	0.3490	1 KB
Solution7	336.2 ns	6.55 ns	9.18 ns	0.3490	1 KB

Method	Mean	Error	StdDev	Gen 0	Allocated
Recursive0	17.27 us	0.340 us	0.631 us	9.2773	28 KB

Method	Mean	Error	StdDev	Gen 0	Allocated
Recursive7	340.7 ns	6.83 ns	8.88 ns	0.3543	1 KB
Recursive7Map	3,710.2 ns	73.60 ns	103.18 ns	20.8321	65 KB

Recursive0.cs

using System.Text.RegularExpressions;

public class Recursive0
{
    public string Substitute(string replacement, IReadOnlyDictionary<string, string> map) => SubstituteImpl(replacement, map, new HashSet<string>());

    public string SubstituteImpl(string replacement, IReadOnlyDictionary<string, string> map, HashSet<string> visited)
    {
        var regex = new Regex("\\[%[a-z|A-Z|_]*%\\]");
        string result = replacement;
        foreach (Match match in regex.Matches(replacement))
        {
            if (match.Success && map.ContainsKey(match.Value) && !visited.Contains(match.Value))
            {
                visited.Add(match.Value);
                result = result.Replace(match.Value, SubstituteImpl(map[match.Value], map, visited));
                visited.Remove(match.Value);
            }
        }
        return result;
    }
}

Recursive7.cs

using System.Buffers;
using System.Runtime.CompilerServices;

public class Recursive7
{
    private readonly Dictionary<int, string> _map;
    private readonly int _sizeDifference;
    private char[] _bufferPool;

    public Recursive7(IReadOnlyDictionary<string, string> map)
    {
        _map = new(map.Count);
        int totalSize = 0;
        foreach (var item in map)
        {
            var keyHash = string.GetHashCode(item.Key.AsSpan());
            _map.Add(keyHash, item.Value);
            totalSize += item.Value.Length;
        }
        _bufferPool = new char[4096 * 8];
        (_map, _sizeDifference) = ProcessInnerReplacements(_map, totalSize);
    }

    private (Dictionary<int, string>, int) ProcessInnerReplacements(IReadOnlyDictionary<int, string> map, int totalSize)
    {
        int newTotalSize = 0;
        var result = new Dictionary<int, string>(map.Count);
        var data = ArrayPool<char>.Shared.Rent(totalSize);
        var visited = new HashSet<int>();
        foreach (var mapEntry in map)
        {
            result.Add(mapEntry.Key, mapEntry.Value);
            visited.Clear();
            visited.Add(mapEntry.Key);
            var buffer = data.AsSpan();

            int length = UpdateEntry(buffer, mapEntry.Value, map, visited);
            newTotalSize += length;
            result[mapEntry.Key] = buffer.Slice(0, length).ToString();
        }
        ArrayPool<char>.Shared.Return(data);
        return (result, newTotalSize);
    }

    [SkipLocalsInit]
    private int UpdateEntry(Span<char> buffer, ReadOnlySpan<char> value, IReadOnlyDictionary<int, string> map, HashSet<int> visited)
    {
        if (!ShouldUpdate(value, visited, out var section, out var substitute, out int hashKey))
        {
            value.CopyTo(buffer);
            return value.Length;
        }

        value.Slice(0, section.Start.Value).CopyTo(buffer);
        buffer = buffer.Slice(section.Start.Value);

        visited.Add(hashKey);
        int length = UpdateEntry(buffer, substitute, map, visited);
        buffer = buffer.Slice(length);
        visited.Remove(hashKey);

        var endSection = value.Slice(section.End.Value);
        int endLength = UpdateEntry(buffer, endSection, map, visited);

        return section.Start.Value + length + endLength;
    }

    [SkipLocalsInit]
    private bool ShouldUpdate(ReadOnlySpan<char> section, HashSet<int> visited, out Range match, out string substitute, out int hashKey)
    {
        hashKey = 0;
        match = new Range(0, 0);
        substitute = string.Empty;
        if (!FindSectionStart(section, out var matchedSection))
            return false;

        var endSection = section.Slice(matchedSection.Length);
        if (!FindEndSection(endSection, out var matchedEndSection))
            return false;

        hashKey = string.GetHashCode(matchedEndSection);
        if (!_map.TryGetValue(hashKey, out substitute) || visited.Contains(hashKey))
            return false;

        match = new Range(matchedSection.Length, matchedEndSection.Length + matchedSection.Length);
        return true;
    }

    [SkipLocalsInit]
    public string Substitute(ReadOnlySpan<char> replacement)
    {
        if (replacement.Length + _sizeDifference > _bufferPool.Length)
            _bufferPool = new char[Math.Max(_bufferPool.Length * 2, replacement.Length + _sizeDifference)];

        var destination = _bufferPool.AsSpan();
        var section = replacement;
        while (section.Length > 0)
        {
            var hasSections = FindSectionStart(section, out var matchedSection);
            matchedSection.CopyTo(destination);
            destination = destination.Slice(matchedSection.Length);
            if (!hasSections)
                break;

            var endSection = section.Slice(matchedSection.Length);
            bool hasMatch = FindEndSection(endSection, out matchedSection);
            if (!hasMatch)
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
                section = endSection.Slice(matchedSection.Length);
                continue;
            }

            // if matched, check if section matches an entry of the map
            var hashKey = string.GetHashCode(matchedSection);
            if (_map.TryGetValue(hashKey, out var subsitute))
            {
                subsitute.CopyTo(destination);
                destination = destination.Slice(subsitute.Length);
            }
            else
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
            }

            section = endSection.Slice(matchedSection.Length);
        }
        var result = new string(_bufferPool.AsSpan(0, _bufferPool.Length - destination.Length));
        return result;
    }

    [SkipLocalsInit]
    private bool FindSectionStart(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var openBrackets = input.IndexOf('[');
        if (openBrackets == -1 || openBrackets >= input.Length || input[openBrackets + 1] != '%')
            return false;

        result = input.Slice(0, openBrackets);
        return true;
    }

    [SkipLocalsInit]
    private bool FindEndSection(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var remainder = input.Slice(2);
        var index = remainder.IndexOfAny('[', ']');
        if (index == -1)
            return false;
        bool isOpen = remainder[index] == '[';
        if (isOpen)
        {
            result = input.Slice(0, index - 1 + 2);
            return false;
        }

        if (input[index - 1 + 2] != '%')
        {
            result = input.Slice(0, index + 1 + 2);
            return false;
        }
        result = input.Slice(0, index + 1 + 2);
        return true;
    }
}

Solution0.cs

using System.Text.RegularExpressions;

public class Solution0
{
    public string Substitute(string replacement, IReadOnlyDictionary<string, string> map)
    {
        var regex = new Regex("\\[%[a-z|A-Z|_]*%\\]");
        string result = replacement;
        foreach (Match match in regex.Matches(replacement))
        {
            if (match.Success && map.ContainsKey(match.Value))
            {
                result = result.Replace(match.Value, map[match.Value]);
            }
        }
        return result;
    }
}

Solution1.cs

using System.Text.RegularExpressions;

public class Solution1
{
    public string Substitute(string replacement, IReadOnlyDictionary<string, string> map, int start = 0)
    {
        var regex = new Regex("\\[%[a-z|A-Z|_]*%\\]");
        var previousReplacement = replacement;
        replacement = regex.Replace(replacement, match => FindReplacement(match, map, ref start), 1, start);
        if (previousReplacement == replacement)
            return replacement;
        return Substitute(replacement, map, start);
    }

    string FindReplacement(Match match, IReadOnlyDictionary<string, string> map,  ref int start)
    {
        if (match.Success && map.ContainsKey(match.Value))
        {
            string replacement = map[match.Value];
            start = match.Index + replacement.Length;
            return replacement;
        }
        return match.Value;
    }
}

Solution2.cs

using System.Text.RegularExpressions;

/// <summary>
/// Move regex to a readonly field. Replace recursion with a while loop. Simplify map access.
/// </summary>
public class Solution2
{
    private readonly IReadOnlyDictionary<string, string> _map;
    private readonly Regex _regex;

    public Solution2(IReadOnlyDictionary<string, string> map)
    {
        _map = map;
        _regex = new Regex("\\[%[a-z|A-Z|_]*%\\]", RegexOptions.Compiled);
    }

    public string Substitute(string replacement)
    {
        string previousReplacement = string.Empty;
        previousReplacement = replacement;
        replacement = _regex.Replace(replacement, FindReplacement);
        return replacement;
    }

    private string FindReplacement(Match match)
    {
        if (match.Success && _map.TryGetValue(match.Value, out var replacement))
            return replacement;
        return match.Value;
    }
}

Solution3.cs

using System.Text.RegularExpressions;

public partial class Solution3
{
    private readonly IReadOnlyDictionary<string, string> _map;

    [RegexGenerator("\\[%[a-z|A-Z|_]*%\\]", RegexOptions.Compiled)]
    private static partial Regex GetRegex();

    public Solution3(IReadOnlyDictionary<string, string> map)
    {
        _map = map;
    }

    public string Substitute(string replacement)
    {
        string previousReplacement = string.Empty;
        previousReplacement = replacement;
        replacement = GetRegex().Replace(replacement, FindReplacement);
        return replacement;
    }

    private string FindReplacement(Match match)
    {
        if (match.Success && _map.TryGetValue(match.Value, out var replacement))
            return replacement;
        return match.Value;
    }
}

Solution4.cs

using System.Text;

public class Solution4
{
    private readonly Dictionary<int, string> _map;

    private readonly int Size;

    public Solution4(IReadOnlyDictionary<string, string> map)
    {
        _map = new(map.Count);
        foreach (var item in map)
        {
            var keyHash = string.GetHashCode(item.Key.AsSpan());
            _map.Add(keyHash, item.Value);
            Size += -item.Value.Length + item.Value.Length;
        }
    }

    public string Substitute(string replacement)
    {
        var sb = new StringBuilder(replacement.Length + Size);
        
        var section = replacement.AsSpan();
        while (section.Length > 0)
        {
            var hasSections = FindSectionStart(section, out var matchedSection);
            sb.Append(matchedSection);
            if (!hasSections)
                break;

            var endSection = section.Slice(matchedSection.Length);
            bool hasMatch = FindEndSection(endSection, out matchedSection);
            if (!hasMatch)
            {
                sb.Append(matchedSection);
                section = endSection.Slice(matchedSection.Length);
                continue;
            }

            // if matched, check if section matches an entry of the map
            bool hasSubstitute = _map.TryGetValue(string.GetHashCode(matchedSection), out var subsitute);
            sb.Append(hasSubstitute ? subsitute.AsSpan() : matchedSection);
            section = endSection.Slice(matchedSection.Length);
        }

        return sb.ToString();
    }

    private bool FindSectionStart(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var openBrackets = input.IndexOf("[%");
        if (openBrackets == -1)
            return false;

        result = input.Slice(0, openBrackets);
        return true;
    }

    private bool FindEndSection(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var remainder = input.Slice(2);
        var index = remainder.IndexOfAny('[', ']');
        if (index == -1)
            return false;
        bool isOpen = remainder[index] == '[';
        if (isOpen)
        {
            result = input.Slice(0, index - 1 + 2);
            return false;
        }

        if (input[index - 1 + 2] != '%')
        {
            result = input.Slice(0, index + 1 + 2);
            return false;
        }
        result = input.Slice(0, index + 1 + 2);
        return true;
    }
}

Solution5.cs

using System.Buffers;

public class Solution5
{
    private readonly Dictionary<int, string> _map;

    private readonly int _size;
    private readonly ArrayPool<char> _bufferPool;

    public Solution5(IReadOnlyDictionary<string, string> map)
    {
        _map = new(map.Count);
        foreach (var item in map)
        {
            var keyHash = string.GetHashCode(item.Key.AsSpan());
            _map.Add(keyHash, item.Value);
            _size += Math.Abs(item.Key.Length - item.Value.Length);
        }
        _bufferPool = ArrayPool<char>.Create(4096 * 8, 1);
    }

    public string Substitute(string replacement)
    {
        var buffer = _bufferPool.Rent(replacement.Length + _size);
        var destination = buffer.AsSpan();
        var section = replacement.AsSpan();
        while (section.Length > 0)
        {
            var hasSections = FindSectionStart(section, out var matchedSection);
            matchedSection.CopyTo(destination);
            destination = destination.Slice(matchedSection.Length);
            if (!hasSections)
                break;

            var endSection = section.Slice(matchedSection.Length);
            bool hasMatch = FindEndSection(endSection, out matchedSection);
            if (!hasMatch)
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
                section = endSection.Slice(matchedSection.Length);
                continue;
            }

            // if matched, check if section matches an entry of the map
            if (_map.TryGetValue(string.GetHashCode(matchedSection), out var subsitute))
            {
                subsitute.CopyTo(destination);
                destination = destination.Slice(subsitute.Length);
            }
            else
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
            }

            section = endSection.Slice(matchedSection.Length);
        }
        var result = new string(buffer.AsSpan(0, buffer.Length - destination.Length));
        _bufferPool.Return(buffer);
        return result;
    }

    private bool FindSectionStart(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var openBrackets = input.IndexOf('[');
        if (openBrackets == -1 || openBrackets >= input.Length || input[openBrackets + 1] != '%')
            return false;

        result = input.Slice(0, openBrackets);
        return true;
    }

    private bool FindEndSection(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var remainder = input.Slice(2);
        var index = remainder.IndexOfAny('[', ']');
        if (index == -1)
            return false;
        bool isOpen = remainder[index] == '[';
        if (isOpen)
        {
            result = input.Slice(0, index - 1 + 2);
            return false;
        }

        if (input[index - 1 + 2] != '%')
        {
            result = input.Slice(0, index + 1 + 2);
            return false;
        }
        result = input.Slice(0, index + 1 + 2);
        return true;
    }
}

Solution6.cs

public class Solution6
{
    private readonly Dictionary<int, string> _map;
    private readonly List<(string, int, int)> _segments;

    public Solution6(IReadOnlyDictionary<string, string> map)
    {
        _map = new(map.Count);
        foreach (var item in map)
        {
            _map.Add(string.GetHashCode(item.Key.AsSpan()), item.Value);
        }
        _segments = new List<(string, int, int)>(map.Count * 2);
    }

    public string Substitute(string replacement)
    {
        _segments.Clear();
        int currentPointer = 0;
        int replacementLength = 0;
        var section = replacement.AsSpan();
        while (section.Length > 0)
        {
            var hasSections = FindSectionStart(section, out int startLength);
            _segments.Add((replacement, currentPointer, startLength));
            currentPointer += startLength;
            if (!hasSections)
                break;

            var endSection = section.Slice(startLength);
            bool hasMatch = FindEndSection(endSection, out int endLength);
            if (!hasMatch)
            {
                _segments.Add((replacement, currentPointer, endLength));
                currentPointer += endLength;
                section = endSection.Slice(endLength);
                continue;
            }

            // if matched, check if section matches an entry of the map
            if (_map.TryGetValue(string.GetHashCode(endSection.Slice(0, endLength)), out var subsitute))
            {
                _segments.Add((subsitute, 0, subsitute.Length));
                //Compensate with endLength for the final string.Create.
                replacementLength += subsitute.Length - endLength;
            }
            else
            {
                _segments.Add((replacement, currentPointer, endLength));
            }

            currentPointer += endLength;

            section = endSection.Slice(endLength);
        }

        return string.Create(currentPointer + replacementLength, _segments, (destinaton, state) =>
         {
             for (int i = 0; i < state.Count; i++)
             {
                 var (source, start, length) = state[i];
                 source.AsSpan(start, length).CopyTo(destinaton);
                 destinaton = destinaton.Slice(length);
             }
         });
    }

    private bool FindSectionStart(ReadOnlySpan<char> input, out int length)
    {
        length = input.Length;
        var openBrackets = input.IndexOf('[');
        if (openBrackets == -1 || openBrackets >= input.Length || input[openBrackets + 1] != '%')
            return false;

        length = openBrackets;
        return true;
    }

    private bool FindEndSection(ReadOnlySpan<char> input, out int length)
    {
        length = input.Length;
        var remainder = input.Slice(2);
        var index = remainder.IndexOfAny('[', ']');
        if (index == -1)
            return false;
        bool isOpen = remainder[index] == '[';
        if (isOpen)
        {
            length = index - 1 + 2;
            return false;
        }

        if (input[index - 1 + 2] != '%')
        {
            length = index + 1 + 2;
            return false;
        }
        length = index + 1 + 2;
        return true;
    }
}

Solution7.cs

using System.Runtime.CompilerServices;

public class Solution7
{
    private readonly Dictionary<int, string> _map;
    private readonly int _size;
    private char[] _bufferPool;

    public Solution7(IReadOnlyDictionary<string, string> map)
    {
        _map = new(map.Count);
        foreach (var item in map)
        {
            var keyHash = string.GetHashCode(item.Key.AsSpan());
            _map.Add(keyHash, item.Value);
            _size += Math.Abs(item.Key.Length - item.Value.Length);
        }
        _bufferPool = new char[4096 * 8];
    }

    [SkipLocalsInit]
    public string Substitute(ReadOnlySpan<char> replacement)
    {
        if (replacement.Length + _size > _bufferPool.Length)
            _bufferPool = new char[Math.Max(_bufferPool.Length * 2, replacement.Length + _size)];

        var destination = _bufferPool.AsSpan();
        var section = replacement;
        while (section.Length > 0)
        {
            var hasSections = FindSectionStart(section, out var matchedSection);
            matchedSection.CopyTo(destination);
            destination = destination.Slice(matchedSection.Length);
            if (!hasSections)
                break;

            var endSection = section.Slice(matchedSection.Length);
            bool hasMatch = FindEndSection(endSection, out matchedSection);
            if (!hasMatch)
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
                section = endSection.Slice(matchedSection.Length);
                continue;
            }

            // if matched, check if section matches an entry of the map
            if (_map.TryGetValue(string.GetHashCode(matchedSection), out var subsitute))
            {
                subsitute.CopyTo(destination);
                destination = destination.Slice(subsitute.Length);
            }
            else
            {
                matchedSection.CopyTo(destination);
                destination = destination.Slice(matchedSection.Length);
            }

            section = endSection.Slice(matchedSection.Length);
        }
        var result = new string(_bufferPool.AsSpan(0, _bufferPool.Length - destination.Length));
        return result;
    }

    [SkipLocalsInit]
    private bool FindSectionStart(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var openBrackets = input.IndexOf('[');
        if (openBrackets == -1 || openBrackets >= input.Length || input[openBrackets + 1] != '%')
            return false;

        result = input.Slice(0, openBrackets);
        return true;
    }

    [SkipLocalsInit]
    private bool FindEndSection(ReadOnlySpan<char> input, out ReadOnlySpan<char> result)
    {
        result = input;
        var remainder = input.Slice(2);
        var index = remainder.IndexOfAny('[', ']');
        if (index == -1)
            return false;
        bool isOpen = remainder[index] == '[';
        if (isOpen)
        {
            result = input.Slice(0, index - 1 + 2);
            return false;
        }

        if (input[index - 1 + 2] != '%')
        {
            result = input.Slice(0, index + 1 + 2);
            return false;
        }
        result = input.Slice(0, index + 1 + 2);
        return true;
    }
}

TestCases.cs

using System.Collections.Generic;
using Xunit;

namespace RegexTests
{
    public class TestCases
    {
        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution0_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution0();
            var result = sut.Substitute(input, map);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution1_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution1();
            var result = sut.Substitute(input, map);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution2_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution2(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution3_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution3(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution4_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution4(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution5_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution5(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution6_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution6(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(InputOutputData))]
        public void Solution7_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Solution7(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(RecursiveInputOutputData))]
        public void Recursive0_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Recursive0();
            var result = sut.Substitute(input, map);
            Assert.Equal(expected, result);
        }

        [Theory]
        [MemberData(nameof(RecursiveInputOutputData))]
        public void Recursive7_Test(IReadOnlyDictionary<string, string> map, string input, string expected)
        {
            var sut = new Recursive7(map);
            var result = sut.Substitute(input);
            Assert.Equal(expected, result);
        }

        public static IEnumerable<object[]> Common()
        {
            yield return new object[] { Map, string.Empty, string.Empty };
            yield return new object[] { Map, "%final_result%", "%final_result%" };
            yield return new object[] { Map, "[%%]", "[%%]" };
            yield return new object[] { Map, "[%]", "[%]" };
            yield return new object[] { Map, "[%", "[%" };
            yield return new object[] { Map, "%]", "%]" };
            yield return new object[] { Map, "[%%%]", "[%%%]" };
            yield return new object[] { Map, "This is a false [%positive%].", "This is a false [%positive%]." };
            yield return new object[] { Map, "This is a half [%po", "This is a half [%po" };
            yield return new object[] { Map, "This is another half po%]", "This is another half po%]" };
            yield return new object[] { Map, "This is a half [%po [%verynice%]", "This is a half [%po very nice" };
            yield return new object[] { Map, "This is another half po%] [%verynice%]", "This is another half po%] very nice" };
            yield return new object[] { Map, "This is a half [%verynice%] [%po", "This is a half very nice [%po" };
            yield return new object[] { Map, "This is another half [%verynice%] po%]", "This is another half very nice po%]" };
            yield return new object[] { Map, "This is a full [%po[%verynice%]po%]", "This is a full [%povery nicepo%]" };
            yield return new object[] { Map, "This is an empty text", "This is an empty text" };
            yield return new object[] { Map, "This is an [%this_is_my_super_template%] empty text", "This is an containing brackets and percent sign to encapsulate template data empty text" };
            yield return new object[] { Map, "[%final_result%]b", "a final, longer textual result.b" };
            yield return new object[] { Map, "a[%final_result%]", "aa final, longer textual result." };
            yield return new object[] { Map, "a[%final_result%]b", "aa final, longer textual result.b" };
            yield return new object[] { Map, "a[%final_0result%]b", "a[%final_0result%]b" };
            yield return new object[] { Map, "a[%final result%]b", "a[%final result%]b" };
            yield return new object[] { Map, "[%final_result%][%final_result%]", "a final, longer textual result.a final, longer textual result." };
            yield return new object[] { Map, "[%final_result%]A[%final_result%]", "a final, longer textual result.Aa final, longer textual result." };
        }

        public static IEnumerable<object[]> InputOutputData()
        {
            foreach (var common in Common())
                yield return common;
            yield return new object[] { Map, "With inner replacement [%replacement_text%]", "With inner replacement sample [%verynice%] message" };
            yield return new object[] { Map, "With cycle [%cycle%]", "With cycle a[%cycle%]b" };
            yield return new object[] { Map, "With cycle [%cycle_a%]", "With cycle a[%cycle_b%]b" };
        }

        public static IEnumerable<object[]> RecursiveInputOutputData()
        {
            foreach (var common in Common())
                yield return common;
            yield return new object[] { Map, "With inner replacement [%replacement_text%]", "With inner replacement sample very nice message" };
            yield return new object[] { Map, "With cycle [%cycle%]", "With cycle a[%cycle%]b" };
            yield return new object[] { Map, "With cycle [%cycle_a%]", "With cycle aa[%cycle_a%]bb" };
            yield return new object[] { Map, "With [%multiple%] in a row.", "With ba[%multiple_a%] and ab[%multiple_b%] in a row." };
        }

        public static Dictionary<string, string> Map { get; } = new Dictionary<string, string>() {
            { "[%this_is_my_super_template%]", "containing brackets and percent sign to encapsulate template data" },
            { "[%replacement_text%]", "sample [%verynice%] message" },
            { "[%final_result%]", "a final, longer textual result." },
            { "[%type_of_document%]","short text"},
            { "[%exec_order%]","from left to right"},
            { "[%user_do%]","can chain together successive"},
            { "[%verynice%]", "very nice" },
            { "[%cycle%]", "a[%cycle%]b" },
            { "[%cycle_a%]", "a[%cycle_b%]b" },
            { "[%cycle_b%]", "a[%cycle_a%]b" },
            { "[%multiple%]", "[%multiple_a%] and [%multiple_b%]" },
            { "[%multiple_a%]", "b[%multiple_b%]" },
            { "[%multiple_b%]", "a[%multiple_a%]" },
        };
    }
}