Rete rules engine

Deep dive

How it works

Parts:

• Working memory element (WME) — a fact, here an (id, attr, value) triple.
• Alpha node — one test on a single fact; its memory holds the facts that pass. Identical tests are shared.
• Join node — links two conditions on a shared variable; left memory = tokens (partial matches), right memory = an alpha memory.
• Terminal node — a token matching all conditions becomes an activation.
• Agenda (conflict set) — activations awaiting firing, ordered by conflict resolution.

1. Assert: run the fact through the alpha tests; store it in each matching alpha memory.
2. The alpha memory activates its joins. A right activation joins the new fact with every left token; a left activation joins a new token with every right fact.
3. A passing join creates a token: stored in the next left memory, or at the last join an activation on the agenda.
4. Retract: remove the fact from the memories and delete the tokens and activations built from it. Nothing is re-matched.
5. Fire: take the best activation (highest salience, then most recent); its action asserts or retracts facts, repeating from 1.

 fact -> [alpha CUSTOMER] -----> [JOIN order.val == cust.id] -> agenda
         [alpha TIER=gold] -----^     left mem: orders; right mem: golds

Drools gives each rule an integer salience (default 0, higher first) to order its agenda (docs).

Code

Two rules share one alpha test. Asserts compare against a naive re-evaluate-all checker after every change, plus order independence, retraction, agenda order and join-test counts.

use std::collections::HashSet;
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct Fact { pub id: u32, pub attr: u8, pub val: u32 } // (id, attr, value) triple
pub const CUSTOMER: u8 = 0; // (order, CUSTOMER, customer_id)
pub const TIER: u8 = 1;     // (customer_id, TIER, tier)
pub const GOLD: u32 = 1;
pub const SILVER: u32 = 2;
struct Alpha { attr: u8, val: Option<u32>, mem: Vec<Fact> } // one constant test + its memory
struct Join { la: usize, ra: usize, left: Vec<Fact> }       // left memory holds 1-fact tokens
struct Rule { salience: i32, join: usize }
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct Match { pub rule: usize, pub order: Fact, pub cust: Fact, stamp: u64 }
#[derive(Default)]
pub struct Rete { alphas: Vec<Alpha>, joins: Vec<Join>, rules: Vec<Rule>,
                  agenda: Vec<Match>, clock: u64, pub join_tests: u64 }
impl Rete {
    fn alpha(&mut self, attr: u8, val: Option<u32>) -> usize {
        if let Some(i) = self.alphas.iter().position(|a| a.attr == attr && a.val == val) { return i; }
        self.alphas.push(Alpha { attr, val, mem: vec![] });
        self.alphas.len() - 1
    }
    pub fn add_rule(&mut self, salience: i32, tier: u32) {
        let (la, ra) = (self.alpha(CUSTOMER, None), self.alpha(TIER, Some(tier)));
        self.joins.push(Join { la, ra, left: vec![] });
        self.rules.push(Rule { salience, join: self.joins.len() - 1 });
    }
    pub fn assert_fact(&mut self, f: Fact) {
        for ai in 0..self.alphas.len() {
            let a = &mut self.alphas[ai];
            if a.attr != f.attr || a.val.map_or(false, |v| v != f.val) || a.mem.contains(&f) { continue; }
            a.mem.push(f);
            for ri in 0..self.rules.len() {
                let j = self.rules[ri].join;
                if self.joins[j].la == ai { // left activation: new token joins the right memory
                    self.joins[j].left.push(f);
                    for r in self.alphas[self.joins[j].ra].mem.clone() { self.test(ri, f, r); }
                }
                if self.joins[j].ra == ai { // right activation: new fact joins the left memory
                    for l in self.joins[j].left.clone() { self.test(ri, l, f); }
                }
            }
        }
    }
    fn test(&mut self, rule: usize, order: Fact, cust: Fact) {
        self.join_tests += 1;
        if order.val == cust.id { // the shared variable ?c
            self.clock += 1;
            self.agenda.push(Match { rule, order, cust, stamp: self.clock });
        }
    }
    pub fn retract_fact(&mut self, f: Fact) {
        for a in &mut self.alphas { a.mem.retain(|x| *x != f); }
        for j in &mut self.joins { j.left.retain(|x| *x != f); }
        self.agenda.retain(|m| m.order != f && m.cust != f); // no re-testing needed
    }
    // conflict resolution: salience, then recency
    pub fn fire(&mut self) -> Option<Match> {
        let best = (0..self.agenda.len()).max_by_key(|&i| {
            (self.rules[self.agenda[i].rule].salience, self.agenda[i].stamp) })?;
        Some(self.agenda.swap_remove(best))
    }
    pub fn matches(&self) -> HashSet<(usize, Fact, Fact)> {
        self.agenda.iter().map(|m| (m.rule, m.order, m.cust)).collect()
    }
}
// naive checker: every pair, every rule
fn naive(facts: &HashSet<Fact>, tiers: &[u32]) -> (HashSet<(usize, Fact, Fact)>, u64) {
    let (mut out, mut tests) = (HashSet::new(), 0);
    for (r, &t) in tiers.iter().enumerate() {
        for o in facts.iter().filter(|f| f.attr == CUSTOMER) {
            for c in facts.iter().filter(|f| f.attr == TIER && f.val == t) {
                tests += 1;
                if o.val == c.id { out.insert((r, *o, *c)); }
            }
        }
    }
    (out, tests)
}
fn main() {
    let tiers = [GOLD, SILVER];
    let mk = || { let mut e = Rete::default(); e.add_rule(10, GOLD); e.add_rule(5, SILVER); e };
    let mut seed = 0x9E3779B97F4A7C15u64;
    let mut rnd = move |n: u32| { seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17; (seed % n as u64) as u32 };
    let (mut e, mut facts, mut naive_tests, mut steps) = (mk(), HashSet::new(), 0u64, 0);
    for _ in 0..2000 {
        let f = if rnd(2) == 0 { Fact { id: rnd(200), attr: CUSTOMER, val: 1000 + rnd(40) } }
                else { Fact { id: 1000 + rnd(40), attr: TIER, val: 1 + rnd(2) } };
        if rnd(10) < 7 { e.assert_fact(f); facts.insert(f); } else { e.retract_fact(f); facts.remove(&f); }
        let (m, t) = naive(&facts, &tiers);
        assert_eq!(e.matches(), m); // incremental == from scratch after every change
        naive_tests += t; steps += 1;
    }
    println!("steps {steps}, facts {}, matches {}", facts.len(), e.agenda.len());    println!("incremental join tests {}, naive join tests {}", e.join_tests, naive_tests);
    let list: Vec<Fact> = facts.iter().copied().collect();
    for _ in 0..20 {
        let (mut p, mut e2) = (list.clone(), mk());
        for i in (1..p.len()).rev() { p.swap(i, rnd(i as u32 + 1) as usize); }
        for f in p { e2.assert_fact(f); }
        assert_eq!(e2.matches(), e.matches());
    }
    let victim = *list.iter().find(|f| f.attr == TIER && e.matches().iter().any(|m| m.2 == **f)).unwrap();
    let before = e.matches();
    e.retract_fact(victim);
    let want: HashSet<_> = before.iter().filter(|m| m.1 != victim && m.2 != victim).copied().collect();
    assert_eq!(e.matches(), want);
    let mut e3 = mk();
    for f in [Fact{id:1,attr:CUSTOMER,val:100}, Fact{id:2,attr:CUSTOMER,val:200},
              Fact{id:100,attr:TIER,val:GOLD}, Fact{id:200,attr:TIER,val:SILVER}] { e3.assert_fact(f); }
    assert_eq!(e3.fire().unwrap().rule, 0);
    assert_eq!(e3.fire().unwrap().rule, 1);
    assert!(e3.fire().is_none());
    println!("all asserts passed");
}

