A De Bruijn index is a standard means of representing regions (and perhaps later types) in a higher-ranked setting. In particular, imagine a type like this:
An floating-point (
f64) type variable ID.
An integral (
usize, etc.) type variable ID.
A type variable ID.
Flags that we track on types. These flags are propagated upwards through the type during type construction, so that we can quickly check whether the type has various kinds of types in it without recursing over the type itself.
“Universes” are used during type- and trait-checking in the presence of
for<..>binders to control what sets of names are visible. Universes are arranged into a tree: the root universe contains names that are always visible. Each child then adds a new set of names that are visible, in addition to those of its parent. We say that the child universe “extends” the parent universe with new names.