Lesser (and more efficient) of two evils


#1

I need to link a tree-like hashmap. Since this involved mutating a structure being iterated over, Rust doesn’t like it. Premature Optimization is the root of all evil yet I don’t like copying all the keys in the first version. My C brain certainly has no problem with the second version.

Is it too unsafe to use? Or maybe there are better ways of going about this?


Struct used:

struct Info {
    requirements: Vector<String>, // Ready
    unlocks: Vector<String>, // Needs to be filled
}

First version:

fn fix_unlocks_dance(mut tree: HashMap<String, Info>) -> HashMap<String, Info> {
    let tree_keys = tree.keys().cloned().collect::<Vec<String>>();
    for key in tree_keys {
        let moved_req;
        {
            let requirements = &mut tree.get_mut(&key).unwrap().requirements;
            moved_req = std::mem::replace(requirements, Vec::new());
        }
        for requirement in &moved_req {
            tree.get_mut::<str>(requirement).unwrap().unlocks.push(key.clone());
        }
        std::mem::replace(&mut tree.get_mut(&key).unwrap().requirements, moved_req);
    }
    tree
}

Second version:

fn fix_unlocks_evil(mut tree: HashMap<String, Info>) -> HashMap<String, Info> {
    let tree_cell = UnsafeCell::new(tree);
    unsafe {
        for (key, info in &*tree_cell.get() {
            for requirement in &info.requirements {
                // This is where this gets uncomfortable 
                (*tree_cell.get()).get_mut(requirement).unwrap().unlocks.push(key.clone());
            }
        }
        tree_cell.into_inner()
    }
}

#2

I’d also say that the “evil” version is ok, but unsafe is always a bit of a wart…

I don’t know the rest of the code but just for this algorithms I’d probably use two separate trees (HashMap<Vector<String>>) instead of a single one.
You never need requirements and unlocks of the same key at the same time, there’s not really an advantage of keeping them together.

Another possibility would be a two-step algorithm using an intermediate tree.

Or, since you return the tree by value anyway you could also build up an entirely new tree by using drain() on the old tree and reusing the keys and values. But this is probably already more overhead than copying all the keys…


#3

You could use a

struct Info {
    requirements: Vector<String>, // Ready
    unlocks: RefCell<Vector<String>>, // Needs to be filled
}