Justin's Regex Blog

Examining the data flow model of using DateTime as a Parser for Dates

2004-08-15T01:55:00Z

Yet another diagram here. This time we get to see some differences between a parser/validator model where the pieces are separated for purposes of providing enhanced user feedback and more specialized return structures. The end result is that we are able to provide many more services with about the same amount of work. This is the best all-around option because it means a relatively small amount of code, requires the least amount of end-user knowledge (even less so than the regular expressions option), and the abstract mapping is appropriate for nearly any programming language.

User Input:
You start to see the first benefits to a parser/validator model in that the input can now take multiple formats. In general parsing a string into a date not only involves make sure the string is in the appropriate format, but also checking the numeric values of portions of the string. The string parsing model still exists through the use of the Parse or ParseExact method, but there are other options. You can specify already parsed integers when creating a DateTime or optionally pre-split string portions. You'd never enable these features through expressions because you'd wind up coding multiple expressions, processing the strings into integers earlier in the data flow model, and wrting a bunch of code to select which expressions to use for validation. Not that you couldn't enable these features, just that it doesn't buy you anything.

Parse:
I put some range checking notes under parsing. This happens because of basic validation of month, day, and year ranges that occurs during the parse or construction phases of a DateTime. If you were writing a light DateTime parser what you might do is leave the range checking in, but rather than throw exceptions provide more feedback. The nice thing about the DateTime integrated range validation is that as the values are parsed into strongly typed integers and a basic range check is done rather than working at the character comparison level.

The parsing of a DateTime is much faster than the character level parsing of a regular expression even though more work is being done towards the end result in terms of getting the data from the least usable format (a string of several values) to the most usable format (a numeric type). In fact even with conversion in place the parsing is much more functional (the possibility of more format strings) and robust.

Result:
Unfortunately the result of a parse or constructed DateTime has onl two possibilities. Either you get a somewhat valid date returned (still needs additional validation) or you get an exception. If you get the exception it is just like a false return value from the Expression processor. To avoid the exception a TryParse in Whidbey will return a boolean true/false depending on parsing success or failure. You still get the same strongly typed parsed results, just without the exception in the failure case.

The result here is massively different from an Expression result. The reason is that each field is now in a numeric format and has been preconverted. It is ready for work to be done, since undoubtedly you'll want to do some work. It is also in the most optimal storage format in terms of size. If you get to this point there were no parsing errors, but there may still be other invalid ranges within the dates.

Validate:
Some of the validation has already occured in the parsing phase, but the extra validation comes in now. By using the strongly typed results you can quickly perform comparisons on the fields to remove days that never existed within a particular calendar. In fact it becomes possible to chain various validators on the end of the process depending on the level of checking that needs to apply. We have several options at this juncture. We can enforce historical accuracy by removing various days that are valid at the parser level but shouldn't be allowed at a historical accuracy level. We can also enforce programmatic ranges such as only allowing dates after 2000.

Each validator in the chain gets a chance to flag an error. This can provide the user with great granularity in user feedback.

User Feedback:
Tell the user where the process failed. There is a lot of work happening on the date and a number of different things that can go wrong. Arguably if you are only asking for a basic date or you expect your users to be smart maybe this doesn't matter to you. However, if you are enforcing odd constraints, such as historical accuracy then user feedback becomes much more important.

Even more important than giving the feedback to the user is having the ability to give the user the feedback. You might use a once over expression to give you a true/false, but that result doesn't allow you to determine enough information to figure out why. In fact you'd have to reparse the string again just to figure out why. Documentation doesn't fix this problem because if I give you a list of ten things that go wrong, but I only give you enough information to tell you that ONE of them went wrong, you still have to figure out which of the ten happened. Originally the .NET Terrarium just told you if your assembly was valid or invalid, but it didn't tell you why. We added reporting because there are about 15 different things that can happen. This allowed us as programmers to test the validation logic. It also allowed end users to fix their own creature code by telling them exactly what was wrong with their code.

Conclusion:
We are almost to the point of having a truly functional date-time parser. At this level there is still a black-box at the parser level. We can't get an internal peak at which values are missing at the parser level nor do we get a look at the range checking. It would be nice to extend these values to the user. After all, we are doing the range checking already, we are doing the work in order to fail the parsing, there isn't any reason once the parsing has already failed not to give an indication of the condition of failure. A light date-time parser is next. This is a true parser and it gives actual feedback at all steps in the process. From an end-user perspective it is the most functional. It is also most functional as a reusable component for developers because it provides them the fastest parsing with more feedback than any of the other methods. The trade-off is programming complexity, but I can assure you that basic parsing routines require only the most basic programming constructs. There won't be anything strange in this process whatsoever.

Examining the data flow model of using Regular Expressions for Dates

2004-08-14T20:18:00Z

I think some diagrams are going to be extremely important for examining the problems of using regular expressions for validating and parsing dates. Especially as you start to rely on more and more complex and time consuming operations to validate additional constraints. The following diagram is what I call the Expression Data Flow Model for Dates. It isn't complex, it just shows the abstract processing from user input to result all the way through processing. I'll use the various blocks to talk about each step in turn. I've also provided a sample run of a sample input and expression along with the result and processing the output.

User Input:
This is where the user is sending data through your data flow pipeline. By using a regular expression you limit yourself to processing string input. This isn't all that bad since most date and time input on the web is done through a textual or string based field. More recently models have changed to supplying the user with a calendar input. Under these scenarios you can toss the expression out altogether and process the separated UI components of the calendar control itself.

You'll see how separating the paser/validator logic later will enable us to short-circuit several of the steps involved in the data flow model.

