Is my simple regex catastrophically backtracking?

Viewed 75

I am parsing a text file using

(?<DateTime>.+?\t.+?)\t(?<Data>.+?)(\t(?<Data2>.+?))?\r\n

Originally it was just

(?<DateTime>.+?\t.+?)\t(?<Data>.+?)\r\n

But then I discovered one file that had an extra column that needed to be accounted for in the 10 files this API should parse, so I had to edit it to come up with the first regex.

Here is an example of the data I am parsing

2020-05-26  08:30:06    18.6
2020-05-26  08:44:38    18.0
2020-05-26  08:52:04    17.5
2020-05-26  09:17:44    18.0
2020-05-26  10:25:35    17.5
2020-05-26  10:47:08    18.0
2020-05-26  11:06:08    18.5

And here is the data with the rogue column

2019-08-21  10:32:21    0   00000   
2019-08-21  19:21:37    0   00000   
2019-08-21  23:24:10    0   00000   
2019-08-22  00:47:39    0   00000   

Note that while these are all zeros right now, other values are possible

Now everything here is still "working" but after I made my edit to the regex now one of the files that has ~8000 records is taking a long time to process. I wrote some console outputs in the parse method and found that it seems to halt around row ~7700 for almost 10 minutes before it suddenly exits with 500. Here is my parse method(I don't think this is important but I'm throwing this in anyway)

DataRow row;
index = 0;
Console.WriteLine("Beginning parse loop");
foreach (Match match in reg.Matches(data)) {
    row = table.NewRow();
    foreach (List<string> column in columns) {
        string value = getRegexGroupValue(match, column);
        if (column[1] == "System.DateTime") {
           if (value != "") {
              row[column[0]] = Convert.ToDateTime(value);
           }
        } else if (column[1] == "System.Int32") {
            row[column[0]] = Convert.ToInt32(value);
        } else {
            row[column[0]] = value;
        }
    }

    table.Rows.Add(row);
    Console.WriteLine(String.Format("Ending loop {0}", index++));
}

What's going on here?

When I use reg.Matches(data).Count in the debug console, it says some error and doesn't show me the row count, but when I use Notepad++ to check the regex I can get the row total just fine

EDIT: I got the file processing again using (?<DateTime>.+?\t.+?)\t(?<Data>.+?)[(\t)(\r\n)] but this is not the best solution as I am no longer capturing the extra column in that file, not sure if we'll ever use that but I'd rather have it than not

1 Answers

You are using .+? too much. Use negated character classes and use anchors:

(?m)^(?<DateTime>[^\t\r\n]+\t[^\t\r\n]+)\t(?<Data>[^\t\r\n]+)(?:\t(?<Data2>[^\t\r\n]+))?\r?$

See proof.

Explanation

                           EXPLANATION
--------------------------------------------------------------------------------
  (?m)                     set flags for this block (with ^ and $
                           matching start and end of line) (case-
                           sensitive) (with . not matching \n)
                           (matching whitespace and # normally)
--------------------------------------------------------------------------------
  ^                        the beginning of a "line"
--------------------------------------------------------------------------------
  (?<DateTime>             group and capture to \k<DateTime>:
--------------------------------------------------------------------------------
    [^\t\r\n]+               any character except: '\t' (tab), '\r'
                             (carriage return), '\n' (newline) (1 or
                             more times (matching the most amount
                             possible))
--------------------------------------------------------------------------------
    \t                       '\t' (tab)
--------------------------------------------------------------------------------
    [^\t\r\n]+               any character except: '\t' (tab), '\r'
                             (carriage return), '\n' (newline) (1 or
                             more times (matching the most amount
                             possible))
--------------------------------------------------------------------------------
  )                        end of \k<DateTime>
--------------------------------------------------------------------------------
  \t                       '\t' (tab)
--------------------------------------------------------------------------------
  (?<Data>                  group and capture to \k<Data>:
--------------------------------------------------------------------------------
    [^\t\r\n]+               any character except: '\t' (tab), '\r'
                             (carriage return), '\n' (newline) (1 or
                             more times (matching the most amount
                             possible))
--------------------------------------------------------------------------------
  )                        end of \k<Data>
--------------------------------------------------------------------------------
  (?:                      group, but do not capture (optional
                           (matching the most amount possible)):
--------------------------------------------------------------------------------
    \t                       '\t' (tab)
--------------------------------------------------------------------------------
    (?<Data2>              group and capture to \k<Data2>:
--------------------------------------------------------------------------------
      [^\t\r\n]+               any character except: '\t' (tab), '\r'
                               (carriage return), '\n' (newline) (1
                               or more times (matching the most
                               amount possible))
--------------------------------------------------------------------------------
    )                        end of \k<Data2>
--------------------------------------------------------------------------------
  )?                       end of grouping
--------------------------------------------------------------------------------
  \r?                      '\r' (carriage return) (optional (matching
                           the most amount possible))
--------------------------------------------------------------------------------
  $                        before an optional \n, and the end of a
                           "line"
Related