Upgrade rust/crates/regex to 1.5.4 am: 3874808a33 am: 8634f71550 am: df6134fce7 am: 6cd46007e3
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/regex/+/1713148
Change-Id: Ic9da62bc060f217f2502c00466f7d0b1dc847dd0
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 33a143b..51b3cd6 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
{
"git": {
- "sha1": "ff283badce21dcebd581909d38b81f2c8c9bfb54"
+ "sha1": "f2dc1b788f773a49f1b6633a6302054978344452"
}
}
diff --git a/Android.bp b/Android.bp
index 99eac66..646c587 100644
--- a/Android.bp
+++ b/Android.bp
@@ -43,7 +43,7 @@
host_supported: true,
crate_name: "regex",
srcs: ["src/lib.rs"],
- edition: "2015",
+ edition: "2018",
features: [
"aho-corasick",
"default",
@@ -71,6 +71,6 @@
}
// dependent_library ["feature_list"]
-// aho-corasick-0.7.15 "default,std"
-// memchr-2.3.4 "default,std,use_std"
-// regex-syntax-0.6.23 "default,unicode,unicode-age,unicode-bool,unicode-case,unicode-gencat,unicode-perl,unicode-script,unicode-segment"
+// aho-corasick-0.7.18 "default,std"
+// memchr-2.4.0 "default,std"
+// regex-syntax-0.6.25 "default,unicode,unicode-age,unicode-bool,unicode-case,unicode-gencat,unicode-perl,unicode-script,unicode-segment"
diff --git a/CHANGELOG.md b/CHANGELOG.md
index f294972..71d1963 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,67 @@
+1.5.4 (2021-05-06)
+==================
+This release fixes another compilation failure when building regex. This time,
+the fix is for when the `pattern` feature is enabled, which only works on
+nightly Rust. CI has been updated to test this case.
+
+* [BUG #772](https://github.com/rust-lang/regex/pull/772):
+ Fix build when `pattern` feature is enabled.
+
+
+1.5.3 (2021-05-01)
+==================
+This releases fixes a bug when building regex with only the `unicode-perl`
+feature. It turns out that while CI was building this configuration, it wasn't
+actually failing the overall build on a failed compilation.
+
+* [BUG #769](https://github.com/rust-lang/regex/issues/769):
+ Fix build in `regex-syntax` when only the `unicode-perl` feature is enabled.
+
+
+1.5.2 (2021-05-01)
+==================
+This release fixes a performance bug when Unicode word boundaries are used.
+Namely, for certain regexes on certain inputs, it's possible for the lazy DFA
+to stop searching (causing a fallback to a slower engine) when it doesn't
+actually need to.
+
+[PR #768](https://github.com/rust-lang/regex/pull/768) fixes the bug, which was
+originally reported in
+[ripgrep#1860](https://github.com/BurntSushi/ripgrep/issues/1860).
+
+
+1.5.1 (2021-04-30)
+==================
+This is a patch release that fixes a compilation error when the `perf-literal`
+feature is not enabled.
+
+
+1.5.0 (2021-04-30)
+==================
+This release primarily updates to Rust 2018 (finally) and bumps the MSRV to
+Rust 1.41 (from Rust 1.28). Rust 1.41 was chosen because it's still reasonably
+old, and is what's in Debian stable at the time of writing.
+
+This release also drops this crate's own bespoke substring search algorithms
+in favor of a new
+[`memmem` implementation provided by the `memchr` crate](https://docs.rs/memchr/2.4.0/memchr/memmem/index.html).
+This will change the performance profile of some regexes, sometimes getting a
+little worse, and hopefully more frequently, getting a lot better. Please
+report any serious performance regressions if you find them.
+
+
+1.4.6 (2021-04-22)
+==================
+This is a small patch release that fixes the compiler's size check on how much
+heap memory a regex uses. Previously, the compiler did not account for the
+heap usage of Unicode character classes. Now it does. It's possible that this
+may make some regexes fail to compile that previously did compile. If that
+happens, please file an issue.
+
+* [BUG OSS-fuzz#33579](https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=33579):
+ Some regexes can use more heap memory than one would expect.
+
+
1.4.5 (2021-03-14)
==================
This is a small patch release that fixes a regression in the size of a `Regex`
diff --git a/Cargo.toml b/Cargo.toml
index 6f8ef4e..260acec 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,8 +11,9 @@
# will likely look very different (and much more reasonable)
[package]
+edition = "2018"
name = "regex"
-version = "1.4.5"
+version = "1.5.4"
authors = ["The Rust Project Developers"]
exclude = ["/scripts/*", "/.github/*"]
autotests = false
@@ -72,15 +73,15 @@
name = "crates-regex"
path = "tests/test_crates_regex.rs"
[dependencies.aho-corasick]
-version = "0.7.6"
+version = "0.7.18"
optional = true
[dependencies.memchr]
-version = "2.2.1"
+version = "2.4.0"
optional = true
[dependencies.regex-syntax]
-version = "0.6.22"
+version = "0.6.25"
default-features = false
[dev-dependencies.lazy_static]
version = "1"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 4b9ca7f..468230b 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "regex"
-version = "1.4.5" #:version
+version = "1.5.4" #:version
authors = ["The Rust Project Developers"]
license = "MIT OR Apache-2.0"
readme = "README.md"
@@ -14,6 +14,7 @@
categories = ["text-processing"]
autotests = false
exclude = ["/scripts/*", "/.github/*"]
+edition = "2018"
[workspace]
members = [
@@ -105,18 +106,18 @@
# For very fast prefix literal matching.
[dependencies.aho-corasick]
-version = "0.7.6"
+version = "0.7.18"
optional = true
# For skipping along search text quickly when a leading byte is known.
[dependencies.memchr]
-version = "2.2.1"
+version = "2.4.0"
optional = true
# For parsing regular expressions.
[dependencies.regex-syntax]
path = "regex-syntax"
-version = "0.6.22"
+version = "0.6.25"
default-features = false
[dev-dependencies]
diff --git a/METADATA b/METADATA
index 52d2bfe..6611aac 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/regex/regex-1.4.5.crate"
+ value: "https://static.crates.io/crates/regex/regex-1.5.4.crate"
}
- version: "1.4.5"
+ version: "1.5.4"
license_type: NOTICE
last_upgrade_date {
year: 2021
- month: 4
- day: 1
+ month: 5
+ day: 19
}
}
diff --git a/PERFORMANCE.md b/PERFORMANCE.md
index b4aeb89..8cd0d9c 100644
--- a/PERFORMANCE.md
+++ b/PERFORMANCE.md
@@ -62,9 +62,7 @@
[`lazy_static`](https://crates.io/crates/lazy_static)
crate provides an answer that works well:
- #[macro_use] extern crate lazy_static;
- extern crate regex;
-
+ use lazy_static::lazy_static;
use regex::Regex;
fn some_helper_function(text: &str) -> bool {
@@ -147,9 +145,9 @@
`is_match` is fastest because it doesn't actually need to find the start or the
end of the leftmost-first match. It can quit immediately after it knows there
is a match. For example, given the regex `a+` and the haystack, `aaaaa`, the
-search will quit after examing the first byte.
+search will quit after examining the first byte.
-In constrast, `find` must return both the start and end location of the
+In contrast, `find` must return both the start and end location of the
leftmost-first match. It can use the DFA matcher for this, but must run it
forwards once to find the end of the match *and then run it backwards* to find
the start of the match. The two scans and the cost of finding the real end of
@@ -198,7 +196,7 @@
Literals in anchored regexes can also be used for detecting non-matches very
quickly. For example, `^foo\w+` and `\w+foo$` may be able to detect a non-match
-just by examing the first (or last) three bytes of the haystack.
+just by examining the first (or last) three bytes of the haystack.
## Unicode word boundaries may prevent the DFA from being used
diff --git a/README.md b/README.md
index f7a2554..86d6996 100644
--- a/README.md
+++ b/README.md
@@ -9,7 +9,7 @@
[](https://github.com/rust-lang/regex/actions)
[](https://crates.io/crates/regex)
-[](https://github.com/rust-lang/regex)
+[](https://github.com/rust-lang/regex)
### Documentation
@@ -27,13 +27,7 @@
```toml
[dependencies]
-regex = "1"
-```
-
-and this to your crate root (if you're using Rust 2015):
-
-```rust
-extern crate regex;
+regex = "1.5"
```
Here's a simple example that matches a date in YYYY-MM-DD format and prints the
@@ -228,7 +222,7 @@
### Minimum Rust version policy
-This crate's minimum supported `rustc` version is `1.28.0`.
+This crate's minimum supported `rustc` version is `1.41.1`.
The current **tentative** policy is that the minimum Rust version required
to use this crate can be increased in minor version updates. For example, if
diff --git a/TEST_MAPPING b/TEST_MAPPING
index ee45373..a731acb 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -5,10 +5,10 @@
"name": "keystore2_test"
},
{
- "name": "vpnprofilestore_test"
+ "name": "libsqlite3-sys_device_test_src_lib"
},
{
- "name": "libsqlite3-sys_device_test_src_lib"
+ "name": "vpnprofilestore_test"
}
]
}
diff --git a/examples/shootout-regex-dna-bytes.rs b/examples/shootout-regex-dna-bytes.rs
index ac4c115..773fd9b 100644
--- a/examples/shootout-regex-dna-bytes.rs
+++ b/examples/shootout-regex-dna-bytes.rs
@@ -5,8 +5,6 @@
// contributed by TeXitoi
// contributed by BurntSushi
-extern crate regex;
-
use std::io::{self, Read};
use std::sync::Arc;
use std::thread;
diff --git a/examples/shootout-regex-dna-cheat.rs b/examples/shootout-regex-dna-cheat.rs
index c7395b7..1bde7ab 100644
--- a/examples/shootout-regex-dna-cheat.rs
+++ b/examples/shootout-regex-dna-cheat.rs
@@ -10,8 +10,6 @@
// replacing them with a single linear scan. i.e., it re-implements
// `replace_all`. As a result, this is around 25% faster. ---AG
-extern crate regex;
-
use std::io::{self, Read};
use std::sync::Arc;
use std::thread;
diff --git a/examples/shootout-regex-dna-replace.rs b/examples/shootout-regex-dna-replace.rs
index 681e077..20694e0 100644
--- a/examples/shootout-regex-dna-replace.rs
+++ b/examples/shootout-regex-dna-replace.rs
@@ -1,5 +1,3 @@
-extern crate regex;
-
use std::io::{self, Read};
macro_rules! regex {
diff --git a/examples/shootout-regex-dna-single-cheat.rs b/examples/shootout-regex-dna-single-cheat.rs
index 04ed05a..70a979c 100644
--- a/examples/shootout-regex-dna-single-cheat.rs
+++ b/examples/shootout-regex-dna-single-cheat.rs
@@ -5,8 +5,6 @@
// contributed by TeXitoi
// contributed by BurntSushi
-extern crate regex;
-
use std::io::{self, Read};
macro_rules! regex {
diff --git a/examples/shootout-regex-dna-single.rs b/examples/shootout-regex-dna-single.rs
index a70c711..b474059 100644
--- a/examples/shootout-regex-dna-single.rs
+++ b/examples/shootout-regex-dna-single.rs
@@ -5,8 +5,6 @@
// contributed by TeXitoi
// contributed by BurntSushi
-extern crate regex;
-
use std::io::{self, Read};
macro_rules! regex {
diff --git a/examples/shootout-regex-dna.rs b/examples/shootout-regex-dna.rs
index 4527422..b96518e 100644
--- a/examples/shootout-regex-dna.rs
+++ b/examples/shootout-regex-dna.rs
@@ -5,8 +5,6 @@
// contributed by TeXitoi
// contributed by BurntSushi
-extern crate regex;
-
use std::io::{self, Read};
use std::sync::Arc;
use std::thread;
diff --git a/src/backtrack.rs b/src/backtrack.rs
index 6100c17..a3d25d6 100644
--- a/src/backtrack.rs
+++ b/src/backtrack.rs
@@ -16,10 +16,10 @@
// the bitset has to be zeroed on each execution, which becomes quite expensive
// on large bitsets.
-use exec::ProgramCache;
-use input::{Input, InputAt};
-use prog::{InstPtr, Program};
-use re_trait::Slot;
+use crate::exec::ProgramCache;
+use crate::input::{Input, InputAt};
+use crate::prog::{InstPtr, Program};
+use crate::re_trait::Slot;
type Bits = u32;
@@ -196,7 +196,7 @@
}
fn step(&mut self, mut ip: InstPtr, mut at: InputAt) -> bool {
- use prog::Inst::*;
+ use crate::prog::Inst::*;
loop {
// This loop is an optimization to avoid constantly pushing/popping
// from the stack. Namely, if we're pushing a job only to run it
diff --git a/src/compile.rs b/src/compile.rs
index 9ffd347..9a2ed5e 100644
--- a/src/compile.rs
+++ b/src/compile.rs
@@ -4,16 +4,16 @@
use std::result;
use std::sync::Arc;
-use syntax::hir::{self, Hir};
-use syntax::is_word_byte;
-use syntax::utf8::{Utf8Range, Utf8Sequence, Utf8Sequences};
+use regex_syntax::hir::{self, Hir};
+use regex_syntax::is_word_byte;
+use regex_syntax::utf8::{Utf8Range, Utf8Sequence, Utf8Sequences};
-use prog::{
+use crate::prog::{
EmptyLook, Inst, InstBytes, InstChar, InstEmptyLook, InstPtr, InstRanges,
InstSave, InstSplit, Program,
};
-use Error;
+use crate::Error;
type Result = result::Result<Patch, Error>;
type ResultOrEmpty = result::Result<Option<Patch>, Error>;
@@ -38,6 +38,7 @@
suffix_cache: SuffixCache,
utf8_seqs: Option<Utf8Sequences>,
byte_classes: ByteClassSet,
+ extra_inst_bytes: usize,
}
impl Compiler {
@@ -54,6 +55,7 @@
suffix_cache: SuffixCache::new(1000),
utf8_seqs: Some(Utf8Sequences::new('\x00', '\x00')),
byte_classes: ByteClassSet::new(),
+ extra_inst_bytes: 0,
}
}
@@ -253,8 +255,8 @@
/// Ok(None) is returned when an expression is compiled to no
/// instruction, and so no patch.entry value makes sense.
fn c(&mut self, expr: &Hir) -> ResultOrEmpty {
- use prog;
- use syntax::hir::HirKind::*;
+ use crate::prog;
+ use regex_syntax::hir::HirKind::*;
self.check_size()?;
match *expr.kind() {
@@ -316,6 +318,13 @@
}
self.compiled.has_unicode_word_boundary = true;
self.byte_classes.set_word_boundary();
+ // We also make sure that all ASCII bytes are in a different
+ // class from non-ASCII bytes. Otherwise, it's possible for
+ // ASCII bytes to get lumped into the same class as non-ASCII
+ // bytes. This in turn may cause the lazy DFA to falsely start
+ // when it sees an ASCII byte that maps to a byte class with
+ // non-ASCII bytes. This ensures that never happens.
+ self.byte_classes.set_range(0, 0x7F);
self.c_empty_look(prog::EmptyLook::WordBoundary)
}
WordBoundary(hir::WordBoundary::UnicodeNegate) => {
@@ -328,6 +337,8 @@
}
self.compiled.has_unicode_word_boundary = true;
self.byte_classes.set_word_boundary();
+ // See comments above for why we set the ASCII range here.
+ self.byte_classes.set_range(0, 0x7F);
self.c_empty_look(prog::EmptyLook::NotWordBoundary)
}
WordBoundary(hir::WordBoundary::Ascii) => {
@@ -420,6 +431,8 @@
}
fn c_class(&mut self, ranges: &[hir::ClassUnicodeRange]) -> ResultOrEmpty {
+ use std::mem::size_of;
+
assert!(!ranges.is_empty());
if self.compiled.uses_bytes() {
Ok(Some(CompileClass { c: self, ranges: ranges }.compile()?))
@@ -429,6 +442,8 @@
let hole = if ranges.len() == 1 && ranges[0].0 == ranges[0].1 {
self.push_hole(InstHole::Char { c: ranges[0].0 })
} else {
+ self.extra_inst_bytes +=
+ ranges.len() * (size_of::<char>() * 2);
self.push_hole(InstHole::Ranges { ranges: ranges })
};
Ok(Some(Patch { hole: hole, entry: self.insts.len() - 1 }))
@@ -548,7 +563,7 @@
}
fn c_repeat(&mut self, rep: &hir::Repetition) -> ResultOrEmpty {
- use syntax::hir::RepetitionKind::*;
+ use regex_syntax::hir::RepetitionKind::*;
match rep.kind {
ZeroOrOne => self.c_repeat_zero_or_one(&rep.hir, rep.greedy),
ZeroOrMore => self.c_repeat_zero_or_more(&rep.hir, rep.greedy),
@@ -795,7 +810,9 @@
fn check_size(&self) -> result::Result<(), Error> {
use std::mem::size_of;
- if self.insts.len() * size_of::<Inst>() > self.size_limit {
+ let size =
+ self.extra_inst_bytes + (self.insts.len() * size_of::<Inst>());
+ if size > self.size_limit {
Err(Error::CompiledTooBig(self.size_limit))
} else {
Ok(())
@@ -927,9 +944,10 @@
Inst::EmptyLook(InstEmptyLook { goto: goto, look: look })
}
InstHole::Char { c } => Inst::Char(InstChar { goto: goto, c: c }),
- InstHole::Ranges { ref ranges } => {
- Inst::Ranges(InstRanges { goto: goto, ranges: ranges.clone() })
- }
+ InstHole::Ranges { ref ranges } => Inst::Ranges(InstRanges {
+ goto: goto,
+ ranges: ranges.clone().into_boxed_slice(),
+ }),
InstHole::Bytes { start, end } => {
Inst::Bytes(InstBytes { goto: goto, start: start, end: end })
}
diff --git a/src/dfa.rs b/src/dfa.rs
index 9ac0c2c..4b60f4d 100644
--- a/src/dfa.rs
+++ b/src/dfa.rs
@@ -42,9 +42,9 @@
use std::mem;
use std::sync::Arc;
-use exec::ProgramCache;
-use prog::{Inst, Program};
-use sparse::SparseSet;
+use crate::exec::ProgramCache;
+use crate::prog::{Inst, Program};
+use crate::sparse::SparseSet;
/// Return true if and only if the given program can be executed by a DFA.
///
@@ -55,7 +55,7 @@
/// This function will also return false if the given program has any Unicode
/// instructions (Char or Ranges) since the DFA operates on bytes only.
pub fn can_exec(insts: &Program) -> bool {
- use prog::Inst::*;
+ use crate::prog::Inst::*;
// If for some reason we manage to allocate a regex program with more
// than i32::MAX instructions, then we can't execute the DFA because we
// use 32 bit instruction pointer deltas for memory savings.
@@ -306,7 +306,7 @@
StateFlags(self.data[0])
}
- fn inst_ptrs(&self) -> InstPtrs {
+ fn inst_ptrs(&self) -> InstPtrs<'_> {
InstPtrs { base: 0, data: &self.data[1..] }
}
}
@@ -894,7 +894,7 @@
mut si: StatePtr,
b: Byte,
) -> Option<StatePtr> {
- use prog::Inst::*;
+ use crate::prog::Inst::*;
// Initialize a queue with the current DFA state's NFA states.
qcur.clear();
@@ -1056,8 +1056,8 @@
q: &mut SparseSet,
flags: EmptyFlags,
) {
- use prog::EmptyLook::*;
- use prog::Inst::*;
+ use crate::prog::EmptyLook::*;
+ use crate::prog::Inst::*;
// We need to traverse the NFA to follow epsilon transitions, so avoid
// recursion with an explicit stack.
@@ -1190,7 +1190,7 @@
q: &SparseSet,
state_flags: &mut StateFlags,
) -> Option<State> {
- use prog::Inst::*;
+ use crate::prog::Inst::*;
// We need to build up enough information to recognize pre-built states
// in the DFA. Generally speaking, this includes every instruction
@@ -1754,7 +1754,7 @@
}
impl fmt::Debug for State {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let ips: Vec<usize> = self.inst_ptrs().collect();
f.debug_struct("State")
.field("flags", &self.flags())
@@ -1764,7 +1764,7 @@
}
impl fmt::Debug for Transitions {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut fmtd = f.debug_map();
for si in 0..self.num_states() {
let s = si * self.num_byte_classes;
@@ -1778,7 +1778,7 @@
struct TransitionsRow<'a>(&'a [StatePtr]);
impl<'a> fmt::Debug for TransitionsRow<'a> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut fmtd = f.debug_map();
for (b, si) in self.0.iter().enumerate() {
match *si {
@@ -1796,7 +1796,7 @@
}
impl fmt::Debug for StateFlags {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("StateFlags")
.field("is_match", &self.is_match())
.field("is_word", &self.is_word())
@@ -1889,7 +1889,6 @@
#[cfg(test)]
mod tests {
- extern crate rand;
use super::{
push_inst_ptr, read_vari32, read_varu32, write_vari32, write_varu32,
diff --git a/src/error.rs b/src/error.rs
index 1c32c85..3e0ec75 100644
--- a/src/error.rs
+++ b/src/error.rs
@@ -31,7 +31,7 @@
}
impl fmt::Display for Error {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Error::Syntax(ref err) => err.fmt(f),
Error::CompiledTooBig(limit) => write!(
@@ -49,7 +49,7 @@
// but the `Syntax` variant is already storing a `String` anyway, so we might
// as well format it nicely.
impl fmt::Debug for Error {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Error::Syntax(ref err) => {
let hr: String = repeat('~').take(79).collect();
diff --git a/src/exec.rs b/src/exec.rs
index 3d5a52b..d5fad1c 100644
--- a/src/exec.rs
+++ b/src/exec.rs
@@ -5,26 +5,26 @@
#[cfg(feature = "perf-literal")]
use aho_corasick::{AhoCorasick, AhoCorasickBuilder, MatchKind};
-use syntax::hir::literal::Literals;
-use syntax::hir::Hir;
-use syntax::ParserBuilder;
+use regex_syntax::hir::literal::Literals;
+use regex_syntax::hir::Hir;
+use regex_syntax::ParserBuilder;
-use backtrack;
-use compile::Compiler;
+use crate::backtrack;
+use crate::compile::Compiler;
#[cfg(feature = "perf-dfa")]
-use dfa;
-use error::Error;
-use input::{ByteInput, CharInput};
-use literal::LiteralSearcher;
-use pikevm;
-use pool::{Pool, PoolGuard};
-use prog::Program;
-use re_builder::RegexOptions;
-use re_bytes;
-use re_set;
-use re_trait::{Locations, RegularExpression, Slot};
-use re_unicode;
-use utf8::next_utf8;
+use crate::dfa;
+use crate::error::Error;
+use crate::input::{ByteInput, CharInput};
+use crate::literal::LiteralSearcher;
+use crate::pikevm;
+use crate::pool::{Pool, PoolGuard};
+use crate::prog::Program;
+use crate::re_builder::RegexOptions;
+use crate::re_bytes;
+use crate::re_set;
+use crate::re_trait::{Locations, RegularExpression, Slot};
+use crate::re_unicode;
+use crate::utf8::next_utf8;
/// `Exec` manages the execution of a regular expression.
///
@@ -140,7 +140,7 @@
///
/// Note that when compiling 2 or more regular expressions, capture groups
/// are completely unsupported. (This means both `find` and `captures`
- /// wont work.)
+ /// won't work.)
pub fn new_many<I, S>(res: I) -> Self
where
S: AsRef<str>,
@@ -373,9 +373,6 @@
AhoCorasickBuilder::new()
.match_kind(MatchKind::LeftmostFirst)
.auto_configure(&lits)
- // We always want this to reduce size, regardless
- // of what auto-configure does.
- .byte_classes(true)
.build_with_size::<u32, _, _>(&lits)
// This should never happen because we'd long exceed the
// compilation limit for regexes first.
@@ -739,7 +736,7 @@
text: &[u8],
start: usize,
) -> dfa::Result<(usize, usize)> {
- use dfa::Result::*;
+ use crate::dfa::Result::*;
let end = match dfa::Fsm::forward(
&self.ro.dfa,
self.cache.value(),
@@ -779,7 +776,7 @@
text: &[u8],
start: usize,
) -> dfa::Result<(usize, usize)> {
- use dfa::Result::*;
+ use crate::dfa::Result::*;
match dfa::Fsm::reverse(
&self.ro.dfa_reverse,
self.cache.value(),
@@ -835,7 +832,7 @@
text: &[u8],
original_start: usize,
) -> Option<dfa::Result<(usize, usize)>> {
- use dfa::Result::*;
+ use crate::dfa::Result::*;
let lcs = self.ro.suffixes.lcs();
debug_assert!(lcs.len() >= 1);
@@ -880,7 +877,7 @@
text: &[u8],
start: usize,
) -> dfa::Result<(usize, usize)> {
- use dfa::Result::*;
+ use crate::dfa::Result::*;
let match_start = match self.exec_dfa_reverse_suffix(text, start) {
None => return self.find_dfa_forward(text, start),
@@ -1263,7 +1260,7 @@
impl Exec {
/// Get a searcher that isn't Sync.
#[cfg_attr(feature = "perf-inline", inline(always))]
- pub fn searcher(&self) -> ExecNoSync {
+ pub fn searcher(&self) -> ExecNoSync<'_> {
ExecNoSync {
ro: &self.ro, // a clone is too expensive here! (and not needed)
cache: self.pool.get(),
@@ -1272,7 +1269,7 @@
/// Get a searcher that isn't Sync and can match on &str.
#[cfg_attr(feature = "perf-inline", inline(always))]
- pub fn searcher_str(&self) -> ExecNoSyncStr {
+ pub fn searcher_str(&self) -> ExecNoSyncStr<'_> {
ExecNoSyncStr(self.searcher())
}
@@ -1550,7 +1547,7 @@
/// literals, and if so, returns them. Otherwise, this returns None.
#[cfg(feature = "perf-literal")]
fn alternation_literals(expr: &Hir) -> Option<Vec<Vec<u8>>> {
- use syntax::hir::{HirKind, Literal};
+ use regex_syntax::hir::{HirKind, Literal};
// This is pretty hacky, but basically, if `is_alternation_literal` is
// true, then we can make several assumptions about the structure of our
@@ -1602,7 +1599,7 @@
mod test {
#[test]
fn uppercut_s_backtracking_bytes_default_bytes_mismatch() {
- use internal::ExecBuilder;
+ use crate::internal::ExecBuilder;
let backtrack_bytes_re = ExecBuilder::new("^S")
.bounded_backtracking()
@@ -1630,7 +1627,7 @@
#[test]
fn unicode_lit_star_backtracking_utf8bytes_default_utf8bytes_mismatch() {
- use internal::ExecBuilder;
+ use crate::internal::ExecBuilder;
let backtrack_bytes_re = ExecBuilder::new(r"^(?u:\*)")
.bounded_backtracking()
diff --git a/src/expand.rs b/src/expand.rs
index 70dbf91..fd9c2d0 100644
--- a/src/expand.rs
+++ b/src/expand.rs
@@ -1,12 +1,12 @@
use std::str;
-use find_byte::find_byte;
+use crate::find_byte::find_byte;
-use re_bytes;
-use re_unicode;
+use crate::re_bytes;
+use crate::re_unicode;
pub fn expand_str(
- caps: &re_unicode::Captures,
+ caps: &re_unicode::Captures<'_>,
mut replacement: &str,
dst: &mut String,
) {
@@ -48,7 +48,7 @@
}
pub fn expand_bytes(
- caps: &re_bytes::Captures,
+ caps: &re_bytes::Captures<'_>,
mut replacement: &[u8],
dst: &mut Vec<u8>,
) {
@@ -125,7 +125,7 @@
/// starting at the beginning of `replacement`.
///
/// If no such valid reference could be found, None is returned.
-fn find_cap_ref(replacement: &[u8]) -> Option<CaptureRef> {
+fn find_cap_ref(replacement: &[u8]) -> Option<CaptureRef<'_>> {
let mut i = 0;
let rep: &[u8] = replacement.as_ref();
if rep.len() <= 1 || rep[0] != b'$' {
@@ -157,7 +157,7 @@
})
}
-fn find_cap_ref_braced(rep: &[u8], mut i: usize) -> Option<CaptureRef> {
+fn find_cap_ref_braced(rep: &[u8], mut i: usize) -> Option<CaptureRef<'_>> {
let start = i;
while rep.get(i).map_or(false, |&b| b != b'}') {
i += 1;
diff --git a/src/input.rs b/src/input.rs
index 3afa2d0..5d50ee3 100644
--- a/src/input.rs
+++ b/src/input.rs
@@ -4,11 +4,9 @@
use std::ops;
use std::u32;
-use syntax;
-
-use literal::LiteralSearcher;
-use prog::InstEmptyLook;
-use utf8::{decode_last_utf8, decode_utf8};
+use crate::literal::LiteralSearcher;
+use crate::prog::InstEmptyLook;
+use crate::utf8::{decode_last_utf8, decode_utf8};
/// Represents a location in the input.
#[derive(Clone, Copy, Debug)]
@@ -175,7 +173,7 @@
}
fn is_empty_match(&self, at: InputAt, empty: &InstEmptyLook) -> bool {
- use prog::EmptyLook::*;
+ use crate::prog::EmptyLook::*;
match empty.look {
StartLine => {
let c = self.previous_char(at);
@@ -268,7 +266,7 @@
}
fn is_empty_match(&self, at: InputAt, empty: &InstEmptyLook) -> bool {
- use prog::EmptyLook::*;
+ use crate::prog::EmptyLook::*;
match empty.look {
StartLine => {
let c = self.previous_char(at);
@@ -348,7 +346,7 @@
pub struct Char(u32);
impl fmt::Debug for Char {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match char::from_u32(self.0) {
None => write!(f, "Empty"),
Some(c) => write!(f, "{:?}", c),
@@ -379,7 +377,7 @@
// available. However, our compiler ensures that if a Unicode word
// boundary is used, then the data must also be available. If it isn't,
// then the compiler returns an error.
- char::from_u32(self.0).map_or(false, syntax::is_word_character)
+ char::from_u32(self.0).map_or(false, regex_syntax::is_word_character)
}
/// Returns true iff the byte is a word byte.
@@ -387,7 +385,7 @@
/// If the byte is absent, then false is returned.
pub fn is_word_byte(self) -> bool {
match char::from_u32(self.0) {
- Some(c) if c <= '\u{7F}' => syntax::is_word_byte(c as u8),
+ Some(c) if c <= '\u{7F}' => regex_syntax::is_word_byte(c as u8),
None | Some(_) => false,
}
}
diff --git a/src/lib.rs b/src/lib.rs
index 357ac0d..7f2dec8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -22,12 +22,6 @@
regex = "1"
```
-If you're using Rust 2015, then you'll also need to add it to your crate root:
-
-```rust
-extern crate regex;
-```
-
# Example: find a date
General use of regular expressions in this package involves compiling an
@@ -68,9 +62,7 @@
For example:
```rust
-#[macro_use] extern crate lazy_static;
-extern crate regex;
-
+use lazy_static::lazy_static;
use regex::Regex;
fn some_helper_function(text: &str) -> bool {
@@ -94,7 +86,7 @@
them by their component pieces:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(\d{4})-(\d{2})-(\d{2})").unwrap();
let text = "2012-03-14, 2013-01-01 and 2014-07-05";
@@ -119,7 +111,7 @@
in our replacement text:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(?P<y>\d{4})-(?P<m>\d{2})-(?P<d>\d{2})").unwrap();
let before = "2012-03-14, 2013-01-01 and 2014-07-05";
@@ -136,7 +128,7 @@
enable insignificant whitespace mode, which also lets you write comments:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(?x)
(?P<y>\d{4}) # the year
@@ -217,7 +209,7 @@
in your expression:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(?i)Δ+").unwrap();
let mat = re.find("ΔδΔ").unwrap();
@@ -244,7 +236,7 @@
match a sequence of numerals, Greek or Cherokee letters:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"[\pN\p{Greek}\p{Cherokee}]+").unwrap();
let mat = re.find("abcΔᎠβⅠᏴγδⅡxyz").unwrap();
@@ -391,7 +383,7 @@
case-insensitively for the first part but case-sensitively for the second part:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(?i)a+(?-i)b+").unwrap();
let cap = re.captures("AaAaAbbBBBb").unwrap();
@@ -425,7 +417,7 @@
word boundary:
```rust
-# extern crate regex; use regex::Regex;
+# use regex::Regex;
# fn main() {
let re = Regex::new(r"(?-u:\b).+(?-u:\b)").unwrap();
let cap = re.captures("$$abc$$").unwrap();
@@ -614,38 +606,30 @@
*/
#![deny(missing_docs)]
-#![cfg_attr(test, deny(warnings))]
#![cfg_attr(feature = "pattern", feature(pattern))]
#![warn(missing_debug_implementations)]
#[cfg(not(feature = "std"))]
compile_error!("`std` feature is currently required to build this crate");
-#[cfg(feature = "perf-literal")]
-extern crate aho_corasick;
-// #[cfg(doctest)]
-// extern crate doc_comment;
-#[cfg(feature = "perf-literal")]
-extern crate memchr;
-#[cfg(test)]
-#[cfg_attr(feature = "perf-literal", macro_use)]
-extern crate quickcheck;
-extern crate regex_syntax as syntax;
-
+// To check README's example
+// TODO: Re-enable this once the MSRV is 1.43 or greater.
+// See: https://github.com/rust-lang/regex/issues/684
+// See: https://github.com/rust-lang/regex/issues/685
// #[cfg(doctest)]
// doc_comment::doctest!("../README.md");
#[cfg(feature = "std")]
-pub use error::Error;
+pub use crate::error::Error;
#[cfg(feature = "std")]
-pub use re_builder::set_unicode::*;
+pub use crate::re_builder::set_unicode::*;
#[cfg(feature = "std")]
-pub use re_builder::unicode::*;
+pub use crate::re_builder::unicode::*;
#[cfg(feature = "std")]
-pub use re_set::unicode::*;
+pub use crate::re_set::unicode::*;
#[cfg(feature = "std")]
#[cfg(feature = "std")]
-pub use re_unicode::{
+pub use crate::re_unicode::{
escape, CaptureLocations, CaptureMatches, CaptureNames, Captures,
Locations, Match, Matches, NoExpand, Regex, Replacer, ReplacerRef, Split,
SplitN, SubCaptureMatches,
@@ -740,10 +724,10 @@
*/
#[cfg(feature = "std")]
pub mod bytes {
- pub use re_builder::bytes::*;
- pub use re_builder::set_bytes::*;
- pub use re_bytes::*;
- pub use re_set::bytes::*;
+ pub use crate::re_builder::bytes::*;
+ pub use crate::re_builder::set_bytes::*;
+ pub use crate::re_bytes::*;
+ pub use crate::re_set::bytes::*;
}
mod backtrack;
@@ -754,8 +738,6 @@
mod exec;
mod expand;
mod find_byte;
-#[cfg(feature = "perf-literal")]
-mod freqs;
mod input;
mod literal;
#[cfg(feature = "pattern")]
@@ -777,9 +759,9 @@
#[doc(hidden)]
#[cfg(feature = "std")]
pub mod internal {
- pub use compile::Compiler;
- pub use exec::{Exec, ExecBuilder};
- pub use input::{Char, CharInput, Input, InputAt};
- pub use literal::LiteralSearcher;
- pub use prog::{EmptyLook, Inst, InstRanges, Program};
+ pub use crate::compile::Compiler;
+ pub use crate::exec::{Exec, ExecBuilder};
+ pub use crate::input::{Char, CharInput, Input, InputAt};
+ pub use crate::literal::LiteralSearcher;
+ pub use crate::prog::{EmptyLook, Inst, InstRanges, Program};
}
diff --git a/src/literal/imp.rs b/src/literal/imp.rs
index e4d04ed..82f050a 100644
--- a/src/literal/imp.rs
+++ b/src/literal/imp.rs
@@ -1,11 +1,8 @@
-use std::cmp;
use std::mem;
use aho_corasick::{self, packed, AhoCorasick, AhoCorasickBuilder};
-use memchr::{memchr, memchr2, memchr3};
-use syntax::hir::literal::{Literal, Literals};
-
-use freqs::BYTE_FREQUENCIES;
+use memchr::{memchr, memchr2, memchr3, memmem};
+use regex_syntax::hir::literal::{Literal, Literals};
/// A prefix extracted from a compiled regular expression.
///
@@ -15,8 +12,8 @@
#[derive(Clone, Debug)]
pub struct LiteralSearcher {
complete: bool,
- lcp: FreqyPacked,
- lcs: FreqyPacked,
+ lcp: Memmem,
+ lcs: Memmem,
matcher: Matcher,
}
@@ -26,10 +23,8 @@
Empty,
/// A set of four or more single byte literals.
Bytes(SingleByteSet),
- /// A single substring, find using memchr and frequency analysis.
- FreqyPacked(FreqyPacked),
- /// A single substring, find using Boyer-Moore.
- BoyerMoore(BoyerMooreSearch),
+ /// A single substring, using vector accelerated routines when available.
+ Memmem(Memmem),
/// An Aho-Corasick automaton.
AC { ac: AhoCorasick<u32>, lits: Vec<Literal> },
/// A packed multiple substring searcher, using SIMD.
@@ -63,8 +58,8 @@
let complete = lits.all_complete();
LiteralSearcher {
complete: complete,
- lcp: FreqyPacked::new(lits.longest_common_prefix().to_vec()),
- lcs: FreqyPacked::new(lits.longest_common_suffix().to_vec()),
+ lcp: Memmem::new(lits.longest_common_prefix()),
+ lcs: Memmem::new(lits.longest_common_suffix()),
matcher: matcher,
}
}
@@ -86,8 +81,7 @@
match self.matcher {
Empty => Some((0, 0)),
Bytes(ref sset) => sset.find(haystack).map(|i| (i, i + 1)),
- FreqyPacked(ref s) => s.find(haystack).map(|i| (i, i + s.len())),
- BoyerMoore(ref s) => s.find(haystack).map(|i| (i, i + s.len())),
+ Memmem(ref s) => s.find(haystack).map(|i| (i, i + s.len())),
AC { ref ac, .. } => {
ac.find(haystack).map(|m| (m.start(), m.end()))
}
@@ -124,24 +118,23 @@
}
/// Returns an iterator over all literals to be matched.
- pub fn iter(&self) -> LiteralIter {
+ pub fn iter(&self) -> LiteralIter<'_> {
match self.matcher {
Matcher::Empty => LiteralIter::Empty,
Matcher::Bytes(ref sset) => LiteralIter::Bytes(&sset.dense),
- Matcher::FreqyPacked(ref s) => LiteralIter::Single(&s.pat),
- Matcher::BoyerMoore(ref s) => LiteralIter::Single(&s.pattern),
+ Matcher::Memmem(ref s) => LiteralIter::Single(&s.finder.needle()),
Matcher::AC { ref lits, .. } => LiteralIter::AC(lits),
Matcher::Packed { ref lits, .. } => LiteralIter::Packed(lits),
}
}
/// Returns a matcher for the longest common prefix of this matcher.
- pub fn lcp(&self) -> &FreqyPacked {
+ pub fn lcp(&self) -> &Memmem {
&self.lcp
}
/// Returns a matcher for the longest common suffix of this matcher.
- pub fn lcs(&self) -> &FreqyPacked {
+ pub fn lcs(&self) -> &Memmem {
&self.lcs
}
@@ -156,8 +149,7 @@
match self.matcher {
Empty => 0,
Bytes(ref sset) => sset.dense.len(),
- FreqyPacked(_) => 1,
- BoyerMoore(_) => 1,
+ Memmem(_) => 1,
AC { ref ac, .. } => ac.pattern_count(),
Packed { ref lits, .. } => lits.len(),
}
@@ -169,8 +161,7 @@
match self.matcher {
Empty => 0,
Bytes(ref sset) => sset.approximate_size(),
- FreqyPacked(ref single) => single.approximate_size(),
- BoyerMoore(ref single) => single.approximate_size(),
+ Memmem(ref single) => single.approximate_size(),
AC { ref ac, .. } => ac.heap_bytes(),
Packed { ref s, .. } => s.heap_bytes(),
}
@@ -205,12 +196,7 @@
return Matcher::Bytes(sset);
}
if lits.literals().len() == 1 {
- let lit = lits.literals()[0].to_vec();
- if BoyerMooreSearch::should_use(lit.as_slice()) {
- return Matcher::BoyerMoore(BoyerMooreSearch::new(lit));
- } else {
- return Matcher::FreqyPacked(FreqyPacked::new(lit));
- }
+ return Matcher::Memmem(Memmem::new(&lits.literals()[0]));
}
let pats = lits.literals().to_owned();
@@ -367,116 +353,27 @@
}
}
-/// Provides an implementation of fast subtring search using frequency
-/// analysis.
+/// A simple wrapper around the memchr crate's memmem implementation.
///
-/// memchr is so fast that we do everything we can to keep the loop in memchr
-/// for as long as possible. The easiest way to do this is to intelligently
-/// pick the byte to send to memchr. The best byte is the byte that occurs
-/// least frequently in the haystack. Since doing frequency analysis on the
-/// haystack is far too expensive, we compute a set of fixed frequencies up
-/// front and hard code them in src/freqs.rs. Frequency analysis is done via
-/// scripts/frequencies.py.
+/// The API this exposes mirrors the API of previous substring searchers that
+/// this supplanted.
#[derive(Clone, Debug)]
-pub struct FreqyPacked {
- /// The pattern.
- pat: Vec<u8>,
- /// The number of Unicode characters in the pattern. This is useful for
- /// determining the effective length of a pattern when deciding which
- /// optimizations to perform. A trailing incomplete UTF-8 sequence counts
- /// as one character.
+pub struct Memmem {
+ finder: memmem::Finder<'static>,
char_len: usize,
- /// The rarest byte in the pattern, according to pre-computed frequency
- /// analysis.
- rare1: u8,
- /// The offset of the rarest byte in `pat`.
- rare1i: usize,
- /// The second rarest byte in the pattern, according to pre-computed
- /// frequency analysis. (This may be equivalent to the rarest byte.)
- ///
- /// The second rarest byte is used as a type of guard for quickly detecting
- /// a mismatch after memchr locates an instance of the rarest byte. This
- /// is a hedge against pathological cases where the pre-computed frequency
- /// analysis may be off. (But of course, does not prevent *all*
- /// pathological cases.)
- rare2: u8,
- /// The offset of the second rarest byte in `pat`.
- rare2i: usize,
}
-impl FreqyPacked {
- fn new(pat: Vec<u8>) -> FreqyPacked {
- if pat.is_empty() {
- return FreqyPacked::empty();
- }
-
- // Find the rarest two bytes. Try to make them distinct (but it's not
- // required).
- let mut rare1 = pat[0];
- let mut rare2 = pat[0];
- for b in pat[1..].iter().cloned() {
- if freq_rank(b) < freq_rank(rare1) {
- rare1 = b;
- }
- }
- for &b in &pat {
- if rare1 == rare2 {
- rare2 = b
- } else if b != rare1 && freq_rank(b) < freq_rank(rare2) {
- rare2 = b;
- }
- }
-
- // And find the offsets of their last occurrences.
- let rare1i = pat.iter().rposition(|&b| b == rare1).unwrap();
- let rare2i = pat.iter().rposition(|&b| b == rare2).unwrap();
-
- let char_len = char_len_lossy(&pat);
- FreqyPacked {
- pat: pat,
- char_len: char_len,
- rare1: rare1,
- rare1i: rare1i,
- rare2: rare2,
- rare2i: rare2i,
- }
- }
-
- fn empty() -> FreqyPacked {
- FreqyPacked {
- pat: vec![],
- char_len: 0,
- rare1: 0,
- rare1i: 0,
- rare2: 0,
- rare2i: 0,
+impl Memmem {
+ fn new(pat: &[u8]) -> Memmem {
+ Memmem {
+ finder: memmem::Finder::new(pat).into_owned(),
+ char_len: char_len_lossy(pat),
}
}
#[cfg_attr(feature = "perf-inline", inline(always))]
pub fn find(&self, haystack: &[u8]) -> Option<usize> {
- let pat = &*self.pat;
- if haystack.len() < pat.len() || pat.is_empty() {
- return None;
- }
- let mut i = self.rare1i;
- while i < haystack.len() {
- i += match memchr(self.rare1, &haystack[i..]) {
- None => return None,
- Some(i) => i,
- };
- let start = i - self.rare1i;
- let end = start + pat.len();
- if end > haystack.len() {
- return None;
- }
- let aligned = &haystack[start..end];
- if aligned[self.rare2i] == self.rare2 && aligned == &*self.pat {
- return Some(start);
- }
- i += 1;
- }
- None
+ self.finder.find(haystack)
}
#[cfg_attr(feature = "perf-inline", inline(always))]
@@ -484,11 +381,11 @@
if text.len() < self.len() {
return false;
}
- text[text.len() - self.len()..] == *self.pat
+ &text[text.len() - self.len()..] == self.finder.needle()
}
pub fn len(&self) -> usize {
- self.pat.len()
+ self.finder.needle().len()
}
pub fn char_len(&self) -> usize {
@@ -496,627 +393,10 @@
}
fn approximate_size(&self) -> usize {
- self.pat.len() * mem::size_of::<u8>()
+ self.finder.needle().len() * mem::size_of::<u8>()
}
}
fn char_len_lossy(bytes: &[u8]) -> usize {
String::from_utf8_lossy(bytes).chars().count()
}
-
-/// An implementation of Tuned Boyer-Moore as laid out by
-/// Andrew Hume and Daniel Sunday in "Fast String Searching".
-/// O(n) in the size of the input.
-///
-/// Fast string searching algorithms come in many variations,
-/// but they can generally be described in terms of three main
-/// components.
-///
-/// The skip loop is where the string searcher wants to spend
-/// as much time as possible. Exactly which character in the
-/// pattern the skip loop examines varies from algorithm to
-/// algorithm, but in the simplest case this loop repeated
-/// looks at the last character in the pattern and jumps
-/// forward in the input if it is not in the pattern.
-/// Robert Boyer and J Moore called this the "fast" loop in
-/// their original paper.
-///
-/// The match loop is responsible for actually examining the
-/// whole potentially matching substring. In order to fail
-/// faster, the match loop sometimes has a guard test attached.
-/// The guard test uses frequency analysis of the different
-/// characters in the pattern to choose the least frequency
-/// occurring character and use it to find match failures
-/// as quickly as possible.
-///
-/// The shift rule governs how the algorithm will shuffle its
-/// test window in the event of a failure during the match loop.
-/// Certain shift rules allow the worst-case run time of the
-/// algorithm to be shown to be O(n) in the size of the input
-/// rather than O(nm) in the size of the input and the size
-/// of the pattern (as naive Boyer-Moore is).
-///
-/// "Fast String Searching", in addition to presenting a tuned
-/// algorithm, provides a comprehensive taxonomy of the many
-/// different flavors of string searchers. Under that taxonomy
-/// TBM, the algorithm implemented here, uses an unrolled fast
-/// skip loop with memchr fallback, a forward match loop with guard,
-/// and the mini Sunday's delta shift rule. To unpack that you'll have to
-/// read the paper.
-#[derive(Clone, Debug)]
-pub struct BoyerMooreSearch {
- /// The pattern we are going to look for in the haystack.
- pattern: Vec<u8>,
-
- /// The skip table for the skip loop.
- ///
- /// Maps the character at the end of the input
- /// to a shift.
- skip_table: Vec<usize>,
-
- /// The guard character (least frequently occurring char).
- guard: u8,
- /// The reverse-index of the guard character in the pattern.
- guard_reverse_idx: usize,
-
- /// Daniel Sunday's mini generalized delta2 shift table.
- ///
- /// We use a skip loop, so we only have to provide a shift
- /// for the skip char (last char). This is why it is a mini
- /// shift rule.
- md2_shift: usize,
-}
-
-impl BoyerMooreSearch {
- /// Create a new string searcher, performing whatever
- /// compilation steps are required.
- fn new(pattern: Vec<u8>) -> Self {
- debug_assert!(!pattern.is_empty());
-
- let (g, gi) = Self::select_guard(pattern.as_slice());
- let skip_table = Self::compile_skip_table(pattern.as_slice());
- let md2_shift = Self::compile_md2_shift(pattern.as_slice());
- BoyerMooreSearch {
- pattern: pattern,
- skip_table: skip_table,
- guard: g,
- guard_reverse_idx: gi,
- md2_shift: md2_shift,
- }
- }
-
- /// Find the pattern in `haystack`, returning the offset
- /// of the start of the first occurrence of the pattern
- /// in `haystack`.
- #[inline]
- fn find(&self, haystack: &[u8]) -> Option<usize> {
- if haystack.len() < self.pattern.len() {
- return None;
- }
-
- let mut window_end = self.pattern.len() - 1;
-
- // Inspired by the grep source. It is a way
- // to do correct loop unrolling without having to place
- // a crashpad of terminating charicters at the end in
- // the way described in the Fast String Searching paper.
- const NUM_UNROLL: usize = 10;
- // 1 for the initial position, and 1 for the md2 shift
- let short_circut = (NUM_UNROLL + 2) * self.pattern.len();
-
- if haystack.len() > short_circut {
- // just 1 for the md2 shift
- let backstop =
- haystack.len() - ((NUM_UNROLL + 1) * self.pattern.len());
- loop {
- window_end =
- match self.skip_loop(haystack, window_end, backstop) {
- Some(i) => i,
- None => return None,
- };
- if window_end >= backstop {
- break;
- }
-
- if self.check_match(haystack, window_end) {
- return Some(window_end - (self.pattern.len() - 1));
- } else {
- let skip = self.skip_table[haystack[window_end] as usize];
- window_end +=
- if skip == 0 { self.md2_shift } else { skip };
- continue;
- }
- }
- }
-
- // now process the input after the backstop
- while window_end < haystack.len() {
- let mut skip = self.skip_table[haystack[window_end] as usize];
- if skip == 0 {
- if self.check_match(haystack, window_end) {
- return Some(window_end - (self.pattern.len() - 1));
- } else {
- skip = self.md2_shift;
- }
- }
- window_end += skip;
- }
-
- None
- }
-
- fn len(&self) -> usize {
- return self.pattern.len();
- }
-
- /// The key heuristic behind which the BoyerMooreSearch lives.
- ///
- /// See `rust-lang/regex/issues/408`.
- ///
- /// Tuned Boyer-Moore is actually pretty slow! It turns out a handrolled
- /// platform-specific memchr routine with a bit of frequency
- /// analysis sprinkled on top actually wins most of the time.
- /// However, there are a few cases where Tuned Boyer-Moore still
- /// wins.
- ///
- /// If the haystack is random, frequency analysis doesn't help us,
- /// so Boyer-Moore will win for sufficiently large needles.
- /// Unfortunately, there is no obvious way to determine this
- /// ahead of time.
- ///
- /// If the pattern itself consists of very common characters,
- /// frequency analysis won't get us anywhere. The most extreme
- /// example of this is a pattern like `eeeeeeeeeeeeeeee`. Fortunately,
- /// this case is wholly determined by the pattern, so we can actually
- /// implement the heuristic.
- ///
- /// A third case is if the pattern is sufficiently long. The idea
- /// here is that once the pattern gets long enough the Tuned
- /// Boyer-Moore skip loop will start making strides long enough
- /// to beat the asm deep magic that is memchr.
- fn should_use(pattern: &[u8]) -> bool {
- // The minimum pattern length required to use TBM.
- const MIN_LEN: usize = 9;
- // The minimum frequency rank (lower is rarer) that every byte in the
- // pattern must have in order to use TBM. That is, if the pattern
- // contains _any_ byte with a lower rank, then TBM won't be used.
- const MIN_CUTOFF: usize = 150;
- // The maximum frequency rank for any byte.
- const MAX_CUTOFF: usize = 255;
- // The scaling factor used to determine the actual cutoff frequency
- // to use (keeping in mind that the minimum frequency rank is bounded
- // by MIN_CUTOFF). This scaling factor is an attempt to make TBM more
- // likely to be used as the pattern grows longer. That is, longer
- // patterns permit somewhat less frequent bytes than shorter patterns,
- // under the assumption that TBM gets better as the pattern gets
- // longer.
- const LEN_CUTOFF_PROPORTION: usize = 4;
-
- let scaled_rank = pattern.len().wrapping_mul(LEN_CUTOFF_PROPORTION);
- let cutoff = cmp::max(
- MIN_CUTOFF,
- MAX_CUTOFF - cmp::min(MAX_CUTOFF, scaled_rank),
- );
- // The pattern must be long enough to be worthwhile. e.g., memchr will
- // be faster on `e` because it is short even though e is quite common.
- pattern.len() > MIN_LEN
- // all the bytes must be more common than the cutoff.
- && pattern.iter().all(|c| freq_rank(*c) >= cutoff)
- }
-
- /// Check to see if there is a match at the given position
- #[inline]
- fn check_match(&self, haystack: &[u8], window_end: usize) -> bool {
- // guard test
- if haystack[window_end - self.guard_reverse_idx] != self.guard {
- return false;
- }
-
- // match loop
- let window_start = window_end - (self.pattern.len() - 1);
- for i in 0..self.pattern.len() {
- if self.pattern[i] != haystack[window_start + i] {
- return false;
- }
- }
-
- true
- }
-
- /// Skip forward according to the shift table.
- ///
- /// Returns the offset of the next occurrence
- /// of the last char in the pattern, or the none
- /// if it never reappears. If `skip_loop` hits the backstop
- /// it will leave early.
- #[inline]
- fn skip_loop(
- &self,
- haystack: &[u8],
- mut window_end: usize,
- backstop: usize,
- ) -> Option<usize> {
- let window_end_snapshot = window_end;
- let skip_of = |we: usize| -> usize {
- // Unsafe might make this faster, but the benchmarks
- // were hard to interpret.
- self.skip_table[haystack[we] as usize]
- };
-
- loop {
- let mut skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
- if skip != 0 {
- skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
- if skip != 0 {
- skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
- if skip != 0 {
- skip = skip_of(window_end);
- window_end += skip;
- skip = skip_of(window_end);
- window_end += skip;
-
- // If ten iterations did not make at least 16 words
- // worth of progress, we just fall back on memchr.
- if window_end - window_end_snapshot
- > 16 * mem::size_of::<usize>()
- {
- // Returning a window_end >= backstop will
- // immediatly break us out of the inner loop in
- // `find`.
- if window_end >= backstop {
- return Some(window_end);
- }
-
- continue; // we made enough progress
- } else {
- // In case we are already there, and so that
- // we will catch the guard char.
- window_end = window_end
- .checked_sub(1 + self.guard_reverse_idx)
- .unwrap_or(0);
-
- match memchr(self.guard, &haystack[window_end..]) {
- None => return None,
- Some(g_idx) => {
- return Some(
- window_end
- + g_idx
- + self.guard_reverse_idx,
- );
- }
- }
- }
- }
- }
- }
-
- return Some(window_end);
- }
- }
-
- /// Compute the ufast skip table.
- fn compile_skip_table(pattern: &[u8]) -> Vec<usize> {
- let mut tab = vec![pattern.len(); 256];
-
- // For every char in the pattern, we write a skip
- // that will line us up with the rightmost occurrence.
- //
- // N.B. the sentinel (0) is written by the last
- // loop iteration.
- for (i, c) in pattern.iter().enumerate() {
- tab[*c as usize] = (pattern.len() - 1) - i;
- }
-
- tab
- }
-
- /// Select the guard character based off of the precomputed
- /// frequency table.
- fn select_guard(pattern: &[u8]) -> (u8, usize) {
- let mut rarest = pattern[0];
- let mut rarest_rev_idx = pattern.len() - 1;
- for (i, c) in pattern.iter().enumerate() {
- if freq_rank(*c) < freq_rank(rarest) {
- rarest = *c;
- rarest_rev_idx = (pattern.len() - 1) - i;
- }
- }
-
- (rarest, rarest_rev_idx)
- }
-
- /// If there is another occurrence of the skip
- /// char, shift to it, otherwise just shift to
- /// the next window.
- fn compile_md2_shift(pattern: &[u8]) -> usize {
- let shiftc = *pattern.last().unwrap();
-
- // For a pattern of length 1 we will never apply the
- // shift rule, so we use a poison value on the principle
- // that failing fast is a good thing.
- if pattern.len() == 1 {
- return 0xDEADBEAF;
- }
-
- let mut i = pattern.len() - 2;
- while i > 0 {
- if pattern[i] == shiftc {
- return (pattern.len() - 1) - i;
- }
- i -= 1;
- }
-
- // The skip char never re-occurs in the pattern, so
- // we can just shift the whole window length.
- pattern.len() - 1
- }
-
- fn approximate_size(&self) -> usize {
- (self.pattern.len() * mem::size_of::<u8>())
- + (256 * mem::size_of::<usize>()) // skip table
- }
-}
-
-fn freq_rank(b: u8) -> usize {
- BYTE_FREQUENCIES[b as usize] as usize
-}
-
-#[cfg(test)]
-mod tests {
- use super::{BoyerMooreSearch, FreqyPacked};
-
- //
- // Unit Tests
- //
-
- // The "hello, world" of string searching
- #[test]
- fn bm_find_subs() {
- let searcher = BoyerMooreSearch::new(Vec::from(&b"pattern"[..]));
- let haystack = b"I keep seeing patterns in this text";
- assert_eq!(14, searcher.find(haystack).unwrap());
- }
-
- #[test]
- fn bm_find_no_subs() {
- let searcher = BoyerMooreSearch::new(Vec::from(&b"pattern"[..]));
- let haystack = b"I keep seeing needles in this text";
- assert_eq!(None, searcher.find(haystack));
- }
-
- //
- // Regression Tests
- //
-
- #[test]
- fn bm_skip_reset_bug() {
- let haystack = vec![0, 0, 0, 0, 0, 1, 1, 0];
- let needle = vec![0, 1, 1, 0];
-
- let searcher = BoyerMooreSearch::new(needle);
- let offset = searcher.find(haystack.as_slice()).unwrap();
- assert_eq!(4, offset);
- }
-
- #[test]
- fn bm_backstop_underflow_bug() {
- let haystack = vec![0, 0];
- let needle = vec![0, 0];
-
- let searcher = BoyerMooreSearch::new(needle);
- let offset = searcher.find(haystack.as_slice()).unwrap();
- assert_eq!(0, offset);
- }
-
- #[test]
- fn bm_naive_off_by_one_bug() {
- let haystack = vec![91];
- let needle = vec![91];
-
- let naive_offset = naive_find(&needle, &haystack).unwrap();
- assert_eq!(0, naive_offset);
- }
-
- #[test]
- fn bm_memchr_fallback_indexing_bug() {
- let mut haystack = vec![
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 87, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- ];
- let needle = vec![1, 1, 1, 1, 32, 32, 87];
- let needle_start = haystack.len();
- haystack.extend(needle.clone());
-
- let searcher = BoyerMooreSearch::new(needle);
- assert_eq!(needle_start, searcher.find(haystack.as_slice()).unwrap());
- }
-
- #[test]
- fn bm_backstop_boundary() {
- let haystack = b"\
-// aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
-e_data.clone_created(entity_id, entity_to_add.entity_id);
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
-"
- .to_vec();
- let needle = b"clone_created".to_vec();
-
- let searcher = BoyerMooreSearch::new(needle);
- let result = searcher.find(&haystack);
- assert_eq!(Some(43), result);
- }
-
- #[test]
- fn bm_win_gnu_indexing_bug() {
- let haystack_raw = vec![
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- ];
- let needle = vec![1, 1, 1, 1, 1, 1, 1];
- let haystack = haystack_raw.as_slice();
-
- BoyerMooreSearch::new(needle.clone()).find(haystack);
- }
-
- //
- // QuickCheck Properties
- //
-
- use quickcheck::TestResult;
-
- fn naive_find(needle: &[u8], haystack: &[u8]) -> Option<usize> {
- assert!(needle.len() <= haystack.len());
-
- for i in 0..(haystack.len() - (needle.len() - 1)) {
- if haystack[i] == needle[0]
- && &haystack[i..(i + needle.len())] == needle
- {
- return Some(i);
- }
- }
-
- None
- }
-
- quickcheck! {
- fn qc_bm_equals_nieve_find(pile1: Vec<u8>, pile2: Vec<u8>) -> TestResult {
- if pile1.len() == 0 || pile2.len() == 0 {
- return TestResult::discard();
- }
-
- let (needle, haystack) = if pile1.len() < pile2.len() {
- (pile1, pile2.as_slice())
- } else {
- (pile2, pile1.as_slice())
- };
-
- let searcher = BoyerMooreSearch::new(needle.clone());
- TestResult::from_bool(
- searcher.find(haystack) == naive_find(&needle, haystack))
- }
-
- fn qc_bm_equals_single(pile1: Vec<u8>, pile2: Vec<u8>) -> TestResult {
- if pile1.len() == 0 || pile2.len() == 0 {
- return TestResult::discard();
- }
-
- let (needle, haystack) = if pile1.len() < pile2.len() {
- (pile1, pile2.as_slice())
- } else {
- (pile2, pile1.as_slice())
- };
-
- let bm_searcher = BoyerMooreSearch::new(needle.clone());
- let freqy_memchr = FreqyPacked::new(needle);
- TestResult::from_bool(
- bm_searcher.find(haystack) == freqy_memchr.find(haystack))
- }
-
- fn qc_bm_finds_trailing_needle(
- haystack_pre: Vec<u8>,
- needle: Vec<u8>
- ) -> TestResult {
- if needle.len() == 0 {
- return TestResult::discard();
- }
-
- let mut haystack = haystack_pre.clone();
- let searcher = BoyerMooreSearch::new(needle.clone());
-
- if haystack.len() >= needle.len() &&
- searcher.find(haystack.as_slice()).is_some() {
- return TestResult::discard();
- }
-
- haystack.extend(needle.clone());
-
- // What if the the tail of the haystack can start the
- // needle?
- let start = haystack_pre.len()
- .checked_sub(needle.len())
- .unwrap_or(0);
- for i in 0..(needle.len() - 1) {
- if searcher.find(&haystack[(i + start)..]).is_some() {
- return TestResult::discard();
- }
- }
-
- TestResult::from_bool(
- searcher.find(haystack.as_slice())
- .map(|x| x == haystack_pre.len())
- .unwrap_or(false))
- }
-
- // qc_equals_* is only testing the negative case as @burntsushi
- // pointed out in https://github.com/rust-lang/regex/issues/446.
- // This quickcheck prop represents an effort to force testing of
- // the positive case. qc_bm_finds_first and qc_bm_finds_trailing_needle
- // already check some of the positive cases, but they don't cover
- // cases where the needle is in the middle of haystack. This prop
- // fills that hole.
- fn qc_bm_finds_subslice(
- haystack: Vec<u8>,
- needle_start: usize,
- needle_length: usize
- ) -> TestResult {
- if haystack.len() == 0 {
- return TestResult::discard();
- }
-
- let needle_start = needle_start % haystack.len();
- let needle_length = needle_length % (haystack.len() - needle_start);
-
- if needle_length == 0 {
- return TestResult::discard();
- }
-
- let needle = &haystack[needle_start..(needle_start + needle_length)];
-
- let bm_searcher = BoyerMooreSearch::new(needle.to_vec());
-
- let start = naive_find(&needle, &haystack);
- match start {
- None => TestResult::from_bool(false),
- Some(nf_start) =>
- TestResult::from_bool(
- nf_start <= needle_start
- && bm_searcher.find(&haystack) == start
- )
- }
- }
-
- fn qc_bm_finds_first(needle: Vec<u8>) -> TestResult {
- if needle.len() == 0 {
- return TestResult::discard();
- }
-
- let mut haystack = needle.clone();
- let searcher = BoyerMooreSearch::new(needle.clone());
- haystack.extend(needle);
-
- TestResult::from_bool(
- searcher.find(haystack.as_slice())
- .map(|x| x == 0)
- .unwrap_or(false))
- }
- }
-}
diff --git a/src/literal/mod.rs b/src/literal/mod.rs
index 783c63b..980f523 100644
--- a/src/literal/mod.rs
+++ b/src/literal/mod.rs
@@ -6,7 +6,7 @@
#[allow(missing_docs)]
#[cfg(not(feature = "perf-literal"))]
mod imp {
- use syntax::hir::literal::Literals;
+ use regex_syntax::hir::literal::Literals;
#[derive(Clone, Debug)]
pub struct LiteralSearcher(());
diff --git a/src/pattern.rs b/src/pattern.rs
index e942667..b4ffd8e 100644
--- a/src/pattern.rs
+++ b/src/pattern.rs
@@ -1,7 +1,8 @@
use std::str::pattern::{Pattern, SearchStep, Searcher};
-use re_unicode::{Matches, Regex};
+use crate::re_unicode::{Matches, Regex};
+#[derive(Debug)]
pub struct RegexSearcher<'r, 't> {
haystack: &'t str,
it: Matches<'r, 't>,
diff --git a/src/pikevm.rs b/src/pikevm.rs
index 299087d..9a14240 100644
--- a/src/pikevm.rs
+++ b/src/pikevm.rs
@@ -17,11 +17,11 @@
use std::mem;
-use exec::ProgramCache;
-use input::{Input, InputAt};
-use prog::{InstPtr, Program};
-use re_trait::Slot;
-use sparse::SparseSet;
+use crate::exec::ProgramCache;
+use crate::input::{Input, InputAt};
+use crate::prog::{InstPtr, Program};
+use crate::re_trait::Slot;
+use crate::sparse::SparseSet;
/// An NFA simulation matching engine.
#[derive(Debug)]
@@ -231,7 +231,7 @@
at: InputAt,
at_next: InputAt,
) -> bool {
- use prog::Inst::*;
+ use crate::prog::Inst::*;
match self.prog[ip] {
Match(match_slot) => {
if match_slot < matches.len() {
@@ -300,7 +300,7 @@
// traverse the set of states. We only push to the stack when we
// absolutely need recursion (restoring captures or following a
// branch).
- use prog::Inst::*;
+ use crate::prog::Inst::*;
loop {
// Don't visit states we've already added.
if nlist.set.contains(ip) {
diff --git a/src/pool.rs b/src/pool.rs
index a506ee9..6a6f15b 100644
--- a/src/pool.rs
+++ b/src/pool.rs
@@ -154,7 +154,7 @@
unsafe impl<T: Send> Sync for Pool<T> {}
impl<T: ::std::fmt::Debug> ::std::fmt::Debug for Pool<T> {
- fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+ fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
f.debug_struct("Pool")
.field("stack", &self.stack)
.field("owner", &self.owner)
@@ -168,7 +168,7 @@
/// The purpose of the guard is to use RAII to automatically put the value back
/// in the pool once it's dropped.
#[derive(Debug)]
-pub struct PoolGuard<'a, T: 'a + Send> {
+pub struct PoolGuard<'a, T: Send> {
/// The pool that this guard is attached to.
pool: &'a Pool<T>,
/// This is None when the guard represents the special "owned" value. In
@@ -193,7 +193,7 @@
/// the value to go back into the pool) and then calling get again is NOT
/// guaranteed to return the same value received in the first get call.
#[cfg_attr(feature = "perf-inline", inline(always))]
- pub fn get(&self) -> PoolGuard<T> {
+ pub fn get(&self) -> PoolGuard<'_, T> {
// Our fast path checks if the caller is the thread that "owns" this
// pool. Or stated differently, whether it is the first thread that
// tried to extract a value from the pool. If it is, then we can return
@@ -217,7 +217,7 @@
///
/// If the pool has no owner, then this will set the owner.
#[cold]
- fn get_slow(&self, caller: usize, owner: usize) -> PoolGuard<T> {
+ fn get_slow(&self, caller: usize, owner: usize) -> PoolGuard<'_, T> {
use std::sync::atomic::Ordering::Relaxed;
if owner == 0 {
@@ -284,7 +284,7 @@
#[test]
fn oibits() {
- use exec::ProgramCache;
+ use crate::exec::ProgramCache;
fn has_oibits<T: Send + Sync + UnwindSafe + RefUnwindSafe>() {}
has_oibits::<Pool<ProgramCache>>();
diff --git a/src/prog.rs b/src/prog.rs
index 74e5f2f..475a811 100644
--- a/src/prog.rs
+++ b/src/prog.rs
@@ -6,8 +6,8 @@
use std::slice;
use std::sync::Arc;
-use input::Char;
-use literal::LiteralSearcher;
+use crate::input::Char;
+use crate::literal::LiteralSearcher;
/// `InstPtr` represents the index of an instruction in a regex program.
pub type InstPtr = usize;
@@ -168,7 +168,7 @@
}
impl fmt::Debug for Program {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
use self::Inst::*;
fn with_goto(cur: usize, goto: usize, fmtd: String) -> String {
@@ -259,8 +259,8 @@
///
/// Other than the benefit of moving invariants into the type system, another
/// benefit is the decreased size. If we remove the `Char` and `Ranges`
-/// instructions from the `Inst` enum, then its size shrinks from 40 bytes to
-/// 24 bytes. (This is because of the removal of a `Vec` in the `Ranges`
+/// instructions from the `Inst` enum, then its size shrinks from 32 bytes to
+/// 24 bytes. (This is because of the removal of a `Box<[]>` in the `Ranges`
/// variant.) Given that byte based machines are typically much bigger than
/// their Unicode analogues (because they can decode UTF-8 directly), this ends
/// up being a pretty significant savings.
@@ -374,7 +374,7 @@
/// succeeds.
pub goto: InstPtr,
/// The set of Unicode scalar value ranges to test.
- pub ranges: Vec<(char, char)>,
+ pub ranges: Box<[(char, char)]>,
}
impl InstRanges {
@@ -432,3 +432,16 @@
self.start <= byte && byte <= self.end
}
}
+
+#[cfg(test)]
+mod test {
+ #[test]
+ #[cfg(target_pointer_width = "64")]
+ fn test_size_of_inst() {
+ use std::mem::size_of;
+
+ use super::Inst;
+
+ assert_eq!(32, size_of::<Inst>());
+ }
+}
diff --git a/src/re_builder.rs b/src/re_builder.rs
index fc140f8..ee63836 100644
--- a/src/re_builder.rs
+++ b/src/re_builder.rs
@@ -37,10 +37,10 @@
($name:ident, $regex_mod:ident, $only_utf8:expr) => {
pub mod $name {
use super::RegexOptions;
- use error::Error;
- use exec::ExecBuilder;
+ use crate::error::Error;
+ use crate::exec::ExecBuilder;
- use $regex_mod::Regex;
+ use crate::$regex_mod::Regex;
/// A configurable builder for a regular expression.
///
@@ -235,10 +235,10 @@
($name:ident, $regex_mod:ident, $only_utf8:expr) => {
pub mod $name {
use super::RegexOptions;
- use error::Error;
- use exec::ExecBuilder;
+ use crate::error::Error;
+ use crate::exec::ExecBuilder;
- use re_set::$regex_mod::RegexSet;
+ use crate::re_set::$regex_mod::RegexSet;
/// A configurable builder for a set of regular expressions.
///
diff --git a/src/re_bytes.rs b/src/re_bytes.rs
index 204a70a..ae55d6d 100644
--- a/src/re_bytes.rs
+++ b/src/re_bytes.rs
@@ -6,13 +6,13 @@
use std::str::FromStr;
use std::sync::Arc;
-use find_byte::find_byte;
+use crate::find_byte::find_byte;
-use error::Error;
-use exec::{Exec, ExecNoSync};
-use expand::expand_bytes;
-use re_builder::bytes::RegexBuilder;
-use re_trait::{self, RegularExpression, SubCapturesPosIter};
+use crate::error::Error;
+use crate::exec::{Exec, ExecNoSync};
+use crate::expand::expand_bytes;
+use crate::re_builder::bytes::RegexBuilder;
+use crate::re_trait::{self, RegularExpression, SubCapturesPosIter};
/// Match represents a single match of a regex in a haystack.
///
@@ -79,14 +79,14 @@
impl fmt::Display for Regex {
/// Shows the original regular expression.
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.as_str())
}
}
impl fmt::Debug for Regex {
/// Shows the original regular expression.
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Display::fmt(self, f)
}
}
@@ -133,7 +133,7 @@
/// bytes:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let text = b"I categorically deny having triskaidekaphobia.";
/// assert!(Regex::new(r"\b\w{13}\b").unwrap().is_match(text));
@@ -156,7 +156,7 @@
/// ASCII word bytes:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let text = b"I categorically deny having triskaidekaphobia.";
/// let mat = Regex::new(r"\b\w{13}\b").unwrap().find(text).unwrap();
@@ -177,7 +177,7 @@
/// word bytes:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let text = b"Retroactively relinquishing remunerations is reprehensible.";
/// for mat in Regex::new(r"\b\w{13}\b").unwrap().find_iter(text) {
@@ -205,7 +205,7 @@
/// year separately.
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"'([^']+)'\s+\((\d{4})\)").unwrap();
/// let text = b"Not my favorite movie: 'Citizen Kane' (1941).";
@@ -227,7 +227,7 @@
/// We can make this example a bit clearer by using *named* capture groups:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)")
/// .unwrap();
@@ -271,7 +271,7 @@
/// some text, where the movie is formatted like "'Title' (xxxx)":
///
/// ```rust
- /// # extern crate regex; use std::str; use regex::bytes::Regex;
+ /// # use std::str; use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)")
/// .unwrap();
@@ -305,7 +305,7 @@
/// To split a string delimited by arbitrary amounts of spaces or tabs:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"[ \t]+").unwrap();
/// let fields: Vec<&[u8]> = re.split(b"a b \t c\td e").collect();
@@ -331,7 +331,7 @@
/// Get the first two words in some text:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"\W+").unwrap();
/// let fields: Vec<&[u8]> = re.splitn(b"Hey! How are you?", 3).collect();
@@ -379,7 +379,7 @@
/// In typical usage, this can just be a normal byte string:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new("[^01]+").unwrap();
/// assert_eq!(re.replace(b"1078910", &b""[..]), &b"1010"[..]);
@@ -392,7 +392,7 @@
/// group matches easily:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # use regex::bytes::Captures; fn main() {
/// let re = Regex::new(r"([^,\s]+),\s+(\S+)").unwrap();
/// let result = re.replace(b"Springsteen, Bruce", |caps: &Captures| {
@@ -411,7 +411,7 @@
/// with named capture groups:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"(?P<last>[^,\s]+),\s+(?P<first>\S+)").unwrap();
/// let result = re.replace(b"Springsteen, Bruce", &b"$first $last"[..]);
@@ -428,7 +428,7 @@
/// underscore:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let re = Regex::new(r"(?P<first>\w+)\s+(?P<second>\w+)").unwrap();
/// let result = re.replace(b"deep fried", &b"${first}_$second"[..]);
@@ -445,7 +445,7 @@
/// byte string with `NoExpand`:
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// use regex::bytes::NoExpand;
///
@@ -546,7 +546,7 @@
/// `a`.
///
/// ```rust
- /// # extern crate regex; use regex::bytes::Regex;
+ /// # use regex::bytes::Regex;
/// # fn main() {
/// let text = b"aaaaa";
/// let pos = Regex::new(r"a+").unwrap().shortest_match(text);
@@ -658,7 +658,7 @@
}
/// Returns an iterator over the capture names.
- pub fn capture_names(&self) -> CaptureNames {
+ pub fn capture_names(&self) -> CaptureNames<'_> {
CaptureNames(self.0.capture_names().iter())
}
@@ -990,15 +990,15 @@
}
impl<'t> fmt::Debug for Captures<'t> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Captures").field(&CapturesDebug(self)).finish()
}
}
-struct CapturesDebug<'c, 't: 'c>(&'c Captures<'t>);
+struct CapturesDebug<'c, 't>(&'c Captures<'t>);
impl<'c, 't> fmt::Debug for CapturesDebug<'c, 't> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fn escape_bytes(bytes: &[u8]) -> String {
let mut s = String::new();
for &b in bytes {
@@ -1084,7 +1084,7 @@
/// The lifetime `'c` corresponds to the lifetime of the `Captures` value, and
/// the lifetime `'t` corresponds to the originally matched text.
#[derive(Clone, Debug)]
-pub struct SubCaptureMatches<'c, 't: 'c> {
+pub struct SubCaptureMatches<'c, 't> {
caps: &'c Captures<'t>,
it: SubCapturesPosIter<'c>,
}
@@ -1116,7 +1116,7 @@
///
/// For example, a no-op replacement would be
/// `dst.extend(&caps[0])`.
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>);
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>);
/// Return a fixed unchanging replacement byte string.
///
@@ -1159,10 +1159,10 @@
///
/// Returned by [`Replacer::by_ref`](trait.Replacer.html#method.by_ref).
#[derive(Debug)]
-pub struct ReplacerRef<'a, R: ?Sized + 'a>(&'a mut R);
+pub struct ReplacerRef<'a, R: ?Sized>(&'a mut R);
impl<'a, R: Replacer + ?Sized + 'a> Replacer for ReplacerRef<'a, R> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
self.0.replace_append(caps, dst)
}
fn no_expansion<'r>(&'r mut self) -> Option<Cow<'r, [u8]>> {
@@ -1171,56 +1171,56 @@
}
impl<'a> Replacer for &'a [u8] {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
caps.expand(*self, dst);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
no_expansion(self)
}
}
impl<'a> Replacer for &'a Vec<u8> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
caps.expand(*self, dst);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
no_expansion(self)
}
}
impl Replacer for Vec<u8> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
caps.expand(self, dst);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
no_expansion(self)
}
}
impl<'a> Replacer for Cow<'a, [u8]> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
caps.expand(self.as_ref(), dst);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
no_expansion(self)
}
}
impl<'a> Replacer for &'a Cow<'a, [u8]> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
caps.expand(self.as_ref(), dst);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
no_expansion(self)
}
}
-fn no_expansion<T: AsRef<[u8]>>(t: &T) -> Option<Cow<[u8]>> {
+fn no_expansion<T: AsRef<[u8]>>(t: &T) -> Option<Cow<'_, [u8]>> {
let s = t.as_ref();
match find_byte(b'$', s) {
Some(_) => None,
@@ -1230,10 +1230,10 @@
impl<F, T> Replacer for F
where
- F: FnMut(&Captures) -> T,
+ F: FnMut(&Captures<'_>) -> T,
T: AsRef<[u8]>,
{
- fn replace_append(&mut self, caps: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut Vec<u8>) {
dst.extend_from_slice((*self)(caps).as_ref());
}
}
@@ -1250,11 +1250,11 @@
pub struct NoExpand<'t>(pub &'t [u8]);
impl<'t> Replacer for NoExpand<'t> {
- fn replace_append(&mut self, _: &Captures, dst: &mut Vec<u8>) {
+ fn replace_append(&mut self, _: &Captures<'_>, dst: &mut Vec<u8>) {
dst.extend_from_slice(self.0);
}
- fn no_expansion(&mut self) -> Option<Cow<[u8]>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, [u8]>> {
Some(Cow::Borrowed(self.0))
}
}
diff --git a/src/re_set.rs b/src/re_set.rs
index 5cb47ad..73d5953 100644
--- a/src/re_set.rs
+++ b/src/re_set.rs
@@ -7,10 +7,10 @@
use std::slice;
use std::vec;
- use error::Error;
- use exec::Exec;
- use re_builder::$builder_mod::RegexSetBuilder;
- use re_trait::RegularExpression;
+ use crate::error::Error;
+ use crate::exec::Exec;
+ use crate::re_builder::$builder_mod::RegexSetBuilder;
+ use crate::re_trait::RegularExpression;
/// Match multiple (possibly overlapping) regular expressions in a single scan.
///
@@ -292,7 +292,7 @@
/// This will always produces matches in ascending order of index, where
/// the index corresponds to the index of the regex that matched with
/// respect to its position when initially building the set.
- pub fn iter(&self) -> SetMatchesIter {
+ pub fn iter(&self) -> SetMatchesIter<'_> {
SetMatchesIter((&*self.matches).into_iter().enumerate())
}
}
@@ -405,7 +405,7 @@
}
impl fmt::Debug for RegexSet {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "RegexSet({:?})", self.0.regex_strings())
}
}
diff --git a/src/re_trait.rs b/src/re_trait.rs
index ea6be9c..680aa54 100644
--- a/src/re_trait.rs
+++ b/src/re_trait.rs
@@ -30,7 +30,7 @@
/// Creates an iterator of all the capture group positions in order of
/// appearance in the regular expression. Positions are byte indices
/// in terms of the original string matched.
- pub fn iter(&self) -> SubCapturesPosIter {
+ pub fn iter(&self) -> SubCapturesPosIter<'_> {
SubCapturesPosIter { idx: 0, locs: self }
}
@@ -138,13 +138,13 @@
/// Returns an iterator over all non-overlapping successive leftmost-first
/// matches.
- fn find_iter(self, text: &Self::Text) -> Matches<Self> {
+ fn find_iter(self, text: &Self::Text) -> Matches<'_, Self> {
Matches { re: self, text: text, last_end: 0, last_match: None }
}
/// Returns an iterator over all non-overlapping successive leftmost-first
/// matches with captures.
- fn captures_iter(self, text: &Self::Text) -> CaptureMatches<Self> {
+ fn captures_iter(self, text: &Self::Text) -> CaptureMatches<'_, Self> {
CaptureMatches(self.find_iter(text))
}
}
diff --git a/src/re_unicode.rs b/src/re_unicode.rs
index 1b478cd..142c78f 100644
--- a/src/re_unicode.rs
+++ b/src/re_unicode.rs
@@ -6,21 +6,20 @@
use std::str::FromStr;
use std::sync::Arc;
-use find_byte::find_byte;
-use syntax;
+use crate::find_byte::find_byte;
-use error::Error;
-use exec::{Exec, ExecNoSyncStr};
-use expand::expand_str;
-use re_builder::unicode::RegexBuilder;
-use re_trait::{self, RegularExpression, SubCapturesPosIter};
+use crate::error::Error;
+use crate::exec::{Exec, ExecNoSyncStr};
+use crate::expand::expand_str;
+use crate::re_builder::unicode::RegexBuilder;
+use crate::re_trait::{self, RegularExpression, SubCapturesPosIter};
/// Escapes all regular expression meta characters in `text`.
///
/// The string returned may be safely used as a literal in a regular
/// expression.
pub fn escape(text: &str) -> String {
- syntax::escape(text)
+ regex_syntax::escape(text)
}
/// Match represents a single match of a regex in a haystack.
@@ -138,14 +137,14 @@
impl fmt::Display for Regex {
/// Shows the original regular expression.
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.as_str())
}
}
impl fmt::Debug for Regex {
/// Shows the original regular expression.
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Display::fmt(self, f)
}
}
@@ -189,7 +188,7 @@
/// Unicode word characters:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let text = "I categorically deny having triskaidekaphobia.";
/// assert!(Regex::new(r"\b\w{13}\b").unwrap().is_match(text));
@@ -212,7 +211,7 @@
/// Unicode word characters:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let text = "I categorically deny having triskaidekaphobia.";
/// let mat = Regex::new(r"\b\w{13}\b").unwrap().find(text).unwrap();
@@ -234,7 +233,7 @@
/// word characters:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let text = "Retroactively relinquishing remunerations is reprehensible.";
/// for mat in Regex::new(r"\b\w{13}\b").unwrap().find_iter(text) {
@@ -262,7 +261,7 @@
/// year separately.
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"'([^']+)'\s+\((\d{4})\)").unwrap();
/// let text = "Not my favorite movie: 'Citizen Kane' (1941).";
@@ -284,7 +283,7 @@
/// We can make this example a bit clearer by using *named* capture groups:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)")
/// .unwrap();
@@ -328,7 +327,7 @@
/// some text, where the movie is formatted like "'Title' (xxxx)":
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"'(?P<title>[^']+)'\s+\((?P<year>\d{4})\)")
/// .unwrap();
@@ -361,7 +360,7 @@
/// To split a string delimited by arbitrary amounts of spaces or tabs:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"[ \t]+").unwrap();
/// let fields: Vec<&str> = re.split("a b \t c\td e").collect();
@@ -385,7 +384,7 @@
/// Get the first two words in some text:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"\W+").unwrap();
/// let fields: Vec<&str> = re.splitn("Hey! How are you?", 3).collect();
@@ -432,7 +431,7 @@
/// In typical usage, this can just be a normal string:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new("[^01]+").unwrap();
/// assert_eq!(re.replace("1078910", ""), "1010");
@@ -445,7 +444,7 @@
/// capturing group matches easily:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # use regex::Captures; fn main() {
/// let re = Regex::new(r"([^,\s]+),\s+(\S+)").unwrap();
/// let result = re.replace("Springsteen, Bruce", |caps: &Captures| {
@@ -461,7 +460,7 @@
/// with named capture groups:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"(?P<last>[^,\s]+),\s+(?P<first>\S+)").unwrap();
/// let result = re.replace("Springsteen, Bruce", "$first $last");
@@ -478,7 +477,7 @@
/// underscore:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let re = Regex::new(r"(?P<first>\w+)\s+(?P<second>\w+)").unwrap();
/// let result = re.replace("deep fried", "${first}_$second");
@@ -495,7 +494,7 @@
/// byte string with `NoExpand`:
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// use regex::NoExpand;
///
@@ -605,7 +604,7 @@
/// `a`.
///
/// ```rust
- /// # extern crate regex; use regex::Regex;
+ /// # use regex::Regex;
/// # fn main() {
/// let text = "aaaaa";
/// let pos = Regex::new(r"a+").unwrap().shortest_match(text);
@@ -717,7 +716,7 @@
}
/// Returns an iterator over the capture names.
- pub fn capture_names(&self) -> CaptureNames {
+ pub fn capture_names(&self) -> CaptureNames<'_> {
CaptureNames(self.0.capture_names().iter())
}
@@ -1001,15 +1000,15 @@
}
impl<'t> fmt::Debug for Captures<'t> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Captures").field(&CapturesDebug(self)).finish()
}
}
-struct CapturesDebug<'c, 't: 'c>(&'c Captures<'t>);
+struct CapturesDebug<'c, 't>(&'c Captures<'t>);
impl<'c, 't> fmt::Debug for CapturesDebug<'c, 't> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// We'd like to show something nice here, even if it means an
// allocation to build a reverse index.
let slot_to_name: HashMap<&usize, &String> =
@@ -1080,7 +1079,7 @@
/// The lifetime `'c` corresponds to the lifetime of the `Captures` value, and
/// the lifetime `'t` corresponds to the originally matched text.
#[derive(Clone, Debug)]
-pub struct SubCaptureMatches<'c, 't: 'c> {
+pub struct SubCaptureMatches<'c, 't> {
caps: &'c Captures<'t>,
it: SubCapturesPosIter<'c>,
}
@@ -1158,7 +1157,7 @@
///
/// For example, a no-op replacement would be
/// `dst.push_str(caps.get(0).unwrap().as_str())`.
- fn replace_append(&mut self, caps: &Captures, dst: &mut String);
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String);
/// Return a fixed unchanging replacement string.
///
@@ -1201,68 +1200,68 @@
///
/// Returned by [`Replacer::by_ref`](trait.Replacer.html#method.by_ref).
#[derive(Debug)]
-pub struct ReplacerRef<'a, R: ?Sized + 'a>(&'a mut R);
+pub struct ReplacerRef<'a, R: ?Sized>(&'a mut R);
impl<'a, R: Replacer + ?Sized + 'a> Replacer for ReplacerRef<'a, R> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
self.0.replace_append(caps, dst)
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
self.0.no_expansion()
}
}
impl<'a> Replacer for &'a str {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
caps.expand(*self, dst);
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
no_expansion(self)
}
}
impl<'a> Replacer for &'a String {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
self.as_str().replace_append(caps, dst)
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
no_expansion(self)
}
}
impl Replacer for String {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
self.as_str().replace_append(caps, dst)
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
no_expansion(self)
}
}
impl<'a> Replacer for Cow<'a, str> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
self.as_ref().replace_append(caps, dst)
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
no_expansion(self)
}
}
impl<'a> Replacer for &'a Cow<'a, str> {
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
self.as_ref().replace_append(caps, dst)
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
no_expansion(self)
}
}
-fn no_expansion<T: AsRef<str>>(t: &T) -> Option<Cow<str>> {
+fn no_expansion<T: AsRef<str>>(t: &T) -> Option<Cow<'_, str>> {
let s = t.as_ref();
match find_byte(b'$', s.as_bytes()) {
Some(_) => None,
@@ -1272,10 +1271,10 @@
impl<F, T> Replacer for F
where
- F: FnMut(&Captures) -> T,
+ F: FnMut(&Captures<'_>) -> T,
T: AsRef<str>,
{
- fn replace_append(&mut self, caps: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, caps: &Captures<'_>, dst: &mut String) {
dst.push_str((*self)(caps).as_ref());
}
}
@@ -1292,11 +1291,11 @@
pub struct NoExpand<'t>(pub &'t str);
impl<'t> Replacer for NoExpand<'t> {
- fn replace_append(&mut self, _: &Captures, dst: &mut String) {
+ fn replace_append(&mut self, _: &Captures<'_>, dst: &mut String) {
dst.push_str(self.0);
}
- fn no_expansion(&mut self) -> Option<Cow<str>> {
+ fn no_expansion(&mut self) -> Option<Cow<'_, str>> {
Some(Cow::Borrowed(self.0))
}
}
diff --git a/src/sparse.rs b/src/sparse.rs
index 421d6b6..98b7266 100644
--- a/src/sparse.rs
+++ b/src/sparse.rs
@@ -62,7 +62,7 @@
}
impl fmt::Debug for SparseSet {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "SparseSet({:?})", self.dense)
}
}
diff --git a/test b/test
index 3d1351c..b10564f 100755
--- a/test
+++ b/test
@@ -1,5 +1,7 @@
#!/bin/bash
+set -e
+
# This is a convenience script for running a broad swath of tests across
# features. We don't test the complete space, since the complete space is quite
# large. Hopefully once we migrate the test suite to better infrastructure
diff --git a/tests/regression_fuzz.rs b/tests/regression_fuzz.rs
index 5f92ed0..4e76704 100644
--- a/tests/regression_fuzz.rs
+++ b/tests/regression_fuzz.rs
@@ -17,3 +17,15 @@
fn empty_any_errors_no_panic() {
assert!(regex_new!(r"\P{any}").is_err());
}
+
+// This tests that a very large regex errors during compilation instead of
+// using gratuitous amounts of memory. The specific problem is that the
+// compiler wasn't accounting for the memory used by Unicode character classes
+// correctly.
+//
+// See: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=33579
+#[test]
+fn big_regex_fails_to_compile() {
+ let pat = "[\u{0}\u{e}\u{2}\\w~~>[l\t\u{0}]p?<]{971158}";
+ assert!(regex_new!(pat).is_err());
+}
diff --git a/tests/replace.rs b/tests/replace.rs
index 700aff2..1dc6106 100644
--- a/tests/replace.rs
+++ b/tests/replace.rs
@@ -94,7 +94,7 @@
replace,
r"([0-9]+)",
"age: 26",
- |captures: &Captures| {
+ |captures: &Captures<'_>| {
match_text!(captures.get(1).unwrap())[0..1].to_owned()
},
"age: 2"
@@ -104,7 +104,7 @@
replace,
r"[0-9]+",
"age: 26",
- |_captures: &Captures| t!("Z").to_owned(),
+ |_captures: &Captures<'_>| t!("Z").to_owned(),
"age: Z"
);
diff --git a/tests/test_backtrack.rs b/tests/test_backtrack.rs
index 617185f..fb934e2 100644
--- a/tests/test_backtrack.rs
+++ b/tests/test_backtrack.rs
@@ -1,8 +1,5 @@
#![cfg_attr(feature = "pattern", feature(pattern))]
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;
diff --git a/tests/test_backtrack_bytes.rs b/tests/test_backtrack_bytes.rs
index 17df4d8..a59426c 100644
--- a/tests/test_backtrack_bytes.rs
+++ b/tests/test_backtrack_bytes.rs
@@ -1,6 +1,3 @@
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;
diff --git a/tests/test_backtrack_utf8bytes.rs b/tests/test_backtrack_utf8bytes.rs
index 78a0135..6d308e9 100644
--- a/tests/test_backtrack_utf8bytes.rs
+++ b/tests/test_backtrack_utf8bytes.rs
@@ -1,8 +1,5 @@
#![cfg_attr(feature = "pattern", feature(pattern))]
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;
diff --git a/tests/test_crates_regex.rs b/tests/test_crates_regex.rs
index d697683..a681604 100644
--- a/tests/test_crates_regex.rs
+++ b/tests/test_crates_regex.rs
@@ -1,6 +1,3 @@
-extern crate quickcheck;
-extern crate regex;
-
/*
* This test is a minimal version of <rofl_0> and <subdiff_0>
*
diff --git a/tests/test_default.rs b/tests/test_default.rs
index af634a0..d4365fb 100644
--- a/tests/test_default.rs
+++ b/tests/test_default.rs
@@ -1,7 +1,6 @@
#![cfg_attr(feature = "pattern", feature(pattern))]
-extern crate rand;
-extern crate regex;
+use regex;
// Due to macro scoping rules, this definition only applies for the modules
// defined below. Effectively, it allows us to use the same tests for both
diff --git a/tests/test_default_bytes.rs b/tests/test_default_bytes.rs
index e4a25dc..f200596 100644
--- a/tests/test_default_bytes.rs
+++ b/tests/test_default_bytes.rs
@@ -1,6 +1,3 @@
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::bytes::Regex;
diff --git a/tests/test_nfa.rs b/tests/test_nfa.rs
index 05dad23..e5a67d1 100644
--- a/tests/test_nfa.rs
+++ b/tests/test_nfa.rs
@@ -1,8 +1,5 @@
#![cfg_attr(feature = "pattern", feature(pattern))]
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;
diff --git a/tests/test_nfa_bytes.rs b/tests/test_nfa_bytes.rs
index 1042318..0a10e03 100644
--- a/tests/test_nfa_bytes.rs
+++ b/tests/test_nfa_bytes.rs
@@ -1,6 +1,3 @@
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;
diff --git a/tests/test_nfa_utf8bytes.rs b/tests/test_nfa_utf8bytes.rs
index 86487a1..36a572b 100644
--- a/tests/test_nfa_utf8bytes.rs
+++ b/tests/test_nfa_utf8bytes.rs
@@ -1,8 +1,5 @@
#![cfg_attr(feature = "pattern", feature(pattern))]
-extern crate rand;
-extern crate regex;
-
macro_rules! regex_new {
($re:expr) => {{
use regex::internal::ExecBuilder;