Finding the dominators of a node is an important first step for numerous algorithms in program analysis. Dominators are used for building an SSA form of a program, eliminating re-computations of expressions, and determining control dependencies between basic blocks.

Background

Node A dominates node B if all paths from the entry node to node B must pass through node A.

For example, in the above graph, node A dominates node B but does not dominate nodes C or D. All paths to B must go through A: entry, A, B or entry, D, C, A, B. However, there exist paths to C and D that do not go through A: entry, D and entry, D, C.

A problem that I run into every once in a while is creating a reference to an item in a data structure that doesn’t hold a reference to the data structure so you can modify it while having the reference and has an API that prevents any kind of misuse.

For a vector, just handing out the index of an element almost works. It can be used to quickly get access to the element in the vector but it can be easily misused and can cause a panic. The index is just a usize which is not tied to the vector that returned it. You can easily pass the index from one vector into another vector without the type system complaining at all.

Something you might not know about rust-doc is that you can document your implementation of traits. I have not seend this feature used a whole lot and it’s not commonly necessary so I was surprised when I tried it and it actually worked.

One example of where you might want to use this is if you implement the AsRef trait on something that has multiple fields that would make sense to be the returned shared reference.