# Substring slice pattern matching

**URL:** <https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814>\
**Category:** language design\
**Created:** [June 13, 2022, 7:25pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814 "2022-06-13T19:25:16Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![afetisov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/afetisov/32/8508_2.png) [@afetisov](https://internals.rust-lang.org/u/afetisov)\
**Post date:** [June 13, 2022, 7:25pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/1 "2022-06-13T19:25:16Z")

</div>

I could not find the following proposal discussed anywhere, which is surprising, since it looks like a very natural addition.

The proposal is to add substring pattern syntax for pattern-matching, which would serve the same purpose as the slice patterns for slices and arrays. The syntax is prone to bikeshedding, but imho it would be most natural to generalize `concat!` and `concat_bytes!` built-in macros to allow using them in pattern position.

An example which would be easier with this proposal:

```rust
// before
fn frobnicate_str(s: &str) -> Frob {
    if s.starts_with("foo") || s.starts_with("moo") {
        frobnicate(&s["foo".len()..])
    } else if s.starts_with("bozoom") {
        frobnicate(&s["bozoom".len()..])
    } else if s.starts_with("ba") {
        barnicate(&s["ba".len()..])
    } else if s.ends_with("quux") {
        quuxnicate(&s[..s.len() - "quux".len()])
    } else {
        panic!("not a frobnicatable string")
    }
}

// after
fn frobnicate_str(s: &str) -> Frob {
    match s {
        concat!("foo" | "moo" | "bozoom", rest@..) => frobnicate(rest),
        concat!("ba", rest@..) => barnicate(rest),
        concat!(start@.., "quux") => quuxnicate(&start),
        _ => panic!("not a frobnicatable string"),
    }
}

```

In my opinion, a match is easier to read that a chain of ifs: the conditions are very explicit, the pattern matching allows to encode complex conditions in a simple form, and the compiler guarantees exhaustive checks.

A similar construct should be added to allow matching on byte slices, i.e.

```rust
fn frobnicate_slice(s: &[u8]) -> Frob {
    match s {
        concat_bytes!(b"foo" | b"moo" | b"bozoom", rest@..) => frobnicate(rest),
        concat_bytes!(b"ba", rest@..) => barnicate(rest),
        concat_bytes!(start@.., b"quux") => quuxnicate(&start),
        _ => panic!("not a frobnicatable string"),
    }
}

```

Note that I do not propose to expand the pattern syntax in any way beyond `concat!` and `concat_bytes!`. In particular, allowing non-literal slices in the pattern, or patterns for containers such as String or Vec, or custom pattern matching, or allowing more than one variable-length pattern are beyond the scope of proposal.

Note that this is more of a syntax sugar than any real extension of the language's expressive power. For byte strings in particular, a pattern match

```rust
if let concat_bytes!(b"foo" | b"quux", rest@..) = b { ... }

```

can be equivalently rewritten to

```rust
if let [b'f', b'o', b'o', rest@..] | [b'q', b'u', b'u', b'x', rest@..] = b { ... }

```

However, the first pattern is much easier to read and write.

For strings, there is currently no direct equivalent of slice patterns. One could match the string slice as a byte slice and manually transcribe a string pattern into the corresponding byte pattern:

```rust
if let [b'f', b'o', b'o', rest@..] = s.as_bytes() { ...}

```

However, this is even less practical than for byte slices in cases where the string pattern goes beyond the ASCII range of characters. Also, `rest` will be a byte slice within the match arm, so if we need to work with actual strings, then we must convert it back into a string slice, either performing redundant utf8 checks or using error-prone unsafe code.

## Syntax

In the current proposal the obvious, although somewhat clunky, pattern syntax `concat(_bytes)!(p1, ..., pn)` is used. Since `concat(_bytes)!` is a macro, if a better syntax is ever found, the migration to new syntax can be made seamless by changing the expansion of the macros to the new pattern syntax. Also, since `concat(_bytes)!` is a built-in macro, there is nothing preventing it from supporting the new patterns even if there is currently no non-macro way to express them in the language (just as there is currently no other way to concatenate compile-time slices).

The expansion of the macro doesn't need to know the surrounding context (i.e. whether it is expanded in pattern position), since adding the pattern syntax is backwards-compatible. Currently the only valid syntax is a concatenation of slice literals, and the macro expand to their concatenation. With this proposal the concatenation of slices is still a slice, just as before. However, it would be now possible to use more general slice patterns within the macro, in which case it would expand to some (for the moment unstable) slice pattern.

If Rust had a slice concatenation operator (say `++`), then the most natural syntax for string patterns would use `++` instead of `concat!`. I find it unlikely that such operator would ever be added, though.

## Semantics

The byte string patterns with `concat_bytes!` can be directly desugared to the stable slice patterns as above, assuming that there are no or-patterns within the `concat_bytes!` call. This means that, in particular, arrays can also be matched with the byte string patterns just like with the usual slice patterns.

Nested or-patterns present the same challenges as any other or-patterns. In principle, they can be directly desugared into sequences of ordinary patterns. In practice, this can lead to an exponential code blowup for deeply nested or-patterns, so some smarter algorithm may be desirable.

String slice patterns with `concat!` do not currently have a stable analogue. One option is to introduce special unstable string slice patterns, just like `core::ptr::addr_of!` expands to an unstable `&raw` reference. Another option is to desugar string slice patterns into byte slice patterns, together with conversions to and from a byte slice.

## Alternatives

For byte slices, the currently stable slice patterns allow to do express the same pattern matching as proposed above. However, this involves manually converting byte slices into explicit arrays of individual bytes, which is tedious and confusing when the byte slices actually represent ASCII strings.

For string slices, the stable alternative is to use the string splitting, pattern matching and subslice functions to manually implement pattern matching. This involves more boilerplate code, redundant definitions of the matched strings (possibly extracted to local variables), or manually computed and hardcoded offsets based on the lengths of fixed suffixes and prefixes. For ad-hoc parsing this can result in quite complex code, viz. the example at the start.

---

<div class="post-metadata">

**Author:** ![mjbshaw](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mjbshaw/32/5103_2.png) [@mjbshaw](https://internals.rust-lang.org/u/mjbshaw)\
**Post date:** [June 13, 2022, 8:08pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/2 "2022-06-13T20:08:36Z")

</div>

`strip_prefix` and `strip_suffix` really weaken the argument since they greatly simplify the original code.

---

<div class="post-metadata">

**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\
**Post date:** [June 13, 2022, 8:27pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/3 "2022-06-13T20:27:02Z")

</div>

Wouldn't the gold standard here be regex? I would wonder what is the minimum number of features necessary to get this working:

```rust
use regex::r;

fn frobnicate_str(s: &str) -> Frob {
    match s {
        r!("(foo|moo|bozoom)(?P<rest>.*)") => frobnicate(rest),
        r!("ba(?P<rest>.*)") => barnicate(rest),
        r!("(?P<start>)quux") => quuxnicate(&start),
        _ => panic!("not a frobnicatable string"),
    }
}

```

Or something very close to this. When I first discovered the regex library in rust this is actually how I expected it to work!

---

<div class="post-metadata">

**Author:** ![jkugelman](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jkugelman/32/8572_2.png) [@jkugelman](https://internals.rust-lang.org/u/jkugelman)\
**Post date:** [June 13, 2022, 8:44pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/4 "2022-06-13T20:44:53Z")

</div>

> [@mjbshaw](#):
>
> `strip_prefix` and `strip_suffix` really weaken the argument since they greatly simplify the original code.

For comparison, using them you get:

```rust
fn frobnicate_str(s: &str) -> Frob {
    if let Some(rest) = s.strip_prefix("foo") {
        frobnicate(rest)
    } else if let Some(rest) = s.strip_prefix("moo") {
        frobnicate(rest)
    } else if let Some(rest) = s.strip_prefix("bozoom") {
        frobnicate(rest)
    } else if let Some(rest) = s.strip_prefix("ba") {
        barnicate(rest)
    } else if let Some(start) = s.strip_suffix("quux") {
        quuxnicate(start)
    } else {
        panic!("not a frobnicatable string")
    }
}

```

Or:

```rust
fn frobnicate_str(s: &str) -> Frob {
    if let Some(rest) = s.strip_prefix("foo")
        .or_else(|| s.strip_prefix("moo"))
        .or_else(|| s.strip_prefix("bozoom"))
    {
        frobnicate(rest)
    } else if let Some(rest) = s.strip_prefix("ba") {
        barnicate(rest)
    } else if let Some(start) = s.strip_suffix("quux") {
        quuxnicate(start)
    } else {
        panic!("not a frobnicatable string")
    }
}

```

---

<div class="post-metadata">

**Author:** ![jjpe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jjpe/32/9779_2.png) [@jjpe](https://internals.rust-lang.org/u/jjpe)\
**Post date:** [June 13, 2022, 9:41pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/5 "2022-06-13T21:41:54Z")

</div>

> [@toc](#):
>
> Wouldn't the gold standard here be regex?

That depends. In terms of expressiveness, most likely yes. However, regexes have `O(2^n)` runtime behavior, which no non-nested match expression exhibits today.

This is also an issue with `.ends_with()` although there the code is `O(n)`. Still, it could silently and suddenly make matches much more expensive.

---

<div class="post-metadata">

**Author:** ![Inky-developer](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/inky-developer/32/8175_2.png) [@Inky-developer](https://internals.rust-lang.org/u/Inky-developer)\
**Post date:** [June 13, 2022, 10:18pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/6 "2022-06-13T22:18:52Z")

</div>

I am not advocating for regex match support (A macro would probably be good enough), but using actual regular regexes would have great performance. The compiler could match all regexes simultaneously using a product automaton which would make the overall match time O(n) where n is the string length

---

<div class="post-metadata">

**Author:** ![jjpe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jjpe/32/9779_2.png) [@jjpe](https://internals.rust-lang.org/u/jjpe)\
**Post date:** [June 13, 2022, 10:34pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/7 "2022-06-13T22:34:44Z")

</div>

> [@Inky-developer](#):
>
> The compiler could match all regexes simultaneously using a product automaton which would make the overall match time O(n) where n is the string length

Not really no. It could be `O(m * n)` though, if it's based on the `regex` crate:

> [@](#):
>
> Untrusted search text is allowed because the matching engine(s) in this crate have time complexity `O(mn)` (with `m ~ regex` and `n ~ search text` ), which means there’s no way to cause exponential blow-up like with some other regular expression engines. (We pay for this by disallowing features like arbitrary look-ahead and backreferences.)

Now while this is at least polynomial and not exponential worst case such as in some other languages, it's still easily more expensive than is naively expected from a match expr.

---

<div class="post-metadata">

**Author:** ![burntsushi](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/burntsushi/32/279_2.png) [@burntsushi](https://internals.rust-lang.org/u/burntsushi)\
**Post date:** [June 13, 2022, 10:57pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/8 "2022-06-13T22:57:55Z")

</div>

> [@Inky-developer](#):
>
> I am not advocating for regex match support (A macro would probably be good enough), but using actual regular regexes would have great performance. The compiler could match all regexes simultaneously using a product automaton which would make the overall match time O(n) where n is the string length

Given your example, I believe this is not possible. In particular, your example includes the use of capturing groups and, importantly, extracting the match positions of specific capturing groups. This requires something strictly more powerful than a simple automaton (namely, a tagged automaton). You can flub simple automata to give you match offsets, but that's about as far as you can get.

> [@jjpe](#):
>
> Now while this is at least polynomial and not exponential worst case such as in some other languages, it's still easily more expensive than is naively expected from a match expr.

If no regexes are used in the match loop, then you can provide a stricter time guarantee.

(I've specifically avoided trying to have an opinions on whether we "should" do any of this or not. I just wanted to clarify things about regexes.)

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [September 11, 2022, 10:58pm UTC](https://internals.rust-lang.org/t/substring-slice-pattern-matching/16814/9 "2022-09-11T22:58:03Z")

</div>

Closed on September 11, 2022, 10:58pm UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.