c# - Regex taking surprisingly long time

Question

I have a search string entered by a user. Normally, the search string is split up using whitespace and then an OR search is performed (an item matches if it matches any of the search string elements). I want to provide a few "advanced" query features, such as the ability to use quotes to enclose literal phrases containing whitespace.

I though I had hammered out a decent regex to split up the strings for me, but it's taking a surprisingly long time to execute (> 2 seconds on my machine). I broke it out to figure out just where the hiccup was, and even more interestingly it seems to occur after the last Match is matched (presumably, at the end of the input). All of the matches up to the end of the string match in less time then I can capture, but that last match (if that's what it is - nothing returns) takes almost all of the 2 seconds.

I was hoping someone might have some insight into how I can speed this regex up a bit. I know I'm using a lookbehind with an unbounded quantifier but, like I said, this doesn't seem to cause any performance issues until after the last match has been matched.

CODE

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace RegexSandboxCSharp {
    class Program {
        static void Main( string[] args ) {

            string l_input1 = "# one  "two three" four five:"six seven"  eight "nine ten"";

            string l_pattern =
                @"(?<=^([^""]*([""][^""]*[""])?)*)s+";

            Regex l_regex = new Regex( l_pattern );

            MatchCollection l_matches = l_regex.Matches( l_input1 );
            System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator();

            DateTime l_listStart = DateTime.Now;
            List<string> l_elements = new List<string>();
            int l_previousIndex = 0;
            int l_previousLength = 0;
            //      The final MoveNext(), which returns false, takes 2 seconds.
            while ( l_matchEnumerator.MoveNext() ) {
                Match l_match = (Match) l_matchEnumerator.Current;
                int l_start = l_previousIndex + l_previousLength;
                int l_length = l_match.Index - l_start;
                l_elements.Add( l_input1.Substring( l_start, l_length ) );

                l_previousIndex = l_match.Index;
                l_previousLength = l_match.Length;
            }
            Console.WriteLine( "List Composition Time: " + ( DateTime.Now - l_listStart ).TotalMilliseconds.ToString() );

            string[] l_terms = l_elements.ToArray();

            Console.WriteLine( String.Join( "
", l_terms ) );

            Console.ReadKey( true );

        }
    }
}

OUTPUT
(This is exactly what I'm getting.)

one
"two three"
four
five:"six seven"
eight
"nine ten"

Answer 1

Try changing your regex to the following:

(?<=^((?>[^"]*)(["][^"]*["])?)*)s+

The only change here is to put the [^"]* into an atomic group, which prevents the catastrophic backtracking that occurs.

Note: The regex above is obviously does not use C# regex string syntax, which I am unfamiliar with, but I think it would be the following:

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)s+";

Why the catastrophic backtracking occurs:
Once all of the valid matches have been found the next match that is attempted is the space inside of the final quoted section. The lookbehind will fail because there are an odd number of quotes before the space.

At this point the regex inside of the lookbehind will start to backtrack. The anchor means it will always start at the beginning of the string, but it can still backtrack by dropping elements from the end of what it has matched. Lets look at the regex inside of the lookbehind:

^([^"]*(["][^"]*["])?)*

Since the quoted sections are optional, they can be dropped as the regex backtracks. For every chunk of non-quote characters that are not inside of a quoted section, before backtracking each character would have been matched as a part of the [^"]* at the beginning of the regex. As backtracking begins on that section the last character will be dropped from what the [^"]* matched, and will be picked up by the outer repetition. At this point it becomes very similar to the example in the catastrophic backtracking link above.