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
680
681
682
683
684
685
686
687
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! What the focused engine is generic over: the members of its zones, the
//! zones themselves, and how the literals among the members meet their
//! duals.
//!
//! A sequent in the engine has two zones. The linear zone `Γ` holds the
//! formulas a proof uses exactly once. The unrestricted zone `Θ` holds the
//! formulas under a `?`, which a proof may copy any number of times.
//!
//! [`Ground`] is the instance whose members are the forest's occurrences:
//! the propositional search. Its methods are the engine's own code,
//! inlined into it.

use super::choices::Choices;
use super::classes::Classes;
use super::context::Context;
use super::framed::{Mark, Unified};
use super::scratch::{Pooled, Pools};
use crate::linear::Instances;
use crate::linear::occurrences::{Forest, Member, OccId, OccSet};
use crate::linear::proofs::Node;
use crate::linear::search::memory::Charged;
use crate::linear::search::{Options, Reason};
use crate::linear::sequents::{Eigen, FoTermId};
use std::fmt::Debug;
use std::hash::Hash;

/// The members of the engine's zones, and the seam where its literals
/// meet: the initial rules, the forced splits' lookups of duals, the copy
/// heuristic, the classes, and what the memo and the loop check may key.
///
/// The memo is the table of stable sequents already decided. The loop
/// check prunes a sequent equal to an ancestor on its branch.
///
/// The forest is passed to every call that reads it, since a pool's
/// workers hold no borrow of their spawner's zone.
pub(super) trait Zone: Sized + Send + Sync {
    /// Whether the members are instances of occurrences under binders,
    /// with the terms the binders were opened with.
    ///
    /// The engine then runs the quantifier rules, closes its identities
    /// by unification, and asks a premise for another answer where the
    /// next one fails. Otherwise it never calls the hooks below that only
    /// such a zone has.
    const FIRST_ORDER: bool = false;

    /// A member of a zone, which names its occurrence.
    type Member: Copy + Eq + Ord + Hash + Debug + Send + Sync + Into<Member> + 'static;
    /// The linear zone, a multiset of members.
    type Linear: Linear<Self::Member> + 'static;
    /// The unrestricted zone, a set of members.
    type Unrestricted: Unrestricted<Self::Member> + 'static;
    /// Where the marks of the members dual to a literal are kept.
    type Duals: Copy;

    /// The zone of a search of the forest under the options.
    fn new(forest: &Forest, options: &Options) -> Self;

    /// The zone of a worker of a pool, spawned from this one.
    #[cfg(feature = "parallel")]
    fn fork(&self) -> Self;

    /// Makes the tables that the keys of this zone and its forks read
    /// shared, for a search on a pool whose engines share one memo.
    #[cfg(feature = "parallel")]
    fn share(&mut self) {}

    /// Whether the alternatives of a choice may run on workers of a pool,
    /// each on a fork of this zone. They may where no rule around the
    /// choice may ask it for another answer.
    #[cfg(feature = "parallel")]
    fn divides(&self) -> bool {
        true
    }

    /// Takes over the zone of the worker whose alternative proved a
    /// choice: the instances, variables and bindings its proof rests on.
    ///
    /// The worker's zone was forked from this one, which has not changed
    /// since. This zone keeps its own counters and cut.
    #[cfg(feature = "parallel")]
    fn adopt(&mut self, _worker: Self) {}

    /// Records that a worker's branch was cut by `reason`, where no
    /// branch of the level was before.
    #[cfg(feature = "parallel")]
    fn cut_by(&mut self, _reason: Reason) {}

    /// The member a goal's occurrence stands for.
    fn root(&self, o: OccId) -> Self::Member;

    /// The occurrence of a member.
    fn occurrence(&self, m: Self::Member) -> OccId;

    /// The member of an occurrence below a member's occurrence.
    fn child(&self, m: Self::Member, child: OccId) -> Self::Member;

    /// The first member dual to the literal `literal` in the unrestricted
    /// zone `within`.
    fn dual_in(
        &self,
        forest: &Forest,
        literal: Self::Member,
        within: &Self::Unrestricted,
    ) -> Option<Self::Member>;

    /// The first member dual to `literal` in `rest`, read on from where
    /// the chain's last lookup of that literal ended.
    ///
    /// `rest` is the context of a chain of forced splits. A split of the
    /// context at a `⊗` is forced when a factor decides it, as a positive
    /// literal takes exactly its dual.
    fn dual_from(
        &self,
        forest: &Forest,
        literal: Self::Member,
        rest: &Self::Linear,
        cursors: &mut Cursors,
    ) -> Option<Self::Member>;

