rust_runes/
knowledge_base.rs

1use crate::compiled::{CompiledRule, Interner, PathIndex};
2use crate::parser::GrlParser;
3use crate::rule::Rule;
4use std::collections::HashMap;
5use std::path::{Path, PathBuf};
6
7/// A set of rules, kept in salience order and compiled for execution.
8///
9/// A [`RuleEngine`](crate::RuleEngine) holds one; rules are usually added through the
10/// engine's `add_rules_from_*` methods.
11#[derive(Debug, Default)]
12pub struct KnowledgeBase {
13    rules: Vec<Rule>,
14    rule_index: HashMap<String, usize>,
15    /// Indices into `rules`, highest salience first; ties keep insertion order.
16    /// Maintained on insert/remove so execution never has to sort.
17    salience_order: Vec<usize>,
18    /// `rules[i]` compiled for execution
19    compiled: Vec<CompiledRule>,
20    /// `position_of[i]` is where `rules[i]` sits in `salience_order`
21    position_of: Vec<usize>,
22    /// Shares memo slots between identical sub-expressions across rules
23    interner: Interner,
24    /// For each fact name, the rules whose conditions read it
25    readers: PathIndex,
26    /// How many rules have conditions with effects, or that call methods
27    /// (which may turn out to be user-registered)
28    effectful_conditions: usize,
29    conditions_with_methods: usize,
30}
31
32impl KnowledgeBase {
33    /// An empty knowledge base.
34    pub fn new() -> Self {
35        Self::default()
36    }
37
38    /// Adds a rule. Fails if a rule with the same name exists.
39    pub fn add_rule(&mut self, rule: Rule) -> Result<(), String> {
40        if self.rule_index.contains_key(&rule.name) {
41            return Err(format!("Rule '{}' already exists", rule.name));
42        }
43
44        let index = self.rules.len();
45        let position = self
46            .salience_order
47            .partition_point(|&i| self.rules[i].salience >= rule.salience);
48        self.salience_order.insert(position, index);
49        self.position_of.push(position);
50        for (p, &i) in self.salience_order.iter().enumerate().skip(position) {
51            self.position_of[i] = p;
52        }
53        self.rule_index.insert(rule.name.clone(), index);
54        let compiled = CompiledRule::new(&rule, &mut self.interner);
55        self.add_readers(index, &compiled);
56        self.compiled.push(compiled);
57        self.rules.push(rule);
58        Ok(())
59    }
60
61    /// Parses GRL text and adds all of its rules. Returns how many were added.
62    /// Nothing is added if any rule fails to parse or clashes with an existing name.
63    pub fn add_rules_from_str(&mut self, grl: &str) -> Result<usize, String> {
64        let rules = GrlParser::new().parse_rules(grl)?;
65        let mut names = std::collections::HashSet::new();
66        for rule in &rules {
67            if self.rule_index.contains_key(&rule.name) || !names.insert(&rule.name) {
68                return Err(format!("Rule '{}' already exists", rule.name));
69            }
70        }
71        let count = rules.len();
72        for rule in rules {
73            self.add_rule(rule)?;
74        }
75        Ok(count)
76    }
77
78    /// Loads all rules from a `.grl` file. Returns how many were added.
79    pub fn add_rules_from_file(&mut self, path: impl AsRef<Path>) -> Result<usize, String> {
80        let path = path.as_ref();
81        let grl =
82            std::fs::read_to_string(path).map_err(|e| format!("{}: {}", path.display(), e))?;
83        self.add_rules_from_str(&grl)
84            .map_err(|e| format!("{}: {}", path.display(), e))
85    }
86
87    /// Loads all `.grl` files under `dir`, recursively, in path order.
88    /// Returns how many rules were added.
89    pub fn add_rules_from_dir(&mut self, dir: impl AsRef<Path>) -> Result<usize, String> {
90        let mut files = Vec::new();
91        collect_grl_files(dir.as_ref(), &mut files)?;
92        files.sort();
93        let mut count = 0;
94        for file in files {
95            count += self.add_rules_from_file(&file)?;
96        }
97        Ok(count)
98    }
99
100    /// The rule with the given name.
101    pub fn get_rule(&self, name: &str) -> Option<&Rule> {
102        self.rule_index
103            .get(name)
104            .and_then(|&index| self.rules.get(index))
105    }
106
107    /// All rules, in the order they were added.
108    pub fn get_rules(&self) -> &[Rule] {
109        &self.rules
110    }
111
112    /// All rules, highest salience first; rules with equal salience in the order they
113    /// were added.
114    pub fn get_rules_sorted_by_salience(&self) -> Vec<&Rule> {
115        self.rules_by_salience().collect()
116    }
117
118    /// Iterates rules highest salience first; rules with equal salience come in
119    /// the order they were added.
120    pub fn rules_by_salience(&self) -> impl Iterator<Item = &Rule> + '_ {
121        self.salience_order.iter().map(|&i| &self.rules[i])
122    }
123
124    /// The rule at `position` in salience order, with its index and compiled form.
125    pub(crate) fn entry_at(&self, position: usize) -> (usize, &Rule, &CompiledRule) {
126        let i = self.salience_order[position];
127        (i, &self.rules[i], &self.compiled[i])
128    }
129
130    /// Where the rule with index `index` sits in salience order.
131    pub(crate) fn position_of(&self, index: usize) -> usize {
132        self.position_of[index]
133    }
134
135    pub(crate) fn index_of(&self, name: &str) -> Option<usize> {
136        self.rule_index.get(name).copied()
137    }
138
139    pub(crate) fn interner(&self) -> &Interner {
140        &self.interner
141    }
142
143    /// Indices of the rules whose conditions read the fact `root`.
144    pub(crate) fn readers(&self) -> &PathIndex {
145        &self.readers
146    }
147
148    /// Whether every rule's condition can be skipped without observable effects,
149    /// given whether any user methods are registered.
150    pub(crate) fn all_conditions_skippable(&self, user_methods_registered: bool) -> bool {
151        self.effectful_conditions == 0
152            && (!user_methods_registered || self.conditions_with_methods == 0)
153    }
154
155    fn add_readers(&mut self, index: usize, compiled: &CompiledRule) {
156        self.effectful_conditions += compiled.has_effects as usize;
157        self.conditions_with_methods += !compiled.condition_methods.is_empty() as usize;
158        self.readers.add(index, &compiled.reads);
159    }
160
161    /// Removes and returns the rule with the given name.
162    pub fn remove_rule(&mut self, name: &str) -> Option<Rule> {
163        if let Some(&index) = self.rule_index.get(name) {
164            let rule = self.rules.remove(index);
165            self.compiled.remove(index);
166            self.rule_index.remove(name);
167
168            // Update indices for rules that came after the removed rule
169            for rule_index in self.rule_index.values_mut() {
170                if *rule_index > index {
171                    *rule_index -= 1;
172                }
173            }
174            self.salience_order.retain(|&i| i != index);
175            for i in self.salience_order.iter_mut() {
176                if *i > index {
177                    *i -= 1;
178                }
179            }
180            self.position_of = vec![0; self.rules.len()];
181            for (p, &i) in self.salience_order.iter().enumerate() {
182                self.position_of[i] = p;
183            }
184            let compiled = std::mem::take(&mut self.compiled);
185            self.readers = PathIndex::default();
186            self.effectful_conditions = 0;
187            self.conditions_with_methods = 0;
188            for (i, rule) in compiled.iter().enumerate() {
189                self.add_readers(i, rule);
190            }
191            self.compiled = compiled;
192
193            Some(rule)
194        } else {
195            None
196        }
197    }
198
199    /// Removes all rules.
200    pub fn clear(&mut self) {
201        self.rules.clear();
202        self.rule_index.clear();
203        self.salience_order.clear();
204        self.compiled.clear();
205        self.position_of.clear();
206        self.interner = Interner::default();
207        self.readers = PathIndex::default();
208        self.effectful_conditions = 0;
209        self.conditions_with_methods = 0;
210    }
211
212    /// The number of rules.
213    pub fn len(&self) -> usize {
214        self.rules.len()
215    }
216
217    /// Whether there are no rules.
218    pub fn is_empty(&self) -> bool {
219        self.rules.is_empty()
220    }
221}
222
223fn collect_grl_files(dir: &Path, files: &mut Vec<PathBuf>) -> Result<(), String> {
224    let entries = std::fs::read_dir(dir).map_err(|e| format!("{}: {}", dir.display(), e))?;
225    for entry in entries {
226        let path = entry
227            .map_err(|e| format!("{}: {}", dir.display(), e))?
228            .path();
229        if path.is_dir() {
230            collect_grl_files(&path, files)?;
231        } else if path
232            .extension()
233            .is_some_and(|ext| ext.eq_ignore_ascii_case("grl"))
234        {
235            files.push(path);
236        }
237    }
238    Ok(())
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244    use crate::ast::Expression;
245
246    fn rule(name: &str, salience: i32) -> Rule {
247        Rule::new(
248            name.to_string(),
249            salience,
250            Expression::Boolean(true),
251            vec![],
252        )
253    }
254
255    fn order(kb: &KnowledgeBase) -> Vec<&str> {
256        kb.rules_by_salience().map(|r| r.name.as_str()).collect()
257    }
258
259    #[test]
260    fn salience_order_is_stable_and_survives_removal() {
261        let mut kb = KnowledgeBase::new();
262        for (name, salience) in [("a", 1), ("b", 5), ("c", 1), ("d", 9), ("e", 5)] {
263            kb.add_rule(rule(name, salience)).unwrap();
264        }
265        assert_eq!(order(&kb), ["d", "b", "e", "a", "c"]);
266
267        kb.remove_rule("b").unwrap();
268        assert_eq!(order(&kb), ["d", "e", "a", "c"]);
269        assert_eq!(kb.get_rule("c").unwrap().name, "c");
270
271        kb.add_rule(rule("f", 5)).unwrap();
272        assert_eq!(order(&kb), ["d", "e", "f", "a", "c"]);
273
274        kb.clear();
275        assert_eq!(order(&kb), Vec::<&str>::new());
276    }
277}
rust_runes/knowledge_base.rs

rust_runes/
knowledge_base.rs
