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#[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
34pub 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 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 let mut sorted = rules;
120 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 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 }
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 _ => {
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 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 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 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 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 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
335pub 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}