    /// Marks the literals among the members of a stable sequent under a
    /// new stamp, with the first member of each. Charges what the marks
    /// allocate to `scratch`.
    ///
    /// A stable sequent is one with no rule left that applies without a
    /// choice.
    fn mark_literals(&mut self, forest: &Forest, members: &[Self::Member], scratch: &mut Charged);

    /// Where the marks of the members dual to `literal` are, or `None`
    /// when it is no literal.
    fn duals(&self, forest: &Forest, literal: Self::Member) -> Option<Self::Duals>;

    /// The first dual member that the last marking marked.
    fn marked(&self, duals: Self::Duals) -> Option<Self::Member>;

    /// Whether the duals are yet to be looked up in `Θ` under the last
    /// marking. From this call on they count as looked up.
    fn first_lookup(&mut self, duals: Self::Duals) -> bool;

    /// Whether a formula of `Θ` has a literal below it whose dual the
    /// last marking marked.
    fn meets(&self, forest: &Forest, formula: Self::Member) -> bool;

    /// The class of a member: the first member interchangeable with it,
    /// itself when it has none.
    fn class(&self, classes: &Classes, m: Self::Member) -> Self::Member;

    /// Whether two members are interchangeable.
    fn same(&self, classes: &Classes, x: Self::Member, y: Self::Member) -> bool;

    /// Whether the memo and the loop check may key a stable sequent of
    /// these zones, which they key by its occurrences
    /// ([`Linear::ground`], [`Unrestricted::ground`]).
    fn memoizes(&self, theta: &Self::Unrestricted, gamma: &Self::Linear) -> bool;

    /// The pool the words of the memo's keys are taken from.
    fn word_lists(pools: &mut Pools<Self>) -> &mut Vec<Pooled<OccId>>;

    /// The members of a linear zone keyed by `words`, where the words are
    /// its members, each once ([`Context::list_into`]).
    fn listed(words: &[OccId]) -> Option<&[Self::Member]>;

    /// Where the bindings, the instances and the eigenvariables stand,
    /// for [`Self::undo`].
    fn mark(&self) -> Mark {
        unreachable!("a zone without binders binds nothing")
    }

    /// Takes back every binding, instance and eigenvariable made since
    /// `mark`.
    fn undo(&mut self, _mark: Mark) {
        unreachable!("a zone without binders binds nothing")
    }

    /// Begins a level of the deepening. The search runs level by level,
    /// each with a copy budget one higher; no first-order bound has cut
    /// the new level yet.
    fn begin_level(&mut self) {}

    /// The first-order bound that cut a branch of the level, if one did.
    fn cut(&self) -> Option<Reason> {
        None
    }

    /// Applies the `∀` rule on `binder`. Returns its body's member under a
    /// fresh eigenvariable (a constant that nothing else names), which
    /// [`Self::introduced`] hands back, or `None` where a bound cuts the
    /// branch.
    ///
    /// # Errors
    ///
    /// [`Reason::IndexLimit`] where the members outgrow their ids.
    fn forall(
        &mut self,
        _forest: &Forest,
        _binder: Self::Member,
    ) -> Result<Option<Self::Member>, Reason> {
        unreachable!("a zone without binders opens none")
    }

    /// The eigenvariable of the latest `∀` rule whose node is not built.
    fn introduced(&mut self) -> Eigen {
        unreachable!("a zone without binders opens none")
    }

    /// Applies the `∃` rule on `binder`. Returns its body's member under a
    /// fresh metavariable (a variable that unification binds later), with
    /// the metavariable's term as the witness, or `None` where a bound
    /// cuts the branch.
    ///
    /// # Errors
    ///
    /// [`Reason::IndexLimit`] where the members outgrow their ids.
    fn exists(
        &mut self,
        _forest: &Forest,
        _binder: Self::Member,
    ) -> Result<Option<(Self::Member, FoTermId)>, Reason> {
        unreachable!("a zone without binders opens none")
    }

    /// Whether two members are literals of one predicate and of opposite
    /// signs, so that an axiom may join them where their terms unify.
    fn opposite(&self, _forest: &Forest, _p: Self::Member, _q: Self::Member) -> bool {
        unreachable!("a zone without binders unifies nothing")
    }

    /// Unifies the terms of two opposite literals, binding
    /// metavariables. It keeps the bindings unless an answer excluded
    /// below fits them.
    fn unify(&mut self, _forest: &Forest, _p: Self::Member, _q: Self::Member) -> Unified {
        unreachable!("a zone without binders unifies nothing")
    }

