NFA and DFA on match with ASCII word boundary

[SeanRBurton]

Running "(?-u:\\B)" (i.e. NotWordBoundaryAscii) against "0\u{7ef5e}" gives the match span (2, 2) using the NFA and (5, 5) using the default match engine.

[SeanRBurton]

repro case:

extern crate regex;                                                             

use regex::internal::ExecBuilder;                                               

fn main() {                                                                     
    let res = "(?-u:\\B)";                                                      
    let re0 = ExecBuilder::new(&res).build().unwrap().into_byte_regex();        
    let re1 = ExecBuilder::new(&res).nfa().build().unwrap().into_byte_regex();  
    let s = "0\u{7ef5e}";                                                       
    println!("{:?}", re0.captures(&s.as_bytes()).unwrap().pos(0)); // Some((5, 5))
    println!("{:?}", re1.captures(&s.as_bytes()).unwrap().pos(0)); // Some((2, 2))
}  

[SeanRBurton]

bump?

[BurntSushi]

Haven't had a chance to look at it yet, sorry. It certainly looks like a bug!

[lukaslueg]

Here are some examples (found by AFL, probably convoluted) which produce different results on ExecBuilder::new().build() and ExecBuild::new().nfa().build() when matching the same random sequence of bytes.

Z\xff\xff\x80A|^    // nfa() has three capture groups, normal has one
^|\x86\x85    // same as above
$\x84*    // nfa() has `.is_match()` as `false`, normal has it as `true`
(?P<a>\w.|\x64})*    // `find_iter()` differs: nfa() has `(0, 0), (1,1), (2,2) ...` while normal has `(0, 0), (1, 5), (6, 6) ...` among others

[BurntSushi]

@lukaslueg Can you file a separate bug? Also, what was the haystack?

[BurntSushi]

This one was a tough nut to crack. The positions reported by the NFA are trivially wrong because they don't fall on valid UTF-8 sequence boundaries. Because of that, the DFA results are indeed correct. If you used a bytes::Regex instead, then the semantics change completely, because the "not an ASCII word boundary" will now match between every pair of arbitrary bytes that doesn't correspond to a word boundary, even if they aren't valid ASCII/UTF-8.

It's not clear whether the bugs reported by @lukaslueg are related. I think I'll need at least the haystack text. (Some of the descriptions are confusing too. The first regex doesn't have any explicit capture groups, for example.)

[lukaslueg]

I'll recompile everything with latest upstream and file new bugs should the issue reappear