Expression Block:
The expression is a parser, as it will be splitting portions of the input string and placing them into groups (aka variables or fields). It is also a validator because it is verifying that specific characters are digits and possibly digits within specific ranges. It also verifies digit counts, separator characters, etc... If you want to add additional validation logic it has to be placed into the expression itself. Without ingeniously designing the expression the result or output is going to be very fixed with respect to the amount of information you get back.

Result:
Once the expression has run you get a single boolean result value of true/false to determine if the pattern was successfully parsed AND validated. You don't know what part of the process failed, only that it failed. There are no partial groups filled so you can't verify that it failed at a specific location in the expression (without ingeniously engineering the expression).

If the pattern does succeed then you have a number of groups or captures that identify the results. Notice that the entire match is stored in group 0 while your capture groups are stored in 1 through 3. The problem that you'll face is that you've ALREADY validated the digits using the expression, you basically performed more than half the work of converting the digits into an actual strongly typed piece of data, but it is STILL returned to you as a string. If you want to continue moving forward and working with the fields themselves you have to do some processing.

The point I have been trying to make with user feedback about expressions comes into play here. You'll notice that we can only tell the user (because the parser and validator is a black box) that the pattern was successful or not. We have no clue why the input failed. We can't identify that it failed for a critical reason like an invalid pattern (failed parsing) or whether it failed for a data and logic reason (a date that doesn't exist in history). Imagine for instance you started at site that published the history of the world and the user is inputting dates to try and find data. On your site, some dates just won't go in and the user can't figure out why. They go to google and search the same date and magically results appear. For dates that don't exist there are sure a lot of pages with information that happened on those dates. The reason? Well, not everyone in history gave a hoot that the calendar was changing and much of written history is overlapped with stuff that happened on dates that technically didn't exist.

Processing:
At the end of the data flow model you can't just keep a date around in the original string based form. A simple date with a 4 digit year is stored using 10 characters or 20 bytes, 10 if you are on a non-Unicode system. However, you really don't need that much information for a date. Without an associated time it will easily encode into a single integer. If you start parsing times then you'll need to use up to 8 bytes. The nice thing about the 8 byte version is that it is fully parsed and encoded. The information is retrieved using a series of quick mathematical transforms rather than having to reparse the string to get information.

If you plan on using the date then you need it in some form where you can work on the members. After all, you can't add easily add days, months, years, or do any sort of transformation on the results of the string in expression form. Some users may point out that JScript allows you to work with the groups as if the underlying capture were actually an integer but this is simply foolishness in not understanding that every time you do that a conversion is being made on your behalf. That means once you've already validated the data once you have to validate it again using conversions since a conversion is nothing more than a validation of the underlying string to see if it has an associated strong typed integer representation. Just doesn't seem to make much sense does it?

Conclusion:
The data flow model for parsing dates with expressions is bleak because you wind up spending a large amount of time parsing and validating inside of the expression itself only to do a large amount of additional processing after the fact. Michael has pointed out that existing methods for parsing often don't give much feedback either. With that in mind, we'll examine the data flow model and the additional feedback provided by using an existing parser with a supplementary validator. You'll see how converting data as you parse it prevents extra processing later and how deconstructing the black-box of the parser/validator that is a regular expression will enable you to start providing more feedback.

Performance: Character Classes versus Alternation Groups

2004-08-14T07:53:00Z

If heated discussion with Michael Ash keeps resulting in this sort of performance break-through then I'll argue with him every day of the week. To follow the performance examinations you are going to have to make sure that both Compiled and ExplicitCapture are on. While it might be nice to also check the interpreted speed, I can imagine that when running in interpreted mode, most of the speed enhancements of the alternation group are completely lost.

Let's start the process by examining the process of matching the inputs of 10 and 12. First we'll do what I call finger matching using a character class. The expression we'll use is 1[02]. Finger matching looks something like this, though having some images would be better, I don't have the time to make them.

Op #: Description
Op 1: Input[0] = Pattern[0]; // Input = “11” for now
Op 2: Fail or Scan; // Fail on no equal, Scan next char on equals
Op 3: Setup Character Class Match; // Here we do math to set up a binary search
Op 4: Input[1] = CharClass[1]; // Because we have two elements 0 and 1, we'll try to match first 1 then 0
Op 5: Succeed or Input[1] = CharClass[2];
Op 6: Succeed or Fail;

Now, don't let the number of operations confuse you. Just because the character class matching looks really fast, it involves setting up a call stack, calling a method, scanning through a string representing the character class itself, and finally returning some true/false value. That can be costly, especially compared to branch and comparison statements. That puts us at an alternation group that does the same thing. It looks something like this 1(0|2). Remember that explicit capture is on. If not, you'll kill your perf. If you don't want explicit capture then at least prevent capture using 1(?:0|2):

Op 1: Input[0] = Pattern[0];
Op 2: Fail or Scan
Op 3: Input[1] = Alt[0][0]; // First alternation group, first check
Op 4: Succeed or Input[1] = Alt[0][1]; // We reach the comparison or success through a branch statement. Fast!
Op 5: Succeed or Fail

There is only one less conceptual operation, but several hundred less machine operations. We find that in the compiled scenarios running a worst case scenario match (aka a match that won't be found in the alternation group or character class) will examine the performance potentials. Here is the code for running against the digit class and the lower case character class (note that going against the lower case word character class is even slower because of Unicode support, so we use an explicit character class).

Regex regex23 = new Regex("^1\\d$", RegexOptions.Compiled | RegexOptions.ExplicitCapture);
Regex regex24 = new Regex("^1(0|1|2|3|4|5|6|7|8|9)$", RegexOptions.Compiled | RegexOptions.ExplicitCapture);

Regex regex25 = new Regex("^a[a-z]$", RegexOptions.Compiled | RegexOptions.ExplicitCapture);
Regex regex26 = new Regex("^a(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)$", RegexOptions.Compiled | RegexOptions.ExplicitCapture);

If you are going to run these under a performance scenario then the use string “1a” for the first pattern. This will match the start of the pattern, and then fail matching the remaining required digit. For the alternation group this will mean 10 branch comparisons. For the character class it means 3 comparisons and the setup of the call-stack. For the other pattern, use “a1” and the same thing will happen. Run them once outside of the loop to get the grease rolling. This makes sure all of the methods are JIT'ed. This is important. Lots of people don't prime the pump, but you need to make sure and call every method at least once and that means possibly exercising hundreds of code-paths in complex scenarios to make sure the perf results don't include JIT time.

// Compile the Shiznut
regex23.IsMatch(Data11);
regex24.IsMatch(Data11);
regex25.IsMatch(Data12);
regex26.IsMatch(Data12);

start = DateTime.Now;
for(int i = 0; i < 10000000; i++) {
    regex23.IsMatch(Data11);
}
end = DateTime.Now;
Console.WriteLine("Character Class [0-9] Elems {0}", end - start);

start = DateTime.Now;
for(int i = 0; i < 10000000; i++) {
    regex24.IsMatch(Data11);
}
end = DateTime.Now;
Console.WriteLine("Alternation Group (0|1|2|3|4|5|6|7|8|9) {0}", end - start);

start = DateTime.Now;
for(int i = 0; i < 10000000; i++) {
    regex25.IsMatch(Data12);
}
end = DateTime.Now;
Console.WriteLine("Character Class [a-z] Elems {0}", end - start);

start = DateTime.Now;
for(int i = 0; i < 10000000; i++) {
    regex26.IsMatch(Data12);
}
end = DateTime.Now;
Console.WriteLine("Alternation Group (a|b|...|y|z) {0}", end - start);

Just a basic set of loops. We are using IsMatch here rather than Match. Match creates some additional objects on the stack and we want to minimize the amount of memory thrash. The results are interesting to say the least. I am displaying the closest set of runs that I was able to capture giving the character class the benefit of the doubt. In my testings the character classes were very iffy in their results and timings fluctuate wildly. For the alternation group the timings are much more stable. I imagine the extra stack thrashing for character classes might have something to do with this timing difference.

Character Class [0-9] Elems 00:00:02.5636864
Alternation Group (0|1|2|3|4|5|6|7|8|9) 00:00:02.3533840
Character Class [a-z] Elems 00:00:02.4334992
Alternation Group (a|b|...|y|z) 00:00:02.3834272

Now with this knowledge, that alternation groups are somewhat faster, you can do some more work to get even better results. For instance, you can order the precedence of characters in the alternation group to more closely resemble the density of characters that you are matching against. For the english language this might mean matching vowels in the beginning. You'll get huge perf wins whenever the alternation group has a character matching a character in the input, but still nothing when the character is outside of the range.

There is one note. A huge peformance gain exists that isn't being taken advantage of. A linear character class such as [a-z] can be turned into two boundary checks. This would certainly save a lot of time. A complex class such as [0-9a-zA-Z] could be turned into 3 such boundary checks. Maybe Kit will grace us with a view and put this on a possible future performance improvement list. While this won't work for complex character classes especially those that are unicode aware, it does work for user specified classes.

Expressions, Parsers, Validators, User Feedback and the tradeoffs we make.

2004-08-11T01:04:00Z

While the traffic has a local nature to regexadvice.com/blogs, there has been a lot of examination of various expressions where a date processing expression has become the topic of note. Personally, I have huge problems with constantly having a date expression tossed out as an example. Primarily the expression is monolithic and already starting to breach, in terms of complexity, the barrier of usefulness. Second, because of its huge nature, and the large amount of time the original author took to create the expression, working with it to prove or disprove discussion is tedious and time consuming, almost not worth it. I'll take a short moment to lay in cement some ideas I have about the usefulness of regular expressions as validators.

Expressions:
Let's start with expressions. Expressions, while they appear light on the surface, are nothing more than generic parsing routines. Each element you place in the expression string is translated into string tokenizing and comparison routines. This is no different from writing in a computer language to give the computer instructions as to what to do. Expressions are a language in and of themselves and the complexity of the underlying implementation simply goes unnoticed. If you've checked any of Darren's or my posts on lexing and parsing you've gotten a sneak peak at what goes on behind the scenes in a regular expression engine.

Parsers:
Parsers are hard-coded routines for examining underlying data. If we take the date-time expression we can convert it into only a few lines of parsing code, definitely less than 30 even if we are very verbose. In fact the number of characters (not lines) in the final parser program is actually shorter than the date expression Michael Ash has posted. His does some extra work though, namely validation, so we'll get to that in a second. Underlying every expression is a highly optimized generic parser, but no generic parser can run at the same speed as an optimized specialized parser. It just can't happen. You can compile expressions under .NET and in some cases the resulting code is more specialized and runs much faster, but it still uses the underlying syntax and semantics of the expression engine which may still create some slow-downs.

Validators:
After a parser is complete the data it retrieves needs to be validated in many cases. The date routines have a number of conditionals that validate certain date regions that never actually existed as calendars were changed to support new knowledge of the movement of the Earth around the Sun. These validations run as assertions, and as soon as an assertion is met the expression is failed and the user is given a boolean feedback as to whether or not the date is valid.

Now, how many of you know the list of invalid date combinations between 1AC and 9999AC? I can definitely say that I don't. Validators are in place so that once the specialized parser is complete the values retrieved can be checked against lists or functions of valid or invalid values. The result is to provide feedback to the user in some form or another.

User Feedback:
The end result of parsing and validation is generally user feedback. The reason I can't stand behind monolithic boolean result expressions is that they don't tell the user what was wrong with the input. If there is a date range in the 1500's that is invalid because of a calendar change then the user needs to be made aware. By all modern calendar rules the date would be valid, but the dates disappeared from history and the user needs to know this else they'll find something wrong with your parsing/validation logic.

This brings up two types of validation. The first type of validation is the validation you perform on user input. The next is the validation the user performs when working with your software. If you don't give a reason why the user is wrong, the user will think that you are wrong. They'll think that your stuff is broken. Further, if you don't give real feedback about why the input is invalid the user can't double check you. After all, if you tell them why they are wrong, but they verify the input is actually valid, then they can notify you of errors in your own program. As Michael has pointed out, he has had many issues with various regular expression engines handling different clauses in different ways. At the end of the day I can't honestly say I'd feel safe using the expressions because of their complexity, their lack of feedback to the user as to what EXACTLY is wrong with the input date, their required support of an underlying regular expression engine, their reliance on complex features, and the fact that a specialized parser does the job faster, more accurately, and with more feedback potential.

Trade-Offs:
What are the trade-offs between parsers and expressions? Well, supposedly expressions are easy to use (not generate, but use), are compact, and are portable between multiple expression systems. However, this isn't necessarily the case. The one thing that expressions do for the user is generate parsers and validators of data without understanding the underlying technology of parsing and validating data. It is a tool-set and an abstraction.

In the end, the trade-offs are going to be:

Speed - The speed of running the parsing and validation logic are going to be much faster when written in shear code.
Portability - Basic parsing code is extremely portable and can be quickly translated between languages. Expression engines are expected to live up to a spec, but general and widespread implementations often differ in small details.
Complexity of Validation - Basic validation in an expression can often require specialized constructs. You often sacrifice the level of validation you can perform.
Feedback - This is the most important feature of any validation. You have to give the user proper feedback so they can either fix the string or find errors in your validation logic. Feedback is almost always platform specific and doesn't integrate well with complex validation rule-sets inside of a single regular expression.

Quote of the Post - Use the appropriate tool for the job by identifying solutions that solve all end user and programmer related problems.

What does conditional matching really mean in a regular expression?

2004-08-10T06:02:00Z

Darren recently drew an example, but even though I'm Regex adept, I didn't find his meaning Conditional Matching. He basically shows a way to match Thur in Thursday or Thurday, but then if there is an s, make sure that day also follows. Now I would assert that you can tell what a regex is supposed to do by listing all of the things it matches. Turns out that his expression will either match Thursday, Thurs, or Thur. I don't know what his intention was, but I can talk a bit about what the conditional syntax buys you...

Let's start by taking a look at what might be a possible single level nesting block capture expression:

^\s*({)?(?(1).+?}|.+?$)

This is designed to match two types of statements. Single-line statements that match all of the characters on a single line, or nested blocks that exists between matching french braces. It isn't built for multiple levels of nesting, but instead just a basic pattern.

Foo
Bar
Baz
{
    Foo
    Bar
    Baz
}
Foo
Bar
{
    Foo
    Bar
    Baz
}

Now this appears to be an excellent reason to use conditional matching. First, we look for an opening brace. If we don't find one then we process one line of input using the else clause. If we do find one then we process the if clause. How would this look as a normal expression though? Can we gain any insight by looking at an expression that does the same thing without the use of the conditional? I sure hope so because it speaks volumes about what a conditional clause really buys you.

^\s*([^{].+?$|{.+?})

Above is one version of a possible expression. We specify an else clause by guaranteeing our condition won't be true. We'll match any character except for an open brace and then begin to match a single line statement. As for the if clause, it is simply rewritten as the second part of the alternation group. If the first character doesn't match the negative character class containing only the open brace, then the open brace must be there and we match it. This just shows off a basic if then. Basic if thens can always be turned into a two element alternation group.

You start to see more where conditionals are useful when the space between the match group (condition) and the conditional expression grows either large or complex. Anything that exists between the conditional has to be repeated within the expression. We'll call this the BEGIN..END expression.

^(BEGIN )?[a-zA-Z0-9][_a-zA-Z0-9]*\$[^\$]+\\)(?(1) END)\\s*$

The BEGIN..END is optional in the expression, but as soon as you add one, you have to also add the other. The END is required whenever the BEGIN is seen. How would you build this requirement in using alternation groups? Well, you have to repeat the middle pattern. The bigger the pattern gets between the condition and the conditional the more pattern you need to repeat. In the above sample this can mean quite a bit.

^(BEGIN [a-zA-Z0-9][_a-zA-Z0-9]*\$[^\$]+\\) END|[a-zA-Z0-9][_a-zA-Z0-9]*\$[^\$]+\\))\\s*$