    /// Opens the answers of a rule's first premise. `members` are the
    /// members of the rule's second premise.
    ///
    /// Returns `false` where they hold no unbound metavariable, so that no
    /// binding of the first premise changes the second. Otherwise the
    /// answers found to fail are excluded while the first premise is
    /// searched, from [`Self::record`] on until [`Self::close_answers`].
    fn open_answers(
        &mut self,
        _forest: &Forest,
        _members: &mut dyn Iterator<Item = Self::Member>,
    ) -> bool {
        unreachable!("a zone without binders has one answer")
    }

    /// Whether the answers last opened are excluded while the first
    /// premise is searched.
    fn searching_first(&mut self, _first: bool) {
        unreachable!("a zone without binders has one answer")
    }

    /// Records the answer the first premise gave last, under which the
    /// second failed, to be excluded from then on. Called before
    /// [`Self::undo`] takes the answer back.
    ///
    /// Returns the bytes the record holds, which the engine charges until
    /// [`Self::close_answers`].
    fn record(&mut self, _forest: &Forest) -> usize {
        unreachable!("a zone without binders has one answer")
    }

    /// Whether the bindings as they stood before the first premise, which
    /// [`Self::undo`] restored, are excluded already. Then every answer
    /// would be, and none is left to search for.
    fn exhausted(&mut self, _forest: &Forest) -> bool {
        unreachable!("a zone without binders has one answer")
    }

    /// Closes the answers last opened.
    fn close_answers(&mut self) {
        unreachable!("a zone without binders has one answer")
    }

    /// Writes the two keys of the stable sequent `⊢ Θ ; Γ` by instance.
    /// Returns false where the sequent is to be decided without a key.
    ///
    /// The sequent's own key names its variables as the search does. Its
    /// canonical key is the same up to a renaming of them.
    fn keys(
        &mut self,
        _forest: &Forest,
        _theta: &Self::Unrestricted,
        _gamma: &Self::Linear,
        _own: &mut Vec<OccId>,
        _canonical: &mut Vec<OccId>,
    ) -> bool {
        unreachable!("a zone without binders keys its sequents by occurrence")
    }

    /// Whether some answer is excluded while its first premise is
    /// searched. A failure found then may rest on the exclusion, so it is
    /// no fact about its sequent.
    fn excluding(&self) -> bool {
        unreachable!("a zone without binders has one answer")
    }

    /// The terms the zone's walks visited since this was last asked. It is
    /// work that grows with the size of the terms, which the engine counts
    /// and polls its stop on.
    fn take_steps(&mut self) -> u64 {
        unreachable!("a zone without binders walks no term")
    }

    /// The unifications of two literals the zone tried and the
    /// metavariables it bound since it was made.
    fn counts(&self) -> (u64, u64) {
        unreachable!("a zone without binders unifies nothing")
    }

    /// The bytes the zone's tables held when last asked and hold now,
    /// which the engine charges to its account.
    fn held(&mut self) -> (usize, usize) {
        unreachable!("a zone without binders holds no table")
    }

    /// Closes the proof found and returns its instance table. Its members
    /// and witnesses are renamed to the table's, and every metavariable
    /// left unbound becomes a fresh constant.
    ///
    /// # Errors
    ///
    /// [`Reason::IndexLimit`] where the table outgrows its ids.
    fn close(&self, _forest: &Forest, _nodes: &mut [Node]) -> Result<Instances, Reason> {
        unreachable!("a zone without binders keeps its proofs as they are")
    }

    /// The choices made while a rule may ask its first premise for
    /// another answer, by which that premise's search is resumed.
    fn choices(&mut self) -> &mut Choices {
        unreachable!("a zone without binders has one answer")
    }
}

/// A linear zone: a multiset of members.
pub(super) trait Linear<M>: Debug + Send + Sync {
    /// The empty zone of a forest.
    fn empty(forest: &Forest) -> Self;
    /// Adds one copy of `m`.
    fn insert(&mut self, m: M);
    /// Removes one copy of `m`, which must be a member.
    fn remove(&mut self, m: M);
    /// Whether `m` is a member.
    fn contains(&self, m: M) -> bool;
    /// Removes every member.
    fn clear(&mut self);
    /// Makes this zone a copy of `other`, in its own buffers.
    fn copy_from(&mut self, other: &Self);
    /// Whether the zone has no member.
    fn is_empty(&self) -> bool;
    /// The members in ascending order, with repeats.
    fn iter(&self) -> impl Iterator<Item = M> + '_;
    /// Appends the members in ascending order, with repeats.
    fn list_into(&self, list: &mut Vec<M>);
    /// The zone as the occurrences the memo keys, when the zone
    /// [memoizes](Zone::memoizes).
    fn ground(&self) -> &Context;
}

