pub struct Node {
pub heads: &'static [(u128, &'static str, usize, u32)],
pub ints: &'static [(i128, u32)],
pub same: &'static [(usize, u32)],
pub wildcard: Option<(&'static str, u32)>,
pub accept: &'static [u32],
}Expand description
One node of the trie over the patterns.
The branches are held by the kind of question they ask rather than in one list, which is what lets the two that can be searched be searched.
Fields§
§heads: &'static [(u128, &'static str, usize, u32)]The branches taken on the head of the subterm, as the Node::key of the name, the name,
how many arguments it takes, and where to go. Sorted by the first three, which is what
Node::branch needs and is the same order as sorting by the name and the count.
ints: &'static [(i128, u32)]The branches taken on the value of a subterm that is a constant, sorted by the value.
same: &'static [(usize, u32)]The branches taken when the subterm is the same thing as a binding this pattern already
made, named by which binding it is. A pattern writes one where it writes a name for the
second time, so this is how x & x is told apart from x & y. In the order the rules
were written, because two of them can match one subterm.
wildcard: Option<(&'static str, u32)>The branch that takes anything, and the name the first rule to reach it gave that hole.
accept: &'static [u32]The rules that end here, in the order the rule file writes them. The first whose guard holds is the one that fires, so every one of them but the last has a guard, which the rule compiler checks.
Implementations§
Source§impl Node
impl Node
Sourcepub fn branch(&self, head: &str, arity: usize) -> Option<u32>
pub fn branch(&self, head: &str, arity: usize) -> Option<u32>
The branch for a term with this head and this many arguments, if the node has one.
A binary search, which is the whole point of the list being sorted. At most one branch can answer, so nothing about which rule fires depends on the list being in this order rather than in the order the rules were written.
Each step compares the keys first and only compares the names when the keys agree, which
for names no longer than sixteen bytes is only on the branch being looked for. Comparing
the names at every step called memcmp at every step, and that was most of what finding a
branch cost.
Sourcepub const fn key(name: &str) -> u128
pub const fn key(name: &str) -> u128
The first sixteen bytes of a name as one number, padded with zeros, which orders the way the names do.
Reading the bytes most significant first makes comparing two of these the same as
comparing the bytes one at a time. A name never holds a zero byte, so the padding sorts
below every byte a name does hold and a name that runs out first is the smaller one, as it
should be. Two names with one key are only known to be equal when neither is longer than
sixteen bytes, which is why Node::branch compares the names as well. A table computes
the key of each of its names when it is compiled.