Output of this exact block (release build, seeded): steps 2000, facts 702, matches 960, incremental join tests 105300, naive join tests 35204526, all asserts passed.

Complexity and constants

• Join: a new fact tests every entry of the opposite memory, O(memory); hashing on the join variable makes it O(matches).
• Measured: 35,204,526 / 105,300 is about 334x fewer join tests than re-evaluating after each change (~700 live facts, 2 rules). The naive checker already pre-filters by alpha tests; I did not time wall clock.
• Space: one entry per fact per alpha memory plus one per partial match; long unselective joins blow up.

Efficiency

• Cost: per change a few comparisons plus join tests proportional to the opposite memory; bound is memory access in the join memories.
• Levers:
  • Share alpha and beta nodes across rules — one test and memory instead of N — rules with common conditions.
  • Most selective condition first — fewer tokens stored — rule authors and compilers.
  • Hash memories on the join variable — join test becomes a bucket lookup — equality joins on large memories.
  • Unlink joins with an empty side (Rete/UL, PHREAK) — skip propagation that cannot match — sparse rule sets.
• Naive → standard → state of the art:
  • Re-test every rule on every fact per change · 35.2M join tests on my workload.
  • Rete with shared alpha memories and token memories · 105k join tests, same workload.
  • Rete/UL or lazy PHREAK · not measured by me; they cut work on rules that cannot fire.

Implementation notes

• Keep back-pointers from facts to their tokens so retract avoids the scan used here (one pointer per token).
• Left memories dominate cost: store tokens as indexes into a fact arena, not copies.
• An update is retract plus assert.
• Add refraction (one firing per activation) and a firing limit.

Pitfalls

• An unselective first condition builds huge token sets.
• Rules that modify facts they match loop (Drools: no-loop).
• not and exists conditions need counted memories or they go stale on retract.
• Lazy propagation (Drools default) can change results that depend on insertion order; see @Propagation in the docs.

Variants and alternatives

In production

• Business rules (insurance, banking eligibility and pricing): Drools in Java applications.
• Expert systems: CLIPS, NASA Johnson Space Center 1985-1996, public domain since 1996.
• Fraud, clinical, network-alarm and logistics rules are typical uses; no named deployment verified.

Implementations

No maintained Rust Rete crate found (crates.io rete 0.0.1, 2020).

Sources

• Charles L. Forgy, Rete: A fast algorithm for the many pattern/many object pattern match problem, Artificial Intelligence 19(1), 17-37, 1982. paper
• Robert B. Doorenbos, Production Matching for Large Learning Systems, PhD thesis, CMU-CS-95-113, Carnegie Mellon University, 1995.
• Daniel P. Miranker, TREAT: A Better Match Algorithm for AI Production Systems, AAAI-87, 1987.
• Drools documentation, Rule engine. docs · code
• CLIPS home page. site