/// An unrestricted zone: a set of members.
pub(super) trait Unrestricted<M>: Debug + Send + Sync {
    /// The empty zone of a forest.
    fn empty(forest: &Forest) -> Self;
    /// Adds `m`.
    fn insert(&mut self, m: M);
    /// Whether `m` is a member.
    fn contains(&self, m: M) -> bool;
    /// Removes every member.
    fn clear(&mut self);
    /// Makes this zone a copy of `other`, in its own buffers.
    fn copy_from(&mut self, other: &Self);
    /// The members in ascending order.
    fn iter(&self) -> impl Iterator<Item = M> + '_;
    /// The zone as the occurrences the memo keys, when the zone
    /// [memoizes](Zone::memoizes).
    fn ground(&self) -> &OccSet;
}

impl Linear<OccId> for Context {
    #[inline]
    fn empty(forest: &Forest) -> Self {
        Self::empty(forest.len())
    }

    #[inline]
    fn insert(&mut self, m: OccId) {
        Self::insert(self, m);
    }

    #[inline]
    fn remove(&mut self, m: OccId) {
        Self::remove(self, m);
    }

    #[inline]
    fn contains(&self, m: OccId) -> bool {
        Self::contains(self, m)
    }

    #[inline]
    fn clear(&mut self) {
        Self::clear(self);
    }

    #[inline]
    fn copy_from(&mut self, other: &Self) {
        self.clone_from(other);
    }

    #[inline]
    fn is_empty(&self) -> bool {
        Self::is_empty(self)
    }

    #[inline]
    fn iter(&self) -> impl Iterator<Item = OccId> + '_ {
        Self::iter(self)
    }

    #[inline]
    fn list_into(&self, list: &mut Vec<OccId>) {
        Self::list_into(self, list);
    }

    #[inline]
    fn ground(&self) -> &Context {
        self
    }
}

impl Unrestricted<OccId> for OccSet {
    #[inline]
    fn empty(forest: &Forest) -> Self {
        forest.empty_set()
    }

    #[inline]
    fn insert(&mut self, m: OccId) {
        Self::insert(self, m);
    }

    #[inline]
    fn contains(&self, m: OccId) -> bool {
        Self::contains(self, m)
    }

    #[inline]
    fn clear(&mut self) {
        Self::clear(self);
    }

    #[inline]
    fn copy_from(&mut self, other: &Self) {
        self.clone_from(other);
    }

    #[inline]
    fn iter(&self) -> impl Iterator<Item = OccId> + '_ {
        Self::iter(self)
    }

    #[inline]
    fn ground(&self) -> &OccSet {
        self
    }
}

/// How far a chain of forced splits has read the forest's lists of the
/// occurrences of each literal in its search for duals.
pub(super) struct Cursors {
    /// Per list (twice the atom plus the sign, as the forest numbers
    /// them), how many occurrences at its head are no longer in the
    /// chain's context.
    pub(super) passed: Vec<u32>,
    /// The lists whose entry is not zero.
    pub(super) moved: Vec<u32>,
}

/// What the members marked last have on one list of a literal's
/// occurrences.
#[derive(Clone, Copy, Debug)]
struct Marks {
    /// The stamp of the marking that last found a member on the list.
    stamp: u64,
    /// The first member that marking found there.
    first: OccId,
    /// The stamp of the marking whose initial rules last looked for the
    /// list's literal in `Θ`.
    tried: u64,
}

/// The zone whose members are the forest's occurrences. Its literals meet
/// through the forest's lists of each literal's occurrences, and the memo
/// keys every sequent.
pub(super) struct Ground {
    /// Per list of a literal's occurrences (twice the atom plus the sign,
    /// as the forest numbers them), what the members marked last have on
    /// it. Empty until the first marking.
    lists: Vec<Marks>,
    /// The stamp of the members marked last. A search that marks a
    /// billion sets a second takes five centuries to wrap it.
    stamp: u64,
}

impl Zone for Ground {
    type Member = OccId;
    type Linear = Context;
    type Unrestricted = OccSet;
    type Duals = usize;

    #[inline]
    fn new(_: &Forest, _: &Options) -> Self {
        Self {
            lists: Vec::new(),
            stamp: 0,
        }
    }

    /// A worker marks on lists of its own.
    #[cfg(feature = "parallel")]
    #[inline]
    fn fork(&self) -> Self {
        Self {
            lists: Vec::new(),
            stamp: 0,
        }
    }

    #[inline]
    fn root(&self, o: OccId) -> OccId {
        o
    }

