Making the Regex engine choke... Ever wanted to? I'll show you how...
Okay, so back in the pre-V1 days I made a humongous regular expression alternation group and wanted to precompile that guy for maximum speed. What exactly is a humongous regular expression? Well imagine 12000 or so words, each on average of 10 characters. I built these into the alternation group using code similar to the following, where text is an array of strings with 12000 elements.
Regex regex = new Regex("(?:(" + string.Join("|", text) + "))+", RegexOptions.Compiled | RegexOptions.IgnoreCase);
It doesn't take anything nearly this complex though to get the engine to barf. My sample program uses 10000 strings of length 8 and precompiles the assembly. If you are faint of heart, don't have a fast machine, or don't care to have your machine hung for 15 minutes, then don't run this program. If you'd like to see a big exception getting thrown and the reason why I had to change my algorithms for finding bad words, then just run this stuff.
using System;
using System.Text.RegularExpressions;
public class TooLargeRegex {
private static void Main(string[] args) {
Random rand = new Random();
string[] text = new string[10000];
for(int i = 0; i < text.Length; i++) {
text[i] =
String.Concat(
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123)),
((char) rand.Next(97, 123))
);
}
Regex regex = new Regex("(?:(" + string.Join("|", text) + "))+", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Console.WriteLine(regex.IsMatch("foobarze"));
}
}
Well, that'll explode on you with an InvalidProgramException. This supposedly happens when invalid IL is detected. Supposedly it means the compiler that generated the IL messed up. Does this mean the .NET Regular Expression compiler is messed up? Well, maybe. We can take this one step further and compile the assembly out to disk and look at it using ILDasm. Perhaps we can find out where the invalid stuff is coming from. The following code should write out the compiled assembly so we can inspect the actual IL (note the assembly is about 3 megs):
RegexCompilationInfo rgi = new RegexCompilationInfo("(?:(" + string.Join("|", text) + "))+", RegexOptions.IgnoreCase, "myRegex", "fooBarBaz", true);
AssemblyName asmn = new AssemblyName();
asmn.Name = "fooBarBaz";
Regex.CompileToAssembly(new RegexCompilationInfo[] { rgi }, asmn);
Once you are done and you end up with fooBarBaz.dll, whatever you do, don't open it in ILDasm. Or if you do, don't try to view the IL for the Go method on myRegexRunner0. This will take an inordinate amount of time. I guess 3 megabytes worth of op-codes is an exceptional amount of stuff to load. However, the /out:fooBarBaz.il option will get you done in no time. So do that instead, and use a text editor that doesn't blink when you throw a 60 megabyte text file at it. So nothing appears to be wrong with the IL at all, so maybe that is a complete bust, but something is going wrong when you run this puppy and get your exception. Perhaps there are too many instructions? Time to round-trip this dern assembly using ilasm. Don't do this unless you again don't have heart problems, because it will take quite some time. I used my time playing some Champions of Norrath and eating some cheese sticks.
Okay, I'm posting, because ILAsm never actually finished compiling the code after two hours. I'll check back again later and maybe post something more in comments. I'm pretty sure either something is wrong in the CLR in terms of JIT'ing the extra large method or somehow the regular expression classes are emitting invalid IL as the InvalidProgramException would indicate. Anyway, have fun!