rucc_rules/

emit.rs

//! The matcher as Rust, for the compiler to link against.
//!
//! `spec/10-backend.md` section 10.2 asks for a generated automaton rather than a chain of
//! conditionals, and this is the half of that which leaves this crate. A build script reads a
//! rule file, builds the trie next door, and writes what this module produces into the build
//! directory of the crate that matches with it. Nothing here is a copy of anything: the rule
//! file is the only place the rules are written, and the table is regenerated whenever it
//! changes.
//!
//! What comes out does not depend on whether the rules lower or simplify. The kind decides
//! what a replacement is written in and therefore what the crate including the file does with
//! it, and that crate already knows which file it asked for. A table of rewrite rules and a
//! table of lowering rules are the same array of nodes and the same array of replacements.
//!
//! # What comes out
//!
//! One Rust source file, holding the trie as an array of nodes, the rules as an array of
//! replacements, and one function per guard. It is data and not code, except for the guards,
//! which are the one part of a rule that has to be evaluated rather than looked up. The walk
//! over the table lives in the crate that includes the file, because the subject of a match
//! there is the compiler's own IR rather than a term, and because a walk written once is a
//! walk written once however many targets there are.
//!
//! The types the file names are the ones that crate defines, and it refers to them through
//! `super`, which is what makes the file includable and nothing else. That is the whole of the
//! contract between the two, and it is small on purpose.
//!
//! # Guards
//!
//! A guard is a condition on the constants a pattern matched, so it becomes a function of the
//! values the bindings hold. A binding that is not a constant at all makes the guard false
//! rather than an error, because a rule guarded by a claim about a number is a rule that does
//! not fire when the operand is not one.
//!
//! The language a guard may be written in is small and this module is where it ends. A head it
//! does not know is refused with the line it is on, rather than emitted and discovered as a
//! compile error in generated code, which is the sort of message nobody can act on.

use std::fmt::Write as _;

use crate::ast::{Rule, Term, TermKind};
use crate::error::Error;
use crate::matcher::Matcher;

/// The helpers a guard can call, and what each one needs emitted with it.
const HELPERS: &[(&str, &str)] = &[
    ("sign_extend", SIGN_EXTEND),
    ("zero_extend", ZERO_EXTEND),
    ("extract", EXTRACT),
    ("shifted", SHIFTED),
    ("low", LOW),
];

/// Turn a rule set and the trie it compiles into into Rust.
///
/// `source` is the rule file as it should be named in the generated file and in anything the
/// compiler says about a rule at run time, so it is the path a person could open rather than
/// wherever the build script happened to find it.
///
/// # Errors
///
/// A guard this module cannot compile, reported with the position of the term that was not
/// understood. Every other way a rule set can be wrong has been reported by the reader or by
/// the trie before anything gets here.
pub fn emit(source: &str, rules: &[Rule], matcher: &Matcher) -> Result<String, Vec<Error>> {
    let mut out = String::new();
    let mut errors = Vec::new();
    let mut wanted: Vec<&'static str> = Vec::new();

    let guards = compile_guards(source, rules, &mut wanted, &mut errors);
    if !errors.is_empty() {
        return Err(errors);
    }

    header(&mut out, source, rules, matcher);
    nodes(&mut out, matcher);
    replacements(&mut out, source, rules, &guards);
    out.push_str(&guards.iter().flatten().map(String::as_str).collect::<String>());
    helpers(&mut out, &wanted);
    Ok(out)
}

