Add convenience methods for extracting bits of text

[orlp]

A lot of my use cases for regex involve extracting some information from text with a simple pattern, where full parsing would be overkill. In this scenario I generally just have N subsections of the text I'm looking to extract (possibly many times), where N is a small constant. Some examples from the recent advent of code:

let re = Regex::new(r"target area:\s*x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)")?;
let re = Regex::new(r"Player 1 starting position:\s*(\d)\s*Player 2 starting position:\s*(\d)\s*")?;
let re = Regex::new(r"(on|off)\s+x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)")?;

In such a scenario it is quite the pain to extract the information I want using the current API. It generally involves something like this, for the last example:

use anyhow::Context;
use itertools::Itertools;
let (status, x1, x2, y1, y2, z1, z2) = re
    .captures(&line)
    .context("match failed")?
    .iter()
    .skip(1)
    .map(|c| c.unwrap().as_str())
    .collect_tuple()
    .unwrap();

Note that I already had to include a third-party library itertools just to get collect_tuple, without that we would either have to start repeatedly calling next() or get(i), or invoke an unnecessary allocation, and in both cases an extra check is needed to ensure there weren't too many captures (indicating a programmer error).

I think that adding a convenience method for this incredibly common use-case would be nice. I would propose the following (with sample implementation):

/// Finds the leftmost-first match in `text` and returns a tuple containing the whole match
/// and its N participating capture groups as strings. If no match is found, `None` is returned.
///
/// # Panics
///
/// Panics if the number of participating captures is not equal to N.
fn extract<'t, const N: usize>(&self, text: &'t str) -> Option<(&'t str, [&'t str; N])> {
    let caps = re.captures(text)?;
    let mut participating = caps.iter().flatten();
    let whole_match = participating.next().unwrap().as_str();
    let captured = [0; N].map(|_| participating.next().unwrap().as_str());
    assert!(participating.next().is_none(), "too many participating capture groups");
    Some((whole_match, captured))
}

And similarly extract_iter returning impl Iterator<Item = (&'t str, [&'t str; N])>.

---

Then, the cumbersome example above would become the elegant:

let [status, x1, x2, y1, y2, z1, z2] = re.extract(&line).context("match failed")?.1;

Another example from the README:

let re = Regex::new(r"(\d{4})-(\d{2})-(\d{2})").unwrap();
for caps in re.captures_iter(TO_SEARCH) {
    // Note that all of the unwraps are actually OK for this regex
    // because the only way for the regex to match is if all of the
    // capture groups match. This is not true in general though!
    println!("year: {}, month: {}, day: {}",
                caps.get(1).unwrap().as_str(),
                caps.get(2).unwrap().as_str(),
                caps.get(3).unwrap().as_str());
}

This could become:

let re = Regex::new(r"(\d{4})-(\d{2})-(\d{2})").unwrap();
for (_date, [year, month, day]) in re.extract_iter(TO_SEARCH) {
    println!("year: {}, month: {}, day: {}", year, month, day);
}

---

Caveats

This API does panic, but I believe that this is fine. It will only ever panic due to a direct programmer error (mismatching possibly participating capture groups to the number of outputs), which would always have been wrong, and does not represent an exceptional but otherwise valid scenario. And for anyone for which this is not acceptable, they can always still use the original API.

Additionally, we call .flatten() on the capturing groups to hide any non-participating capturing groups. I do believe this is actually fine as well, allowing uses cases such as this, where we have an alternation with a similar capture group on either side, without wanting to capture the context:

let id_strings_re = Regex::new(r#""id:([^"]*)"|'id:([^']*)'"#)?;
let [id] = id_strings_re.extract(text).unwrap().1;

If this would be a welcome addition I'm more than happy to make a pull request.

[BurntSushi]

I do find this somewhat intriguing. Const generics does make this sort of API reasonably appealing.

I haven't given this a ton of thought yet, but one question did pop up. Toward the end, you mention that capturing groups are flattened to remove non-participating capturing groups. You provide an example where both sides of an alternation have the same number of captures. But what happens when both sides of the branch have a different number of capturing groups? I believe in such a case, it seems almost impossible to correctly use this new extract API. Because the size of the array returned is determined at compile time, but because of the flattening, the actual number of capture matches is determined at runtime. So it's impossible to reconcile.

I'm not saying that this means we shouldn't add an API like this, but it seems like a possible footgun to me. And I don't think it's a terribly uncommon use case, although certainly not as common as others.

[orlp]

But what happens when both sides of the branch have a different number of capturing groups? I believe in such a case, it seems almost impossible to correctly use this new extract API. Because the size of the array returned is determined at compile time, but because of the flattening, the actual number of capture matches is determined at runtime. So it's impossible to reconcile.

Yes, I would consider this a programmer error. There are three ways we could deal with it:

1. As it is now in the sample implementation, only panic if the number of matched participating groups differs from N. A bit questionable, because your program might seem to work correctly in testing, but panic and fail for a different input.

2. During regex compilation, keep track of the number of capture groups in the syntax tree. When a|b occurs in the regex, and the number of capture groups for a and b differs, set a flag. Then, extract will check this flag at the start, and if set, immediately panic. (This does assume this problem can only be introduced due to alternation, correct me if I'm wrong on this.)

3. Don't allow any 'fallible capture groups' (that is, a capture group inside an alternation, or any other such constructs I've missed) whatsoever when using extract, again by checking and setting a flag during compilation. I think this is unnecessarily strict.

[BurntSushi]

I think it can be introduced in other ways, e.g., (?:(\w)(\s))? might have 2 or 0 capturing groups. But either way, your suggestion is I believe workable: such a property is something that can be detected by analyzing the syntax of the regex.

[orlp]

And I'm sure that there's valid regexes that can be proven to always have the same number of capturing groups that would be excluded by such a static analysis. This would be the advantage of approach nr. 1, nothing would be disallowed. But I do think approach nr. 2 is the most sensible for most users, preventing accidental footguns. Then you can be sure that if it works in testing, it always works. Again, people can always use the original API if they want full flexibility.

Briefly browsing through the source code I think adding a 'deterministic capture group' check to Hir shouldn't be too difficult by adding a method fn deterministic_capture_group_count(&self) -> Option<usize> which recursively computes the value, using the basic rules such that an Alternation HirKind's children must all have an equal Some(x), else the result is None. This value is then computed once during regex compilation near the end, and stored, and extract can then check

assert_eq!(exec.ro.deterministic_capture_group_count, Some(N), "extract must always have N capture groups")

[BurntSushi]

Ideally such properties are computed inductively and not recursively. The Hir type has a bunch of "smart" constructors for exactly this reason, and indeed, they are the only public way to compose regular expression syntactic values, precisely so that a number of properties can be computed inductively. This avoids needing to do another recursive pass on the syntax tree.

In any case, I haven't fully decided whether this is an API I'd want. I need to noodle on it. And ultimately get more eyes on it, since once it's added, that's it. No going back.

[orlp]

Alright, fair enough, in that case it would be an attribute on HirInfo. Out of curiosity I went over the cases and came up with this:

For empty(), literal(), class(), anchor(), word_boundary():

info.det_capture_count = Some(0);

For repetition(rep):

info.det_capture_count = match (rep.kind, rep.hir.det_capture_count) {
    // Always zero.
    (_, Some(0)) => Some(0),
    (RepetitionKind::Range(RepetitionRange::Exactly(0)), _) => Some(0),
    (RepetitionKind::Range(RepetitionRange::Bounded(_, 0)) => Some(0),

    // Nondeterministic.
    (RepetitionKind::ZeroOrOne, _) => None,
    (RepetitionKind::ZeroOrMore, _) => None,
    (RepetitionKind::Range(RepetitionRange::AtLeast(0)), _) => None,
    (RepetitionKind::Range(RepetitionRange::Bounded(0, _)) => None
    
    // Deterministic.
    (RepetitionKind::OneOrMore, Some(n)) => Some(n),
    (RepetitionKind::Range(RepetitionRange::Exactly(_)), Some(n)) => Some(n),
    (RepetitionKind::Range(RepetitionRange::AtLeast(_)), Some(n)) => Some(n),
    (RepetitionKind::Range(RepetitionRange::Bounded(_, _)), Some(n)) => Some(n),
};

For group(grp):

info.det_capture_count = match grp.kind {
    GroupKind::CaptureIndex(_) => grp.hir.info.det_capture_count.map(|n| n + 1),
    GroupKind::CaptureName(_) => todo!("unresolved question: disallowing named captures, or treat as unnamed?"),
    GroupKind::NonCapturing(_) => grp.hir.info.det_capture_count,
};

For concat(exprs):

info.det_capture_count = exprs.iter().fold(Some(0), |cnt, e| Some(cnt? + e.info.det_capture_count?));

For alternation(exprs):

info.det_capture_count = exprs.iter().reduce(|a, b| (a? == b?).then(|| a.unwrap())).unwrap_or(Some(0));

It does lead to an unresolved question: what should we do regarding named capture groups when using extract?

[BurntSushi]

I think they get treated as unnamed groups. Every capturing group, whether named or not, is addressable by index. And this API merely requires that groups are indexable, which is satisfied by all such groups. Named groups just give a name to a group in addition to an index.

[orlp]

Ok, that makes sense, then it's just

GroupKind::CaptureIndex(_) | GroupKind::CaptureName(_) => grp.hir.info.det_capture_count.map(|n| n + 1),

[orlp]

In any case, I haven't fully decided whether this is an API I'd want. I need to noodle on it. And ultimately get more eyes on it, since once it's added, that's it. No going back.

How is the noodling coming along? As a summary refresher I believe we agreed on a static analysis method being feasible to allow a deterministic number of capture groups be efficiently determined during Regex compile time. This would allow

/// Finds the leftmost-first match in `text` and returns a tuple containing the whole match
/// and its N participating capture groups as strings. If no match is found, `None` is returned.
///
/// # Panics
///
/// Panics if the number of participating captures is not equal to N, or is non-deterministic.
fn extract<'t, const N: usize>(&self, text: &'t str) -> Option<(&'t str, [&'t str; N])>

to always immediately panic when called with an incorrect N or if the regex has an non-deterministic number of capture groups. This makes the extract method either always succeed or always fail, and never a footgun depending on the text input, which was your main concern on the initial proposal. The existence of this method would make using regex (in my opinion) vastly more convenient to use for extracting matches from text, e.g. replacing

use anyhow::Context;
use itertools::Itertools;
let re = Regex::new(r"(on|off)\s+x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)")?;
let (status, x1, x2, y1, y2, z1, z2) = re
    .captures(&line)
    .context("match failed")?
    .iter()
    .skip(1)
    .map(|c| c.unwrap().as_str())
    .collect_tuple()
    .unwrap();

with

use anyhow::Context;
let re = Regex::new(r"(on|off)\s+x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)")?;
let [status, x1, x2, y1, y2, z1, z2] = re.extract(&line).context("match failed")?.1;

[BurntSushi]

Is it possible to provide a bigger code example? Looking at your samples with fresh eyes, they look unnecessarily convoluted by the fact that you're using tuples. But if you're using tuples, why not just use capture indexing instead? Because you have a tuple, you must know the number of capturing groups at compile time. For example:

let (x, y, z) = (caps[1], caps[2], caps[3]);

I believe this is equivalent to your code but much simpler.

[orlp]

I believe this is equivalent to your code but much simpler.

Well, to be apples to apples with the previous example we have to extract all seven parts:

use anyhow::Context;
let re = Regex::new(r"(on|off)\s+x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)")?;
let caps = re.captures(&line).context("match failed")?;
let (status, x1, x2, y1, y2, z1, z2) = (caps[1], caps[2], caps[3], caps[4], caps[5], caps[6], caps[7]);

This sort of approach really smells though, for multiple reasons:

1. We have hardcoded a loop over the captures using manual indexing. This is error prone, and boiler-platey.

2. This code is not actually equivalent in the sense that we have lost the panic when we mess up and mis-match the number of capture groups to our extraction. For example, say we no longer needed the status but forgot to remove the capture group from the regex, and introduced this bug:

   let re = Regex::new(r"(on|off)\s+x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)")?;
   let caps = re.captures(&line).context("match failed")?;
   let (x1, x2, y1, y2, z1, z2) = (caps[1], caps[2], caps[3], caps[4], caps[5], caps[6]);

   This would just silently 'succeed' because our indexing scheme does not check that the number of capture groups matches our extraction. The extract method would correctly instantly panic, as would the collect_tuple.

3. The indexing scheme is less flexible because it does not flatten deterministically determined capture groups. E.g. consider an (overly) simplified regex for extracting URLs from HTML:

   let re = Regex::new(r#"<(a)[^>]+href="([^"]+)"|<(img)[^>]+src="([^"]+)""#);
   for (_el, [tag, url]) in re.extract_iter(&html).context("match failed")? {
       println!("{tag} {url}");
   }

   You can't do this with the indexing API, because we have four capture groups that alternatingly participate.

4. The indexing approach also suffers from your initially raised footgun: captures can participate or not depending on the user input. Because we haven't done any static checking for deterministic capture groups the indexing approach might succeed with test inputs but fail in production. With extract and extract_iter we can rest easy that our number of capture groups always matches our intent exactly, regardless of the string being matched.

[BurntSushi]

Those are good points.

Does the ecosystem have a way of introducing unstable APIs into crates? I'm not convinced we can get this right on our first try. It would be better I think to make it available somehow without committing to it to see how it gets used in practice.