How to implement generic intersperse with mutations possible

Question

Goal

Create function/macro which has an api like such:

fn writesperse(
    buf: &mut String,
    items: impl IntoIterator<Item=impl fmt::Display>,
    sep: impl fmt::Display,
) -> fmt::Result {
    // intersperse impl elided
}

with the main consumer of this api being a struct similar to:

use std::fmt;

// Drives building of query
struct QueryBuilder<'a> {
    buf: String,
    data: &'a Data,
    state: State,
}

impl<'a> QueryBuilder<'a> {
    // example method showing how writesperse might be used
    fn f(&mut self) -> fmt::Result {
        writesperse(
            &mut self.buf,
            self.data.names().map(|n| self.state.resolve(n)),
            ", ",
        )
    }
}

// Represents mutable container for computed values
struct State;
impl State {
    fn resolve(&mut self, _name: &str) -> &StateRef {
        // mutate state if name has not been seen before (elided)
        &StateRef
    }
}

// Represents example computed value
struct StateRef;
impl fmt::Display for StateRef {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "STATEREF")
    }
}

// Immutable container with various collections of objects
struct Data;
impl Data {
    // example iterator of references to some owned data
    fn names(&self) -> impl Iterator<Item=&str> {
        ::std::iter::once("name")
    }

    // another iterator of a different references
    fn items(&self) -> impl Iterator<Item=&DataRef> {
        ::std::iter::once(&DataRef)
    }
}

// Represents some type Data might own
struct DataRef;

Error

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:13:50
   |
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |                                                  ^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime '_ as defined on the body at 13:35...
  --> src/lib.rs:13:35
   |
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:13:39
   |
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |                                       ^^^^^^^^^^
note: but, the lifetime must be valid for the method call at 13:13...
  --> src/lib.rs:13:13
   |
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that a type/lifetime parameter is in scope here
  --> src/lib.rs:13:13
   |
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

What I've tried

My only success thus far has been to manually do the intersperse logic at each site where it is needed.

let mut iter = some_iter.into_iter();
if let Some(i) = iter.next() {
    // do any state mutation here so mutable reference is released
    let n = self.state.resolve(n);
    write!(&mut self.buf, "{}", n)?;
}

for i in iter {
    // do same thing above
}

If I try and make State::resolve immutable, (which means I would need to pre-compute the values which is not desirable), I get a different error.

error[E0502]: cannot borrow `self` as immutable because it is also borrowed as mutable
  --> src/lib.rs:13:35
   |
11 |         writesperse(
   |         ----------- mutable borrow later used by call
12 |             &mut self.buf,
   |             ------------- mutable borrow occurs here
13 |             self.data.names().map(|n| self.state.resolve(n)),
   |                                   ^^^ ---- second borrow occurs due to use of `self` in closure
   |                                   |
   |                                   immutable borrow occurs here

This error is easier to understand. However, I don't understand why what I am trying to do is disallowed. Why can I not hand out a mutable reference to QueryBuilder's buf and an iterator of references to objects within State and/or Data at the same time?

Ultimately, my number one priority is abstracting the intersperse logic into some function or macro which expects an Iterator<Item=fmt::Display>. It would be an added bonus if this Iterator could possibly mutate state and return a reference to its data. I don't think this is possible though, at least from my understanding of the streaming-iterator crate.

Thanks for your help!

Answer 1

writesperse is not the problem here, resolve is.

Because it takes &mut self and returns a reference with a lifetime bound to self, you can't call resolve a second time unless the reference obtained from the first call has been dropped. You can see this in this simplified f (compiler error interspersed):

// error[E0499]: cannot borrow `self.state` as mutable more than once at a time
fn f(&mut self) {
    let a = self.state.resolve("alec");
    //      ---------- first mutable borrow occurs here
    let _b = self.state.resolve("brian");
    //       ^^^^^^^^^^ second mutable borrow occurs here
    println!("{}", a);
    //             - first borrow later used here
}

Part of the contract of an Iterator is that it does not yield internal references. So |n| self.state.resolve(n) is simply not a closure that can be passed to Iterator::map.

Fixing resolve

If resolve took &self instead of &mut self, this would work because the closure would not need to borrow self.state exclusively; it could return references with the lifetime of the original without worrying about overlap. So let's try that:

fn resolve(&self, _name: &str) -> &StateRef {
    // some kind of interior mutability thing here, probably have to return
    // `std::cell:Ref<StateRef>` or `MutexGuard<StateRef>` instead, but that
    // doesn't matter for this demonstration
    &StateRef
}

Oh dear.

error[E0502]: cannot borrow `self` as immutable because it is also borrowed as mutable
  --> src/lib.rs:23:35
   |
21 |         writesperse(
   |         ----------- mutable borrow later used by call
22 |             &mut self.buf,
   |             ------------- mutable borrow occurs here
23 |             self.data.names().map(|n| self.state.resolve(n)),
   |                                   ^^^ ---- second borrow occurs due to use of `self` in closure
   |                                   |
   |                                   immutable borrow occurs here

What's going on? Because the closure uses self in a context where an immutable reference is required, the closure borrows self, and the &mut self.buf also borrows (part of) self mutably, and they both have to exist at the same time to pass into writesperse. So this looks like a dead end, but it's actually really close: it just needs a small change to f to compile.

fn f(&mut self) -> fmt::Result {
    let state = &self.state;
    writesperse(
        &mut self.buf,
        self.data.names().map(|n| state.resolve(n)),
        ", ",
    )
}

The compiler can reason about mutually exclusive partial borrows as long as they happen all within the body of a single function. The compiler will let you borrow self.state and mutably borrow self.buf at the same time as long as the borrows happen in the same function. Creating a variable to borrow self.state makes it so that only state is captured by the closure, not self.

Other options

The above works, if you're able to make resolve take &self. Here are some other ideas:

• You could attack the problem from the other direction: make resolve return StateRef by value so it doesn't extend the &mut borrow.
• You can achieve the same thing by altering the closure so that it doesn't return a reference; |n| state.resolve(n).to_string() works with no further changes (but it does do a bunch of unnecessary allocation and copying).
• You could use Arc or Rc instead of & references and defer all lifetime management to runtime.
• You could write a macro that does the repetitive part for you so that writesperse is not necessary.

See also

• How do I return a reference to something inside a RefCell without breaking encapsulation? if you need to use interior mutability to make resolve take &self
• Mutable borrow of self doesn't change to immutable explains why state is still considered "mutably borrowed" after resolve returns