/// The comment nobody reads until they have to, and the table itself.
fn header(out: &mut String, source: &str, rules: &[Rule], matcher: &Matcher) {
    let shape = matcher.shape();
    let _ = write!(
        out,
        "\
// Generated from {source} by rucc-rules. Do not edit this file: edit the
// rule file and build again. It holds {} rules over {} trie nodes.
//
// The widest node has {} branches. Reading them in the order the rules are written would ask
// that many questions to reach the last of them and to find that none of them matched, and the
// search that is done instead asks {}. {} nodes ask more than one kind of question, which is how
// many of them the order the kinds are tried in decides anything at.
//
// The types are the ones the module that includes this file defines, and the walk over the
// table is there too. What is here is the table.

use super::{{Node, Piece, Rule, Table}};

/// The rule file this table was built from, so that anything said about a rule can name a file
/// somebody can open.
pub const SOURCE: &str = {source:?};

/// The rules of this file, as an automaton over their patterns.
pub static TABLE: Table = Table {{ source: SOURCE, nodes: NODES, rules: RULES }};
",
        rules.len(),
        shape.nodes,
        shape.widest,
        shape.search,
        shape.mixed,
    );
}

/// The trie, one array entry per node, with node zero the root.
fn nodes(out: &mut String, matcher: &Matcher) {
    out.push_str(
        "\n/// The trie over the patterns. A node holds the branches taken on the head of a\n\
         /// term, the branches taken on the value of a constant, the branches taken on a\n\
         /// repeat of an earlier binding, the branch that takes anything, and the rule that\n\
         /// ends here if one does. The first two are sorted, which is what makes finding a\n\
         /// branch a search.\nstatic NODES: &[Node] = &[\n",
    );
    for (index, node) in matcher.nodes.iter().enumerate() {
        let _ = writeln!(out, "    // {index}");
        out.push_str("    Node {\n        heads: &[");
        for (head, arity, next) in &node.heads {
            let _ = write!(out, "\n            ({head:?}, {arity}, {next}),");
        }
        if !node.heads.is_empty() {
            out.push_str("\n        ");
        }
        out.push_str("],\n        ints: &[");
        for (value, next) in &node.ints {
            let _ = write!(out, "\n            ({value}, {next}),");
        }
        if !node.ints.is_empty() {
            out.push_str("\n        ");
        }
        out.push_str("],\n        same: &[");
        for (binding, next) in &node.same {
            let _ = write!(out, "\n            ({binding}, {next}),");
        }
        if !node.same.is_empty() {
            out.push_str("\n        ");
        }
        out.push_str("],\n");
        match &node.wildcard {
            Some((name, next)) => {
                let _ = writeln!(out, "        wildcard: Some(({name:?}, {next})),");
            }
            None => out.push_str("        wildcard: None,\n"),
        }
        match node.accept {
            Some(rule) => {
                let _ = writeln!(out, "        accept: Some({rule}),");
            }
            None => out.push_str("        accept: None,\n"),
        }
        out.push_str("    },\n");
    }
    out.push_str("];\n");
}

/// The rules, one array entry each, in the order the file writes them.
fn replacements(out: &mut String, source: &str, rules: &[Rule], guards: &[Option<String>]) {
    out.push_str(
        "\n/// The rules, in the order the rule file writes them, which is the order the\n\
         /// `accept` of a trie node names.\nstatic RULES: &[Rule] = &[\n",
    );
    for (index, rule) in rules.iter().enumerate() {
        let pattern = rule.pattern.to_string();
        let _ = writeln!(out, "    // {source}:{}", rule.line);
        out.push_str("    Rule {\n");
        let _ = writeln!(out, "        pattern: {pattern:?},");
        out.push_str("        replacement: &[");
        let bound = bound_names(&rule.pattern);
        for piece in pieces(&rule.replacement, &bound) {
            let _ = write!(out, "\n            {piece},");
        }
        out.push_str("\n        ],\n");
        match guards[index] {
            Some(_) => {
                let _ = writeln!(out, "        guard: Some(guard_{index}),");
            }
            None => out.push_str("        guard: None,\n"),
        }
        let _ = writeln!(out, "        line: {},", rule.line);
        out.push_str("    },\n");
    }
    out.push_str("];\n");
}

/// The names a pattern binds, in the order the matcher binds them, which is the pre-order it
/// walks the subject in. A replacement names one of them and the table holds the position,
/// because a position is what the match has and a name is what the reader has.
///
/// A name written twice binds once. The second occurrence is a test that the two places hold the
/// same thing rather than a second hole, so it takes no position, and counting it here would put
/// every later name one place along from where the match actually holds it.
fn bound_names(pattern: &Term) -> Vec<String> {
    let mut out: Vec<String> = Vec::new();
    pattern.walk(&mut |term| {
        if let TermKind::Var(name) = &term.kind {
            if !out.iter().any(|have| have == name) {
                out.push(name.clone());
            }
        }
    });
    out
}

