deduxit 0.4.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
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! The derived rules of the forward search, compiled from the forest
//! before the search starts.
//!
//! A focused proof alternates two kinds of phases. A focus decomposes one
//! positive formula (`⊗`, `1`, `⊕`, `0`, `!` and the literals the bias
//! makes positive) as far as it stays positive. It then releases what is
//! left to an asynchronous phase, which decomposes the negative formulas
//! by invertible rules until the sequent is stable (no invertible rule
//! applies).
//!
//! A derived rule is the proof term of one focus and the asynchronous
//! phases of what it releases, read forward. There is one rule per
//! formula a focus can begin on and per choice of the `⊕` sides under it.
//! Its steps are in postorder. A hole is where a premise goes, a stable
//! sequent derived before. A slot is where an axiom's partner, a negative
//! literal, is chosen. The goal is compiled the same way into its own
//! asynchronous phase, whose holes the search fills.

use super::super::Reason;
use super::super::memory::{Charged, bytes_of};
use crate::hash::HashMap;
use crate::linear::occurrences::{Forest, OccId, Reading, Side};
use crate::linear::proofs::Branch;
use crate::linear::sequents::Kind;
use std::ops::Range;

/// A step of a rule's term, in postorder. A step's operands are the
/// results of the steps before it, as on a stack.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Step {
    /// `⊢ p, x`: the axiom on the positive literal and the partner chosen
    /// for the slot.
    Axiom(OccId, u32),
    /// `⊢ 1`.
    One(OccId),
    /// `⊢ ⊤` with any context.
    Top(OccId),
    /// The premise put into the hole.
    Hole(u32),
    /// `⊗` on its two operands.
    Tensor(OccId),
    /// `⊕` on the operand, its side as given.
    Plus(OccId, Branch),
    /// `!` on its operand, which must have nothing else.
    Bang(OccId),
    /// `⅋` on its operand.
    Par(OccId),
    /// `⊥` on its operand.
    Bot(OccId),
    /// `&` on its two operands.
    With(OccId),
    /// `?`: the subformula leaves the unrestricted zone.
    Quest(OccId),
    /// A copy of the formula into the unrestricted zone.
    Copy(OccId),
}

/// The partner of a positive literal in an axiom: a negative literal of
/// the same atom. It is in the linear zone, or in the unrestricted one
/// when it is the subformula of a `?` (a copy above the axiom).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Partner {
    /// The negative literal.
    pub(super) x: OccId,
    /// Whether it comes from the unrestricted zone.
    pub(super) theta: bool,
}

/// A rule: its ranges of the steps, holes and slots of [`Rules`].
#[derive(Clone, Debug)]
pub(super) struct Rule {
    /// Its steps.
    pub(super) steps: Range<u32>,
    /// Its holes, in the order their steps come.
    pub(super) holes: Range<u32>,
    /// Its slots, in the order their steps come.
    pub(super) slots: Range<u32>,
}

/// A hole of a rule, where a premise goes.
///
/// It lists the occurrences the term takes from the premise put there,
/// which the premise must hold unless it may absorb or weaken them. It
/// also lists the subformulas of the `?` the phase met before it, which
/// the premise's unrestricted zone may hold.
#[derive(Clone, Debug)]
pub(super) struct Hole {
    /// The rule it belongs to.
    pub(super) rule: u32,
    /// Its place among the rule's holes.
    pub(super) index: u32,
    /// The release of the rule it belongs to. The holes of one release
    /// share their context, and the contexts of different releases are
    /// joined side by side.
    pub(super) group: u32,
    /// The range of its members in [`Rules::leaves`], sorted.
    pub(super) leaves: Range<u32>,
    /// The range of the subformulas of `?` in [`Rules::leaves`], sorted.
    pub(super) theta: Range<u32>,
}

