rucc-rules 0.7.2

//! What the compiled rule set matches, and in what order.

use rucc_rules::{Matcher, Rule, Term, parse};

/// Two of the rules `spec/10-backend.md` section 10.2 writes out, including the one that is not
/// x86-64, because the point of the trie is what happens when rules share a prefix. The other
/// two are the general forms the first two are special cases of, which is what makes the order
/// the rules are tried in observable.
const RULES: &str = "\
(rule (lower (add.i64 (value x) (mul.i64 (value y) (iconst 4))))
      (x64.lea (amode_base_index_scale x y 4))
      (spec (= (bvadd x (bvmul y 4)) (result))))
(rule (lower (add.i64 (value x) (shl.i64 (value y) (iconst k))))
      (if (and (>= k 0) (< k 64)))
      (a64.add_shifted x y (lsl k))
      (spec (= (bvadd x (bvshl y k)) (result))))
(rule (lower (add.i64 (value x) (mul.i64 (value y) (iconst m))))
      (x64.imul_then_add x y m)
      (spec (= (bvadd x (bvmul y m)) (result))))
(rule (lower (add.i64 (value x) (value y)))
      (x64.add x y)
      (spec (= (bvadd x y) (result))))";

fn rules(text: &str) -> Vec<Rule> {
    match parse("t.rules", text) {
        Ok(rules) => rules,
        Err(errors) => panic!("{}", errors[0]),
    }
}

fn matcher(text: &str) -> Matcher {
    match Matcher::build("t.rules", &rules(text)) {
        Ok(matcher) => matcher,
        Err(errors) => panic!("{}", errors[0]),
    }
}

/// Subjects are written in the rule language too, since a pattern with no variables in it is
/// exactly a ground term.
fn term(text: &str) -> Term {
    // The replacement and the specification are the smallest well formed things that mention
    // nothing, since only the pattern is wanted here.
    let text = format!("(rule (lower {text}) (nothing) (spec (= (result) (result))))");
    match parse("t.rules", &text) {
        Ok(rules) => rules.into_iter().next().expect("one rule").pattern,
        Err(errors) => panic!("{}", errors[0]),
    }
}

#[test]
fn the_rule_that_names_the_most_is_the_rule_that_fires() {
    let matcher = matcher(RULES);
    let subject = term("(add.i64 (value a) (mul.i64 (value b) (iconst 4)))");
    let found = matcher.find(&subject).expect("something has to match");
    assert_eq!(found.rule, 0);
    assert_eq!(found.get("x").map(ToString::to_string).as_deref(), Some("a"));
    assert_eq!(found.get("y").map(ToString::to_string).as_deref(), Some("b"));
}

/// The scale in the first rule is written out as `4`, so a subject with any other scale has to
/// fall past it. Falling past a literal test and into a wildcard is the case a matcher built as
/// a chain of conditionals gets right by accident and a trie has to get right on purpose.
#[test]
fn a_literal_that_does_not_match_falls_through_to_the_more_general_rule() {
    let matcher = matcher(RULES);
    let subject = term("(add.i64 (value a) (mul.i64 (value b) (iconst 8)))");
    let found = matcher.find(&subject).expect("the general rule has to catch it");
    assert_eq!(found.rule, 2);
    assert_eq!(found.get("m").map(ToString::to_string).as_deref(), Some("8"));
}

#[test]
fn a_shift_by_a_constant_reaches_the_rule_that_asked_for_one() {
    let matcher = matcher(RULES);
    let subject = term("(add.i64 (value a) (shl.i64 (value b) (iconst 3)))");
    let found = matcher.find(&subject).expect("something has to match");
    assert_eq!(found.rule, 1);
    assert_eq!(found.get("k").map(ToString::to_string).as_deref(), Some("3"));
}

#[test]
fn nothing_matches_when_nothing_matches() {
    let matcher = matcher(RULES);
    assert!(matcher.find(&term("(sub.i64 (value a) (value b))")).is_none());
    assert!(matcher.find(&term("(add.i64 (value a))")).is_none());
    assert_eq!(matcher.find(&term("(add.i64 (value a) (value b))")).map(|m| m.rule), Some(3));
}

