deduxit 0.5.0

A collection of logic suites: decides, checks, proves step by step and exports sequents of linear logic and of classical, intuitionistic and minimal propositional logic, with checked proofs, Kripke countermodels and Rocq certificates.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! Cut elimination on proofs with instances: the members of a step's
//! proof past the forest, the substitution of a witness for an
//! eigenvariable, and the renaming apart that keeps every eigenvariable
//! introduced by one `∀` step.
//!
//! A step reads the proof's members through its instance table. It adds
//! what it makes to a copy of that table: a binder's body under a
//! witness, and the terms, frames and members of a subproof it
//! substitutes into.
//!
//! A step copies a subproof only where it changes. So where a step
//! remakes a `∀` step, the proof may still read the original elsewhere,
//! through a subproof that two places share. Two `∀` steps with one
//! eigenvariable are no proof, so the copy gets an eigenvariable of its
//! own ([`Rewrite::apart`]).

use super::Rewrite;
use crate::hash::HashMap;
use crate::limits::{Phase, Progress, Refusal, Space};
use crate::linear::occurrences::instances::Terms;
use crate::linear::occurrences::{FrameId, Instances, Member, OccId};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::{Eigen, FoTerm, FoTermId};

/// What a step knows of the members of a proof with instances: the
/// proof's table, extended by what the step makes, and the lookups that
/// find an instance's member, a frame and an eigenvariable's term by what
/// they hold.
pub(super) struct Table {
    /// The proof's table and what the step added to it.
    pub(super) instances: Instances,
    /// Every member of the table, by its occurrence and frame.
    members: HashMap<(OccId, FrameId), Member>,
    /// Every frame of the table, by its parent and term.
    frames: HashMap<(Option<FrameId>, FoTermId), FrameId>,
    /// The term of every eigenvariable the table holds.
    eigens: HashMap<Eigen, FoTermId>,
    /// The next eigenvariable that no term and no `∀` step names, or
    /// `None` past the last a number names.
    next: Option<u32>,
}

impl Table {
    /// Returns the table of `proof`, or `None` for a proof without one.
    pub(super) fn of(proof: &Proof) -> Option<Self> {
        let instances = proof.instances()?.clone();
        let members = instances
            .members
            .iter()
            .enumerate()
            // The table's ids are `u32`s, which `Proof::with_instances`
            // checked.
            .map(|(n, &key)| (key, Member::new(instances.occurrences + n as u32)))
            .collect();
        let frames = instances
            .frames
            .iter()
            .enumerate()
            .map(|(n, &key)| (key, FrameId::new(n as u32)))
            .collect();
        let mut eigens = HashMap::default();
        let mut most: Option<u32> = None;
        for (n, term) in instances.terms.iter().enumerate() {
            if let FoTerm::Eigen(a) = *term {
                eigens
                    .entry(a)
                    .or_insert(FoTermId::new(instances.base_terms + n as u32));
                most = most.max(Some(a.get()));
            }
        }
        for node in proof.nodes() {
            if let Node::Forall(_, a, _) = *node {
                most = most.max(Some(a.get()));
            }
        }
        let next = most.map_or(Some(0), |a| a.checked_add(1));
        Some(Self {
            instances,
            members,
            frames,
            eigens,
            next,
        })
    }

    /// Returns the occurrence and frame of a member, `None` for one of
    /// the forest's own occurrences.
    pub(super) fn resolve(&self, m: Member) -> (OccId, Option<FrameId>) {
        match self.instances.instance(m) {
            Some((o, frame)) => (o, Some(frame)),
            None => (m.occ(), None),
        }
    }

    /// Returns the member that is `o` under `frame`, added where the
    /// table lacks it; the occurrence itself without a frame.
    pub(super) fn member(&mut self, o: OccId, frame: Option<FrameId>) -> Member {
        let Some(frame) = frame else {
            return Member::from(o);
        };
        *self
            .members
            .entry((o, frame))
            .or_insert_with(|| self.instances.member(o, frame))
    }

