whipplescript_core/
selection.rs

1//! The provenance-native selection algebra (vw note §7.3; untie
2//! readiness tracker Phase 2): a revset-shaped composable expression
3//! language over recorded change-units, feeding the three selective
4//! verbs (`undo <selection>`, `transport <selection>`, `adopt --only`)
5//! and the archaeology queries.
6//!
7//! Grammar (union `|` loosest, then difference `~`, then intersection
8//! `&`, parens group):
9//!
10//! ```text
11//! expr   := diff ( '|' diff )*
12//! diff   := inter ( '~' inter )*
13//! inter  := prim ( '&' prim )*
14//! prim   := atom | '(' expr ')'
15//! atom   := path(<glob>) | by-effect(<prefix>) | by-origin(<prefix>)
16//!         | by(<prefix>) | intent(<prefix>)
17//!         | in-branch(<id>) | change(<id>) | cut(<id>)
18//!         | since(<stamp>) | until(<stamp>) | dependents-of(expr)
19//! ```
20//!
21//! The unit of selection is one recorded write: (cut, path,
22//! before → after), derived from cut lineage. `dependents-of` is the
23//! slicer seam's conservative floor: path-level dependence (a later
24//! unit on the same path consumed the earlier one's output). The
25//! declaration/slice-granularity atoms (`decl(...)`, `slice-of(...)`)
26//! arrive when the slicer joins as this algebra's client — the grammar
27//! is closed under adding atoms.
28
29use std::collections::BTreeSet;
30
31use serde::{Deserialize, Serialize};
32
33/// One recorded change-unit: what one cut did to one path.
34#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
35pub struct ChangeUnit {
36    /// Position in the branch's cut order, oldest first — the
37    /// dependence direction.
38    pub seq: usize,
39    pub cut_id: String,
40    pub change_id: String,
41    pub branch_id: String,
42    pub path: String,
43    pub before: Option<String>,
44    pub after: Option<String>,
45    pub origin: Option<String>,
46    /// The cut's observed principal (DR-0052; `None` = pre-actor row).
47    pub actor: Option<String>,
48    /// The motivating work item / incident id, when the operation
49    /// carried one (repair cuts always do; ordinary writes may not).
50    pub intent: Option<String>,
51    pub recorded_at: String,
52    /// Declaration-level sub-rows (DR-0054): the declarations this unit
53    /// changed, when both sides of a `.whip` path had a canonical form.
54    /// Empty = attribution stays path-level for this unit (fail closed,
55    /// never guessed).
56    #[serde(default)]
57    pub decls: Vec<DeclUnit>,
58}
59
60/// One changed declaration within a change-unit (DR-0054 Decision 6.3).
61#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
62pub struct DeclUnit {
63    /// Normalized header line (`rule triage`, `class Report`).
64    pub identity: String,
65    /// Canonical content hash before the cut; `None` = added here.
66    pub before_canon: Option<String>,
67    /// Canonical content hash after the cut; `None` = deleted here.
68    pub after_canon: Option<String>,
69}
70
71#[derive(Clone, Debug, Eq, PartialEq)]
72pub enum SelExpr {
73    Union(Box<SelExpr>, Box<SelExpr>),
74    Intersect(Box<SelExpr>, Box<SelExpr>),
75    Difference(Box<SelExpr>, Box<SelExpr>),
76    Atom(SelAtom),
77}
78
79#[derive(Clone, Debug, Eq, PartialEq)]
80pub enum SelAtom {
81    Path(String),
82    ByEffect(String),
83    ByOrigin(String),
84    /// Actor prefix (DR-0052 A2): `by(s:sess-7)` selects that session's
85    /// units, `by(s:)` every session's, `by(git:)` everything imported.
86    /// Prefix matching over the namespaced principal string is the v1
87    /// chain approximation — tier-precise joins arrive with session
88    /// carriage.
89    ByActor(String),
90    /// Intent prefix: the tracker item / incident that motivated the
91    /// cut. Empty until intent-carrying operations (repair, ingest)
92    /// record it.
93    ByIntent(String),
94    /// Declaration-identity glob (DR-0054): `decl(rule close)` selects
95    /// units that changed that declaration; `decl(rule *)` every unit
96    /// with a changed rule. Only units with declaration sub-rows match.
97    Decl(String),
98    InBranch(String),
99    Change(String),
100    Cut(String),
101    Since(String),
102    Until(String),
103    DependentsOf(Box<SelExpr>),
104}
105
106/// Parse a selection expression. Errors carry the offending position's
107/// remainder — enough for a CLI message.
108pub fn parse(input: &str) -> Result<SelExpr, String> {
109    let mut parser = Parser {
110        rest: input.trim(),
111        depth: 0,
112    };
113    let expr = parser.expr()?;
114    if !parser.rest.is_empty() {
115        return Err(format!("unexpected trailing input: `{}`", parser.rest));
116    }
117    Ok(expr)
118}
119
120/// Recursion-depth ceiling for the selection grammar. Every `(` and
121/// `dependents-of(...)` nesting level descends through `prim`, so bounding it
122/// there returns an ordinary `Err` on a pathologically nested selection
123/// expression (a CLI arg) instead of overflowing the stack. Far above any real
124/// selection.
125const MAX_SELECTION_DEPTH: usize = 256;
126
127struct Parser<'a> {
128    rest: &'a str,
129    depth: usize,
130}
131
132impl<'a> Parser<'a> {
133    fn skip_ws(&mut self) {
134        self.rest = self.rest.trim_start();
135    }
136
137    fn eat(&mut self, token: char) -> bool {
138        self.skip_ws();
139        if let Some(stripped) = self.rest.strip_prefix(token) {
140            self.rest = stripped;
141            true
142        } else {
143            false
144        }
145    }
146
147    fn expr(&mut self) -> Result<SelExpr, String> {
148        let mut left = self.diff()?;
149        while self.eat('|') {
150            let right = self.diff()?;
151            left = SelExpr::Union(Box::new(left), Box::new(right));
152        }
153        Ok(left)
154    }
155
156    fn diff(&mut self) -> Result<SelExpr, String> {
157        let mut left = self.inter()?;
158        while self.eat('~') {
159            let right = self.inter()?;
160            left = SelExpr::Difference(Box::new(left), Box::new(right));
161        }
162        Ok(left)
163    }
164
165    fn inter(&mut self) -> Result<SelExpr, String> {
166        let mut left = self.prim()?;
167        while self.eat('&') {
168            let right = self.prim()?;
169            left = SelExpr::Intersect(Box::new(left), Box::new(right));
170        }
171        Ok(left)
172    }
173
174    fn prim(&mut self) -> Result<SelExpr, String> {
175        self.depth += 1;
176        if self.depth > MAX_SELECTION_DEPTH {
177            self.depth -= 1;
178            return Err(format!(
179                "selection expression is nested too deeply (limit {MAX_SELECTION_DEPTH})"
180            ));
181        }
182        let result = self.prim_inner();
183        self.depth -= 1;
184        result
185    }
186
187    fn prim_inner(&mut self) -> Result<SelExpr, String> {
188        self.skip_ws();
189        if self.eat('(') {
190            let inner = self.expr()?;
191            if !self.eat(')') {
192                return Err(format!("expected `)` at `{}`", self.rest));
193            }
194            return Ok(inner);
195        }
196        let name_len = self
197            .rest
198            .find(|c: char| !(c.is_ascii_alphanumeric() || c == '-' || c == '_'))
199            .unwrap_or(self.rest.len());
200        let name = &self.rest[..name_len];
201        if name.is_empty() {
202            return Err(format!("expected a selection atom at `{}`", self.rest));
203        }
204        self.rest = &self.rest[name_len..];
205        if !self.eat('(') {
206            return Err(format!("expected `(` after `{name}`"));
207        }
208        if name == "dependents-of" {
209            let inner = self.expr()?;
210            if !self.eat(')') {
211                return Err(format!("expected `)` at `{}`", self.rest));
212            }
213            return Ok(SelExpr::Atom(SelAtom::DependentsOf(Box::new(inner))));
214        }
215        // A plain-argument atom: the argument runs to the matching `)`.
216        let close = self
217            .rest
218            .find(')')
219            .ok_or_else(|| format!("unterminated `{name}(`"))?;
220        let arg = self.rest[..close].trim().to_owned();
221        self.rest = &self.rest[close + 1..];
222        let atom = match name {
223            "path" => SelAtom::Path(arg),
224            "by-effect" => SelAtom::ByEffect(arg),
225            "by-origin" => SelAtom::ByOrigin(arg),
226            "by" => SelAtom::ByActor(arg),
227            "intent" => SelAtom::ByIntent(arg),
228            "decl" => SelAtom::Decl(arg),
229            "in-branch" => SelAtom::InBranch(arg),
230            "change" => SelAtom::Change(arg),
231            "cut" => SelAtom::Cut(arg),
232            "since" => SelAtom::Since(arg),
233            "until" => SelAtom::Until(arg),
234            other => return Err(format!("unknown selection atom `{other}`")),
235        };
236        Ok(SelExpr::Atom(atom))
237    }
238}
239
240/// A `*`/`?` glob match (segments are not special: `*` crosses `/`,
241/// matching the whole-path selection intent).
242pub fn glob_matches(pattern: &str, value: &str) -> bool {
243    // Iterative two-pointer glob with single-star backtracking: O(len(pattern)
244    // * len(value)) worst case. The prior recursion was `*`-splits with no
245    // memoization, so a pattern with interleaved stars against a non-matching
246    // value (e.g. `a*a*a*...*Z` vs `aaaa...`) backtracked exponentially and hung
247    // the process on an operator/agent-supplied `path(<glob>)` atom.
248    let pattern = pattern.as_bytes();
249    let value = value.as_bytes();
250    let (mut p, mut v) = (0usize, 0usize);
251    // The last `*` seen and the value position to resume from if the tail fails.
252    let (mut star, mut resume) = (None, 0usize);
253    while v < value.len() {
254        if p < pattern.len() && (pattern[p] == b'?' || pattern[p] == value[v]) {
255            p += 1;
256            v += 1;
257        } else if p < pattern.len() && pattern[p] == b'*' {
258            // Record this star and provisionally match zero characters.
259            star = Some(p);
260            resume = v;
261            p += 1;
262        } else if let Some(star_p) = star {
263            // Mismatch: let the last star absorb one more value byte.
264            p = star_p + 1;
265            resume += 1;
266            v = resume;
267        } else {
268            return false;
269        }
270    }
271    // Trailing pattern must be all stars to match the consumed value.
272    while p < pattern.len() && pattern[p] == b'*' {
273        p += 1;
274    }
275    p == pattern.len()
276}
277
278/// Evaluate an expression over a change-unit universe, returning the
279/// selected indices.
280pub fn eval(expr: &SelExpr, universe: &[ChangeUnit]) -> BTreeSet<usize> {
281    match expr {
282        SelExpr::Union(a, b) => eval(a, universe)
283            .union(&eval(b, universe))
284            .copied()
285            .collect(),
286        SelExpr::Intersect(a, b) => eval(a, universe)
287            .intersection(&eval(b, universe))
288            .copied()
289            .collect(),
290        SelExpr::Difference(a, b) => eval(a, universe)
291            .difference(&eval(b, universe))
292            .copied()
293            .collect(),
294        SelExpr::Atom(atom) => eval_atom(atom, universe),
295    }
296}
297
298fn eval_atom(atom: &SelAtom, universe: &[ChangeUnit]) -> BTreeSet<usize> {
299    let pick = |predicate: &dyn Fn(&ChangeUnit) -> bool| -> BTreeSet<usize> {
300        universe
301            .iter()
302            .enumerate()
303            .filter(|(_, unit)| predicate(unit))
304            .map(|(index, _)| index)
305            .collect()
306    };
307    match atom {
308        SelAtom::Path(glob) => pick(&|unit| glob_matches(glob, &unit.path)),
309        SelAtom::ByEffect(prefix) => pick(&|unit| unit.cut_id.starts_with(prefix.as_str())),
310        SelAtom::ByOrigin(prefix) => pick(&|unit| {
311            unit.origin
312                .as_deref()
313                .is_some_and(|origin| origin.starts_with(prefix.as_str()))
314        }),
315        SelAtom::ByActor(prefix) => pick(&|unit| {
316            unit.actor
317                .as_deref()
318                .is_some_and(|actor| actor.starts_with(prefix.as_str()))
319        }),
320        SelAtom::ByIntent(prefix) => pick(&|unit| {
321            unit.intent
322                .as_deref()
323                .is_some_and(|intent| intent.starts_with(prefix.as_str()))
324        }),
325        SelAtom::Decl(glob) => pick(&|unit| {
326            unit.decls
327                .iter()
328                .any(|decl| glob_matches(glob, &decl.identity))
329        }),
330        SelAtom::InBranch(branch) => pick(&|unit| unit.branch_id == *branch),
331        SelAtom::Change(change) => pick(&|unit| unit.change_id == *change),
332        SelAtom::Cut(cut) => pick(&|unit| unit.cut_id == *cut),
333        SelAtom::Since(stamp) => pick(&|unit| unit.recorded_at.as_str() >= stamp.as_str()),
334        SelAtom::Until(stamp) => pick(&|unit| unit.recorded_at.as_str() <= stamp.as_str()),
335        SelAtom::DependentsOf(inner) => {
336            // The conservative dependence floor: a later unit on the
337            // same path consumed the earlier one's output. Closure over
338            // the universe; includes the seeds.
339            let seeds = eval(inner, universe);
340            let mut selected = seeds.clone();
341            for &seed in &seeds {
342                let seed_unit = &universe[seed];
343                for (index, unit) in universe.iter().enumerate() {
344                    if unit.path == seed_unit.path && unit.seq > seed_unit.seq {
345                        selected.insert(index);
346                    }
347                }
348            }
349            selected
350        }
351    }
352}
353
354/// The stranding check (selective-undo.maude, the slicer's 7th client at
355/// its path-level floor): undoing `selected` strands every RETAINED
356/// later unit whose path input came from an undone write. Returns the
357/// stranded indices — empty means the exclusion's dependency closure is
358/// clean and the proposal is safe.
359pub fn stranded_by_undo(selected: &BTreeSet<usize>, universe: &[ChangeUnit]) -> BTreeSet<usize> {
360    let mut stranded = BTreeSet::new();
361    for &chosen in selected {
362        let undone = &universe[chosen];
363        for (index, unit) in universe.iter().enumerate() {
364            if unit.path == undone.path && unit.seq > undone.seq && !selected.contains(&index) {
365                stranded.insert(index);
366            }
367        }
368    }
369    stranded
370}
371
372#[cfg(test)]
373mod tests {
374    use super::*;
375
376    fn unit(seq: usize, cut: &str, path: &str, at: &str) -> ChangeUnit {
377        ChangeUnit {
378            seq,
379            cut_id: cut.to_owned(),
380            change_id: cut.to_owned(),
381            branch_id: "b1".to_owned(),
382            path: path.to_owned(),
383            before: None,
384            after: Some(format!("h{seq}")),
385            origin: Some(format!("write:{path}")),
386            actor: None,
387            intent: None,
388            recorded_at: at.to_owned(),
389            decls: Vec::new(),
390        }
391    }
392
393    fn unit_by(seq: usize, cut: &str, path: &str, actor: &str, at: &str) -> ChangeUnit {
394        ChangeUnit {
395            actor: Some(actor.to_owned()),
396            ..unit(seq, cut, path, at)
397        }
398    }
399
400    /// DR-0052 A2: `by(<prefix>)` selects over the namespaced principal —
401    /// exact session, whole-namespace sweeps (`by(s:)`, `by(git:)`) — and
402    /// composes with the algebra; pre-actor rows (`None`) never match.
403    /// `intent(<prefix>)` mirrors it over the intent tier.
404    #[test]
405    fn actor_and_intent_atoms_select_and_compose() {
406        let universe = vec![
407            unit_by(0, "c1", "src/a.rs", "s:sess-7", "t1"),
408            unit_by(1, "c2", "src/b.rs", "s:sess-9", "t2"),
409            unit_by(2, "c3", "docs/c.md", "git:alice@example.com", "t3"),
410            unit(3, "c4", "src/a.rs", "t4"), // pre-actor row
411        ];
412        let by_session = eval(&parse("by(s:sess-7)").expect("parse"), &universe);
413        assert_eq!(by_session, BTreeSet::from([0]));
414        let all_sessions = eval(&parse("by(s:)").expect("parse"), &universe);
415        assert_eq!(all_sessions, BTreeSet::from([0, 1]));
416        let imported = eval(&parse("by(git:)").expect("parse"), &universe);
417        assert_eq!(imported, BTreeSet::from([2]));
418        // What others built on session 7's work: dependents minus its own.
419        let downstream = eval(
420            &parse("dependents-of(by(s:sess-7)) ~ by(s:sess-7)").expect("parse"),
421            &universe,
422        );
423        assert_eq!(downstream, BTreeSet::from([3]));
424        // Intent selects nothing until an operation records one, then
425        // prefix-matches.
426        assert!(eval(&parse("intent(inc-)").expect("parse"), &universe).is_empty());
427        let mut with_intent = universe.clone();
428        with_intent[1].intent = Some("inc-42".to_owned());
429        assert_eq!(
430            eval(&parse("intent(inc-)").expect("parse"), &with_intent),
431            BTreeSet::from([1])
432        );
433    }
434
435    /// DR-0054: `decl(<glob>)` selects units by changed-declaration
436    /// identity; units without sub-rows (no canonical form) never match —
437    /// fail closed, composing with the algebra like every atom.
438    #[test]
439    fn decl_atom_selects_by_declaration_identity() {
440        let mut universe = vec![
441            unit(0, "c1", "flows/main.whip", "t1"),
442            unit(1, "c2", "flows/main.whip", "t2"),
443            unit(2, "c3", "notes/readme.md", "t3"),
444        ];
445        universe[0].decls = vec![DeclUnit {
446            identity: "rule triage".to_owned(),
447            before_canon: None,
448            after_canon: Some("k1".to_owned()),
449        }];
450        universe[1].decls = vec![
451            DeclUnit {
452                identity: "rule close".to_owned(),
453                before_canon: Some("k2".to_owned()),
454                after_canon: Some("k3".to_owned()),
455            },
456            DeclUnit {
457                identity: "class Report".to_owned(),
458                before_canon: Some("k4".to_owned()),
459                after_canon: None,
460            },
461        ];
462        assert_eq!(
463            eval(&parse("decl(rule close)").expect("parse"), &universe),
464            BTreeSet::from([1])
465        );
466        assert_eq!(
467            eval(&parse("decl(rule *)").expect("parse"), &universe),
468            BTreeSet::from([0, 1])
469        );
470        assert_eq!(
471            eval(
472                &parse("decl(rule *) ~ decl(class *)").expect("parse"),
473                &universe
474            ),
475            BTreeSet::from([0])
476        );
477        assert!(eval(&parse("decl(gauge *)").expect("parse"), &universe).is_empty());
478    }
479
480    #[test]
481    fn grammar_parses_composition_with_precedence() {
482        let expr = parse("path(src/*.md) & since(t3) | by-effect(eff_) ~ cut(c9)").expect("parse");
483        // `|` binds loosest: (path & since) | (by-effect ~ cut).
484        let SelExpr::Union(left, right) = expr else {
485            panic!("expected a union at the top");
486        };
487        assert!(matches!(*left, SelExpr::Intersect(..)));
488        assert!(matches!(*right, SelExpr::Difference(..)));
489        assert!(parse("path(unclosed").is_err());
490        assert!(parse("nonsense(x)").is_err());
491        assert!(parse("path(a) extra").is_err());
492    }
493
494    #[test]
495    fn deeply_nested_selection_errors_instead_of_overflowing_the_stack() {
496        // A pathologically nested selection expression (a CLI arg) must return
497        // a normal Err, not abort the process. Run on a production-sized stack.
498        std::thread::Builder::new()
499            .stack_size(8 * 1024 * 1024)
500            .spawn(|| {
501                let deep = format!("{}path(a){}", "(".repeat(4000), ")".repeat(4000));
502                let result = parse(&deep);
503                assert!(
504                    result
505                        .as_ref()
506                        .err()
507                        .is_some_and(|message| message.contains("nested too deeply")),
508                    "expected a depth-limit diagnostic, got {result:?}"
509                );
510                let ok = format!("{}path(a){}", "(".repeat(64), ")".repeat(64));
511                assert!(parse(&ok).is_ok(), "64-deep nesting must parse");
512            })
513            .expect("spawn")
514            .join()
515            .expect("nested-selection parse must not crash");
516    }
517
518    #[test]
519    fn atoms_select_by_provenance_dimensions() {
520        let universe = vec![
521            unit(0, "eff_1-f0", "src/a.md", "t1"),
522            unit(1, "eff_2-f0", "src/b.md", "t2"),
523            unit(2, "cut_x", "notes/c.txt", "t3"),
524        ];
525        let by_path = eval(&parse("path(src/*.md)").expect("parse"), &universe);
526        assert_eq!(by_path, BTreeSet::from([0, 1]));
527        let by_effect = eval(&parse("by-effect(eff_2)").expect("parse"), &universe);
528        assert_eq!(by_effect, BTreeSet::from([1]));
529        let since = eval(&parse("since(t2)").expect("parse"), &universe);
530        assert_eq!(since, BTreeSet::from([1, 2]));
531        let composed = eval(
532            &parse("path(src/*.md) ~ by-effect(eff_2)").expect("parse"),
533            &universe,
534        );
535        assert_eq!(composed, BTreeSet::from([0]));
536        let grouped = eval(
537            &parse("(path(src/*.md) | path(notes/*)) & until(t2)").expect("parse"),
538            &universe,
539        );
540        assert_eq!(grouped, BTreeSet::from([0, 1]));
541    }
542
543    /// The model's fixture, verbatim: e1 wrote p1; e2, e3 wrote p2.
544    /// Undoing p1 strands e3's path-level input? No — path-level
545    /// dependence binds within a path: undoing e2 strands e3 (later on
546    /// p2, retained); undoing p2 entirely (e2 AND e3) strands nothing;
547    /// dependents-of(e2) pulls e3 into the selection.
548    #[test]
549    fn stranding_and_dependents_mirror_the_model() {
550        let universe = vec![
551            unit(0, "e1", "p1", "t1"),
552            unit(1, "e2", "p2", "t2"),
553            unit(2, "e3", "p2", "t3"),
554        ];
555        // Undo e2 alone: e3 is retained and read e2's output — stranded.
556        let sel = eval(&parse("cut(e2)").expect("parse"), &universe);
557        assert_eq!(stranded_by_undo(&sel, &universe), BTreeSet::from([2]));
558        // Undo the whole path: the reader is inside the selection.
559        let sel = eval(&parse("path(p2)").expect("parse"), &universe);
560        assert!(stranded_by_undo(&sel, &universe).is_empty());
561        // The closure operator repairs the stranding selection.
562        let sel = eval(&parse("dependents-of(cut(e2))").expect("parse"), &universe);
563        assert_eq!(sel, BTreeSet::from([1, 2]));
564        assert!(stranded_by_undo(&sel, &universe).is_empty());
565        // Undoing e1 strands nothing: nothing later touched p1.
566        let sel = eval(&parse("cut(e1)").expect("parse"), &universe);
567        assert!(stranded_by_undo(&sel, &universe).is_empty());
568    }
569
570    #[test]
571    fn glob_semantics() {
572        assert!(glob_matches("src/*.md", "src/deep/a.md"));
573        assert!(glob_matches("*", "anything"));
574        assert!(glob_matches("a?c", "abc"));
575        assert!(!glob_matches("a?c", "ac"));
576        assert!(!glob_matches("src/*.md", "src/a.txt"));
577        // Multi-star and edge forms the two-pointer matcher must still get right.
578        assert!(glob_matches("a*b*c", "axxbyyc"));
579        assert!(glob_matches("**", "anything"));
580        assert!(glob_matches("*.md", ".md"));
581        assert!(glob_matches("", ""));
582        assert!(!glob_matches("", "x"));
583        assert!(!glob_matches("a*b", "axxbx")); // trailing literal must anchor
584        assert!(glob_matches("a*b", "ab"));
585    }
586
587    #[test]
588    fn glob_worst_case_is_linear_not_exponential() {
589        // The classic exponential-backtracking trigger: many stars interleaved
590        // with a literal that never appears in a long value. The linear matcher
591        // returns promptly; the old recursion hung for effectively forever.
592        let pattern = "a*".repeat(30) + "Z";
593        let value = "a".repeat(60);
594        assert!(!glob_matches(&pattern, &value));
595    }
596}
whipplescript_core/selection.rs

whipplescript_core/
selection.rs