    #[inline]
    fn occurrence(&self, m: OccId) -> OccId {
        m
    }

    #[inline]
    fn child(&self, _: OccId, child: OccId) -> OccId {
        child
    }

    /// Found through the forest's list of the dual literal's occurrences,
    /// not through the zone's members.
    ///
    /// Always inlined. It takes a set, not a closure, and two zones share
    /// its callers, so the compiler would otherwise leave it out of line:
    /// a call per lookup on a chain of copies.
    #[inline(always)]
    fn dual_in(&self, f: &Forest, literal: OccId, within: &OccSet) -> Option<OccId> {
        let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
        f.literals(atom, !sign)
            .iter()
            .copied()
            .find(|&d| within.contains(d))
    }

    /// What [`Self::dual_in`] finds in `rest`, read from where the chain's
    /// last lookup of that literal ended. The context of a chain only
    /// loses members, so the occurrences passed over once are gone from
    /// it.
    ///
    /// So a chain's lookups of one literal together cost its list once.
    /// Read from the head each time, they are quadratic, and most of a
    /// search's time on a Petri net's marking of thousands of equal
    /// tokens.
    #[inline]
    fn dual_from(
        &self,
        f: &Forest,
        literal: OccId,
        rest: &Context,
        cursors: &mut Cursors,
    ) -> Option<OccId> {
        let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
        let duals = f.literals(atom, !sign);
        let list = Forest::list(atom, !sign);
        let start = cursors.passed[list] as usize;
        let found = duals[start..].iter().position(|&d| rest.contains(d));
        let passed = found.map_or(duals.len(), |at| start + at);
        if passed != start {
            if start == 0 {
                cursors.moved.push(list as u32);
            }
            // A list is a part of the forest's occurrences, which a `u32`
            // indexes.
            cursors.passed[list] = passed as u32;
        }
        found.map(|at| duals[start + at])
    }

    /// One pass over the members. Ranking the copies then costs the
    /// members and the formulas of `Θ` once each, not their product. The
    /// product is a quarter of a second per stable sequent on a Petri
    /// net's marking of thousands of tokens under clauses of thousands of
    /// literals.
    #[inline]
    fn mark_literals(&mut self, f: &Forest, members: &[OccId], scratch: &mut Charged) {
        if self.lists.is_empty() {
            let lists = f.lists();
            scratch.charge(lists * size_of::<Marks>());
            self.lists = vec![
                Marks {
                    stamp: 0,
                    first: OccId::new(0),
                    tried: 0,
                };
                lists
            ];
        }
        self.stamp += 1;
        for &m in members {
            if let (Some(atom), Some(sign)) = (f.atom(m), f.sign(m)) {
                let list = &mut self.lists[Forest::list(atom, sign)];
                if list.stamp != self.stamp {
                    list.stamp = self.stamp;
                    list.first = m;
                }
            }
        }
    }

    /// The list of the dual literal's occurrences.
    #[inline]
    fn duals(&self, f: &Forest, literal: OccId) -> Option<usize> {
        let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
        Some(Forest::list(atom, !sign))
    }

    #[inline]
    fn marked(&self, dual: usize) -> Option<OccId> {
        let list = &self.lists[dual];
        (list.stamp == self.stamp).then_some(list.first)
    }

    #[inline]
    fn first_lookup(&mut self, dual: usize) -> bool {
        let list = &mut self.lists[dual];
        if list.tried == self.stamp {
            return false;
        }
        list.tried = self.stamp;
        true
    }

    /// The copy heuristic's test: a copy of a formula that meets a member
    /// is tried first.
    #[inline]
    fn meets(&self, f: &Forest, a: OccId) -> bool {
        f.subtree(a).any(|l| match (f.atom(l), f.sign(l)) {
            (Some(atom), Some(sign)) => self.lists[Forest::list(atom, !sign)].stamp == self.stamp,
            _ => false,
        })
    }

    #[inline]
    fn class(&self, classes: &Classes, m: OccId) -> OccId {
        classes.of(m)
    }

    #[inline]
    fn same(&self, classes: &Classes, x: OccId, y: OccId) -> bool {
        classes.same(x, y)
    }

    #[inline]
    fn memoizes(&self, _: &OccSet, _: &Context) -> bool {
        true
    }

    /// The lists of members, which are occurrences.
    #[inline]
    fn word_lists(pools: &mut Pools<Self>) -> &mut Vec<Pooled<OccId>> {
        &mut pools.lists
    }

    #[inline]
    fn listed(words: &[OccId]) -> Option<&[OccId]> {
        Some(words)
    }
}