    /// Returns the member that is `o` under the frame of `like`, a member
    /// of an occurrence under as many binders.
    pub(super) fn beside(&mut self, o: OccId, like: Member) -> Member {
        let (_, frame) = self.resolve(like);
        self.member(o, frame)
    }

    /// Returns the frame that pushes `term` onto `parent`, added where the
    /// table lacks it.
    pub(super) fn frame(&mut self, parent: Option<FrameId>, term: FoTermId) -> FrameId {
        *self
            .frames
            .entry((parent, term))
            .or_insert_with(|| self.instances.frame(parent, term))
    }

    /// Returns the term of the eigenvariable `a`, added where the table
    /// lacks it.
    pub(super) fn eigen(&mut self, a: Eigen) -> FoTermId {
        *self
            .eigens
            .entry(a)
            .or_insert_with(|| self.instances.eigen(a))
    }

    /// Returns the member of the body of the binder `m` stands for, under
    /// `m`'s frame with `term` pushed.
    pub(super) fn body(&mut self, m: Member, term: FoTermId) -> Member {
        let (o, frame) = self.resolve(m);
        let frame = self.frame(frame, term);
        self.member(OccId::new(o.get() + 1), Some(frame))
    }

    /// Returns a new eigenvariable that no term and no `∀` step of the
    /// proof names, or the refusal past the last a number names.
    pub(super) fn fresh(&mut self) -> Result<Eigen, Refusal> {
        let a = self.next.ok_or(Refusal::Index {
            what: Space::Term,
            count: u64::from(u32::MAX) + 1,
            most: u64::from(u32::MAX),
        })?;
        self.next = a.checked_add(1);
        Ok(Eigen::new(a))
    }

    /// Returns the terms of the sequent and of the table, one space of
    /// ids.
    fn terms<'t>(&'t self, proof: &'t Proof) -> Terms<'t> {
        Terms {
            fo: &proof.forest().sequent().fo,
            table: &self.instances,
        }
    }
}

/// Which terms and frames name an eigenvariable a substitution maps, so
/// that one shared by many nodes is walked once.
#[derive(Default)]
struct Named {
    /// The terms, by their ids.
    terms: HashMap<FoTermId, bool>,
    /// The frames.
    frames: HashMap<FrameId, bool>,
}

/// What a substitution replaced so far, so that a term, frame or member
/// shared by many nodes is walked once.
#[derive(Default)]
struct Replaced {
    /// The terms, by their ids before.
    terms: HashMap<FoTermId, FoTermId>,
    /// The frames.
    frames: HashMap<FrameId, FrameId>,
    /// The members.
    members: HashMap<Member, Member>,
}