/// One replacement term, flattened into the pieces that build it, in pre-order.
fn pieces(term: &Term, bound: &[String]) -> Vec<String> {
    let mut out = Vec::new();
    push_pieces(term, bound, &mut out);
    out
}

fn push_pieces(term: &Term, bound: &[String], out: &mut Vec<String>) {
    match &term.kind {
        TermKind::Var(name) => {
            // The reader has already refused a replacement naming something the pattern never
            // bound, so there is a position for every name that reaches here.
            let index = bound.iter().position(|have| have == name).unwrap_or_default();
            out.push(format!("Piece::Var {{ name: {name:?}, index: {index} }}"));
        }
        TermKind::Int(value) => out.push(format!("Piece::Int({value})")),
        TermKind::App { head, args } => {
            out.push(format!("Piece::App {{ head: {head:?}, arity: {} }}", args.len()));
            for arg in args {
                push_pieces(arg, bound, out);
            }
        }
    }
}

/// One function per guarded rule, or nothing for a rule with no guard.
fn compile_guards(
    source: &str,
    rules: &[Rule],
    wanted: &mut Vec<&'static str>,
    errors: &mut Vec<Error>,
) -> Vec<Option<String>> {
    let mut out = Vec::with_capacity(rules.len());
    for (index, rule) in rules.iter().enumerate() {
        let Some(guard) = &rule.guard else {
            out.push(None);
            continue;
        };
        let bound = bound_names(&rule.pattern);
        let mut used = Vec::new();
        let condition = match condition(source, guard, &bound, wanted, &mut used) {
            Ok(text) => text,
            Err(error) => {
                errors.push(error);
                out.push(None);
                continue;
            }
        };
        // The condition comes out in the order the rule file writes it, so that a reader can hold
        // the two side by side. That is what the lint is turned off for: `(>= k 0)` and `(< k 64)`
        // are two conditions in the rule and `(0..64).contains(&k)` is not either of them.
        let mut text = format!(
            "\n/// `{guard}`, which is the guard of the rule on line {}.\n\
             #[allow(clippy::manual_range_contains)]\nfn guard_{index}(bound: \
             &[Option<i128>]) -> bool {{\n",
            rule.line
        );
        used.sort_unstable();
        used.dedup();
        for at in used {
            let _ = writeln!(
                text,
                "    // {}\n    let Some(Some(v{at})) = bound.get({at}).copied() else {{ return \
                 false }};",
                bound[at]
            );
        }
        let _ = writeln!(text, "    {}\n}}", bare(&condition));
        out.push(Some(text));
    }
    out
}

/// An expression without the parentheses that wrap the whole of it.
///
/// Every condition is emitted parenthesised, because an operand of one has to be. The outermost
/// one is nobody's operand, and Rust warns about the parentheses around it, which in a generated
/// file is a warning the reader of it can do nothing with.
fn bare(text: &str) -> &str {
    let Some(inner) = text.strip_prefix('(').and_then(|text| text.strip_suffix(')')) else {
        return text;
    };
    let mut depth = 0i32;
    for c in inner.chars() {
        match c {
            '(' => depth += 1,
            ')' => depth -= 1,
            _ => {}
        }
        // The pair that opened the string closed before the end of it, so the two ends are not
        // a pair and taking them off would be taking off two different people's parentheses.
        if depth < 0 {
            return text;
        }
    }
    inner
}

