Module rustc_utils::cache

source ·
Expand description

Data structures for memoizing computations.

Contruct new caches using Default::default, then construct/retrieve elements with get. get should only ever be used with one, compute function1.

In terms of choice,

  • CopyCache should be used for expensive computations that create cheap (i.e. small) values.
  • Cache should be used for expensive computations that create expensive (i.e. large) values.

Both types of caches implement recursion breaking. In general because caches are supposed to be used as simple & (no mut) the reference may be freely copied, including into the compute closure. What this means is that a compute may call get on the cache again. This is usually safe and can be used to compute data structures that recursively depend on one another, dynamic-programming style. However if a get on a key k itself calls get again on the same k this will either create an infinite recursion or an inconsistent cache1.

Consider a simple example where we compute the Fibonacci Series with a CopyCache:

struct Fib(CopyCache<u32, u32>);

impl Fib {
  fn get(&self, i: u32) -> u32 {
    self.0.get(i, |_| {
      if this <= 1 {
        return this;
      }
      let fib_1 = self.get(this - 1);
      let fib_2 = self.get(this - 2);
      fib_1 + fib_2
    })
  }
}

let cache = Fib(Default::default());
let fib_5 = cache.get(5);

This use of recursive get calls is perfectly legal. However if we made an error and called chache.get(this, ...) (forgetting the decrement) we would have created an inadvertend infinite recursion.

To avoid this scenario both caches are implemented to detect when a recursive call as described is performed and get will panic. If your code uses recursive construction and would like to handle this case gracefully use get_maybe_recursive instead wich returns None from get(k) iff k this call (potentially transitively) originates from another get(k) call.

  1. For any given cache value get should only ever be used with one, referentially transparent compute function. Essentially this means running compute(k) should always return the same value independent of the state of it’s environment. Violation of this rule can introduces non-determinism in your program. ↩

Structs