Regex Complexity

Today I got a shocker.

I tried the not-too-complicated regular expression:

href=['"](?<link>[^?'">]*\??[^'" >]*)[^>]*(?<displayed>[^>]*)</a>

I worked in the excellent RegexBuddy, and ran the above regex on a normal size HTML page (the regex aims to find all links in a page). The regex hung, and I got the following message:

The match attempt was aborted early because the regular expression is too complex. The regex engine you plan to use it with may not be able to handle it at all and crash. Look up "catastrophic backtracking" in the help file to learn how to avoid this situation.

I looked up “catastrophic backtracking”, and got that regexes such as “(x+x+)+y” are evil. Sure – but my regex does not contain nested repetition operations!

I then tried this regex on a short page, and it worked. This was another surprise, as I always thought most regex implementations are compiled, and then run in O(n) (I never took the time to learn all the regex flavors, I just assumed what I learned in the university was the general rule).

It turns out that one of the algorithms to implement regex uses backtracking, so a regex might work on a short string but fail on a larger one. It appears even simple expressions such as “(a|aa)*b” take exponential time in this implementation.

I looked around a bit, but failed to find a good description of the internal implementation of .NET’s regular expression engine.

BTW, the work-around I used here is modify the regex. It’s not exactly what I aimed for, but it’s close enough:

href=['"](?<link>[^'">]*)[^>]*>(?<displayed>[^>]*)</a>

TimeoutStream

What do you do when you want to read all the data from a Stream object in .NET? You use StreamReader.ReadToEnd().


Stream stream = ...;
StreamReader reader = new StreamReader(stream);
string data = reader.ReadToEnd();


Apparently there is no sane way to put a timeout on the above logic. If you call it and your stream doesn't have a timeout, you're doomed. Even if you stream has an internal timeout, you could still be doomed - for example, say you are reading from a website that sends you the letter 'A' every second. The timeout on the HttpResponseStream could be used, but still (assuming it's higher than one second), you can't set a timeout to the entire ReadToEnd() operation.

I wrote a small proxy class TimeoutStream that wraps any stream with a total timeout since the moment of its creation. Any blocking operation performed on it will fail if the stream has been created too far in the past.

I could use Asynchronous IO to sort of guarantee completion in this timeout without relying on a timeout on the stream itself - however, it appears to be impossible to do correctly in .NET - there is no good way to kill that IO operation if it does not complete within the allotted timeout (see here)- so far now this is good enough for our needs because we can indeed set a timeout on the HttpWebRequest object itself (in addition to using TimeoutStream).

The code is available here.

Whys is Open Source so hard?

Today I came with with an idea for a cool feature for RSS clients. What I want is intelligent filtering like StumbleUpon - users would click "I like it" or "I like it not" on RSS items, and the client could learn a user's "taste" and prioritize future items. Google revealed someone just thought of this about 2 weeks ago. Still, I don't want to pay 20$ for an RSS reader, and I don't want a reader that specializes in this, I want this as just another feature of a standard RSS reader, so I went on to try and add this to some existing open source RSS client.

I immediately found NClassifier, an open source .NET text classifier. Looks promising.

For an RSS client I mainly found Rssbandit. A bit ugly, but I could work with that.

Then, crash. I spent several good hours just trying to get the blasted code. At first I naively thought perhaps the code would be attached to some version of the installer. Nope. I went to the CVS, installed TortoiseCVS, and failed to login with a blank password. At this point I decided to try accessing the SVN version, since I'm already familiar with SVN. I managed to get the code, but it did not build due to a LicenseException :(

I figured the SVN version might be different from the CVS, so I went back to my efforts to use TortoiseCVS, and succeeded ... to connect. In SVN, I could just get the entire latest version. In CVS, I had to choose "packages" to download. Trying some packages, I found that TortoiseSVN does download, only it deletes the downloaded file just at the end of the download. ARG!

I really don't understand why this entire process has to be so complicated. This entire process should have taken half an hour, including downloading the code, modifying and initial testing. Why almost every time you download open source code, it never compiles on the first build. Why the SVN and CVS versions are different.

Bottom Line
I still like my idea of intelligent, learning RSS reader. If anyone has more knowledge in the mysterious ways of Sourceforge and wants to help, call.

Dotnet Web Crawler Speedup

I'm writing a web crawler in C#, and getting it to perform well was really annoying.
I tried simply using ThreadPool.QueueUserWorkItem() to queue up my requests to multiple threads. Each thread just ran WebClient.DownloadString().

While the threads did run in parallel, it turned out WebClient had an inherent lock.
I tried messing with the ConnectionManagementSection, but that turned out read-only.
After some Google, I found that the configuration can only be changed by modifying the machine.config or user.config files! Seems pretty stupid to me.

After doing that simply didn't work either, I found this code that helped me through. I still don't know exactly why WebClient.DownloadString() doesn't work, but after some tweaking I got to about 2.5 pages pre second. Still not top speed, but way better than the 0.5 pages/second I started with.