Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Various inconsistencies between different engines #429

Closed
SeanRBurton opened this issue Dec 11, 2017 · 4 comments
Closed

Various inconsistencies between different engines #429

SeanRBurton opened this issue Dec 11, 2017 · 4 comments

Comments

@SeanRBurton
Copy link
Contributor

I've generated several failing test-cases which exercise various dark corners, and should make for good regression tests. I did my best to make them mostly orthogonal, but most of the issues seem to be word-boundary related.

fn test() {
    let patterns = [
        "(?:(?-u:\\b)|(?u:h))+",
        "(?u:\\B)",
        "(?:(?u:\\b)|(?s-u:.))+",
        "(?:(?-u:\\B)|(?su:.))+",
        "(?m:$)(?m:^)(?su:.)",
        "(?m:$)^(?m:^)",
        "(?P<kp>(?iu:do)(?m:$))*",

        "(?u:\\B)",
        "(?:(?-u:\\b)|(?u:[\u{0}-W]))+",
        "((?m:$)(?-u:\\B)(?s-u:.)(?-u:\\B)$)",
        "(?m:$)(?m:$)^(?su:.)",
        "(?-u:\\B)(?m:^)",
        "(?:(?u:\\b)|(?-u:.))+",
    ];
    let haystacks = [
        "h",
        "鋸",
        "oB",
        "\u{fef80}",
        "\n‣",
        "\n",
        "dodo",

        "䡁",
        "0",
        "\n\n",
        "\n\u{81}¨\u{200a}",
        "0\n",
        "0",
    ];
    for (i, (pattern, haystack)) in patterns.iter()
                                            .zip(haystacks.iter()).enumerate() {
        let re0 = ExecBuilder::new(&pattern).only_utf8(false)
                                            .build()
                                            .unwrap()
                                            .into_regex();
        let re1 = ExecBuilder::new(&pattern).only_utf8(false)
                                            .nfa()
                                            .bytes(i < 7)
                                            .build()
                                            .unwrap()
                                            .into_regex();
        let caps0 = re0.captures(haystack);
        let caps1 = re1.captures(haystack);
        let mut correct = true;
        match (caps0, caps1) {
            (Some(a), Some(b)) => {
                for (c0, c1) in a.iter().zip(b.iter()) {
                    match (c0, c1) {
                        (Some(c), Some(d)) => {
                            if c.start() != d.start() || c.end() != d.end() {
                                correct = false;
                                break;
                            }
                        }
                        (None, None) => (),
                        _ => {
                            correct = false;
                            break;
                        }
                    }
                }
            }
            _ => correct = false,
        }
        println!("{:?}", correct);
    }
}
@sanmai-NL
Copy link

@SeanRBurton: good work! What follow-up to this do you have in mind?

@BurntSushi
Copy link
Member

@sanmai-NL Eh? If there are inconsistencies between the different engines, then we should fix them. These are hard bugs to fix because they require deep context, and likely don't appear often, so they haven't hit the top of my list to look at.

@sanmai-NL
Copy link

Yes, so I just meant to ask the reporter to suggest how to prioritize any potential improvements. He seems to take an interest in this issue considering he’s filing it. 🙂

@BurntSushi
Copy link
Member

These are all fixed in my in-progress regex-automata work that will land once #656 is done.

BurntSushi added a commit that referenced this issue Jul 5, 2023
I usually close tickets on a commit-by-commit basis, but this refactor
was so big that it wasn't feasible to do that. So ticket closures are
marked here.

Closes #244
Closes #259
Closes #476
Closes #644
Closes #675
Closes #824
Closes #961

Closes #68
Closes #510
Closes #787
Closes #891

Closes #429
Closes #517
Closes #579
Closes #779
Closes #850
Closes #921
Closes #976
Closes #1002

Closes #656
crapStone added a commit to Calciumdibromid/CaBr2 that referenced this issue Jul 18, 2023
This PR contains the following updates:

