So someone requested a Regex Builder / Assistant for Rubberduck and since my CS class had been covering the topic only recently I was thinking to myself: "This sounds interesting, you should do this".
Long story short, a day of designing and a weekend of implementation (and some more polishing) as well as a few reviews later Rubberduck has a fully working Regex Assistant (which even supports i18n).
It can be given a VBA Regular Expression pattern and tells you what it does in a manner similar to other well-known assistants (regex101, expresso, ...)
This means it can parse a given syntactically correct Regex and recognize the separate Atoms and Quantifiers. It analyzes said Atoms and builds a structure that allows displaying useful information about the pattern.
This is accomplished by parsing the expression into a Tree-Structure.
Any Regular Expression is built by either the smallest possible unit you have (an Atom) or other regular expressions. This definition allows us to "abuse" the syntax into building our Design.
We basically need to handle two (well three) things to represent any arbitrary Regular Expression.
- Atoms
- Regular Expressions
- Quantifiers
to be fully correct, Quantifiers actually belong in cahoots with Atoms, but they're.. different, so we'll treat them differently.
This sets the stage for our "data holders":
Atom.cs
using Rubberduck.RegexAssistant.i18n;
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
namespace Rubberduck.RegexAssistant
{
public interface IAtom : IDescribable
{
string Specifier { get; }
}
internal class CharacterClass : IAtom
{
public static readonly string Pattern = @"(?<!\\)\[(?<expression>.*?)(?<!\\)\]";
private static readonly Regex Matcher = new Regex("^" + Pattern + "$");
private readonly bool _inverseMatching;
public bool InverseMatching { get { return _inverseMatching; } }
private readonly IList<string> _characterSpecifiers;
public IList<string> CharacterSpecifiers { get { return _characterSpecifiers; } }
private readonly string _specifier;
public CharacterClass(string specifier)
{
Match m = Matcher.Match(specifier);
if (!m.Success)
{
throw new ArgumentException("The given specifier does not denote a character class");
}
this._specifier = specifier;
string actualSpecifier = m.Groups["expression"].Value;
_inverseMatching = actualSpecifier.StartsWith("^");
_characterSpecifiers= ExtractCharacterSpecifiers(InverseMatching ? actualSpecifier.Substring(1) : actualSpecifier);
}
public string Specifier
{
get
{
return _specifier;
}
}
private static readonly Regex CharacterRanges = new Regex(@"(\\[dDwWsS]|(\\[ntfvr]|\\([0-7]{3}|x[\dA-F]{2}|u[\dA-F]{4}|[\\\.\[\]])|.)(-(\\[ntfvr]|\\([0-7]{3}|x[A-F]{2}|u[\dA-F]{4}|[\.\\\[\]])|.))?)");
private IList<string> ExtractCharacterSpecifiers(string characterClass)
{
MatchCollection specifiers = CharacterRanges.Matches(characterClass);
var result = new List<string>();
foreach (Match specifier in specifiers)
{
if (specifier.Value.Contains("\\"))
{
if (specifier.Value.EndsWith("-\\"))
{
throw new ArgumentException("Character Ranges that have incorrectly escaped characters as target are not allowed");
}
else if (specifier.Value.Length == 1)
{
// Something's bork with the Pattern. For now we skip this it shouldn't affect anyone
continue;
}
}
result.Add(specifier.Value);
}
return result;
}
public string Description
{
get
{
return string.Format(InverseMatching
? AssistantResources.AtomDescription_CharacterClass_Inverted
: AssistantResources.AtomDescription_CharacterClass
, HumanReadableClass());
}
}
private string HumanReadableClass()
{
return string.Join(", ", CharacterSpecifiers); // join last with and?
}
public override bool Equals(object obj)
{
if (obj is CharacterClass)
{
return (obj as CharacterClass)._specifier.Equals(_specifier);
}
return false;
}
public override int GetHashCode()
{
return _specifier.GetHashCode();
}
}
public class Group : IAtom
{
public static readonly string Pattern = @"(?<!\\)\((?<expression>.*(?<!\\))\)";
private static readonly Regex Matcher = new Regex("^" + Pattern + "$");
private readonly IRegularExpression _subexpression;
private readonly string _specifier;
public Group(string specifier) {
Match m = Matcher.Match(specifier);
if (!m.Success)
{
throw new ArgumentException("The given specifier does not denote a Group");
}
_subexpression = RegularExpression.Parse(m.Groups["expression"].Value);
_specifier = specifier;
}
public IRegularExpression Subexpression { get { return _subexpression; } }
public string Specifier
{
get
{
return _specifier;
}
}
public string Description
{
get
{
return string.Format(AssistantResources.AtomDescription_Group, _specifier);
}
}
public override bool Equals(object obj)
{
if (obj is Group)
{
return (obj as Group)._specifier.Equals(_specifier);
}
return false;
}
public override int GetHashCode()
{
return _specifier.GetHashCode();
}
}
internal class Literal : IAtom
{
public static readonly string Pattern = @"(?<expression>\\(u[\dA-F]{4}|x[\dA-F]{2}|[0-7]{3}|[bB\(\){}\\\[\]\.+*?1-9nftvrdDwWsS])|[^()\[\]{}\\*+?^$])";
private static readonly Regex Matcher = new Regex("^" + Pattern + "$");
private static readonly ISet<char> EscapeLiterals = new HashSet<char>();
private readonly string _specifier;
static Literal() {
foreach (char escape in new char[]{ '.', '+', '*', '?', '(', ')', '{', '}', '[', ']', '|', '\\' })
{
EscapeLiterals.Add(escape);
}
_escapeDescriptions.Add('d', AssistantResources.AtomDescription_Digit);
_escapeDescriptions.Add('D', AssistantResources.AtomDescription_NonDigit);
_escapeDescriptions.Add('b', AssistantResources.AtomDescription_WordBoundary);
_escapeDescriptions.Add('B', AssistantResources.AtomDescription_NonWordBoundary);
_escapeDescriptions.Add('w', AssistantResources.AtomDescription_WordCharacter);
_escapeDescriptions.Add('W', AssistantResources.AtomDescription_NonWordCharacter);
_escapeDescriptions.Add('s', AssistantResources.AtomDescription_Whitespace);
_escapeDescriptions.Add('S', AssistantResources.AtomDescription_NonWhitespace);
_escapeDescriptions.Add('n', AssistantResources.AtomDescription_Newline);
_escapeDescriptions.Add('r', AssistantResources.AtomDescription_CarriageReturn);
_escapeDescriptions.Add('f', AssistantResources.AtomDescription_FormFeed);
_escapeDescriptions.Add('v', AssistantResources.AtomDescription_VTab);
_escapeDescriptions.Add('t', AssistantResources.AtomDescription_HTab);
}
public Literal(string specifier)
{
Match m = Matcher.Match(specifier);
if (!m.Success)
{
throw new ArgumentException("The given specifier does not denote a Literal");
}
_specifier = specifier;
}
public string Specifier
{
get
{
return _specifier;
}
}
private static readonly Dictionary<char, string> _escapeDescriptions = new Dictionary<char, string>();
public string Description
{
get
{
// here be dragons!
// keep track of:
// - escaped chars
// - escape sequences (each having a different description)
// - codepoint escapes (belongs into above category but kept separate)
// - and actually boring literal matches
if (_specifier.Length > 1)
{
string relevant = _specifier.Substring(1); // skip the damn Backslash at the start
if (relevant.Length > 1) // longer sequences
{
if (relevant.StartsWith("u"))
{
return string.Format(AssistantResources.AtomDescription_Literal_UnicodePoint, relevant.Substring(1)); //skip u
}
else if (relevant.StartsWith("x"))
{
return string.Format(AssistantResources.AtomDescription_Literal_HexCodepoint, relevant.Substring(1)); // skip x
}
else
{
return string.Format(AssistantResources.AtomDescription_Literal_OctalCodepoint, relevant); // no format specifier to skip
}
}
else if (EscapeLiterals.Contains(relevant[0]))
{
return string.Format(AssistantResources.AtomDescription_Literal_EscapedLiteral, relevant);
}
else if (char.IsDigit(relevant[0]))
{
return string.Format(AssistantResources.AtomDescription_Literal_Backreference, relevant);
}
else
{
return _escapeDescriptions[relevant[0]];
}
}
if (_specifier.Equals("."))
{
return AssistantResources.AtomDescription_Dot;
}
return string.Format(AssistantResources.AtomDescription_Literal_ActualLiteral, _specifier);
}
}
public override bool Equals(object obj)
{
if (obj is Literal)
{
return (obj as Literal)._specifier.Equals(_specifier);
}
return false;
}
public override int GetHashCode()
{
return _specifier.GetHashCode();
}
}
}
IRegularExpression.cs
using Rubberduck.RegexAssistant.Extensions;
using Rubberduck.RegexAssistant.i18n;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
namespace Rubberduck.RegexAssistant
{
public interface IRegularExpression : IDescribable
{
Quantifier Quantifier { get; }
IList<IRegularExpression> Subexpressions { get; }
}
public class ConcatenatedExpression : IRegularExpression
{
private readonly Quantifier _quantifier;
private readonly IList<IRegularExpression> _subexpressions;
public ConcatenatedExpression(IList<IRegularExpression> subexpressions)
{
_subexpressions = subexpressions;
_quantifier = new Quantifier(string.Empty); // these are always exactly once. Quantifying happens through groups
}
public string Description
{
get
{
return AssistantResources.ExpressionDescription_ConcatenatedExpression;
}
}
public Quantifier Quantifier
{
get
{
return _quantifier;
}
}
public IList<IRegularExpression> Subexpressions
{
get
{
return _subexpressions;
}
}
}
public class AlternativesExpression : IRegularExpression
{
private readonly Quantifier _quantifier;
private readonly IList<IRegularExpression> _subexpressions;
public AlternativesExpression(IList<IRegularExpression> subexpressions)
{
_subexpressions = subexpressions;
_quantifier = new Quantifier(string.Empty); // these are always exactly once. Quantifying happens through groups
}
public string Description
{
get
{
return string.Format(AssistantResources.ExpressionDescription_AlternativesExpression, _subexpressions.Count);
}
}
public Quantifier Quantifier
{
get
{
return _quantifier;
}
}
public IList<IRegularExpression> Subexpressions
{
get
{
return _subexpressions;
}
}
}
public class SingleAtomExpression : IRegularExpression
{
public readonly IAtom Atom;
private readonly Quantifier _quantifier;
public SingleAtomExpression(IAtom atom, Quantifier quantifier)
{
Atom = atom;
_quantifier = quantifier;
}
public string Description
{
get
{
return string.Format("{0} {1}.", Atom.Description, Quantifier.HumanReadable());
}
}
public Quantifier Quantifier
{
get
{
return _quantifier;
}
}
public IList<IRegularExpression> Subexpressions
{
get
{
return new List<IRegularExpression>(Enumerable.Empty<IRegularExpression>());
}
}
public override bool Equals(object obj)
{
if (obj is SingleAtomExpression)
{
SingleAtomExpression other = obj as SingleAtomExpression;
return other.Atom.Equals(Atom) && other.Quantifier.Equals(Quantifier);
}
return false;
}
public override int GetHashCode()
{
return Atom.GetHashCode() ^ Quantifier.GetHashCode();
}
}
public class ErrorExpression : IRegularExpression
{
private readonly string _errorToken;
public ErrorExpression(string errorToken)
{
_errorToken = errorToken;
}
public string Description
{
get
{
return string.Format(AssistantResources.ExpressionDescription_ErrorExpression, _errorToken);
}
}
public Quantifier Quantifier
{
get
{
return new Quantifier(string.Empty);
}
}
public IList<IRegularExpression> Subexpressions
{
get
{
return new List<IRegularExpression>();
}
}
}
}
and for the curious:
Quantifier.cs
using System;
using System.Text.RegularExpressions;
namespace Rubberduck.RegexAssistant
{
public class Quantifier
{
public static readonly string Pattern = @"(?<quantifier>(?<!\\)[\?\*\+]|(?<!\\)\{(\d+)(,\d*)?(?<!\\)\})";
private static readonly Regex Matcher = new Regex(@"^\{(?<min>\d+)(?<max>,\d*)?\}$");
public readonly QuantifierKind Kind;
public readonly int MinimumMatches;
public readonly int MaximumMatches;
public Quantifier(string expression)
{
if (expression.Length == 0)
{
Kind = QuantifierKind.None;
MaximumMatches = 1;
MinimumMatches = 1;
}
else if (expression.Length > 1)
{
Kind = QuantifierKind.Expression;
Match m = Matcher.Match(expression);
if (!m.Success)
{
throw new ArgumentException(string.Format("Cannot extract a Quantifier from the expression {1}", expression));
}
int minimum;
// shouldn't ever happen
if (!int.TryParse(m.Groups["min"].Value, out minimum))
{
throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
}
MinimumMatches = minimum;
string maximumString = m.Groups["max"].Value; // drop the comma
if (maximumString.Length > 1)
{
int maximum;
// shouldn't ever happen
if (!int.TryParse(maximumString.Substring(1), out maximum))
{
throw new ArgumentException("Cannot Parse Quantifier Expression into Range");
}
MaximumMatches = maximum;
}
else if (maximumString.Length == 1) // got a comma, so we're unbounded
{
MaximumMatches = int.MaxValue;
}
else // exact match, because no comma
{
MaximumMatches = minimum;
}
}
else
{
switch (expression.ToCharArray()[0])
{
case '*':
MinimumMatches = 0;
MaximumMatches = int.MaxValue;
Kind = QuantifierKind.Wildcard;
break;
case '+':
MinimumMatches = 1;
MaximumMatches = int.MaxValue;
Kind = QuantifierKind.Wildcard;
break;
case '?':
MinimumMatches = 0;
MaximumMatches = 1;
Kind = QuantifierKind.Wildcard;
break;
default:
throw new ArgumentException("Passed Quantifier String was not an allowed Quantifier");
}
}
}
public override bool Equals(object obj)
{
if (obj is Quantifier)
{
var other = obj as Quantifier;
return other.Kind == Kind && other.MinimumMatches == MinimumMatches && other.MaximumMatches == MaximumMatches;
}
return false;
}
public override int GetHashCode()
{
return MinimumMatches ^ MaximumMatches ^ Kind.GetHashCode();
}
public override string ToString()
{
return string.Format("Quantifier[{0}: {1} to {2}", Kind, MinimumMatches, MaximumMatches);
}
}
public enum QuantifierKind
{
None, Expression, Wildcard
}
}
Now all of this must critically support internationalization. That's why each of these is inherently coupled with some internationalization. I'm aware that this could be somewhat avoided with extension methods or by introducing a separate class to handle the mess. I decided against that to keep the simplicity of the design.
Last but not least, we'll need to actually build a tree from these "data holders". That's done ... well I have a big comment there, it explains how it works:
internal static class RegularExpression
{
/// <summary>
/// We basically run a Chain of Responsibility here. At first we try to parse the whole specifier as one Atom.
/// If this fails, we assume it's a ConcatenatedExpression and proceed to create one of these.
/// That works well until we encounter a non-escaped '|' outside of a CharacterClass. Then we know that we actually have an AlternativesExpression.
/// This means we have to check what we got back and add it to a List of subexpressions to the AlternativesExpression.
/// We then proceed to the next alternative (ParseIntoConcatenatedExpression consumes the tokens it uses) and keep adding to our subexpressions.
///
/// Note that Atoms (or more specifically Groups) can request a Parse of their subexpressions.
/// Also note that TryParseAtom is responsible for grabbing an Atom <b>and</b> it's Quantifier.
/// If there is no Quantifier following (either because the input is exhausted or there directly is the next atom) then we instead pair with `new Quantifier("")`
/// </summary>
/// <param name="specifier">The full Regular Expression specifier to Parse</param>
/// <returns>An IRegularExpression that encompasses the complete given specifier</returns>
public static IRegularExpression Parse(string specifier)
{
IRegularExpression expression;
// ByRef requires us to hack around here, because TryParseAsAtom doesn't fail when it doesn't consume the specifier anymore
string specifierCopy = specifier;
if (TryParseAsAtom(ref specifierCopy, out expression) && specifierCopy.Length == 0)
{
return expression;
}
List<IRegularExpression> subexpressions = new List<IRegularExpression>();
while (specifier.Length != 0)
{
expression = ParseIntoConcatenatedExpression(ref specifier);
// ! actually an AlternativesExpression
if (specifier.Length != 0 || subexpressions.Count != 0)
{
// flatten hierarchy
var parsedSubexpressions = (expression as ConcatenatedExpression).Subexpressions;
if (parsedSubexpressions.Count == 1)
{
expression = parsedSubexpressions[0];
}
subexpressions.Add(expression);
}
}
return (subexpressions.Count == 0) ? expression : new AlternativesExpression(subexpressions);
}
/// <summary>
/// Successively parses the complete specifer into Atoms and returns a ConcatenatedExpression after the specifier has been exhausted or a single '|' is encountered at the start of the remaining specifier.
/// Note: this may fail to work if the last encountered token cannot be parsed into an Atom, but the remaining specifier has nonzero lenght
/// </summary>
/// <param name="specifier">The specifier to Parse into a concatenated expression</param>
/// <returns>The ConcatenatedExpression resulting from parsing the given specifier, either completely or up to the first encountered '|'</returns>
private static IRegularExpression ParseIntoConcatenatedExpression(ref string specifier)
{
List<IRegularExpression> subexpressions = new List<IRegularExpression>();
string currentSpecifier = specifier;
int oldSpecifierLength = currentSpecifier.Length + 1;
while (currentSpecifier.Length > 0 && currentSpecifier.Length < oldSpecifierLength)
{
oldSpecifierLength = currentSpecifier.Length;
IRegularExpression expression;
// we actually have an AlternativesExpression, return the current status to Parse after updating the specifier
if (currentSpecifier[0].Equals('|'))
{
specifier = currentSpecifier.Substring(1); // skip leading |
return new ConcatenatedExpression(subexpressions);
}
if (TryParseAsAtom(ref currentSpecifier, out expression))
{
subexpressions.Add(expression);
}
else if (currentSpecifier.Length == oldSpecifierLength)
{
subexpressions.Add(new ErrorExpression(currentSpecifier.Substring(0, 1)));
currentSpecifier = currentSpecifier.Substring(1);
}
}
specifier = ""; // we've exhausted the specifier, tell Parse about it to prevent infinite looping
return new ConcatenatedExpression(subexpressions);
}
private static readonly Regex groupWithQuantifier = new Regex("^" + Group.Pattern + Quantifier.Pattern + "?");
private static readonly Regex characterClassWithQuantifier = new Regex("^" + CharacterClass.Pattern + Quantifier.Pattern + "?");
private static readonly Regex literalWithQuantifier = new Regex("^" + Literal.Pattern + Quantifier.Pattern + "?");
/// <summary>
/// Tries to parse the given specifier into an Atom. For that all categories of Atoms are checked in the following order:
/// 1. Group
/// 2. Class
/// 3. Literal
/// When it succeeds, the given expression will be assigned a SingleAtomExpression containing the Atom and it's Quantifier.
/// The parsed atom will be removed from the specifier and the method returns true. To check whether the complete specifier was an Atom,
/// one needs to examine the specifier after calling this method. If it was, the specifier is empty after calling.
/// </summary>
/// <param name="specifier">The specifier to extract the leading Atom out of. Will be shortened if an Atom was successfully extracted</param>
/// <param name="expression">The resulting SingleAtomExpression</param>
/// <returns>True, if an Atom could be extracted, false otherwise</returns>
// Note: could be rewritten to not consume the specifier and instead return an integer specifying the consumed length of specifier. This would remove the by-ref passed string hack
internal static bool TryParseAsAtom(ref string specifier, out IRegularExpression expression)
{
Match m = groupWithQuantifier.Match(specifier);
if (m.Success)
{
string atom = m.Groups["expression"].Value;
string quantifier = m.Groups["quantifier"].Value;
specifier = specifier.Substring(atom.Length + 2 + quantifier.Length);
expression = new SingleAtomExpression(new Group("("+atom+")"), new Quantifier(quantifier));
return true;
}
m = characterClassWithQuantifier.Match(specifier);
if (m.Success)
{
string atom = m.Groups["expression"].Value;
string quantifier = m.Groups["quantifier"].Value;
specifier = specifier.Substring(atom.Length + 2 + quantifier.Length);
expression = new SingleAtomExpression(new CharacterClass("["+atom+"]"), new Quantifier(quantifier));
return true;
}
m = literalWithQuantifier.Match(specifier);
if (m.Success)
{
string atom = m.Groups["expression"].Value;
string quantifier = m.Groups["quantifier"].Value;
specifier = specifier.Substring(atom.Length + quantifier.Length);
expression = new SingleAtomExpression(new Literal(atom), new Quantifier(quantifier));
return true;
}
expression = null;
return false;
}
}
Do note that this class is packed into the same file (and namespace-declaration) as IRegularExpression
.
Questions:
- Is this design obvious?
- Is the code maintainable?
- Could i18n be handled cleaner?
I am 100% sure this code works, because regular expressions are methodically simple, and I've verified a significant number of edge-cases in an extensive test-suite, that can be found alongside the code on github
I
tacked onto the beginning of a defenseless name probably wouldn't see it that way though. \$\endgroup\$I
followed by aPascalCase
identifier expects it to be an interface; the expletives would burst if theI
was missing and the type was later found to be an interface, as it's convention. It might seem like some silly Hungarian coming from a non-.net perspective, ...but something doesn't feel right if it's missing. \$\endgroup\$