pepl_types/
ast_diff.rs

1//! AST diff infrastructure for PEPL.
2//!
3//! Compares two PEPL ASTs and produces a structured list of changes.
4//! Used for:
5//! - Evolve operation scope validation
6//! - Incremental compilation (re-codegen only changed subtrees)
7//! - Event storage optimization (store diffs instead of full snapshots)
8//! - PEPL's transformation guarantee: "diffs are AST-level, not line-level"
9
10use crate::ast::*;
11use serde::{Deserialize, Serialize};
12
13// ══════════════════════════════════════════════════════════════════════════════
14// Types
15// ══════════════════════════════════════════════════════════════════════════════
16
17/// A single change between two ASTs.
18#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
19pub struct AstChange {
20    /// Dot-separated path to the changed node (e.g., "state.count", "actions.increment").
21    pub path: String,
22    /// The kind of change.
23    pub kind: ChangeKind,
24}
25
26/// What kind of change occurred.
27#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
28pub enum ChangeKind {
29    /// A node was added (not present in old AST).
30    Added,
31    /// A node was removed (not present in new AST).
32    Removed,
33    /// A node was modified (present in both, but different).
34    Modified,
35}
36
37/// A structured diff between two PEPL ASTs.
38#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
39pub struct AstDiff {
40    pub changes: Vec<AstChange>,
41}
42
43/// Allowed scope for change validation.
44#[derive(Debug, Clone, PartialEq)]
45pub enum AllowedScope {
46    /// Any change is allowed.
47    Any,
48    /// Only changes within these paths are allowed.
49    Paths(Vec<String>),
50}
51
52// ══════════════════════════════════════════════════════════════════════════════
53// Core diff
54// ══════════════════════════════════════════════════════════════════════════════
55
56impl AstDiff {
57    /// Compute the diff between two programs.
58    pub fn diff(old: &Program, new: &Program) -> Self {
59        let mut changes = Vec::new();
60        diff_program(old, new, &mut changes);
61        AstDiff { changes }
62    }
63
64    /// True if the two ASTs are identical (no changes).
65    pub fn is_empty(&self) -> bool {
66        self.changes.is_empty()
67    }
68
69    /// Number of changes.
70    pub fn len(&self) -> usize {
71        self.changes.len()
72    }
73
74    /// Serialize to compact JSON.
75    pub fn to_json(&self) -> String {
76        serde_json::to_string(self).unwrap_or_else(|_| "[]".to_string())
77    }
78
79    /// Deserialize from JSON.
80    pub fn from_json(json: &str) -> Result<Self, serde_json::Error> {
81        serde_json::from_str(json)
82    }
83
84    /// Validate that all changes fall within allowed scopes.
85    /// Returns the list of out-of-scope changes (empty = all valid).
86    pub fn validate_scope(&self, scope: &AllowedScope) -> Vec<&AstChange> {
87        match scope {
88            AllowedScope::Any => vec![],
89            AllowedScope::Paths(allowed) => self
90                .changes
91                .iter()
92                .filter(|c| !allowed.iter().any(|a| c.path.starts_with(a)))
93                .collect(),
94        }
95    }
96}
97
98// ══════════════════════════════════════════════════════════════════════════════
99// Diff walkers
100// ══════════════════════════════════════════════════════════════════════════════
101
102fn push(changes: &mut Vec<AstChange>, path: &str, kind: ChangeKind) {
103    changes.push(AstChange {
104        path: path.to_string(),
105        kind,
106    });
107}
108
109fn diff_program(old: &Program, new: &Program, changes: &mut Vec<AstChange>) {
110    // Space name
111    if old.space.name.name != new.space.name.name {
112        push(changes, "space.name", ChangeKind::Modified);
113    }
114
115    // Space body
116    diff_space_body(&old.space.body, &new.space.body, changes);
117
118    // Test blocks – TestsBlock has no name, so diff by index; inner cases keyed by description
119    let max_tests = old.tests.len().max(new.tests.len());
120    for i in 0..max_tests {
121        match (old.tests.get(i), new.tests.get(i)) {
122            (Some(o), Some(n)) => {
123                diff_vec_by_name(
124                    &o.cases,
125                    &n.cases,
126                    |c| c.description.clone(),
127                    &format!("tests[{}].cases", i),
128                    changes,
129                );
130            }
131            (None, Some(_)) => {
132                changes.push(AstChange {
133                    path: format!("tests[{}]", i),
134                    kind: ChangeKind::Added,
135                });
136            }
137            (Some(_), None) => {
138                changes.push(AstChange {
139                    path: format!("tests[{}]", i),
140                    kind: ChangeKind::Removed,
141                });
142            }
143            (None, None) => {}
144        }
145    }
146}
147
148fn diff_space_body(old: &SpaceBody, new: &SpaceBody, changes: &mut Vec<AstChange>) {
149    // Types
150    diff_vec_by_name(
151        &old.types,
152        &new.types,
153        |t| t.name.name.clone(),
154        "types",
155        changes,
156    );
157
158    // State fields
159    diff_vec_by_name(
160        &old.state.fields,
161        &new.state.fields,
162        |f| f.name.name.clone(),
163        "state",
164        changes,
165    );
166
167    // Capabilities
168    match (&old.capabilities, &new.capabilities) {
169        (None, Some(_)) => push(changes, "capabilities", ChangeKind::Added),
170        (Some(_), None) => push(changes, "capabilities", ChangeKind::Removed),
171        (Some(o), Some(n)) => {
172            // Required capabilities
173            diff_vec_by_name(
174                &o.required,
175                &n.required,
176                |c| c.name.clone(),
177                "capabilities.required",
178                changes,
179            );
180            // Optional capabilities
181            diff_vec_by_name(
182                &o.optional,
183                &n.optional,
184                |c| c.name.clone(),
185                "capabilities.optional",
186                changes,
187            );
188        }
189        (None, None) => {}
190    }
191
192    // Credentials
193    match (&old.credentials, &new.credentials) {
194        (None, Some(_)) => push(changes, "credentials", ChangeKind::Added),
195        (Some(_), None) => push(changes, "credentials", ChangeKind::Removed),
196        (Some(o), Some(n)) => {
197            diff_vec_by_name(
198                &o.fields,
199                &n.fields,
200                |c| c.name.name.clone(),
201                "credentials",
202                changes,
203            );
204        }
205        (None, None) => {}
206    }
207
208    // Derived
209    match (&old.derived, &new.derived) {
210        (None, Some(_)) => push(changes, "derived", ChangeKind::Added),
211        (Some(_), None) => push(changes, "derived", ChangeKind::Removed),
212        (Some(o), Some(n)) => {
213            diff_vec_by_name(
214                &o.fields,
215                &n.fields,
216                |f| f.name.name.clone(),
217                "derived",
218                changes,
219            );
220        }
221        (None, None) => {}
222    }
223
224    // Invariants
225    diff_vec_by_name(
226        &old.invariants,
227        &new.invariants,
228        |i| i.name.name.clone(),
229        "invariants",
230        changes,
231    );
232
233    // Actions
234    diff_vec_by_name(
235        &old.actions,
236        &new.actions,
237        |a| a.name.name.clone(),
238        "actions",
239        changes,
240    );
241
242    // Views
243    diff_vec_by_name(
244        &old.views,
245        &new.views,
246        |v| v.name.name.clone(),
247        "views",
248        changes,
249    );
250
251    // Update
252    diff_option_block(&old.update, &new.update, "update", changes);
253
254    // HandleEvent
255    diff_option_block(&old.handle_event, &new.handle_event, "handleEvent", changes);
256}
257
258/// Diff two vectors of named items. Items are matched by name.
259fn diff_vec_by_name<T: PartialEq>(
260    old: &[T],
261    new: &[T],
262    name_fn: impl Fn(&T) -> String,
263    prefix: &str,
264    changes: &mut Vec<AstChange>,
265) {
266    let old_names: Vec<String> = old.iter().map(&name_fn).collect();
267    let new_names: Vec<String> = new.iter().map(&name_fn).collect();
268
269    // Removed items
270    for (i, name) in old_names.iter().enumerate() {
271        if !new_names.contains(name) {
272            push(changes, &format!("{prefix}.{name}"), ChangeKind::Removed);
273        } else {
274            // Check if modified
275            let new_idx = new_names.iter().position(|n| n == name).unwrap();
276            if old[i] != new[new_idx] {
277                push(changes, &format!("{prefix}.{name}"), ChangeKind::Modified);
278            }
279        }
280    }
281
282    // Added items
283    for name in &new_names {
284        if !old_names.contains(name) {
285            push(changes, &format!("{prefix}.{name}"), ChangeKind::Added);
286        }
287    }
288}
289
290/// Diff optional blocks (update, handle_event).
291fn diff_option_block<T: PartialEq>(
292    old: &Option<T>,
293    new: &Option<T>,
294    name: &str,
295    changes: &mut Vec<AstChange>,
296) {
297    match (old, new) {
298        (None, Some(_)) => push(changes, name, ChangeKind::Added),
299        (Some(_), None) => push(changes, name, ChangeKind::Removed),
300        (Some(o), Some(n)) if o != n => push(changes, name, ChangeKind::Modified),
301        _ => {}
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308    use crate::Span;
309
310    fn span() -> Span {
311        Span::new(0, 0, 0, 0)
312    }
313
314    fn ident(name: &str) -> Ident {
315        Ident {
316            name: name.to_string(),
317            span: span(),
318        }
319    }
320
321    fn minimal_program(name: &str) -> Program {
322        Program {
323            space: SpaceDecl {
324                name: ident(name),
325                body: SpaceBody {
326                    types: vec![],
327                    state: StateBlock {
328                        fields: vec![],
329                        span: span(),
330                    },
331                    capabilities: None,
332                    credentials: None,
333                    derived: None,
334                    invariants: vec![],
335                    actions: vec![],
336                    views: vec![],
337                    update: None,
338                    handle_event: None,
339                    span: span(),
340                },
341                span: span(),
342            },
343            tests: vec![],
344            span: span(),
345        }
346    }
347
348    fn with_state_field(mut prog: Program, name: &str, default: Expr) -> Program {
349        prog.space.body.state.fields.push(StateField {
350            name: ident(name),
351            type_ann: TypeAnnotation {
352                kind: TypeKind::Named("number".to_string()),
353                span: span(),
354            },
355            default,
356            span: span(),
357        });
358        prog
359    }
360
361    fn with_action(mut prog: Program, name: &str) -> Program {
362        prog.space.body.actions.push(ActionDecl {
363            name: ident(name),
364            params: vec![],
365            body: Block {
366                stmts: vec![],
367                span: span(),
368            },
369            span: span(),
370        });
371        prog
372    }
373
374    fn with_view(mut prog: Program, name: &str) -> Program {
375        prog.space.body.views.push(ViewDecl {
376            name: ident(name),
377            params: vec![],
378            body: UIBlock {
379                elements: vec![],
380                span: span(),
381            },
382            span: span(),
383        });
384        prog
385    }
386
387    fn num_literal(n: f64) -> Expr {
388        Expr::new(ExprKind::NumberLit(n), span())
389    }
390
391    #[allow(dead_code)]
392    fn str_literal(s: &str) -> Expr {
393        Expr::new(ExprKind::StringLit(s.to_string()), span())
394    }
395
396    // ─── Tests ───────────────────────────────────────────────────────────
397
398    #[test]
399    fn identical_programs_produce_empty_diff() {
400        let a = minimal_program("Test");
401        let b = minimal_program("Test");
402        let diff = AstDiff::diff(&a, &b);
403        assert!(diff.is_empty());
404        assert_eq!(diff.len(), 0);
405    }
406
407    #[test]
408    fn space_name_change_detected() {
409        let a = minimal_program("Old");
410        let b = minimal_program("New");
411        let diff = AstDiff::diff(&a, &b);
412        assert_eq!(diff.len(), 1);
413        assert_eq!(diff.changes[0].path, "space.name");
414        assert_eq!(diff.changes[0].kind, ChangeKind::Modified);
415    }
416
417    #[test]
418    fn state_field_added() {
419        let a = minimal_program("T");
420        let b = with_state_field(minimal_program("T"), "count", num_literal(0.0));
421        let diff = AstDiff::diff(&a, &b);
422        assert_eq!(diff.len(), 1);
423        assert_eq!(diff.changes[0].path, "state.count");
424        assert_eq!(diff.changes[0].kind, ChangeKind::Added);
425    }
426
427    #[test]
428    fn state_field_removed() {
429        let a = with_state_field(minimal_program("T"), "count", num_literal(0.0));
430        let b = minimal_program("T");
431        let diff = AstDiff::diff(&a, &b);
432        assert_eq!(diff.len(), 1);
433        assert_eq!(diff.changes[0].path, "state.count");
434        assert_eq!(diff.changes[0].kind, ChangeKind::Removed);
435    }
436
437    #[test]
438    fn state_field_modified() {
439        let a = with_state_field(minimal_program("T"), "count", num_literal(0.0));
440        let b = with_state_field(minimal_program("T"), "count", num_literal(42.0));
441        let diff = AstDiff::diff(&a, &b);
442        assert_eq!(diff.len(), 1);
443        assert_eq!(diff.changes[0].path, "state.count");
444        assert_eq!(diff.changes[0].kind, ChangeKind::Modified);
445    }
446
447    #[test]
448    fn action_added() {
449        let a = minimal_program("T");
450        let b = with_action(minimal_program("T"), "increment");
451        let diff = AstDiff::diff(&a, &b);
452        assert_eq!(diff.len(), 1);
453        assert_eq!(diff.changes[0].path, "actions.increment");
454        assert_eq!(diff.changes[0].kind, ChangeKind::Added);
455    }
456
457    #[test]
458    fn action_removed() {
459        let a = with_action(minimal_program("T"), "increment");
460        let b = minimal_program("T");
461        let diff = AstDiff::diff(&a, &b);
462        assert_eq!(diff.len(), 1);
463        assert_eq!(diff.changes[0].path, "actions.increment");
464        assert_eq!(diff.changes[0].kind, ChangeKind::Removed);
465    }
466
467    #[test]
468    fn view_modified() {
469        let a = with_view(minimal_program("T"), "main");
470        let mut b = with_view(minimal_program("T"), "main");
471        // Modify the view by adding an element
472        b.space.body.views[0].body.elements.push(UIElement::Component(ComponentExpr {
473            name: ident("Text"),
474            props: vec![],
475            children: None,
476            span: span(),
477        }));
478        let diff = AstDiff::diff(&a, &b);
479        assert_eq!(diff.len(), 1);
480        assert_eq!(diff.changes[0].path, "views.main");
481        assert_eq!(diff.changes[0].kind, ChangeKind::Modified);
482    }
483
484    #[test]
485    fn multiple_changes_detected() {
486        let a = with_state_field(
487            with_action(minimal_program("T"), "old_action"),
488            "x",
489            num_literal(0.0),
490        );
491        let b = with_state_field(
492            with_action(minimal_program("T"), "new_action"),
493            "x",
494            num_literal(1.0),
495        );
496        let diff = AstDiff::diff(&a, &b);
497        // state.x modified, actions.old_action removed, actions.new_action added
498        assert_eq!(diff.len(), 3);
499    }
500
501    #[test]
502    fn json_round_trip() {
503        let a = minimal_program("T");
504        let b = with_state_field(minimal_program("T"), "x", num_literal(0.0));
505        let diff = AstDiff::diff(&a, &b);
506        let json = diff.to_json();
507        let restored = AstDiff::from_json(&json).unwrap();
508        assert_eq!(diff, restored);
509    }
510
511    #[test]
512    fn scope_validation_any_allows_all() {
513        let a = minimal_program("T");
514        let b = with_state_field(minimal_program("T"), "x", num_literal(0.0));
515        let diff = AstDiff::diff(&a, &b);
516        let violations = diff.validate_scope(&AllowedScope::Any);
517        assert!(violations.is_empty());
518    }
519
520    #[test]
521    fn scope_validation_rejects_out_of_scope() {
522        let a = minimal_program("T");
523        let b = with_action(
524            with_state_field(minimal_program("T"), "x", num_literal(0.0)),
525            "inc",
526        );
527        let diff = AstDiff::diff(&a, &b);
528        let violations = diff.validate_scope(&AllowedScope::Paths(vec!["state".to_string()]));
529        assert_eq!(violations.len(), 1);
530        assert_eq!(violations[0].path, "actions.inc");
531    }
532
533    #[test]
534    fn scope_validation_accepts_in_scope() {
535        let a = minimal_program("T");
536        let b = with_state_field(minimal_program("T"), "x", num_literal(0.0));
537        let diff = AstDiff::diff(&a, &b);
538        let violations = diff.validate_scope(&AllowedScope::Paths(vec!["state".to_string()]));
539        assert!(violations.is_empty());
540    }
541
542    #[test]
543    fn empty_diff_json() {
544        let diff = AstDiff {
545            changes: vec![],
546        };
547        let json = diff.to_json();
548        assert_eq!(json, r#"{"changes":[]}"#);
549    }
550}
pepl_types/ast_diff.rs

pepl_types/
ast_diff.rs