/// Every rule of the search, or the goal's phase: one rule whose holes
/// are the goal's stable sequents.
#[derive(Debug, Default)]
pub(super) struct Rules {
    /// The rules.
    pub(super) all: Vec<Rule>,
    /// Every rule's steps.
    pub(super) steps: Vec<Step>,
    /// Every rule's holes.
    pub(super) holes: Vec<Hole>,
    /// The members of the holes, each hole's range sorted.
    pub(super) leaves: Vec<OccId>,
    /// Every rule's slots, each a range of [`Rules::partners`].
    pub(super) slots: Vec<Range<u32>>,
    /// The partners of the slots.
    pub(super) partners: Vec<Partner>,
    /// The range of [`Rules::partners`] each positive literal takes under
    /// a focus on a formula. Every rule with that focus shares it.
    lists: HashMap<(OccId, OccId), Range<u32>>,
    /// The holes by their first member.
    pub(super) by_leaf: HashMap<OccId, Vec<u32>>,
    /// The holes that take no member.
    pub(super) open: Vec<u32>,
}

/// What a forest's occurrences are to the search: their polarity under
/// the bias, the subformulas of `?` that the goal's asynchronous phase
/// puts into the unrestricted zone on every branch, and the reading.
pub(super) struct Shape<'a> {
    /// The forest.
    pub(super) forest: &'a Forest,
    /// The sign of each atom's positive literal.
    signs: Box<[crate::linear::occurrences::Sign]>,
    /// The intuitionistic reading, in intuitionistic mode.
    pub(super) reading: Option<&'a Reading<'a>>,
    /// Whether weakening is allowed.
    pub(super) affine: bool,
    /// The members of the goal, sorted.
    pub(super) goal: Vec<OccId>,
    /// The subformulas of the `?` that the goal reaches through `⅋` alone,
    /// sorted. They are in the unrestricted zone of every sequent of a
    /// proof.
    pub(super) globals: Vec<OccId>,
}

impl<'a> Shape<'a> {
    /// Returns the shape of a goal of the forest under the atoms' signs.
    pub(super) fn new(
        forest: &'a Forest,
        goal: &[OccId],
        signs: Box<[crate::linear::occurrences::Sign]>,
        reading: Option<&'a Reading<'a>>,
        affine: bool,
    ) -> Self {
        let mut members = goal.to_vec();
        members.sort_unstable();
        let mut globals = Vec::new();
        let mut walk = members.clone();
        while let Some(o) = walk.pop() {
            match forest.kind(o) {
                Kind::Par => walk.extend(forest.children(o)),
                Kind::Quest => globals.extend(forest.left(o)),
                _ => {}
            }
        }
        globals.sort_unstable();
        globals.dedup();
        Self {
            forest,
            signs,
            reading,
            affine,
            goal: members,
            globals,
        }
    }

    /// Whether an occurrence is positive: `⊗ 1 ⊕ 0 !` (and `∃`), and the
    /// literals the bias makes positive.
    pub(super) fn positive(&self, o: OccId) -> bool {
        match self.forest.kind(o) {
            Kind::Tensor | Kind::One | Kind::Plus | Kind::Zero | Kind::Bang | Kind::Exists => true,
            Kind::Atom | Kind::DualAtom => {
                let atom = self.forest.atom(o).expect("a literal has an atom");
                self.forest.sign(o) == Some(self.signs[atom.index()])
            }
            Kind::Par | Kind::Bot | Kind::With | Kind::Top | Kind::Quest | Kind::Forall => false,
        }
    }

    /// Whether an occurrence stays in a stable sequent's linear zone when
    /// an asynchronous phase meets it: a positive formula or a negative
    /// literal.
    fn stable(&self, o: OccId) -> bool {
        self.positive(o) || self.forest.is_literal(o)
    }

    /// Whether two occurrences can stand in one sequent of a proof of the
    /// goal, the goal's own members among them ([`coherent`]).
    pub(super) fn coherent(&self, x: OccId, y: OccId) -> bool {
        coherent(self.forest, x, y)
    }

    /// Whether an occurrence is in output position under the reading.
    pub(super) fn output(&self, o: OccId) -> bool {
        self.reading.is_some_and(|r| r.position(o) == Side::Output)
    }
}

/// Whether an occurrence lies inside the subformula of a `?`, whose copies
/// can repeat it.
fn copied(forest: &Forest, o: OccId) -> bool {
    let mut a = o;
    while let Some(p) = forest.parent(a) {
        if forest.kind(p) == Kind::Quest {
            return true;
        }
        a = p;
    }
    false
}