impl Rewrite<'_> {
    /// Returns the table of a proof with instances.
    fn table(&mut self) -> &mut Table {
        self.table
            .as_mut()
            .expect("a proof with instances has a table")
    }

    /// Returns the subproof at `top` with the eigenvariables `sigma` maps
    /// replaced by their terms: in the frames of the members its nodes
    /// name, in the witnesses of its `∃` steps, and as the eigenvariable of
    /// a `∀` step, where the term is an eigenvariable (a renaming).
    ///
    /// A node whose subproof names none of them is kept, shared with
    /// whatever else reads it; every other is made anew. Terms are closed,
    /// so no variable is captured. The nodes made anew are counted and
    /// charged ([`afford`](Self::afford)) before any is made; a copy has at
    /// most the nodes `top` reaches.
    pub(super) fn substitute(
        &mut self,
        top: NodeId,
        sigma: &HashMap<Eigen, FoTermId>,
    ) -> Result<NodeId, Refusal> {
        let reach = reached(&self.nodes, top, None);
        let mut named = Named::default();
        let mut changes = vec![false; top.index() + 1];
        for id in (0..=top.index()).filter(|&i| reach[i]) {
            let node = self.nodes[id];
            changes[id] = node.premises().any(|p| changes[p.index()])
                || node
                    .members()
                    .any(|m| self.names_member(m, sigma, &mut named))
                || match node {
                    Node::Exists(_, w, _) => self.names_term(w, sigma, &mut named),
                    Node::Forall(_, a, _) => sigma.contains_key(&a),
                    _ => false,
                };
        }
        self.afford(changes.iter().filter(|&&c| c).count())?;
        let mut replaced = Replaced::default();
        let mut made: HashMap<NodeId, NodeId> = HashMap::default();
        for id in (0..=top.index()).filter(|&i| changes[i]) {
            let node = self.nodes[id];
            let mut pairs: Vec<(Member, Member)> = Vec::with_capacity(2);
            for m in node.members() {
                pairs.push((m, self.substituted_member(m, sigma, &mut replaced)));
            }
            let renamed = match with_members(node, &pairs) {
                Node::Exists(m, w, p) => {
                    Node::Exists(m, self.substituted_term(w, sigma, &mut replaced), p)
                }
                Node::Forall(m, a, p) => match sigma.get(&a) {
                    Some(&term) => {
                        let FoTerm::Eigen(b) = self.term(term) else {
                            unreachable!("a `∀` step's eigenvariable is renamed to one")
                        };
                        Node::Forall(m, b, p)
                    }
                    None => Node::Forall(m, a, p),
                },
                node => node,
            };
            let renamed = renamed.map_premises(|p| made.get(&p).copied().unwrap_or(p));
            let new = self.push(renamed);
            made.insert(NodeId::new(id as u32), new);
        }
        Ok(made.get(&top).copied().unwrap_or(top))
    }

    /// Refuses `more` nodes added to the arena past a step's bounds. The
    /// arena (the proof's nodes and those the step made) may hold at most
    /// `most` nodes, and at most `memory` bytes at sixteen a node.
    ///
    /// The proof made has at most the arena's nodes, so a step within the
    /// bound makes a proof within it. The check is conservative: a step
    /// whose copies replace subproofs it no longer reads may be refused
    /// though the proof it would make is smaller.
    pub(super) fn afford(&self, more: usize) -> Result<(), Refusal> {
        self.within_ids()?;
        if self.nodes.len().saturating_add(more) > self.most {
            return Err(Refusal::Elimination {
                what: crate::limits::Bound::Nodes,
                limit: self.most as u64,
            });
        }
        let bytes =
            (self.nodes.len().saturating_add(more) as u64).saturating_mul(size_of::<Node>() as u64);
        match self.memory {
            Some(limit) if bytes > limit => Err(Refusal::Memory {
                phase: Phase::Eliminate,
                limit_bytes: limit,
                needed_bytes: Some(bytes),
            }),
            _ => Ok(()),
        }
    }

    /// Returns whether the frame of `m` names an eigenvariable `sigma`
    /// maps.
    fn names_member(&self, m: Member, sigma: &HashMap<Eigen, FoTermId>, named: &mut Named) -> bool {
        let table = self.table.as_ref().expect("a proof with instances");
        let Some((_, frame)) = table.instances.instance(m) else {
            return false;
        };
        let mut chain = Vec::new();
        let mut next = Some(frame);
        let mut found = false;
        while let Some(f) = next {
            if let Some(&known) = named.frames.get(&f) {
                found = known;
                break;
            }
            chain.push(f);
            next = table.instances.frame_parts(f).0;
        }
        for f in chain.into_iter().rev() {
            found = found || self.names_term(table.instances.frame_parts(f).1, sigma, named);
            named.frames.insert(f, found);
        }
        found
    }

    /// Returns whether the term `id` names an eigenvariable `sigma` maps,
    /// by a walk with a stack of its own.
    fn names_term(
        &self,
        id: FoTermId,
        sigma: &HashMap<Eigen, FoTermId>,
        named: &mut Named,
    ) -> bool {
        let table = self.table.as_ref().expect("a proof with instances");
        let terms = table.terms(self.proof);
        let base = table.instances.base_terms as usize;
        let mut walk = vec![(id, false)];
        while let Some((t, expanded)) = walk.pop() {
            if t.index() < base || named.terms.contains_key(&t) {
                continue;
            }
            let found = match terms.term(t) {
                FoTerm::Eigen(a) => sigma.contains_key(&a),
                FoTerm::App(_, args) => {
                    let list = terms.list(args);
                    if !expanded {
                        walk.push((t, true));
                        walk.extend(list.iter().map(|&a| (a, false)));
                        continue;
                    }
                    list.iter()
                        .any(|a| named.terms.get(a).copied().unwrap_or(false))
                }
                FoTerm::Bound(_) | FoTerm::Meta(_) => false,
            };
            named.terms.insert(t, found);
        }
        named.terms.get(&id).copied().unwrap_or(false)
    }

    /// Returns the term `id` of the sequent or the table.
    fn term(&self, id: FoTermId) -> FoTerm {
        let table = self.table.as_ref().expect("a proof with instances");
        table.terms(self.proof).term(id)
    }

    /// Returns `m` with `sigma` applied to its frame.
    fn substituted_member(
        &mut self,
        m: Member,
        sigma: &HashMap<Eigen, FoTermId>,
        replaced: &mut Replaced,
    ) -> Member {
        if let Some(&done) = replaced.members.get(&m) {
            return done;
        }
        let (o, frame) = self.table().resolve(m);
        let made = match frame {
            None => m,
            Some(frame) => {
                let new = self.substituted_frame(frame, sigma, replaced);
                if new == frame {
                    m
                } else {
                    self.table().member(o, Some(new))
                }
            }
        };
        replaced.members.insert(m, made);
        made
    }

    /// Returns `frame` with `sigma` applied to its terms: the cells up to
    /// the first one replaced before, then made downwards.
    fn substituted_frame(
        &mut self,
        frame: FrameId,
        sigma: &HashMap<Eigen, FoTermId>,
        replaced: &mut Replaced,
    ) -> FrameId {
        let mut chain = Vec::new();
        let mut next = Some(frame);
        let mut below: Option<FrameId> = None;
        while let Some(f) = next {
            if let Some(&done) = replaced.frames.get(&f) {
                below = Some(done);
                break;
            }
            chain.push(f);
            next = self.table().instances.frame_parts(f).0;
        }
        for f in chain.into_iter().rev() {
            let (parent, term) = self.table().instances.frame_parts(f);
            let term_made = self.substituted_term(term, sigma, replaced);
            let made = if below == parent && term_made == term {
                f
            } else {
                self.table().frame(below, term_made)
            };
            replaced.frames.insert(f, made);
            below = Some(made);
        }
        below.expect("a frame holds a term")
    }

    /// Returns the term `id` with `sigma` applied, by a walk with a stack
    /// of its own, since a witness may be nested as deep as a search's
    /// bindings went. The sequent's own terms name no eigenvariable.
    fn substituted_term(
        &mut self,
        id: FoTermId,
        sigma: &HashMap<Eigen, FoTermId>,
        replaced: &mut Replaced,
    ) -> FoTermId {
        let base = self.table().instances.base_terms as usize;
        let mut walk = vec![(id, false)];
        while let Some((t, expanded)) = walk.pop() {
            if t.index() < base || replaced.terms.contains_key(&t) {
                continue;
            }
            let made = match self.term(t) {
                FoTerm::Eigen(a) => sigma.get(&a).copied().unwrap_or(t),
                FoTerm::App(f, args) => {
                    let table = self.table.as_ref().expect("a proof with instances");
                    let list: Vec<FoTermId> = table.terms(self.proof).list(args).to_vec();
                    if !expanded {
                        walk.push((t, true));
                        walk.extend(list.iter().map(|&a| (a, false)));
                        continue;
                    }
                    let args: Vec<FoTermId> = list
                        .iter()
                        .map(|a| replaced.terms.get(a).copied().unwrap_or(*a))
                        .collect();
                    if args == list {
                        t
                    } else {
                        self.table().instances.apply(f, &args)
                    }
                }
                FoTerm::Bound(_) | FoTerm::Meta(_) => t,
            };
            replaced.terms.insert(t, made);
        }
        replaced.terms.get(&id).copied().unwrap_or(id)
    }

    /// Gives every eigenvariable that two `∀` steps of the proof at `root`
    /// introduce a step of its own, and returns the root.
    ///
    /// A step remakes a `∀` step held by a subproof it changes, while the
    /// proof may still read the original elsewhere. Each round takes the
    /// first such pair of twins in arena order. It makes the later one
    /// anew (or the earlier, where it lies above the later) with a fresh
    /// eigenvariable throughout its subproof, and so every `∀` step of
    /// that subproof that the proof still reads elsewhere.
    ///
    /// A round takes one introduction away from an eigenvariable that two
    /// steps introduce and adds none, so the rounds end. Every node a
    /// round makes is charged before it is made
    /// ([`afford`](Self::afford)), and `stop` is asked each round.
    pub(super) fn apart(
        &mut self,
        mut root: NodeId,
        stop: &mut dyn FnMut(Progress) -> bool,
    ) -> Result<NodeId, Refusal> {
        let mut rounds: u64 = 0;
        loop {
            let reach = reached(&self.nodes, root, None);
            let mut first: HashMap<Eigen, NodeId> = HashMap::default();
            let mut twins = None;
            for (i, _) in reach.iter().enumerate().filter(|&(_, &r)| r) {
                if let Node::Forall(_, a, _) = self.nodes[i] {
                    let id = NodeId::new(i as u32);
                    if let Some(&earlier) = first.get(&a) {
                        twins = Some((earlier, id));
                        break;
                    }
                    first.insert(a, id);
                }
            }
            let Some((earlier, later)) = twins else {
                return Ok(root);
            };
            rounds += 1;
            if stop(Progress::new(Phase::Eliminate, 1, rounds)) {
                return Err(Refusal::Stopped {
                    phase: Phase::Eliminate,
                });
            }
            let Node::Forall(_, _, premise) = self.nodes[later.index()] else {
                unreachable!("a twin is a `∀` step")
            };
            let renamed = if reached(&self.nodes, premise, None)[earlier.index()] {
                earlier
            } else {
                later
            };
            let Node::Forall(m, a, premise) = self.nodes[renamed.index()] else {
                unreachable!("a twin is a `∀` step")
            };
            // A `∀` step above that the proof also reads other than through
            // the one renamed keeps its eigenvariable there, so its copy
            // takes a fresh one.
            let elsewhere = reached(&self.nodes, root, Some(renamed));
            let above = reached(&self.nodes, premise, None);
            let mut sigma: HashMap<Eigen, FoTermId> = HashMap::default();
            let fresh = self.table().fresh()?;
            let fresh_term = self.table().eigen(fresh);
            sigma.insert(a, fresh_term);
            for (i, _) in above.iter().enumerate().filter(|&(_, &r)| r) {
                if let Node::Forall(_, b, _) = self.nodes[i]
                    && elsewhere[i]
                {
                    let fresh = self.table().fresh()?;
                    let term = self.table().eigen(fresh);
                    sigma.insert(b, term);
                }
            }
            let premise = self.substitute(premise, &sigma)?;
            // The step renamed, and every node below it that reaches it.
            let mut below = vec![false; root.index() + 1];
            below[renamed.index()] = true;
            for i in renamed.index() + 1..=root.index() {
                below[i] = self.nodes[i].premises().any(|p| below[p.index()]);
            }
            self.afford(below.iter().filter(|&&b| b).count())?;
            let made = self.push(Node::Forall(m, fresh, premise));
            root = self.replace(renamed, made, root);
        }
    }

    /// Returns a table that holds only what the nodes `root` reaches name,
    /// with those nodes' members and witnesses renumbered into it. A
    /// step's table extends the proof's, so without this what the step left
    /// unread would pile up across the steps.
    pub(super) fn compact(&mut self, root: NodeId) -> Instances {
        let table = self.table.as_ref().expect("a proof with instances");
        let mut copy = Transfer {
            terms: table.terms(self.proof),
            table,
            out: Instances::new(self.forest),
            term_at: HashMap::default(),
            frame_at: HashMap::default(),
            member_at: HashMap::default(),
        };
        let reach = reached(&self.nodes, root, None);
        for (i, _) in reach.iter().enumerate().filter(|&(_, &r)| r) {
            let node = self.nodes[i];
            let pairs = node.members().map(|m| (m, copy.member(m)));
            let pairs: Vec<(Member, Member)> = pairs.collect();
            let node = with_members(node, &pairs);
            self.nodes[i] = match node {
                Node::Exists(m, w, p) => Node::Exists(m, copy.term(w), p),
                node => node,
            };
        }
        copy.out
    }
}