That makes conditionals pretty darn nice in my book since they save you a bunch of typing. Using the same conditional multiple times still reduces into a single alternation group. So a bunch of extra work isn't apparent in this scenario. Adding more than a single conditional has some very negative impacts on the final expression. You can either increase the number of alternations exponentially or linearly depending on how the conditionals are organized. Maybe I'll get into that complexity another time. A quick summary follows:

Conditionals allow you to select between up to two patterns based on the match success of previous patterns.

Conditionals can be dependent on either a previous numbered or named match group or on a pattern that is specified as the conditional.

A single conditional can be rewritten as an alternation group with two patterns.

The true or left pattern is normally a combination of the optional match group, the intermediate pattern, and the if clause

The false or right pattern is normally a combination of the intermediate pattern and the else clause

A single conditional used multiple times in a pattern can still be rewritten as an alternation group with two patterns

Multiple conditionals in the same pattern can increase the number of alternations linearly or exponentially or a combination of both

A conditional with a second conditional in the if clause increases linearly from 2 to 3 alternations

A pattern with two separate conditionals increases exponentially from 2 to 4 alternations (think binary truth tables)

The not so basics of NOT!

2004-08-06T05:50:00Z

It is very easy to build a regular expression that matches a particular pattern, but not one that matches the absence of a pattern. Thankfully we've been given some tools in the form of assertions that make the ability to perform a NOT operation quite easy. Let's start by looking at the negative lookahead assertion using a pattern that has been in hot discussion lately over on Darren's blog The sugary synax we love... Lookaround .

