irregex behaves differently with overlapping character sets on some machines

[sjamaan]

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

[Jim Ursetto]

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

[sjamaan]

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.

[sjamaan]

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.

[Alex Shinn]

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.

[sjamaan]

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 ;)

[sjamaan]

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?

[felix winkelmann]

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

[felix winkelmann]

Milestone 4.8.0 deleted