Skip to main content

graph_grammar/
engine.rs

1use std::collections::{HashMap, HashSet};
2
3use serde::Serialize;
4
5use crate::graph::Host;
6use crate::matching::{find_matches, find_one_match};
7use crate::rewrite::apply_rule_at;
8use crate::rng::Rng;
9use crate::schema::{parse_validated, schema_check};
10use crate::types::{ApiError, Grammar, Graph, MatchResult, Rule};
11
12// ============================================================================
13// Stateful engine ,a port of engine.ts. Drives a rule set over the host graph
14// under a strategy (random/priority/sequential/maximal), with reproducible RNG
15// seeded from config.seed. Holds the graph, RNG, per-rule application counts and
16// the sequential pointer. One step costs one match search.
17// ============================================================================
18
19#[derive(Serialize, Default)]
20pub(crate) struct StepResult {
21    applied: bool,
22    #[serde(rename = "ruleId", skip_serializing_if = "Option::is_none")]
23    rule_id: Option<String>,
24    #[serde(rename = "createdNodes")]
25    created_nodes: Vec<String>,
26    #[serde(rename = "createdEdges")]
27    created_edges: Vec<String>,
28    #[serde(rename = "deletedNodes")]
29    deleted_nodes: Vec<String>,
30    #[serde(rename = "deletedEdges")]
31    deleted_edges: Vec<String>,
32}
33
34/// Opaque stateful engine handle (exposed across the FFI as `Engine*`).
35pub struct Engine {
36    grammar: Grammar,
37    pub(crate) host: Host,
38    rng: Rng,
39    counter: i64,
40    id_seq: i64,
41    steps: i64,
42    app_count: HashMap<String, i64>,
43    seq_ptr: usize,
44}
45
46impl Engine {
47    fn new(grammar: Grammar, start: Option<Graph>) -> Self {
48        let start_graph = start.unwrap_or_else(|| grammar.start.clone());
49        let rng = Rng::new(grammar.config.seed as u32);
50        Engine {
51            host: Host::from_graph(start_graph),
52            grammar,
53            rng,
54            counter: 0,
55            id_seq: 0,
56            steps: 0,
57            app_count: HashMap::new(),
58            seq_ptr: 0,
59        }
60    }
61
62    fn node_delta(&self, rule: &Rule) -> i64 {
63        let preserved: HashSet<&str> =
64            rule.rhs.nodes.iter().filter_map(|n| n.map_from.as_deref()).collect();
65        let created = rule.rhs.nodes.iter().filter(|n| n.map_from.is_none()).count() as i64;
66        let deleted =
67            rule.lhs.nodes.iter().filter(|n| !preserved.contains(n.id.as_str())).count() as i64;
68        created - deleted
69    }
70
71    fn fits_node_budget(&self, rule: &Rule) -> bool {
72        let cap = self.grammar.config.max_nodes;
73        cap <= 0 || self.host.nodes.len() as i64 + self.node_delta(rule) <= cap
74    }
75
76    fn enabled_rules(&self) -> Vec<usize> {
77        (0..self.grammar.rules.len())
78            .filter(|&i| {
79                let r = &self.grammar.rules[i];
80                r.enabled
81                    && !r.lhs.nodes.is_empty()
82                    && (r.max_applications == 0
83                        || self.app_count.get(&r.id).copied().unwrap_or(0) < r.max_applications)
84                    && self.fits_node_budget(r)
85            })
86            .collect()
87    }
88
89    fn nac_blocked(&self, ri: usize) -> bool {
90        self.grammar.rules[ri]
91            .nac
92            .iter()
93            .any(|nac| !nac.nodes.is_empty() && find_one_match(nac, &self.host, None).is_some())
94    }
95
96    /// A single random match for a rule (NAC-aware), or None. Consumes RNG.
97    fn one_match(&mut self, ri: usize) -> Option<MatchResult> {
98        if self.nac_blocked(ri) {
99            return None;
100        }
101        let lhs = &self.grammar.rules[ri].lhs;
102        find_one_match(lhs, &self.host, Some(&mut self.rng))
103    }
104
105    fn pick_rule_and_match(&mut self) -> Option<(usize, MatchResult)> {
106        let rules = self.enabled_rules();
107        if rules.is_empty() {
108            return None;
109        }
110        match self.grammar.config.strategy.as_str() {
111            "priority" => {
112                // Priority wins ACROSS tiers — a higher-priority tier is fully
113                // exhausted before any lower one is considered. But within a tier of
114                // equal-priority PEERS we must not let slice order decide: an
115                // always-matching peer listed first would starve its equals forever.
116                // So among the peers of the highest tier that has a match we draw
117                // WEIGHT-BIASED (reproducibly, via the seeded rng), exactly as the
118                // `random` strategy does — just confined to one tier.
119                let mut sorted = rules;
120                // stable sort by priority desc (mirrors [...].sort((a,b)=>b.priority-a.priority))
121                sorted.sort_by(|&a, &b| {
122                    self.grammar.rules[b]
123                        .priority
124                        .partial_cmp(&self.grammar.rules[a].priority)
125                        .unwrap_or(std::cmp::Ordering::Equal)
126                });
127                let mut i = 0;
128                while i < sorted.len() {
129                    let p = self.grammar.rules[sorted[i]].priority;
130                    let mut tier: Vec<usize> = Vec::new();
131                    while i < sorted.len() && self.grammar.rules[sorted[i]].priority == p {
132                        tier.push(sorted[i]);
133                        i += 1;
134                    }
135                    if tier.len() == 1 {
136                        // Single rule in this tier: no peer draw, so the rng sequence
137                        // (and thus every grammar with all-distinct priorities) is
138                        // unchanged.
139                        if let Some(m) = self.one_match(tier[0]) {
140                            return Some((tier[0], m));
141                        }
142                        continue;
143                    }
144                    let mut weights: Vec<f64> =
145                        tier.iter().map(|&ri| self.grammar.rules[ri].weight).collect();
146                    while !tier.is_empty() {
147                        let idx = self.rng.weighted_index(&weights);
148                        let ri = tier[idx];
149                        if let Some(m) = self.one_match(ri) {
150                            return Some((ri, m));
151                        }
152                        tier.remove(idx);
153                        weights.remove(idx);
154                    }
155                    // No peer in this tier matched — descend to the next lower tier.
156                }
157                None
158            }
159            "sequential" => {
160                let n = rules.len();
161                for i in 0..n {
162                    let ri = rules[(self.seq_ptr + i) % n];
163                    if let Some(m) = self.one_match(ri) {
164                        self.seq_ptr = (self.seq_ptr + i + 1) % n;
165                        return Some((ri, m));
166                    }
167                }
168                None
169            }
170            // random (default): weight-biased draw among applicable rules; first
171            // that matches wins, without probing every rule up front.
172            _ => {
173                let mut pool = rules;
174                let mut weights: Vec<f64> =
175                    pool.iter().map(|&ri| self.grammar.rules[ri].weight).collect();
176                while !pool.is_empty() {
177                    let idx = self.rng.weighted_index(&weights);
178                    let ri = pool[idx];
179                    if let Some(m) = self.one_match(ri) {
180                        return Some((ri, m));
181                    }
182                    pool.remove(idx);
183                    weights.remove(idx);
184                }
185                None
186            }
187        }
188    }
189
190    fn pick_maximal_rule(&mut self) -> Option<usize> {
191        // Filter is deterministic (no RNG); only the weighted pick draws.
192        let candidates: Vec<usize> = self
193            .enabled_rules()
194            .into_iter()
195            .filter(|&ri| {
196                !self.nac_blocked(ri)
197                    && !find_matches(&self.grammar.rules[ri].lhs, &self.host, 1, None).is_empty()
198            })
199            .collect();
200        if candidates.is_empty() {
201            return None;
202        }
203        let weights: Vec<f64> = candidates.iter().map(|&ri| self.grammar.rules[ri].weight).collect();
204        let idx = self.rng.weighted_index(&weights);
205        Some(candidates[idx])
206    }
207
208    fn apply_maximal(&mut self, ri: usize) -> Result<StepResult, ApiError> {
209        // All matches, deterministic order, then shuffled (mirrors applyMaximal).
210        let mut matches = find_matches(&self.grammar.rules[ri].lhs, &self.host, 0, None);
211        if matches.is_empty() {
212            return Ok(StepResult::default());
213        }
214        self.rng.shuffle(&mut matches);
215
216        let mut used: HashSet<String> = HashSet::new();
217        let mut agg = StepResult::default();
218        let mut count = 0i64;
219        for m in &matches {
220            let nodes: Vec<String> = m.node_map.values().cloned().collect();
221            if nodes.iter().any(|n| used.contains(n)) {
222                continue;
223            }
224            let prob = self.grammar.rules[ri].probability;
225            if prob < 1.0 && self.rng.next() > prob {
226                continue;
227            }
228            let max_app = self.grammar.rules[ri].max_applications;
229            let id = self.grammar.rules[ri].id.clone();
230            if max_app != 0 && self.app_count.get(&id).copied().unwrap_or(0) >= max_app {
231                break;
232            }
233            if !self.fits_node_budget(&self.grammar.rules[ri]) {
234                break;
235            }
236            let out = apply_rule_at(
237                &mut self.host,
238                &self.grammar.rules[ri],
239                m,
240                Some(&mut self.rng),
241                &mut self.counter,
242                &mut self.id_seq,
243            )?;
244            for n in nodes {
245                used.insert(n);
246            }
247            agg.created_nodes.extend(out.created_nodes);
248            agg.created_edges.extend(out.created_edges);
249            agg.deleted_nodes.extend(out.deleted_nodes);
250            agg.deleted_edges.extend(out.deleted_edges);
251            *self.app_count.entry(id).or_insert(0) += 1;
252            count += 1;
253        }
254        if count > 0 {
255            self.steps += 1;
256        }
257        agg.applied = count > 0;
258        agg.rule_id = Some(self.grammar.rules[ri].id.clone());
259        Ok(agg)
260    }
261
262    pub(crate) fn step(&mut self) -> Result<StepResult, ApiError> {
263        if self.grammar.config.strategy == "maximal" {
264            return match self.pick_maximal_rule() {
265                Some(ri) => self.apply_maximal(ri),
266                None => Ok(StepResult::default()),
267            };
268        }
269
270        let Some((ri, m)) = self.pick_rule_and_match() else {
271            return Ok(StepResult::default());
272        };
273
274        // Probability gate: a no-op step that still returns a ruleId so the run
275        // loop retries.
276        let prob = self.grammar.rules[ri].probability;
277        if prob < 1.0 && self.rng.next() > prob {
278            return Ok(StepResult { rule_id: Some(self.grammar.rules[ri].id.clone()), ..Default::default() });
279        }
280
281        let out = apply_rule_at(
282            &mut self.host,
283            &self.grammar.rules[ri],
284            &m,
285            Some(&mut self.rng),
286            &mut self.counter,
287            &mut self.id_seq,
288        )?;
289        let id = self.grammar.rules[ri].id.clone();
290        *self.app_count.entry(id.clone()).or_insert(0) += 1;
291        self.steps += 1;
292        Ok(StepResult {
293            applied: true,
294            rule_id: Some(id),
295            created_nodes: out.created_nodes,
296            created_edges: out.created_edges,
297            deleted_nodes: out.deleted_nodes,
298            deleted_edges: out.deleted_edges,
299        })
300    }
301
302    /// Run until no rule applies or a bound is hit. `max_steps`: None → use
303    /// config.maxSteps; <=0 → an uncapped run with a hard safety bound.
304    pub(crate) fn run(&mut self, max_steps: Option<i64>) -> Result<i64, ApiError> {
305        let requested = max_steps.unwrap_or(self.grammar.config.max_steps);
306        let cap: i64 = if requested > 0 { requested } else { 500_000 };
307        let mut applied = 0i64;
308        let mut empty_streak = 0;
309        for _ in 0..cap {
310            let r = self.step()?;
311            if !r.applied {
312                // probability skips return a ruleId; allow bounded retries.
313                if r.rule_id.is_some() && empty_streak < 64 {
314                    empty_streak += 1;
315                    continue;
316                }
317                break;
318            }
319            empty_streak = 0;
320            applied += 1;
321        }
322        Ok(applied)
323    }
324}
325
326pub(crate) fn engine_from_json(grammar_json: &str, start_json: Option<&str>) -> Result<Engine, ApiError> {
327    let grammar: Grammar = parse_validated(grammar_json, schema_check::grammar(), "grammar")?;
328    let start = match start_json {
329        Some(s) => Some(parse_validated::<Graph>(s, schema_check::graph(), "start graph")?),
330        None => None,
331    };
332    Ok(Engine::new(grammar, start))
333}
334
335/// Build an engine from a grammar, run it, and return `(final_graph_json, applied)`.
336/// Convenience for tests / one-shot use; the FFI uses the stateful handle.
337pub fn run_grammar(
338    grammar_json: &str,
339    start_json: Option<&str>,
340    max_steps: Option<i64>,
341) -> Result<(String, i64), ApiError> {
342    let mut engine = engine_from_json(grammar_json, start_json)?;
343    let applied = engine.run(max_steps)?;
344    let graph = serde_json::to_string(&engine.host.to_graph()).expect("graph serializes");
345    Ok((graph, applied))
346}