/// The prefix every rule shares is one branch, not three. This is the whole reason the matcher
/// is a trie, so it is worth asserting rather than trusting.
#[test]
fn rules_that_start_the_same_way_share_the_steps_they_agree_on() {
    let shown = matcher(RULES).to_string();
    assert_eq!(shown.matches("add.i64/2").count(), 1, "{shown}");
    // Four, not five: the one all four rules share, one inside each of the two second operands
    // that are shifts or multiplies, and one for the plain add. The two multiply rules agree on
    // everything up to the scale, so they share the `value/1` inside the multiply.
    assert_eq!(shown.matches("value/1").count(), 4, "{shown}");
}

#[test]
fn the_wildcard_is_the_last_thing_tried_at_every_node() {
    let shown = matcher(RULES).to_string();
    let expected = "\
add.i64/2
  value/1
    bind x
      mul.i64/2
        value/1
          bind y
            iconst/1
              4
                => rule 0
              bind m
                => rule 2
      shl.i64/2
        value/1
          bind y
            iconst/1
              bind k
                => rule 1
      value/1
        bind y
          => rule 3
";
    assert_eq!(shown, expected);
}

/// Two of the identities `spec/optimizer/13-rewrite-rules.md` section 13.4 writes with one name
/// in two places, and under the second of them the general rule it is a special case of. That
/// pair is what makes the order the two are tried in observable.
const SAME: &str = "\
(rule (simplify (and.i32 (value.i32 x) (value.i32 x)))
      (value.i32 x)
      (spec (= x (result))))
(rule (simplify (xor.i32 (value.i32 x) (value.i32 x)))
      (iconst.i32 0)
      (spec (= 0 (result))))
(rule (lower (xor.i32 (value.i32 x) (value.i32 y)))
      (x64.xor x y)
      (spec (= (bvxor x y) (result))))";

/// The second occurrence of a name is a claim about the subject and not a hole in the pattern,
/// so the rule fires on a term with one thing in both operands and binds that thing once.
#[test]
fn a_name_written_twice_matches_a_term_with_the_same_thing_in_both_places() {
    let matcher = matcher(SAME);
    let subject = term("(and.i32 (value.i32 a) (value.i32 a))");
    let found = matcher.find(&subject).expect("something has to match");
    assert_eq!(found.rule, 0);
    assert_eq!(found.bindings.len(), 1);
    assert_eq!(found.get("x").map(ToString::to_string).as_deref(), Some("a"));
}

/// The same rule against two different things. There is no wildcard beside the test at that
/// node, so nothing catches it, which is the point: `x & x` is not a rule about `x & y`.
#[test]
fn a_name_written_twice_refuses_a_term_with_two_different_things_in_it() {
    let matcher = matcher(SAME);
    let subject = term("(and.i32 (value.i32 a) (value.i32 b))");
    assert!(matcher.find(&subject).is_none());
}

/// A rule that wants one thing in both operands is more specific than a rule that takes any
/// two, so it is tried first, for the same reason a literal is tried before a wildcard.
#[test]
fn a_name_written_twice_is_tried_before_the_rule_that_takes_any_two() {
    let matcher = matcher(SAME);
    let alike = term("(xor.i32 (value.i32 a) (value.i32 a))");
    assert_eq!(matcher.find(&alike).expect("something has to match").rule, 1);
    let apart = term("(xor.i32 (value.i32 a) (value.i32 b))");
    assert_eq!(matcher.find(&apart).expect("the general rule has to catch it").rule, 2);

    // And the trie says the same thing, with the test ahead of the wildcard at that node.
    let shown = matcher.to_string();
    let wanted = "\
  value.i32/1
    bind x
      value.i32/1
        same as binding 0
          => rule 1
        bind y
          => rule 2
";
    assert!(shown.ends_with(wanted), "{shown}");
}

#[test]
fn a_rule_that_can_never_fire_is_refused_rather_than_dropped() {
    let text = "\
(rule (lower (add.i64 (value x) (value y))) (x64.add x y) (spec (= (bvadd x y) (result))))
(rule (lower (add.i64 (value a) (value b))) (x64.lea a b) (spec (= (bvadd a b) (result))))";
    let Err(errors) = Matcher::build("t.rules", &rules(text)) else {
        panic!("that was supposed to be refused");
    };
    assert_eq!(
        errors[0].to_string(),
        "t.rules:2:1: this rule can never fire, because the rule on line 1 matches everything it does"
    );
}

#[test]
fn an_empty_rule_set_matches_nothing_and_says_so() {
    let matcher = Matcher::build("t.rules", &[]).expect("nothing to refuse");
    assert!(matcher.is_empty());
    assert!(matcher.find(&term("(add.i64 (value a) (value b))")).is_none());
}