| use alloc::{boxed::Box, string::String, vec, vec::Vec}; |
| |
| use crate::{error::Error, utf8}; |
| |
| mod parse; |
| |
| /// 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) -> String { |
| let mut buf = String::new(); |
| buf.reserve(pattern.len()); |
| for ch in pattern.chars() { |
| if is_meta_character(ch) { |
| buf.push('\\'); |
| } |
| buf.push(ch); |
| } |
| buf |
| } |
| |
| /// Returns true if the given character has significance in a regex. |
| /// |
| /// Generally speaking, these are the only characters which _must_ be escaped |
| /// in order to match their literal meaning. For example, to match a literal |
| /// `|`, one could write `\|`. Sometimes escaping isn't always necessary. For |
| /// example, `-` is treated as a meta character because of its significance |
| /// for writing ranges inside of character classes, but the regex `-` will |
| /// match a literal `-` because `-` has no special meaning outside of character |
| /// classes. |
| /// |
| /// In order to determine whether a character may be escaped at all, the |
| /// [`is_escapeable_character`] routine should be used. The difference between |
| /// `is_meta_character` and `is_escapeable_character` is that the latter will |
| /// return true for some characters that are _not_ meta characters. For |
| /// example, `%` and `\%` both match a literal `%` in all contexts. In other |
| /// words, `is_escapeable_character` includes "superfluous" escapes. |
| /// |
| /// Note that the set of characters for which this function returns `true` or |
| /// `false` is fixed and won't change in a semver compatible release. (In this |
| /// case, "semver compatible release" actually refers to the `regex` crate |
| /// itself, since reducing or expanding the set of meta characters would be a |
| /// breaking change for not just `regex-syntax` but also `regex` itself.) |
| fn is_meta_character(c: char) -> bool { |
| match c { |
| '\\' | '.' | '+' | '*' | '?' | '(' | ')' | '|' | '[' | ']' | '{' |
| | '}' | '^' | '$' | '#' | '&' | '-' | '~' => true, |
| _ => false, |
| } |
| } |
| |
| /// Returns true if the given character can be escaped in a regex. |
| /// |
| /// This returns true in all cases that `is_meta_character` returns true, but |
| /// also returns true in some cases where `is_meta_character` returns false. |
| /// For example, `%` is not a meta character, but it is escapeable. That is, |
| /// `%` and `\%` both match a literal `%` in all contexts. |
| /// |
| /// The purpose of this routine is to provide knowledge about what characters |
| /// may be escaped. Namely, most regex engines permit "superfluous" escapes |
| /// where characters without any special significance may be escaped even |
| /// though there is no actual _need_ to do so. |
| /// |
| /// This will return false for some characters. For example, `e` is not |
| /// escapeable. Therefore, `\e` will either result in a parse error (which is |
| /// true today), or it could backwards compatibly evolve into a new construct |
| /// with its own meaning. Indeed, that is the purpose of banning _some_ |
| /// superfluous escapes: it provides a way to evolve the syntax in a compatible |
| /// manner. |
| fn is_escapeable_character(c: char) -> bool { |
| // Certainly escapeable if it's a meta character. |
| if is_meta_character(c) { |
| return true; |
| } |
| // Any character that isn't ASCII is definitely not escapeable. There's |
| // no real need to allow things like \☃ right? |
| if !c.is_ascii() { |
| return false; |
| } |
| // Otherwise, we basically say that everything is escapeable unless it's a |
| // letter or digit. Things like \3 are either octal (when enabled) or an |
| // error, and we should keep it that way. Otherwise, letters are reserved |
| // for adding new syntax in a backwards compatible way. |
| match c { |
| '0'..='9' | 'A'..='Z' | 'a'..='z' => false, |
| // While not currently supported, we keep these as not escapeable to |
| // give us some flexibility with respect to supporting the \< and |
| // \> word boundary assertions in the future. By rejecting them as |
| // escapeable, \< and \> will result in a parse error. Thus, we can |
| // turn them into something else in the future without it being a |
| // backwards incompatible change. |
| '<' | '>' => false, |
| _ => true, |
| } |
| } |
| |
| /// The configuration for a regex parser. |
| #[derive(Clone, Copy, Debug)] |
| pub(crate) struct Config { |
| /// The maximum number of times we're allowed to recurse. |
| /// |
| /// Note that unlike the regex-syntax parser, we actually use recursion in |
| /// this parser for simplicity. My hope is that by setting a conservative |
| /// default call limit and providing a way to configure it, that we can |
| /// keep this simplification. But if we must, we can re-work the parser to |
| /// put the call stack on the heap like regex-syntax does. |
| pub(crate) nest_limit: u32, |
| /// Various flags that control how a pattern is interpreted. |
| pub(crate) flags: Flags, |
| } |
| |
| impl Default for Config { |
| fn default() -> Config { |
| Config { nest_limit: 50, flags: Flags::default() } |
| } |
| } |
| |
| /// Various flags that control the interpretation of the pattern. |
| /// |
| /// These can be set via explicit configuration in code, or change dynamically |
| /// during parsing via inline flags. For example, `foo(?i:bar)baz` will match |
| /// `foo` and `baz` case sensitiviely and `bar` case insensitively (assuming a |
| /// default configuration). |
| #[derive(Clone, Copy, Debug, Default)] |
| pub(crate) struct Flags { |
| /// Whether to match case insensitively. |
| /// |
| /// This is the `i` flag. |
| pub(crate) case_insensitive: bool, |
| /// Whether `^` and `$` should be treated as line anchors or not. |
| /// |
| /// This is the `m` flag. |
| pub(crate) multi_line: bool, |
| /// Whether `.` should match line terminators or not. |
| /// |
| /// This is the `s` flag. |
| pub(crate) dot_matches_new_line: bool, |
| /// Whether to swap the meaning of greedy and non-greedy operators. |
| /// |
| /// This is the `U` flag. |
| pub(crate) swap_greed: bool, |
| /// Whether to enable CRLF mode. |
| /// |
| /// This is the `R` flag. |
| pub(crate) crlf: bool, |
| /// Whether to ignore whitespace. i.e., verbose mode. |
| /// |
| /// This is the `x` flag. |
| pub(crate) ignore_whitespace: bool, |
| } |
| |
| #[derive(Clone, Debug, Eq, PartialEq)] |
| pub(crate) struct Hir { |
| kind: HirKind, |
| is_start_anchored: bool, |
| is_match_empty: bool, |
| static_explicit_captures_len: Option<usize>, |
| } |
| |
| #[derive(Clone, Debug, Eq, PartialEq)] |
| pub(crate) enum HirKind { |
| Empty, |
| Char(char), |
| Class(Class), |
| Look(Look), |
| Repetition(Repetition), |
| Capture(Capture), |
| Concat(Vec<Hir>), |
| Alternation(Vec<Hir>), |
| } |
| |
| impl Hir { |
| /// Parses the given pattern string with the given configuration into a |
| /// structured representation. If the pattern is invalid, then an error |
| /// is returned. |
| pub(crate) fn parse(config: Config, pattern: &str) -> Result<Hir, Error> { |
| self::parse::Parser::new(config, pattern).parse() |
| } |
| |
| /// Returns the underlying kind of this high-level intermediate |
| /// representation. |
| /// |
| /// Note that there is explicitly no way to build an `Hir` directly from |
| /// an `HirKind`. If you need to do that, then you must do case analysis |
| /// on the `HirKind` and call the appropriate smart constructor on `Hir`. |
| pub(crate) fn kind(&self) -> &HirKind { |
| &self.kind |
| } |
| |
| /// Returns true if and only if this Hir expression can only match at the |
| /// beginning of a haystack. |
| pub(crate) fn is_start_anchored(&self) -> bool { |
| self.is_start_anchored |
| } |
| |
| /// Returns true if and only if this Hir expression can match the empty |
| /// string. |
| pub(crate) fn is_match_empty(&self) -> bool { |
| self.is_match_empty |
| } |
| |
| /// If the pattern always reports the same number of matching capture groups |
| /// for every match, then this returns the number of those groups. This |
| /// doesn't include the implicit group found in every pattern. |
| pub(crate) fn static_explicit_captures_len(&self) -> Option<usize> { |
| self.static_explicit_captures_len |
| } |
| |
| fn fail() -> Hir { |
| let kind = HirKind::Class(Class { ranges: vec![] }); |
| Hir { |
| kind, |
| is_start_anchored: false, |
| is_match_empty: false, |
| static_explicit_captures_len: Some(0), |
| } |
| } |
| |
| fn empty() -> Hir { |
| let kind = HirKind::Empty; |
| Hir { |
| kind, |
| is_start_anchored: false, |
| is_match_empty: true, |
| static_explicit_captures_len: Some(0), |
| } |
| } |
| |
| fn char(ch: char) -> Hir { |
| let kind = HirKind::Char(ch); |
| Hir { |
| kind, |
| is_start_anchored: false, |
| is_match_empty: false, |
| static_explicit_captures_len: Some(0), |
| } |
| } |
| |
| fn class(class: Class) -> Hir { |
| let kind = HirKind::Class(class); |
| Hir { |
| kind, |
| is_start_anchored: false, |
| is_match_empty: false, |
| static_explicit_captures_len: Some(0), |
| } |
| } |
| |
| fn look(look: Look) -> Hir { |
| let kind = HirKind::Look(look); |
| Hir { |
| kind, |
| is_start_anchored: matches!(look, Look::Start), |
| is_match_empty: true, |
| static_explicit_captures_len: Some(0), |
| } |
| } |
| |
| fn repetition(rep: Repetition) -> Hir { |
| if rep.min == 0 && rep.max == Some(0) { |
| return Hir::empty(); |
| } else if rep.min == 1 && rep.max == Some(1) { |
| return *rep.sub; |
| } |
| let is_start_anchored = rep.min > 0 && rep.sub.is_start_anchored; |
| let is_match_empty = rep.min == 0 || rep.sub.is_match_empty; |
| let mut static_explicit_captures_len = |
| rep.sub.static_explicit_captures_len; |
| // If the static captures len of the sub-expression is not known or |
| // is greater than zero, then it automatically propagates to the |
| // repetition, regardless of the repetition. Otherwise, it might |
| // change, but only when the repetition can match 0 times. |
| if rep.min == 0 |
| && static_explicit_captures_len.map_or(false, |len| len > 0) |
| { |
| // If we require a match 0 times, then our captures len is |
| // guaranteed to be zero. Otherwise, if we *can* match the empty |
| // string, then it's impossible to know how many captures will be |
| // in the resulting match. |
| if rep.max == Some(0) { |
| static_explicit_captures_len = Some(0); |
| } else { |
| static_explicit_captures_len = None; |
| } |
| } |
| Hir { |
| kind: HirKind::Repetition(rep), |
| is_start_anchored, |
| is_match_empty, |
| static_explicit_captures_len, |
| } |
| } |
| |
| fn capture(cap: Capture) -> Hir { |
| let is_start_anchored = cap.sub.is_start_anchored; |
| let is_match_empty = cap.sub.is_match_empty; |
| let static_explicit_captures_len = cap |
| .sub |
| .static_explicit_captures_len |
| .map(|len| len.saturating_add(1)); |
| let kind = HirKind::Capture(cap); |
| Hir { |
| kind, |
| is_start_anchored, |
| is_match_empty, |
| static_explicit_captures_len, |
| } |
| } |
| |
| fn concat(mut subs: Vec<Hir>) -> Hir { |
| if subs.is_empty() { |
| Hir::empty() |
| } else if subs.len() == 1 { |
| subs.pop().unwrap() |
| } else { |
| let is_start_anchored = subs[0].is_start_anchored; |
| let mut is_match_empty = true; |
| let mut static_explicit_captures_len = Some(0usize); |
| for sub in subs.iter() { |
| is_match_empty = is_match_empty && sub.is_match_empty; |
| static_explicit_captures_len = static_explicit_captures_len |
| .and_then(|len1| { |
| Some((len1, sub.static_explicit_captures_len?)) |
| }) |
| .and_then(|(len1, len2)| Some(len1.saturating_add(len2))); |
| } |
| Hir { |
| kind: HirKind::Concat(subs), |
| is_start_anchored, |
| is_match_empty, |
| static_explicit_captures_len, |
| } |
| } |
| } |
| |
| fn alternation(mut subs: Vec<Hir>) -> Hir { |
| if subs.is_empty() { |
| Hir::fail() |
| } else if subs.len() == 1 { |
| subs.pop().unwrap() |
| } else { |
| let mut it = subs.iter().peekable(); |
| let mut is_start_anchored = |
| it.peek().map_or(false, |sub| sub.is_start_anchored); |
| let mut is_match_empty = |
| it.peek().map_or(false, |sub| sub.is_match_empty); |
| let mut static_explicit_captures_len = |
| it.peek().and_then(|sub| sub.static_explicit_captures_len); |
| for sub in it { |
| is_start_anchored = is_start_anchored && sub.is_start_anchored; |
| is_match_empty = is_match_empty || sub.is_match_empty; |
| if static_explicit_captures_len |
| != sub.static_explicit_captures_len |
| { |
| static_explicit_captures_len = None; |
| } |
| } |
| Hir { |
| kind: HirKind::Alternation(subs), |
| is_start_anchored, |
| is_match_empty, |
| static_explicit_captures_len, |
| } |
| } |
| } |
| } |
| |
| impl HirKind { |
| /// Returns a slice of this kind's sub-expressions, if any. |
| fn subs(&self) -> &[Hir] { |
| use core::slice::from_ref; |
| |
| match *self { |
| HirKind::Empty |
| | HirKind::Char(_) |
| | HirKind::Class(_) |
| | HirKind::Look(_) => &[], |
| HirKind::Repetition(Repetition { ref sub, .. }) => from_ref(sub), |
| HirKind::Capture(Capture { ref sub, .. }) => from_ref(sub), |
| HirKind::Concat(ref subs) => subs, |
| HirKind::Alternation(ref subs) => subs, |
| } |
| } |
| } |
| |
| #[derive(Clone, Debug, Eq, PartialEq)] |
| pub(crate) struct Class { |
| pub(crate) ranges: Vec<ClassRange>, |
| } |
| |
| impl Class { |
| /// Create a new class from the given ranges. The ranges may be provided |
| /// in any order or may even overlap. They will be automatically |
| /// canonicalized. |
| fn new<I: IntoIterator<Item = ClassRange>>(ranges: I) -> Class { |
| let mut class = Class { ranges: ranges.into_iter().collect() }; |
| class.canonicalize(); |
| class |
| } |
| |
| /// Expand this class such that it matches the ASCII codepoints in this set |
| /// case insensitively. |
| fn ascii_case_fold(&mut self) { |
| let len = self.ranges.len(); |
| for i in 0..len { |
| if let Some(folded) = self.ranges[i].ascii_case_fold() { |
| self.ranges.push(folded); |
| } |
| } |
| self.canonicalize(); |
| } |
| |
| /// Negate this set. |
| /// |
| /// For all `x` where `x` is any element, if `x` was in this set, then it |
| /// will not be in this set after negation. |
| fn negate(&mut self) { |
| const MIN: char = '\x00'; |
| const MAX: char = char::MAX; |
| |
| if self.ranges.is_empty() { |
| self.ranges.push(ClassRange { start: MIN, end: MAX }); |
| return; |
| } |
| |
| // There should be a way to do this in-place with constant memory, |
| // but I couldn't figure out a simple way to do it. So just append |
| // the negation to the end of this range, and then drain it before |
| // we're done. |
| let drain_end = self.ranges.len(); |
| |
| // If our class doesn't start the minimum possible char, then negation |
| // needs to include all codepoints up to the minimum in this set. |
| if self.ranges[0].start > MIN { |
| self.ranges.push(ClassRange { |
| start: MIN, |
| // OK because we know it's bigger than MIN. |
| end: prev_char(self.ranges[0].start).unwrap(), |
| }); |
| } |
| for i in 1..drain_end { |
| // let lower = self.ranges[i - 1].upper().increment(); |
| // let upper = self.ranges[i].lower().decrement(); |
| // self.ranges.push(I::create(lower, upper)); |
| self.ranges.push(ClassRange { |
| // OK because we know i-1 is never the last range and therefore |
| // there must be a range greater than it. It therefore follows |
| // that 'end' can never be char::MAX, and thus there must be |
| // a next char. |
| start: next_char(self.ranges[i - 1].end).unwrap(), |
| // Since 'i' is guaranteed to never be the first range, it |
| // follows that there is always a range before this and thus |
| // 'start' can never be '\x00'. Thus, there must be a previous |
| // char. |
| end: prev_char(self.ranges[i].start).unwrap(), |
| }); |
| } |
| if self.ranges[drain_end - 1].end < MAX { |
| // let lower = self.ranges[drain_end - 1].upper().increment(); |
| // self.ranges.push(I::create(lower, I::Bound::max_value())); |
| self.ranges.push(ClassRange { |
| // OK because we know 'end' is less than char::MAX, and thus |
| // there is a next char. |
| start: next_char(self.ranges[drain_end - 1].end).unwrap(), |
| end: MAX, |
| }); |
| } |
| self.ranges.drain(..drain_end); |
| // We don't need to canonicalize because we processed the ranges above |
| // in canonical order and the new ranges we added based on those are |
| // also necessarily in canonical order. |
| } |
| |
| /// Converts this set into a canonical ordering. |
| fn canonicalize(&mut self) { |
| if self.is_canonical() { |
| return; |
| } |
| self.ranges.sort(); |
| assert!(!self.ranges.is_empty()); |
| |
| // Is there a way to do this in-place with constant memory? I couldn't |
| // figure out a way to do it. So just append the canonicalization to |
| // the end of this range, and then drain it before we're done. |
| let drain_end = self.ranges.len(); |
| for oldi in 0..drain_end { |
| // If we've added at least one new range, then check if we can |
| // merge this range in the previously added range. |
| if self.ranges.len() > drain_end { |
| let (last, rest) = self.ranges.split_last_mut().unwrap(); |
| if let Some(union) = last.union(&rest[oldi]) { |
| *last = union; |
| continue; |
| } |
| } |
| self.ranges.push(self.ranges[oldi]); |
| } |
| self.ranges.drain(..drain_end); |
| } |
| |
| /// Returns true if and only if this class is in a canonical ordering. |
| fn is_canonical(&self) -> bool { |
| for pair in self.ranges.windows(2) { |
| if pair[0] >= pair[1] { |
| return false; |
| } |
| if pair[0].is_contiguous(&pair[1]) { |
| return false; |
| } |
| } |
| true |
| } |
| } |
| |
| #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)] |
| pub(crate) struct ClassRange { |
| pub(crate) start: char, |
| pub(crate) end: char, |
| } |
| |
| impl ClassRange { |
| /// Apply simple case folding to this byte range. Only ASCII case mappings |
| /// (for A-Za-z) are applied. |
| /// |
| /// Additional ranges are appended to the given vector. Canonical ordering |
| /// is *not* maintained in the given vector. |
| fn ascii_case_fold(&self) -> Option<ClassRange> { |
| if !(ClassRange { start: 'a', end: 'z' }).is_intersection_empty(self) { |
| let start = core::cmp::max(self.start, 'a'); |
| let end = core::cmp::min(self.end, 'z'); |
| return Some(ClassRange { |
| start: char::try_from(u32::from(start) - 32).unwrap(), |
| end: char::try_from(u32::from(end) - 32).unwrap(), |
| }); |
| } |
| if !(ClassRange { start: 'A', end: 'Z' }).is_intersection_empty(self) { |
| let start = core::cmp::max(self.start, 'A'); |
| let end = core::cmp::min(self.end, 'Z'); |
| return Some(ClassRange { |
| start: char::try_from(u32::from(start) + 32).unwrap(), |
| end: char::try_from(u32::from(end) + 32).unwrap(), |
| }); |
| } |
| None |
| } |
| |
| /// Union the given overlapping range into this range. |
| /// |
| /// If the two ranges aren't contiguous, then this returns `None`. |
| fn union(&self, other: &ClassRange) -> Option<ClassRange> { |
| if !self.is_contiguous(other) { |
| return None; |
| } |
| let start = core::cmp::min(self.start, other.start); |
| let end = core::cmp::max(self.end, other.end); |
| Some(ClassRange { start, end }) |
| } |
| |
| /// Returns true if and only if the two ranges are contiguous. Two ranges |
| /// are contiguous if and only if the ranges are either overlapping or |
| /// adjacent. |
| fn is_contiguous(&self, other: &ClassRange) -> bool { |
| let (s1, e1) = (u32::from(self.start), u32::from(self.end)); |
| let (s2, e2) = (u32::from(other.start), u32::from(other.end)); |
| core::cmp::max(s1, s2) <= core::cmp::min(e1, e2).saturating_add(1) |
| } |
| |
| /// Returns true if and only if the intersection of this range and the |
| /// other range is empty. |
| fn is_intersection_empty(&self, other: &ClassRange) -> bool { |
| let (s1, e1) = (self.start, self.end); |
| let (s2, e2) = (other.start, other.end); |
| core::cmp::max(s1, s2) > core::cmp::min(e1, e2) |
| } |
| } |
| |
| /// The high-level intermediate representation for a look-around assertion. |
| /// |
| /// An assertion match is always zero-length. Also called an "empty match." |
| #[derive(Clone, Copy, Debug, Eq, PartialEq)] |
| pub(crate) enum Look { |
| /// Match the beginning of text. Specifically, this matches at the starting |
| /// position of the input. |
| Start = 1 << 0, |
| /// Match the end of text. Specifically, this matches at the ending |
| /// position of the input. |
| End = 1 << 1, |
| /// Match the beginning of a line or the beginning of text. Specifically, |
| /// this matches at the starting position of the input, or at the position |
| /// immediately following a `\n` character. |
| StartLF = 1 << 2, |
| /// Match the end of a line or the end of text. Specifically, this matches |
| /// at the end position of the input, or at the position immediately |
| /// preceding a `\n` character. |
| EndLF = 1 << 3, |
| /// Match the beginning of a line or the beginning of text. Specifically, |
| /// this matches at the starting position of the input, or at the position |
| /// immediately following either a `\r` or `\n` character, but never after |
| /// a `\r` when a `\n` follows. |
| StartCRLF = 1 << 4, |
| /// Match the end of a line or the end of text. Specifically, this matches |
| /// at the end position of the input, or at the position immediately |
| /// preceding a `\r` or `\n` character, but never before a `\n` when a `\r` |
| /// precedes it. |
| EndCRLF = 1 << 5, |
| /// Match an ASCII-only word boundary. That is, this matches a position |
| /// where the left adjacent character and right adjacent character |
| /// correspond to a word and non-word or a non-word and word character. |
| Word = 1 << 6, |
| /// Match an ASCII-only negation of a word boundary. |
| WordNegate = 1 << 7, |
| /// Match the start of an ASCII-only word boundary. That is, this matches a |
| /// position at either the beginning of the haystack or where the previous |
| /// character is not a word character and the following character is a word |
| /// character. |
| WordStart = 1 << 8, |
| /// Match the end of an ASCII-only word boundary. That is, this matches |
| /// a position at either the end of the haystack or where the previous |
| /// character is a word character and the following character is not a word |
| /// character. |
| WordEnd = 1 << 9, |
| /// Match the start half of an ASCII-only word boundary. That is, this |
| /// matches a position at either the beginning of the haystack or where the |
| /// previous character is not a word character. |
| WordStartHalf = 1 << 10, |
| /// Match the end half of an ASCII-only word boundary. That is, this |
| /// matches a position at either the end of the haystack or where the |
| /// following character is not a word character. |
| WordEndHalf = 1 << 11, |
| } |
| |
| impl Look { |
| /// Returns true if the given position in the given haystack matches this |
| /// look-around assertion. |
| pub(crate) fn is_match(&self, haystack: &[u8], at: usize) -> bool { |
| use self::Look::*; |
| |
| match *self { |
| Start => at == 0, |
| End => at == haystack.len(), |
| StartLF => at == 0 || haystack[at - 1] == b'\n', |
| EndLF => at == haystack.len() || haystack[at] == b'\n', |
| StartCRLF => { |
| at == 0 |
| || haystack[at - 1] == b'\n' |
| || (haystack[at - 1] == b'\r' |
| && (at >= haystack.len() || haystack[at] != b'\n')) |
| } |
| EndCRLF => { |
| at == haystack.len() |
| || haystack[at] == b'\r' |
| || (haystack[at] == b'\n' |
| && (at == 0 || haystack[at - 1] != b'\r')) |
| } |
| Word => { |
| let word_before = |
| at > 0 && utf8::is_word_byte(haystack[at - 1]); |
| let word_after = |
| at < haystack.len() && utf8::is_word_byte(haystack[at]); |
| word_before != word_after |
| } |
| WordNegate => { |
| let word_before = |
| at > 0 && utf8::is_word_byte(haystack[at - 1]); |
| let word_after = |
| at < haystack.len() && utf8::is_word_byte(haystack[at]); |
| word_before == word_after |
| } |
| WordStart => { |
| let word_before = |
| at > 0 && utf8::is_word_byte(haystack[at - 1]); |
| let word_after = |
| at < haystack.len() && utf8::is_word_byte(haystack[at]); |
| !word_before && word_after |
| } |
| WordEnd => { |
| let word_before = |
| at > 0 && utf8::is_word_byte(haystack[at - 1]); |
| let word_after = |
| at < haystack.len() && utf8::is_word_byte(haystack[at]); |
| word_before && !word_after |
| } |
| WordStartHalf => { |
| let word_before = |
| at > 0 && utf8::is_word_byte(haystack[at - 1]); |
| !word_before |
| } |
| WordEndHalf => { |
| let word_after = |
| at < haystack.len() && utf8::is_word_byte(haystack[at]); |
| !word_after |
| } |
| } |
| } |
| } |
| |
| /// The high-level intermediate representation of a repetition operator. |
| /// |
| /// A repetition operator permits the repetition of an arbitrary |
| /// sub-expression. |
| #[derive(Clone, Debug, Eq, PartialEq)] |
| pub(crate) struct Repetition { |
| /// The minimum range of the repetition. |
| /// |
| /// Note that special cases like `?`, `+` and `*` all get translated into |
| /// the ranges `{0,1}`, `{1,}` and `{0,}`, respectively. |
| /// |
| /// When `min` is zero, this expression can match the empty string |
| /// regardless of what its sub-expression is. |
| pub(crate) min: u32, |
| /// The maximum range of the repetition. |
| /// |
| /// Note that when `max` is `None`, `min` acts as a lower bound but where |
| /// there is no upper bound. For something like `x{5}` where the min and |
| /// max are equivalent, `min` will be set to `5` and `max` will be set to |
| /// `Some(5)`. |
| pub(crate) max: Option<u32>, |
| /// Whether this repetition operator is greedy or not. A greedy operator |
| /// will match as much as it can. A non-greedy operator will match as |
| /// little as it can. |
| /// |
| /// Typically, operators are greedy by default and are only non-greedy when |
| /// a `?` suffix is used, e.g., `(expr)*` is greedy while `(expr)*?` is |
| /// not. However, this can be inverted via the `U` "ungreedy" flag. |
| pub(crate) greedy: bool, |
| /// The expression being repeated. |
| pub(crate) sub: Box<Hir>, |
| } |
| |
| /// The high-level intermediate representation for a capturing group. |
| /// |
| /// A capturing group always has an index and a child expression. It may |
| /// also have a name associated with it (e.g., `(?P<foo>\w)`), but it's not |
| /// necessary. |
| /// |
| /// Note that there is no explicit representation of a non-capturing group |
| /// in a `Hir`. Instead, non-capturing grouping is handled automatically by |
| /// the recursive structure of the `Hir` itself. |
| #[derive(Clone, Debug, Eq, PartialEq)] |
| pub(crate) struct Capture { |
| /// The capture index of the capture. |
| pub(crate) index: u32, |
| /// The name of the capture, if it exists. |
| pub(crate) name: Option<Box<str>>, |
| /// The expression inside the capturing group, which may be empty. |
| pub(crate) sub: Box<Hir>, |
| } |
| |
| fn next_char(ch: char) -> Option<char> { |
| // Skip over the surrogate range. |
| if ch == '\u{D7FF}' { |
| return Some('\u{E000}'); |
| } |
| // OK because char::MAX < u32::MAX and we handle U+D7FF above. |
| char::from_u32(u32::from(ch).checked_add(1).unwrap()) |
| } |
| |
| fn prev_char(ch: char) -> Option<char> { |
| // Skip over the surrogate range. |
| if ch == '\u{E000}' { |
| return Some('\u{D7FF}'); |
| } |
| // OK because subtracting 1 from any valid scalar value other than 0 |
| // and U+E000 yields a valid scalar value. |
| Some(char::from_u32(u32::from(ch).checked_sub(1)?).unwrap()) |
| } |
| |
| impl Drop for Hir { |
| fn drop(&mut self) { |
| use core::mem; |
| |
| match *self.kind() { |
| HirKind::Empty |
| | HirKind::Char(_) |
| | HirKind::Class(_) |
| | HirKind::Look(_) => return, |
| HirKind::Capture(ref x) if x.sub.kind.subs().is_empty() => return, |
| HirKind::Repetition(ref x) if x.sub.kind.subs().is_empty() => { |
| return |
| } |
| HirKind::Concat(ref x) if x.is_empty() => return, |
| HirKind::Alternation(ref x) if x.is_empty() => return, |
| _ => {} |
| } |
| |
| let mut stack = vec![mem::replace(self, Hir::empty())]; |
| while let Some(mut expr) = stack.pop() { |
| match expr.kind { |
| HirKind::Empty |
| | HirKind::Char(_) |
| | HirKind::Class(_) |
| | HirKind::Look(_) => {} |
| HirKind::Capture(ref mut x) => { |
| stack.push(mem::replace(&mut x.sub, Hir::empty())); |
| } |
| HirKind::Repetition(ref mut x) => { |
| stack.push(mem::replace(&mut x.sub, Hir::empty())); |
| } |
| HirKind::Concat(ref mut x) => { |
| stack.extend(x.drain(..)); |
| } |
| HirKind::Alternation(ref mut x) => { |
| stack.extend(x.drain(..)); |
| } |
| } |
| } |
| } |
| } |