| Package | Type | Update | Change |
|---|---|---|---|
| [regex](https://github.com/rust-lang/regex) | dependencies | minor | `1.8.4` -> `1.9.1` |

---

### Release Notes

<details>
<summary>rust-lang/regex (regex)</summary>

### [`v1.9.1`](https://github.com/rust-lang/regex/blob/HEAD/CHANGELOG.md#191-2023-07-07)

[Compare Source](rust-lang/regex@1.9.0...1.9.1)

\==================
This is a patch release which fixes a memory usage regression. In the regex
1.9 release, one of the internal engines used a more aggressive allocation
strategy than what was done previously. This patch release reverts to the
prior on-demand strategy.

Bug fixes:

-   [BUG #&#8203;1027](rust-lang/regex#1027):
    Change the allocation strategy for the backtracker to be less aggressive.

### [`v1.9.0`](https://github.com/rust-lang/regex/blob/HEAD/CHANGELOG.md#190-2023-07-05)

[Compare Source](rust-lang/regex@1.8.4...1.9.0)

\==================
This release marks the end of a [years long rewrite of the regex crate
internals](rust-lang/regex#656). Since this is
such a big release, please report any issues or regressions you find. We would
also love to hear about improvements as well.

In addition to many internal improvements that should hopefully result in
"my regex searches are faster," there have also been a few API additions:

-   A new `Captures::extract` method for quickly accessing the substrings
    that match each capture group in a regex.
-   A new inline flag, `R`, which enables CRLF mode. This makes `.` match any
    Unicode scalar value except for `\r` and `\n`, and also makes `(?m:^)` and
    `(?m:$)` match after and before both `\r` and `\n`, respectively, but never
    between a `\r` and `\n`.
-   `RegexBuilder::line_terminator` was added to further customize the line
    terminator used by `(?m:^)` and `(?m:$)` to be any arbitrary byte.
-   The `std` Cargo feature is now actually optional. That is, the `regex` crate
    can be used without the standard library.
-   Because `regex 1.9` may make binary size and compile times even worse, a
    new experimental crate called `regex-lite` has been published. It prioritizes
    binary size and compile times over functionality (like Unicode) and
    performance. It shares no code with the `regex` crate.

New features:

-   [FEATURE #&#8203;244](rust-lang/regex#244):
    One can opt into CRLF mode via the `R` flag.
    e.g., `(?mR:$)` matches just before `\r\n`.
-   [FEATURE #&#8203;259](rust-lang/regex#259):
    Multi-pattern searches with offsets can be done with `regex-automata 0.3`.
-   [FEATURE #&#8203;476](rust-lang/regex#476):
    `std` is now an optional feature. `regex` may be used with only `alloc`.
-   [FEATURE #&#8203;644](rust-lang/regex#644):
    `RegexBuilder::line_terminator` configures how `(?m:^)` and `(?m:$)` behave.
-   [FEATURE #&#8203;675](rust-lang/regex#675):
    Anchored search APIs are now available in `regex-automata 0.3`.
-   [FEATURE #&#8203;824](rust-lang/regex#824):
    Add new `Captures::extract` method for easier capture group access.
-   [FEATURE #&#8203;961](rust-lang/regex#961):
    Add `regex-lite` crate with smaller binary sizes and faster compile times.
-   [FEATURE #&#8203;1022](rust-lang/regex#1022):
    Add `TryFrom` implementations for the `Regex` type.

Performance improvements:

-   [PERF #&#8203;68](rust-lang/regex#68):
    Added a one-pass DFA engine for faster capture group matching.
-   [PERF #&#8203;510](rust-lang/regex#510):
    Inner literals are now used to accelerate searches, e.g., `\w+@&#8203;\w+` will scan
    for `@`.
-   [PERF #&#8203;787](rust-lang/regex#787),
    [PERF #&#8203;891](rust-lang/regex#891):
    Makes literal optimizations apply to regexes of the form `\b(foo|bar|quux)\b`.

(There are many more performance improvements as well, but not all of them have
specific issues devoted to them.)

Bug fixes:

-   [BUG #&#8203;429](rust-lang/regex#429):
    Fix matching bugs related to `\B` and inconsistencies across internal engines.
-   [BUG #&#8203;517](rust-lang/regex#517):
    Fix matching bug with capture groups.
-   [BUG #&#8203;579](rust-lang/regex#579):
    Fix matching bug with word boundaries.
-   [BUG #&#8203;779](rust-lang/regex#779):
    Fix bug where some regexes like `(re)+` were not equivalent to `(re)(re)*`.
-   [BUG #&#8203;850](rust-lang/regex#850):
    Fix matching bug inconsistency between NFA and DFA engines.
-   [BUG #&#8203;921](rust-lang/regex#921):
    Fix matching bug where literal extraction got confused by `$`.
-   [BUG #&#8203;976](rust-lang/regex#976):
    Add documentation to replacement routines about dealing with fallibility.
-   [BUG #&#8203;1002](rust-lang/regex#1002):
    Use corpus rejection in fuzz testing.

</details>

---

### Configuration

📅 **Schedule**: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined).

🚦 **Automerge**: Disabled by config. Please merge this manually once you are satisfied.

♻ **Rebasing**: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox.

🔕 **Ignore**: Close this PR and you won't be reminded about this update again.

---

 - [ ] <!-- rebase-check -->If you want to rebase/retry this PR, check this box

---

This PR has been generated by [Renovate Bot](https://github.com/renovatebot/renovate).
<!--renovate-debug:eyJjcmVhdGVkSW5WZXIiOiIzNi4wLjAiLCJ1cGRhdGVkSW5WZXIiOiIzNi44LjExIiwidGFyZ2V0QnJhbmNoIjoiZGV2ZWxvcCJ9-->

Co-authored-by: cabr2-bot <cabr2.help@gmail.com>
Co-authored-by: crapStone <crapstone01@gmail.com>
Reviewed-on: https://codeberg.org/Calciumdibromid/CaBr2/pulls/1957
Reviewed-by: crapStone <crapstone01@gmail.com>
Co-authored-by: Calciumdibromid Bot <cabr2_bot@noreply.codeberg.org>
Co-committed-by: Calciumdibromid Bot <cabr2_bot@noreply.codeberg.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants