diff options
Diffstat (limited to 'vendor/regex/src/lib.rs')
| -rw-r--r-- | vendor/regex/src/lib.rs | 1347 |
1 files changed, 946 insertions, 401 deletions
diff --git a/vendor/regex/src/lib.rs b/vendor/regex/src/lib.rs index 82c1b77ad..6dbd3c202 100644 --- a/vendor/regex/src/lib.rs +++ b/vendor/regex/src/lib.rs @@ -1,146 +1,371 @@ /*! -This crate provides a library for parsing, compiling, and executing regular -expressions. Its syntax is similar to Perl-style regular expressions, but lacks -a few features like look around and backreferences. In exchange, all searches -execute in linear time with respect to the size of the regular expression and -search text. +This crate provides routines for searching strings for matches of a [regular +expression] (aka "regex"). The regex syntax supported by this crate is similar +to other regex engines, but it lacks several features that are not known how to +implement efficiently. This includes, but is not limited to, look-around and +backreferences. In exchange, all regex searches in this crate have worst case +`O(m * n)` time complexity, where `m` is proportional to the size of the regex +and `n` is proportional to the size of the string being searched. -This crate's documentation provides some simple examples, describes -[Unicode support](#unicode) and exhaustively lists the -[supported syntax](#syntax). +[regular expression]: https://en.wikipedia.org/wiki/Regular_expression -For more specific details on the API for regular expressions, please see the -documentation for the [`Regex`](struct.Regex.html) type. +If you just want API documentation, then skip to the [`Regex`] type. Otherwise, +here's a quick example showing one way of parsing the output of a grep-like +program: + +```rust +use regex::Regex; + +let re = Regex::new(r"(?m)^([^:]+):([0-9]+):(.+)$").unwrap(); +let hay = "\ +path/to/foo:54:Blue Harvest +path/to/bar:90:Something, Something, Something, Dark Side +path/to/baz:3:It's a Trap! +"; + +let mut results = vec![]; +for (_, [path, lineno, line]) in re.captures_iter(hay).map(|c| c.extract()) { + results.push((path, lineno.parse::<u64>()?, line)); +} +assert_eq!(results, vec![ + ("path/to/foo", 54, "Blue Harvest"), + ("path/to/bar", 90, "Something, Something, Something, Dark Side"), + ("path/to/baz", 3, "It's a Trap!"), +]); +# Ok::<(), Box<dyn std::error::Error>>(()) +``` + +# Overview + +The primary type in this crate is a [`Regex`]. Its most important methods are +as follows: + +* [`Regex::new`] compiles a regex using the default configuration. A +[`RegexBuilder`] permits setting a non-default configuration. (For example, +case insensitive matching, verbose mode and others.) +* [`Regex::is_match`] reports whether a match exists in a particular haystack. +* [`Regex::find`] reports the byte offsets of a match in a haystack, if one +exists. [`Regex::find_iter`] returns an iterator over all such matches. +* [`Regex::captures`] returns a [`Captures`], which reports both the byte +offsets of a match in a haystack and the byte offsets of each matching capture +group from the regex in the haystack. +[`Regex::captures_iter`] returns an iterator over all such matches. + +There is also a [`RegexSet`], which permits searching for multiple regex +patterns simultaneously in a single search. However, it currently only reports +which patterns match and *not* the byte offsets of a match. + +Otherwise, this top-level crate documentation is organized as follows: + +* [Usage](#usage) shows how to add the `regex` crate to your Rust project. +* [Examples](#examples) provides a limited selection of regex search examples. +* [Performance](#performance) provides a brief summary of how to optimize regex +searching speed. +* [Unicode](#unicode) discusses support for non-ASCII patterns. +* [Syntax](#syntax) enumerates the specific regex syntax supported by this +crate. +* [Untrusted input](#untrusted-input) discusses how this crate deals with regex +patterns or haystacks that are untrusted. +* [Crate features](#crate-features) documents the Cargo features that can be +enabled or disabled for this crate. +* [Other crates](#other-crates) links to other crates in the `regex` family. # Usage -This crate is [on crates.io](https://crates.io/crates/regex) and can be +The `regex` crate is [on crates.io](https://crates.io/crates/regex) and can be used by adding `regex` to your dependencies in your project's `Cargo.toml`. +Or more simply, just run `cargo add regex`. + +Here is a complete example that creates a new Rust project, adds a dependency +on `regex`, creates the source code for a regex search and then runs the +program. + +First, create the project in a new directory: -```toml -[dependencies] -regex = "1" +```text +$ mkdir regex-example +$ cd regex-example +$ cargo init ``` -# Example: find a date +Second, add a dependency on `regex`: -General use of regular expressions in this package involves compiling an -expression and then using it to search, split or replace text. For example, -to confirm that some text resembles a date: +```text +$ cargo add regex +``` + +Third, edit `src/main.rs`. Delete what's there and replace it with this: + +``` +use regex::Regex; + +fn main() { + let re = Regex::new(r"Hello (?<name>\w+)!").unwrap(); + let Some(caps) = re.captures("Hello Murphy!") else { + println!("no match!"); + return; + }; + println!("The name is: {}", &caps["name"]); +} +``` + +Fourth, run it with `cargo run`: + +```text +$ cargo run + Compiling memchr v2.5.0 + Compiling regex-syntax v0.7.1 + Compiling aho-corasick v1.0.1 + Compiling regex v1.8.1 + Compiling regex-example v0.1.0 (/tmp/regex-example) + Finished dev [unoptimized + debuginfo] target(s) in 4.22s + Running `target/debug/regex-example` +The name is: Murphy +``` + +The first time you run the program will show more output like above. But +subsequent runs shouldn't have to re-compile the dependencies. + +# Examples + +This section provides a few examples, in tutorial style, showing how to +search a haystack with a regex. There are more examples throughout the API +documentation. + +Before starting though, it's worth defining a few terms: + +* A **regex** is a Rust value whose type is `Regex`. We use `re` as a +variable name for a regex. +* A **pattern** is the string that is used to build a regex. We use `pat` as +a variable name for a pattern. +* A **haystack** is the string that is searched by a regex. We use `hay` as a +variable name for a haystack. + +Sometimes the words "regex" and "pattern" are used interchangeably. + +General use of regular expressions in this crate proceeds by compiling a +**pattern** into a **regex**, and then using that regex to search, split or +replace parts of a **haystack**. + +### Example: find a middle initial + +We'll start off with a very simple example: a regex that looks for a specific +name but uses a wildcard to match a middle initial. Our pattern serves as +something like a template that will match a particular name with *any* middle +initial. ```rust use regex::Regex; -let re = Regex::new(r"^\d{4}-\d{2}-\d{2}$").unwrap(); -assert!(re.is_match("2014-01-01")); + +// We use 'unwrap()' here because it would be a bug in our program if the +// pattern failed to compile to a regex. Panicking in the presence of a bug +// is okay. +let re = Regex::new(r"Homer (.)\. Simpson").unwrap(); +let hay = "Homer J. Simpson"; +let Some(caps) = re.captures(hay) else { return }; +assert_eq!("J", &caps[1]); ``` -Notice the use of the `^` and `$` anchors. In this crate, every expression -is executed with an implicit `.*?` at the beginning and end, which allows -it to match anywhere in the text. Anchors can be used to ensure that the -full text matches an expression. +There are a few things worth noticing here in our first example: -This example also demonstrates the utility of -[raw strings](https://doc.rust-lang.org/stable/reference/tokens.html#raw-string-literals) -in Rust, which -are just like regular strings except they are prefixed with an `r` and do -not process any escape sequences. For example, `"\\d"` is the same -expression as `r"\d"`. +* The `.` is a special pattern meta character that means "match any single +character except for new lines." (More precisely, in this crate, it means +"match any UTF-8 encoding of any Unicode scalar value other than `\n`.") +* We can match an actual `.` literally by escaping it, i.e., `\.`. +* We use Rust's [raw strings] to avoid needing to deal with escape sequences in +both the regex pattern syntax and in Rust's string literal syntax. If we didn't +use raw strings here, we would have had to use `\\.` to match a literal `.` +character. That is, `r"\."` and `"\\."` are equivalent patterns. +* We put our wildcard `.` instruction in parentheses. These parentheses have a +special meaning that says, "make whatever part of the haystack matches within +these parentheses available as a capturing group." After finding a match, we +access this capture group with `&caps[1]`. -# Example: Avoid compiling the same regex in a loop +[raw strings]: https://doc.rust-lang.org/stable/reference/tokens.html#raw-string-literals -It is an anti-pattern to compile the same regular expression in a loop -since compilation is typically expensive. (It takes anywhere from a few -microseconds to a few **milliseconds** depending on the size of the -regex.) Not only is compilation itself expensive, but this also prevents -optimizations that reuse allocations internally to the matching engines. +Otherwise, we execute a search using `re.captures(hay)` and return from our +function if no match occurred. We then reference the middle initial by asking +for the part of the haystack that matched the capture group indexed at `1`. +(The capture group at index 0 is implicit and always corresponds to the entire +match. In this case, that's `Homer J. Simpson`.) -In Rust, it can sometimes be a pain to pass regular expressions around if -they're used from inside a helper function. Instead, we recommend using the -[`lazy_static`](https://crates.io/crates/lazy_static) crate to ensure that -regular expressions are compiled exactly once. +### Example: named capture groups -For example: +Continuing from our middle initial example above, we can tweak the pattern +slightly to give a name to the group that matches the middle initial: ```rust -use lazy_static::lazy_static; use regex::Regex; -fn some_helper_function(text: &str) -> bool { - lazy_static! { - static ref RE: Regex = Regex::new("...").unwrap(); - } - RE.is_match(text) -} +// Note that (?P<middle>.) is a different way to spell the same thing. +let re = Regex::new(r"Homer (?<middle>.)\. Simpson").unwrap(); +let hay = "Homer J. Simpson"; +let Some(caps) = re.captures(hay) else { return }; +assert_eq!("J", &caps["middle"]); +``` + +Giving a name to a group can be useful when there are multiple groups in +a pattern. It makes the code referring to those groups a bit easier to +understand. + +### Example: validating a particular date format + +This examples shows how to confirm whether a haystack, in its entirety, matches +a particular date format: + +```rust +use regex::Regex; -fn main() {} +let re = Regex::new(r"^\d{4}-\d{2}-\d{2}$").unwrap(); +assert!(re.is_match("2010-03-14")); ``` -Specifically, in this example, the regex will be compiled when it is used for -the first time. On subsequent uses, it will reuse the previous compilation. +Notice the use of the `^` and `$` anchors. In this crate, every regex search is +run with an implicit `(?s:.)*?` at the beginning of its pattern, which allows +the regex to match anywhere in a haystack. Anchors, as above, can be used to +ensure that the full haystack matches a pattern. + +This crate is also Unicode aware by default, which means that `\d` might match +more than you might expect it to. For example: + +```rust +use regex::Regex; + +let re = Regex::new(r"^\d{4}-\d{2}-\d{2}$").unwrap(); +assert!(re.is_match("𝟚𝟘𝟙𝟘-𝟘𝟛-𝟙𝟜")); +``` + +To only match an ASCII decimal digit, all of the following are equivalent: -# Example: iterating over capture groups +* `[0-9]` +* `(?-u:\d)` +* `[[:digit:]]` +* `[\d&&\p{ascii}]` -This crate provides convenient iterators for matching an expression -repeatedly against a search string to find successive non-overlapping -matches. For example, to find all dates in a string and be able to access -them by their component pieces: +### Example: finding dates in a haystack + +In the previous example, we showed how one might validate that a haystack, +in its entirety, corresponded to a particular date format. But what if we wanted +to extract all things that look like dates in a specific format from a haystack? +To do this, we can use an iterator API to find all matches (notice that we've +removed the anchors and switched to looking for ASCII-only digits): ```rust -# 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"; -for cap in re.captures_iter(text) { - println!("Month: {} Day: {} Year: {}", &cap[2], &cap[3], &cap[1]); -} -// Output: -// Month: 03 Day: 14 Year: 2012 -// Month: 01 Day: 01 Year: 2013 -// Month: 07 Day: 05 Year: 2014 -# } +use regex::Regex; + +let re = Regex::new(r"[0-9]{4}-[0-9]{2}-[0-9]{2}").unwrap(); +let hay = "What do 1865-04-14, 1881-07-02, 1901-09-06 and 1963-11-22 have in common?"; +// 'm' is a 'Match', and 'as_str()' returns the matching part of the haystack. +let dates: Vec<&str> = re.find_iter(hay).map(|m| m.as_str()).collect(); +assert_eq!(dates, vec![ + "1865-04-14", + "1881-07-02", + "1901-09-06", + "1963-11-22", +]); +``` + +We can also iterate over [`Captures`] values instead of [`Match`] values, and +that in turn permits accessing each component of the date via capturing groups: + +```rust +use regex::Regex; + +let re = Regex::new(r"(?<y>[0-9]{4})-(?<m>[0-9]{2})-(?<d>[0-9]{2})").unwrap(); +let hay = "What do 1865-04-14, 1881-07-02, 1901-09-06 and 1963-11-22 have in common?"; +// 'm' is a 'Match', and 'as_str()' returns the matching part of the haystack. +let dates: Vec<(&str, &str, &str)> = re.captures_iter(hay).map(|caps| { + // The unwraps are okay because every capture group must match if the whole + // regex matches, and in this context, we know we have a match. + // + // Note that we use `caps.name("y").unwrap().as_str()` instead of + // `&caps["y"]` because the lifetime of the former is the same as the + // lifetime of `hay` above, but the lifetime of the latter is tied to the + // lifetime of `caps` due to how the `Index` trait is defined. + let year = caps.name("y").unwrap().as_str(); + let month = caps.name("m").unwrap().as_str(); + let day = caps.name("d").unwrap().as_str(); + (year, month, day) +}).collect(); +assert_eq!(dates, vec![ + ("1865", "04", "14"), + ("1881", "07", "02"), + ("1901", "09", "06"), + ("1963", "11", "22"), +]); ``` -Notice that the year is in the capture group indexed at `1`. This is -because the *entire match* is stored in the capture group at index `0`. +### Example: simpler capture group extraction -# Example: replacement with named capture groups +One can use [`Captures::extract`] to make the code from the previous example a +bit simpler in this case: + +```rust +use regex::Regex; + +let re = Regex::new(r"([0-9]{4})-([0-9]{2})-([0-9]{2})").unwrap(); +let hay = "What do 1865-04-14, 1881-07-02, 1901-09-06 and 1963-11-22 have in common?"; +let dates: Vec<(&str, &str, &str)> = re.captures_iter(hay).map(|caps| { + let (_, [year, month, day]) = caps.extract(); + (year, month, day) +}).collect(); +assert_eq!(dates, vec![ + ("1865", "04", "14"), + ("1881", "07", "02"), + ("1901", "09", "06"), + ("1963", "11", "22"), +]); +``` + +`Captures::extract` works by ensuring that the number of matching groups match +the number of groups requested via the `[year, month, day]` syntax. If they do, +then the substrings for each corresponding capture group are automatically +returned in an appropriately sized array. Rust's syntax for pattern matching +arrays does the rest. + +### Example: replacement with named capture groups Building on the previous example, perhaps we'd like to rearrange the date -formats. This can be done with text replacement. But to make the code -clearer, we can *name* our capture groups and use those names as variables -in our replacement text: +formats. This can be done by finding each match and replacing it with +something different. The [`Regex::replace_all`] routine provides a convenient +way to do this, including by supporting references to named groups in the +replacement string: ```rust -# 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"; +use regex::Regex; + +let re = Regex::new(r"(?<y>\d{4})-(?<m>\d{2})-(?<d>\d{2})").unwrap(); +let before = "1973-01-05, 1975-08-25 and 1980-10-18"; let after = re.replace_all(before, "$m/$d/$y"); -assert_eq!(after, "03/14/2012, 01/01/2013 and 07/05/2014"); -# } +assert_eq!(after, "01/05/1973, 08/25/1975 and 10/18/1980"); ``` -The `replace` methods are actually polymorphic in the replacement, which +The replace methods are actually polymorphic in the replacement, which provides more flexibility than is seen here. (See the documentation for -`Regex::replace` for more details.) +[`Regex::replace`] for more details.) + +### Example: verbose mode -Note that if your regex gets complicated, you can use the `x` flag to -enable insignificant whitespace mode, which also lets you write comments: +When your regex gets complicated, you might consider using something other +than regex. But if you stick with regex, you can use the `x` flag to enable +insignificant whitespace mode or "verbose mode." In this mode, whitespace +is treated as insignificant and one may write comments. This may make your +patterns easier to comprehend. ```rust -# use regex::Regex; -# fn main() { +use regex::Regex; + let re = Regex::new(r"(?x) - (?P<y>\d{4}) # the year + (?P<y>\d{4}) # the year, including all Unicode digits - - (?P<m>\d{2}) # the month + (?P<m>\d{2}) # the month, including all Unicode digits - - (?P<d>\d{2}) # the day + (?P<d>\d{2}) # the day, including all Unicode digits ").unwrap(); -let before = "2012-03-14, 2013-01-01 and 2014-07-05"; + +let before = "1973-01-05, 1975-08-25 and 1980-10-18"; let after = re.replace_all(before, "$m/$d/$y"); -assert_eq!(after, "03/14/2012, 01/01/2013 and 07/05/2014"); -# } +assert_eq!(after, "01/05/1973, 08/25/1975 and 10/18/1980"); ``` If you wish to match against whitespace in this mode, you can still use `\s`, @@ -148,10 +373,10 @@ If you wish to match against whitespace in this mode, you can still use `\s`, directly with `\ `, use its hex character code `\x20` or temporarily disable the `x` flag, e.g., `(?-x: )`. -# Example: match multiple regular expressions simultaneously +### Example: match multiple regular expressions simultaneously -This demonstrates how to use a `RegexSet` to match multiple (possibly -overlapping) regular expressions in a single scan of the search text: +This demonstrates how to use a [`RegexSet`] to match multiple (possibly +overlapping) regexes in a single scan of a haystack: ```rust use regex::RegexSet; @@ -166,7 +391,8 @@ let set = RegexSet::new(&[ r"foobar", ]).unwrap(); -// Iterate over and collect all of the matches. +// Iterate over and collect all of the matches. Each match corresponds to the +// ID of the matching pattern. let matches: Vec<_> = set.matches("foobar").into_iter().collect(); assert_eq!(matches, vec![0, 2, 3, 4, 6]); @@ -176,96 +402,225 @@ assert!(!matches.matched(5)); assert!(matches.matched(6)); ``` -# Pay for what you use +# Performance + +This section briefly discusses a few concerns regarding the speed and resource +usage of regexes. -With respect to searching text with a regular expression, there are three -questions that can be asked: +### Only ask for what you need -1. Does the text match this expression? -2. If so, where does it match? -3. Where did the capturing groups match? +When running a search with a regex, there are generally three different types +of information one can ask for: + +1. Does a regex match in a haystack? +2. Where does a regex match in a haystack? +3. Where do each of the capturing groups match in a haystack? Generally speaking, this crate could provide a function to answer only #3, which would subsume #1 and #2 automatically. However, it can be significantly more expensive to compute the location of capturing group matches, so it's best not to do it if you don't need to. -Therefore, only use what you need. For example, don't use `find` if you -only need to test if an expression matches a string. (Use `is_match` -instead.) +Therefore, only ask for what you need. For example, don't use [`Regex::find`] +if you only need to test if a regex matches a haystack. Use [`Regex::is_match`] +instead. + +### Unicode can impact memory usage and search speed + +This crate has first class support for Unicode and it is **enabled by default**. +In many cases, the extra memory required to support it will be negligible and +it typically won't impact search speed. But it can in some cases. + +With respect to memory usage, the impact of Unicode principally manifests +through the use of Unicode character classes. Unicode character classes +tend to be quite large. For example, `\w` by default matches around 140,000 +distinct codepoints. This requires additional memory, and tends to slow down +regex compilation. While a `\w` here and there is unlikely to be noticed, +writing `\w{100}` will for example result in quite a large regex by default. +Indeed, `\w` is considerably larger than its ASCII-only version, so if your +requirements are satisfied by ASCII, it's probably a good idea to stick to +ASCII classes. The ASCII-only version of `\w` can be spelled in a number of +ways. All of the following are equivalent: + +* `[0-9A-Za-z_]` +* `(?-u:\w)` +* `[[:word:]]` +* `[\w&&\p{ascii}]` + +With respect to search speed, Unicode tends to be handled pretty well, even when +using large Unicode character classes. However, some of the faster internal +regex engines cannot handle a Unicode aware word boundary assertion. So if you +don't need Unicode-aware word boundary assertions, you might consider using +`(?-u:\b)` instead of `\b`, where the former uses an ASCII-only definition of +a word character. + +### Literals might accelerate searches + +This crate tends to be quite good at recognizing literals in a regex pattern +and using them to accelerate a search. If it is at all possible to include +some kind of literal in your pattern, then it might make search substantially +faster. For example, in the regex `\w+@\w+`, the engine will look for +occurrences of `@` and then try a reverse match for `\w+` to find the start +position. + +### Avoid re-compiling regexes, especially in a loop + +It is an anti-pattern to compile the same pattern in a loop since regex +compilation is typically expensive. (It takes anywhere from a few microseconds +to a few **milliseconds** depending on the size of the pattern.) Not only is +compilation itself expensive, but this also prevents optimizations that reuse +allocations internally to the regex engine. + +In Rust, it can sometimes be a pain to pass regexes around if they're used from +inside a helper function. Instead, we recommend using crates like [`once_cell`] +and [`lazy_static`] to ensure that patterns are compiled exactly once. + +[`once_cell`]: https://crates.io/crates/once_cell +[`lazy_static`]: https://crates.io/crates/lazy_static + +This example shows how to use `once_cell`: -# Unicode +```rust +use { + once_cell::sync::Lazy, + regex::Regex, +}; -This implementation executes regular expressions **only** on valid UTF-8 -while exposing match locations as byte indices into the search string. (To -relax this restriction, use the [`bytes`](bytes/index.html) sub-module.) -Conceptually, the regex engine works by matching a haystack as if it were a -sequence of Unicode scalar values. +fn some_helper_function(haystack: &str) -> bool { + static RE: Lazy<Regex> = Lazy::new(|| Regex::new(r"...").unwrap()); + RE.is_match(haystack) +} + +fn main() { + assert!(some_helper_function("abc")); + assert!(!some_helper_function("ac")); +} +``` + +Specifically, in this example, the regex will be compiled when it is used for +the first time. On subsequent uses, it will reuse the previously built `Regex`. +Notice how one can define the `Regex` locally to a specific function. + +### Sharing a regex across threads can result in contention + +While a single `Regex` can be freely used from multiple threads simultaneously, +there is a small synchronization cost that must be paid. Generally speaking, +one shouldn't expect to observe this unless the principal task in each thread +is searching with the regex *and* most searches are on short haystacks. In this +case, internal contention on shared resources can spike and increase latency, +which in turn may slow down each individual search. + +One can work around this by cloning each `Regex` before sending it to another +thread. The cloned regexes will still share the same internal read-only portion +of its compiled state (it's reference counted), but each thread will get +optimized access to the mutable space that is used to run a search. In general, +there is no additional cost in memory to doing this. The only cost is the added +code complexity required to explicitly clone the regex. (If you share the same +`Regex` across multiple threads, each thread still gets its own mutable space, +but accessing that space is slower.) -Only simple case folding is supported. Namely, when matching -case-insensitively, the characters are first mapped using the "simple" case -folding rules defined by Unicode. +# Unicode -Regular expressions themselves are **only** interpreted as a sequence of -Unicode scalar values. This means you can use Unicode characters directly -in your expression: +This section discusses what kind of Unicode support this regex library has. +Before showing some examples, we'll summarize the relevant points: + +* This crate almost fully implements "Basic Unicode Support" (Level 1) as +specified by the [Unicode Technical Standard #18][UTS18]. The full details +of what is supported are documented in [UNICODE.md] in the root of the regex +crate repository. There is virtually no support for "Extended Unicode Support" +(Level 2) from UTS#18. +* The top-level [`Regex`] runs searches *as if* iterating over each of the +codepoints in the haystack. That is, the fundamental atom of matching is a +single codepoint. +* [`bytes::Regex`], in contrast, permits disabling Unicode mode for part of all +of your pattern in all cases. When Unicode mode is disabled, then a search is +run *as if* iterating over each byte in the haystack. That is, the fundamental +atom of matching is a single byte. (A top-level `Regex` also permits disabling +Unicode and thus matching *as if* it were one byte at a time, but only when +doing so wouldn't permit matching invalid UTF-8.) +* When Unicode mode is enabled (the default), `.` will match an entire Unicode +scalar value, even when it is encoded using multiple bytes. When Unicode mode +is disabled (e.g., `(?-u:.)`), then `.` will match a single byte in all cases. +* The character classes `\w`, `\d` and `\s` are all Unicode-aware by default. +Use `(?-u:\w)`, `(?-u:\d)` and `(?-u:\s)` to get their ASCII-only definitions. +* Similarly, `\b` and `\B` use a Unicode definition of a "word" character. +To get ASCII-only word boundaries, use `(?-u:\b)` and `(?-u:\B)`. This also +applies to the special word boundary assertions. (That is, `\b{start}`, +`\b{end}`, `\b{start-half}`, `\b{end-half}`.) +* `^` and `$` are **not** Unicode-aware in multi-line mode. Namely, they only +recognize `\n` (assuming CRLF mode is not enabled) and not any of the other +forms of line terminators defined by Unicode. +* Case insensitive searching is Unicode-aware and uses simple case folding. +* Unicode general categories, scripts and many boolean properties are available +by default via the `\p{property name}` syntax. +* In all cases, matches are reported using byte offsets. Or more precisely, +UTF-8 code unit offsets. This permits constant time indexing and slicing of the +haystack. + +[UTS18]: https://unicode.org/reports/tr18/ +[UNICODE.md]: https://github.com/rust-lang/regex/blob/master/UNICODE.md + +Patterns themselves are **only** interpreted as a sequence of Unicode scalar +values. This means you can use Unicode characters directly in your pattern: ```rust -# use regex::Regex; -# fn main() { +use regex::Regex; + let re = Regex::new(r"(?i)Δ+").unwrap(); -let mat = re.find("ΔδΔ").unwrap(); -assert_eq!((mat.start(), mat.end()), (0, 6)); -# } +let m = re.find("ΔδΔ").unwrap(); +assert_eq!((0, 6), (m.start(), m.end())); +// alternatively: +assert_eq!(0..6, m.range()); ``` -Most features of the regular expressions in this crate are Unicode aware. Here -are some examples: - -* `.` will match any valid UTF-8 encoded Unicode scalar value except for `\n`. - (To also match `\n`, enable the `s` flag, e.g., `(?s:.)`.) -* `\w`, `\d` and `\s` are Unicode aware. For example, `\s` will match all forms - of whitespace categorized by Unicode. -* `\b` matches a Unicode word boundary. -* Negated character classes like `[^a]` match all Unicode scalar values except - for `a`. -* `^` and `$` are **not** Unicode aware in multi-line mode. Namely, they only - recognize `\n` and not any of the other forms of line terminators defined - by Unicode. - -Unicode general categories, scripts, script extensions, ages and a smattering -of boolean properties are available as character classes. For example, you can -match a sequence of numerals, Greek or Cherokee letters: +As noted above, Unicode general categories, scripts, script extensions, ages +and a smattering of boolean properties are available as character classes. For +example, you can match a sequence of numerals, Greek or Cherokee letters: ```rust -# use regex::Regex; -# fn main() { +use regex::Regex; + let re = Regex::new(r"[\pN\p{Greek}\p{Cherokee}]+").unwrap(); -let mat = re.find("abcΔᎠβⅠᏴγδⅡxyz").unwrap(); -assert_eq!((mat.start(), mat.end()), (3, 23)); -# } +let m = re.find("abcΔᎠβⅠᏴγδⅡxyz").unwrap(); +assert_eq!(3..23, m.range()); ``` -For a more detailed breakdown of Unicode support with respect to -[UTS#18](https://unicode.org/reports/tr18/), -please see the -[UNICODE](https://github.com/rust-lang/regex/blob/master/UNICODE.md) -document in the root of the regex repository. +While not specific to Unicode, this library also supports character class set +operations. Namely, one can nest character classes arbitrarily and perform set +operations on them. Those set operations are union (the default), intersection, +difference and symmetric difference. These set operations tend to be most +useful with Unicode character classes. For example, to match any codepoint +that is both in the `Greek` script and in the `Letter` general category: + +```rust +use regex::Regex; + +let re = Regex::new(r"[\p{Greek}&&\pL]+").unwrap(); +let subs: Vec<&str> = re.find_iter("ΔδΔ𐅌ΔδΔ").map(|m| m.as_str()).collect(); +assert_eq!(subs, vec!["ΔδΔ", "ΔδΔ"]); -# Opt out of Unicode support +// If we just matches on Greek, then all codepoints would match! +let re = Regex::new(r"\p{Greek}+").unwrap(); +let subs: Vec<&str> = re.find_iter("ΔδΔ𐅌ΔδΔ").map(|m| m.as_str()).collect(); +assert_eq!(subs, vec!["ΔδΔ𐅌ΔδΔ"]); +``` -The `bytes` sub-module provides a `Regex` type that can be used to match -on `&[u8]`. By default, text is interpreted as UTF-8 just like it is with -the main `Regex` type. However, this behavior can be disabled by turning -off the `u` flag, even if doing so could result in matching invalid UTF-8. -For example, when the `u` flag is disabled, `.` will match any byte instead -of any Unicode scalar value. +### Opt out of Unicode support + +The [`bytes::Regex`] type that can be used to search `&[u8]` haystacks. By +default, haystacks are conventionally treated as UTF-8 just like it is with the +main `Regex` type. However, this behavior can be disabled by turning off the +`u` flag, even if doing so could result in matching invalid UTF-8. For example, +when the `u` flag is disabled, `.` will match any byte instead of any Unicode +scalar value. Disabling the `u` flag is also possible with the standard `&str`-based `Regex` type, but it is only allowed where the UTF-8 invariant is maintained. For example, `(?-u:\w)` is an ASCII-only `\w` character class and is legal in an -`&str`-based `Regex`, but `(?-u:\xFF)` will attempt to match the raw byte -`\xFF`, which is invalid UTF-8 and therefore is illegal in `&str`-based +`&str`-based `Regex`, but `(?-u:\W)` will attempt to match *any byte* that +isn't in `(?-u:\w)`, which in turn includes bytes that are invalid UTF-8. +Similarly, `(?-u:\xFF)` will attempt to match the raw byte `\xFF` (instead of +`U+00FF`), which is invalid UTF-8 and therefore is illegal in `&str`-based regexes. Finally, since Unicode support requires bundling large Unicode data @@ -281,10 +636,11 @@ The syntax supported in this crate is documented below. Note that the regular expression parser and abstract syntax are exposed in a separate crate, [`regex-syntax`](https://docs.rs/regex-syntax). -## Matching one character +### Matching one character <pre class="rust"> . any character except new line (includes new line with s flag) +[0-9] any ASCII digit \d digit (\p{Nd}) \D not digit \pX Unicode character class identified by a one-letter name @@ -307,20 +663,23 @@ a separate crate, [`regex-syntax`](https://docs.rs/regex-syntax). [0-9--4] Direct subtraction (matching 0-9 except 4) [a-g~~b-h] Symmetric difference (matching `a` and `h` only) [\[\]] Escaping in character classes (matching [ or ]) +[a&&b] An empty character class matching nothing </pre> Any named character class may appear inside a bracketed `[...]` character -class. For example, `[\p{Greek}[:digit:]]` matches any Greek or ASCII -digit. `[\p{Greek}&&\pL]` matches Greek letters. +class. For example, `[\p{Greek}[:digit:]]` matches any ASCII digit or any +codepoint in the `Greek` script. `[\p{Greek}&&\pL]` matches Greek letters. Precedence in character classes, from most binding to least: -1. Ranges: `a-cd` == `[a-c]d` -2. Union: `ab&&bc` == `[ab]&&[bc]` -3. Intersection: `^a-z&&b` == `^[a-z&&b]` -4. Negation +1. Ranges: `[a-cd]` == `[[a-c]d]` +2. Union: `[ab&&bc]` == `[[ab]&&[bc]]` +3. Intersection, difference, symmetric difference. All three have equivalent +precedence, and are evaluated in left-to-right order. For example, +`[\pL--\p{Greek}&&\p{Uppercase}]` == `[[\pL--\p{Greek}]&&\p{Uppercase}]`. +4. Negation: `[^a-z&&b]` == `[^[a-z&&b]]`. -## Composites +### Composites <pre class="rust"> xy concatenation (x followed by y) @@ -346,7 +705,7 @@ let re = Regex::new(r"sam|samwise").unwrap(); assert_eq!("sam", re.find(haystack).unwrap().as_str()); ``` -## Repetitions +### Repetitions <pre class="rust"> x* zero or more of x (greedy) @@ -363,21 +722,44 @@ x{n,}? at least n x (ungreedy/lazy) x{n}? exactly n x </pre> -## Empty matches +### Empty matches <pre class="rust"> -^ the beginning of text (or start-of-line with multi-line mode) -$ the end of text (or end-of-line with multi-line mode) -\A only the beginning of text (even with multi-line mode enabled) -\z only the end of text (even with multi-line mode enabled) -\b a Unicode word boundary (\w on one side and \W, \A, or \z on other) -\B not a Unicode word boundary +^ the beginning of a haystack (or start-of-line with multi-line mode) +$ the end of a haystack (or end-of-line with multi-line mode) +\A only the beginning of a haystack (even with multi-line mode enabled) +\z only the end of a haystack (even with multi-line mode enabled) +\b a Unicode word boundary (\w on one side and \W, \A, or \z on other) +\B not a Unicode word boundary +\b{start}, \< a Unicode start-of-word boundary (\W|\A on the left, \w on the right) +\b{end}, \> a Unicode end-of-word boundary (\w on the left, \W|\z on the right)) +\b{start-half} half of a Unicode start-of-word boundary (\W|\A on the left) +\b{end-half} half of a Unicode end-of-word boundary (\W|\z on the right) </pre> -The empty regex is valid and matches the empty string. For example, the empty -regex matches `abc` at positions `0`, `1`, `2` and `3`. +The empty regex is valid and matches the empty string. For example, the +empty regex matches `abc` at positions `0`, `1`, `2` and `3`. When using the +top-level [`Regex`] on `&str` haystacks, an empty match that splits a codepoint +is guaranteed to never be returned. However, such matches are permitted when +using a [`bytes::Regex`]. For example: -## Grouping and flags +```rust +let re = regex::Regex::new(r"").unwrap(); +let ranges: Vec<_> = re.find_iter("💩").map(|m| m.range()).collect(); +assert_eq!(ranges, vec![0..0, 4..4]); + +let re = regex::bytes::Regex::new(r"").unwrap(); +let ranges: Vec<_> = re.find_iter("💩".as_bytes()).map(|m| m.range()).collect(); +assert_eq!(ranges, vec![0..0, 1..1, 2..2, 3..3, 4..4]); +``` + +Note that an empty regex is distinct from a regex that can never match. +For example, the regex `[a&&b]` is a character class that represents the +intersection of `a` and `b`. That intersection is empty, which means the +character class is empty. Since nothing is in the empty set, `[a&&b]` matches +nothing, not even the empty string. + +### Grouping and flags <pre class="rust"> (exp) numbered capture group (indexed by opening parenthesis) @@ -405,6 +787,7 @@ All flags are by default disabled unless stated otherwise. They are: i case-insensitive: letters match both upper and lower case m multi-line mode: ^ and $ match begin/end of line s allow . to match \n +R enables CRLF mode: when multi-line mode is enabled, \r\n is used U swap the meaning of x* and x*? u Unicode support (enabled by default) x verbose mode, ignores whitespace and allow line comments (starting with `#`) @@ -418,22 +801,22 @@ Flags can be toggled within a pattern. Here's an example that matches case-insensitively for the first part but case-sensitively for the second part: ```rust -# use regex::Regex; -# fn main() { +use regex::Regex; + let re = Regex::new(r"(?i)a+(?-i)b+").unwrap(); -let cap = re.captures("AaAaAbbBBBb").unwrap(); -assert_eq!(&cap[0], "AaAaAbb"); -# } +let m = re.find("AaAaAbbBBBb").unwrap(); +assert_eq!(m.as_str(), "AaAaAbb"); ``` Notice that the `a+` matches either `a` or `A`, but the `b+` only matches `b`. Multi-line mode means `^` and `$` no longer match just at the beginning/end of -the input, but at the beginning/end of lines: +the input, but also at the beginning/end of lines: ``` -# use regex::Regex; +use regex::Regex; + let re = Regex::new(r"(?m)^line \d+").unwrap(); let m = re.find("line one\nline 2\n").unwrap(); assert_eq!(m.as_str(), "line 2"); @@ -442,44 +825,72 @@ assert_eq!(m.as_str(), "line 2"); Note that `^` matches after new lines, even at the end of input: ``` -# use regex::Regex; +use regex::Regex; + let re = Regex::new(r"(?m)^").unwrap(); let m = re.find_iter("test\n").last().unwrap(); assert_eq!((m.start(), m.end()), (5, 5)); ``` -Here is an example that uses an ASCII word boundary instead of a Unicode -word boundary: +When both CRLF mode and multi-line mode are enabled, then `^` and `$` will +match either `\r` and `\n`, but never in the middle of a `\r\n`: + +``` +use regex::Regex; + +let re = Regex::new(r"(?mR)^foo$").unwrap(); +let m = re.find("\r\nfoo\r\n").unwrap(); +assert_eq!(m.as_str(), "foo"); +``` + +Unicode mode can also be selectively disabled, although only when the result +*would not* match invalid UTF-8. One good example of this is using an ASCII +word boundary instead of a Unicode word boundary, which might make some regex +searches run faster: ```rust -# use regex::Regex; -# fn main() { +use regex::Regex; + let re = Regex::new(r"(?-u:\b).+(?-u:\b)").unwrap(); -let cap = re.captures("$$abc$$").unwrap(); -assert_eq!(&cap[0], "abc"); -# } +let m = re.find("$$abc$$").unwrap(); +assert_eq!(m.as_str(), "abc"); ``` -## Escape sequences +### Escape sequences + +Note that this includes all possible escape sequences, even ones that are +documented elsewhere. <pre class="rust"> -\* literal *, works for any punctuation character: \.+*?()|[]{}^$ -\a bell (\x07) -\f form feed (\x0C) -\t horizontal tab -\n new line -\r carriage return -\v vertical tab (\x0B) -\123 octal character code (up to three digits) (when enabled) -\x7F hex character code (exactly two digits) -\x{10FFFF} any hex character code corresponding to a Unicode code point -\u007F hex character code (exactly four digits) -\u{7F} any hex character code corresponding to a Unicode code point -\U0000007F hex character code (exactly eight digits) -\U{7F} any hex character code corresponding to a Unicode code point +\* literal *, applies to all ASCII except [0-9A-Za-z<>] +\a bell (\x07) +\f form feed (\x0C) +\t horizontal tab +\n new line +\r carriage return +\v vertical tab (\x0B) +\A matches at the beginning of a haystack +\z matches at the end of a haystack +\b word boundary assertion +\B negated word boundary assertion +\b{start}, \< start-of-word boundary assertion +\b{end}, \> end-of-word boundary assertion +\b{start-half} half of a start-of-word boundary assertion +\b{end-half} half of a end-of-word boundary assertion +\123 octal character code, up to three digits (when enabled) +\x7F hex character code (exactly two digits) +\x{10FFFF} any hex character code corresponding to a Unicode code point +\u007F hex character code (exactly four digits) +\u{7F} any hex character code corresponding to a Unicode code point +\U0000007F hex character code (exactly eight digits) +\U{7F} any hex character code corresponding to a Unicode code point +\p{Letter} Unicode character class +\P{Letter} negated Unicode character class +\d, \s, \w Perl character class +\D, \S, \W negated Perl character class </pre> -## Perl character classes (Unicode friendly) +### Perl character classes (Unicode friendly) These classes are based on the definitions provided in [UTS#18](https://www.unicode.org/reports/tr18/#Compatibility_Properties): @@ -493,7 +904,10 @@ These classes are based on the definitions provided in \W not word character </pre> -## ASCII character classes +### ASCII character classes + +These classes are based on the definitions provided in +[UTS#18](https://www.unicode.org/reports/tr18/#Compatibility_Properties): <pre class="rust"> [[:alnum:]] alphanumeric ([0-9A-Za-z]) @@ -512,16 +926,228 @@ These classes are based on the definitions provided in [[:xdigit:]] hex digit ([0-9A-Fa-f]) </pre> +# Untrusted input + +This crate is meant to be able to run regex searches on untrusted haystacks +without fear of [ReDoS]. This crate also, to a certain extent, supports +untrusted patterns. + +[ReDoS]: https://en.wikipedia.org/wiki/ReDoS + +This crate differs from most (but not all) other regex engines in that it +doesn't use unbounded backtracking to run a regex search. In those cases, +one generally cannot use untrusted patterns *or* untrusted haystacks because +it can be very difficult to know whether a particular pattern will result in +catastrophic backtracking or not. + +We'll first discuss how this crate deals with untrusted inputs and then wrap +it up with a realistic discussion about what practice really looks like. + +### Panics + +Outside of clearly documented cases, most APIs in this crate are intended to +never panic regardless of the inputs given to them. For example, `Regex::new`, +`Regex::is_match`, `Regex::find` and `Regex::captures` should never panic. That +is, it is an API promise that those APIs will never panic no matter what inputs +are given to them. With that said, regex engines are complicated beasts, and +providing a rock solid guarantee that these APIs literally never panic is +essentially equivalent to saying, "there are no bugs in this library." That is +a bold claim, and not really one that can be feasibly made with a straight +face. + +Don't get the wrong impression here. This crate is extensively tested, not just +with unit and integration tests, but also via fuzz testing. For example, this +crate is part of the [OSS-fuzz project]. Panics should be incredibly rare, but +it is possible for bugs to exist, and thus possible for a panic to occur. If +you need a rock solid guarantee against panics, then you should wrap calls into +this library with [`std::panic::catch_unwind`]. + +It's also worth pointing out that this library will *generally* panic when +other regex engines would commit undefined behavior. When undefined behavior +occurs, your program might continue as if nothing bad has happened, but it also +might mean your program is open to the worst kinds of exploits. In contrast, +the worst thing a panic can do is a denial of service. + +[OSS-fuzz project]: https://android.googlesource.com/platform/external/oss-fuzz/+/refs/tags/android-t-preview-1/projects/rust-regex/ +[`std::panic::catch_unwind`]: https://doc.rust-lang.org/std/panic/fn.catch_unwind.html + +### Untrusted patterns + +The principal way this crate deals with them is by limiting their size by +default. The size limit can be configured via [`RegexBuilder::size_limit`]. The +idea of a size limit is that compiling a pattern into a `Regex` will fail if it +becomes "too big." Namely, while *most* resources consumed by compiling a regex +are approximately proportional (albeit with some high constant factors in some +cases, such as with Unicode character classes) to the length of the pattern +itself, there is one particular exception to this: counted repetitions. Namely, +this pattern: + +```text +a{5}{5}{5}{5}{5}{5} +``` + +Is equivalent to this pattern: + +```text +a{15625} +``` + +In both of these cases, the actual pattern string is quite small, but the +resulting `Regex` value is quite large. Indeed, as the first pattern shows, +it isn't enough to locally limit the size of each repetition because they can +be stacked in a way that results in exponential growth. + +To provide a bit more context, a simplified view of regex compilation looks +like this: + +* The pattern string is parsed into a structured representation called an AST. +Counted repetitions are not expanded and Unicode character classes are not +looked up in this stage. That is, the size of the AST is proportional to the +size of the pattern with "reasonable" constant factors. In other words, one +can reasonably limit the memory used by an AST by limiting the length of the +pattern string. +* The AST is translated into an HIR. Counted repetitions are still *not* +expanded at this stage, but Unicode character classes are embedded into the +HIR. The memory usage of a HIR is still proportional to the length of the +original pattern string, but the constant factors---mostly as a result of +Unicode character classes---can be quite high. Still though, the memory used by +an HIR can be reasonably limited by limiting the length of the pattern string. +* The HIR is compiled into a [Thompson NFA]. This is the stage at which +something like `\w{5}` is rewritten to `\w\w\w\w\w`. Thus, this is the stage +at which [`RegexBuilder::size_limit`] is enforced. If the NFA exceeds the +configured size, then this stage will fail. + +[Thompson NFA]: https://en.wikipedia.org/wiki/Thompson%27s_construction + +The size limit helps avoid two different kinds of exorbitant resource usage: + +* It avoids permitting exponential memory usage based on the size of the +pattern string. +* It avoids long search times. This will be discussed in more detail in the +next section, but worst case search time *is* dependent on the size of the +regex. So keeping regexes limited to a reasonable size is also a way of keeping +search times reasonable. + +Finally, it's worth pointing out that regex compilation is guaranteed to take +worst case `O(m)` time, where `m` is proportional to the size of regex. The +size of the regex here is *after* the counted repetitions have been expanded. + +**Advice for those using untrusted regexes**: limit the pattern length to +something small and expand it as needed. Configure [`RegexBuilder::size_limit`] +to something small and then expand it as needed. + +### Untrusted haystacks + +The main way this crate guards against searches from taking a long time is by +using algorithms that guarantee a `O(m * n)` worst case time and space bound. +Namely: + +* `m` is proportional to the size of the regex, where the size of the regex +includes the expansion of all counted repetitions. (See the previous section on +untrusted patterns.) +* `n` is proportional to the length, in bytes, of the haystack. + +In other words, if you consider `m` to be a constant (for example, the regex +pattern is a literal in the source code), then the search can be said to run +in "linear time." Or equivalently, "linear time with respect to the size of the +haystack." + +But the `m` factor here is important not to ignore. If a regex is +particularly big, the search times can get quite slow. This is why, in part, +[`RegexBuilder::size_limit`] exists. + +**Advice for those searching untrusted haystacks**: As long as your regexes +are not enormous, you should expect to be able to search untrusted haystacks +without fear. If you aren't sure, you should benchmark it. Unlike backtracking +engines, if your regex is so big that it's likely to result in slow searches, +this is probably something you'll be able to observe regardless of what the +haystack is made up of. + +### Iterating over matches + +One thing that is perhaps easy to miss is that the worst case time +complexity bound of `O(m * n)` applies to methods like [`Regex::is_match`], +[`Regex::find`] and [`Regex::captures`]. It does **not** apply to +[`Regex::find_iter`] or [`Regex::captures_iter`]. Namely, since iterating over +all matches can execute many searches, and each search can scan the entire +haystack, the worst case time complexity for iterators is `O(m * n^2)`. + +One example of where this occurs is when a pattern consists of an alternation, +where an earlier branch of the alternation requires scanning the entire +haystack only to discover that there is no match. It also requires a later +branch of the alternation to have matched at the beginning of the search. For +example, consider the pattern `.*[^A-Z]|[A-Z]` and the haystack `AAAAA`. The +first search will scan to the end looking for matches of `.*[^A-Z]` even though +a finite automata engine (as in this crate) knows that `[A-Z]` has already +matched the first character of the haystack. This is due to the greedy nature +of regex searching. That first search will report a match at the first `A` only +after scanning to the end to discover that no other match exists. The next +search then begins at the second `A` and the behavior repeats. + +There is no way to avoid this. This means that if both patterns and haystacks +are untrusted and you're iterating over all matches, you're susceptible to +worst case quadratic time complexity. One possible way to mitigate this +is to drop down to the lower level `regex-automata` crate and use its +`meta::Regex` iterator APIs. There, you can configure the search to operate +in "earliest" mode by passing a `Input::new(haystack).earliest(true)` to +`meta::Regex::find_iter` (for example). By enabling this mode, you give up +the normal greedy match semantics of regex searches and instead ask the regex +engine to immediately stop as soon as a match has been found. Enabling this +mode will thus restore the worst case `O(m * n)` time complexity bound, but at +the cost of different semantics. + +### Untrusted inputs in practice + +While providing a `O(m * n)` worst case time bound on all searches goes a long +way toward preventing [ReDoS], that doesn't mean every search you can possibly +run will complete without burning CPU time. In general, there are a few ways +for the `m * n` time bound to still bite you: + +* You are searching an exceptionally long haystack. No matter how you slice +it, a longer haystack will take more time to search. This crate may often make +very quick work of even long haystacks because of its literal optimizations, +but those aren't available for all regexes. +* Unicode character classes can cause searches to be quite slow in some cases. +This is especially true when they are combined with counted repetitions. While +the regex size limit above will protect you from the most egregious cases, +the default size limit still permits pretty big regexes that can execute more +slowly than one might expect. +* While routines like [`Regex::find`] and [`Regex::captures`] guarantee +worst case `O(m * n)` search time, routines like [`Regex::find_iter`] and +[`Regex::captures_iter`] actually have worst case `O(m * n^2)` search time. +This is because `find_iter` runs many searches, and each search takes worst +case `O(m * n)` time. Thus, iteration of all matches in a haystack has +worst case `O(m * n^2)`. A good example of a pattern that exhibits this is +`(?:A+){1000}|` or even `.*[^A-Z]|[A-Z]`. + +In general, unstrusted haystacks are easier to stomach than untrusted patterns. +Untrusted patterns give a lot more control to the caller to impact the +performance of a search. In many cases, a regex search will actually execute in +average case `O(n)` time (i.e., not dependent on the size of the regex), but +this can't be guaranteed in general. Therefore, permitting untrusted patterns +means that your only line of defense is to put a limit on how big `m` (and +perhaps also `n`) can be in `O(m * n)`. `n` is limited by simply inspecting +the length of the haystack while `m` is limited by *both* applying a limit to +the length of the pattern *and* a limit on the compiled size of the regex via +[`RegexBuilder::size_limit`]. + +It bears repeating: if you're accepting untrusted patterns, it would be a good +idea to start with conservative limits on `m` and `n`, and then carefully +increase them as needed. + # Crate features By default, this crate tries pretty hard to make regex matching both as fast -as possible and as correct as it can be, within reason. This means that there -is a lot of code dedicated to performance, the handling of Unicode data and the -Unicode data itself. Overall, this leads to more dependencies, larger binaries -and longer compile times. This trade off may not be appropriate in all cases, -and indeed, even when all Unicode and performance features are disabled, one -is still left with a perfectly serviceable regex engine that will work well -in many cases. +as possible and as correct as it can be. This means that there is a lot of +code dedicated to performance, the handling of Unicode data and the Unicode +data itself. Overall, this leads to more dependencies, larger binaries and +longer compile times. This trade off may not be appropriate in all cases, and +indeed, even when all Unicode and performance features are disabled, one is +still left with a perfectly serviceable regex engine that will work well in +many cases. (Note that code is not arbitrarily reducible, and for this reason, +the [`regex-lite`](https://docs.rs/regex-lite) crate exists to provide an even +more minimal experience by cutting out Unicode and performance, but still +maintaining the linear search time bound.) This crate exposes a number of features for controlling that trade off. Some of these features are strictly performance oriented, such that disabling them @@ -530,32 +1156,61 @@ Other features, such as the ones controlling the presence or absence of Unicode data, can result in a loss of functionality. For example, if one disables the `unicode-case` feature (described below), then compiling the regex `(?i)a` will fail since Unicode case insensitivity is enabled by default. Instead, -callers must use `(?i-u)a` instead to disable Unicode case folding. Stated -differently, enabling or disabling any of the features below can only add or -subtract from the total set of valid regular expressions. Enabling or disabling -a feature will never modify the match semantics of a regular expression. +callers must use `(?i-u)a` to disable Unicode case folding. Stated differently, +enabling or disabling any of the features below can only add or subtract from +the total set of valid regular expressions. Enabling or disabling a feature +will never modify the match semantics of a regular expression. -All features below are enabled by default. +Most features below are enabled by default. Features that aren't enabled by +default are noted. ### Ecosystem features * **std** - - When enabled, this will cause `regex` to use the standard library. Currently, - disabling this feature will always result in a compilation error. It is - intended to add `alloc`-only support to regex in the future. + When enabled, this will cause `regex` to use the standard library. In terms + of APIs, `std` causes error types to implement the `std::error::Error` + trait. Enabling `std` will also result in performance optimizations, + including SIMD and faster synchronization primitives. Notably, **disabling + the `std` feature will result in the use of spin locks**. To use a regex + engine without `std` and without spin locks, you'll need to drop down to + the [`regex-automata`](https://docs.rs/regex-automata) crate. +* **logging** - + When enabled, the `log` crate is used to emit messages about regex + compilation and search strategies. This is **disabled by default**. This is + typically only useful to someone working on this crate's internals, but might + be useful if you're doing some rabbit hole performance hacking. Or if you're + just interested in the kinds of decisions being made by the regex engine. ### Performance features * **perf** - - Enables all performance related features. This feature is enabled by default - and will always cover all features that improve performance, even if more - are added in the future. + Enables all performance related features except for `perf-dfa-full`. This + feature is enabled by default is intended to cover all reasonable features + that improve performance, even if more are added in the future. * **perf-dfa** - Enables the use of a lazy DFA for matching. The lazy DFA is used to compile portions of a regex to a very fast DFA on an as-needed basis. This can result in substantial speedups, usually by an order of magnitude on large haystacks. The lazy DFA does not bring in any new dependencies, but it can make compile times longer. +* **perf-dfa-full** - + Enables the use of a full DFA for matching. Full DFAs are problematic because + they have worst case `O(2^n)` construction time. For this reason, when this + feature is enabled, full DFAs are only used for very small regexes and a + very small space bound is used during determinization to avoid the DFA + from blowing up. This feature is not enabled by default, even as part of + `perf`, because it results in fairly sizeable increases in binary size and + compilation time. It can result in faster search times, but they tend to be + more modest and limited to non-Unicode regexes. +* **perf-onepass** - + Enables the use of a one-pass DFA for extracting the positions of capture + groups. This optimization applies to a subset of certain types of NFAs and + represents the fastest engine in this crate for dealing with capture groups. +* **perf-backtrack** - + Enables the use of a bounded backtracking algorithm for extracting the + positions of capture groups. This usually sits between the slowest engine + (the PikeVM) and the fastest engine (one-pass DFA) for extracting capture + groups. It's used whenever the regex is not one-pass and is small enough. * **perf-inline** - Enables the use of aggressive inlining inside match routines. This reduces the overhead of each match. The aggressive inlining, however, increases @@ -609,193 +1264,83 @@ All features below are enabled by default. This enables using classes like `\p{gcb=Extend}`, `\p{wb=Katakana}` and `\p{sb=ATerm}`. - -# Untrusted input - -This crate can handle both untrusted regular expressions and untrusted -search text. - -Untrusted regular expressions are handled by capping the size of a compiled -regular expression. -(See [`RegexBuilder::size_limit`](struct.RegexBuilder.html#method.size_limit).) -Without this, it would be trivial for an attacker to exhaust your system's -memory with expressions like `a{100}{100}{100}`. - -Untrusted search text is allowed because the matching engine(s) in this -crate have time complexity `O(mn)` (with `m ~ regex` and `n ~ search -text`), which means there's no way to cause exponential blow-up like with -some other regular expression engines. (We pay for this by disallowing -features like arbitrary look-ahead and backreferences.) - -When a DFA is used, pathological cases with exponential state blow-up are -avoided by constructing the DFA lazily or in an "online" manner. Therefore, -at most one new state can be created for each byte of input. This satisfies -our time complexity guarantees, but can lead to memory growth -proportional to the size of the input. As a stopgap, the DFA is only -allowed to store a fixed number of states. When the limit is reached, its -states are wiped and continues on, possibly duplicating previous work. If -the limit is reached too frequently, it gives up and hands control off to -another matching engine with fixed memory requirements. -(The DFA size limit can also be tweaked. See -[`RegexBuilder::dfa_size_limit`](struct.RegexBuilder.html#method.dfa_size_limit).) +# Other crates + +This crate has two required dependencies and several optional dependencies. +This section briefly describes them with the goal of raising awareness of how +different components of this crate may be used independently. + +It is somewhat unusual for a regex engine to have dependencies, as most regex +libraries are self contained units with no dependencies other than a particular +environment's standard library. Indeed, for other similarly optimized regex +engines, most or all of the code in the dependencies of this crate would +normally just be unseparable or coupled parts of the crate itself. But since +Rust and its tooling ecosystem make the use of dependencies so easy, it made +sense to spend some effort de-coupling parts of this crate and making them +independently useful. + +We only briefly describe each crate here. + +* [`regex-lite`](https://docs.rs/regex-lite) is not a dependency of `regex`, +but rather, a standalone zero-dependency simpler version of `regex` that +prioritizes compile times and binary size. In exchange, it eschews Unicode +support and performance. Its match semantics are as identical as possible to +the `regex` crate, and for the things it supports, its APIs are identical to +the APIs in this crate. In other words, for a lot of use cases, it is a drop-in +replacement. +* [`regex-syntax`](https://docs.rs/regex-syntax) provides a regular expression +parser via `Ast` and `Hir` types. It also provides routines for extracting +literals from a pattern. Folks can use this crate to do analysis, or even to +build their own regex engine without having to worry about writing a parser. +* [`regex-automata`](https://docs.rs/regex-automata) provides the regex engines +themselves. One of the downsides of finite automata based regex engines is that +they often need multiple internal engines in order to have similar or better +performance than an unbounded backtracking engine in practice. `regex-automata` +in particular provides public APIs for a PikeVM, a bounded backtracker, a +one-pass DFA, a lazy DFA, a fully compiled DFA and a meta regex engine that +combines all them together. It also has native multi-pattern support and +provides a way to compile and serialize full DFAs such that they can be loaded +and searched in a no-std no-alloc environment. `regex-automata` itself doesn't +even have a required dependency on `regex-syntax`! +* [`memchr`](https://docs.rs/memchr) provides low level SIMD vectorized +routines for quickly finding the location of single bytes or even substrings +in a haystack. In other words, it provides fast `memchr` and `memmem` routines. +These are used by this crate in literal optimizations. +* [`aho-corasick`](https://docs.rs/aho-corasick) provides multi-substring +search. It also provides SIMD vectorized routines in the case where the number +of substrings to search for is relatively small. The `regex` crate also uses +this for literal optimizations. */ +#![no_std] #![deny(missing_docs)] #![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(doctest)] +doc_comment::doctest!("../README.md"); -// 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"); +extern crate alloc; +#[cfg(any(test, feature = "std"))] +extern crate std; -#[cfg(feature = "std")] pub use crate::error::Error; -#[cfg(feature = "std")] -pub use crate::re_builder::set_unicode::*; -#[cfg(feature = "std")] -pub use crate::re_builder::unicode::*; -#[cfg(feature = "std")] -pub use crate::re_set::unicode::*; -#[cfg(feature = "std")] -pub use crate::re_unicode::{ - escape, CaptureLocations, CaptureMatches, CaptureNames, Captures, - Locations, Match, Matches, NoExpand, Regex, Replacer, ReplacerRef, Split, - SplitN, SubCaptureMatches, -}; - -/** -Match regular expressions on arbitrary bytes. - -This module provides a nearly identical API to the one found in the -top-level of this crate. There are two important differences: - -1. Matching is done on `&[u8]` instead of `&str`. Additionally, `Vec<u8>` -is used where `String` would have been used. -2. Unicode support can be disabled even when disabling it would result in -matching invalid UTF-8 bytes. - -# Example: match null terminated string - -This shows how to find all null-terminated strings in a slice of bytes: -```rust -# use regex::bytes::Regex; -let re = Regex::new(r"(?-u)(?P<cstr>[^\x00]+)\x00").unwrap(); -let text = b"foo\x00bar\x00baz\x00"; - -// Extract all of the strings without the null terminator from each match. -// The unwrap is OK here since a match requires the `cstr` capture to match. -let cstrs: Vec<&[u8]> = - re.captures_iter(text) - .map(|c| c.name("cstr").unwrap().as_bytes()) - .collect(); -assert_eq!(vec![&b"foo"[..], &b"bar"[..], &b"baz"[..]], cstrs); -``` - -# Example: selectively enable Unicode support - -This shows how to match an arbitrary byte pattern followed by a UTF-8 encoded -string (e.g., to extract a title from a Matroska file): - -```rust -# use std::str; -# use regex::bytes::Regex; -let re = Regex::new( - r"(?-u)\x7b\xa9(?:[\x80-\xfe]|[\x40-\xff].)(?u:(.*))" -).unwrap(); -let text = b"\x12\xd0\x3b\x5f\x7b\xa9\x85\xe2\x98\x83\x80\x98\x54\x76\x68\x65"; -let caps = re.captures(text).unwrap(); - -// Notice that despite the `.*` at the end, it will only match valid UTF-8 -// because Unicode mode was enabled with the `u` flag. Without the `u` flag, -// the `.*` would match the rest of the bytes. -let mat = caps.get(1).unwrap(); -assert_eq!((7, 10), (mat.start(), mat.end())); - -// If there was a match, Unicode mode guarantees that `title` is valid UTF-8. -let title = str::from_utf8(&caps[1]).unwrap(); -assert_eq!("☃", title); -``` - -In general, if the Unicode flag is enabled in a capture group and that capture -is part of the overall match, then the capture is *guaranteed* to be valid -UTF-8. - -# Syntax - -The supported syntax is pretty much the same as the syntax for Unicode -regular expressions with a few changes that make sense for matching arbitrary -bytes: - -1. The `u` flag can be disabled even when disabling it might cause the regex to -match invalid UTF-8. When the `u` flag is disabled, the regex is said to be in -"ASCII compatible" mode. -2. In ASCII compatible mode, neither Unicode scalar values nor Unicode -character classes are allowed. -3. In ASCII compatible mode, Perl character classes (`\w`, `\d` and `\s`) -revert to their typical ASCII definition. `\w` maps to `[[:word:]]`, `\d` maps -to `[[:digit:]]` and `\s` maps to `[[:space:]]`. -4. In ASCII compatible mode, word boundaries use the ASCII compatible `\w` to -determine whether a byte is a word byte or not. -5. Hexadecimal notation can be used to specify arbitrary bytes instead of -Unicode codepoints. For example, in ASCII compatible mode, `\xFF` matches the -literal byte `\xFF`, while in Unicode mode, `\xFF` is a Unicode codepoint that -matches its UTF-8 encoding of `\xC3\xBF`. Similarly for octal notation when -enabled. -6. In ASCII compatible mode, `.` matches any *byte* except for `\n`. When the -`s` flag is additionally enabled, `.` matches any byte. - -# Performance - -In general, one should expect performance on `&[u8]` to be roughly similar to -performance on `&str`. -*/ -#[cfg(feature = "std")] -pub mod 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::*; -} +pub use crate::{builders::string::*, regex::string::*, regexset::string::*}; -mod backtrack; -mod compile; -#[cfg(feature = "perf-dfa")] -mod dfa; +mod builders; +pub mod bytes; mod error; -mod exec; -mod expand; mod find_byte; -mod input; -mod literal; #[cfg(feature = "pattern")] mod pattern; -mod pikevm; -mod pool; -mod prog; -mod re_builder; -mod re_bytes; -mod re_set; -mod re_trait; -mod re_unicode; -mod sparse; -mod utf8; - -/// The `internal` module exists to support suspicious activity, such as -/// testing different matching engines and supporting the `regex-debug` CLI -/// utility. -#[doc(hidden)] -#[cfg(feature = "std")] -pub mod internal { - 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}; +mod regex; +mod regexset; + +/// Escapes all regular expression meta characters in `pattern`. +/// +/// The string returned may be safely used as a literal in a regular +/// expression. +pub fn escape(pattern: &str) -> alloc::string::String { + regex_syntax::escape(pattern) } |