/// A guard as a Rust expression of type `bool`.
fn condition(
    source: &str,
    term: &Term,
    bound: &[String],
    wanted: &mut Vec<&'static str>,
    used: &mut Vec<usize>,
) -> Result<String, Error> {
    let TermKind::App { head, args } = &term.kind else {
        return Err(refused(source, term, "a guard is a condition, and this is not one"));
    };
    let arity = args.len();
    match (head.as_str(), arity) {
        ("and" | "or", 1..) => {
            let joint = if head == "and" { " && " } else { " || " };
            let mut parts = Vec::with_capacity(arity);
            for arg in args {
                parts.push(condition(source, arg, bound, wanted, used)?);
            }
            Ok(format!("({})", parts.join(joint)))
        }
        ("not", 1) => Ok(format!("!{}", condition(source, &args[0], bound, wanted, used)?)),
        ("=" | "!=" | "<" | "<=" | ">" | ">=", 2) => {
            let operator = if head == "=" { "==" } else { head.as_str() };
            let left = value(source, &args[0], bound, wanted, used)?;
            let right = value(source, &args[1], bound, wanted, used)?;
            Ok(format!("({left} {operator} {right})"))
        }
        _ => Err(refused(
            source,
            term,
            &format!(
                "`{head}` of {arity} is not a condition a guard can be compiled to. A guard is \
                 `and`, `or`, `not`, or a comparison of two numbers"
            ),
        )),
    }
}

/// A term inside a guard that stands for a number.
fn value(
    source: &str,
    term: &Term,
    bound: &[String],
    wanted: &mut Vec<&'static str>,
    used: &mut Vec<usize>,
) -> Result<String, Error> {
    match &term.kind {
        TermKind::Int(number) => Ok(format!("{number}")),
        TermKind::Var(name) => {
            // The reader has already refused a guard naming something the pattern never bound.
            let at = bound.iter().position(|have| have == name).unwrap_or_default();
            used.push(at);
            Ok(format!("v{at}"))
        }
        TermKind::App { head, args } => {
            let arity = args.len();
            match (head.as_str(), arity) {
                // Adding and subtracting, which is what a guard about two offsets into one object
                // is written in.
                //
                // Saturating rather than plain, because a guard is a condition on whatever
                // constants the match happened to hold and there is nothing to stop those being
                // the ends of the type. Plain arithmetic there is a panic in a debug build and a
                // wrap in a release one, and neither is an answer to a question about a rule.
                //
                // Saturating is not the solver's arithmetic either. The solver reads a guard in
                // the width the rule runs at, where adding wraps, and this reads it in `i128`,
                // where it does not. The two agree exactly while the operands stay small, so a
                // rule that adds says how small in the same guard, and one that does not is a
                // rule proved about arithmetic the compiler is not doing.
                ("+" | "-", 2) => {
                    let left = value(source, &args[0], bound, wanted, used)?;
                    let right = value(source, &args[1], bound, wanted, used)?;
                    let name = if head == "+" { "saturating_add" } else { "saturating_sub" };
                    Ok(format!("({left}).{name}({right})"))
                }
                ("sign_extend" | "zero_extend" | "extract", 3) => {
                    let first = width(source, &args[0])?;
                    let second = width(source, &args[1])?;
                    let inner = value(source, &args[2], bound, wanted, used)?;
                    let name = match head.as_str() {
                        "sign_extend" => "sign_extend",
                        "zero_extend" => "zero_extend",
                        _ => "extract",
                    };
                    want(wanted, name);
                    Ok(format!("{name}({first}, {second}, {inner})"))
                }
                _ => Err(refused(
                    source,
                    term,
                    &format!(
                        "`{head}` of {arity} is not a number a guard can be compiled to. The \
                         ones that are are `+`, `-`, `sign_extend`, `zero_extend` and `extract`"
                    ),
                )),
            }
        }
    }
}

/// A width, which has to be written out rather than computed, because it is how many bits a
/// machine instruction has room for and not something a program is allowed to vary.
fn width(source: &str, term: &Term) -> Result<String, Error> {
    match &term.kind {
        TermKind::Int(number) if (0..=128).contains(number) => Ok(format!("{number}")),
        _ => Err(refused(source, term, "a width has to be a number from 0 to 128")),
    }
}

