Binary search is used with incorrectly-sorted array

[SimonSapin]

The “dynamic” matching of CharClass uses a binary search within char ranges, which relies on the input being sorted. The input is indeed sorted in its “natural” order, but the comparison function in case-insensitive mode uses a different order.

This leads to incorrect results:

assert!(Regex::new(r"(?i)[a_]+$").unwrap().is_match("A_"));

The above fails, because _ in ASCII is between upper-case and lower-case letters. The comparison function maps the 'a'..'a' range to its upper case 'A'..'A', which has a different order relative to '_'..'_'.

Compare with e.g. the code below, which succeeds.

assert!(Regex::new(r"(?i)[a=]+$").unwrap().is_match("A="));

The comparison function has a FIXME to move the case mapping outside of it and have the Vec of ranges be already mapped. I assume this was intended for performance, but I think it’ll also fix this issue. I’ll try it.

[BurntSushi]

Nice find! If you find an easy fix, that would be awesome. Otherwise, I am in the process of rewriting the parser with the intention of fixing a bunch of little bugaboos like this. (Although I didn't realize this caused buggy behavior!)

[SimonSapin]

I have a fix, but I’m also tracking down another bug. Let we write up an issue.

[SimonSapin]

#75 is that issue. #78 has fixes for both and #55.

[BurntSushi]

Awesome! I'm currently out, but I'll review as soon as I get home and get this merged. Thank you!