Summary

irregex behaves differently with overlapping character sets on some machines

Metadata

Description

We haven't figured out the cause or anything else yet, but on my NetBSD box, I get the following (expected and correct output):

 #;1> (use irregex)
 ; loading library irregex ...
 #;2> (irregex-match 
         '(seq (* white) (submatch (+ print)) 
               (* white) ":" (+ white)
               (submatch (+ print)) (* white))
      "io:event-dispatch")
 #f

On call-cc.org (and on another of Mario's machines which is x86-64 Linux) we get this:

 #;1> (use irregex)
 ; loading library irregex ...
 #;2> #;2> (irregex-match 
         '(seq (* white) (submatch (+ print)) 
               (* white) ":" (+ white)
               (submatch (+ print)) (* white))
      "io:event-dispatch")
 #<regexp-match (2 submatches)>
 #;3> (irregex-match-substring #2 1)
 "i"
 #;4> (irregex-match-substring #2 2)
 #f

Changes and comments

[2011-07-08 22:40:14 UTC] zbigniew wrote:

I get the correct output with 4.7.0 on macosx-unix-gnu-x86-64.

[2011-07-08 23:25:06 UTC] sjamaan wrote:

It's also "wrong" with irregex upstream but that's because the regex itself is wrong; it should be "graphic", not "print". "print" includes whitespace!

So this is a bug in qwiki (and I'll fix it asap), but the inconsistent output on the same input remains unexplained.

[2011-07-08 23:30:42 UTC] sjamaan changed summary

[2011-07-08 23:31:32 UTC] sjamaan wrote:

So the current status is: irregex is okay but in Chicken it sometimes produces different output with the same input if the input is ambiguous.

[2011-07-09 08:44:19 UTC] ashinn wrote:

In a recent commit a bug seems to have been introduced with the char-set handling.

Going back to version 59 and it works, provided you give it a regexp that actually matches - in this case, you need to replace the (+ white) with (* white) or add some whitespace after the colon.

[2011-07-10 23:49:09 UTC] sjamaan wrote:

The bug appears to be in the nfa->dfa conversion, since the NFA resulting from this SRE is exactly the same before and after the breaking change.

I've managed to reduce it further to an even simpler match, which gets compiled to this DFA:

 #;2> (pp (nfa->dfa (sre->nfa (quote (seq (+ print) white)) ~none)))
 #((#f (#((#\tab . #\newline) (#\space . #\~)) . 1))
   (#f (#((#\tab . #\tab) (#\! . #\~)) . 2) (#\space . 2) (#\newline . 2))
   (#t (#((#\tab . #\tab) (#\! . #\~)) . 2) (#\space . 2) (#\newline . 2)))

It should look something like this (the accepting state should be left when encountering a non-whitespace character):

 #((#f (#((#\tab . #\newline) (#\space . #\~)) . 1))
   (#f (#((#\space . #\~)) . 2) (#\tab . 2) (#\newline . 2))
   (#t (#((#\! . #\~)) . 1) (#\space . 2) #((#\tab . 2) (#\newline . 2))))

It's most likely in the hairy nfa-join-transitions! procedure. I don't understand it anymore so I'll probably just end up rewriting it ;)

[2011-07-13 00:45:31 UTC] sjamaan changed status from new to assigned

[2011-07-13 00:45:31 UTC] sjamaan set owner to felix

[2011-07-13 00:45:31 UTC] sjamaan wrote:

This bug was rather evil but easy to fix (after hammering on it for three days to pinpoint the cause).

Felix: Could you please review and merge 7d0520e145bc251abe2499af8149ff271ede6b29 from irregex-bugfixes to master?

[2011-07-13 17:37:30 UTC] felix changed status from assigned to closed

[2011-07-13 17:37:30 UTC] felix set resolution to fixed

[2011-07-13 17:37:30 UTC] felix wrote:

Has been merged. Note that master is currently broken (expander/transformer issue).

[2012-09-24 21:47:48 UTC] felix changed milestone from 4.8.0 to 4.9.0

[2012-09-24 21:47:48 UTC] felix wrote:

Milestone 4.8.0 deleted