Enum cranelift_isle::trie::TrieNode

pub enum TrieNode {
    Decision {
        edges: Vec<TrieEdge>,
    },
    Leaf {
        prio: Prio,
        output: ExprSequence,
    },
    Empty,
}

A node in the term trie.

Variants

Decision

Fields

edges: Vec<TrieEdge>

The child sub-tries that we can match from this point on.

One or more patterns could match.

Maybe one pattern already has matched, but there are more (higher priority and/or same priority but more specific) patterns that could still match.

Leaf

Fields

prio: Prio

The priority of this rule.

output: ExprSequence

The RHS expression to evaluate upon a successful LHS pattern match.

The successful match of an LHS pattern, and here is its RHS expression.

Empty

No LHS pattern matches.

Implementations

impl TrieNode

pub fn sort(&mut self)

Sort edges by priority.

Examples found in repository

src/trie.rs (line 245)

    pub fn sort(&mut self) {
        match self {
            TrieNode::Decision { edges } => {
                // Sort by priority, highest integer value first; then
                // by trie symbol.
                edges.sort_by_cached_key(|edge| (-edge.prio, edge.symbol.clone()));
                for child in edges {
                    child.node.sort();
                }
            }
            _ => {}
        }
    }

    /// Get a pretty-printed version of this trie, for debugging.
    pub fn pretty(&self) -> String {
        let mut s = String::new();
        pretty_rec(&mut s, self, "");
        return s;

        fn pretty_rec(s: &mut String, node: &TrieNode, indent: &str) {
            match node {
                TrieNode::Decision { edges } => {
                    s.push_str(indent);
                    s.push_str("TrieNode::Decision:\n");

                    let new_indent = indent.to_owned() + "    ";
                    for edge in edges {
                        s.push_str(indent);
                        s.push_str(&format!(
                            "  edge: prio = {:?}, symbol: {:?}\n",
                            edge.prio, edge.symbol
                        ));
                        pretty_rec(s, &edge.node, &new_indent);
                    }
                }
                TrieNode::Empty | TrieNode::Leaf { .. } => {
                    s.push_str(indent);
                    s.push_str(&format!("{:?}\n", node));
                }
            }
        }
    }
}

#[derive(Debug, Default)]
struct TermFunctionsBuilder {
    builders_by_term: BTreeMap<TermId, TrieNode>,
}

impl TermFunctionsBuilder {
    fn build(&mut self, termenv: &TermEnv) {
        log!("termenv: {:?}", termenv);
        for rule in termenv.rules.iter() {
            let (pattern, expr) = lower_rule(termenv, rule.id);

            log!(
                "build:\n- rule {:?}\n- pattern {:?}\n- expr {:?}",
                rule,
                pattern,
                expr
            );

            let symbols = pattern
                .insts
                .into_iter()
                .map(|op| TrieSymbol::Match { op })
                .chain(std::iter::once(TrieSymbol::EndOfMatch));

            self.builders_by_term
                .entry(rule.root_term)
                .or_insert(TrieNode::Empty)
                .insert(rule.prio, symbols, expr);
        }

        for builder in self.builders_by_term.values_mut() {
            builder.sort();
        }
    }

pub fn pretty(&self) -> String

Get a pretty-printed version of this trie, for debugging.

Trait Implementations

impl Clone for TrieNode

fn clone(&self) -> TrieNode

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TrieNode

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.