Mutating vector elements in HashMap<String, Vec<&mut String>>

Question

I've boiled a problem I'm seeing down to this example:

use std::collections::HashMap;

fn process(mut inputs: Vec<String>) -> Vec<String> {

    // keep track of duplicate entries in the input Vec
    let mut duplicates: HashMap<String, Vec<&mut String>> = HashMap::new();
    for input in &mut inputs {
        duplicates.entry(input.clone())                                                                               
                  .or_insert_with(|| Vec::new())                                                                      
                  .push(input);
    }
    
    // modify the input vector in place to append the number of each duplicate
    for (key, instances) in duplicates {
        for (i, instance) in instances.iter().enumerate() {
            *instance = format!("{}_{}", instance, i);
        }
    }
    
    return inputs;
}

fn main() {
    println!("results: {:?}", process(vec![
        String::from("test"),
        String::from("another_test"),
        String::from("test")
    ]));
}

I would expect this to print something like results: test_0, another_test_0, test_1 but am instead running into build issues:

error[E0308]: mismatched types
  --> src/main.rs:13:25
   |
13 |             *instance = format!("{}_{}", instance, i);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `&mut String`, found struct `String`
   |

I'm still a bit new to rust and so haven't really found anything online that has helped. I'm hoping that I'm doing something silly. Thanks in advance for the help!

Answer 1

The problem you're facing is that immutability is transitive.

That is, coming from other languages you might expect that a & &mut Foo would let you dereference the outer ref', access the inner mutable ref, and update the Foo based on that. However if you consider the purpose of rust's unique references, this would be the same as allowing multiple mutable references: take a mutable reference, create any number of immutable references to it, and any holder of one such would be able to modify the original object, concurrently.

Therefore that's not acceptable. All references in a chain must be unique (&mut) in order to get mutable access to what's at the end of the chain, and so you need to instances.iter_mut(), and dereference twice (otherwise you're assigning to the &mut String at the first level, not the inner String), and for that you need instances itself to be mutable:

    for (_, mut instances) in duplicates {
        for (i, instance) in instances.iter_mut().enumerate() {
            **instance = format!("{}_{}", instance, i);
        }
    }

alternatively since you don't care about duplicates' keys:

    for instances in duplicates.values_mut() {
        for (i, instance) in instances.iter_mut().enumerate() {
            **instance = format!("{}_{}", instance, i);
        }
    }

Answer 2

for (key, instances) in duplicates {
    for (i, instance) in instances.iter().enumerate() {
        *instance = format!("{}_{}", instance, i);
    }
}

for (key, instances) in duplicates invokes the IntoIterator trait on HashMap<String, Vec<&mut String>>, with

type Item = (String, Vec<&mut String>);

so instances: Vec<&mut String>.¹ instances.iter() then produces references to the elements of instances, so instance: &&mut String. So instance would need to be dereferenced twice in order to access the element in inputs, which, unfortunately, doesn't actually work:

error[E0594]: cannot assign to `**instance` which is behind a `&` reference
  --> src/main.rs:14:13
   |
13 |         for (i, instance) in instances.iter().enumerate() {
   |                 -------- help: consider changing this to be a mutable reference: `&mut &mut String`
14 |             **instance = format!("{}_{}", instance, i);
   |             ^^^^^^^^^^ `instance` is a `&` reference, so the data it refers to cannot be written

The problem is that we are not allowed to modify the T value behind &&mut T. Here's the reason: immutable references can be freely copied, so there may be multiple &&mut T instances pointing to the same &mut T, defeating the anti-aliasing property of &mut.

Therefore, we have to change the type of instance to &mut &mut String, by using mut and .iter_mut():

for (key, mut instances) in duplicates {
    for (i, instance) in instances.iter_mut().enumerate() {
        **instance = format!("{}_{}", instance, i);
    }
}

Since key isn't needed, we can use .values_mut(), so that instances itself becomes an &mut:

for instances in duplicates.values_mut() {
    for (i, instance) in instances.iter_mut().enumerate() {
        **instance = format!("{}_{}", instance, i);
    }
}

¹ We'll use var: type to denote that var is of type type.

---

In general, references (especially mutable ones) stored in containers are tedious to work with, so I recommend an alternative approach: (with an in-place interface for simplicity)

use std::{collections::HashMap, fmt::Write};

fn process(texts: &mut Vec<String>) {
    let mut counter = HashMap::<String, usize>::new();

    for text in texts.iter_mut() {
        let count = counter.entry(text.clone()).or_insert(0);
        write!(text, "_{}", count).unwrap();
        *count += 1;
    }
}

(playground)

Answer 3

Iterating returns you references over the values stored in your map's vecs.

As your map's vecs contain references to start with, you have to dereference twice, using **.

You also need to use iter_mut when iterating if you want to change the content.

All in one, you can change your loop like this:

for (key, instances) in duplicates.iter_mut() {
    for (i, instance) in instances.iter_mut().enumerate() {
        **instance = format!("{}_{}", instance, i);
    }
}

playground