/// Whether two occurrences can stand in one sequent of a proof of a goal
/// whose own members can.
///
/// Outside the subformulas of `?`, nothing is repeated. There two members
/// of one sequent are distinct, and neither lies below the other. The
/// connective that joins them is a `⅋`, which a rule decomposed below
/// them. A `⊗`, `&` or `⊕` above both would send them to different
/// premises or keep only one side.
///
/// Two occurrences joined by a `?` formula are let through: the formula
/// twice, or the formula beside a member of its subformula, as in a goal
/// after a contraction and a dereliction. No stable sequent holds a `?`
/// formula, since a goal's phase decomposes it first, and everything below
/// its subformula may repeat.
///
/// A goal of the sequent's roots has coherent members, and so does every
/// goal of a derivation of them.
pub(super) fn coherent(forest: &Forest, x: OccId, y: OccId) -> bool {
    let Some(w) = forest.lca(x, y) else {
        return true;
    };
    if forest.kind(w) == Kind::Quest || copied(forest, w) {
        return true;
    }
    w != x && w != y && forest.kind(w) == Kind::Par
}

/// Whether every two members of a list sorted in the forest's order can
/// stand in one sequent of a proof.
///
/// It tests the neighbours only: in a list sorted in preorder, the common
/// ancestors of any two members are those of some two neighbours.
pub(super) fn coherent_list(forest: &Forest, sorted: &[OccId]) -> bool {
    sorted.windows(2).all(|w| coherent(forest, w[0], w[1]))
}

/// A subtree of a rule's term still to be written.
enum Pending {
    /// The focus on a positive formula.
    Focus(OccId),
    /// An asynchronous phase.
    Async(Phase),
    /// A copy of the subformula of a `?` and the phase it begins.
    Copy(OccId),
}

/// The state of an asynchronous phase: the negative formulas left to
/// decompose, the stable members met, and the subformulas of `?` moved
/// into the unrestricted zone.
#[derive(Clone, Default)]
struct Phase {
    /// A `⊤` met, which closes the phase.
    top: Option<OccId>,
    /// The `⅋`, `⊥` and `?` left.
    unary: Vec<OccId>,
    /// The `&` left, decomposed last.
    withs: Vec<OccId>,
    /// The stable members met.
    leaves: Vec<OccId>,
    /// The subformulas of `?` met.
    theta: Vec<OccId>,
    /// The release the phase belongs to, among the rule's. The premises of
    /// one release share their context.
    group: u32,
}

impl Phase {
    /// Returns the bytes its lists hold.
    fn bytes(&self) -> usize {
        bytes_of(&self.unary)
            + bytes_of(&self.withs)
            + bytes_of(&self.leaves)
            + bytes_of(&self.theta)
    }

    /// Places an occurrence the phase meets.
    fn place(&mut self, shape: &Shape<'_>, o: OccId) {
        if shape.stable(o) {
            self.leaves.push(o);
            return;
        }
        match shape.forest.kind(o) {
            Kind::Top => {
                self.top.get_or_insert(o);
            }
            Kind::With => self.withs.push(o),
            _ => self.unary.push(o),
        }
    }
}

/// Writes rules into a [`Rules`], charging what it allocates.
struct Writer<'s, 'a, 'c> {
    /// The shape of the goal.
    shape: &'s Shape<'a>,
    /// The rules written.
    rules: Rules,
    /// The steps of the rule being written, in reverse.
    reversed: Vec<Step>,
    /// Its holes, in reverse, as their members, `?` subformulas and
    /// release.
    holes: Vec<(Vec<OccId>, Vec<OccId>, u32)>,
    /// Its slots, in reverse, as the positive literal and the root.
    slots: Vec<(OccId, OccId)>,
    /// The charge for what is allocated. It holds the rules' tables as
    /// long as the search runs.
    charged: &'s mut Charged<'c>,
    /// The bytes charged for the rules' tables.
    held: usize,
    /// The steps written since the last poll.
    unpolled: u64,
    /// The releases of the rule being written.
    groups: u32,
    /// The bytes the rule being written holds beside its steps: its
    /// holes' lists and the phases waiting on the stack.
    pending: usize,
    /// The bytes of the lists in [`Rules::by_leaf`]. The table's own
    /// capacity does not count them.
    inner: usize,
}