The pattern matches &, in order to escape it as &, but it doesn't escape the & if it is already part of an entity escape.

&(?!lt;|rt;|amp;)

We used the negative look-ahead to match all ampersands that aren't followed by an entity. Not too hard at all. The NOT in this case means look for specific items and fail the match if they exist. Along with the negative look-ahead assertion there is an equivalent look-behind assertion. With it you can match all patterns that aren't in turn preceded by something.

Now, let's talk about the other forms of NOT that we are given with regular expressions that aren't related to assertions. First off we can build a negative character class group. This allows us to match all but a certain set of characters. If we wanted to begin building a simple version of the assertion pattern, we might at least make sure that the next character following the & wasn't an l, r or a.

&[^lra]

Now we are matching all & that are NOT followed by the l, r, or a... If we continue building the pattern out we can even use character classes to form complex NOT operations for entire strings and groups of strings.

&($|[^lra]|a[^m]|am[^p]|amp[^;]|[lr][^t]|[lr]t[^;])

We've now constructed an identical pattern using the character class NOT operator to perform the same operation as the negative look-ahead assertion. If you look at the comments in the post I've referenced you'll also notice a third syntax I use for creating a NOT operator, and that is to optionally match something and then only if it matches try to match an impossible character.

&(?(lt;|rt;|amp;)^)