/// Remember a helper, and everything it is written in terms of.
fn want(wanted: &mut Vec<&'static str>, name: &'static str) {
    if wanted.contains(&name) {
        return;
    }
    wanted.push(name);
    match name {
        "sign_extend" => want(wanted, "shifted"),
        "zero_extend" | "extract" => want(wanted, "low"),
        _ => {}
    }
}

/// The helpers the guards used, in a fixed order so that the file does not move about between
/// builds for no reason.
fn helpers(out: &mut String, wanted: &[&str]) {
    for (name, text) in HELPERS {
        if wanted.contains(name) {
            out.push_str(text);
        }
    }
}

fn refused(source: &str, term: &Term, message: &str) -> Error {
    Error {
        path: source.to_owned(),
        line: term.line,
        column: term.column,
        message: message.to_owned(),
    }
}

const SIGN_EXTEND: &str = "
/// The low `from` bits of `value`, sign extended to `to` bits.
fn sign_extend(from: u32, to: u32, value: i128) -> i128 {
    shifted(to, shifted(from, value))
}
";

const ZERO_EXTEND: &str = "
/// The low `from` bits of `value`, read as a number and not sign extended.
fn zero_extend(from: u32, to: u32, value: i128) -> i128 {
    low(to, low(from, value))
}
";

const EXTRACT: &str = "
/// The bits from `hi` down to `lo` of `value`, read as a number.
fn extract(hi: u32, lo: u32, value: i128) -> i128 {
    if lo >= 128 || hi < lo {
        return 0;
    }
    low(hi - lo + 1, value >> lo)
}
";

const SHIFTED: &str = "
/// `value` read as a signed number that many bits wide.
fn shifted(bits: u32, value: i128) -> i128 {
    match 128u32.checked_sub(bits) {
        Some(room) if room > 0 => (value << room) >> room,
        _ => value,
    }
}
";

const LOW: &str = "
/// The low `bits` bits of `value`, read as a number.
fn low(bits: u32, value: i128) -> i128 {
    if bits >= 128 {
        return value;
    }
    #[allow(clippy::cast_possible_wrap)]
    let masked = (value as u128 & ((1u128 << bits) - 1)) as i128;
    masked
}
";

#[cfg(test)]
mod tests {
    use super::*;
    use crate::parse;

    fn built(text: &str) -> String {
        let rules = parse("rules/test.rules", text).expect("the rules read");
        let matcher = Matcher::build("rules/test.rules", &rules).expect("the matcher builds");
        emit("rules/test.rules", &rules, &matcher).expect("the table is emitted")
    }

    /// The shape of the file, which is what the module that includes it is written against.
    #[test]
    fn a_rule_set_comes_out_as_a_table_of_nodes_and_a_table_of_rules() {
        let out = built(
            "(rule (lower (add.i64 (value.i64 x) (value.i64 y)))\n\
             (x64.add_rr_64 x y)\n\
             (spec (= (bvadd x y) (result))))\n",
        );
        assert!(out.contains("use super::{Node, Piece, Rule, Table};"), "{out}");
        assert!(out.contains("pub const SOURCE: &str = \"rules/test.rules\";"), "{out}");
        assert!(out.contains("(\"add.i64\", 2, 1),"), "{out}");
        assert!(out.contains("wildcard: Some((\"x\", 3)),"), "{out}");
        assert!(out.contains("accept: Some(0),"), "{out}");
        assert!(out.contains("Piece::App { head: \"x64.add_rr_64\", arity: 2 }"), "{out}");
        assert!(out.contains("Piece::Var { name: \"x\", index: 0 }"), "{out}");
        assert!(out.contains("Piece::Var { name: \"y\", index: 1 }"), "{out}");
        assert!(out.contains("guard: None,"), "{out}");
    }