/// How many steps of the rules are written between two polls of the stop,
/// each a unit of work.
const STEPS_PER_POLL: u64 = 1 << 12;

impl<'s, 'a, 'c> Writer<'s, 'a, 'c> {
    /// Charges the tables' growth. Fails with the memory limit when the
    /// account is over its bound.
    fn settle(&mut self) -> Result<(), Reason> {
        let r = &self.rules;
        let held = bytes_of(&r.all)
            + bytes_of(&r.steps)
            + bytes_of(&r.holes)
            + bytes_of(&r.leaves)
            + bytes_of(&r.slots)
            + bytes_of(&r.partners)
            + r.by_leaf.capacity() * (size_of::<(OccId, Vec<u32>)>() + 1)
            + r.lists.capacity() * (size_of::<((OccId, OccId), Range<u32>)>() + 1)
            + bytes_of(&r.open)
            + bytes_of(&self.reversed)
            + bytes_of(&self.holes)
            + self.pending
            + self.inner;
        self.charged.resize(self.held, held);
        self.held = held;
        if self.charged.account().over() {
            return Err(Reason::MemoryLimit {
                limit_bytes: self.charged.account().limit(),
            });
        }
        Ok(())
    }

    /// Counts a step written. Every [`STEPS_PER_POLL`] steps, it charges
    /// the tables and what the rule being written holds, and polls the
    /// stop with the steps as work.
    fn tick(&mut self, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
        self.tick_by(1, stop)
    }

    /// Counts `units` of work (steps written, literals scanned for
    /// partners, members copied into the tables), charging and polling as
    /// [`Writer::tick`] does.
    fn tick_by(&mut self, units: u64, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
        self.unpolled += units;
        if self.unpolled < STEPS_PER_POLL {
            return Ok(());
        }
        self.settle()?;
        if stop(std::mem::take(&mut self.unpolled)) {
            return Err(Reason::Stopped);
        }
        Ok(())
    }

    /// Writes the term below `root` under the choice of `⊕` sides given,
    /// and records it as a rule unless a slot has no partner.
    ///
    /// `anchor` is the formula the focus began on. An axiom's partner must
    /// be able to stand beside it.
    fn write(
        &mut self,
        root: Pending,
        sides: &[(OccId, Branch)],
        anchor: OccId,
        stop: &mut dyn FnMut(u64) -> bool,
    ) -> Result<(), Reason> {
        let forest = self.shape.forest;
        self.reversed.clear();
        self.holes.clear();
        self.slots.clear();
        self.pending = 0;
        self.groups = 0;
        let mut stack = Vec::new();
        self.push(&mut stack, root);
        while let Some(pending) = stack.pop() {
            self.tick(stop)?;
            match pending {
                Pending::Copy(o) => {
                    self.reversed.push(Step::Copy(o));
                    let next = self.under_focus(o);
                    self.push(&mut stack, next);
                }
                Pending::Focus(o) => match forest.kind(o) {
                    Kind::Tensor => {
                        self.reversed.push(Step::Tensor(o));
                        let (l, r) = (forest.left(o).expect("⊗"), forest.right(o).expect("⊗"));
                        // The steps are written in reversed postorder, so
                        // the right operand comes first.
                        let (l, r) = (self.under_focus(l), self.under_focus(r));
                        self.push(&mut stack, l);
                        self.push(&mut stack, r);
                    }
                    Kind::Plus => {
                        let side = sides
                            .iter()
                            .find(|&&(p, _)| p == o)
                            .map(|&(_, side)| side)
                            .expect("every ⊕ under the focus has a side");
                        self.reversed.push(Step::Plus(o, side));
                        let child = match side {
                            Branch::Left => forest.left(o),
                            Branch::Right => forest.right(o),
                        }
                        .expect("⊕");
                        let next = self.under_focus(child);
                        self.push(&mut stack, next);
                    }
                    Kind::One => self.reversed.push(Step::One(o)),
                    Kind::Bang => {
                        self.reversed.push(Step::Bang(o));
                        let mut phase = self.release();
                        phase.place(self.shape, forest.left(o).expect("!"));
                        self.push(&mut stack, Pending::Async(phase));
                    }
                    Kind::Atom | Kind::DualAtom => {
                        let slot = self.slots.len() as u32;
                        self.slots.push((o, anchor));
                        self.reversed.push(Step::Axiom(o, slot));
                    }
                    Kind::Zero
                    | Kind::Par
                    | Kind::Bot
                    | Kind::With
                    | Kind::Top
                    | Kind::Quest
                    | Kind::Forall
                    | Kind::Exists => {
                        unreachable!("a plan never focuses on a 0, a negative formula or a binder")
                    }
                },
                Pending::Async(mut phase) => {
                    self.pending -= phase.bytes();
                    loop {
                        if let Some(t) = phase.top {
                            self.reversed.push(Step::Top(t));
                            break;
                        }
                        if let Some(o) = phase.unary.pop() {
                            match forest.kind(o) {
                                Kind::Par => {
                                    self.reversed.push(Step::Par(o));
                                    for c in forest.children(o) {
                                        phase.place(self.shape, c);
                                    }
                                }
                                Kind::Bot => self.reversed.push(Step::Bot(o)),
                                Kind::Quest => {
                                    self.reversed.push(Step::Quest(o));
                                    phase.theta.push(forest.left(o).expect("?"));
                                }
                                _ => unreachable!("only ⅋, ⊥ and ? are unary in a phase"),
                            }
                            self.tick(stop)?;
                            continue;
                        }
                        if let Some(o) = phase.withs.pop() {
                            self.reversed.push(Step::With(o));
                            let mut left = phase.clone();
                            left.place(self.shape, forest.left(o).expect("&"));
                            phase.place(self.shape, forest.right(o).expect("&"));
                            // In reversed postorder the right premise comes
                            // first, and the left one after everything the
                            // right one pushes.
                            self.push(&mut stack, Pending::Async(left));
                            self.tick(stop)?;
                            continue;
                        }
                        let index = self.holes.len() as u32;
                        phase.leaves.sort_unstable();
                        phase.theta.sort_unstable();
                        self.pending += bytes_of(&phase.leaves) + bytes_of(&phase.theta);
                        self.holes.push((phase.leaves, phase.theta, phase.group));
                        self.reversed.push(Step::Hole(index));
                        break;
                    }
                }
            }
        }
        self.record(stop)?;
        self.settle()
    }

