Union-find implementation. The main type is
You can define your own type for the keys in the table, but you
UnifyKey for that type. The assumption is that
keys will be newtyped integers, hence we require that they
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
NoError (an uninstantiable struct). Using this
type also unlocks various more ergonomic methods (e.g.,
in place of
The best way to see how it is used is to read the
search for e.g.
Backing store for an in-place unification table. Not typically used directly.
A struct which can never be instantiated. Used for the error type for infallible cases.
At any time, users may snapshot a unification table. The changes made during the snapshot may either be committed or rolled back.
Table of unification keys and their values. You must define a key type K
that implements the
Value of a unification key. We implement Tarjan's union-find
algorithm: when two keys are unified, one of them is converted
into a "redirect" pointing at the other. These redirects form a
DAG: the roots of the DAG (nodes that are not redirected) are each
associated with a value of type
A convenient helper for unification values which must be equal or
else an error occurs. For example, if you are unifying types in a
simple functional language, this may be appropriate, since (e.g.)
you can't unify a type variable bound to
Largely internal trait implemented by the unification table
backing store types. The most common such type is
This trait is implemented by any type that can serve as a type
variable. We call such variables unification keys. For example,
this trait is implemented by
Trait implemented for values associated with a unification key. This trait defines how to merge the values from two keys that are unioned together. This merging can be fallible. If you attempt to union two keys whose values cannot be merged, then the error is propagated up and the two keys are not unioned.
A unification table that uses an "in-place" vector.