Skip to main content

dive_core/
generate.rs

1//! Successor and initial-state generation with TLC's `getNextStates` rules.
2//!
3//! The continuation list (TLC's `ActionItemList`) is a stack of nodes in the
4//! machine, linked by index; a call pushes its items and truncates them on
5//! return, so `\A` and `[A]_v` can run two continuations from one tail. The
6//! successor buffer is `Machine::s1`, bound and unbound in place: each
7//! emitted successor is a snapshot of it (§8.2). Bindings of frame slots
8//! are saved and restored around every generator scope, so a continuation
9//! always runs with the bindings it was created under.
10
11use crate::Error;
12use crate::eval::Machine;
13use crate::handle::Handle;
14use crate::plan::{Bind, Code, G, GNode, Node, P, Raw, Unch};
15
16mod composition;
17mod constructive;
18
19const NONE: u32 = u32::MAX;
20
21/// A pending item of the continuation list.
22#[derive(Clone, Copy, Debug)]
23pub(crate) enum Item {
24    /// A conjunct: its generator and its boolean form.
25    Conj(G, P),
26    /// The remaining variables of an `UNCHANGED` (a `GNode::Unchanged` or
27    /// `GNode::StepBox`), from index `from`.
28    Unch { g: G, from: u32 },
29    /// An `\A` body under one later binding, whose slot values start at
30    /// `vals` in `Machine::cvals`.
31    Under { g: G, vals: u32 },
32    /// `<<A>>_v`'s `CHANGED v`: `v = v'`, which must be false.
33    Changed(P),
34}
35
36/// A node of the continuation stack.
37#[derive(Clone, Copy, Debug)]
38pub struct ContNode {
39    item: Item,
40    next: u32,
41}
42
43/// Where emitted states go.
44pub trait Sink {
45    /// Receives the successor in `m.s1` (complete or not). Returning an
46    /// error of kind [`crate::ErrorKind::Stop`] ends the enumeration.
47    ///
48    /// # Errors
49    /// Stop, or any error of the sink's own checks.
50    fn emit(&mut self, m: &mut Machine, code: &Code) -> Result<(), Error>;
51
52    /// Whether actual Next traversal uses constructive index ordering. This
53    /// does not affect separately evaluated predicates or ENABLED queries.
54    fn constructive(&self) -> bool {
55        false
56    }
57
58    /// Chooses an index below the positive bound for constructive traversal.
59    ///
60    /// # Errors
61    /// An ordinary sink has no random-index owner.
62    fn generation_index(&mut self, _: u64) -> Result<u64, Error> {
63        Err(Error::unsupported(
64            "constructive generation has no index chooser",
65        ))
66    }
67}
68
69impl Machine {
70    fn push_cont(&mut self, item: Item, next: u32) -> u32 {
71        #[allow(
72            clippy::cast_possible_truncation,
73            reason = "continuation stacks are small"
74        )]
75        let at = self.conts.len() as u32;
76        self.conts.push(ContNode { item, next });
77        at
78    }
79
80    fn save(&mut self, slots: impl Iterator<Item = u32>) -> usize {
81        let mark = self.saved.len();
82        for s in slots {
83            let v = self.slot(s);
84            self.saved.push(v);
85        }
86        mark
87    }
88
89    fn restore(&mut self, mark: usize, slots: impl Iterator<Item = u32>) {
90        for (k, s) in slots.enumerate() {
91            let v = self.saved.get(mark + k).copied().unwrap_or(Handle::EMPTY);
92            self.set_slot(s, v);
93        }
94        self.saved.truncate(mark);
95    }
96
97    fn bind_var(&mut self, var: u16, v: Handle) {
98        if let Some(x) = self.s1.get_mut(usize::from(var)) {
99            *x = v;
100            self.assigned += 1;
101        }
102    }
103
104    fn unbind_var(&mut self, var: u16) {
105        if let Some(x) = self.s1.get_mut(usize::from(var)) {
106            *x = Handle::EMPTY;
107            self.assigned -= 1;
108        }
109    }
110
111    /// Clears the successor buffer.
112    pub fn clear_buffer(&mut self) {
113        self.s1.iter_mut().for_each(|x| *x = Handle::EMPTY);
114        self.assigned = 0;
115    }
116
117    /// Runs one action (or initial predicate) from `self.s0`, emitting every
118    /// successor into `sink`. The caller has entered the action's frame.
119    ///
120    /// # Errors
121    /// Evaluation errors, refusals, and the sink's stop.
122    pub fn run_action(&mut self, code: &Code, g: G, sink: &mut dyn Sink) -> Result<(), Error> {
123        self.clear_buffer();
124        let mark = self.conts.len();
125        let r = self.gen_node(code, g, NONE, sink);
126        self.conts.truncate(mark);
127        r
128    }
129
130    /// Runs actual Next traversal with bounded randomized disjunction and
131    /// existential ordering. The sink stops after its first admitted complete
132    /// row; continuing searches remaining alternatives. `choose(n)` must return
133    /// a value below the positive `n`. Ordinary predicate/ENABLED evaluation
134    /// never inherits these operational choices.
135    ///
136    /// # Errors
137    /// The ordinary generation errors, unsupported indexed domains or an
138    /// out-of-range caller index.
139    pub fn run_action_generation(
140        &mut self,
141        code: &Code,
142        g: G,
143        sink: &mut dyn Sink,
144        choose: &mut dyn FnMut(u64) -> u64,
145    ) -> Result<(), Error> {
146        struct Constructive<'a> {
147            sink: &'a mut dyn Sink,
148            choose: &'a mut dyn FnMut(u64) -> u64,
149        }
150        impl Sink for Constructive<'_> {
151            fn emit(&mut self, machine: &mut Machine, code: &Code) -> Result<(), Error> {
152                self.sink.emit(machine, code)
153            }
154            fn constructive(&self) -> bool {
155                true
156            }
157            fn generation_index(&mut self, bound: u64) -> Result<u64, Error> {
158                Ok((self.choose)(bound))
159            }
160        }
161        self.run_action(code, g, &mut Constructive { sink, choose })
162    }
163
164    /// `ENABLED A` in the current state `s0` (TLC's `Tool.enabled`): runs
165    /// `A` with a fresh successor buffer and stops at the first successor,
166    /// complete or not. The buffer and the continuation stack of an
167    /// enclosing generation are saved and restored around it.
168    ///
169    /// # Errors
170    /// Evaluation errors and refusals inside `A`.
171    pub(crate) fn enabled(&mut self, code: &Code, g: G) -> Result<Handle, Error> {
172        struct First(bool);
173        impl Sink for First {
174            fn emit(&mut self, _: &mut Machine, _: &Code) -> Result<(), Error> {
175                self.0 = true;
176                Err(Error::stop())
177            }
178        }
179        let saved = std::mem::take(&mut self.s1);
180        self.s1 = vec![Handle::EMPTY; saved.len()];
181        let assigned = self.assigned;
182        let mut first = First(false);
183        let r = self.run_action(code, g, &mut first);
184        self.s1 = saved;
185        self.assigned = assigned;
186        match r {
187            Ok(()) => Ok(Handle::bool(first.0)),
188            Err(e) if first.0 && e.kind() == crate::ErrorKind::Stop => Ok(Handle::TRUE),
189            Err(e) => Err(e),
190        }
191    }
192
193    fn cont(&mut self, code: &Code, acts: u32, sink: &mut dyn Sink) -> Result<(), Error> {
194        if acts == NONE {
195            return sink.emit(self, code);
196        }
197        if self.warn && self.assigned == self.s1.len() {
198            return self.fast(code, acts, sink);
199        }
200        let Some(&c) = self.conts.get(acts as usize) else {
201            return Err(Error::internal("continuation out of range"));
202        };
203        match c.item {
204            Item::Conj(g, _) => self.gen_node(code, g, c.next, sink),
205            Item::Unch { g, from } => self.unchanged(code, g, from, c.next, sink),
206            Item::Changed(same) => {
207                if self.changed(code, same)? {
208                    self.cont(code, c.next, sink)
209                } else {
210                    Ok(())
211                }
212            }
213            Item::Under { g, vals } => {
214                let binds = forall_binds(code, g)?;
215                let slots: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
216                let mark = self.save(slots.iter().copied());
217                for (k, &s) in slots.iter().enumerate() {
218                    let v = self
219                        .cvals
220                        .get(vals as usize + k)
221                        .copied()
222                        .unwrap_or(Handle::EMPTY);
223                    self.set_slot(s, v);
224                }
225                let body = match code.gnodes.get(g as usize) {
226                    Some(GNode::Forall { body, .. }) => *body,
227                    _ => return Err(Error::internal("continuation of a non-\\A node")),
228                };
229                let r = self.gen_node(code, body, c.next, sink);
230                self.restore(mark, slots.iter().copied());
231                r
232            }
233        }
234    }
235
236    /// TLC's `getNextStatesAllAssigned`: the pending items are evaluated as
237    /// booleans; an `UNCHANGED` item leaves the shortcut.
238    fn fast(&mut self, code: &Code, acts: u32, sink: &mut dyn Sink) -> Result<(), Error> {
239        let mut cur = acts;
240        while cur != NONE {
241            let Some(&c) = self.conts.get(cur as usize) else {
242                return Err(Error::internal("continuation out of range"));
243            };
244            match c.item {
245                Item::Conj(_, p) => {
246                    if !self.eval_bool(code, p)? {
247                        return Ok(());
248                    }
249                }
250                Item::Unch { g, from } => return self.unchanged(code, g, from, c.next, sink),
251                Item::Changed(same) => {
252                    if !self.changed(code, same)? {
253                        return Ok(());
254                    }
255                }
256                Item::Under { g, vals } => {
257                    let (binds, body_p) = match code.gnodes.get(g as usize) {
258                        Some(GNode::Forall { binds, body_p, .. }) => (binds, *body_p),
259                        _ => return Err(Error::internal("continuation of a non-\\A node")),
260                    };
261                    let slots: Vec<u32> =
262                        binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
263                    let mark = self.save(slots.iter().copied());
264                    for (k, &s) in slots.iter().enumerate() {
265                        let v = self
266                            .cvals
267                            .get(vals as usize + k)
268                            .copied()
269                            .unwrap_or(Handle::EMPTY);
270                        self.set_slot(s, v);
271                    }
272                    let b = self.eval_bool(code, body_p);
273                    self.restore(mark, slots.iter().copied());
274                    if !b? {
275                        return Ok(());
276                    }
277                }
278            }
279            cur = c.next;
280        }
281        sink.emit(self, code)
282    }
283
284    /// TLC's `CHANGED` item: `v` evaluated in `s0` and in `s1` (as the
285    /// current state) differ.
286    fn changed(&mut self, code: &Code, same: P) -> Result<bool, Error> {
287        Ok(!self.eval_bool(code, same)?)
288    }
289
290    fn unchanged(
291        &mut self,
292        code: &Code,
293        g: G,
294        from: u32,
295        rest: u32,
296        sink: &mut dyn Sink,
297    ) -> Result<(), Error> {
298        let items: &[Unch] = match code.gnodes.get(g as usize) {
299            Some(GNode::Unchanged(v) | GNode::StepBox { vars: v, .. }) => v,
300            _ => return Err(Error::internal("UNCHANGED continuation of another node")),
301        };
302        let Some(&item) = items.get(from as usize) else {
303            return self.cont(code, rest, sink);
304        };
305        let mark = self.conts.len();
306        let next = if (from as usize + 1) < items.len() {
307            self.push_cont(Item::Unch { g, from: from + 1 }, rest)
308        } else {
309            rest
310        };
311        let r = match item {
312            Unch::Var { var, at } => {
313                let old = self
314                    .s0
315                    .get(usize::from(var))
316                    .copied()
317                    .unwrap_or(Handle::EMPTY);
318                let cur = self
319                    .s1
320                    .get(usize::from(var))
321                    .copied()
322                    .unwrap_or(Handle::EMPTY);
323                if cur.is_empty() {
324                    self.bind_var(var, old);
325                    let r = self.cont(code, next, sink);
326                    self.unbind_var(var);
327                    r
328                } else if self.demand_equals(cur, old)? {
329                    self.cont(code, next, sink)
330                } else {
331                    // TLC prints warning 2143 here (`Tool.java:1676`).
332                    if !self.warnings.contains(&(var, at)) {
333                        self.warnings.push((var, at));
334                    }
335                    Ok(())
336                }
337            }
338            // `verifyUnchanged`: `e` in `s0` and in `s1` as the current
339            // state.
340            Unch::Verify(same) => {
341                if self.eval_bool(code, same)? {
342                    self.cont(code, next, sink)
343                } else {
344                    Ok(())
345                }
346            }
347        };
348        self.conts.truncate(mark);
349        r
350    }
351
352    fn gen_node(&mut self, code: &Code, g: G, acts: u32, sink: &mut dyn Sink) -> Result<(), Error> {
353        let Some(observer) = &self.debugger else {
354            return self.gen_node_inner(code, g, acts, sink);
355        };
356        let instruction = crate::debug::Instruction::Generator(g);
357        let guard = crate::debug::Guard::enter(observer, instruction, code, self)?;
358        let result = self.gen_node_inner(code, g, acts, sink);
359        let returned = match &result {
360            Ok(()) => crate::debug::Returned::Generated,
361            Err(error) => crate::debug::Returned::Failed(error),
362        };
363        guard.returned(instruction, code, self, returned)?;
364        result
365    }
366
367    #[allow(clippy::too_many_lines, reason = "one arm per generator rule")]
368    fn gen_node_inner(
369        &mut self,
370        code: &Code,
371        g: G,
372        acts: u32,
373        sink: &mut dyn Sink,
374    ) -> Result<(), Error> {
375        if self.fuel != u64::MAX {
376            self.charge(1)?;
377        }
378        let Some(node) = code.gnodes.get(g as usize) else {
379            return Err(Error::internal("generator node out of range"));
380        };
381        match node {
382            GNode::Composition { first, then, reset } => {
383                if sink.constructive() {
384                    return Err(Error::unsupported(
385                        "constructive generation of action composition",
386                    ));
387                }
388                if acts != NONE || self.assigned != 0 {
389                    return Err(Error::unsupported(
390                        "action composition with pending conjuncts or preassigned variables",
391                    ));
392                }
393                self.composition(code, *first, *then, reset, sink)
394            }
395            GNode::Conj(items) => {
396                let Some((&(first, _), rest)) = items.split_first() else {
397                    return self.cont(code, acts, sink);
398                };
399                let mark = self.conts.len();
400                let mut head = acts;
401                for &(gi, pi) in rest.iter().rev() {
402                    head = self.push_cont(Item::Conj(gi, pi), head);
403                }
404                let r = self.gen_node(code, first, head, sink);
405                self.conts.truncate(mark);
406                r
407            }
408            GNode::Disj(items) => {
409                if sink.constructive() {
410                    return self.generation_disjunction(code, items, acts, sink);
411                }
412                for &gi in items {
413                    self.gen_node(code, gi, acts, sink)?;
414                }
415                Ok(())
416            }
417            GNode::Exists { binds, body, .. } => {
418                self.charge(binds.iter().map(|b| b.slots.len()).sum())?;
419                let slots: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
420                let mark = self.save(slots.iter().copied());
421                let r = if sink.constructive() {
422                    self.generation_exists(code, binds, *body, acts, sink)
423                } else {
424                    self.for_each_binding(code, binds, &mut |machine| {
425                        machine.gen_node(code, *body, acts, sink)?;
426                        Ok(true)
427                    })
428                    .map(|_| ())
429                };
430                self.restore(mark, slots.iter().copied());
431                r
432            }
433            GNode::Forall { binds, body, .. } => {
434                self.charge(binds.iter().map(|b| b.slots.len()).sum())?;
435                let slots: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
436                let mark = self.save(slots.iter().copied());
437                let r = (|| {
438                    let mut contexts: Vec<Vec<Handle>> = Vec::new();
439                    self.for_each_binding(code, binds, &mut |machine| {
440                        machine.charge(slots.len() + 1)?;
441                        contexts.push(slots.iter().map(|&s| machine.slot(s)).collect());
442                        Ok(true)
443                    })?;
444                    if contexts.is_empty() {
445                        return self.cont(code, acts, sink);
446                    }
447                    let cmark = self.conts.len();
448                    let vmark = self.cvals.len();
449                    let result = (|| {
450                        let mut head = acts;
451                        for ctx in contexts.iter().skip(1) {
452                            self.charge(ctx.len() + 1)?;
453                            #[allow(
454                                clippy::cast_possible_truncation,
455                                reason = "small value stacks"
456                            )]
457                            let at = self.cvals.len() as u32;
458                            self.cvals.extend_from_slice(ctx);
459                            head = self.push_cont(Item::Under { g, vals: at }, head);
460                        }
461                        for (&s, &v) in slots.iter().zip(&contexts[0]) {
462                            self.set_slot(s, v);
463                        }
464                        self.gen_node(code, *body, head, sink)
465                    })();
466                    self.conts.truncate(cmark);
467                    self.cvals.truncate(vmark);
468                    result
469                })();
470                self.restore(mark, slots.iter().copied());
471                r
472            }
473            GNode::If { cond, then, other } => {
474                if self.eval_bool(code, *cond)? {
475                    self.gen_node(code, *then, acts, sink)
476                } else {
477                    self.gen_node(code, *other, acts, sink)
478                }
479            }
480            GNode::Case { arms, other } => {
481                if sink.constructive() {
482                    return Err(Error::unsupported(
483                        "constructive generation of CASE actions",
484                    ));
485                }
486                for &(p, gi) in arms {
487                    if self.eval_bool(code, p)? {
488                        return self.gen_node(code, gi, acts, sink);
489                    }
490                }
491                match other {
492                    Some(o) => self.gen_node(code, *o, acts, sink),
493                    None => Err(Error::eval(
494                        "TLC encountered a CASE with no conditions true",
495                    )),
496                }
497            }
498            GNode::Implies { lhs, rhs } => {
499                if self.eval_bool(code, *lhs)? {
500                    self.gen_node(code, *rhs, acts, sink)
501                } else {
502                    self.cont(code, acts, sink)
503                }
504            }
505            GNode::Assign { var, rhs } => {
506                let r = self.eval_component(code, *rhs)?;
507                let cur = self
508                    .s1
509                    .get(usize::from(*var))
510                    .copied()
511                    .unwrap_or(Handle::EMPTY);
512                if cur.is_empty() {
513                    self.bind_var(*var, r);
514                    let res = self.cont(code, acts, sink);
515                    self.unbind_var(*var);
516                    res
517                } else if self.demand_equals(cur, r)? {
518                    self.cont(code, acts, sink)
519                } else {
520                    Ok(())
521                }
522            }
523            GNode::AssignIn { var, set } => self.assign_in(code, *var, *set, acts, sink),
524            GNode::AssignInRaw { var, set, raw } => {
525                self.assign_in_raw(code, *var, *set, raw, acts, sink)
526            }
527            GNode::Unchanged(_) => self.unchanged(code, g, 0, acts, sink),
528            GNode::StepBox { action, .. } => {
529                self.gen_node(code, *action, acts, sink)?;
530                self.unchanged(code, g, 0, acts, sink)
531            }
532            GNode::StepAngle { action, same } => {
533                let mark = self.conts.len();
534                let head = self.push_cont(Item::Changed(*same), acts);
535                let r = self.gen_node(code, *action, head, sink);
536                self.conts.truncate(mark);
537                r
538            }
539            GNode::FcnAction { binds, arg, body } => {
540                self.fcn_action(code, binds, *arg, *body, acts, sink)
541            }
542            GNode::Scope { reset, body } => {
543                let mark = self.save(reset.iter().copied());
544                for &s in reset {
545                    self.set_slot(s, Handle::EMPTY);
546                }
547                let r = self.gen_node(code, *body, acts, sink);
548                self.restore(mark, reset.iter().copied());
549                r
550            }
551            GNode::Guard(p) => {
552                if self.eval_bool(code, *p)? {
553                    self.cont(code, acts, sink)
554                } else {
555                    Ok(())
556                }
557            }
558        }
559    }
560
561    fn assign_in(
562        &mut self,
563        code: &Code,
564        var: u16,
565        set: P,
566        acts: u32,
567        sink: &mut dyn Sink,
568    ) -> Result<(), Error> {
569        let cur = self
570            .s1
571            .get(usize::from(var))
572            .copied()
573            .unwrap_or(Handle::EMPTY);
574        // A primed definition's site over a filter is streamed as its body
575        // is, without building the set to cache it.
576        let set = match code.nodes.get(set as usize) {
577            Some(Node::Memo { site, body })
578                if cur.is_empty()
579                    && code.sites.get(*site as usize).is_some_and(|s| s.candidate)
580                    && matches!(code.nodes.get(*body as usize), Some(Node::Filter { .. })) =>
581            {
582                *body
583            }
584            _ => set,
585        };
586        // A filter is streamed: its bound set's elements, filtered, without
587        // building the set.
588        if cur.is_empty()
589            && let Some(Node::Filter { bind, pred, subset }) = code.nodes.get(set as usize)
590        {
591            // A proven `SUBSET F` rewrite streams the subsets of `F`: they
592            // are the filter's elements, in its order.
593            if let Some(mut c) = self.subset_cursor(code, *subset)? {
594                loop {
595                    let before = self.heap.mark();
596                    let Some(e) = self.work_next(&mut c)? else {
597                        break;
598                    };
599                    let forced = self.thunk_mark();
600                    self.bind_var(var, e);
601                    let r = self.cont(code, acts, sink);
602                    self.unbind_var(var);
603                    r?;
604                    if self.thunks_released(forced) {
605                        self.heap.rollback(before);
606                    }
607                }
608                return Ok(());
609            }
610            // Enumerated without normalizing, so that a symbolic domain's
611            // candidates are built one at a time.
612            let dom = self.eval(code, bind.domain)?;
613            let mut c = self.work_cursor(dom)?;
614            let mark = self.save(bind.slots.iter().copied());
615            let r = (|| {
616                loop {
617                    let before = self.heap.mark();
618                    let Some(e) = self.work_next(&mut c)? else {
619                        break;
620                    };
621                    let forced = self.thunk_mark();
622                    self.bind_one(bind, e)?;
623                    if self.eval_bool(code, *pred)? {
624                        self.bind_var(var, e);
625                        let r = self.cont(code, acts, sink);
626                        self.unbind_var(var);
627                        r?;
628                    }
629                    // A rejected candidate is freed (as in
630                    // `Machine::filter`), and so is an accepted one once its
631                    // continuation has emitted its states.
632                    if self.thunks_released(forced) {
633                        self.heap.rollback(before);
634                    }
635                }
636                Ok(())
637            })();
638            self.restore(mark, bind.slots.iter().copied());
639            return r;
640        }
641        let s = self.eval(code, set)?;
642        if !cur.is_empty() {
643            return if self.member(cur, s)? {
644                self.cont(code, acts, sink)
645            } else {
646                Ok(())
647            };
648        }
649        if !s.is_compound() {
650            return Err(Error::eval("The right side of \\IN is not a set"));
651        }
652        if !self.heap.is_finite(s) {
653            return Err(Error::eval("The right side of \\IN is not enumerable"));
654        }
655        let mut c = self.work_cursor(s)?;
656        self.each_in(&mut c, code, var, acts, sink)
657    }
658}
659
660impl Machine {
661    /// Binds `var` to each element of `c` in turn and runs the
662    /// continuation. An element and the continuation's transients are freed
663    /// once it returns: an `Init` over a large set would
664    /// otherwise hold every candidate state until the level ends. Only when
665    /// no thunk was forced to a transient meanwhile, whose slot may hold a
666    /// value built after the mark; the
667    /// cursor's own state predates the mark.
668    fn each_in(
669        &mut self,
670        c: &mut crate::heap::Cursor,
671        code: &Code,
672        var: u16,
673        acts: u32,
674        sink: &mut dyn Sink,
675    ) -> Result<(), Error> {
676        loop {
677            let before = self.heap.mark();
678            let Some(e) = self.work_next(c)? else {
679                return Ok(());
680            };
681            let forced = self.thunk_mark();
682            self.bind_var(var, e);
683            let r = self.cont(code, acts, sink);
684            self.unbind_var(var);
685            r?;
686            if self.thunks_released(forced) {
687                self.heap.rollback(before);
688            }
689        }
690    }
691
692    /// `x' \in S` over a set whose TLC `elements()` may repeat elements
693    /// (§6): TLC's multiplicity is computed, and the run refuses when it
694    /// differs from the normalized set's, because which one TLC walks
695    /// depends on the set object's history. Otherwise the normalized set
696    /// is enumerated, in the run's value order.
697    fn assign_in_raw(
698        &mut self,
699        code: &Code,
700        var: u16,
701        set: P,
702        raw: &Raw,
703        acts: u32,
704        sink: &mut dyn Sink,
705    ) -> Result<(), Error> {
706        let cur = self
707            .s1
708            .get(usize::from(var))
709            .copied()
710            .unwrap_or(Handle::EMPTY);
711        let s = self.eval(code, set)?;
712        if !cur.is_empty() {
713            return if self.member(cur, s)? {
714                self.cont(code, acts, sink)
715            } else {
716                Ok(())
717            };
718        }
719        if !s.is_compound() {
720            return Err(Error::eval("The right side of \\IN is not a set"));
721        }
722        if !self.heap.is_finite(s) {
723            return Err(Error::eval("The right side of \\IN is not enumerable"));
724        }
725        let elems = self.raw_elems(code, raw)?;
726        let listed = elems.len() as u64;
727        let distinct = self.work_cardinality(s)?;
728        if listed != distinct {
729            return Err(Error::unsupported(format!(
730                "x' \\in a lazily represented set: TLC's unnormalized enumeration of it ({listed} elements) differs from its normalized one ({distinct} elements), and which one TLC uses depends on whether it has already compared, sized or fingerprinted the same set object"
731            )));
732        }
733        // Under TLC's exploration order the order is observable too (A6):
734        // the parts' sequence must be the normalized order.
735        if self.heap.store().semantics().tlc_exploration
736            && elems
737                .windows(2)
738                .any(|w| self.heap.cmp(w[0], w[1]) != std::cmp::Ordering::Less)
739        {
740            return Err(Error::unsupported(
741                "x' \\in a lazily represented set under --compat=tlc: TLC's unnormalized enumeration of it lists the elements in another order than its normalized one, and which one TLC uses depends on the set object's history (A6)",
742            ));
743        }
744        let mut c = self.work_cursor(s)?;
745        self.each_in(&mut c, code, var, acts, sink)
746    }
747
748    fn finite_elems(&mut self, h: Handle) -> Result<Vec<Handle>, Error> {
749        if !h.is_compound() || !self.heap.view(h).kind.is_set() {
750            return Err(Error::eval("enumerating a value that is not a set"));
751        }
752        if !self.heap.is_finite(h) {
753            return Err(Error::unsupported(
754                "TLC's enumeration of a lazily represented set with an infinite part (core)",
755            ));
756        }
757        let n = self.work_norm(h)?;
758        self.work_elements(n)
759    }
760
761    fn distinct(&mut self, elems: &[Handle]) -> usize {
762        let mut v = elems.to_vec();
763        let set = self.heap.set_from(&mut v);
764        self.heap.view(set).len()
765    }
766
767    /// TLC's `elements()` sequence of a lazily represented set, repeats
768    /// included (the order within a part is normalized; only the length is
769    /// observable here).
770    #[allow(clippy::too_many_lines, reason = "one arm per lazy set class")]
771    fn raw_elems(&mut self, code: &Code, raw: &Raw) -> Result<Vec<Handle>, Error> {
772        match raw {
773            Raw::Leaf(p) => {
774                let h = self.eval(code, *p)?;
775                self.finite_elems(h)
776            }
777            Raw::Cup(a, b) => {
778                let mut x = self.raw_elems(code, a)?;
779                x.extend(self.raw_elems(code, b)?);
780                Ok(x)
781            }
782            Raw::Union(items) => {
783                // The enumerated set of sets is normalized first: equal
784                // members are listed once.
785                let mut members: Vec<(Handle, Vec<Handle>)> = Vec::new();
786                for r in items {
787                    let elems = self.raw_elems(code, r)?;
788                    let mut v = elems.clone();
789                    let set = self.heap.set_from(&mut v);
790                    if let Some((_, other)) = members.iter().find(|(m, _)| self.heap.eq(*m, set)) {
791                        if other.len() != elems.len() {
792                            return Err(Error::unsupported(
793                                "UNION of equal sets that TLC enumerates differently (core)",
794                            ));
795                        }
796                        continue;
797                    }
798                    members.push((set, elems));
799                }
800                Ok(members.into_iter().flat_map(|(_, e)| e).collect())
801            }
802            Raw::UnionOf(p) => {
803                let outer = self.eval(code, *p)?;
804                let members = self.finite_elems(outer)?;
805                if members.len() == 1 {
806                    // A lone member is never compared while the outer set
807                    // is normalized, so TLC may still hold it lazily.
808                    return Err(Error::unsupported(
809                        "UNION of a one-member set whose member TLC may represent lazily (core)",
810                    ));
811                }
812                let mut x = Vec::new();
813                for m in members {
814                    x.extend(self.finite_elems(m)?);
815                }
816                Ok(x)
817            }
818            Raw::Filter { bind, pred, inner } => {
819                let elems = self.raw_elems(code, inner)?;
820                let mark = self.save(bind.slots.iter().copied());
821                let r = (|| {
822                    let mut out = Vec::new();
823                    for e in elems {
824                        self.bind_one(bind, e)?;
825                        if self.eval_bool(code, *pred)? {
826                            out.push(e);
827                        }
828                    }
829                    Ok(out)
830                })();
831                self.restore(mark, bind.slots.iter().copied());
832                r
833            }
834            Raw::Cap(ra, rb, pa, pb) => {
835                let a = self.eval(code, *pa)?;
836                let (walk, other) = if self.heap.is_finite(a) {
837                    (ra, *pb)
838                } else {
839                    (rb, *pa)
840                };
841                let elems = self.raw_elems(code, walk)?;
842                let o = self.eval(code, other)?;
843                let mut out = Vec::new();
844                for e in elems {
845                    if self.member(e, o)? {
846                        out.push(e);
847                    }
848                }
849                Ok(out)
850            }
851            Raw::Minus(ra, pb) => {
852                let elems = self.raw_elems(code, ra)?;
853                let o = self.eval(code, *pb)?;
854                let mut out = Vec::new();
855                for e in elems {
856                    if !self.member(e, o)? {
857                        out.push(e);
858                    }
859                }
860                Ok(out)
861            }
862            Raw::Odometer(parts, p) => {
863                let mut repeats = false;
864                for r in parts {
865                    let elems = self.raw_elems(code, r)?;
866                    repeats |= self.distinct(&elems) != elems.len();
867                }
868                let h = self.eval(code, *p)?;
869                let elems = self.finite_elems(h)?;
870                if repeats && !elems.is_empty() {
871                    return Err(Error::unsupported(
872                        "x' \\in a set of functions, records or tuples over a lazily represented set whose enumeration repeats elements (core)",
873                    ));
874                }
875                Ok(elems)
876            }
877        }
878    }
879
880    /// `f[a]` as an action over an unmaterialized function constructor
881    /// (`Tool.java:1263-1289`, `getFcnContext` `:3997-4074`): the domains
882    /// are evaluated, then the argument; the argument is checked against
883    /// the domains and bound to the parameters; the body is enumerated.
884    fn fcn_action(
885        &mut self,
886        code: &Code,
887        binds: &[Bind],
888        arg: P,
889        body: G,
890        acts: u32,
891        sink: &mut dyn Sink,
892    ) -> Result<(), Error> {
893        let mut domains = Vec::with_capacity(binds.len());
894        for b in binds {
895            domains.push(self.eval(code, b.domain)?);
896        }
897        let a = self.eval(code, arg)?;
898        let slots: Vec<u32> = binds.iter().flat_map(|b| b.slots.iter().copied()).collect();
899        let mark = self.save(slots.iter().copied());
900        let r = (|| {
901            let params: usize = binds
902                .iter()
903                .map(|b| if b.tuple { 1 } else { b.slots.len() })
904                .sum();
905            if params == 1 {
906                let (Some(b), Some(&d)) = (binds.first(), domains.first()) else {
907                    return Err(Error::internal("a function action without parameters"));
908                };
909                if !self.member(a, d)? {
910                    return Err(Error::eval(
911                        "In applying a function, the argument is not in its domain",
912                    ));
913                }
914                self.bind_one(b, a)?;
915            } else {
916                let elems = self.tuple_elems(a).ok_or_else(|| {
917                    Error::eval("Attempted to apply a function to an argument not in its domain")
918                })?;
919                let mut k = 0usize;
920                for (b, &d) in binds.iter().zip(&domains) {
921                    if b.tuple {
922                        let e = *elems.get(k).ok_or_else(|| {
923                            Error::eval("a function argument has too few components")
924                        })?;
925                        k += 1;
926                        if !self.member(e, d)? {
927                            return Err(Error::eval(
928                                "In applying a function, an argument is not in its domain",
929                            ));
930                        }
931                        self.bind_one(b, e)?;
932                    } else {
933                        for &s in &b.slots {
934                            let e = *elems.get(k).ok_or_else(|| {
935                                Error::eval("a function argument has too few components")
936                            })?;
937                            k += 1;
938                            if !self.member(e, d)? {
939                                return Err(Error::eval(
940                                    "In applying a function, an argument is not in its domain",
941                                ));
942                            }
943                            self.set_slot(s, e);
944                        }
945                    }
946                }
947            }
948            self.gen_node(code, body, acts, sink)
949        })();
950        self.restore(mark, slots.iter().copied());
951        r
952    }
953
954    /// The components of a tuple (TLC's `toTuple`: a function over
955    /// `1..n`).
956    fn tuple_elems(&self, h: Handle) -> Option<Vec<Handle>> {
957        if !h.is_compound() {
958            return None;
959        }
960        let v = self.heap.view(h);
961        (v.kind == crate::node::Kind::IntFcn && (v.lo == 1 || v.data.is_empty()))
962            .then(|| v.data.to_vec())
963    }
964}
965
966fn forall_binds(code: &Code, g: G) -> Result<&[Bind], Error> {
967    match code.gnodes.get(g as usize) {
968        Some(GNode::Forall { binds, .. }) => Ok(binds),
969        _ => Err(Error::internal("continuation of a non-\\A node")),
970    }
971}