How can I iterate over a delimited string, accumulating state from previous iterations without explicitly tracking the state?

user_1391064 0
Viewed 165

I want to produce an iterator over a delimited string such that each substring separated by the delimiter is returned on each iteration with the substring from the previous iteration, including the delimiter.

For example, given the string "ab:cde:fg", the iterator should return the following:

  1. "ab"
  2. "ab:cde"
  3. "ab:cde:fg"

Simple Solution

A simple solution is to just iterate over collection returned from splitting on the delimiter, keeping track of the previous path:

let mut state = String::new();
for part in "ab:cde:fg".split(':') {
    if !state.is_empty() {
        state.push_str(":");
    }
    state.push_str(part);
    dbg!(&state);
}

The downside here is the need to explicitly keep track of the state with an extra mutable variable.

Using scan

I thought scan could be used to hide the state:

    "ab:cde:fg"
        .split(":")
        .scan(String::new(), |state, x| {
            if !state.is_empty() {
                state.push_str(":");
            }
            state.push_str(x);
            Some(&state)
        })
        .for_each(|x| { dbg!(x); });

However, this fails with the error:

cannot infer an appropriate lifetime for borrow expression due to conflicting requirements

What is the problem with the scan version and how can it be fixed?

rust
2 Answers

Why even build a new string? You can get the indices of the : and use slices to the original string.

fn main() {
    let test = "ab:cde:fg";

    let strings = test
        .match_indices(":")            // get the positions of the `:`
        .map(|(i, _)| &test[0..i])     // get the string to that position
        .chain(std::iter::once(test)); // let's not forget about the entire string

    for substring in strings {
        println!("{:?}", substring);
    }
}

(Permalink to the playground)

user_27338510

First of all, let us cheat and get your code to compile, so that we can inspect the issue at hand. We can do so by cloning the state. Also, let's add some debug message:

fn main() -> () {
    "ab:cde:fg"
        .split(":")
        .scan(String::new(), |state, x| {  // (1)
            if !state.is_empty() {
                state.push_str(":");
            }
            state.push_str(x);
            eprintln!(">>> scan with {} {}", state, x);
            Some(state.clone())
        })
        .for_each(|x| {                    // (2)
            dbg!(x);
        });
}

This results in the following output:

scan with ab ab
[src/main.rs:13] x = "ab"
scan with ab:cde cde
[src/main.rs:13] x = "ab:cde"
scan with ab:cde:fg fg
[src/main.rs:13] x = "ab:cde:fg"

Note how the eprintln! and dbg! outputs are interleaved? That's the result of Iterator's laziness. However, in practice, this means that our intermediate String is borrowed twice:

  • in the anonymous function |state, x| in state (1)
  • in the anonymous function |x| in, well, x (2)

However, this would lead to duplicate borrows, even though at least one of them is mutable. The mutable borrow therefore enforces the lifetime of our String to be bound to the anonymous function, whereas the latter function still needs an alive String. Even if we somehow managed to annotate lifetimes, we would just end up with an invalid borrow in (2), as the value is still borrowed as mutable.

The easy way out is a clone. The smarter way out uses match_indices and string slices.

user_11396970
Related