    /// Pushes a subtree to write. The lists of a phase count among what
    /// the rule being written holds until it is popped.
    fn push(&mut self, stack: &mut Vec<Pending>, pending: Pending) {
        if let Pending::Async(phase) = &pending {
            self.pending += phase.bytes();
        }
        stack.push(pending);
    }

    /// Returns a new phase of a release of its own.
    fn release(&mut self) -> Phase {
        // A rule of 2³² releases has as many steps, and `record` refuses
        // it before the numbers are read.
        self.groups = self.groups.wrapping_add(1);
        Phase {
            group: self.groups.wrapping_sub(1),
            ..Phase::default()
        }
    }

    /// Returns the subtree of an operand of a positive connective under
    /// focus. The focus goes on into a positive operand, and a negative
    /// one is released.
    fn under_focus(&mut self, o: OccId) -> Pending {
        if self.shape.positive(o) {
            Pending::Focus(o)
        } else {
            let mut phase = self.release();
            phase.place(self.shape, o);
            Pending::Async(phase)
        }
    }

    /// Records the rule written, numbering its holes and slots in the
    /// order of its steps, unless a slot has no partner.
    ///
    /// Fails with [`Reason::IndexLimit`] for a rule that takes a table past
    /// what a `u32` indexes, which only a search without a memory bound
    /// reaches.
    fn record(&mut self, stop: &mut dyn FnMut(u64) -> bool) -> Result<(), Reason> {
        let base_slot = self.rules.slots.len();
        // The slots in step order, the reverse of the written order. Rules
        // that focus on the same formula under other `⊕` sides share their
        // literals' lists.
        let slots = std::mem::take(&mut self.slots);
        for &(p, anchor) in slots.iter().rev() {
            let range = match self.rules.lists.get(&(p, anchor)) {
                Some(range) => range.clone(),
                None => {
                    let start = self.rules.partners.len() as u32;
                    let (found, scanned) = partners(self.shape, p, anchor);
                    self.rules.partners.extend(found);
                    let range = start..self.rules.partners.len() as u32;
                    self.rules.lists.insert((p, anchor), range.clone());
                    self.tick_by(scanned, stop)?;
                    range
                }
            };
            if range.is_empty() {
                self.rules.slots.truncate(base_slot);
                self.holes.clear();
                self.pending = 0;
                return Ok(());
            }
            self.rules.slots.push(range);
        }
        let rule = self.rules.all.len() as u32;
        let (holes, slots) = (self.holes.len() as u32, slots.len() as u32);
        let hole_base = self.rules.holes.len() as u32;
        // The holes leave the rule being written as they are copied into
        // the tables, which are charged and polled as they grow. The goal's
        // phase can hold tens of millions of members.
        let written = std::mem::take(&mut self.holes);
        self.pending += bytes_of(&written);
        for (index, (leaves, theta, group)) in written.into_iter().rev().enumerate() {
            let start = self.rules.leaves.len() as u32;
            self.rules.leaves.extend_from_slice(&leaves);
            let mid = self.rules.leaves.len() as u32;
            self.rules.leaves.extend_from_slice(&theta);
            let end = self.rules.leaves.len() as u32;
            let global = self.rules.holes.len() as u32;
            match leaves.first() {
                Some(&first) => {
                    let list = self.rules.by_leaf.entry(first).or_default();
                    let before = bytes_of(list);
                    list.push(global);
                    self.inner += bytes_of(list) - before;
                }
                None => self.rules.open.push(global),
            }
            self.rules.holes.push(Hole {
                rule,
                index: index as u32,
                group,
                leaves: start..mid,
                theta: mid..end,
            });
            self.pending -= bytes_of(&leaves) + bytes_of(&theta);
            self.tick_by(1 + (leaves.len() + theta.len()) as u64, stop)?;
        }
        self.pending = 0;
        let step_base = self.rules.steps.len() as u32;
        for i in (0..self.reversed.len()).rev() {
            let step = self.reversed[i];
            self.rules.steps.push(match step {
                Step::Hole(h) => Step::Hole(holes - 1 - h),
                Step::Axiom(p, s) => Step::Axiom(p, slots - 1 - s),
                step => step,
            });
            self.tick(stop)?;
        }
        self.rules.all.push(Rule {
            steps: step_base..self.rules.steps.len() as u32,
            holes: hole_base..hole_base + holes,
            slots: base_slot as u32..base_slot as u32 + slots,
        });
        // Every index into the tables is a `u32`, and every range over them
        // was taken from their lengths. A table past `u32::MAX` would make
        // them wrap, so the rule that takes one there is refused before any
        // is read.
        let most = u32::MAX as usize;
        let r = &self.rules;
        if [
            r.all.len(),
            r.steps.len(),
            r.holes.len(),
            r.leaves.len(),
            r.slots.len(),
            r.partners.len(),
        ]
        .into_iter()
        .any(|len| len > most)
        {
            return Err(Reason::IndexLimit);
        }
        Ok(())
    }
}

