Simple Regex #6½: More Lazy Quantifiers

Hush. Hush.

The security-related components of my work continue to comprise only product-specific threats and mitigation, which means I can't exactly blog about them in a public forum like this one. Instead, here's a little more on the subject of that previous application of Regular Expressions to music catalogues.

Oh and about that previous article, I have to be honest and say that I've been getting complaints! Apparently the level of explanation offered wasn't even up to my usual low standards of lucidity? Let's try to rectify that here. The goal you'll remember was to parse a list of classical music pieces like this,

49. Violin Concerto in E major, RV271 "L'amoroso" - Antonio Vivaldi

subject to the proviso that while an item's rank (here equal to 49), title (Violin Concerto) and composer name (Antonio Vivaldi) are all mandatory, the key (E major), opus/catalogue number (RV271) and nickname (L'amoroso) are all optional. Here's an analysis of the Regex pattern I'm using to split these records into fields:

private const string rank = @"(\d+)\.";
private const string title = @" (.+?)";
private const string key = @"(?: in ([A-G](?: flat| sharp)?(?: major| minor)?))?";
private const string number = @"(?:, (.+?))?";
private const string nickname = @"(?: ""(.+)"")?";
private const string composer = @" - (.+)";
private const string pattern = rank + title + key + number + nickname + composer;

The @ symbol is an artifact of the C# language. Most of its appearances above are redundant, but regardless, I do tend to use it habitually when working with Regex. It saves having to double all backslashes. So the first line

private const string rank = @"(\d+)\.";

