Execbuilder::new() and ExecBuilder::new().nfa() disagree on .is_match()

[lukaslueg]

AFL found a regex pattern where the two engines differ on .is_match(). There are many more examples, I strongly suspect them to be of the same underlying cause, though.

Tested with git as of today. As far as I tested this, the assertion succeeds if the bogus repetition count is removed or set to 1 or if the 'ä' is turned into an ASCII-character.

extern crate regex;

pub const HAYSTACK_BYTES: [u8; 262] = [212,194,101,43,14,254,200,102,172,158,178,63,73,128,238,90,186,218,203,107,17,42,187,194,114,122,39,42,202,120,78,115,51,8,109,230,114,178,50,40,233,196,250,19,230,246,130,68,88,49,4,87,73,253,96,140,121,187,133,37,174,185,69,126,100,39,234,88,147,125,51,142,131,153,103,107,47,27,92,0,36,42,79,245,225,15,205,183,108,44,19,164,215,140,128,87,12,217,253,133,5,251,120,78,224,130,209,100,78,138,101,62,121,226,131,123,19,12,130,77,118,202,115,187,243,168,18,46,102,111,111,98,97,114,89,240,245,241,239,215,176,34,71,253,166,145,32,162,6,23,106,198,192,105,182,19,183,228,153,80,140,62,171,120,184,101,142,165,165,162,123,222,119,97,28,72,30,246,250,12,210,74,180,118,38,99,44,211,198,82,31,131,198,120,65,12,31,76,15,18,137,80,242,118,195,176,244,106,138,176,15,67,203,132,213,138,65,3,242,223,20,137,37,214,96,32,72,109,132,75,28,112,190,249,19,243,98,136,224,12,182,154,248,111,245,31,108,144,25,209,196,192,225,207,145,190,24,2,216,33,127,138,];

fn main() {
    let pattern = "${2}ä";
    let haystack = &HAYSTACK_BYTES;
    let re0 = regex::internal::ExecBuilder::new(pattern).build().map(|b| b.into_byte_regex()).unwrap();
    let re1 = regex::internal::ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.is_match(haystack), re1.is_match(haystack));
}

[lukaslueg]

ping. the fuzzer is running idle as it get clobbered by the above :-D No harm done though.

[lukaslueg]

Maybe it's my goggles that do nothing but ${2}ä still fails for me. The unittests that were put in place check for ${2}a.

[lukaslueg]

This also fails

extern crate regex;

pub const HAYSTACK_BYTES: [u8; 262] = [10,219,130,110,51,1,221,51,205,70,12,201,191,23,226,175,74,207,138,124,182,166,176,65,174,198,202,158,2,225,16,59,179,254,110,226,184,239,17,223,254,67,212,147,166,109,45,144,214,233,247,218,110,148,102,109,112,84,46,161,70,151,35,221,154,172,175,60,186,160,44,165,38,160,131,178,147,197,230,9,227,110,242,93,196,25,23,88,150,240,202,57,72,161,79,33,88,155,46,20,156,209,80,17,6,122,255,159,42,138,97,148,42,1,134,254,175,154,118,137,252,119,88,132,250,255,7,94,102,111,111,98,97,114,192,69,24,44,7,187,217,77,117,131,107,37,205,153,231,243,188,64,147,183,87,202,87,34,221,49,172,14,222,197,206,157,196,176,100,113,151,181,106,89,224,194,54,164,240,210,162,157,107,21,239,126,84,168,76,73,117,99,18,144,107,103,7,136,44,210,32,17,9,133,177,94,171,172,164,253,159,236,46,60,118,74,81,246,72,57,131,136,252,22,30,96,136,28,172,240,252,51,203,154,45,147,114,190,238,10,87,185,242,57,30,54,151,233,121,58,127,159,24,132,25,194,65,211,134,29,236,76,];

fn main() {
    let pattern = ".";
    let haystack = &HAYSTACK_BYTES;
    let re0 = regex::internal::ExecBuilder::new(pattern).build().map(|b| b.into_byte_regex()).unwrap();
    let re1 = regex::internal::ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.find_iter(haystack).collect::<Vec<_>>(),
               re1.find_iter(haystack).collect::<Vec<_>>());
}

[BurntSushi]

This program completes successfully for me:

extern crate regex;

use regex::Regex;
use regex::internal::ExecBuilder;

