Hacker News Reader

Comment by shdon | Hacker News Reader

Personally, I've found it really helps to limit the patterns as much as possible to best match the valid input. My own rules of thumb:

- Prefer character classes like \d, \s or \w over .

- Prefer non-greedy .*? over greedy .*

- Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*>

- Prefer {count specifiers} over unbounded repeats. Not \d+ but \d{,3} instead

View on HN

Agreed on all points. It is very frustrating that greedy is the default behavior.

Great list. I would add

- Anchor when possible (^, $)

(If I understand correctly)

This "(^,$)" should be parsed as a list of useful "anchor" symbols (resp. start and end of string) rather than a regexep itself. I wasted some time before I realised this.

Yes, that's essentially what I was trying to communicate.

Since we are engine agnostic here be careful interpreting ^ or $ as start/end of _string_ though. In some regex engines this means start/end of _line_. If that's the case and if a regex validates input up to $ an attacker might be able to sneak in extra data after a newline. In Python you'd need multiline enabled but Ruby matches by default:

  irb(main):001:0> /^okay$/ =~ "okay\noops"
  => 0  # matches from position 0

(Ruby has \A and \Z for start and end of string to address this).

> - Exclude a delimiter from the search space, like using [^>]*?> rather than .*?> or worse yet .*>

Or indeed:

    (?!>).*?

Not quite. This works:

     (?:(?!>).)*>?

But that is a very long winded way of writing:

     [^>]*?>

which is long way of writing:

     [^>]*>

I was missing the trailing > in my pattern but you are still right (as is the article)

It's been fun to note the benchmarks:

all tested against the string: <a href="sdfsdf">sefsefsefsef</a>

  1.
    (?!>).*?>
   2 matches, 41 steps
  2. 
    (?:(?!>).)*>?
   3 matches, 142 steps
  3. (typo?)
    (?:(?!>).)*?>
   2 matches, 161 steps
  4.
    [^>]*?>
   2 matches, 6 steps
  5. 
    [^>]*>
   2 matches, 6 steps

The most important trait to avoid exponential behavior is to avoid nesting ?, *, +, etc.

Reply on news.ycombinator.com