/// The span offsets of capturing groups after a match has been found. /// /// This type represents the output of regex engines that can report the /// offsets at which capturing groups matches or "submatches" occur. For /// example, the [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM). When a match /// occurs, it will at minimum contain the [`PatternID`] of the pattern that /// matched. Depending upon how it was constructed, it may also contain the /// start/end offsets of the entire match of the pattern and the start/end /// offsets of each capturing group that participated in the match. /// /// Values of this type are always created for a specific [`GroupInfo`]. It is /// unspecified behavior to use a `Captures` value in a search with any regex /// engine that has a different `GroupInfo` than the one the `Captures` were /// created with. /// /// # Constructors /// /// There are three constructors for this type that control what kind of /// information is available upon a match: /// /// * [`Captures::all`]: Will store overall pattern match offsets in addition /// to the offsets of capturing groups that participated in the match. /// * [`Captures::matches`]: Will store only the overall pattern /// match offsets. The offsets of capturing groups (even ones that participated /// in the match) are not available. /// * [`Captures::empty`]: Will only store the pattern ID that matched. No /// match offsets are available at all. /// /// If you aren't sure which to choose, then pick the first one. The first one /// is what convenience routines like, /// [`PikeVM::create_captures`](crate::nfa::thompson::pikevm::PikeVM::create_captures), /// will use automatically. /// /// The main difference between these choices is performance. Namely, if you /// ask for _less_ information, then the execution of regex search may be able /// to run more quickly. /// /// # Notes /// /// It is worth pointing out that this type is not coupled to any one specific /// regex engine. Instead, its coupling is with [`GroupInfo`], which is the /// thing that is responsible for mapping capturing groups to "slot" offsets. /// Slot offsets are indices into a single sequence of memory at which matching /// haystack offsets for the corresponding group are written by regex engines. /// /// # Example /// /// This example shows how to parse a simple date and extract the components of /// the date via capturing groups: /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span}; /// /// let re = PikeVM::new(r"^([0-9]{4})-([0-9]{2})-([0-9]{2})$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "2010-03-14", &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(Span::from(0..4)), caps.get_group(1)); /// assert_eq!(Some(Span::from(5..7)), caps.get_group(2)); /// assert_eq!(Some(Span::from(8..10)), caps.get_group(3)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// # Example: named capturing groups /// /// This example is like the one above, but leverages the ability to name /// capturing groups in order to make the code a bit clearer: /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span}; /// /// let re = PikeVM::new(r"^(?P<y>[0-9]{4})-(?P<m>[0-9]{2})-(?P<d>[0-9]{2})$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "2010-03-14", &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(Span::from(0..4)), caps.get_group_by_name("y")); /// assert_eq!(Some(Span::from(5..7)), caps.get_group_by_name("m")); /// assert_eq!(Some(Span::from(8..10)), caps.get_group_by_name("d")); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[derive(Clone)] pubstruct Captures { /// The group info that these capture groups are coupled to. This is what /// gives the "convenience" of the `Captures` API. Namely, it provides the /// slot mapping and the name|-->index mapping for capture lookups by name.
group_info: GroupInfo, /// The ID of the pattern that matched. Regex engines must set this to /// None when no match occurs.
pid: Option<PatternID>, /// The slot values, i.e., submatch offsets. /// /// In theory, the smallest sequence of slots would be something like /// `max(groups(pattern) for pattern in regex) * 2`, but instead, we use /// `sum(groups(pattern) for pattern in regex) * 2`. Why? /// /// Well, the former could be used in theory, because we don't generally /// have any overlapping APIs that involve capturing groups. Therefore, /// there's technically never any need to have slots set for multiple /// patterns. However, this might change some day, in which case, we would /// need to have slots available. /// /// The other reason is that during the execution of some regex engines, /// there exists a point in time where multiple slots for different /// patterns may be written to before knowing which pattern has matched. /// Therefore, the regex engines themselves, in order to support multiple /// patterns correctly, must have all slots available. If `Captures` /// doesn't have all slots available, then regex engines can't write /// directly into the caller provided `Captures` and must instead write /// into some other storage and then copy the slots involved in the match /// at the end of the search. /// /// So overall, at least as of the time of writing, it seems like the path /// of least resistance is to just require allocating all possible slots /// instead of the conceptual minimum. Another way to justify this is that /// the most common case is a single pattern, in which case, there is no /// inefficiency here since the 'max' and 'sum' calculations above are /// equivalent in that case. /// /// N.B. The mapping from group index to slot is maintained by `GroupInfo` /// and is considered an API guarantee. See `GroupInfo` for more details on /// that mapping. /// /// N.B. `Option<NonMaxUsize>` has the same size as a `usize`.
slots: Vec<Option<NonMaxUsize>>,
}
impl Captures { /// Create new storage for the offsets of all matching capturing groups. /// /// This routine provides the most information for matches---namely, the /// spans of matching capturing groups---but also requires the regex search /// routines to do the most work. /// /// It is unspecified behavior to use the returned `Captures` value in a /// search with a `GroupInfo` other than the one that is provided to this /// constructor. /// /// # Example /// /// This example shows that all capturing groups---but only ones that /// participated in a match---are available to query after a match has /// been found: /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::captures::Captures, /// Span, Match, /// }; /// /// let re = PikeVM::new( /// r"^(?:(?P<lower>[a-z]+)|(?P<upper>[A-Z]+))(?P<digits>[0-9]+)$", /// )?; /// let mut cache = re.create_cache(); /// let mut caps = Captures::all(re.get_nfa().group_info().clone()); /// /// re.captures(&mut cache, "ABC123", &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(Match::must(0, 0..6)), caps.get_match()); /// // The 'lower' group didn't match, so it won't have any offsets. /// assert_eq!(None, caps.get_group_by_name("lower")); /// assert_eq!(Some(Span::from(0..3)), caps.get_group_by_name("upper")); /// assert_eq!(Some(Span::from(3..6)), caps.get_group_by_name("digits")); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn all(group_info: GroupInfo) -> Captures { let slots = group_info.slot_len();
Captures { group_info, pid: None, slots: vec![None; slots] }
}
/// Create new storage for only the full match spans of a pattern. This /// does not include any capturing group offsets. /// /// It is unspecified behavior to use the returned `Captures` value in a /// search with a `GroupInfo` other than the one that is provided to this /// constructor. /// /// # Example /// /// This example shows that only overall match offsets are reported when /// this constructor is used. Accessing any capturing groups other than /// the 0th will always return `None`. /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::captures::Captures, /// Match, /// }; /// /// let re = PikeVM::new( /// r"^(?:(?P<lower>[a-z]+)|(?P<upper>[A-Z]+))(?P<digits>[0-9]+)$", /// )?; /// let mut cache = re.create_cache(); /// let mut caps = Captures::matches(re.get_nfa().group_info().clone()); /// /// re.captures(&mut cache, "ABC123", &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(Match::must(0, 0..6)), caps.get_match()); /// // We didn't ask for capturing group offsets, so they aren't available. /// assert_eq!(None, caps.get_group_by_name("lower")); /// assert_eq!(None, caps.get_group_by_name("upper")); /// assert_eq!(None, caps.get_group_by_name("digits")); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn matches(group_info: GroupInfo) -> Captures { // This is OK because we know there are at least this many slots, // and GroupInfo construction guarantees that the number of slots fits // into a usize. let slots = group_info.pattern_len().checked_mul(2).unwrap();
Captures { group_info, pid: None, slots: vec![None; slots] }
}
/// Create new storage for only tracking which pattern matched. No offsets /// are stored at all. /// /// It is unspecified behavior to use the returned `Captures` value in a /// search with a `GroupInfo` other than the one that is provided to this /// constructor. /// /// # Example /// /// This example shows that only the pattern that matched can be accessed /// from a `Captures` value created via this constructor. /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::captures::Captures, /// PatternID, /// }; /// /// let re = PikeVM::new_many(&[r"[a-z]+", r"[A-Z]+"])?; /// let mut cache = re.create_cache(); /// let mut caps = Captures::empty(re.get_nfa().group_info().clone()); /// /// re.captures(&mut cache, "aABCz", &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(PatternID::must(0)), caps.pattern()); /// // We didn't ask for any offsets, so they aren't available. /// assert_eq!(None, caps.get_match()); /// /// re.captures(&mut cache, &"aABCz"[1..], &mut caps); /// assert!(caps.is_match()); /// assert_eq!(Some(PatternID::must(1)), caps.pattern()); /// // We didn't ask for any offsets, so they aren't available. /// assert_eq!(None, caps.get_match()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn empty(group_info: GroupInfo) -> Captures {
Captures { group_info, pid: None, slots: vec![] }
}
/// Returns true if and only if this capturing group represents a match. /// /// This is a convenience routine for `caps.pattern().is_some()`. /// /// # Example /// /// When using the PikeVM (for example), the lightest weight way of /// detecting whether a match exists is to create capturing groups that /// only track the ID of the pattern that match (if any): /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::captures::Captures, /// }; /// /// let re = PikeVM::new(r"[a-z]+")?; /// let mut cache = re.create_cache(); /// let mut caps = Captures::empty(re.get_nfa().group_info().clone()); /// /// re.captures(&mut cache, "aABCz", &mut caps); /// assert!(caps.is_match()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn is_match(&self) -> bool { self.pid.is_some()
}
/// Returns the identifier of the pattern that matched when this /// capturing group represents a match. If no match was found, then this /// always returns `None`. /// /// This returns a pattern ID in precisely the cases in which `is_match` /// returns `true`. Similarly, the pattern ID returned is always the /// same pattern ID found in the `Match` returned by `get_match`. /// /// # Example /// /// When using the PikeVM (for example), the lightest weight way of /// detecting which pattern matched is to create capturing groups that only /// track the ID of the pattern that match (if any): /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::captures::Captures, /// PatternID, /// }; /// /// let re = PikeVM::new_many(&[r"[a-z]+", r"[A-Z]+"])?; /// let mut cache = re.create_cache(); /// let mut caps = Captures::empty(re.get_nfa().group_info().clone()); /// /// re.captures(&mut cache, "ABC", &mut caps); /// assert_eq!(Some(PatternID::must(1)), caps.pattern()); /// // Recall that offsets are only available when using a non-empty /// // Captures value. So even though a match occurred, this returns None! /// assert_eq!(None, caps.get_match()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn pattern(&self) -> Option<PatternID> { self.pid
}
/// Returns the pattern ID and the span of the match, if one occurred. /// /// This always returns `None` when `Captures` was created with /// [`Captures::empty`], even if a match was found. /// /// If this routine returns a non-`None` value, then `is_match` is /// guaranteed to return `true` and `pattern` is also guaranteed to return /// a non-`None` value. /// /// # Example /// /// This example shows how to get the full match from a search: /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Match}; /// /// let re = PikeVM::new_many(&[r"[a-z]+", r"[A-Z]+"])?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "ABC", &mut caps); /// assert_eq!(Some(Match::must(1, 0..3)), caps.get_match()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn get_match(&self) -> Option<Match> {
Some(Match::new(self.pattern()?, self.get_group(0)?))
}
/// Returns the span of a capturing group match corresponding to the group /// index given, only if both the overall pattern matched and the capturing /// group participated in that match. /// /// This returns `None` if `index` is invalid. `index` is valid if and only /// if it's less than [`Captures::group_len`] for the matching pattern. /// /// This always returns `None` when `Captures` was created with /// [`Captures::empty`], even if a match was found. This also always /// returns `None` for any `index > 0` when `Captures` was created with /// [`Captures::matches`]. /// /// If this routine returns a non-`None` value, then `is_match` is /// guaranteed to return `true`, `pattern` is guaranteed to return a /// non-`None` value and `get_match` is guaranteed to return a non-`None` /// value. /// /// By convention, the 0th capture group will always return the same /// span as the span returned by `get_match`. This is because the 0th /// capture group always corresponds to the entirety of the pattern's /// match. (It is similarly always unnamed because it is implicit.) This /// isn't necessarily true of all regex engines. For example, one can /// hand-compile a [`thompson::NFA`](crate::nfa::thompson::NFA) via a /// [`thompson::Builder`](crate::nfa::thompson::Builder), which isn't /// technically forced to make the 0th capturing group always correspond to /// the entire match. /// /// # Example /// /// This example shows how to get the capturing groups, by index, from a /// match: /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// # if !cfg!(target_pointer_width = "64") { return Ok(()); } // see #1039 /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span, Match}; /// /// let re = PikeVM::new(r"^(?P<first>\pL+)\s+(?P<last>\pL+)$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Bruce Springsteen", &mut caps); /// assert_eq!(Some(Match::must(0, 0..17)), caps.get_match()); /// assert_eq!(Some(Span::from(0..5)), caps.get_group(1)); /// assert_eq!(Some(Span::from(6..17)), caps.get_group(2)); /// // Looking for a non-existent capturing group will return None: /// assert_eq!(None, caps.get_group(3)); /// assert_eq!(None, caps.get_group(9944060567225171988)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn get_group(&self, index: usize) -> Option<Span> { let pid = self.pattern()?; // There's a little bit of work needed to map captures to slots in the // fully general case. But in the overwhelming common case of a single // pattern, we can just do some simple arithmetic. let (slot_start, slot_end) = ifself.group_info().pattern_len() == 1 {
(index.checked_mul(2)?, index.checked_mul(2)?.checked_add(1)?)
} else { self.group_info().slots(pid, index)?
}; let start = self.slots.get(slot_start).copied()??; let end = self.slots.get(slot_end).copied()??;
Some(Span { start: start.get(), end: end.get() })
}
/// Returns the span of a capturing group match corresponding to the group /// name given, only if both the overall pattern matched and the capturing /// group participated in that match. /// /// This returns `None` if `name` does not correspond to a valid capturing /// group for the pattern that matched. /// /// This always returns `None` when `Captures` was created with /// [`Captures::empty`], even if a match was found. This also always /// returns `None` for any `index > 0` when `Captures` was created with /// [`Captures::matches`]. /// /// If this routine returns a non-`None` value, then `is_match` is /// guaranteed to return `true`, `pattern` is guaranteed to return a /// non-`None` value and `get_match` is guaranteed to return a non-`None` /// value. /// /// # Example /// /// This example shows how to get the capturing groups, by name, from a /// match: /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span, Match}; /// /// let re = PikeVM::new(r"^(?P<first>\pL+)\s+(?P<last>\pL+)$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Bruce Springsteen", &mut caps); /// assert_eq!(Some(Match::must(0, 0..17)), caps.get_match()); /// assert_eq!(Some(Span::from(0..5)), caps.get_group_by_name("first")); /// assert_eq!(Some(Span::from(6..17)), caps.get_group_by_name("last")); /// // Looking for a non-existent capturing group will return None: /// assert_eq!(None, caps.get_group_by_name("middle")); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn get_group_by_name(&self, name: &str) -> Option<Span> { let index = self.group_info().to_index(self.pattern()?, name)?; self.get_group(index)
}
/// Returns an iterator of possible spans for every capturing group in the /// matching pattern. /// /// If this `Captures` value does not correspond to a match, then the /// iterator returned yields no elements. /// /// Note that the iterator returned yields elements of type `Option<Span>`. /// A span is present if and only if it corresponds to a capturing group /// that participated in a match. /// /// # Example /// /// This example shows how to collect all capturing groups: /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span}; /// /// let re = PikeVM::new( /// // Matches first/last names, with an optional middle name. /// r"^(?P<first>\pL+)\s+(?:(?P<middle>\pL+)\s+)?(?P<last>\pL+)$", /// )?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Harry James Potter", &mut caps); /// assert!(caps.is_match()); /// let groups: Vec<Option<Span>> = caps.iter().collect(); /// assert_eq!(groups, vec![ /// Some(Span::from(0..18)), /// Some(Span::from(0..5)), /// Some(Span::from(6..11)), /// Some(Span::from(12..18)), /// ]); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// This example uses the same regex as the previous example, but with a /// haystack that omits the middle name. This results in a capturing group /// that is present in the elements yielded by the iterator but without a /// match: /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::{nfa::thompson::pikevm::PikeVM, Span}; /// /// let re = PikeVM::new( /// // Matches first/last names, with an optional middle name. /// r"^(?P<first>\pL+)\s+(?:(?P<middle>\pL+)\s+)?(?P<last>\pL+)$", /// )?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Harry Potter", &mut caps); /// assert!(caps.is_match()); /// let groups: Vec<Option<Span>> = caps.iter().collect(); /// assert_eq!(groups, vec![ /// Some(Span::from(0..12)), /// Some(Span::from(0..5)), /// None, /// Some(Span::from(6..12)), /// ]); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn iter(&self) -> CapturesPatternIter<'_> { let names = self
.pattern()
.map_or(GroupInfoPatternNames::empty().enumerate(), |pid| { self.group_info().pattern_names(pid).enumerate()
});
CapturesPatternIter { caps: self, names }
}
/// Return the total number of capturing groups for the matching pattern. /// /// If this `Captures` value does not correspond to a match, then this /// always returns `0`. /// /// This always returns the same number of elements yielded by /// [`Captures::iter`]. That is, the number includes capturing groups even /// if they don't participate in the match. /// /// # Example /// /// This example shows how to count the total number of capturing groups /// associated with a pattern. Notice that it includes groups that did not /// participate in a match (just like `Captures::iter` does). /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::nfa::thompson::pikevm::PikeVM; /// /// let re = PikeVM::new( /// // Matches first/last names, with an optional middle name. /// r"^(?P<first>\pL+)\s+(?:(?P<middle>\pL+)\s+)?(?P<last>\pL+)$", /// )?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Harry Potter", &mut caps); /// assert_eq!(4, caps.group_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn group_len(&self) -> usize { let pid = matchself.pattern() {
None => return0,
Some(pid) => pid,
}; self.group_info().group_len(pid)
}
/// Returns a reference to the underlying group info on which these /// captures are based. /// /// The difference between `GroupInfo` and `Captures` is that the former /// defines the structure of capturing groups where as the latter is what /// stores the actual match information. So where as `Captures` only gives /// you access to the current match, `GroupInfo` lets you query any /// information about all capturing groups, even ones for patterns that /// weren't involved in a match. /// /// Note that a `GroupInfo` uses reference counting internally, so it may /// be cloned cheaply. /// /// # Example /// /// This example shows how to get all capturing group names from the /// underlying `GroupInfo`. Notice that we don't even need to run a /// search. /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, PatternID}; /// /// let re = PikeVM::new_many(&[ /// r"(?P<foo>a)", /// r"(a)(b)", /// r"ab", /// r"(?P<bar>a)(?P<quux>a)", /// r"(?P<foo>z)", /// ])?; /// let caps = re.create_captures(); /// /// let expected = vec![ /// (PatternID::must(0), 0, None), /// (PatternID::must(0), 1, Some("foo")), /// (PatternID::must(1), 0, None), /// (PatternID::must(1), 1, None), /// (PatternID::must(1), 2, None), /// (PatternID::must(2), 0, None), /// (PatternID::must(3), 0, None), /// (PatternID::must(3), 1, Some("bar")), /// (PatternID::must(3), 2, Some("quux")), /// (PatternID::must(4), 0, None), /// (PatternID::must(4), 1, Some("foo")), /// ]; /// // We could also just use 're.get_nfa().group_info()'. /// let got: Vec<(PatternID, usize, Option<&str>)> = /// caps.group_info().all_names().collect(); /// assert_eq!(expected, got); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn group_info(&self) -> &GroupInfo {
&self.group_info
}
/// Interpolates the capture references in `replacement` with the /// corresponding substrings in `haystack` matched by each reference. The /// interpolated string is returned. /// /// See the [`interpolate` module](interpolate) for documentation on the /// format of the replacement string. /// /// # Example /// /// This example shows how to use interpolation, and also shows how it /// can work with multi-pattern regexes. /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, PatternID}; /// /// let re = PikeVM::new_many(&[ /// r"(?<day>[0-9]{2})-(?<month>[0-9]{2})-(?<year>[0-9]{4})", /// r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})", /// ])?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let replacement = "year=$year, month=$month, day=$day"; /// /// // This matches the first pattern. /// let hay = "On 14-03-2010, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let result = caps.interpolate_string(hay, replacement); /// assert_eq!("year=2010, month=03, day=14", result); /// /// // And this matches the second pattern. /// let hay = "On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let result = caps.interpolate_string(hay, replacement); /// assert_eq!("year=2010, month=03, day=14", result); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn interpolate_string(
&self,
haystack: &str,
replacement: &str,
) -> String { letmut dst = String::new(); self.interpolate_string_into(haystack, replacement, &mut dst);
dst
}
/// Interpolates the capture references in `replacement` with the /// corresponding substrings in `haystack` matched by each reference. The /// interpolated string is written to `dst`. /// /// See the [`interpolate` module](interpolate) for documentation on the /// format of the replacement string. /// /// # Example /// /// This example shows how to use interpolation, and also shows how it /// can work with multi-pattern regexes. /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, PatternID}; /// /// let re = PikeVM::new_many(&[ /// r"(?<day>[0-9]{2})-(?<month>[0-9]{2})-(?<year>[0-9]{4})", /// r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})", /// ])?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let replacement = "year=$year, month=$month, day=$day"; /// /// // This matches the first pattern. /// let hay = "On 14-03-2010, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let mut dst = String::new(); /// caps.interpolate_string_into(hay, replacement, &mut dst); /// assert_eq!("year=2010, month=03, day=14", dst); /// /// // And this matches the second pattern. /// let hay = "On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let mut dst = String::new(); /// caps.interpolate_string_into(hay, replacement, &mut dst); /// assert_eq!("year=2010, month=03, day=14", dst); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn interpolate_string_into(
&self,
haystack: &str,
replacement: &str,
dst: &mut String,
) {
interpolate::string(
replacement,
|index, dst| { let span = matchself.get_group(index) {
None => return,
Some(span) => span,
};
dst.push_str(&haystack[span]);
},
|name| self.group_info().to_index(self.pattern()?, name),
dst,
);
}
/// Interpolates the capture references in `replacement` with the /// corresponding substrings in `haystack` matched by each reference. The /// interpolated byte string is returned. /// /// See the [`interpolate` module](interpolate) for documentation on the /// format of the replacement string. /// /// # Example /// /// This example shows how to use interpolation, and also shows how it /// can work with multi-pattern regexes. /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, PatternID}; /// /// let re = PikeVM::new_many(&[ /// r"(?<day>[0-9]{2})-(?<month>[0-9]{2})-(?<year>[0-9]{4})", /// r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})", /// ])?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let replacement = b"year=$year, month=$month, day=$day"; /// /// // This matches the first pattern. /// let hay = b"On 14-03-2010, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let result = caps.interpolate_bytes(hay, replacement); /// assert_eq!(&b"year=2010, month=03, day=14"[..], result); /// /// // And this matches the second pattern. /// let hay = b"On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let result = caps.interpolate_bytes(hay, replacement); /// assert_eq!(&b"year=2010, month=03, day=14"[..], result); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn interpolate_bytes(
&self,
haystack: &[u8],
replacement: &[u8],
) -> Vec<u8> { letmut dst = vec![]; self.interpolate_bytes_into(haystack, replacement, &mut dst);
dst
}
/// Interpolates the capture references in `replacement` with the /// corresponding substrings in `haystack` matched by each reference. The /// interpolated byte string is written to `dst`. /// /// See the [`interpolate` module](interpolate) for documentation on the /// format of the replacement string. /// /// # Example /// /// This example shows how to use interpolation, and also shows how it /// can work with multi-pattern regexes. /// /// ``` /// use regex_automata::{nfa::thompson::pikevm::PikeVM, PatternID}; /// /// let re = PikeVM::new_many(&[ /// r"(?<day>[0-9]{2})-(?<month>[0-9]{2})-(?<year>[0-9]{4})", /// r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})", /// ])?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let replacement = b"year=$year, month=$month, day=$day"; /// /// // This matches the first pattern. /// let hay = b"On 14-03-2010, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let mut dst = vec![]; /// caps.interpolate_bytes_into(hay, replacement, &mut dst); /// assert_eq!(&b"year=2010, month=03, day=14"[..], dst); /// /// // And this matches the second pattern. /// let hay = b"On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// let mut dst = vec![]; /// caps.interpolate_bytes_into(hay, replacement, &mut dst); /// assert_eq!(&b"year=2010, month=03, day=14"[..], dst); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn interpolate_bytes_into(
&self,
haystack: &[u8],
replacement: &[u8],
dst: &mut Vec<u8>,
) {
interpolate::bytes(
replacement,
|index, dst| { let span = matchself.get_group(index) {
None => return,
Some(span) => span,
};
dst.extend_from_slice(&haystack[span]);
},
|name| self.group_info().to_index(self.pattern()?, name),
dst,
);
}
/// This is a convenience routine for extracting the substrings /// corresponding to matching capture groups in the given `haystack`. The /// `haystack` should be the same substring used to find the match spans in /// this `Captures` value. /// /// This is identical to [`Captures::extract_bytes`], except it works with /// `&str` instead of `&[u8]`. /// /// # Panics /// /// This panics if the number of explicit matching groups in this /// `Captures` value is less than `N`. This also panics if this `Captures` /// value does not correspond to a match. /// /// Note that this does *not* panic if the number of explicit matching /// groups is bigger than `N`. In that case, only the first `N` matching /// groups are extracted. /// /// # Example /// /// ``` /// use regex_automata::nfa::thompson::pikevm::PikeVM; /// /// let re = PikeVM::new(r"([0-9]{4})-([0-9]{2})-([0-9]{2})")?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let hay = "On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// assert!(caps.is_match()); /// let (full, [year, month, day]) = caps.extract(hay); /// assert_eq!("2010-03-14", full); /// assert_eq!("2010", year); /// assert_eq!("03", month); /// assert_eq!("14", day); /// /// // We can also ask for fewer than all capture groups. /// let (full, [year]) = caps.extract(hay); /// assert_eq!("2010-03-14", full); /// assert_eq!("2010", year); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn extract<'h, const N: usize>(
&self,
haystack: &'h str,
) -> (&'h str, [&'h str; N]) { letmut matched = self.iter().flatten(); let whole_match = &haystack[matched.next().expect("a match")]; let group_matches = [0; N].map(|_| { let sp = matched.next().expect("too few matching groups");
&haystack[sp]
});
(whole_match, group_matches)
}
/// This is a convenience routine for extracting the substrings /// corresponding to matching capture groups in the given `haystack`. The /// `haystack` should be the same substring used to find the match spans in /// this `Captures` value. /// /// This is identical to [`Captures::extract`], except it works with /// `&[u8]` instead of `&str`. /// /// # Panics /// /// This panics if the number of explicit matching groups in this /// `Captures` value is less than `N`. This also panics if this `Captures` /// value does not correspond to a match. /// /// Note that this does *not* panic if the number of explicit matching /// groups is bigger than `N`. In that case, only the first `N` matching /// groups are extracted. /// /// # Example /// /// ``` /// use regex_automata::nfa::thompson::pikevm::PikeVM; /// /// let re = PikeVM::new(r"([0-9]{4})-([0-9]{2})-([0-9]{2})")?; /// let mut cache = re.create_cache(); /// let mut caps = re.create_captures(); /// /// let hay = b"On 2010-03-14, I became a Tenneessee lamb."; /// re.captures(&mut cache, hay, &mut caps); /// assert!(caps.is_match()); /// let (full, [year, month, day]) = caps.extract_bytes(hay); /// assert_eq!(b"2010-03-14", full); /// assert_eq!(b"2010", year); /// assert_eq!(b"03", month); /// assert_eq!(b"14", day); /// /// // We can also ask for fewer than all capture groups. /// let (full, [year]) = caps.extract_bytes(hay); /// assert_eq!(b"2010-03-14", full); /// assert_eq!(b"2010", year); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn extract_bytes<'h, const N: usize>(
&self,
haystack: &'h [u8],
) -> (&'h [u8], [&'h [u8]; N]) { letmut matched = self.iter().flatten(); let whole_match = &haystack[matched.next().expect("a match")]; let group_matches = [0; N].map(|_| { let sp = matched.next().expect("too few matching groups");
&haystack[sp]
});
(whole_match, group_matches)
}
}
/// Lower level "slot" oriented APIs. One does not typically need to use these /// when executing a search. They are instead mostly intended for folks that /// are writing their own regex engine while reusing this `Captures` type. impl Captures { /// Clear this `Captures` value. /// /// After clearing, all slots inside this `Captures` value will be set to /// `None`. Similarly, any pattern ID that it was previously associated /// with (for a match) is erased. /// /// It is not usually necessary to call this routine. Namely, a `Captures` /// value only provides high level access to the capturing groups of the /// pattern that matched, and only low level access to individual slots. /// Thus, even if slots corresponding to groups that aren't associated /// with the matching pattern are set, then it won't impact the higher /// level APIs. Namely, higher level APIs like [`Captures::get_group`] will /// return `None` if no pattern ID is present, even if there are spans set /// in the underlying slots. /// /// Thus, to "clear" a `Captures` value of a match, it is usually only /// necessary to call [`Captures::set_pattern`] with `None`. /// /// # Example /// /// This example shows what happens when a `Captures` value is cleared. /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::nfa::thompson::pikevm::PikeVM; /// /// let re = PikeVM::new(r"^(?P<first>\pL+)\s+(?P<last>\pL+)$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Bruce Springsteen", &mut caps); /// assert!(caps.is_match()); /// let slots: Vec<Option<usize>> = /// caps.slots().iter().map(|s| s.map(|x| x.get())).collect(); /// // Note that the following ordering is considered an API guarantee. /// assert_eq!(slots, vec![ /// Some(0), /// Some(17), /// Some(0), /// Some(5), /// Some(6), /// Some(17), /// ]); /// /// // Now clear the slots. Everything is gone and it is no longer a match. /// caps.clear(); /// assert!(!caps.is_match()); /// let slots: Vec<Option<usize>> = /// caps.slots().iter().map(|s| s.map(|x| x.get())).collect(); /// assert_eq!(slots, vec![ /// None, /// None, /// None, /// None, /// None, /// None, /// ]); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn clear(&mutself) { self.pid = None; for slot inself.slots.iter_mut() {
*slot = None;
}
}
/// Set the pattern on this `Captures` value. /// /// When the pattern ID is `None`, then this `Captures` value does not /// correspond to a match (`is_match` will return `false`). Otherwise, it /// corresponds to a match. /// /// This is useful in search implementations where you might want to /// initially call `set_pattern(None)` in order to avoid the cost of /// calling `clear()` if it turns out to not be necessary. /// /// # Example /// /// This example shows that `set_pattern` merely overwrites the pattern ID. /// It does not actually change the underlying slot values. /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::nfa::thompson::pikevm::PikeVM; /// /// let re = PikeVM::new(r"^(?P<first>\pL+)\s+(?P<last>\pL+)$")?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "Bruce Springsteen", &mut caps); /// assert!(caps.is_match()); /// assert!(caps.pattern().is_some()); /// let slots: Vec<Option<usize>> = /// caps.slots().iter().map(|s| s.map(|x| x.get())).collect(); /// // Note that the following ordering is considered an API guarantee. /// assert_eq!(slots, vec![ /// Some(0), /// Some(17), /// Some(0), /// Some(5), /// Some(6), /// Some(17), /// ]); /// /// // Now set the pattern to None. Note that the slot values remain. /// caps.set_pattern(None); /// assert!(!caps.is_match()); /// assert!(!caps.pattern().is_some()); /// let slots: Vec<Option<usize>> = /// caps.slots().iter().map(|s| s.map(|x| x.get())).collect(); /// // Note that the following ordering is considered an API guarantee. /// assert_eq!(slots, vec![ /// Some(0), /// Some(17), /// Some(0), /// Some(5), /// Some(6), /// Some(17), /// ]); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn set_pattern(&mutself, pid: Option<PatternID>) { self.pid = pid;
}
/// Returns the underlying slots, where each slot stores a single offset. /// /// Every matching capturing group generally corresponds to two slots: one /// slot for the starting position and another for the ending position. /// Typically, either both are present or neither are. (The weasel word /// "typically" is used here because it really depends on the regex engine /// implementation. Every sensible regex engine likely adheres to this /// invariant, and every regex engine in this crate is sensible.) /// /// Generally speaking, callers should prefer to use higher level routines /// like [`Captures::get_match`] or [`Captures::get_group`]. /// /// An important note here is that a regex engine may not reset all of the /// slots to `None` values when no match occurs, or even when a match of /// a different pattern occurs. But this depends on how the regex engine /// implementation deals with slots. /// /// # Example /// /// This example shows how to get the underlying slots from a regex match. /// /// ``` /// use regex_automata::{ /// nfa::thompson::pikevm::PikeVM, /// util::primitives::{PatternID, NonMaxUsize}, /// }; /// /// let re = PikeVM::new_many(&[ /// r"[a-z]+", /// r"[0-9]+", /// ])?; /// let (mut cache, mut caps) = (re.create_cache(), re.create_captures()); /// /// re.captures(&mut cache, "123", &mut caps); /// assert_eq!(Some(PatternID::must(1)), caps.pattern()); /// // Note that the only guarantee we have here is that slots 2 and 3 /// // are set to correct values. The contents of the first two slots are /// // unspecified since the 0th pattern did not match. /// let expected = &[ /// None, /// None, /// NonMaxUsize::new(0), /// NonMaxUsize::new(3), /// ]; /// assert_eq!(expected, caps.slots()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn slots(&self) -> &[Option<NonMaxUsize>] {
&self.slots
}
/// Returns the underlying slots as a mutable slice, where each slot stores /// a single offset. /// /// This tends to be most useful for regex engine implementations for /// writing offsets for matching capturing groups to slots. /// /// See [`Captures::slots`] for more information about slots. #[inline] pubfn slots_mut(&mutself) -> &mut [Option<NonMaxUsize>] {
&mutself.slots
}
}
/// A little helper type to provide a nice map-like debug representation for /// our capturing group spans. struct CapturesDebugMap<'a> {
pid: PatternID,
caps: &'a Captures,
}
letmut map = f.debug_map(); let names = self.caps.group_info().pattern_names(self.pid); for (group_index, maybe_name) in names.enumerate() { let key = Key(group_index, maybe_name); matchself.caps.get_group(group_index) {
None => map.entry(&key, &None::<()>),
Some(span) => map.entry(&key, &span),
};
}
map.finish()
}
}
/// An iterator over all capturing groups in a `Captures` value. /// /// This iterator includes capturing groups that did not participate in a /// match. See the [`Captures::iter`] method documentation for more details /// and examples. /// /// The lifetime parameter `'a` refers to the lifetime of the underlying /// `Captures` value. #[derive(Clone, Debug)] pubstruct CapturesPatternIter<'a> {
caps: &'a Captures,
names: core::iter::Enumerate<GroupInfoPatternNames<'a>>,
}
impl<'a> Iterator for CapturesPatternIter<'a> { type Item = Option<Span>;
impl<'a> ExactSizeIterator for CapturesPatternIter<'a> {} impl<'a> core::iter::FusedIterator for CapturesPatternIter<'a> {}
/// Represents information about capturing groups in a compiled regex. /// /// The information encapsulated by this type consists of the following. For /// each pattern: /// /// * A map from every capture group name to its corresponding capture group /// index. /// * A map from every capture group index to its corresponding capture group /// name. /// * A map from capture group index to its corresponding slot index. A slot /// refers to one half of a capturing group. That is, a capture slot is either /// the start or end of a capturing group. A slot is usually the mechanism /// by which a regex engine records offsets for each capturing group during a /// search. /// /// A `GroupInfo` uses reference counting internally and is thus cheap to /// clone. /// /// # Mapping from capture groups to slots /// /// One of the main responsibilities of a `GroupInfo` is to build a mapping /// from `(PatternID, u32)` (where the `u32` is a capture index) to something /// called a "slot." As mentioned above, a slot refers to one half of a /// capturing group. Both combined provide the start and end offsets of /// a capturing group that participated in a match. /// /// **The mapping between group indices and slots is an API guarantee.** That /// is, the mapping won't change within a semver compatible release. /// /// Slots exist primarily because this is a convenient mechanism by which /// regex engines report group offsets at search time. For example, the /// [`nfa::thompson::State::Capture`](crate::nfa::thompson::State::Capture) /// NFA state includes the slot index. When a regex engine transitions through /// this state, it will likely use the slot index to write the current haystack /// offset to some region of memory. When a match is found, those slots are /// then reported to the caller, typically via a convenient abstraction like a /// [`Captures`] value. /// /// Because this crate provides first class support for multi-pattern regexes, /// and because of some performance related reasons, the mapping between /// capturing groups and slots is a little complex. However, in the case of a /// single pattern, the mapping can be described very simply: for all capture /// group indices `i`, its corresponding slots are at `i * 2` and `i * 2 + 1`. /// Notice that the pattern ID isn't involved at all here, because it only /// applies to a single-pattern regex, it is therefore always `0`. /// /// In the multi-pattern case, the mapping is a bit more complicated. To talk /// about it, we must define what we mean by "implicit" vs "explicit" /// capturing groups: /// /// * An **implicit** capturing group refers to the capturing group that is /// present for every pattern automatically, and corresponds to the overall /// match of a pattern. Every pattern has precisely one implicit capturing /// group. It is always unnamed and it always corresponds to the capture group /// index `0`. /// * An **explicit** capturing group refers to any capturing group that /// appears in the concrete syntax of the pattern. (Or, if an NFA was hand /// built without any concrete syntax, it refers to any capturing group with an /// index greater than `0`.) /// /// Some examples: /// /// * `\w+` has one implicit capturing group and zero explicit capturing /// groups. /// * `(\w+)` has one implicit group and one explicit group. /// * `foo(\d+)(?:\pL+)(\d+)` has one implicit group and two explicit groups. /// /// Turning back to the slot mapping, we can now state it as follows: /// /// * Given a pattern ID `pid`, the slots for its implicit group are always /// at `pid * 2` and `pid * 2 + 1`. /// * Given a pattern ID `0`, the slots for its explicit groups start /// at `group_info.pattern_len() * 2`. /// * Given a pattern ID `pid > 0`, the slots for its explicit groups start /// immediately following where the slots for the explicit groups of `pid - 1` /// end. /// /// In particular, while there is a concrete formula one can use to determine /// where the slots for the implicit group of any pattern are, there is no /// general formula for determining where the slots for explicit capturing /// groups are. This is because each pattern can contain a different number /// of groups. /// /// The intended way of getting the slots for a particular capturing group /// (whether implicit or explicit) is via the [`GroupInfo::slot`] or /// [`GroupInfo::slots`] method. /// /// See below for a concrete example of how capturing groups get mapped to /// slots. /// /// # Example /// /// This example shows how to build a new `GroupInfo` and query it for /// information. /// /// ``` /// use regex_automata::util::{captures::GroupInfo, primitives::PatternID}; /// /// let info = GroupInfo::new(vec![ /// vec![None, Some("foo")], /// vec![None], /// vec![None, None, None, Some("bar"), None], /// vec![None, None, Some("foo")], /// ])?; /// // The number of patterns being tracked. /// assert_eq!(4, info.pattern_len()); /// // We can query the number of groups for any pattern. /// assert_eq!(2, info.group_len(PatternID::must(0))); /// assert_eq!(1, info.group_len(PatternID::must(1))); /// assert_eq!(5, info.group_len(PatternID::must(2))); /// assert_eq!(3, info.group_len(PatternID::must(3))); /// // An invalid pattern always has zero groups. /// assert_eq!(0, info.group_len(PatternID::must(999))); /// // 2 slots per group /// assert_eq!(22, info.slot_len()); /// /// // We can map a group index for a particular pattern to its name, if /// // one exists. /// assert_eq!(Some("foo"), info.to_name(PatternID::must(3), 2)); /// assert_eq!(None, info.to_name(PatternID::must(2), 4)); /// // Or map a name to its group index. /// assert_eq!(Some(1), info.to_index(PatternID::must(0), "foo")); /// assert_eq!(Some(2), info.to_index(PatternID::must(3), "foo")); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// # Example: mapping from capture groups to slots /// /// This example shows the specific mapping from capture group indices for /// each pattern to their corresponding slots. The slot values shown in this /// example are considered an API guarantee. /// /// ``` /// use regex_automata::util::{captures::GroupInfo, primitives::PatternID}; /// /// let info = GroupInfo::new(vec![ /// vec![None, Some("foo")], /// vec![None], /// vec![None, None, None, Some("bar"), None], /// vec![None, None, Some("foo")], /// ])?; /// /// // We first show the slots for each pattern's implicit group. /// assert_eq!(Some((0, 1)), info.slots(PatternID::must(0), 0)); /// assert_eq!(Some((2, 3)), info.slots(PatternID::must(1), 0)); /// assert_eq!(Some((4, 5)), info.slots(PatternID::must(2), 0)); /// assert_eq!(Some((6, 7)), info.slots(PatternID::must(3), 0)); /// /// // And now we show the slots for each pattern's explicit group. /// assert_eq!(Some((8, 9)), info.slots(PatternID::must(0), 1)); /// assert_eq!(Some((10, 11)), info.slots(PatternID::must(2), 1)); /// assert_eq!(Some((12, 13)), info.slots(PatternID::must(2), 2)); /// assert_eq!(Some((14, 15)), info.slots(PatternID::must(2), 3)); /// assert_eq!(Some((16, 17)), info.slots(PatternID::must(2), 4)); /// assert_eq!(Some((18, 19)), info.slots(PatternID::must(3), 1)); /// assert_eq!(Some((20, 21)), info.slots(PatternID::must(3), 2)); /// /// // Asking for the slots for an invalid pattern ID or even for an invalid /// // group index for a specific pattern will return None. So for example, /// // you're guaranteed to not get the slots for a different pattern than the /// // one requested. /// assert_eq!(None, info.slots(PatternID::must(5), 0)); /// assert_eq!(None, info.slots(PatternID::must(1), 1)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[derive(Clone, Debug, Default)] pubstruct GroupInfo(Arc<GroupInfoInner>);
impl GroupInfo { /// Creates a new group info from a sequence of patterns, where each /// sequence of patterns yields a sequence of possible group names. The /// index of each pattern in the sequence corresponds to its `PatternID`, /// and the index of each group in each pattern's sequence corresponds to /// its corresponding group index. /// /// While this constructor is very generic and therefore perhaps hard to /// chew on, an example of a valid concrete type that can be passed to /// this constructor is `Vec<Vec<Option<String>>>`. The outer `Vec` /// corresponds to the patterns, i.e., one `Vec<Option<String>>` per /// pattern. The inner `Vec` corresponds to the capturing groups for /// each pattern. The `Option<String>` corresponds to the name of the /// capturing group, if present. /// /// It is legal to pass an empty iterator to this constructor. It will /// return an empty group info with zero slots. An empty group info is /// useful for cases where you have no patterns or for cases where slots /// aren't being used at all (e.g., for most DFAs in this crate). /// /// # Errors /// /// This constructor returns an error if the given capturing groups are /// invalid in some way. Those reasons include, but are not necessarily /// limited to: /// /// * Too many patterns (i.e., `PatternID` would overflow). /// * Too many capturing groups (e.g., `u32` would overflow). /// * A pattern is given that has no capturing groups. (All patterns must /// have at least an implicit capturing group at index `0`.) /// * The capturing group at index `0` has a name. It must be unnamed. /// * There are duplicate capturing group names within the same pattern. /// (Multiple capturing groups with the same name may exist, but they /// must be in different patterns.) /// /// An example below shows how to trigger some of the above error /// conditions. /// /// # Example /// /// This example shows how to build a new `GroupInfo` and query it for /// information. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// let info = GroupInfo::new(vec![ /// vec![None, Some("foo")], /// vec![None], /// vec![None, None, None, Some("bar"), None], /// vec![None, None, Some("foo")], /// ])?; /// // The number of patterns being tracked. /// assert_eq!(4, info.pattern_len()); /// // 2 slots per group /// assert_eq!(22, info.slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// # Example: empty `GroupInfo` /// /// This example shows how to build a new `GroupInfo` and query it for /// information. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// let info = GroupInfo::empty(); /// // Everything is zero. /// assert_eq!(0, info.pattern_len()); /// assert_eq!(0, info.slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// # Example: error conditions /// /// This example shows how to provoke some of the ways in which building /// a `GroupInfo` can fail. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// // Either the group info is empty, or all patterns must have at least /// // one capturing group. /// assert!(GroupInfo::new(vec![ /// vec![None, Some("a")], // ok /// vec![None], // ok /// vec![], // not ok /// ]).is_err()); /// // Note that building an empty group info is OK. /// assert!(GroupInfo::new(Vec::<Vec<Option<String>>>::new()).is_ok()); /// /// // The first group in each pattern must correspond to an implicit /// // anonymous group. i.e., One that is not named. By convention, this /// // group corresponds to the overall match of a regex. Every other group /// // in a pattern is explicit and optional. /// assert!(GroupInfo::new(vec![vec![Some("foo")]]).is_err()); /// /// // There must not be duplicate group names within the same pattern. /// assert!(GroupInfo::new(vec![ /// vec![None, Some("foo"), Some("foo")], /// ]).is_err()); /// // But duplicate names across distinct patterns is OK. /// assert!(GroupInfo::new(vec![ /// vec![None, Some("foo")], /// vec![None, Some("foo")], /// ]).is_ok()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// There are other ways for building a `GroupInfo` to fail but are /// difficult to show. For example, if the number of patterns given would /// overflow `PatternID`. pubfn new<P, G, N>(pattern_groups: P) -> Result<GroupInfo, GroupInfoError> where
P: IntoIterator<Item = G>,
G: IntoIterator<Item = Option<N>>,
N: AsRef<str>,
{ letmut group_info = GroupInfoInner {
slot_ranges: vec![],
name_to_index: vec![],
index_to_name: vec![],
memory_extra: 0,
}; for (pattern_index, groups) in pattern_groups.into_iter().enumerate() { // If we can't convert the pattern index to an ID, then the caller // tried to build capture info for too many patterns. let pid = PatternID::new(pattern_index)
.map_err(GroupInfoError::too_many_patterns)?;
letmut groups_iter = groups.into_iter().enumerate(); match groups_iter.next() {
None => return Err(GroupInfoError::missing_groups(pid)),
Some((_, Some(_))) => { return Err(GroupInfoError::first_must_be_unnamed(pid))
}
Some((_, None)) => {}
}
group_info.add_first_group(pid); // Now iterate over the rest, which correspond to all of the // (conventionally) explicit capture groups in a regex pattern. for (group_index, maybe_name) in groups_iter { // Just like for patterns, if the group index can't be // converted to a "small" index, then the caller has given too // many groups for a particular pattern. let group = SmallIndex::new(group_index).map_err(|_| {
GroupInfoError::too_many_groups(pid, group_index)
})?;
group_info.add_explicit_group(pid, group, maybe_name)?;
}
}
group_info.fixup_slot_ranges()?;
Ok(GroupInfo(Arc::new(group_info)))
}
/// This creates an empty `GroupInfo`. /// /// This is a convenience routine for calling `GroupInfo::new` with an /// iterator that yields no elements. /// /// # Example /// /// This example shows how to build a new empty `GroupInfo` and query it /// for information. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// let info = GroupInfo::empty(); /// // Everything is zero. /// assert_eq!(0, info.pattern_len()); /// assert_eq!(0, info.all_group_len()); /// assert_eq!(0, info.slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` pubfn empty() -> GroupInfo {
GroupInfo::new(core::iter::empty::<[Option<&str>; 0]>())
.expect("empty group info is always valid")
}
/// Return the capture group index corresponding to the given name in the /// given pattern. If no such capture group name exists in the given /// pattern, then this returns `None`. /// /// If the given pattern ID is invalid, then this returns `None`. /// /// This also returns `None` for all inputs if these captures are empty /// (e.g., built from an empty [`GroupInfo`]). To check whether captures /// are are present for a specific pattern, use [`GroupInfo::group_len`]. /// /// # Example /// /// This example shows how to find the capture index for the given pattern /// and group name. /// /// Remember that capture indices are relative to the pattern, such that /// the same capture index value may refer to different capturing groups /// for distinct patterns. /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let (pid0, pid1) = (PatternID::must(0), PatternID::must(1)); /// /// let nfa = NFA::new_many(&[ /// r"a(?P<quux>\w+)z(?P<foo>\s+)", /// r"a(?P<foo>\d+)z", /// ])?; /// let groups = nfa.group_info(); /// assert_eq!(Some(2), groups.to_index(pid0, "foo")); /// // Recall that capture index 0 is always unnamed and refers to the /// // entire pattern. So the first capturing group present in the pattern /// // itself always starts at index 1. /// assert_eq!(Some(1), groups.to_index(pid1, "foo")); /// /// // And if a name does not exist for a particular pattern, None is /// // returned. /// assert!(groups.to_index(pid0, "quux").is_some()); /// assert!(groups.to_index(pid1, "quux").is_none()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn to_index(&self, pid: PatternID, name: &str) -> Option<usize> { let indices = self.0.name_to_index.get(pid.as_usize())?;
indices.get(name).cloned().map(|i| i.as_usize())
}
/// Return the capture name for the given index and given pattern. If the /// corresponding group does not have a name, then this returns `None`. /// /// If the pattern ID is invalid, then this returns `None`. /// /// If the group index is invalid for the given pattern, then this returns /// `None`. A group `index` is valid for a pattern `pid` in an `nfa` if and /// only if `index < nfa.pattern_capture_len(pid)`. /// /// This also returns `None` for all inputs if these captures are empty /// (e.g., built from an empty [`GroupInfo`]). To check whether captures /// are are present for a specific pattern, use [`GroupInfo::group_len`]. /// /// # Example /// /// This example shows how to find the capture group name for the given /// pattern and group index. /// /// ``` /// # if cfg!(miri) { return Ok(()); } // miri takes too long /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let (pid0, pid1) = (PatternID::must(0), PatternID::must(1)); /// /// let nfa = NFA::new_many(&[ /// r"a(?P<foo>\w+)z(\s+)x(\d+)", /// r"a(\d+)z(?P<foo>\s+)", /// ])?; /// let groups = nfa.group_info(); /// assert_eq!(None, groups.to_name(pid0, 0)); /// assert_eq!(Some("foo"), groups.to_name(pid0, 1)); /// assert_eq!(None, groups.to_name(pid0, 2)); /// assert_eq!(None, groups.to_name(pid0, 3)); /// /// assert_eq!(None, groups.to_name(pid1, 0)); /// assert_eq!(None, groups.to_name(pid1, 1)); /// assert_eq!(Some("foo"), groups.to_name(pid1, 2)); /// // '3' is not a valid capture index for the second pattern. /// assert_eq!(None, groups.to_name(pid1, 3)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn to_name(&self, pid: PatternID, group_index: usize) -> Option<&str> { let pattern_names = self.0.index_to_name.get(pid.as_usize())?;
pattern_names.get(group_index)?.as_deref()
}
/// Return an iterator of all capture groups and their names (if present) /// for a particular pattern. /// /// If the given pattern ID is invalid or if this `GroupInfo` is empty, /// then the iterator yields no elements. /// /// The number of elements yielded by this iterator is always equal to /// the result of calling [`GroupInfo::group_len`] with the same /// `PatternID`. /// /// # Example /// /// This example shows how to get a list of all capture group names for /// a particular pattern. /// /// ``` /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let nfa = NFA::new(r"(a)(?P<foo>b)(c)(d)(?P<bar>e)")?; /// // The first is the implicit group that is always unnammed. The next /// // 5 groups are the explicit groups found in the concrete syntax above. /// let expected = vec![None, None, Some("foo"), None, None, Some("bar")]; /// let got: Vec<Option<&str>> = /// nfa.group_info().pattern_names(PatternID::ZERO).collect(); /// assert_eq!(expected, got); /// /// // Using an invalid pattern ID will result in nothing yielded. /// let got = nfa.group_info().pattern_names(PatternID::must(999)).count(); /// assert_eq!(0, got); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn pattern_names(&self, pid: PatternID) -> GroupInfoPatternNames<'_> {
GroupInfoPatternNames {
it: self
.0
.index_to_name
.get(pid.as_usize())
.map(|indices| indices.iter())
.unwrap_or([].iter()),
}
}
/// Return an iterator of all capture groups for all patterns supported by /// this `GroupInfo`. Each item yielded is a triple of the group's pattern /// ID, index in the pattern and the group's name, if present. /// /// # Example /// /// This example shows how to get a list of all capture groups found in /// one NFA, potentially spanning multiple patterns. /// /// ``` /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let nfa = NFA::new_many(&[ /// r"(?P<foo>a)", /// r"a", /// r"(a)", /// ])?; /// let expected = vec![ /// (PatternID::must(0), 0, None), /// (PatternID::must(0), 1, Some("foo")), /// (PatternID::must(1), 0, None), /// (PatternID::must(2), 0, None), /// (PatternID::must(2), 1, None), /// ]; /// let got: Vec<(PatternID, usize, Option<&str>)> = /// nfa.group_info().all_names().collect(); /// assert_eq!(expected, got); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` /// /// Unlike other capturing group related routines, this routine doesn't /// panic even if captures aren't enabled on this NFA: /// /// ``` /// use regex_automata::nfa::thompson::{NFA, WhichCaptures}; /// /// let nfa = NFA::compiler() /// .configure(NFA::config().which_captures(WhichCaptures::None)) /// .build_many(&[ /// r"(?P<foo>a)", /// r"a", /// r"(a)", /// ])?; /// // When captures aren't enabled, there's nothing to return. /// assert_eq!(0, nfa.group_info().all_names().count()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn all_names(&self) -> GroupInfoAllNames<'_> {
GroupInfoAllNames {
group_info: self,
pids: PatternID::iter(self.pattern_len()),
current_pid: None,
names: None,
}
}
/// Returns the starting and ending slot corresponding to the given /// capturing group for the given pattern. The ending slot is always one /// more than the starting slot returned. /// /// Note that this is like [`GroupInfo::slot`], except that it also returns /// the ending slot value for convenience. /// /// If either the pattern ID or the capture index is invalid, then this /// returns None. /// /// # Example /// /// This example shows that the starting slots for the first capturing /// group of each pattern are distinct. /// /// ``` /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let nfa = NFA::new_many(&["a", "b"])?; /// assert_ne!( /// nfa.group_info().slots(PatternID::must(0), 0), /// nfa.group_info().slots(PatternID::must(1), 0), /// ); /// /// // Also, the start and end slot values are never equivalent. /// let (start, end) = nfa.group_info().slots(PatternID::ZERO, 0).unwrap(); /// assert_ne!(start, end); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn slots(
&self,
pid: PatternID,
group_index: usize,
) -> Option<(usize, usize)> { // Since 'slot' only even returns valid starting slots, we know that // there must also be an end slot and that end slot is always one more // than the start slot. self.slot(pid, group_index).map(|start| (start, start + 1))
}
/// Returns the starting slot corresponding to the given capturing group /// for the given pattern. The ending slot is always one more than the /// value returned. /// /// If either the pattern ID or the capture index is invalid, then this /// returns None. /// /// # Example /// /// This example shows that the starting slots for the first capturing /// group of each pattern are distinct. /// /// ``` /// use regex_automata::{nfa::thompson::NFA, PatternID}; /// /// let nfa = NFA::new_many(&["a", "b"])?; /// assert_ne!( /// nfa.group_info().slot(PatternID::must(0), 0), /// nfa.group_info().slot(PatternID::must(1), 0), /// ); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn slot(&self, pid: PatternID, group_index: usize) -> Option<usize> { if group_index >= self.group_len(pid) { return None;
} // At this point, we know that 'pid' refers to a real pattern and that // 'group_index' refers to a real group. We therefore also know that // the pattern and group can be combined to return a correct slot. // That's why we don't need to use checked arithmetic below. if group_index == 0 {
Some(pid.as_usize() * 2)
} else { // As above, we don't need to check that our slot is less than the // end of our range since we already know the group index is a // valid index for the given pattern. let (start, _) = self.0.slot_ranges[pid];
Some(start.as_usize() + ((group_index - 1) * 2))
}
}
/// Returns the total number of patterns in this `GroupInfo`. /// /// This may return zero if the `GroupInfo` was constructed with no /// patterns. /// /// This is guaranteed to be no bigger than [`PatternID::LIMIT`] because /// `GroupInfo` construction will fail if too many patterns are added. /// /// # Example /// /// ``` /// use regex_automata::nfa::thompson::NFA; /// /// let nfa = NFA::new_many(&["[0-9]+", "[a-z]+", "[A-Z]+"])?; /// assert_eq!(3, nfa.group_info().pattern_len()); /// /// let nfa = NFA::never_match(); /// assert_eq!(0, nfa.group_info().pattern_len()); /// /// let nfa = NFA::always_match(); /// assert_eq!(1, nfa.group_info().pattern_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn pattern_len(&self) -> usize { self.0.pattern_len()
}
/// Return the number of capture groups in a pattern. /// /// If the pattern ID is invalid, then this returns `0`. /// /// # Example /// /// This example shows how the values returned by this routine may vary /// for different patterns and NFA configurations. /// /// ``` /// use regex_automata::{nfa::thompson::{NFA, WhichCaptures}, PatternID}; /// /// let nfa = NFA::new(r"(a)(b)(c)")?; /// // There are 3 explicit groups in the pattern's concrete syntax and /// // 1 unnamed and implicit group spanning the entire pattern. /// assert_eq!(4, nfa.group_info().group_len(PatternID::ZERO)); /// /// let nfa = NFA::new(r"abc")?; /// // There is just the unnamed implicit group. /// assert_eq!(1, nfa.group_info().group_len(PatternID::ZERO)); /// /// let nfa = NFA::compiler() /// .configure(NFA::config().which_captures(WhichCaptures::None)) /// .build(r"abc")?; /// // We disabled capturing groups, so there are none. /// assert_eq!(0, nfa.group_info().group_len(PatternID::ZERO)); /// /// let nfa = NFA::compiler() /// .configure(NFA::config().which_captures(WhichCaptures::None)) /// .build(r"(a)(b)(c)")?; /// // We disabled capturing groups, so there are none, even if there are /// // explicit groups in the concrete syntax. /// assert_eq!(0, nfa.group_info().group_len(PatternID::ZERO)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn group_len(&self, pid: PatternID) -> usize { self.0.group_len(pid)
}
/// Return the total number of capture groups across all patterns. /// /// This includes implicit groups that represent the entire match of a /// pattern. /// /// # Example /// /// This example shows how the values returned by this routine may vary /// for different patterns and NFA configurations. /// /// ``` /// use regex_automata::{nfa::thompson::{NFA, WhichCaptures}, PatternID}; /// /// let nfa = NFA::new(r"(a)(b)(c)")?; /// // There are 3 explicit groups in the pattern's concrete syntax and /// // 1 unnamed and implicit group spanning the entire pattern. /// assert_eq!(4, nfa.group_info().all_group_len()); /// /// let nfa = NFA::new(r"abc")?; /// // There is just the unnamed implicit group. /// assert_eq!(1, nfa.group_info().all_group_len()); /// /// let nfa = NFA::new_many(&["(a)", "b", "(c)"])?; /// // Each pattern has one implicit groups, and two /// // patterns have one explicit group each. /// assert_eq!(5, nfa.group_info().all_group_len()); /// /// let nfa = NFA::compiler() /// .configure(NFA::config().which_captures(WhichCaptures::None)) /// .build(r"abc")?; /// // We disabled capturing groups, so there are none. /// assert_eq!(0, nfa.group_info().all_group_len()); /// /// let nfa = NFA::compiler() /// .configure(NFA::config().which_captures(WhichCaptures::None)) /// .build(r"(a)(b)(c)")?; /// // We disabled capturing groups, so there are none, even if there are /// // explicit groups in the concrete syntax. /// assert_eq!(0, nfa.group_info().group_len(PatternID::ZERO)); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn all_group_len(&self) -> usize { self.slot_len() / 2
}
/// Returns the total number of slots in this `GroupInfo` across all /// patterns. /// /// The total number of slots is always twice the total number of capturing /// groups, including both implicit and explicit groups. /// /// # Example /// /// This example shows the relationship between the number of capturing /// groups and slots. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// // There are 11 total groups here. /// let info = GroupInfo::new(vec![ /// vec![None, Some("foo")], /// vec![None], /// vec![None, None, None, Some("bar"), None], /// vec![None, None, Some("foo")], /// ])?; /// // 2 slots per group gives us 11*2=22 slots. /// assert_eq!(22, info.slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn slot_len(&self) -> usize { self.0.small_slot_len().as_usize()
}
/// Returns the total number of slots for implicit capturing groups. /// /// This is like [`GroupInfo::slot_len`], except it doesn't include the /// explicit slots for each pattern. Since there are always exactly 2 /// implicit slots for each pattern, the number of implicit slots is always /// equal to twice the number of patterns. /// /// # Example /// /// This example shows the relationship between the number of capturing /// groups, implicit slots and explicit slots. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// // There are 11 total groups here. /// let info = GroupInfo::new(vec![vec![None, Some("foo"), Some("bar")]])?; /// // 2 slots per group gives us 11*2=22 slots. /// assert_eq!(6, info.slot_len()); /// // 2 implicit slots per pattern gives us 2 implicit slots since there /// // is 1 pattern. /// assert_eq!(2, info.implicit_slot_len()); /// // 2 explicit capturing groups gives us 2*2=4 explicit slots. /// assert_eq!(4, info.explicit_slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn implicit_slot_len(&self) -> usize { self.pattern_len() * 2
}
/// Returns the total number of slots for explicit capturing groups. /// /// This is like [`GroupInfo::slot_len`], except it doesn't include the /// implicit slots for each pattern. (There are always 2 implicit slots for /// each pattern.) /// /// For a non-empty `GroupInfo`, it is always the case that `slot_len` is /// strictly greater than `explicit_slot_len`. For an empty `GroupInfo`, /// both the total number of slots and the number of explicit slots is /// `0`. /// /// # Example /// /// This example shows the relationship between the number of capturing /// groups, implicit slots and explicit slots. /// /// ``` /// use regex_automata::util::captures::GroupInfo; /// /// // There are 11 total groups here. /// let info = GroupInfo::new(vec![vec![None, Some("foo"), Some("bar")]])?; /// // 2 slots per group gives us 11*2=22 slots. /// assert_eq!(6, info.slot_len()); /// // 2 implicit slots per pattern gives us 2 implicit slots since there /// // is 1 pattern. /// assert_eq!(2, info.implicit_slot_len()); /// // 2 explicit capturing groups gives us 2*2=4 explicit slots. /// assert_eq!(4, info.explicit_slot_len()); /// /// # Ok::<(), Box<dyn std::error::Error>>(()) /// ``` #[inline] pubfn explicit_slot_len(&self) -> usize { self.slot_len().saturating_sub(self.implicit_slot_len())
}
/// Returns the memory usage, in bytes, of this `GroupInfo`. /// /// This does **not** include the stack size used up by this `GroupInfo`. /// To compute that, use `std::mem::size_of::<GroupInfo>()`. #[inline] pubfn memory_usage(&self) -> usize { use core::mem::size_of as s;
/// A map from capture group name to its corresponding capture group index. /// /// This type is actually wrapped inside a Vec indexed by pattern ID on a /// `GroupInfo`, since multiple patterns may have the same capture group name. /// That is, each pattern gets its own namespace of capture group names. /// /// Perhaps a more memory efficient representation would be /// HashMap<(PatternID, Arc<str>), usize>, but this makes it difficult to look /// up a capture index by name without producing a `Arc<str>`, which requires /// an allocation. To fix this, I think we'd need to define our own unsized /// type or something? Anyway, I didn't give this much thought since it /// probably doesn't matter much in the grand scheme of things. But it did /// stand out to me as mildly wasteful. #[cfg(feature = "std")] type CaptureNameMap = std::collections::HashMap<Arc<str>, SmallIndex>; #[cfg(not(feature = "std"))] type CaptureNameMap = alloc::collections::BTreeMap<Arc<str>, SmallIndex>;
/// The inner guts of `GroupInfo`. This type only exists so that it can /// be wrapped in an `Arc` to make `GroupInfo` reference counted. #[derive(Debug, Default)] struct GroupInfoInner {
slot_ranges: Vec<(SmallIndex, SmallIndex)>,
name_to_index: Vec<CaptureNameMap>,
index_to_name: Vec<Vec<Option<Arc<str>>>>,
memory_extra: usize,
}
impl GroupInfoInner { /// This adds the first unnamed group for the given pattern ID. The given /// pattern ID must be zero if this is the first time this method is /// called, or must be exactly one more than the pattern ID supplied to the /// previous call to this method. (This method panics if this rule is /// violated.) /// /// This can be thought of as initializing the GroupInfo state for the /// given pattern and closing off the state for any previous pattern. fn add_first_group(&mutself, pid: PatternID) {
assert_eq!(pid.as_usize(), self.slot_ranges.len());
assert_eq!(pid.as_usize(), self.name_to_index.len());
assert_eq!(pid.as_usize(), self.index_to_name.len()); // This is the start of our slots for the explicit capturing groups. // Note that since the slots for the 0th group for every pattern appear // before any slots for the nth group (where n > 0) in any pattern, we // will have to fix up the slot ranges once we know how many patterns // we've added capture groups for. let slot_start = self.small_slot_len(); self.slot_ranges.push((slot_start, slot_start)); self.name_to_index.push(CaptureNameMap::new()); self.index_to_name.push(vec![None]); self.memory_extra += core::mem::size_of::<Option<Arc<str>>>();
}
/// Add an explicit capturing group for the given pattern with the given /// index. If the group has a name, then that must be given as well. /// /// Note that every capturing group except for the first or zeroth group is /// explicit. /// /// This returns an error if adding this group would result in overflowing /// slot indices or if a capturing group with the same name for this /// pattern has already been added. fn add_explicit_group<N: AsRef<str>>(
&mutself,
pid: PatternID,
group: SmallIndex,
maybe_name: Option<N>,
) -> Result<(), GroupInfoError> { // We also need to check that the slot index generated for // this group is also valid. Although, this is a little weird // because we offset these indices below, at which point, we'll // have to recheck them. Gosh this is annoying. Note that // the '+2' below is OK because 'end' is guaranteed to be less // than isize::MAX. let end = &mutself.slot_ranges[pid].1;
*end = SmallIndex::new(end.as_usize() + 2).map_err(|_| {
GroupInfoError::too_many_groups(pid, group.as_usize())
})?; iflet Some(name) = maybe_name { let name = Arc::<str>::from(name.as_ref()); ifself.name_to_index[pid].contains_key(&*name) { return Err(GroupInfoError::duplicate(pid, &name));
} let len = name.len(); self.name_to_index[pid].insert(Arc::clone(&name), group); self.index_to_name[pid].push(Some(name)); // Adds the memory used by the Arc<str> in both maps. self.memory_extra += 2 * (len + core::mem::size_of::<Option<Arc<str>>>()); // And also the value entry for the 'name_to_index' map. // This is probably an underestimate for 'name_to_index' since // hashmaps/btrees likely have some non-zero overhead, but we // assume here that they have zero overhead. self.memory_extra += core::mem::size_of::<SmallIndex>();
} else { self.index_to_name[pid].push(None); self.memory_extra += core::mem::size_of::<Option<Arc<str>>>();
} // This is a sanity assert that checks that our group index // is in line with the number of groups added so far for this // pattern.
assert_eq!(group.one_more(), self.group_len(pid)); // And is also in line with the 'index_to_name' map.
assert_eq!(group.one_more(), self.index_to_name[pid].len());
Ok(())
}
/// This corrects the slot ranges to account for the slots corresponding /// to the zeroth group of each pattern. That is, every slot range is /// offset by 'pattern_len() * 2', since each pattern uses two slots to /// represent the zeroth group. fn fixup_slot_ranges(&mutself) -> Result<(), GroupInfoError> { usecrate::util::primitives::IteratorIndexExt; // Since we know number of patterns fits in PatternID and // PatternID::MAX < isize::MAX, it follows that multiplying by 2 will // never overflow usize. let offset = self.pattern_len().checked_mul(2).unwrap(); for (pid, &mut (refmut start, refmut end)) in self.slot_ranges.iter_mut().with_pattern_ids()
{ let group_len = 1 + ((end.as_usize() - start.as_usize()) / 2); let new_end = match end.as_usize().checked_add(offset) {
Some(new_end) => new_end,
None => { return Err(GroupInfoError::too_many_groups(
pid, group_len,
))
}
};
*end = SmallIndex::new(new_end).map_err(|_| {
GroupInfoError::too_many_groups(pid, group_len)
})?; // Since start <= end, if end is valid then start must be too.
*start = SmallIndex::new(start.as_usize() + offset).unwrap();
}
Ok(())
}
/// Return the total number of patterns represented by this capture slot /// info. fn pattern_len(&self) -> usize { self.slot_ranges.len()
}
/// Return the total number of capturing groups for the given pattern. If /// the given pattern isn't valid for this capture slot info, then 0 is /// returned. fn group_len(&self, pid: PatternID) -> usize { let (start, end) = matchself.slot_ranges.get(pid.as_usize()) {
None => return0,
Some(range) => range,
}; // The difference between any two SmallIndex values always fits in a // usize since we know that SmallIndex::MAX <= isize::MAX-1. We also // know that start<=end by construction and that the number of groups // never exceeds SmallIndex and thus never overflows usize. 1 + ((end.as_usize() - start.as_usize()) / 2)
}
/// Return the total number of slots in this capture slot info as a /// "small index." fn small_slot_len(&self) -> SmallIndex { // Since slots are allocated in order of pattern (starting at 0) and // then in order of capture group, it follows that the number of slots // is the end of the range of slots for the last pattern. This is // true even when the last pattern has no capturing groups, since // 'slot_ranges' will still represent it explicitly with an empty // range. self.slot_ranges.last().map_or(SmallIndex::ZERO, |&(_, end)| end)
}
}
/// An error that may occur when building a `GroupInfo`. /// /// Building a `GroupInfo` does a variety of checks to make sure the /// capturing groups satisfy a number of invariants. This includes, but is not /// limited to, ensuring that the first capturing group is unnamed and that /// there are no duplicate capture groups for a specific pattern. #[derive(Clone, Debug)] pubstruct GroupInfoError {
kind: GroupInfoErrorKind,
}
/// The kind of error that occurs when building a `GroupInfo` fails. /// /// We keep this un-exported because it's not clear how useful it is to /// export it. #[derive(Clone, Debug)] enum GroupInfoErrorKind { /// This occurs when too many patterns have been added. i.e., It would /// otherwise overflow a `PatternID`.
TooManyPatterns { err: PatternIDError }, /// This occurs when too many capturing groups have been added for a /// particular pattern.
TooManyGroups { /// The ID of the pattern that had too many groups.
pattern: PatternID, /// The minimum number of groups that the caller has tried to add for /// a pattern.
minimum: usize,
}, /// An error that occurs when a pattern has no capture groups. Either the /// group info must be empty, or all patterns must have at least one group /// (corresponding to the unnamed group for the entire pattern).
MissingGroups { /// The ID of the pattern that had no capturing groups.
pattern: PatternID,
}, /// An error that occurs when one tries to provide a name for the capture /// group at index 0. This capturing group must currently always be /// unnamed.
FirstMustBeUnnamed { /// The ID of the pattern that was found to have a named first /// capturing group.
pattern: PatternID,
}, /// An error that occurs when duplicate capture group names for the same /// pattern are added. /// /// NOTE: At time of writing, this error can never occur if you're using /// regex-syntax, since the parser itself will reject patterns with /// duplicate capture group names. This error can only occur when the /// builder is used to hand construct NFAs.
Duplicate { /// The pattern in which the duplicate capture group name was found.
pattern: PatternID, /// The duplicate name.
name: String,
},
}
matchself.kind {
TooManyPatterns { ref err } => {
write!(f, "too many patterns to build capture info: {}", err)
}
TooManyGroups { pattern, minimum } => {
write!(
f, "too many capture groups (at least {}) were \
found for pattern {}",
minimum,
pattern.as_usize()
)
}
MissingGroups { pattern } => write!(
f, "no capturing groups found for pattern {} \
(either all patterns have zero groups or all patterns have \
at least one group)",
pattern.as_usize(),
),
FirstMustBeUnnamed { pattern } => write!(
f, "first capture group (at index 0) for pattern {} has a name \
(it must be unnamed)",
pattern.as_usize(),
),
Duplicate { pattern, ref name } => write!(
f, "duplicate capture group name '{}' found for pattern {}",
name,
pattern.as_usize(),
),
}
}
}
/// An iterator over capturing groups and their names for a specific pattern. /// /// This iterator is created by [`GroupInfo::pattern_names`]. /// /// The lifetime parameter `'a` refers to the lifetime of the `GroupInfo` /// from which this iterator was created. #[derive(Clone, Debug)] pubstruct GroupInfoPatternNames<'a> {
it: core::slice::Iter<'a, Option<Arc<str>>>,
}
impl<'a> ExactSizeIterator for GroupInfoPatternNames<'a> {} impl<'a> core::iter::FusedIterator for GroupInfoPatternNames<'a> {}
/// An iterator over capturing groups and their names for a `GroupInfo`. /// /// This iterator is created by [`GroupInfo::all_names`]. /// /// The lifetime parameter `'a` refers to the lifetime of the `GroupInfo` /// from which this iterator was created. #[derive(Debug)] pubstruct GroupInfoAllNames<'a> {
group_info: &'a GroupInfo,
pids: PatternIDIter,
current_pid: Option<PatternID>,
names: Option<core::iter::Enumerate<GroupInfoPatternNames<'a>>>,
}
impl<'a> Iterator for GroupInfoAllNames<'a> { type Item = (PatternID, usize, Option<&'a str>);
fn next(&mutself) -> Option<(PatternID, usize, Option<&'a str>)> { // If the group info has no captures, then we never have anything // to yield. We need to consider this case explicitly (at time of // writing) because 'pattern_capture_names' will panic if captures // aren't enabled. ifself.group_info.0.index_to_name.is_empty() { return None;
} ifself.current_pid.is_none() { self.current_pid = Some(self.pids.next()?);
} let pid = self.current_pid.unwrap(); ifself.names.is_none() { self.names = Some(self.group_info.pattern_names(pid).enumerate());
} let (group_index, name) = matchself.names.as_mut().unwrap().next() {
Some((group_index, name)) => (group_index, name),
None => { self.current_pid = None; self.names = None; returnself.next();
}
};
Some((pid, group_index, name))
}
}
Messung V0.5 in Prozent
¤ Dauer der Verarbeitung: 0.41 Sekunden
(vorverarbeitet am 2026-06-18)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