/// Returns `node` with each member it names replaced by its pair's second
/// member.
fn with_members(node: Node, pairs: &[(Member, Member)]) -> Node {
    node.renamed(|m| {
        Ok::<_, std::convert::Infallible>(
            pairs
                .iter()
                .find(|&&(from, _)| from == m)
                .map_or(m, |&(_, to)| to),
        )
    })
    .unwrap_or_else(|never| match never {})
}

/// Returns, for every node of `nodes` up to `top`, whether `top` reaches
/// it, not passing beyond `avoid` where one is given.
fn reached(nodes: &[Node], top: NodeId, avoid: Option<NodeId>) -> Vec<bool> {
    let mut reached = vec![false; top.index() + 1];
    reached[top.index()] = true;
    for i in (0..=top.index()).rev() {
        if reached[i] && Some(NodeId::new(i as u32)) != avoid {
            for p in nodes[i].premises() {
                reached[p.index()] = true;
            }
        }
    }
    reached
}

/// The copy of what a proof's nodes name into a table of their own.
struct Transfer<'t> {
    /// The terms of the table copied from, with the sequent's.
    terms: Terms<'t>,
    /// The table copied from.
    table: &'t Table,
    /// The table made.
    out: Instances,
    /// Each term copied, by its id before.
    term_at: HashMap<FoTermId, FoTermId>,
    /// Each frame copied.
    frame_at: HashMap<FrameId, FrameId>,
    /// Each member copied.
    member_at: HashMap<Member, Member>,
}

