Skip to main content

dive_eval/
tuple_names.rs

1//! Constructor-grounded result facts, separate from expression effects.
2
3use std::collections::HashSet;
4use std::sync::{Arc, Weak};
5
6use dive_ir::{Arg, DefId, Expr, ExprId, OpRef, StdKind, StdOp, StdSupport};
7use dive_value::{Fcn, Set, SetKind, Value};
8
9use crate::core::Core;
10use crate::env::{Env, Ev, Frame, OpVal, StateRef, SubstLink, Sv, Thunk};
11use crate::{ConstBinding, EvalError, Evaluator, HostControl, Result, Scope};
12
13mod scalar_callbacks;
14#[cfg(test)]
15mod tests;
16
17/// A checked own-call fact for the supplied source roots of one evaluator.
18///
19/// Every reachable concatenation in these roots has a tuple operand. This
20/// says nothing about other native name creators, effects, model truth or
21/// roots the caller omitted. There is no public constructor; a model driver
22/// must supply its complete checking path before removing a sequential reason.
23#[derive(Clone)]
24pub struct TupleConcatSources {
25    owner: Weak<Core>,
26}
27
28impl std::fmt::Debug for TupleConcatSources {
29    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
30        f.debug_struct("TupleConcatSources").finish_non_exhaustive()
31    }
32}
33
34impl TupleConcatSources {
35    /// Whether the inspected roots belong to this actual evaluator.
36    #[must_use]
37    pub fn belongs_to(&self, evaluator: &Evaluator) -> bool {
38        self.owner.ptr_eq(&Arc::downgrade(&evaluator.core))
39    }
40}
41
42fn reserve<T>(values: &mut Vec<T>, count: usize) -> Result<()> {
43    values
44        .try_reserve(count)
45        .map_err(|_| EvalError::resource_limit("tuple name analysis allocation"))
46}
47
48fn push<T>(values: &mut Vec<T>, value: T) -> Result<()> {
49    reserve(values, 1)?;
50    values.push(value);
51    Ok(())
52}
53
54impl Evaluator {
55    /// Inspects complete source roots for constructor-grounded tuple concatenation.
56    ///
57    /// Literal tuples and the unchanged native `Append` ground a finite monotone
58    /// result analysis. All actuals remain unknown; recursion is never assumed
59    /// tuple-valued. Every child is still inspected for its own calls. Opaque
60    /// captures, native roots and unknown higher-order calls decline without forcing a
61    /// value, calling a provider, or changing permissions or evaluation.
62    ///
63    /// `definitions` are bare configuration/assumption roots, not merely native
64    /// definitions seen as fully applied callees. This fact covers only the
65    /// supplied roots; it does not grant model-wide name or parallel authority.
66    /// The walk has no count or depth ceiling and polls the supplied control,
67    /// or the installed evaluator control when it is absent.
68    ///
69    /// ```no_run
70    /// # fn inspect(ev: &dive_eval::Evaluator, root: (dive_ir::ExprId, dive_eval::Scope))
71    /// # -> dive_eval::Result<()> {
72    /// let fact = ev.tuple_concat_sources(&[root], &[], None)?;
73    /// # let _ = fact; Ok(()) }
74    /// ```
75    ///
76    /// # Errors
77    /// Actual control interruption or a failed analysis allocation.
78    pub fn tuple_concat_sources(
79        &self,
80        roots: &[(ExprId, Scope)],
81        definitions: &[DefId],
82        control: Option<&dyn HostControl>,
83    ) -> Result<Option<TupleConcatSources>> {
84        let mut analysis = Analysis {
85            ev: self,
86            control,
87            blocked: Vec::new(),
88        };
89        analysis.poll()?;
90        // A direct standard reference has lost any configured-constant origin.
91        // Keep these origins unknown, including a same-target override.
92        for binding in self.core.consts.iter().flatten() {
93            analysis.poll()?;
94            if let ConstBinding::Def(def) = binding
95                && let Some(op) = self.core.ir.def(self.redirected(*def)).std
96            {
97                push(&mut analysis.blocked, op)?;
98            }
99        }
100        for (index, def) in self.core.ir.defs().iter().enumerate() {
101            analysis.poll()?;
102            let id = DefId(
103                u32::try_from(index)
104                    .map_err(|_| EvalError::resource_limit("tuple name definition index"))?,
105            );
106            if let Some(op) = def.std
107                && (self.redirected(id) != id || self.is_value_override(id))
108            {
109                push(&mut analysis.blocked, op)?;
110            }
111        }
112        let Some(mut sources) = analysis.captures(roots)? else {
113            return Ok(None);
114        };
115        for &def in definitions {
116            analysis.poll()?;
117            let Some(body) = analysis.user_body(def, 0) else {
118                return Ok(None);
119            };
120            push(&mut sources.exprs, body)?;
121        }
122        let Some(callbacks) = analysis.closed_scalar_callbacks(&sources)? else {
123            return Ok(None);
124        };
125        let tuples = analysis.results()?;
126        if !analysis.calls(&sources.exprs, &tuples, callbacks)? {
127            return Ok(None);
128        }
129        analysis.poll()?;
130        Ok(Some(TupleConcatSources {
131            owner: Arc::downgrade(&self.core),
132        }))
133    }
134}
135
136struct Analysis<'a> {
137    ev: &'a Evaluator,
138    control: Option<&'a dyn HostControl>,
139    blocked: Vec<StdOp>,
140}
141
142impl Analysis<'_> {
143    fn poll(&self) -> Result<()> {
144        if let Some(control) = self.control {
145            control.check().map_err(EvalError::interrupted)
146        } else {
147            self.ev.core.host.check_control()
148        }
149    }
150
151    fn native(&self, op: &OpRef, arity: usize) -> Option<StdOp> {
152        let op = match op {
153            OpRef::Std(op) => *op,
154            OpRef::Def(def) => {
155                let target = self.ev.ir().defs().get(def.index())?;
156                if self.ev.redirected(*def) != *def
157                    || self.ev.is_value_override(*def)
158                    || target.params.len() != arity
159                    || target.params.iter().any(|p| p.arity != 0)
160                {
161                    return None;
162                }
163                target.std?
164            }
165            _ => return None,
166        };
167        (op.kind() == StdKind::Value
168            && op.support() == StdSupport::Core
169            && usize::try_from(op.java_arity()).ok() == Some(arity)
170            && !self.blocked.contains(&op)
171            && !self.ev.core.std_redirects.contains_key(&op))
172        .then_some(op)
173    }
174
175    fn user_body(&self, def: DefId, arity: usize) -> Option<ExprId> {
176        let target = self.ev.ir().defs().get(def.index())?;
177        (target.std.is_none()
178            && self.ev.redirected(def) == def
179            && !self.ev.is_value_override(def)
180            && target.params.len() == arity
181            && target.params.iter().all(|p| p.arity == 0))
182        .then_some(target.body)
183    }
184
185    // Result dependencies exclude children whose values do not determine the
186    // outer result kind. The independent call walk below still visits them.
187    fn result_edges(&self, expr: &Expr, edges: &mut Vec<ExprId>) -> Result<()> {
188        match expr {
189            Expr::If { then, other, .. } => {
190                push(edges, *then)?;
191                push(edges, *other)?;
192            }
193            Expr::Case { arms, other } => {
194                for arm in arms {
195                    push(edges, arm.value)?;
196                }
197                if let Some(other) = other {
198                    push(edges, *other)?;
199                }
200            }
201            Expr::Label { body, .. }
202            | Expr::Selected(body)
203            | Expr::Let { body, .. }
204            | Expr::Subst { body, .. } => push(edges, *body)?,
205            Expr::Def(def) => {
206                if let Some(body) = self.user_body(*def, 0) {
207                    push(edges, body)?;
208                }
209            }
210            Expr::Apply { callee, args } if args.iter().all(|a| matches!(a, Arg::Expr { .. })) => {
211                match self.native(callee, args.len()) {
212                    Some(StdOp::SequencesConcat) => {
213                        for arg in args {
214                            if let Arg::Expr { expr, .. } = arg {
215                                push(edges, *expr)?;
216                            }
217                        }
218                    }
219                    Some(_) => {}
220                    None => {
221                        if let OpRef::Def(def) = callee
222                            && let Some(body) = self.user_body(*def, args.len())
223                        {
224                            push(edges, body)?;
225                        }
226                    }
227                }
228            }
229            _ => {}
230        }
231        Ok(())
232    }
233
234    fn results(&self) -> Result<Vec<bool>> {
235        let count = self.ev.ir().nodes().len();
236        let mut users = Vec::new();
237        reserve(&mut users, count)?;
238        users.resize_with(count, Vec::new);
239        let mut tuples = Vec::new();
240        reserve(&mut tuples, count)?;
241        tuples.resize(count, false);
242        let mut work = Vec::new();
243        for (index, node) in self.ev.ir().nodes().iter().enumerate() {
244            self.poll()?;
245            let id = ExprId(
246                u32::try_from(index)
247                    .map_err(|_| EvalError::resource_limit("tuple name expression index"))?,
248            );
249            let mut edges = Vec::new();
250            self.result_edges(&node.expr, &mut edges)?;
251            for edge in edges {
252                let Some(dependents) = users.get_mut(edge.index()) else {
253                    return Err(EvalError::bug("tuple name result dependency"));
254                };
255                push(dependents, id)?;
256            }
257            push(&mut work, id)?;
258        }
259        while let Some(id) = work.pop() {
260            self.poll()?;
261            if tuples[id.index()] {
262                continue;
263            }
264            let expr = self.ev.ir().expr(id);
265            let mut edges = Vec::new();
266            self.result_edges(expr, &mut edges)?;
267            let grounded = matches!(expr, Expr::Tuple(_))
268                || matches!(expr, Expr::Apply { callee, args }
269                    if args.iter().all(|a| matches!(a, Arg::Expr { .. }))
270                    && self.native(callee, args.len()) == Some(StdOp::SequencesAppend));
271            let proved = if matches!(expr, Expr::Apply { callee, args }
272                if self.native(callee, args.len()) == Some(StdOp::SequencesConcat))
273            {
274                edges.iter().any(|e| tuples[e.index()])
275            } else {
276                !edges.is_empty() && edges.iter().all(|e| tuples[e.index()])
277            };
278            if grounded || proved {
279                tuples[id.index()] = true;
280                for &user in &users[id.index()] {
281                    push(&mut work, user)?;
282                }
283            }
284        }
285        Ok(tuples)
286    }
287
288    fn calls(&self, sources: &[ExprId], tuples: &[bool], callbacks: bool) -> Result<bool> {
289        let mut contexts = Vec::new();
290        push(&mut contexts, Lexical::default())?;
291        let mut seen = HashSet::new();
292        let mut work = Vec::new();
293        for &source in sources {
294            push(&mut work, (source, 0))?;
295        }
296        while let Some((id, context)) = work.pop() {
297            self.poll()?;
298            if seen.contains(&(id, context)) {
299                continue;
300            }
301            seen.try_reserve(1)
302                .map_err(|_| EvalError::resource_limit("tuple name call contexts allocation"))?;
303            seen.insert((id, context));
304            let Some(node) = self.ev.ir().nodes().get(id.index()) else {
305                return Ok(false);
306            };
307            match &node.expr {
308                Expr::Apply { callee, args } => {
309                    if !self.call(
310                        callee,
311                        args,
312                        tuples,
313                        &contexts[context],
314                        &mut work,
315                        callbacks,
316                    )? {
317                        return Ok(false);
318                    }
319                }
320                Expr::Def(def) if self.stored_value_leaf(*def) => {
321                    // eval_def_use returns this already inspected stored value.
322                    // Its overridden body is not evaluated and grants no tuple fact.
323                }
324                Expr::Def(def) => {
325                    if let Some(op) = self.native(&OpRef::Def(*def), 0) {
326                        if op.creates_runtime_names() {
327                            return Ok(false);
328                        }
329                    } else if let Some(body) = self.user_body(*def, 0) {
330                        push(&mut work, (body, 0))?;
331                    } else {
332                        return Ok(false);
333                    }
334                }
335                Expr::Let { defs, body } => {
336                    let context = self.enter_let(defs, &contexts[context], tuples)?;
337                    let next = if let Some(index) = contexts.iter().position(|old| *old == context)
338                    {
339                        index
340                    } else {
341                        let index = contexts.len();
342                        push(&mut contexts, context)?;
343                        index
344                    };
345                    push(&mut work, (*body, next))?;
346                    for def in defs {
347                        push(&mut work, (self.ev.ir().def(*def).body, 0))?;
348                    }
349                    continue;
350                }
351                _ => {}
352            }
353            // These constructs can rebind slots, retain a closure or replace
354            // dynamic context. Never carry a dominated LET fact through them.
355            let context = if matches!(
356                node.expr,
357                Expr::Quant { .. }
358                    | Expr::SetFilter { .. }
359                    | Expr::SetMap { .. }
360                    | Expr::FcnCons { .. }
361                    | Expr::RecFcn { .. }
362                    | Expr::TemporalQuant { .. }
363                    | Expr::Subst { .. }
364                    | Expr::Except { .. }
365                    | Expr::Prime(_)
366                    | Expr::Enabled(_)
367            ) {
368                0
369            } else {
370                context
371            };
372            node.expr
373                .try_for_each_child(|child| push(&mut work, (child, context)))?;
374        }
375        Ok(true)
376    }
377
378    fn stored_value_leaf(&self, def: DefId) -> bool {
379        let Some(target) = self.ev.ir().defs().get(def.index()) else {
380            return false;
381        };
382        target.params.is_empty()
383            && target.std.is_none()
384            && self.ev.redirected(def) == def
385            && self.ev.core.def_values.contains_key(&def)
386    }
387
388    fn call(
389        &self,
390        callee: &OpRef,
391        args: &[Arg],
392        tuples: &[bool],
393        context: &Lexical,
394        work: &mut Vec<(ExprId, usize)>,
395        callbacks: bool,
396    ) -> Result<bool> {
397        if !callbacks && args.iter().any(|a| matches!(a, Arg::Op { .. })) {
398            return Ok(false);
399        }
400        if let Some(op) = self.native(callee, args.len()) {
401            if op.creates_runtime_names() && op != StdOp::SequencesConcat {
402                return Ok(false);
403            }
404            if op == StdOp::SequencesConcat
405                && !args.iter().any(|a| {
406                    matches!(a, Arg::Expr { expr, .. }
407                    if tuples[expr.index()] || self.local_tuple(*expr, context))
408                })
409            {
410                return Ok(false);
411            }
412        } else if callbacks
413            && args.len() == 2
414            && matches!(callee, OpRef::Param(_) | OpRef::Subst(_))
415        {
416            // The separate closed-origin walk proved every possible operator
417            // value is a name-free scalar comparison. No tuple fact follows.
418        } else if let OpRef::Def(def) = callee
419            && let Some(body) = self.call_body(*def, args)
420        {
421            // A callee's own frame and captured parent are not this callsite's
422            // lexical proof context, even for a zero-arity local operator.
423            push(work, (body, 0))?;
424        } else {
425            return Ok(false);
426        }
427        Ok(true)
428    }
429
430    fn enter_let(&self, defs: &[DefId], old: &Lexical, tuples: &[bool]) -> Result<Lexical> {
431        let mut context = Lexical {
432            frame: old.frame,
433            slots: Vec::new(),
434        };
435        reserve(&mut context.slots, old.slots.len())?;
436        context.slots.extend_from_slice(&old.slots);
437        for &def in defs {
438            self.poll()?;
439            let definition = self.ev.ir().def(def);
440            let dive_ir::DefScope::LetValue { parent, slot, .. } = definition.scope else {
441                continue;
442            };
443            // Mint only for a real LET-owned slot of this immutable IR. A root
444            // Local, formal, capture or similarly numbered foreign frame cannot
445            // acquire this fact merely by having a tuple stored in it.
446            if context.frame != Some(parent) {
447                context.slots.clear();
448                context.frame = Some(parent);
449            }
450            context.slots.retain(|(bound, _)| *bound != slot);
451            let valid = self
452                .ev
453                .ir()
454                .def(parent)
455                .frame
456                .get(slot.index())
457                .is_some_and(|info| info.kind == dive_ir::SlotKind::LetValue(def));
458            if valid
459                && self.user_body(def, 0) == Some(definition.body)
460                && tuples[definition.body.index()]
461            {
462                push(&mut context.slots, (slot, def))?;
463            }
464        }
465        context.slots.sort_unstable();
466        Ok(context)
467    }
468
469    fn local_tuple(&self, expr: ExprId, context: &Lexical) -> bool {
470        let Expr::Local(local) = self.ev.ir().expr(expr) else {
471            return false;
472        };
473        local.up == 0
474            && context.slots.iter().any(|(slot, def)| {
475                *slot == local.slot
476                    && matches!(self.ev.ir().def(*def).scope,
477                dive_ir::DefScope::LetValue { parent, slot: bound, .. }
478                    if Some(parent) == context.frame && bound == local.slot)
479            })
480    }
481}
482
483// Facts arise only from an actually entered LET. They never populate the global
484// expression result vector, and roots/user-definition bodies start empty.
485#[derive(Default, PartialEq, Eq)]
486struct Lexical {
487    frame: Option<DefId>,
488    slots: Vec<(dive_ir::Slot, DefId)>,
489}
490
491struct Sources {
492    exprs: Vec<ExprId>,
493    scalar_callbacks: bool,
494}
495
496enum Capture {
497    Environment(Env),
498    Slot(Sv),
499    Value(Value),
500    State(StateRef),
501}
502
503#[derive(Default)]
504struct Retained {
505    frames: Vec<Arc<Frame>>,
506    links: Vec<Arc<SubstLink>>,
507    functions: Vec<Fcn>,
508    sets: Vec<Set>,
509    thunks: Vec<Arc<Thunk>>,
510    states: Vec<Arc<[Option<Value>]>>,
511    scalar_callbacks: bool,
512}
513
514impl Analysis<'_> {
515    fn captures(&self, roots: &[(ExprId, Scope)]) -> Result<Option<Sources>> {
516        let mut work = Vec::new();
517        let mut sources = Vec::new();
518        let mut retained = Retained::default();
519        for (expr, scope) in roots {
520            self.poll()?;
521            if !Arc::ptr_eq(&scope.owner, &self.ev.core.ir)
522                || !Arc::ptr_eq(&scope.names, &self.ev.core.names)
523                || !scope.context.ptr_eq(&Arc::downgrade(&self.ev.core))
524            {
525                return Ok(None);
526            }
527            push(&mut sources, *expr)?;
528            if let Some(wrapper) = scope.wrapper {
529                push(&mut sources, wrapper)?;
530            }
531            push(&mut work, Capture::Environment(scope.env.clone()))?;
532        }
533        for value in self.ev.core.def_values.values() {
534            push(&mut work, Capture::Value(value.clone()))?;
535        }
536        for value in self.ev.core.startup.iter().chain(&self.ev.core.def_cache) {
537            if let Some(value) = value.get() {
538                push(&mut work, Capture::Value(value.clone()))?;
539            }
540        }
541        for binding in self.ev.core.consts.iter().flatten() {
542            if let ConstBinding::Value(value) = binding {
543                push(&mut work, Capture::Value(value.clone()))?;
544            }
545        }
546        while let Some(task) = work.pop() {
547            self.poll()?;
548            let known = match task {
549                Capture::Environment(env) => {
550                    self.capture_environment(env, &mut work, &mut retained)?
551                }
552                Capture::Slot(slot) => {
553                    self.capture_slot(slot, &mut work, &mut sources, &mut retained)?
554                }
555                Capture::Value(value) => self.capture_value(value, &mut work, &mut retained)?,
556                Capture::State(StateRef::Null | StateRef::Empty) => true,
557                Capture::State(StateRef::Vals(values)) => {
558                    if !retained
559                        .states
560                        .iter()
561                        .any(|prior| Arc::ptr_eq(prior, &values))
562                    {
563                        push(&mut retained.states, values.clone())?;
564                        for value in values.iter().flatten() {
565                            push(&mut work, Capture::Value(value.clone()))?;
566                        }
567                    }
568                    true
569                }
570                Capture::State(StateRef::Named(_)) => false,
571            };
572            if !known {
573                return Ok(None);
574            }
575        }
576        Ok(Some(Sources {
577            exprs: sources,
578            scalar_callbacks: retained.scalar_callbacks,
579        }))
580    }
581
582    fn capture_environment(
583        &self,
584        env: Env,
585        work: &mut Vec<Capture>,
586        retained: &mut Retained,
587    ) -> Result<bool> {
588        if env.dynamic.at.is_some() || env.dynamic.cut.is_some() {
589            return Ok(false);
590        }
591        let mut link = env.dynamic.subst.clone();
592        while let Some(current) = link.take() {
593            self.poll()?;
594            if retained
595                .links
596                .iter()
597                .any(|prior| Arc::ptr_eq(prior, &current))
598            {
599                break;
600            }
601            push(&mut retained.links, current.clone())?;
602            push(work, Capture::Slot(current.val.clone()))?;
603            link.clone_from(&current.next);
604        }
605        let mut frame = Some(env.frame);
606        while let Some(current) = frame.take() {
607            self.poll()?;
608            if retained
609                .frames
610                .iter()
611                .any(|prior| Arc::ptr_eq(prior, &current))
612            {
613                break;
614            }
615            push(&mut retained.frames, current.clone())?;
616            let Some(definition) = self.ev.ir().defs().get(current.def.index()) else {
617                return Ok(false);
618            };
619            for (index, slot) in current.slots.iter().enumerate() {
620                if definition.params.get(index).is_some_and(|p| p.arity != 0)
621                    && !matches!(slot, Sv::Op(_))
622                {
623                    return Ok(false); // An opaque operator root is not forwarding.
624                }
625                push(work, Capture::Slot(slot.clone()))?;
626            }
627            frame.clone_from(&current.parent);
628        }
629        Ok(true)
630    }
631
632    fn capture_slot(
633        &self,
634        slot: Sv,
635        work: &mut Vec<Capture>,
636        sources: &mut Vec<ExprId>,
637        retained: &mut Retained,
638    ) -> Result<bool> {
639        self.poll()?;
640        match slot {
641            Sv::Thunk(thunk) => {
642                if retained
643                    .thunks
644                    .iter()
645                    .any(|prior| Arc::ptr_eq(prior, &thunk))
646                {
647                    return Ok(true);
648                }
649                push(&mut retained.thunks, thunk.clone())?;
650                push(sources, thunk.expr)?;
651                push(work, Capture::Environment(thunk.env.clone()))?;
652                for cache in thunk.stored_caches().into_iter().flatten() {
653                    let (Ev::V(value), before, after) = cache else {
654                        return Ok(false);
655                    };
656                    push(work, Capture::Value(value))?;
657                    push(work, Capture::State(before))?;
658                    push(work, Capture::State(after))?;
659                }
660            }
661            Sv::Val(value) => push(work, Capture::Value(value))?,
662            Sv::Unset | Sv::AnalysisBound | Sv::AnalysisConstant => {}
663            Sv::Op(op) if self.scalar_operator(&op) => retained.scalar_callbacks = true,
664            Sv::Fcn(_) | Sv::Op(_) => return Ok(false),
665        }
666        Ok(true)
667    }
668
669    fn capture_value(
670        &self,
671        value: Value,
672        work: &mut Vec<Capture>,
673        retained: &mut Retained,
674    ) -> Result<bool> {
675        match value {
676            Value::Fcn(function) => {
677                if retained
678                    .functions
679                    .iter()
680                    .any(|prior| prior.ptr_eq(&function))
681                {
682                    return Ok(true);
683                }
684                push(&mut retained.functions, function.clone())?;
685                for (key, value) in function.iter() {
686                    self.poll()?;
687                    push(work, Capture::Value(key))?;
688                    push(work, Capture::Value(value.clone()))?;
689                }
690            }
691            Value::Set(set) => {
692                // A warm provider is still opaque. Inspect representation before
693                // any cached payload, without asking the provider about itself.
694                if !matches!(
695                    set.kind(),
696                    SetKind::Raw
697                        | SetKind::Enum
698                        | SetKind::Interval
699                        | SetKind::Nat
700                        | SetKind::Int
701                        | SetKind::Strings
702                ) {
703                    return Ok(false);
704                }
705                if retained.sets.iter().any(|prior| prior.ptr_eq(&set)) {
706                    return Ok(true);
707                }
708                push(&mut retained.sets, set.clone())?;
709                if matches!(set.kind(), SetKind::Raw | SetKind::Enum) {
710                    let Some(values) = set.stored_elements() else {
711                        return Ok(false);
712                    };
713                    for value in values {
714                        self.poll()?;
715                        push(work, Capture::Value(value.clone()))?;
716                    }
717                }
718            }
719            _ => {}
720        }
721        Ok(true)
722    }
723}