The above pattern tries to match a beginning of string character if it finds any of the patterns or literals we don't want to follow the & character. Since we shouldn't be able to match the start of string it will cause the expression to fail and the conditional will act like a NOT operator.

Hopefully you've found some of this interesting, then again maybe not. Each tool in a regular expression can be viewed as a hint at how the pattern is going to operate. Some of the tools affect the string scanner (such as assertions that do a forward or backward scan based on the current stream offset) others control backtracking and greediness. By manipulating the tools and understanding how they work you can make the most performant expressions.

Have you ever dreamed a problem? Two nights in a row now, no sleep for me I guess...

2004-05-26T12:56:00Z

When I get really zoned in on a problem I can't sleep, or rather I do sleep, but it seems that somehow the topic in my head becomes the makings of some really interesting dream. I've always had mild insomnia, so I'm capable of sleeping and dreaming right on the edge of the asleep/wake border. I've often found myself with an actual dream continuing even as I wake up and become conscious enough to do stuff around my house. Definitely not something I recommend to others.

My point? Well, I kept thinking about this problem of decomposing the ranges into expressions. ALL NIGHT. My brain kept telling me that some additional items would be nice to add. Namely, the creation of range coverage print-outs for each of the generated range decompositions (if you note the ranges are doing things like covering 0-9, then 10 through 99, then 100 through 999, etc... That is the way things get decomposed. Unfortunately doing it this way does leave one single spot for error. A number such as 001 will match \d?\d?\d. If you wanted something that threw on leading zeros, you'd have to add more to the expressions.

Since they break down this way, it becomes easy to take our expressions and turn them back into the ranges that they would match. I'm not talking about the standard ranges of say 0 through 5000, but the actual saturation ranges of 0 through 9, 10 through 99, etc..., so you know that every inch of your range has actually been covered and that your algorithm isn't screwing up.

The second thing I kept coming to was the concept that merging two ranges wouldn't be that hard, or merging N arbitrary ranges. The concept would be finding any ranges that overlap, and then merging their contents to produce a new match group that would match the expanded range or set of ranges. Then I thought, hell this is nothing more than a subset of set theory. I think that was the point I was trying to make. You see Darren has been wanting a way into set theory, and I think he found it. Each of the expressions we are forming denotes a set, and the key is to find if all members in the set defined by the range are also present in at most one other set that represents are decomposed expression. Note the keywords there.

X is our target number X is in the set of { rangestart..rangeend }
Y is our expression Y is the superset of all sets { decomposed1..decomposedn }
All T in X must be a member of Y additionally all T in X must be a member of at most one decomposed and not more
All T not in X must not be a member of Y

Y is just a cute way of aliasing the set X, or is it? Your Y is based on your decomposed expressions, so it becomes possible for Y and X to be different sets. In fact, if you are using optional matching Y may match string representations of integers that don't exist in the integer set X. However, Y and X will still have the same footprint if viewed in the light of integer value only. After all, there is an int.Parse somewhere in the implementation and outside of the theory.

Still looking for a darn math mark-up tool. I've seen the MathML crap, but it requires a specialized viewer. There are a couple of math packages that export in HTML and maybe those would work. I'll have to keep my eyes open and find something, since the above looks a lot better in set notation than it does in written out verbose American English.

Added some extra features to my algorithms, and so I'm posting an input batch file you can use for testing your own.

2004-05-26T00:50:00Z

The batch file echo's expected output, along with the ouput of the program you are running. If your output is different then you might have some code refactoring to do. As soon as I get some algorithms from third parties I'll post my full algorithm. I expect an algorithm from Darren shortly ;-)