/// Returns the partners a positive literal under focus may take, and the
/// literals scanned, as work.
///
/// The partners are the negative literals of its atom that can stand
/// beside the formula the focus began on, of the opposite position under
/// a reading. One that is the subformula of a `?` comes from the
/// unrestricted zone, and from the linear zone too where the goal holds
/// it.
fn partners(shape: &Shape<'_>, p: OccId, anchor: OccId) -> (Vec<Partner>, u64) {
    let forest = shape.forest;
    let (atom, sign) = (
        forest.atom(p).expect("a literal"),
        forest.sign(p).expect("a literal"),
    );
    let mut found = Vec::new();
    for &x in forest.literals(atom, !sign) {
        if shape.reading.is_some() && shape.output(x) == shape.output(p) {
            continue;
        }
        if !shape.coherent(anchor, x) {
            continue;
        }
        let quest = forest
            .parent(x)
            .is_some_and(|q| forest.kind(q) == Kind::Quest);
        if quest {
            found.push(Partner { x, theta: true });
        }
        if !quest || shape.goal.binary_search(&x).is_ok() {
            found.push(Partner { x, theta: false });
        }
    }
    (found, forest.literals(atom, !sign).len() as u64)
}

/// Calls `each` with every way of choosing the `⊕` sides under a focus
/// on `root`, until it fails. A way is a list of the `⊕` reached and the
/// side taken.
///
/// A choice that reaches a `0` is left out, since no focus on it
/// succeeds. `each` is also called with `None` for every choice looked
/// at, whole or not, as a unit of work, since choices that a `0` ends can
/// be exponentially many.
fn plans(
    shape: &Shape<'_>,
    root: OccId,
    mut each: impl FnMut(Option<&[(OccId, Branch)]>) -> Result<(), Reason>,
) -> Result<(), Reason> {
    let forest = shape.forest;
    let mut open = vec![Vec::new()];
    'plans: while let Some(sides) = open.pop() {
        each(None)?;
        let mut walk = vec![root];
        while let Some(o) = walk.pop() {
            match forest.kind(o) {
                Kind::Tensor => walk.extend(forest.children(o).filter(|&c| shape.positive(c))),
                Kind::Plus => match sides.iter().find(|&&(p, _)| p == o) {
                    Some(&(_, side)) => {
                        let child = match side {
                            Branch::Left => forest.left(o),
                            Branch::Right => forest.right(o),
                        }
                        .expect("⊕");
                        if shape.positive(child) {
                            walk.push(child);
                        }
                    }
                    None => {
                        for side in [Branch::Right, Branch::Left] {
                            let mut more = sides.clone();
                            more.push((o, side));
                            open.push(more);
                        }
                        continue 'plans;
                    }
                },
                Kind::Zero => continue 'plans,
                _ => {}
            }
        }
        each(Some(&sides))?;
    }
    Ok(())
}