impl Transfer<'_> {
    /// Returns the id in the table made of the term `id`, by a walk with a
    /// stack of its own; the sequent's terms keep their ids.
    fn term(&mut self, id: FoTermId) -> FoTermId {
        let base = self.out.base_terms as usize;
        let mut walk = vec![(id, false)];
        while let Some((t, expanded)) = walk.pop() {
            if t.index() < base || self.term_at.contains_key(&t) {
                continue;
            }
            let made = match self.terms.term(t) {
                FoTerm::App(f, args) => {
                    let list = self.terms.list(args);
                    if !expanded {
                        walk.push((t, true));
                        walk.extend(list.iter().map(|&a| (a, false)));
                        continue;
                    }
                    let args: Vec<FoTermId> = list
                        .iter()
                        .map(|a| self.term_at.get(a).copied().unwrap_or(*a))
                        .collect();
                    self.out.apply(f, &args)
                }
                term @ (FoTerm::Eigen(_) | FoTerm::Bound(_) | FoTerm::Meta(_)) => {
                    self.out.push_term(term)
                }
            };
            self.term_at.insert(t, made);
        }
        self.term_at.get(&id).copied().unwrap_or(id)
    }

    /// Returns the frame of the table made for `frame`: the cells up to
    /// the first copied before, then made downwards.
    fn frame(&mut self, frame: FrameId) -> FrameId {
        let mut chain = Vec::new();
        let mut next = Some(frame);
        let mut below = None;
        while let Some(f) = next {
            if let Some(&done) = self.frame_at.get(&f) {
                below = Some(done);
                break;
            }
            chain.push(f);
            next = self.table.instances.frame_parts(f).0;
        }
        for f in chain.into_iter().rev() {
            let term = self.term(self.table.instances.frame_parts(f).1);
            let made = self.out.frame(below, term);
            self.frame_at.insert(f, made);
            below = Some(made);
        }
        below.expect("a frame holds a term")
    }

    /// Returns the member of the table made for `m`.
    fn member(&mut self, m: Member) -> Member {
        let (o, Some(frame)) = self.table.resolve(m) else {
            return m;
        };
        if let Some(&done) = self.member_at.get(&m) {
            return done;
        }
        let frame = self.frame(frame);
        let made = self.out.member(o, frame);
        self.member_at.insert(m, made);
        made
    }
}