conjure_core/rule_engine/
rewrite_naive.rs

1use super::{resolve_rules::RuleData, RewriteError, RuleSet};
2use crate::{
3    ast::{Expression as Expr, SubModel},
4    bug,
5    rule_engine::{
6        get_rules_grouped,
7        rewriter_common::{log_rule_application, RuleResult},
8        submodel_zipper::submodel_ctx,
9    },
10    Model,
11};
12
13use itertools::Itertools;
14use std::sync::Arc;
15use tracing::trace;
16use uniplate::Biplate;
17
18/// A naive, exhaustive rewriter for development purposes. Applies rules in priority order,
19/// favouring expressions found earlier during preorder traversal of the tree.
20pub fn rewrite_naive<'a>(
21    model: &Model,
22    rule_sets: &Vec<&'a RuleSet<'a>>,
23    prop_multiple_equally_applicable: bool,
24) -> Result<Model, RewriteError> {
25    let rules_grouped = get_rules_grouped(rule_sets)
26        .unwrap_or_else(|_| bug!("get_rule_priorities() failed!"))
27        .into_iter()
28        .collect_vec();
29
30    let mut model = model.clone();
31    let mut done_something = true;
32
33    trace!(
34        target: "rule_engine_human",
35        "Model before rewriting:\n\n{}\n--\n",
36        model
37    );
38
39    // Rewrite until there are no more rules left to apply.
40    while done_something {
41        let mut new_model = None;
42        done_something = false;
43
44        // Rewrite each sub-model in the tree, largest first.
45        for (mut submodel, ctx) in <_ as Biplate<SubModel>>::contexts_bi(&model) {
46            if try_rewrite_model(
47                &mut submodel,
48                &rules_grouped,
49                prop_multiple_equally_applicable,
50            )
51            .is_some()
52            {
53                new_model = Some(ctx(submodel));
54                done_something = true;
55                break;
56            }
57        }
58        if let Some(new_model) = new_model {
59            model = new_model;
60        }
61    }
62
63    trace!(
64        target: "rule_engine_human",
65        "Final model:\n\n{}",
66        model
67    );
68    Ok(model)
69}
70
71// Tries to do a single rewrite on the model.
72//
73// Returns None if no change was made.
74fn try_rewrite_model(
75    submodel: &mut SubModel,
76    rules_grouped: &Vec<(u16, Vec<RuleData<'_>>)>,
77    prop_multiple_equally_applicable: bool,
78) -> Option<()> {
79    type CtxFn = Arc<dyn Fn(Expr) -> SubModel>;
80    let mut results: Vec<(RuleResult<'_>, u16, Expr, CtxFn)> = vec![];
81
82    // Iterate over rules by priority in descending order.
83    'top: for (priority, rules) in rules_grouped.iter() {
84        // Using Biplate, rewrite both the expression tree, and any value lettings in the symbol
85        // table.
86        for (expr, ctx) in submodel_ctx(submodel.clone()) {
87            // Clone expr and ctx so they can be reused
88            let expr = expr.clone();
89            let ctx = ctx.clone();
90            for rd in rules {
91                match (rd.rule.application)(&expr, &submodel.symbols()) {
92                    Ok(red) => {
93                        // Collect applicable rules
94                        results.push((
95                            RuleResult {
96                                rule_data: rd.clone(),
97                                reduction: red,
98                            },
99                            *priority,
100                            expr.clone(),
101                            ctx.clone(),
102                        ));
103                    }
104                    Err(_) => {
105                        // when called a lot, this becomes very expensive!
106                        #[cfg(debug_assertions)]
107                        tracing::trace!(
108                            "Rule attempted but not applied: {} (priority {}, rule set {}), to expression: {}",
109                            rd.rule.name,
110                            priority,
111                            rd.rule_set.name,
112                            expr
113                        );
114                    }
115                }
116            }
117            // This expression has the highest rule priority so far, so this is what we want to
118            // rewrite.
119            if !results.is_empty() {
120                break 'top;
121            }
122        }
123    }
124
125    match results.as_slice() {
126        [] => {
127            return None;
128        } // no rules are applicable.
129        [(result, _priority, expr, ctx), ..] => {
130            if prop_multiple_equally_applicable {
131                assert_no_multiple_equally_applicable_rules(&results, rules_grouped);
132            }
133
134            // Extract the single applicable rule and apply it
135            log_rule_application(result, expr, submodel);
136
137            // Replace expr with new_expression
138            *submodel = ctx(result.reduction.new_expression.clone());
139
140            // Apply new symbols and top level
141            result.reduction.clone().apply(submodel);
142        }
143    }
144
145    Some(())
146}
147
148// Exits with a bug if there are multiple equally applicable rules for an expression.
149fn assert_no_multiple_equally_applicable_rules<CtxFnType>(
150    results: &Vec<(RuleResult<'_>, u16, Expr, CtxFnType)>,
151    rules_grouped: &Vec<(u16, Vec<RuleData<'_>>)>,
152) {
153    if results.len() <= 1 {
154        return;
155    }
156
157    let names: Vec<_> = results
158        .iter()
159        .map(|(result, _, _, _)| result.rule_data.rule.name)
160        .collect();
161
162    // Extract the expression from the first result
163    let expr = results[0].2.clone();
164
165    // Construct a single string to display the names of the rules grouped by priority
166    let mut rules_by_priority_string = String::new();
167    rules_by_priority_string.push_str("Rules grouped by priority:\n");
168    for (priority, rules) in rules_grouped.iter() {
169        rules_by_priority_string.push_str(&format!("Priority {}:\n", priority));
170        for rd in rules {
171            rules_by_priority_string.push_str(&format!(
172                "  - {} (from {})\n",
173                rd.rule.name, rd.rule_set.name
174            ));
175        }
176    }
177    bug!("Multiple equally applicable rules for {expr}: {names:#?}\n\n{rules_by_priority_string}");
178}
conjure_core/rule_engine/rewrite_naive.rs

conjure_core/rule_engine/
rewrite_naive.rs
