Skip to main content

qualia_core_db/modalities/
temporal_ltl.rs

1use crate::NQuin;
2
3pub const OP_LTL_GLOBALLY: u8 = 0x40;
4pub const OP_LTL_FINALLY: u8 = 0x41;
5pub const OP_LTL_NEXT: u8 = 0x42;
6pub const OP_LTL_UNTIL: u8 = 0x43;
7pub const OP_LTL_RELEASE: u8 = 0x44;
8
9#[repr(C)]
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11pub enum LtlFormula {
12    Globally(u64),
13    Finally(u64),
14    Next(u64),
15    Until { ante: u64, consequent: u64 },
16    Release { trigger: u64, invariant: u64 },
17}
18
19#[derive(Debug)]
20pub enum TemporalError {
21    AbortedTimeout,
22}
23
24/// Timeout guard for a lock lease: `Err(AbortedTimeout)` when
25/// `current_time` is past `lock_granted_at + ttl_seconds`, else `Ok`.
26/// The lease boundary itself (`==`) is still valid.
27pub fn evaluate_lock_lease(
28    lock_granted_at: u64,
29    current_time: u64,
30    ttl_seconds: u64,
31) -> Result<(), TemporalError> {
32    if current_time > lock_granted_at + ttl_seconds {
33        return Err(TemporalError::AbortedTimeout);
34    }
35    Ok(())
36}
37
38/// Evaluate an `LtlFormula` over a finite quin trace — the
39/// predicate-hash is the proposition at each state. Empty traces
40/// satisfy nothing. `Until`/`Release` scan for the earliest index where
41/// the consequent holds with the antecedent/invariant holding
42/// throughout the prefix.
43pub fn evaluate_ltl_trace(trace: &[NQuin], formula: &LtlFormula) -> bool {
44    match formula {
45        LtlFormula::Globally(p) => {
46            if trace.is_empty() {
47                return false;
48            }
49            for quin in trace {
50                if quin.predicate != *p {
51                    return false;
52                }
53            }
54            true
55        }
56        LtlFormula::Finally(p) => {
57            if trace.is_empty() {
58                return false;
59            }
60            for quin in trace {
61                if quin.predicate == *p {
62                    return true;
63                }
64            }
65            false
66        }
67        LtlFormula::Next(p) => {
68            if trace.len() < 2 {
69                return false;
70            }
71            trace[1].predicate == *p
72        }
73        LtlFormula::Until { ante, consequent } => {
74            if trace.is_empty() {
75                return false;
76            }
77            for (i, quin) in trace.iter().enumerate() {
78                if quin.predicate == *consequent {
79                    let mut ante_held = true;
80                    for j in 0..i {
81                        if trace[j].predicate != *ante {
82                            ante_held = false;
83                            break;
84                        }
85                    }
86                    if ante_held {
87                        return true;
88                    }
89                }
90            }
91            false
92        }
93        LtlFormula::Release { trigger, invariant } => {
94            if trace.is_empty() {
95                return true;
96            }
97            for (i, quin) in trace.iter().enumerate() {
98                if quin.predicate != *invariant {
99                    let mut triggered = false;
100                    for j in 0..=i {
101                        if trace[j].predicate == *trigger {
102                            triggered = true;
103                            break;
104                        }
105                    }
106                    if !triggered {
107                        return false;
108                    }
109                }
110            }
111            true
112        }
113    }
114}
115
116/// Metric temporal (MTL) "within": after the EARLIEST occurrence of `trigger`
117/// (each event quin carries its timestamp in `metadata`), `target` must occur at
118/// some time `t1` with `t0 <= t1 <= t0 + window`. Models deadlines — e.g. "remedy
119/// within 30 days of breach". Zero-heap (two linear scans; no allocation).
120pub fn holds_within(trace: &[NQuin], trigger: u64, target: u64, window: u64) -> bool {
121    // t0 = earliest timestamp at which the trigger holds.
122    let mut t0: Option<u64> = None;
123    for q in trace {
124        if q.predicate == trigger {
125            t0 = Some(match t0 {
126                Some(prev) => prev.min(q.metadata),
127                None => q.metadata,
128            });
129        }
130    }
131    let t0 = match t0 {
132        Some(t) => t,
133        None => return false, // trigger never occurred
134    };
135    let deadline = t0.saturating_add(window);
136    for q in trace {
137        if q.predicate == target && q.metadata >= t0 && q.metadata <= deadline {
138            return true;
139        }
140    }
141    false
142}
143
144/// MTL **bounded-globally** `G[t0, t0+window] inv`: from the earliest `trigger` timestamp `t0`,
145/// the `invariant` must hold at *every* event whose timestamp lies in `[t0, t0+window]`. Returns
146/// `true` vacuously if no in-window events. Zero-heap.
147pub fn holds_globally_within(trace: &[NQuin], trigger: u64, invariant: u64, window: u64) -> bool {
148    let mut t0: Option<u64> = None;
149    for q in trace {
150        if q.predicate == trigger {
151            t0 = Some(t0.map_or(q.metadata, |p| p.min(q.metadata)));
152        }
153    }
154    let t0 = match t0 {
155        Some(t) => t,
156        None => return false,
157    };
158    let deadline = t0.saturating_add(window);
159    // Every event in the window must satisfy the invariant.
160    for q in trace {
161        if q.metadata >= t0
162            && q.metadata <= deadline
163            && q.predicate != invariant
164            && q.predicate != trigger
165        {
166            return false;
167        }
168    }
169    true
170}
171
172// ─── Past-time LTL (Once, Historically, Since) ────────────────────────────────────
173
174/// **Once** `O p` (past ◇): `p` held at some point in the trace (the past-time dual of `Finally`).
175pub fn evaluate_once(trace: &[NQuin], p: u64) -> bool {
176    trace.iter().any(|q| q.predicate == p)
177}
178
179/// **Historically** `H p` (past □): `p` held at *every* point in the trace (dual of `Globally`).
180/// Vacuously true on an empty trace (nothing in the past violated it).
181pub fn evaluate_historically(trace: &[NQuin], p: u64) -> bool {
182    trace.iter().all(|q| q.predicate == p)
183}
184
185/// **Since** `p S q`: at the end of the trace, `q` held at some past point and `p` has held at
186/// every point since (inclusive of after `q`). Retrospective legal analysis ("the duty has held
187/// since the breach"). Zero-heap.
188pub fn evaluate_since(trace: &[NQuin], p: u64, q: u64) -> bool {
189    // Find the latest index where q held; require p at every index after it.
190    let mut q_at: Option<usize> = None;
191    for (i, ev) in trace.iter().enumerate() {
192        if ev.predicate == q {
193            q_at = Some(i);
194        }
195    }
196    match q_at {
197        None => false,
198        Some(qi) => trace[qi + 1..].iter().all(|ev| ev.predicate == p),
199    }
200}
201
202// ─── Büchi-style streaming monitor (continuous safety monitoring) ─────────────────
203
204/// An incremental monitor for the safety fragment `G(p)` ("`p` always holds") — the practical
205/// Büchi-automaton acceptance for stream monitoring: it stays `Safe` while every streamed event
206/// satisfies `p`, and latches to `Violated` permanently on the first event that does not. Zero-heap.
207#[derive(Debug, Clone, Copy, PartialEq, Eq)]
208pub struct SafetyMonitor {
209    pub invariant: u64,
210    pub violated: bool,
211}
212
213impl SafetyMonitor {
214    /// Start monitoring `G(invariant)`.
215    pub fn new(invariant: u64) -> Self {
216        Self {
217            invariant,
218            violated: false,
219        }
220    }
221    /// Feed the next streamed event predicate; returns `true` while still safe.
222    pub fn step(&mut self, event_predicate: u64) -> bool {
223        if event_predicate != self.invariant {
224            self.violated = true;
225        }
226        !self.violated
227    }
228    /// Is the monitored safety property still holding?
229    #[inline]
230    pub fn is_safe(&self) -> bool {
231        !self.violated
232    }
233}
234
235// ─── Allen-interval bridge ────────────────────────────────────────────────────────
236
237/// Extract the `[first, last]` timestamp interval over which `predicate` occurs in the timed
238/// `trace` (each event's timestamp in `metadata`), or `None` if it never occurs. The bridge to
239/// the Allen Interval Algebra (`interval_reasoning::allen_relation` relates two such intervals).
240pub fn predicate_interval(trace: &[NQuin], predicate: u64) -> Option<(u64, u64)> {
241    let mut lo: Option<u64> = None;
242    let mut hi: Option<u64> = None;
243    for q in trace {
244        if q.predicate == predicate {
245            lo = Some(lo.map_or(q.metadata, |v| v.min(q.metadata)));
246            hi = Some(hi.map_or(q.metadata, |v| v.max(q.metadata)));
247        }
248    }
249    Some((lo?, hi?))
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255    use crate::NQuin;
256
257    fn timed(predicate: u64, t: u64) -> NQuin {
258        NQuin {
259            subject: 0,
260            predicate,
261            object: 0,
262            context: 0,
263            metadata: t,
264            parity: 0,
265        }
266    }
267
268    #[test]
269    fn test_mtl_holds_within() {
270        let breach = 1u64;
271        let remedy = 2u64;
272        // breach at t=10, remedy at t=25 → within window 30.
273        let trace = [timed(breach, 10), timed(remedy, 25)];
274        assert!(
275            holds_within(&trace, breach, remedy, 30),
276            "remedy 15 after breach ≤ 30 window"
277        );
278        assert!(
279            !holds_within(&trace, breach, remedy, 10),
280            "remedy 15 after breach > 10 window"
281        );
282        // remedy before the breach does not count.
283        let late = [timed(remedy, 5), timed(breach, 10)];
284        assert!(
285            !holds_within(&late, breach, remedy, 30),
286            "a remedy before the breach is not within"
287        );
288        // no trigger → false.
289        assert!(!holds_within(&[timed(remedy, 25)], breach, remedy, 30));
290    }
291
292    fn make_quin(predicate: u64) -> NQuin {
293        NQuin {
294            subject: 0,
295            predicate,
296            object: 0,
297            context: 0,
298            metadata: 0,
299            parity: 0,
300        }
301    }
302
303    #[test]
304    fn test_ltl_globally() {
305        let p = 100;
306        let q_p = make_quin(p);
307        let q_not_p = make_quin(99);
308
309        assert!(evaluate_ltl_trace(
310            &[q_p, q_p, q_p],
311            &LtlFormula::Globally(p)
312        ));
313        assert!(!evaluate_ltl_trace(
314            &[q_p, q_not_p, q_p],
315            &LtlFormula::Globally(p)
316        ));
317        assert!(!evaluate_ltl_trace(&[], &LtlFormula::Globally(p)));
318    }
319
320    #[test]
321    fn test_ltl_finally() {
322        let p = 100;
323        let q_p = make_quin(p);
324        let q_not_p = make_quin(99);
325
326        assert!(evaluate_ltl_trace(
327            &[q_not_p, q_not_p, q_p],
328            &LtlFormula::Finally(p)
329        ));
330        assert!(!evaluate_ltl_trace(
331            &[q_not_p, q_not_p],
332            &LtlFormula::Finally(p)
333        ));
334        assert!(!evaluate_ltl_trace(&[], &LtlFormula::Finally(p)));
335    }
336
337    #[test]
338    fn test_ltl_next() {
339        let p = 100;
340        let q_p = make_quin(p);
341        let q_not_p = make_quin(99);
342
343        assert!(evaluate_ltl_trace(&[q_not_p, q_p], &LtlFormula::Next(p)));
344        assert!(!evaluate_ltl_trace(&[q_p, q_not_p], &LtlFormula::Next(p)));
345        assert!(!evaluate_ltl_trace(&[q_p], &LtlFormula::Next(p)));
346        assert!(!evaluate_ltl_trace(&[], &LtlFormula::Next(p)));
347    }
348
349    #[test]
350    fn test_ltl_until() {
351        let p = 100;
352        let q = 200;
353        let q_p = make_quin(p);
354        let q_q = make_quin(q);
355        let q_other = make_quin(99);
356
357        assert!(evaluate_ltl_trace(
358            &[q_p, q_p, q_q],
359            &LtlFormula::Until {
360                ante: p,
361                consequent: q
362            }
363        ));
364        assert!(evaluate_ltl_trace(
365            &[q_q],
366            &LtlFormula::Until {
367                ante: p,
368                consequent: q
369            }
370        ));
371        assert!(!evaluate_ltl_trace(
372            &[q_p, q_p, q_p],
373            &LtlFormula::Until {
374                ante: p,
375                consequent: q
376            }
377        ));
378        assert!(!evaluate_ltl_trace(
379            &[q_p, q_other, q_q],
380            &LtlFormula::Until {
381                ante: p,
382                consequent: q
383            }
384        ));
385        assert!(!evaluate_ltl_trace(
386            &[],
387            &LtlFormula::Until {
388                ante: p,
389                consequent: q
390            }
391        ));
392    }
393
394    #[test]
395    fn test_ltl_release() {
396        let trigger = 100;
397        let invariant = 200;
398        let q_t = make_quin(trigger);
399        let q_i = make_quin(invariant);
400        let q_other = make_quin(99);
401
402        assert!(evaluate_ltl_trace(
403            &[q_i, q_i, q_i],
404            &LtlFormula::Release { trigger, invariant }
405        ));
406        assert!(evaluate_ltl_trace(
407            &[q_i, q_t, q_other],
408            &LtlFormula::Release { trigger, invariant }
409        ));
410        assert!(!evaluate_ltl_trace(
411            &[q_i, q_other, q_t],
412            &LtlFormula::Release { trigger, invariant }
413        ));
414        assert!(evaluate_ltl_trace(
415            &[],
416            &LtlFormula::Release { trigger, invariant }
417        ));
418    }
419
420    #[test]
421    fn past_time_ltl_once_historically_since() {
422        let (breach, duty, repaired) = (1u64, 2u64, 3u64);
423        let trace = [make_quin(breach), make_quin(duty), make_quin(duty)];
424        // Once: breach happened at some past point.
425        assert!(evaluate_once(&trace, breach));
426        assert!(!evaluate_once(&trace, repaired));
427        // Historically: duty did NOT hold at every point (breach was first).
428        assert!(!evaluate_historically(&trace, duty));
429        assert!(evaluate_historically(
430            &[make_quin(duty), make_quin(duty)],
431            duty
432        ));
433        // Since: the duty has held since the breach (every point after breach is duty).
434        assert!(evaluate_since(&trace, duty, breach));
435        // Not "since" if the consequent never held.
436        assert!(!evaluate_since(&trace, duty, repaired));
437    }
438
439    #[test]
440    fn streaming_safety_monitor_latches_on_violation() {
441        let safe = 100u64;
442        let mut mon = SafetyMonitor::new(safe);
443        assert!(mon.step(safe) && mon.step(safe), "still safe");
444        assert!(!mon.step(999), "a non-conforming event violates G(p)");
445        assert!(!mon.step(safe), "violation latches permanently");
446        assert!(!mon.is_safe());
447    }
448
449    #[test]
450    fn metric_globally_and_allen_interval() {
451        let (start, ok, bad) = (1u64, 2u64, 3u64);
452        // From trigger@10, invariant `ok` holds across the window [10,40].
453        let good = [timed(start, 10), timed(ok, 20), timed(ok, 35)];
454        assert!(holds_globally_within(&good, start, ok, 30));
455        // A bad event inside the window breaks it.
456        let broken = [timed(start, 10), timed(bad, 25)];
457        assert!(!holds_globally_within(&broken, start, ok, 30));
458        // Allen-interval extraction: `ok` spans [20,35].
459        assert_eq!(predicate_interval(&good, ok), Some((20, 35)));
460        assert_eq!(predicate_interval(&good, bad), None);
461    }
462}