    /// A name written twice comes out as a test and not as a second hole, so the positions a
    /// replacement and a guard are written against count it once. Here `k` is binding one, which
    /// it would not be if the second `x` had taken a position of its own.
    #[test]
    fn a_name_written_twice_comes_out_as_a_test_and_takes_no_position() {
        let out = built(
            "(rule (simplify (and.i32 (value.i32 x) (value.i32 x)))\n\
             (value.i32 x)\n\
             (spec (= x (result))))\n\
             (rule (simplify (shl.i32 (value.i32 x) (iconst.i32 k)))\n\
             (if (>= k 0))\n\
             (value.i32 x)\n\
             (spec (= (bvshl x k) (result))))\n",
        );
        assert!(out.contains("same: &[\n            (0, "), "{out}");
        assert!(out.contains("Piece::Var { name: \"x\", index: 0 }"), "{out}");
        assert!(
            out.contains("let Some(Some(v1)) = bound.get(1).copied() else { return false };"),
            "{out}"
        );
    }

    /// A guard becomes a function of the constants the pattern matched, and the helpers it
    /// calls come with it. A binding it reads that is not a constant makes it false, which is
    /// what the `let ... else` in it is for.
    #[test]
    fn a_guard_comes_out_as_a_function_of_the_bindings() {
        let out = built(
            "(rule (lower (shl.i64 (value.i64 x) (iconst.i64 k)))\n\
             (if (and (>= k 0) (< k 64)))\n\
             (x64.shl_ri_64 x k)\n\
             (spec (= (bvshl x k) (result))))\n",
        );
        assert!(out.contains("guard: Some(guard_0),"), "{out}");
        assert!(out.contains("fn guard_0(bound: &[Option<i128>]) -> bool {"), "{out}");
        assert!(
            out.contains("let Some(Some(v1)) = bound.get(1).copied() else { return false };"),
            "{out}"
        );
        assert!(out.contains("(v1 >= 0) && (v1 < 64)"), "{out}");
        // Nothing this guard does not use is emitted, because an unused function in a
        // generated file is a warning in the crate that includes it.
        assert!(!out.contains("fn sign_extend"), "{out}");
        assert!(!out.contains("fn low"), "{out}");
    }

    /// The immediate guard, which is the one that needs the arithmetic helpers, and which is
    /// what pulls `shifted` and `low` in behind them.
    #[test]
    fn a_guard_that_reads_bits_brings_the_helpers_it_needs() {
        let out = built(
            "(rule (lower (add.i64 (value.i64 x) (iconst.i64 k)))\n\
             (if (= k (sign_extend 32 64 (extract 31 0 k))))\n\
             (x64.add_ri_64 x k)\n\
             (spec (= (bvadd x k) (result))))\n",
        );
        assert!(out.contains("v1 == sign_extend(32, 64, extract(31, 0, v1))"), "{out}");
        assert!(out.contains("fn sign_extend(from: u32, to: u32, value: i128) -> i128 {"), "{out}");
        assert!(out.contains("fn shifted(bits: u32, value: i128) -> i128 {"), "{out}");
        assert!(out.contains("fn extract(hi: u32, lo: u32, value: i128) -> i128 {"), "{out}");
        assert!(out.contains("fn low(bits: u32, value: i128) -> i128 {"), "{out}");
        assert!(!out.contains("fn zero_extend"), "{out}");
    }

    /// A guard written in something this module does not compile is refused here, with the
    /// position of the term, rather than emitted and found later as a compile error in a
    /// generated file that nobody wrote.
    #[test]
    fn a_guard_nothing_can_be_made_of_is_refused_where_it_is_written() {
        let rules = parse(
            "rules/test.rules",
            "(rule (lower (add.i64 (value.i64 x) (iconst.i64 k)))\n\
             (if (fits_in_a_byte k))\n\
             (x64.add_ri_64 x k)\n\
             (spec (= (bvadd x k) (result))))\n",
        )
        .expect("the rules read");
        let matcher = Matcher::build("rules/test.rules", &rules).expect("the matcher builds");
        let errors = emit("rules/test.rules", &rules, &matcher).expect_err("the guard is refused");
        assert_eq!(errors.len(), 1);
        assert_eq!(errors[0].line, 2);
        assert!(
            errors[0].message.contains("`fits_in_a_byte` of 1 is not a condition"),
            "{}",
            errors[0]
        );
    }
}