Improving regex to match each line in a file, including windows and/or linux line break, even for missing line break at EOF

Question

My requirement is to match each line of a text file, including the line terminator of each, at most excluding the terminator of the last line, to take into account the crippled, non POSIX-compiant files generated on Windows; each line terminator can be either \n or \r\n.

And I'm looking for the best regex, performance-wise.

The first regex I could come up with is this:

\n|\r\n|[^\r\n]++(\r\n|\n)?

A few comments on it:

• since three alternatives cannot match at the same place, I guess the order of the alternatives is irrelevant, regardless of the engine being a DFA or NFA;
• the ++ instead of + should save some memory, but not some time, as backtracking shouldn't occur.

From Code Review, a suggestion was to use .*(\r?\n|$) (or [^\r\n]*(\r?\n|$), if . also matches \n o \r), but this has a flaw: it also matches the empty string at the end of the file.

That suggested regex can be improved like this:

(?=.).*(\r?\n)?

where the lookahead guarantees that there's at least one character matched by .* and (\r?\n)? together, which prevents the emtpy string at the end of the file from matching.

Which of the two regexes above should be better, performance-wise? Is there any other better way to match as per my requirements?

Please, if you use the ^/$ anchors or similar, comment about that, because their behavior is dependent on whether the engine considers them as multiline by default.

Answer 1

The best performance in regex is achieved when each subsequent pattern cannot match at the same locationin the string. . and \R are opposite patterns, . is used to match any char but line break chars, and \R is used to match any line break sequence.

In context of C++ Boost regex, where a . matches any char including line break chars and ^ and $ anchors are line (not string) "terminators", the pattern you may consider using is

(?-s)^(?!\z).*\R?

See the regex demo. Details:

• (?-s) - turning singleline mode off, the . will now fail to match line break chars
• ^ - start of a line (boost::regex syntax does not require (?m) to make ^ line-aware, it is the default behavior)
• (?!\z) - a negative lookahead that fails the match if the current position is at the very end of string
• .* - any zero or more chars other than line break chars, as many as possible (this pattern moves the regex index right at the end of the line)
• \R? - an optional line break sequence.

Here is a C++ boost::regex demo:

#include <boost/regex.hpp>
#include <iostream>
#include <string>

int main()
{
  std::string text = "Line1\nLine2\r\nLine3\rLastLine\n";
  boost::regex expression(R"((?-s)^(?!\z).*\R?)");
  boost::smatch match;
  boost::sregex_token_iterator iter(text.begin(), text.end(), expression, 0);
  boost::sregex_token_iterator end;
  for( ; iter != end; ++iter ) {
   std::cout << "'" << *iter << "'" << std::endl;
  }
  return 0;
}

Output:

'Line1
'
'Line2
'
'Line3
'
'LastLine
'