Batch file for testing your regex range generator.

Thanks to Darren, I had to examine the process of neg-pos neg-neg ranges in addition to what I was already doing.

2004-05-25T06:46:00Z

Negative ranges are actually quite easy to implement. There are a couple of options:

Parm1 +, Parm2 +
Parm1 -, Parm2 -
Parm1 -, Parm2 0
Parm1 0, Parm2 -
Parm1 +, Parm2 0
Parm1 0, Parm2 +

6 options isn't that bad. We also have relative equality, but we'll get to that. So we have some new scenarios. The first is a parm1 being negative and parm2 being neg or 0. This is basically a postive range with a negative symbol attached:

return "-" + BuildCaptureForRange(Math.Abs(range1), Math.Abs(range2));

Next we have parm1 still negative with the absolute value equal to parm2. This is the cast of -500 through 500 and we want to special case it by making an optional negative symbol.

return "-?" + BuildCaptureForRange(0, range2);

The final special case is that we have a negative and postive value. This is basically two ranges, one from 0 to Abs(parm1) and one from 0 to parm2. We switch between the two cases using a conditional expression of (?(-)-(neg range)|(pos range)).

return "(?(-)-" + BuildCaptureForRange(0, Math.Abs(range1)) + "|" + BuildCaptureForRange(0, range2) + ")";

Note that I've minimized the number of special cases by pre-sorting parm1 and parm2 by value to make sure the lesser value is always in the first local. I also have a special case (value) whenever range1 is equal to range2. The overall code appears to be:

// quick return for simple ranges
if ( range1 == range2 ) {
    return "(" + range1 + ")";
}

// Swap the min/max values
if ( range1 > range2 ) {
    int temp = range2;
    range2 = range1;
    range1 = temp;
}

if ( range1 < 0 && range2 <= 0 ){
    return "-" + BuildCaptureForRange(Math.Abs(range1), Math.Abs(range2));
} else if ( range1 < 0 ) {
    if ( Math.Abs(range1) == range2 ) {
        return "-?" + BuildCaptureForRange(0, range2);
    } else {
        return "(?(-)-" + BuildCaptureForRange(0, Math.Abs(range1)) + "|" + BuildCaptureForRange(0, range2) + ")";
    }
}

Now that I've completed my Darren Task I can probably go to bed. You can't mention something to me and not expect some code the next day (hour or maybe even minute). For testing, I'm including a sample batch file for you to run over top of your own algorithms:

@echo off
BuildRangeGroups 5 255
BuildRangeGroups 222 228
BuildRangeGroups 699 700
BuildRangeGroups 699 701
BuildRangeGroups 699 710
BuildRangeGroups 698 710
BuildRangeGroups 7650 7710
BuildRangeGroups 50 7710
BuildRangeGroups 6998998 7000000
BuildRangeGroups 7000 7999
BuildRangeGroups 7555 7999
BuildRangeGroups 1000 11000
BuildRangeGroups 0 69989
BuildRangeGroups -500 0
BuildRangeGroups -500 500
BuildRangeGroups 0 -500
BuildRangeGroups 500 -500
BuildRangeGroups -50 7710
BuildRangeGroups -1000 69989
BuildRangeGroups 0 1000
BuildRangeGroups 0 255
BuildRangeGroups 0 5000
BuildRangeGroups 0 11000

Along with the required output so you can validate that your algorithm is complete. If you only want to implement part of the algorithm, then that is fine. Nothing requires that you implement the entire thing. Just use the expressions below as reference. Also, let me know if you think there is a range of specific note that might cause issues with a generator or even if some of my generated expressions below are inaccurate.

(25[0-5]|[5-9]|2[0-4]\d|1?\d\d)
(22[2-8])
(700|699|[7-6]\d\d)
(699|70[01]|[7-6]\d\d)
(710|699|70\d|[7-6]\d\d)
(710|69[89]|70\d|[7-6]\d\d)
(7710|770\d|76[5-9]\d|7[7-6]\d\d)
(7710|770\d|[5-9]\d|7[0-6]\d\d|[1-6]?\d\d\d)
(7000000|699899[89]|6999\d\d\d|[7-6]\d\d\d\d\d\d)
(7\d\d\d)
(755[5-9]|75[6-9]\d|7[6-9]\d\d)
(11000|10\d\d\d|[1-9]\d\d\d|\d\d\d\d)
(699[0-8]\d|69[0-8]\d\d|6[0-8]\d\d\d|[1-5]?\d?\d?\d?\d)
-(500|[1-4]?\d?\d)
-?(500|[1-4]?\d?\d)
-(500|[1-4]?\d?\d)
-?(500|[1-4]?\d?\d)
(?(-)-(50|[1-4]?\d)|(7710|770\d|7[0-6]\d\d|[1-6]?\d?\d?\d))
(?(-)-(1000|\d?\d?\d)|(699[0-8]\d|69[0-8]\d\d|6[0-8]\d\d\d|[1-5]?\d?\d?\d?\d))
(1000|\d?\d?\d)
(25[0-5]|2[0-4]\d|1?\d?\d)
(5000|[1-4]?\d?\d?\d)
(11000|10\d\d\d|\d?\d?\d?\d)