pub const HAYSTACK_BYTES: [u8; 262] = [212,194,101,43,14,254,200,102,172,158,178,63,73,128,238,90,186,218,203,107,17,42,187,194,114,122,39,42,202,120,78,115,51,8,109,230,114,178,50,40,233,196,250,19,230,246,130,68,88,49,4,87,73,253,96,140,121,187,133,37,174,185,69,126,100,39,234,88,147,125,51,142,131,153,103,107,47,27,92,0,36,42,79,245,225,15,205,183,108,44,19,164,215,140,128,87,12,217,253,133,5,251,120,78,224,130,209,100,78,138,101,62,121,226,131,123,19,12,130,77,118,202,115,187,243,168,18,46,102,111,111,98,97,114,89,240,245,241,239,215,176,34,71,253,166,145,32,162,6,23,106,198,192,105,182,19,183,228,153,80,140,62,171,120,184,101,142,165,165,162,123,222,119,97,28,72,30,246,250,12,210,74,180,118,38,99,44,211,198,82,31,131,198,120,65,12,31,76,15,18,137,80,242,118,195,176,244,106,138,176,15,67,203,132,213,138,65,3,242,223,20,137,37,214,96,32,72,109,132,75,28,112,190,249,19,243,98,136,224,12,182,154,248,111,245,31,108,144,25,209,196,192,225,207,145,190,24,2,216,33,127,138,];

fn main() {
    let pattern = "${2}ä";
    let haystack = &HAYSTACK_BYTES;
    let re0 = ExecBuilder::new(pattern).build().unwrap().into_byte_regex();
    let re1 = ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.is_match(haystack), re1.is_match(haystack));
}

But dammit, you're right, this one doesn't:

extern crate regex;

use regex::Regex;
use regex::internal::ExecBuilder;

pub const HAYSTACK_BYTES: [u8; 262] = [212,194,101,43,14,254,200,102,172,158,178,63,73,128,238,90,186,218,203,107,17,42,187,194,114,122,39,42,202,120,78,115,51,8,109,230,114,178,50,40,233,196,250,19,230,246,130,68,88,49,4,87,73,253,96,140,121,187,133,37,174,185,69,126,100,39,234,88,147,125,51,142,131,153,103,107,47,27,92,0,36,42,79,245,225,15,205,183,108,44,19,164,215,140,128,87,12,217,253,133,5,251,120,78,224,130,209,100,78,138,101,62,121,226,131,123,19,12,130,77,118,202,115,187,243,168,18,46,102,111,111,98,97,114,89,240,245,241,239,215,176,34,71,253,166,145,32,162,6,23,106,198,192,105,182,19,183,228,153,80,140,62,171,120,184,101,142,165,165,162,123,222,119,97,28,72,30,246,250,12,210,74,180,118,38,99,44,211,198,82,31,131,198,120,65,12,31,76,15,18,137,80,242,118,195,176,244,106,138,176,15,67,203,132,213,138,65,3,242,223,20,137,37,214,96,32,72,109,132,75,28,112,190,249,19,243,98,136,224,12,182,154,248,111,245,31,108,144,25,209,196,192,225,207,145,190,24,2,216,33,127,138,];

fn main() {
    let pattern = ".";
    let haystack = &HAYSTACK_BYTES;
    let re0 = ExecBuilder::new(pattern).build().unwrap().into_byte_regex();
    let re1 = ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.is_match(haystack), re1.is_match(haystack));
}

[lukaslueg]

Notice that the haystack is different for the ${2}ä-example.

[BurntSushi]

@lukaslueg I think my first program in my previous comment matches your initial submission, no?

[lukaslueg]

It does, sorry, I changed it from under your nose.

pub const HAYSTACK_BYTES: [u8; 262] = [10,219,130,110,51,1,221,51,205,70,12,201,191,23,226,175,74,207,138,124,182,166,176,65,174,198,202,158,2,225,16,59,179,254,110,226,184,239,17,223,254,67,212,147,166,109,45,144,214,233,247,218,110,148,102,109,112,84,46,161,70,151,35,221,154,172,175,60,186,160,44,165,38,160,131,178,147,197,230,9,227,110,242,93,196,25,23,88,150,240,202,57,72,161,79,33,88,155,46,20,156,209,80,17,6,122,255,159,42,138,97,148,42,1,134,254,175,154,118,137,252,119,88,132,250,255,7,94,102,111,111,98,97,114,192,69,24,44,7,187,217,77,117,131,107,37,205,153,231,243,188,64,147,183,87,202,87,34,221,49,172,14,222,197,206,157,196,176,100,113,151,181,106,89,224,194,54,164,240,210,162,157,107,21,239,126,84,168,76,73,117,99,18,144,107,103,7,136,44,210,32,17,9,133,177,94,171,172,164,253,159,236,46,60,118,74,81,246,72,57,131,136,252,22,30,96,136,28,172,240,252,51,203,154,45,147,114,190,238,10,87,185,242,57,30,54,151,233,121,58,127,159,24,132,25,194,65,211,134,29,236,76,];

