Panic "BUG: reverse match implies forward match" under certain conditions

[qezz]

I've been trying to find an error in my small application, hence decided to utilize AFL to try different inputs to it. Application is based on a library that uses regex under the hood.

So, with help of AFL I discovered that the application crashes in certain conditions.
In short, the following test fails:

#[test]
fn weird_thing1() {
    // Note that 'Ј' is not 'j', but cyrillic Je 
    // https://en.wikipedia.org/wiki/Je_(Cyrillic)
    let regx = "()Ј01";
    let text = "()Ј01";
    let replace_with = "w";
    
    let re = regex::Regex::new(regx).unwrap();
    assert_eq!(re.replace(text, replace_with), "()w");
}

• Expected: Probably text as is. Upd: or "()w"
• Actual: Panic: thread 'replace::weird_thing1' panicked at 'BUG: reverse match implies forward match', src/exec.rs:889:27

Was able to reproduce only when parens and 'Je' symbol (https://en.wikipedia.org/wiki/Je_(Cyrillic)) are present, and followed by two or more characters.

See playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=53d71f4fa917ddba17d19630b86a81ac

---

One more weird thing:

I decided to add simple tests to tests/replace.rs to try it out, but faced the following:

1. When only one test is added, like

   replace!(weird_thing1, replace, r"()Ј01", "()Ј01", t!("w"), "()w");

   test case fails with ($ cargo test replace)

   ...
   test replace::trim ... ok
   test replace::weird_thing1 ... FAILED
   
   failures:
   
   ---- replace::weird_thing1 stdout ----
   thread 'replace::weird_thing1' panicked at 'BUG: reverse match implies forward match', src/exec.rs:889:27
   note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
   
   
   failures:
       replace::weird_thing1
   
   test result: FAILED. 18 passed; 1 failed; 0 ignored; 0 measured; 780 filtered out
   

2. But when I add another one like

   replace!(weird_thing1, replace, r"()Ј01", "()Ј01", t!("w"), "()w"); // the first one
   replace!(weird_thing2, replace, r"()Ј01", "()Ј01", t!("w"), "something"); // a new one

   then ($ cargo test replace)

   test replace::trim ... ok
   test replace::weird_thing1 ... ok
   test replace::weird_thing2 ... FAILED
   
   failures:
   
   ---- replace::weird_thing2 stdout ----
   thread 'replace::weird_thing2' panicked at 'assertion failed: `(left == right)`
     left: `"()w"`,
    right: `"something"`', tests/replace.rs:13:1
   note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
   
   
   failures:
       replace::weird_thing2
   
   test result: FAILED. 19 passed; 1 failed; 0 ignored; 0 measured; 769 filtered out
   

Which basically means that the first test finished successfully, and the second one reached the assert! statement. On the playground, I haven't tried the regex!() macro which is used in tests/replace.rs. So it could be the reason why this behavior is not the same on the playground, where Regex::new() is used.

[BurntSushi]

Nice find! Smaller reproduction:

fn main() {
    // Note that 'Ј' is not 'j', but cyrillic Je 
    // https://en.wikipedia.org/wiki/Je_(Cyrillic)
    let regx = "()Ј01";
    let text = "zЈ01";
    
    let re = regex::Regex::new(regx).unwrap();
    assert!(re.find(text).is_some());
}

This will probably be fixed by #656. I suspect this has a similar root cause as #524, as I think the empty sub-group here is probably causing problems somewhere.

[qezz]

Thank you for a quick response! I hope the mentioned plans will fix this.