ChainMap

chainmap

This library provides a chain of HashMaps with interior mutability of each intermediate layer. The HashMaps are reference-counted, thus it is possible to create a tree of layers of HashMaps and not just a single chain.

The higher maps in the tree (close to the leaves) have higher priority.

One possible use case is for the management of nested scopes.

An example from the appropriate section of the Book: 15. Scoping rules - RAII

fn create_box() {
    // CreateBoxScope
    let _box1 = Box::new(3i32);
}

fn main() {
    // MainScope
    let _box2 = Box::new(5i32);
    {
        // NestedScope
        let box3 = Box::new(4i32);
    }

    for i in 0u32..1_000 {
        // LoopScope<i>
        create_box();
    }
}

Could be represented as

MainScope["_box2" => 5i32]
    ├── NestedScope["_box3" => 4i32]
    ├── LoopScope0[]
    │       └── CreateBoxScope["_box1" => 3i32]
    ├── LoopScope1[]
    │       └── CreateBoxScope["_box1" => 3i32]
    │   ...
    └── LoopScope999[]
            └── CreateBoxScope["_box1" => 3i32]

Where each [ $( $key => $value ),* ] is a level of a tree of ChainMaps built on the previous one.

This it turn could be declared as

let mut main_scope = ChainMap::new();
main_scope.insert("_box2", 5i32);

let mut nested_scope = main_scope.extend();
nested_scope.insert("_box1", 5i32);

let mut loop_scope = Vec::new();
for _ in 0..1000 {
    let mut h = HashMap::new();
    h.insert("_box1", 3i32);
    loop_scope.push(main_scope.extend().extend_with(h));
}

The rules for which map entries are accessible from a certain level of the ChainMap tree are exactly the same as how they would be for the corresponding scopes.

Questions

Why another chain map ?

There are already chain maps out there:

chain-map

hash-chain

However, both of these implementations of a chain map do not allow multiple branches from a single root, as they are wrappers around a Vec<HashMap<K, V>>.

On the other hand, this crate allows one to fork several maps out of a common root, saving memory usage at the cost of a less friendly internal representation: A Vec<HashMap<K, V>> is certainly better to work with than a tree of Option<Rc<(Mutex<HashMap<K, V>, Self)>>s.

Why require mut everywhere if there is interior mutability ?

The ChainMap could just as well take &self everywhere instead of requiring &mut self, and it would still work. After all, a Mutex can have its contents changed even if its container is immutable.

There are two reasons for not making all methods take &self:

1. Despite interior mutability, it would feel weird to insert into a non-mut structure.

   A HashMap requires mut to insert, and I wanted the ChainMap to feel like a HashMap as much as possible, hence the choice of the same method names insert and get.

2. The fork and fork_with methods do require &mut self and there is no (safe) way to bypass that.

   fork is declared as:

   pub fn fork(&mut self) -> Self {
       let newlevel = self.extend();
       let oldlevel = self.extend_fallthrough();
       std::mem::replace(&mut *self, oldlevel);
       newlevel
   }
   

   When used:

   let ch = ChainMap::new();
   let _ = ch.fork();
   

   ch0 is not the same object before and after the call to fork !

   The object that used to be contained in ch has been moved out and there is now no way to access the former ch other than implicitly by reading it from one of its children.

   It is also impossible to insert a new key into it.