Negated regular expressions in Oniguruma and Ruby

Suraj N. Kurapati

13 November 2011
15 November 2011

Overview
Wholly negated regular expressions
Partly negated regular expressions
Conclusion

About a week ago, I submitted this feature request asking for the ability to negate regular expressions in Ruby. I have since implemented the feature myself by patching Ruby trunk and patching Oniguruma 5.9.2 beside it. And now, I shall explain to you how it all works.

Overview

Regular expressions can be negated either as a whole (/.../v) or in part /(?v:...)/) through the negation flag (v). The letter v was chosen for the negation flag because it comes from the ed(1) program of UNIX heritage, where it serves a global command that negates the sense of the regular expression passed in. This v heritage can also be found in grep(1), whose -v command-line option inverts its matching behavior.

Wholly negated regular expressions

This is the simplest part of the implementation. We match the negated regular expression as usual, treating it as if it were not negated, and then negate the result of that match if there were no matching errors.

Partly negated regular expressions

At parse time, a partly negated regular expression, say r in /(?v:r)/, is expanded into /(?:rN)?.*?/ where N is a special instruction (OP_NEGATE) that causes the regular expression matching engine to treat the input matched thus far as a mismatch.

For example, the /a(?v:b)c/ parse tree looks like this after expansion:

PATTERN: /a(?v:b)c/ (US-ASCII)
<list:275ca40>
   <string:275c9f0>a
   <enclose:275c950> option:4
      <quantifier:2755640>{0,1}
         <string:275c9a0>b
   <quantifier:2755690>{0,-1}?
      <anychar:275af20>
   <string:2755550>c

Since r is wrapped in an optional non-capturing group (/(?:rN)?/), the matching engine is able to continue onward when r does not match. However, if r did not match because the matching engine reached non-matching input characters, then those characters will obstruct the matching engine from continuing onward. That is why /.*?/ is provided.

For example, when /a(?v:b)c/ is matched against the input "axyzc", the non-matching input characters ("xyz") will obstruct the matching engine from matching the rest of the regular expression (/c/) against the rest of the input ("xyzc"). However, since /.*?/ consumes "xyz", the matching engine can proceed to match /c/ against "c".

Conclusion

In all, this was a challenging and fun learning experience for me. I brushed up on my rusty (thanks Ruby!) knowledge of the C language and the GDB debugger while also adding some shiny new tools to my repertoire:

Clewn for graphical operation of GDB through GVim
Cscope for answering the inverse of questions I ask Ctags

I have submitted my patches simultaneously to the Ruby developers and to the author of Oniguruma, and now await their response. If all goes well, we might see this feature in Ruby and Oniguruma someday. Enjoy! :-]

Updates

15 November 2011:

After playing with Oniguruma in GDB some more, I learned that its negative lookahead implementation follows the same approach as my OP_NEGATE addition: if the subexpression matches completely, then trigger a mismatch.

Consequently, I was able to remove my OP_NEGATE addition by expanding /(?v:r)/ into /(?:(?!r).)/, where the negative lookahead serves as a barrier that protects . from anything that matches the negated r.

PATTERN: /a(?v:b)c/ (US-ASCII)
<list:136aad0>
   <string:136ab70>a
   <enclose:136ac10> option:4
      <list:136a850>
         <anchor:136b250> prec read not
            <string:136ab20>b
         <anychar:136b2a0>
   <string:136ac60>c

Now, you can think of partly negated regular expressions as barriers that match a single input character. If you want them to match more (or less) input characters, then you can simply quantify them accordingly.

Finally, the idea behind this negative lookahead expansion comes from Akira TANAKA’s 2007 suggestion on specifying partly negated regular expressions in Ruby 1.8. Only, I realized it too late: after implementing OP_NEGATE and learning how Oniguruma really works.