Taxo stores every relationship in a %Taxo{} struct. The struct holds
three maps, and it keeps all three in sync on every change.
Tags
A tag is a node in the hierarchy. A tag can be any Elixir term: an atom, a string, a tuple, or anything else you use as a map key.
Three maps, one invariant
| Map | Holds |
|---|---|
:parents | The direct parents of a tag |
:ancestors | Every parent, and every parent of those parents |
:descendants | The inverse of :ancestors: every tag that has this tag as an ancestor |
:ancestors and :descendants always agree. parent is in
ancestors(child) only if child is in descendants(parent), and the
other way round. Taxo keeps this true after every derive/3 and
underive/3 call, so a caller never checks both maps to be sure.
:parents is a subset of :ancestors. A direct parent is also an
ancestor.
How derive/3 updates the hierarchy
Adding one link, child -> parent, can change many tags' ancestors and
descendants, not just child's and parent's.
Take this example: :dog is derived from :mammal, then :mammal is
derived from :animal. The second call must also add :animal to
:dog's ancestors, even though that call only names :mammal and
:animal.
derive/3 handles this on every call. It looks at every tag already
connected to child as a descendant, and every tag already connected to
parent as an ancestor. It updates :ancestors and :descendants for all
of those tags at once, not just for child and parent.
Cycles
A hierarchy must stay acyclic. No tag can be its own ancestor. derive/3
checks this before it writes anything. If parent is already a descendant
of child, the new link would close a loop. derive/3 raises
Taxo.CyclicDerivationError instead of applying the change.
Why underive/3 rebuilds instead of subtracting
Removing a link can also shrink many tags' ancestor and descendant sets, not just the two tags named in the link. Working out exactly which sets shrink, and by how much, means checking whether some other path still supports each entry.
underive/3 sidesteps that check. It drops the named link, then rebuilds
the whole taxonomy from an empty one, calling derive/3 on every link that
remains.
This is simple, and it is correct. But its cost grows with the size of the whole taxonomy, not with the size of the link removed. Removing one link from a large hierarchy is not a cheap call.