/// Compiles the rules of the search.
///
/// The rules are a focus on every positive formula a stable sequent can
/// hold, and a copy of every subformula of a `?` except the negative
/// literals (which a partner takes from the unrestricted zone). Each comes
/// under every choice of its `⊕` sides. Charges the tables to `charged`,
/// which holds them while the search runs, and counts a step as a unit of
/// work for `stop`.
pub(super) fn compile(
    shape: &Shape<'_>,
    charged: &mut Charged<'_>,
    stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Rules, Reason> {
    let forest = shape.forest;
    let mut writer = Writer {
        shape,
        rules: Rules::default(),
        reversed: Vec::new(),
        holes: Vec::new(),
        slots: Vec::new(),
        charged,
        held: 0,
        unpolled: 0,
        groups: 0,
        pending: 0,
        inner: 0,
    };
    let mut previous = None;
    for &g in &shape.goal {
        if previous.replace(g) == Some(g) {
            continue;
        }
        for o in forest.subtree(g) {
            let parent = forest.parent(o).filter(|_| o != g).map(|p| forest.kind(p));
            let focus = shape.positive(o)
                && matches!(parent, None | Some(Kind::Par | Kind::With | Kind::Bang));
            if focus {
                plans(shape, o, |sides| match sides {
                    Some(sides) => writer.write(Pending::Focus(o), sides, o, stop),
                    None => writer.tick(stop),
                })?;
            }
            let copied =
                parent == Some(Kind::Quest) && !(forest.is_literal(o) && !shape.positive(o));
            if copied {
                plans(shape, o, |sides| match sides {
                    Some(sides) => writer.write(Pending::Copy(o), sides, o, stop),
                    None => writer.tick(stop),
                })?;
            }
        }
    }
    writer.settle()?;
    Ok(writer.rules)
}

/// Compiles the goal's asynchronous phase as one rule without slots, whose
/// holes are the stable sequents the goal decomposes into. Charges it to
/// `charged`, and counts a step as a unit of work for `stop`.
pub(super) fn goal(
    shape: &Shape<'_>,
    charged: &mut Charged<'_>,
    stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Rules, Reason> {
    let mut writer = Writer {
        shape,
        rules: Rules::default(),
        reversed: Vec::new(),
        holes: Vec::new(),
        slots: Vec::new(),
        charged,
        held: 0,
        unpolled: 0,
        groups: 0,
        pending: 0,
        inner: 0,
    };
    let mut phase = writer.release();
    for &o in &shape.goal {
        phase.place(shape, o);
    }
    let anchor = shape.goal.first().copied().unwrap_or(OccId::new(0));
    writer.write(Pending::Async(phase), &[], anchor, stop)?;
    Ok(writer.rules)
}