And I thought I was done. Reducing certain cases to optional captures is easy, others are more difficult...

2004-05-25T04:52:00Z

Optional captures come into play when the minimum range value has fewer digits than the maximum range value. Let's take a look at some ranges that exhibit the behavior so we have a base with which to work from. The first range is a familiar one, and is the byte range of 0 - 255:

25[0-5]
2[0-4]\d
1?\d?\d (match any 1 digit number, optionally any 2 digit number, optionally any 3 digit number starting with 1)

To examine the complexity of making an arbitary rule out of the above, let's see what happens when you add the range 5-255:

25[0-5]
2[0-4]\d
[5-9]
1?\d\d

So now that we have a single digit lower range, we now add at least 1 new capture. When this happens, we move the optional clauses 1 left. A simple shift. That isn't too bad. Since we don't get a huge amount of simplicity when using the optional captures, I don't see much of a reason to implement them. Adding them for the basic case of the lower range being 0 isn't bad though and only changes the basic algorithm by some small amount. How many optional captures will there be? Max(0, MaxDigits - MinDigits - 1)... In the case of a lower range of 5 and upper of 255 this becomes Max(0, 3 - 1 - 1) or Max(0, 1) or 1 optional capture. Looking at 0 to 255 this becomes Max(0, 3 - 0 - 1) or Max(0, 2) or 2. In this case 0 represents a lack of any digits.