matches one or more decimal digits (followed by a literal period, which is outside the capturing parentheses, and so doesn't itself get included in the captured group). The second line

private const string title = @" (.+?)";

matches a space (again excluded, being outside the group) followed by one or more characters of the title, but matching as few characters as possible consistent with an overall successful match.

It helps to apply these two visual filters when inspecting the various groups in patterns like the third line above:

(?: starts a non-capturing group;
)? ends an optional group.

So for example, the overall key group pattern above is both non-capturing, since it starts with (?:, and optional, since it ends with )?. Nested within it is the main capturing group (labelled c1 in the expanded analysis below) for the key text, and nested in turn within that are two further, non-capturing, optional groups, n1 and n2:

private const string n1 = @"(?: flat| sharp)?";
private const string n2 = @"(?: major| minor)?";
private const string c1 = @"([A-G]" + n1 + n2 + ")";
private const string key = @"(?: in " + c1 + ")?";

More Music Maestro!

Hopefully that's as much analysis as we need for this pattern. It's a little more complex than previously, because of the addition of this opus/catalogue number field, appearing when I generalised the listening project, originally featuring just symphonies, to include also the concerti, symphonic poems and ballets in the following lists:

• Symphonies (129)
• Concerti (60 piano, 50 violin, 40 other)
• Tone Poems (50)
• Ballets (16)

That should be enough to keep HMV in business for a few more weeks! I wanted the project to include all our classical favourites, so piano concerti became a necessity (Grieg for me, Tchaikovsky #1 for the wife), as did tone poems (The Planets, for both of us) and ballets (Bolero). Anyway, the addition of opus/catalogue number field seemed like a good idea. And obviously being optional, it had to be added with yet a third lazy quantifier. Equally lazy is my detection of the number field's existence, which is triggered by the presence of a comma in the title (but after the key, if any). It would be possible to do more, since this field does have certain structure, although not as much as the key field. Noticing that only one record contained commas in the actual title,

106. Symphony No. 14 for soprano, bass, strings, and percussion – Dmitri Shostakovich

I just deleted them. Well sometimes, and particularly with Regex, the best solution is to get a life.

Simple Regex #6: Lazy Quantifiers

Dedicated Listener

I've decided to listen to 129 classical symphonies and rate them against each other, to try to understand this musical format a little better. The project has two immediate side effects of a technical nature. I've had to:

1. Replace the 32GB SDHC card on my phone MP3 player, a venerable Sony Ericsson Xperia X10 Mini, with the bleeding edge Sandisk 64GB SDXC, to make room for a shedload of symphonies; and
2. Brush up on greedy quantifiers, and their lazier, more reluctant counterparts.

The former was a pleasant surprise. The phone manufacturer's specifications have always claimed microSDHC compatibility "up to 16GB", but I'd been using a 32GB card ever since the X10 Mini got shunted out of my wife's handbag by the arrival of a bouncing new baby Galaxy. Still, the jump to purchase the XC card was a bit of a leap of faith, since nobody else online appeared to have tried this particular combo. Sadly, it worked! Yes sadly, because otherwise, I'd have had a great case for a new phone...

The latter side effect occurs because I've arrived at my list of 129 symphonies under test by combining the main table of 120 listed at Digital Dream Door,

http://www.digitaldreamdoor.com/pages/best-classic-symp.html

with a further 9 also-rans suggested by that forum's moderator, and compiler of the main list, whom we shall call Brian (for that is his name). Having screen scraped his raw data, converting all its en–dashes and “directional quotes” to hy-phens and "neutrals", I was left with the task of parsing these results. Here's a small sample:

 1. Symphony No. 9 in D minor "Choral" - Ludwig Van Beethoven
 2. Symphony No. 5 in C minor - Ludwig Van Beethoven
11. Symphonie Fantastique - Hector Berlioz
63. Symphony No. 3 "The Camp Meeting" - Charles Ives

For analysis, I need to extract certain data from these entries. The first, dot-terminated field is Brian's initial rank. This is followed by the full title of the symphony, which usually includes its performance key, and sometimes a popular alternate title or nickname. Finally, a hyphen sets off the composer name.

Now, it would have been easy to take multiple passes at this task, first removing any optional (key and nickname) fields present, then splitting the remaining text into the mandatory rank, root title and composer name fields. Too easy, in fact. Why do that, when we could just use a single Regex pattern to simultaneously extract the full compliment of fields, mandatory and optional?

Too Greedy

The difficulty is that the pattern capturing the symphony title could also gobble up any key and/or nickname information that might be present. Let's say for simplicity that the key field can be identified by the word in, while the nickname is delimited by double quotation marks. That gives us two optional groups:

(?: in (.+?))?
(".+")?

where we've nested the capturing key group (underlined) in a non-capturing group (?: )? in order to exclude the in keyword itself from the captured data. Let's try dropping these into our first attempt at a mandatory field template:

(\d+)\. (.+)(?: in (.+?))?(".+")? - (.+)

This succeeds in extracting the leftmost rank and rightmost composer name fields correctly. However, there's no key or nickname information parsed out; all of that remains resolutely embedded in the title field. We say that the + quantifier in the title group (.+) is greedy. It gobbles up as many input characters as possible, backtracking only when necessary to find an overall pattern match. If it can devour the key and nickname information without breaking the match, as here it can because those groups are optional, then it will.

Dieting

Quantifiers like ?, *, + and {m,n} can be made less greedy by following them with a question mark. For example, the ? quantifier on its own matches zero or one occurrence(s) of the preceding expression, but with a preference for one. That's to say, it will gobble up input characters whenever it can. ?? also matches zero or one occurrence(s) of the expression immediately before it, but with a preference for zero. In general, these so-called lazy quantifiers consume as few input characters as possible, while still letting the overall pattern match succeed. Which turns out to be exactly what's needed in our case:

(\d+)\. (.+?)(?: in (.+?))?(".+")? - (.+)

Now the title group (.+?) consumes the minimum possible number of characters, meaning that if there are key or nickname fields present, the associated groups will now have a higher priority in extracting those from the input stream. Similarly, the identical key group (.+?) has itself been put on a diet, to stop it gobbling up any present nickname.

The final pattern that I used contained many further refinements, including named groups for readability, generalisation of white space, trimming of field contents, and stricter key field matching with a more specific group pattern,

[A-G](?: sharp| flat)?(?: major| minor)?

which actually removes the need for the second lazy quantifier above. Incidentally this also allows the word in to appear in the symphony's title in a non-key, non-nickname context - as for example in Igor Stravinsky's Symphony in Three Movements, which happens to be number 76 on Brian's list.

Further Reading, Listening

Greedy and lazy Regex quantifiers are explained in more detail at MSDN:

http://msdn.microsoft.com/en-us/library/3206d374.aspx

A good online tool for testing regular expressions containing multiple groups is Derek Slager's AJAX offering, A Better .NET Regular Expression Tester, which can be found here:

http://derekslager.com/blog/posts/2007/09/a-better-dotnet-regular-expression-tester.ashx

As for the listening exercise, a quick survey of my dusty old Classic FM CDs reveals that I already have good recordings of 43 56 symphonies on Brian's list, including all of his top 20 25 (and quite a few duplicates; who authorised that?). So cost wise, I'm exactly one third almost half complete. Although to be honest, I've never really liked Solti's limp wristed walkthrough of Mozart's Jupiter...

Simple Regex #5: Named Groups

Regex.Result()

Almost every Regex question landing on my desk has the potential to get its own blog post. This month's candidate is almost straightforward enough to be painless. Almost, because well, there's always some pain with Regex! Colleague 7 wanted to know how to extract coordinate data tidily from a string...

Regex question for you if you don't mind:

@1,X=123@1,Y=456

Looking to pick the x and y coordinates out of that string and return a point. I can obviously get the bits separately. But that would be too easy!

(?<=X=)[0-9]+
and
(?<=Y=)[0-9]+

Should I use named capture groups?

Well, personally I would, because the outcome is (1) marginally more readable than indexed groups, in my opinion; and (2) more robust, when subsequently you have to extend the pattern to incorporate further groups. Relabeling index-based groups is a nightmare!

Notice that the above suggested digit filters are using zero-width positive look-behind assertions, (?<= ), which were covered in the previous article in this series. These are just looking for an X or a Y, followed by an equal sign, and then the string of one or more digits which we wish to extract. Let's make these constants in our code, so it's easier to concentrate on what's around them (I've replaced the numeral set [0-9] with the digit class \d, another personal preference):

const string x = @"(?<=X=)\d+";
const string y = @"(?<=Y=)\d+";

Without named groups, we would simply incorporate x and y into a grouping pattern with an intervening wild string:

const string pattern = "(" + x + ").*(" + y + ")";
var input = "@1,X=123@1,Y=456";
var match = Regex.Match(input, pattern);
if (match.Success)
 return match.Result("($1,$2)"); // Output: (123,456)

Two changes are required to convert to named groups. First the names have to be applied. This involves adding a ? at the start of each group, followed by its name in either angle brackets, or as here, single quotes:

const string pattern = "(?'X'" + x + ").*(?'Y'" + y + ")";

Then after the match succeeds, these names, this time enclosed in curly braces, can be used to extract the relevant matched values:

if (match.Success)
 return match.Result("(${X},${Y})"); // Output: (123,456)

Follow Up Questions

Any reason you didn't use string.Format to define the regex?
This is what I ended up with: 

const string xCoordGroupName = "XCOORD";
const string yCoordGroupName = "YCOORD";
string pattern = string.Format("X=(?<{0}>[0-9]+).*Y=(?<{1}>[0-9]+)", xCoordGroupName, yCoordGroupName);
var match = Regex.Match(coords, pattern);

Readability by any chance?

Try changing that to "const string pattern...".
The + string concatenation operator is not inefficient at compile time.
Also, you often get a lot of {}s in your patterns, and Format doesn't like that.

SDL Tools TFS 2010 Update

Better, Late

Team Foundation Server 2010 takes credit for most of the just-released updates to Microsoft's SDL toolset:

Threat Modeling Tool v3.1.8

The main pre-coding system security analysis tool has been updated with a number of bug fixes, improving the stability of the product's Visio 2010 and TFS 2010 support. 6MB msi.

MiniFuzz Tool v1.5.5

This SDL verification phase helper has also benefited from several stability-related bug fixes, and improved control of target application shutdown. It too has had TFS 2010 support added. 2MB msi.

RegExFuzz Tool v1.1.0

H Beam Piper and John Scalzi's retro SF aside, this is my favourite little fuzzy. It allows checking against a specific class of DoS attack, via regular expression patterns with exponential evaluation times. The update again contains a number of bug fixes based on version 1 feedback. 2MB msi. Unfortunately there are still a couple of unresolved known issues, albeit fairly minor ones. From the supplied documentation (ReadMe.rtf):

1. The tool does not handle nested anchors in a regular expression. A regular expression can be assumed to start with ‘^’ and ended with ‘$’. If these tags or their variants are included in a target regular expression, the tool will throw an unhandled exception. The work-around is to break up the nested regular expression and test the resulting regular expressions individually.


2. The tool requires that hexadecimal (‘\x’ prefix) characters within the regular expression be 2 characters. Those with a 0-padding assumed single character description will cause the tool to throw an unhandled exception. The work-around is to make all hexadecimal character descriptions two characters ‘\xCC’.

Simple Regex #4: Assertions

That Old Saw

Another Regex question, another blog post! This time, Colleague A wants to highlight search terms by inserting some CSS spans into his HTML. It's the old problem of ignoring the content of tags during substitution. For example, suppose he highlights the search term school by applying the CSS class xred. This causes injection of spans like this into his output:

Alan went to class at <span class="xred">school</span> next day.

So far the rendering is as expected:

Alan went to class at school next day.

Trouble is, he next wants to highlight the search term class in xgreen:

Alan went to class at school next day.

Doing another simple replace operation would cause the new, "false positive" instances of the term class (occurring within the previously added HTML tags) to be incorrectly incorporated into new xgreen spans, resulting instead in invalid markup, and an onscreen train wreck.

Alan went to class at class="xred">school next day.

The following method of avoiding substitutions within tags is far from the best available solution, even among those offered by Regex. However, it does provide a conveniently simple example to let me introduce another Regex concept, namely Assertions.

Zero Width Assertions

In the context of regular expressions, an assertion is simply a statement about the context of the current match. The simplest examples are the "begins with", "ends with" and "exact match" assertions, which use the ^ and $ characters to match the beginning and end of the line, respectively. Suppose our input is 12345. Then the pattern 234 will match this successfully. The pattern ^234 will not, because the caret ^ constrains the matching to occur at the start of the input string, and ours does not start with 234 (the pattern ^123 will of course succeed). Similarly in the pattern 234$, the dollar $ constrains the matching to occur at the end of the input string, and so this will also fail to match our input, whereas 345$ will succeed. Finally, using both assertions, ^12345$ will match only the entire input string 12345, while any other sub-pattern such as ^1234$ fails.

These two meta characters are examples of atomic zero-width assertions, also known as anchors. Zero-width means that they do not cause the engine to advance through the string or consume characters; they just assert something about the current position in the input. There are several other anchors, but now I want to turn to more general assertions.

Assertion Types

Both of the above examples can be characterised as positive assertions, in that they require something to be true about the current position; namely that it is the start, or end, of the line. You could imagine another assertion type, where you want to match a particular sequence anywhere except either or both of those positions. And yes, such negative assertions are available, as we'll soon see.

Another characteristic of assertions is the direction they face. The caret ^ is termed a look-behind assertion; it states that no input exists before the current position. Similarly the dollar $ is termed look-ahead, as it states there's no further input available beyond the current position.

Finally, the new assertions I'm about to introduce, while still zero-width, are no longer atomic. Instead of referring to known fixed points, such as the beginning or end of the string, line, previous match, or word/non-word boundary, these new assertions contain their own independent subexpression patterns, which they assert do (or do not) occur immediately before (or after) the current position in the input. The parentheses here reflect the difference between positive and negative assertions, and between look-behind and look-ahead behaviour. So there have to be four types, right?

They all use syntax similar to grouping constructs. Positive assertions are indicated by =, negative by !. By default these are assumed to be look-ahead, unless prefixed by < to signify look-behind.

positive look-ahead: (?= subexpression)
negative look-ahead: (?! subexpression)
positive look-behind: (?<= subexpression) ◀ this is the one we are going to use
negative look-behind: (?<! subexpression)

Back To Highlighting

Refer to MSDN for examples of each of these. Now I just want to finish by showing how a zero-width positive look-behind assertion can be used to protect the content of those HTML tags.

How can we write a pattern to match search terms ignoring tag contents? If we're inside a tag, then there's a < somewhere to our left, as yet unmatched by a closing >, while if we're outside, then either there are no < on the left, or else every such < is matched by a corresponding > also on our left. In other words, we want everything on our left to consist of: start of line ^, followed by any number of (a) non-< characters, or else (b) < characters with eventual matching > characters:

^([^<]|<[^>]*>)*

Finally, wrap that as the subexpression in the third template above, and we're done:

(?<=^([^<]|<[^>]*>)*)

Code Sample

private static string Highlight(string input, string search, string cssClassName)

{

  const string assertion = "(?<=^([^<]|<[^>]*>)*)";

  var pattern = string.Format("{0}{1}", assertion, search);

  return Regex.Replace(

      input,

      pattern,

      match => string.Format("<span class=\"{0}\">{1}</span>", cssClassName, match.Value));

}



private static string Test()

{

  return Highlight(

      "<span class=\"ignorethisclass\">This</span> is the class.",

      "class",

      "highlight");

}



// Output: <span class="ignorethisclass">This</span> is the <span class="highlight">class</span>.

Disclaimer

Remember, this is only an illustrative example. As a practical HTML postprocessing solution, there's still a number of holes in it!

Simple Regex #3½: Balancing Groups

Undo Revisited

I've been taken to task for failing to provide a Regex-based solution to the problem in the previous article of this series, namely, removal of backtracked elements from a path. One correspondent even left a comment containing the missing Regex solution! Another complained that my I/O path specific .Net workaround would be zero help to someone just happening upon my article, maybe while researching some other aspect of the underlying patterns.

It's a fair cop, and the only way to salvage even a wee bit of reputation is to provide a full explanation of the proposed Regex solution. In mitigation, the proposed mechanism (Balancing Group Definitions, described below) is also unique to the .Net implementation of Regex. But hey, I'm only the piano player...

This is one of those curious cases where the attempt to generalise the problem reveals a simplifying hidden structure. The first underlying pattern mentioned above is the Undo (or sometimes the Delete) pattern. Consider the original example:

d:\project\client\forms\..\..\version.cs

The entire midsection "\client\forms\..\.." is redundant; we'd like to delete such missteps, obtaining a "normalised" answer such as

d:\project\version.cs

Consider the operating system's behaviour as it attempts to follow the original verbose path. It acts like a finite state machine. Each time it encounters a subdirectory name, like \client or \forms, it enters that subdirectory. Each time it encounters the parent token \.. it reverses back out of the most recently entered subdirectory.

But look what happens when we replace the phrases subdirectory name with letter, and parent token with backspace. Now the problem can be seen to be completely analogous with that of correcting a typed word.

A Typo Processor

Let's use the # symbol to represent the pressing of the backspace key. Then our new problem is to take an input comprising a sequence of letters and # symbols, and parsing it, recover the correctly typed word. For example, if I misspell yield as yeild but correct the mistake manually before completing the word, then the input string (the received sequence of keystrokes) might be yei##ield, and the required output is, of course, yield.

The pattern that our Typo Detector has to detect is: a number (one or more) of # symbols, immediately preceded by exactly that same number of letters. This then is the pattern - in the example case, ei## - that must be removed, in order to, erm, yield the corrected word.

Following the naive reasoning of the original article, we might try using something like \w# (one "word" character, followed by a backspace token) to match the typo pattern. And just as before, this fails in the second simplest test case (the ei## of the previous paragraph). What we need is \w\w## to match that case. But then we also need \w\w\w### to detect the case where three consecutive mistyped characters are corrected. And so on. In fact what we need is approximated by the pseudopattern

\w{n}#{n}

where n cannot be specified in advance, but

• is greater than zero, and
• represents the same number in both positions.

Actually, we want even more than that. What about cases where I make a mistake while correcting a previous typo? For example yei#i##ield. Ideally we'd also like permuted edit patterns like this one, \w\w#\w##, extracted as entire single units. Unbelievably, this functionality is readily provided by the Microsoft proprietary Regex extension known as...

The Balancing Group Definition

But first, let's revise the Group concept from the ground up. Groups are simply added to a Regex by surrounding any pattern subexpression in parentheses. For example, the pattern

0141(\d{3})\d{4}

not only matches any BT landline number in Glasgow, but also allows the central three-digit exchange code to be retrieved conveniently as a group for use elsewhere. These anonymous groups are retrieved by numerical index, which can quickly get a bit too fiddly for comfort.

The next level of usability is the named group. The prefix ? within a group introduces its name, which should be enclosed in either apostrophes or angle brackets. For example, the pattern

0141(?'exchange' \d{3})\d{4}

allows retrieval of the three-digit exchange group by name. And we are nearly there. Because it's an interesting implementation detail about groups, and in particular named groups, that they are pushed on to a stack as they are identified. This means that they can also be popped off. If we can push a group for each word character typed, pop one for each backspace token, and determine when the stack becomes empty, then we can detect all redundant groups in the input stream.

The balancing group definition will delete ("pop") a previous group, and replace it ("push") with the interval between the previously defined group and the current group. Syntactically, we append the previous group name to the current one, using a hyphen for separation. So it looks like this:

(?'curr-prev' subexpression)

The current group name curr is optional, since nothing says that all groups have to be named. The previous group name prev is mandatory; we do need some way of referring to it, since we're about to pop it.

Here is the magic pattern:

\w((?>\w(?'N')|#(?'-N'))*(?(N)(?!)))#

Since it detects an erroneous word character which is subsequently deleted, it begins naturally enough with \w( and ends with )#. Hey this is easy! Now look at the first interior pattern, west of the asterisk:

(?>\w(?'N')|#(?'-N'))

This is saying a couple of things:

• If there's another word character \w then push a new group, which we call N.
• Otherwise if there's a backspace token # then pop the most recent group named N.

The asterisk allows this process to happen any number of times, including zero. This corresponds to typing some characters, deleting a few, typing some more, and so on. Penultimately, east of the asterisk and just prior to the final #, we find another expression:

(?(N)(?!))

This is a trick! If there are still undeleted word character groups on the stack, i.e. an N that hasn't yet been popped, this construction forces a match against the pattern (?!) about which all we need know is that it will fail. Well okay, it's called an expressionless negative lookahead, if you really must know everything! Otherwise so long as the final # appears, we have found a wholly redundant segment.

Back To The Path

If in our magic pattern we now replace \w with a pattern for a subdirectory name, such as \\\w+, and if we further replace # with the parent directory pattern \\\.\. throughout, then we transform it into the path normalizer that was the subject of the original article. The details are horrendous, because filesystem subdirectory names can contain other than word characters, including dots. We have to exclude \.. from these, and \. requires even more special handling. Nevertheless we have solved the fundamental problem of applying Regex here, and as it so happens that all of my subdirectory names were well behaved and dotless in any case, this solution would have worked for me.

Further Generalisation

The Undo/Delete pattern itself represents a simple subset of the problems that these Regex Grouping Constructs are capable of solving. Refer to the MSDN Regex topic on the applicability of Balancing Group Definitions for a complete guide to applying these constructs in any given recursively nested construct parsing context, such as matching parentheses, opening and closing brackets, quotation marks, mathematical expressions, or lines of program code containing multiple nested calls (most of which cannot be parsed in Regex implementations other than the .Net one).

Though be warned, the expository technical language used over there assumes at least some familiarity with the domain of abstract formal languages. Perhaps a better, more gentle introduction to balancing groups can be found in either of these articles:

• .NET Regular Expressions: Regex and Balanced Matching [Ryan Byington]
• Matching Balanced Constructs with .NET Regular Expressions [Wes Haggard]

Update (20 June 2011): I was going to share my .NET Regex Tester online with you, before I noticed that Derek Slager's is, in his own words, better... so, here's a link to his:

http://derekslager.com/blog/posts/2007/09/a-better-dotnet-regular-expression-tester.ashx

Good luck!

Simple Regex #3: A Failure Case

No Back Tracking

I was processing a number of Visual Studio files. A large-ish number of C# solution, project, and source files. Looking for any obsolete (or otherwise redundant) .cs file which wasn't included in a .csproj - or worse, any .csproj that wasn't explicitly built by a .sln. Now, some of these projects referred to files not in the directory subtree of the project file itself. Also, some such references employed relative paths.

For example, if the project file at

d:\project\client\startup.csproj

refers to the source file at

d:\project\engine\utils.cs

then it's likely to do so using two dots; i.e., under the guise of

..\engine\utils.cs

Obviously, appending this relative path to the client directory path

d:\project\client\

yields a perfectly serviceable, though not optimal, source file path:

d:\project\client\..\engine\utils.cs

Trouble is, my earlier directory traversal, building up the dictionary of source files, created the entry for this file using the "key":

d:\project\engine\utils.cs

So in order to normalize keys, I needed to remove the \client\.. portion of the calculated path, making these two identical. Sounds like an ideal job for a wee bit of simple Regex, no? Just remove all instances of a backslash, followed by a bunch of non-backslash characters (the redundant directory name), followed by another backslash and two periods:

return Regex.Replace(input, @"\\[^\\]+\\\.\.", string.Empty); // Bug!

No!

I puzzled for a little while over why the output of this function still contained embedded \..\, before finally adding some debug code and discovering the answer.

Before:

d:\project\client\forms\..\..\version.cs

After:

d:\project\client\..\version.cs

Why hasn't the above code removed \client\.. from this path? Because \client\.. wasn't in the original input string. When it does appear, the Regex.Replace operation (having just removed \forms\..) has already moved beyond that position in processing the input string. And it does not backtrack. Can't afford to, that would be mayhem. Imagine it trying to replace "x" by "xx" with backtracking.

~(∀x)(x is a nail)

I could work around the bug, say by detecting whether any change has been made to the input string, and if so (or rather, while so) re-running the operation. That's clearly inefficient. No, the best thing to do here is accept I've selected the wrong tool for the job - a conclusion you'll reach fairly often with Regex!

Here finally is the smart approach to this problem:

return System.IO.Path.GetFullPath(input); // Fixed.

Regex Tennis

Game History Validation

This example from the Universe of Regular Expressions illustrates a substantial, real world application of the "AB alphabet" type, famous from countless introductions and tutorials. But this example didn't arise at work. It came up while we were relaxing on holiday one summer, and watching Wimbledon. Suddenly I started sketching state diagrams on the backs of Embo postcards...

Suppose during a tennis match we want to record more than just game and set scores; we'd like to record the detailed sequence of points won and lost in each game. So for example, if player A won a "love game" (in which player B failed to score at all), we might record the four points that she won in this format:

AAAA

If instead she lost just one point out of five, but went on to win, then the game will be represented by one of these:

BAAAA
ABAAA
AABAA
AAABA

depending upon whether she lost the first, second, third or fourth point (she can't have lost the final fifth point, since she did win the game). Similarly if she lost two points, well, those could be any two out of the first five points. Applying binomial coefficients, "five choose two" = ten possibilities, and the game's history will be one of these:

BBAAAA
BABAAA
BAABAA
BAAABA
ABBAAA
ABABAA
ABAABA
AABBAA
AABABA
AAABBA

Now suppose we wish to validate such game histories. Can we use a Regex to determine whether a given sequence of As and Bs represents a legal game of tennis? Well, the scoring in any sport can be represented by a finite state machine, so yes, a Regex can certainly validate a game of tennis. But before proceeding, it's worth mentioning that Regex has no built-in support for permutations. That sometimes makes it the wrong tool for jobs like this one, which may have rather long solutions as a consequence. Solution sizes are exponential in the alphabet size, to be exact. Our alphabet has just two letters, so we'll persevere for now.

The examples given so far represent full, legal games. Illegal examples include such things as A, AA, AAA (these games are still in progress), or AAAAB (player A has already won the game before B "wins" that impossible final fifth point). In fact, when taken together with their opposites, i.e. the corresponding cases where B wins instead of A, the foregoing 15 cases already exhaust all 30 possibilities for what we'll call a short game (up to six points). So, by disjoining ( | ) all of the foregoing examples and their opposites, then forcing a full game match by delimiting the result with ^ and $, we can obtain a canonical pattern capable of validating all short games:

^(AAAA|BBBB|BAAAA|ABBBB|ABAAA|BABBB|...|AAABBA|BBBAAB)$

But we can also do a lot better. Here is a rough sketch of the state transition diagram for an arbitrary game. For simplicity, tiebreak games are excluded from this treatment, but aside from the game length, their analysis is essentially the same. Scoring on the diagram proceeds from left to right, except when forced back (arrows) from Adv_A or Adv_B to Deuce. The transition is upward whenever A wins the point, downward when B.

Our so-called short games correspond to all the valid paths through this diagram, from Start to Win_A or Win_B, and avoiding Deuce. It so happens that the analysis used here is better explained in a later part of this problem, so for now I'll just pull out of my hat this improved pattern, which matches all 30 (and only those) short games:

(AAAB?B?A|(AAB|ABA|BAA)(AB?A|BAA)|(ABB|BAB|BBA)AAA
|BBBA?A?B|(BBA|BAB|ABB)(BA?B|ABB)|(BAA|ABA|AAB)BBB)

Next we address the remaining long games. After six equally shared points, the score is "40-40", aka "Deuce". For either player to win the game from this point, she must score a further two consecutive points, making it therefore a game of 8 (or 10, or 12, ...) points in total. Now, applying binomials again, there are "six choose three" = twenty ways to reach this intermediate Deuce state, beginning at Start. This portion of the game history comprises 3 As and 3 Bs, intermixed in any one of these 20 possible sequences.

Divide and Conquer!

Cut the play in half. If there are 3 As in the first half, then there must be 3 Bs in the second:

AAABBB

Or if there are 2 As and a B in the first half, then the second must comprise some combination of one more A and 2 Bs:

(AAB|ABA|BAA)(ABB|BAB|BBA)

And so on. There are only four such partitions, and when we gather them together in a disjunction, we obtain the pattern matching any sequence of play from Start to Deuce:

(AAABBB|(AAB|ABA|BAA)(ABB|BAB|BBA)
|BBBAAA|(ABB|BAB|BBA)(AAB|ABA|BAA))

The long game pattern is completed by tacking on to this stem the playoff stage, in which the winner concludes with two consecutive points. This is simply any number (possibly zero) of AB or BA pairs, followed by a final AA or BB. Converting these words into symbols:

(AB|BA)*(AA|BB)

To obtain the final Regex pattern of a tennis game, take the disjunction of the patterns above for matching short and long games:

(AAAB?B?A|(AAB|ABA|BAA)(AB?A|BAA)|(ABB|BAB|BBA)AAA
|BBBA?A?B|(BBA|BAB|ABB)(BA?B|ABB)|(BAA|ABA|AAB)BBB|
(AAABBB|(AAB|ABA|BAA)(ABB|BAB|BBA)
|BBBAAA|(ABB|BAB|BBA)(AAB|ABA|BAA))(AB|BA)*(AA|BB))

An Alternative Approach

The above is a complete solution, and despite the pattern lengths involved, still a practical one, since these patterns or equivalents can easily be autogenerated. However, the autogeneration process is exactly equivalent to walking through the state diagram. If we can do that, then we already have a finite state machine capable of game history validation.

Class TennisGame below is one example of such a state machine, encoding the scoring rules of tennis games. It has a Play method which accepts one string parameter purporting to be a game history, and returns the validation result as a boolean. Any two adjacent characters can be used for the alphabet, so for example, a game history can be written as ABAAA, or equivalently, as "10111".

public enum Point
{
  Love, Fifteen, Thirty, Forty, Advantage, Win
}

public class TennisGame
{
  public bool Legal { get; private set; }
  public Point[] Score { get; private set; }

  public TennisGame()
  {
    Score = new Point[2];
    Reset();
  }

  public void Reset()
  {
    Score[0] = Score[1] = Point.Love;
    Legal = true;
  }

  public bool Play(string points)
  {
    Reset();
    foreach (var point in points)
      WinPoint(point & 1);
    return Legal && GameOver;
  }

  private void WinPoint(int player)
  {
    if (GameOver)
      Legal = false;
    switch (Score[player])
    {
      case Point.Love:
      case Point.Fifteen:
      case Point.Thirty:
        Score[player]++;
        break;
      case Point.Forty:
        switch (Score[1 - player])
        {
          case Point.Love:
          case Point.Fifteen:
          case Point.Thirty:
            Score[player] = Point.Win;
            break;
          case Point.Forty:
            Score[player] = Point.Advantage;
            break;
          case Point.Advantage:
            Score[1 - player] = Point.Forty;
            break;
          default:
            Legal = false;
            break;
        }
        break;
      case Point.Advantage:
        Score[player] = Point.Win;
        break;
      default:
        Legal = false;
        break;
    }
  }

  public bool GameOver
  {
    get { return Score[0] == Point.Win || Score[1] == Point.Win; }
  }
}

These two approaches are essentially equivalent in terms of not just the infinite set of game histories they'll validate, but also in runtime behaviour. That's because .NET converts regular expressions into finite state machines prior to execution (either at runtime, or when compiled with the RegexOptions.Compiled flag). It is left as an exercise for the student to extend both of these approaches to cover whole sets, matches and tournaments, with and without tiebreakers!

Simple Regex #2: Validation

What's a Valid XML Element Name?

Sometimes we want to convert customer entered data to XML. Sometimes we want to use it for an element name. Obviously it'll need some sanitising, so what should we escape? The XML RFC is a wee bit twisty on this question, its section on Start Tags defining a Name roughly, i.e. ignoring so-called combining characters and extenders, like this:

NameStartChar ::= Letter | ‘_’ | ‘:’
NameChar ::= NameStartChar | Digit | ‘.’ | ‘-’
Name ::= NameStartChar (NameChar)*

That's similar to the definition of an identifier in many languages, but with the addition of a few specific punctuation marks. The twist comes when you consider namespaces. The XML Names recommendation states that these assign a meaning to names containing colon characters, and that therefore, authors should not use the colon in XML names except for namespace purposes. Even though XML processors must still accept the colon as a valid name character, as per the above syntax, it gives off the odour of a practice to avoid. So we go with this:

NameStartChar ::= Letter | ‘_’
NameChar ::= NameStartChar | Digit | ‘.’ | ‘-’
Name ::= NameStartChar (NameChar)*

No Colons Then?

That's right. Our element names start with a letter or underscore, then continue with any number of these, possibly in combination with digits, periods, and hyphens. To put it another way (inexactly, but in practice acceptably, for my purpose): an element name is any nonempty sequence of word characters (letters, numbers, underscores), periods, and hyphens; and it must start with either a letter or an underscore.

In the interests of localization, rather than the parochial a-zA-Z_0-9, we should use the Regex word character class \w to represent, erm, word characters. That just leaves the period and hyphen to be mopped up in the main sequence. Similarly, when it comes to specifying the initial letter, rather than a-zA-Z, we should use the letter class \p{L} built for just this purpose:

private static string ToElementName(string input)
{
  // Replace all non-hyphen/period/word characters with underscores.
  var result = new StringBuilder(Regex.Replace(input, @"[^-.\w]", "_"));
  // If input doesn't start with a letter or underscore, prepend an underscore.
  if (!Regex.IsMatch(input, @"^[\p{L}_]"))
    result.Insert(0, '_');
  // Done.
  return result.ToString();
}

A point to note about the first pattern [^-.\w] is that neither the hyphen nor the period need be escaped. Within brackets, the period represents itself, rather than being a wildcard; and the hyphen is similarly literal (as opposed to indicating a range) when it appears as the first item in a set.

Other Useful Character Classes

Why yes, there are some others, I'm glad you asked. These two are probably the droids you're looking for: \p{Lu} for uppercase letters, and \p{Ll} for their lowercase comrades. For the full story about Character Classes in C#, go to http://msdn.microsoft.com/en-us/library/20bw873z.aspx.

Simple Regex #1: Metacharacters

Useful Concepts: Opacity

Oh sure, I know there's no shortage of guides to regular expression on these Internets. However, questions about them continue to land on my desk with a satisfyingly fitting regularity. So I've decided to write about them, starting with this one. Colleague C wants to parse some data from Discogs, the music database / marketplace. Credits on individual tracks follow a comma separated format like this:

Piano, Guitars [Lead, Bass, 12 String Acoustic], Drums, Kitchen Sink

followed by the artist's name. What C wants to do, is to parse each individual instrument or grouping of instruments, ending up with something like this:

Piano
Guitars [Lead, Bass, 12 String Acoustic]
Drums
Kitchen Sink

Obviously the "wrinkle" is that bracketed sections can contain commas, which we don't want to act as field separators. In fact (and this is key to the answer), we don't care at all what's inside the bracketed areas. Everything after a left bracket, up to and including the first right bracket if any, should be preserved just as it is. Such is frequently the situation with string encodings; separators and terminators are implicitly "escaped" when parenthesised. We may also term such bracketed content "opaque", meaning that our parser "cannot see inside it" - to discern, for example, those commas.

My First Metacharacter

That being the case, we might as well treat an entire bracketed expression as a single, inscrutable and indivisible (meta)character. One example of a pattern matching such an expression is:

\[[^\]]*]

which is to say, a literal left bracket "[", followed by any number of non-"]" characters (the sub pattern for such a sequence is shown underlined), followed by a final right bracket "]". For the sake of clarity and language independence I'll be omitting pattern delimiters in most of my examples; you should add your own enclosing @"" or // as appropriate for your environment. Now we can say that each match in our output is a sequence of atoms, where every atom is one or other of these:

• any single character, which is neither a comma, nor a left bracket;
• a bracketed expression, as recently defined above.

Here then is the pattern that matches one of our newly identified atoms:

[^,[]|\[[^\]]*]

Note the use of the OR operator "|" between the two underlined sub patterns for matching (1) a single character, and (2) a bracketed expression. Now, a match can be expressed as a sequence comprising any number of atoms:

([^,[]|\[[^\]]*])*

Here the underline spans a single atom. If we now test this solution, we find that it has two bugs. It intersperses zero-length matches between the desired ones, and it preserves spaces after commas in the input string, manifesting these as leading spaces in the second and subsequent output matches. Both issues can be addressed by insisting that a match additionally starts with at least one non-comma, non-space character (prepended and underlined below):

[^, ]([^,[]|\[[^\]]*])*

And that, assuming only that bracketed expressions aren't nested, is one final answer to the case of the Discogs Parsing Regex.

Previously: Regex Fuzzing; Quantum Regex.