with ${2}ä or . should fail.

[BurntSushi]

Neither of these programs fail for me on master:

extern crate regex;

use regex::Regex;
use regex::internal::ExecBuilder;

pub const HAYSTACK_BYTES: &'static [u8] = &[10,219,130,110,51,1,221,51,205,70,12,201,191,23,226,175,74,207,138,124,182,166,176,65,174,198,202,158,2,225,16,59,179,254,110,226,184,239,17,223,254,67,212,147,166,109,45,144,214,233,247,218,110,148,102,109,112,84,46,161,70,151,35,221,154,172,175,60,186,160,44,165,38,160,131,178,147,197,230,9,227,110,242,93,196,25,23,88,150,240,202,57,72,161,79,33,88,155,46,20,156,209,80,17,6,122,255,159,42,138,97,148,42,1,134,254,175,154,118,137,252,119,88,132,250,255,7,94,102,111,111,98,97,114,192,69,24,44,7,187,217,77,117,131,107,37,205,153,231,243,188,64,147,183,87,202,87,34,221,49,172,14,222,197,206,157,196,176,100,113,151,181,106,89,224,194,54,164,240,210,162,157,107,21,239,126,84,168,76,73,117,99,18,144,107,103,7,136,44,210,32,17,9,133,177,94,171,172,164,253,159,236,46,60,118,74,81,246,72,57,131,136,252,22,30,96,136,28,172,240,252,51,203,154,45,147,114,190,238,10,87,185,242,57,30,54,151,233,121,58,127,159,24,132,25,194,65,211,134,29,236,76,];

fn main() {
    let pattern = "${2}ä";
    let haystack = HAYSTACK_BYTES;
    let re0 = ExecBuilder::new(pattern).build().unwrap().into_byte_regex();
    let re1 = ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.is_match(haystack), re1.is_match(haystack));
}

and

extern crate regex;

use regex::Regex;
use regex::internal::ExecBuilder;

pub const HAYSTACK_BYTES: &'static [u8] = &[10,219,130,110,51,1,221,51,205,70,12,201,191,23,226,175,74,207,138,124,182,166,176,65,174,198,202,158,2,225,16,59,179,254,110,226,184,239,17,223,254,67,212,147,166,109,45,144,214,233,247,218,110,148,102,109,112,84,46,161,70,151,35,221,154,172,175,60,186,160,44,165,38,160,131,178,147,197,230,9,227,110,242,93,196,25,23,88,150,240,202,57,72,161,79,33,88,155,46,20,156,209,80,17,6,122,255,159,42,138,97,148,42,1,134,254,175,154,118,137,252,119,88,132,250,255,7,94,102,111,111,98,97,114,192,69,24,44,7,187,217,77,117,131,107,37,205,153,231,243,188,64,147,183,87,202,87,34,221,49,172,14,222,197,206,157,196,176,100,113,151,181,106,89,224,194,54,164,240,210,162,157,107,21,239,126,84,168,76,73,117,99,18,144,107,103,7,136,44,210,32,17,9,133,177,94,171,172,164,253,159,236,46,60,118,74,81,246,72,57,131,136,252,22,30,96,136,28,172,240,252,51,203,154,45,147,114,190,238,10,87,185,242,57,30,54,151,233,121,58,127,159,24,132,25,194,65,211,134,29,236,76,];

fn main() {
    let pattern = ".";
    let haystack = HAYSTACK_BYTES;
    let re0 = ExecBuilder::new(pattern).build().unwrap().into_byte_regex();
    let re1 = ExecBuilder::new(pattern).nfa().build().unwrap().into_byte_regex();
    assert_eq!(re0.is_match(haystack), re1.is_match(haystack));
}

[lukaslueg]

did you

assert_eq!(re0.find_iter(haystack).collect::<Vec<_>>(),
               re1.find_iter(haystack).collect::<Vec<_>>());

?