Module rustc_data_structures::unify
source · Expand description
Union-find implementation. The main type is UnificationTable
.
You can define your own type for the keys in the table, but you
must implement UnifyKey
for that type. The assumption is that
keys will be newtyped integers, hence we require that they
implement Copy
.
Keys can have values associated with them. The assumption is that
these values are cheaply cloneable (ideally, Copy
), and some of
the interfaces are oriented around that assumption. If you just
want the classical “union-find” algorithm where you group things
into sets, use the Value
type of ()
.
When you have keys with non-trivial values, you must also define
how those values can be merged. As part of doing this, you can
define the “error” type to return on error; if errors are not
possible, use NoError
(an uninstantiable struct). Using this
type also unlocks various more ergonomic methods (e.g., union()
in place of unify_var_var()
).
The best way to see how it is used is to read the tests.rs
file;
search for e.g. UnitKey
.
Structs
UnifyKey
trait. Unification tables can be used in two-modes:V
and a rank. The rank is used
to keep the DAG relatively balanced, which helps keep the running
time of the algorithm under control. For more information, see
http://en.wikipedia.org/wiki/Disjoint-set_data_structure.Traits
int
with one bound to
float
(but you can unify two type variables both bound to
int
).InPlace
,
which indicates a standard, mutable unification table.IntVid
, which represents integral
variables.