Things are definitely getting interesting now. I've upgraded the algorithm a bit to solve most optional captures, but I've probably added some edge cases that produce failures in other areas of the algorithm now. Here is some output from the upgraded algorithm (upgrade code is not yet hosted anywhere since I want to test it for new failures).

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>runtests.cmd

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 0 255
(25[0-5]|2[0-4]\d|1?\d?\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 5 255
(25[0-5]|[5-9]|2[0-4]\d|1?\d\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 222 228
(22[2-8])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 700
(700|699)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 701
(699|70[01])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 710
(710|699|70\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 698 710
(710|69[89]|70\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 7650 7710
(7710|770\d|76[5-9]\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 50 7710
(7710|770\d|[5-9]\d|7[0-6]\d\d|[1-6]?\d\d\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 6998998 7000000
(7000000|699899[89]|6999\d\d\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 7000 7999
(7[0-9]\d\d)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 7555 7999
(755[5-9]|75[6-9]\d|7[6-9]\d\d)

An Algorithm has been prepared, I'm linking it into an article so you don't have to look at it if you don't want. It is a spoiler.

2004-05-25T03:33:00Z

The final algorithm has quite a few special cases, but I've attempted to refactor the code and make it as small as possible. For readability I've chosen to use [0-9] in place of \d. You can easily change this out and use the more common \d. Note that the algorithm is not fully optimizing and it doesn't necessarily make use of optional characters, so patterns such as 0 255 turn out to be 5 alternation group items in place of the 4 people commonly find and the 3 that is possible.

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 0 255
(25[0-5]|[0-9]|2[0-4][0-9]|[1-9][0-9]|1[0-9][0-9])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 222 228
(22[2-8])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 700
(700|699)

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 701
(699|70[01])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 699 710
(710|699|70[0-9])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 698 710
(710|69[89]|70[0-9])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 7650 7710
(7710|765[0-9]|770[0-9]|76[6-9][0-9])

C:\Projects\CSharp\RegularExpressions\BuildRangeGroups>BuildRangeGroups 6998998 7000000
(7000000|699899[89]|6999[0-9][0-9][0-9])

Here is the code if you are eager to take a look. Sample Algorithm for Regex Range Validation

That range algorithm was more difficult than I originally pointed out due to some strange oddities.

2004-05-25T00:51:00Z

What kinds of strange oddities would I be talking about? Well, check out the following oddity:

699 through 700
699|700

699 through 701
699|70[01]

699 through 718
699|70\d|71[0-8]

698 through 701
69[89]|70[01]

You start to get the picture. There are some oddities when the max value has 0's and the min value has 9's that lead the right edge of the ranges. A standard algorithm as I had outlaid before would do the following:

699 through 700
leftmost = 0
starti = min.Length - 1 = 2

69[9-9]|70[0-0]|6[9-9]\d|7[0-0]\d

You see the problem? Based on the algorithm of simply finding the leftmost variable character isn't enough, since we also have some dependence on the rightmost character. There is one solution we can code in, only process a pattern possibility if the character isn't an extreme character. For the lower bound ranges extremes are 9's and for upper bound extremes are 0.

699 through 700
leftmost = 0, starti =min.Length - 1=2, skip starti = 2 and starti = 1 based on extremes
go to final range processing (step 5). Since max-min is now only 1, we won't add any patterns. A null result-set?

What our algorithm really needed to be was 699|700. However, based on our rules, that won't happen. Another rule, then might be that we add the pattern if we've approached (i-1) == leftmost.

699 through 708
leftmost = 0, starti = min.Length - 1 = 2
starti = 2, skip 9 in 699, process 8 in 708, results 70[0-8]
starti = 1, skip by default, hit rule (starti-1)==leftmost, same for 708, results 699|708

So we need another rule. Only process the default pattern if we haven't already processed a pattern. By that means, the end result is now 699|70[0-8]. Darn, we start to add a large number of rules to the generation of the range alternation group. There are still some items I haven't fully made elegant yet, as I've recently realized. Take the following:

699 through 710
699|70\d|710

By our default rule of only processing non-zero digits would exclude us from creating 70\d (actually it wouldn't, since our code would skip it the first time through and then create it the second time through using one of the exceptions). Since 70\d gets created as an exception 710 never gets created.

I'll leave these thoughts with you. I'm still waiting for some algorithms to show up!

Playing with the Regulator utility and I quickly find myself being second guessed by the Intellisense...

2004-05-23T02:24:00Z

I can honestly say that I really don't like intellisense, but the addition of intellisense with the Regulator application is probably pretty powerful for a large number of users. I started playing with the beta, and figured I'd load up some patterns that I've been playing with. As I started typing my patterns in, I kept getting an intellisense popup. When I continue typing, my last typed character often gets replaced. A good example would be creating a digit match:

\d

Once you type that in you'll get the intellisense popup. However, try and type another digit escape sequence, and you'll find your d has been replaced by the next \ character. Not fun my friend, not fun at all.

Nice little tool though I must say. It definitely has the ability to make my life a bit easier. I had read some posts on making enhancements to the tool. Some enhancements I'd like to see include plug-ins for generating test input to the expressions. Right now you can load tests from files and that is pretty nice, but I'd like something that models your expression and tries to make edge case input, that would be really nice. More cool features might include automatically generating expressions that match a large input such as a web page. Hopefully some of Darren's work on the HTML parser might help here.

A little jewel I plan on developing is the performant compiled expression. This won't exist for every expression, but for many types of expression you can hard-code in certain assumptions that make processing much more performant. In addtion, you can create strongly typed processing classes that return real results rather than simply captured expanses of string. Take the following:

(?<ID>\d\d\d\d)

The above could easily be translated and parsed as an integer and placed within a field or property on a capture structure. And this time, not a generic name/value structure like that used in the current .NET expressions. The added amount of time consumed to strongly type the value will be more than made up for in terms of time used to access the items later. In addition, you can compile with optimizations for specific use cases. If the expression is for validation (IsMatch), then there is no reason to store captures and groups or even listen to hints about creating named capture groups, ordinal groups, etc... This can be very powerful in server environments where validation should occur without the memory overhead of object allocations. Other optimizations can also be performed making the use of regular expressions more like a scalpel than a blunt axe.

0 through N ranges are interesting, but what about M through N ranges.

2004-05-22T22:40:00Z

You can read about the decomposition of 0 through N ranges here Value range parsing using Regular Expressions. Breaking down the dotted decimal IP byte processing. Make sure to read the comments, because there is a way to use even fewer decompositions than I listed in the article through the use of optional captures.

Now the trick is examining ranges with both upper and lower bounds. This is an empirical review as I'll take several ranges and decompose them, but I won't necessarily explain the mathematics for finding the count of the decompositions. We'll start with the decomposition of 222-555, which requires 5 decompositions to yield all results.

22[2-9]
2[3-9]\d
[3-4]\d\d
5[0-4]\d
55[0-5]

The next process will yield the range validation of 22-555. The difference here is that instead of having all numbers in the range of the same length, we now have numbers of varying lengths. The decomposition doesn't change much, and is equivalent to the decomposition of the range 222-555, except that the lower bound number of 22 is now equivalent to 022-555 (this allows our decomposition to yield the same results).

2[2-9]
[3-9]\d
[1-4]\d\d
5[0-4]\d
55[0-5]

You may notice a simple pattern between the two. There is a symmetry between where the character classes are used to denote custom ranges of digits and the static captures (both \d and non custom character classes are considered static captures for the purpose of this example). There is definitely a mathematical relationship between the layout of the ranges, and I could probably spend 10 or so pages explaining it, but I'll leave it out. The point is there is also an algorithmic association between the numbers that recursively works from the right side of the first range back through to the left and back to the right of the second range.

First, sort the ranges by min/max. This is important. Second, determine the first non matching character in the ranges starting from the left.

1. 222 and 555 are sorted thusly: min(222), max(555)
2. compare 2 to 5, since they are unmatched, then we start matching there.

That second step is important. Say you were sorting 222 and 228, you an see that the first non-matching character is the ones place. That means the left-side of the range doesn't matter for the purposes of generating our ranges. The range match simply becomes 22[2-8], and there is only a single decomposition. That means our decomposition is only based on the difference in the right side of the equation or rather based on the left-most digit that doesn't match. Any missing left side digits should be replaced with 0's and used in this process.

The third step is to build range groups from the digit value to 9 as you walk the first string from right to left. The fourth is to do the same for the second string only this time you build from 0 up to digit value. This results in (digit-1)*2 decompositions. The final decomposition or fifth step is to build the middle range.

3. 22[2-9], 2[3-9]\d
4. 55[0-5], 5[0-4]\d
5. [3-4]\d\d

[Editorial Note: I just drank some death sauce and I'm experiencing a slight hot twinge in my mouth]

The fifth step is dependent upon the relationship between the upper and lower bound numbers. If the difference between the two numbers is less than 2, then you leave out the final step, and it isn't needed. If the difference is greater than 2, then you subtract 1 from the upper and add 1 to the lower to get your range.

No refactoring, no fluff, just a quick range creation algorithm for regular expressions. I challenge you to convert the algorithm into code. There are several ways to implement each of the steps, and maybe even some more interesting algorithms.

Running your expressions asynchronously and making them cancellable.

2004-05-22T03:55:00Z

I blogged this over on weblogs, but I think this was the better spot for it. I'll definitely fix the classes up a bit more and add some additional functionality. For one, I'd like to add batching so you could run a bunch of them with timing metrics.

Asynchronous Regular Expressions using the ThreadPool and a cancellation model.