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
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! The zones of a derived sequent: the unrestricted zone as a set, the
//! linear zone as a multiset, and the `State` a subproof proves.

use super::error::Dyadic;
use crate::hash::{HashMap, HashSet};
use crate::linear::occurrences::Member;
use crate::linear::sequents::Eigen;

/// Returns the bytes of a hash table whose entries take `entry` bytes and
/// which held `most` of them when it was fullest.
///
/// The standard library's table has a power of two of slots, four at
/// least, and fills seven in eight at most. Each slot has a control byte
/// beside its entry, and sixteen more bytes follow, the width of its SSE2
/// group. The table never gives slots back, and a copy has as many as its
/// original. A table that entries came and went from can have twice or
/// four times the slots, so this is the least the table takes, and within
/// that factor of what it does. Where the group is eight bytes (wasm32,
/// and aarch64's NEON) the table takes eight bytes fewer than counted,
/// which only makes a bound stricter.
///
/// Nothing overflows: `most` counts distinct members, each a `u32`, so 2³²
/// at most. That is 2³³ slots at most and fewer than 2³⁸ bytes, counted
/// in `u64` on every target. On a 32-bit target `most` is below 2³²
/// anyway.
pub(super) fn table_bytes(most: usize, entry: usize) -> u64 {
    if most == 0 {
        return 0;
    }
    let slots = (most as u64 * 8).div_ceil(7).next_power_of_two().max(4);
    slots * (entry as u64 + 1) + 16
}

/// The unrestricted zone: a set of members.
#[derive(Clone, Debug, Default)]
pub(super) struct Zone {
    /// The members.
    pub(super) members: HashSet<Member>,
    /// The most members the table has held, which its memory follows.
    /// They are distinct `u32` members, so 2³² at most; on a 32-bit target
    /// it is a table's length, so below 2³² there.
    pub(super) most: usize,
}

impl Zone {
    /// Returns the number of members.
    pub(super) fn len(&self) -> usize {
        self.members.len()
    }

    /// Returns whether the set has no member.
    pub(super) fn is_empty(&self) -> bool {
        self.members.is_empty()
    }

    /// Returns the members, in no particular order.
    pub(super) fn iter(&self) -> impl Iterator<Item = Member> + '_ {
        self.members.iter().copied()
    }

    /// Adds `o` and returns whether it was not a member.
    pub(super) fn insert(&mut self, o: Member) -> bool {
        // The table makes room before it looks a member up. Adding one
        // that is there already would double a full table, and the count
        // of its bytes would miss it.
        if self.members.contains(&o) {
            return false;
        }
        self.members.insert(o);
        self.most = self.most.max(self.members.len());
        true
    }

    /// Removes `o` and returns whether it was a member.
    pub(super) fn remove(&mut self, o: Member) -> bool {
        self.members.remove(&o)
    }

    /// Returns the bytes the table takes.
    pub(super) fn bytes(&self) -> u64 {
        table_bytes(self.most, size_of::<Member>())
    }
}

/// The linear zone: how many copies of each member it holds. A multiset
/// whose insertions and removals cost the same whatever its size.
///
/// The counters saturate and never wrap. The pass refuses a zone of more
/// than [`MOST`](Self::MOST) members before any rule reads it, so every
/// count a rule sees is the true one.
#[derive(Clone, Debug, Default)]
pub(super) struct Bag {
    /// The copies of every member, never zero. A count saturates at
    /// `u32::MAX`, and then the zone has at least that many members, more
    /// than [`MOST`](Self::MOST). So a count that a rule reads is exact.
    pub(super) counts: HashMap<Member, u32>,
    /// The number of members, with repeats. The sum of two zones within
    /// [`MOST`](Self::MOST) is below 2³³, so on a 64-bit target it is
    /// exact until the pass refuses it. Where a `usize` has 32 bits it
    /// saturates at `u32::MAX`, which is over the bound as well.
    pub(super) len: usize,
    /// The most distinct members the table has held, which its memory
    /// follows. They are `u32` members, so 2³² at most; on a 32-bit
    /// target it is a table's length, so below 2³² there.
    pub(super) most: usize,
}

impl PartialEq for Bag {
    /// Returns whether both hold the same copies of the same members,
    /// whatever their tables held before.
    fn eq(&self, other: &Self) -> bool {
        self.len == other.len && self.counts == other.counts
    }
}

impl Eq for Bag {}

impl Bag {
    /// The most members a zone may hold. It is below the value a counter
    /// saturates at, so a saturated counter is always over it, and it fits
    /// a `usize` of 32 bits.
    pub(super) const MOST: usize = (u32::MAX - 1) as usize;

    /// Returns the multiset of the given ids.
    pub(super) fn of(ids: impl IntoIterator<Item = Member>) -> Self {
        let mut bag = Self::default();
        for o in ids {
            bag.insert(o);
        }
        bag
    }

    /// Returns whether the multiset has no member.
    pub(super) fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the members with their numbers of copies, in no particular
    /// order.
    pub(super) fn counts(&self) -> impl Iterator<Item = (Member, u32)> + '_ {
        self.counts.iter().map(|(&o, &n)| (o, n))
    }

    /// Returns the members in ascending order, with repeats.
    pub(super) fn sorted(&self) -> Vec<Member> {
        let mut ids: Vec<Member> = self
            .counts()
            .flat_map(|(o, n)| std::iter::repeat_n(o, n as usize))
            .collect();
        ids.sort_unstable();
        ids
    }

    /// Adds one copy of `o`.
    pub(super) fn insert(&mut self, o: Member) {
        let n = self.counts.entry(o).or_insert(0);
        *n = n.saturating_add(1);
        self.len = self.len.saturating_add(1);
        self.most = self.most.max(self.counts.len());
    }

    /// Removes one copy of `o` and returns whether there was one.
    pub(super) fn remove(&mut self, o: Member) -> bool {
        let Some(n) = self.counts.get_mut(&o) else {
            return false;
        };
        // A count in the table is one at least, and the length is no less
        // than any count, so neither goes below zero.
        *n -= 1;
        if *n == 0 {
            self.counts.remove(&o);
        }
        self.len -= 1;
        true
    }

    /// Adds every copy of every member of `other`: the multiset sum,
    /// pouring the smaller table into the larger.
    pub(super) fn add(&mut self, mut other: Self) {
        if other.counts.len() > self.counts.len() {
            std::mem::swap(self, &mut other);
        }
        for (o, n) in other.counts {
            let own = self.counts.entry(o).or_insert(0);
            *own = own.saturating_add(n);
        }
        self.len = self.len.saturating_add(other.len);
        self.most = self.most.max(self.counts.len());
    }

    /// Raises every member's copies to those `other` has of it: the
    /// multiset union.
    pub(super) fn unite(&mut self, mut other: Self) {
        if other.counts.len() > self.counts.len() {
            std::mem::swap(self, &mut other);
        }
        for (o, n) in other.counts {
            let own = self.counts.entry(o).or_insert(0);
            if n > *own {
                self.len = self.len.saturating_add((n - *own) as usize);
                *own = n;
            }
        }
        self.most = self.most.max(self.counts.len());
    }

    /// Returns the bytes the table takes.
    pub(super) fn bytes(&self) -> u64 {
        table_bytes(self.most, size_of::<(Member, u32)>())
    }

    /// Returns whether no member has more copies here than in `other`.
    pub(super) fn is_subset(&self, other: &Self) -> bool {
        self.len <= other.len
            && self
                .counts()
                .all(|(o, n)| other.counts.get(&o).is_some_and(|&m| n <= m))
    }
}

/// What a subproof proves, as the checker derives it from the node's
/// premises: the dyadic sequent `⊢ Θ ; Γ`. With `any` set it proves
/// `⊢ Θ ; Γ, Δ` for every `Δ`, because a `⊤` leaf above absorbs whatever
/// context it is given.
///
/// `Θ` is the least unrestricted zone the subproof needs: the occurrences
/// it copies and does not itself move into `Θ` with a `?` step. Weakening
/// and contraction on `Θ` are implicit, so any larger zone does as well.
/// So a proof is correct when its root needs an empty `Θ` and derives the
/// sequent's formulas, and the checker never has to know the actual zone.
///
/// Both zones are tables of their members, so a sequent takes memory for
/// what it holds and none for the width of the forest.
///
/// A sequent that a rule or an observer reads has passed
/// [`Pass::within`](super::pass::Pass::within), so its linear zone has at
/// most [`Bag::MOST`] members, fewer than 2³² − 1. The sums below are
/// exact for such a sequent. While a rule builds one they saturate, which
/// only a longer zone can make them do, and that zone is refused before
/// anything reads them.
#[derive(Clone, Debug)]
pub(crate) struct State {
    /// The unrestricted zone the subproof needs.
    pub(super) theta: Zone,
    /// The linear zone.
    pub(super) gamma: Bag,
    /// How many members of the linear zone are in output position, under
    /// a reading. No more than the zone has members; it saturates with the
    /// zone's length, at `usize::MAX` as the length does, which on a
    /// 32-bit target is `u32::MAX` and over [`Bag::MOST`] as well.
    pub(super) outputs: usize,
    /// The weights of the linear zone's members, added up: fewer than
    /// 2³² − 1 members of a weight below 2³² each, so below 2⁶⁴.
    pub(super) linear: u64,
    /// The weights of the `?` formulas of the unrestricted zone's members,
    /// added up. It is at every moment the sum over the set as it stands.
    /// The set holds at most 2³² members, since a member is a `u32`, each
    /// of a weight below 2³²: below 2⁶⁴.
    pub(super) unrestricted: u64,
    /// The weights of the linear zone's members in output position: no
    /// more than `linear`.
    pub(super) goal: u64,
    /// Whether a `⊤` above absorbs any further linear context.
    pub(super) any: bool,
}

/// A set of eigenvariables, as the pass carries it from a node towards
/// the root: those that the witnesses and cut frames above name and no
/// `∀` step above introduces.
#[derive(Clone, Debug, Default)]
pub(super) struct Eigens {
    /// The members.
    pub(super) set: HashSet<Eigen>,
    /// The most members the table has held, which its memory follows. It
    /// is a table's length, and no more than the proof has terms.
    pub(super) most: usize,
}

impl Eigens {
    /// Adds `a`.
    pub(super) fn insert(&mut self, a: Eigen) {
        if self.set.insert(a) {
            self.most = self.most.max(self.set.len());
        }
    }

    /// Adds every member of `other`, pouring the smaller set into the
    /// larger.
    pub(super) fn add(&mut self, mut other: Self) {
        if other.set.len() > self.set.len() {
            std::mem::swap(self, &mut other);
        }
        self.set.extend(other.set);
        self.most = self.most.max(self.set.len());
    }

    /// Returns the bytes the set takes: its table, and its box with what
    /// the allocator keeps for it.
    pub(super) fn bytes(&self) -> u64 {
        table_bytes(self.most, size_of::<Eigen>()) + size_of::<Self>() as u64 + 16
    }
}

impl State {
    /// What a sequent takes besides its tables: the value, and what the
    /// allocator keeps for it.
    pub(super) const OWN: u64 = size_of::<Self>() as u64 + 16;

    /// Returns the least bytes the sequent takes in memory: the value and
    /// its two tables as they were when fullest. Fewer than 2³⁹.
    pub(super) fn bytes(&self) -> u64 {
        Self::OWN + self.theta.bytes() + self.gamma.bytes()
    }

    /// Returns how many entries the sequent's two tables hold, which a rule
    /// that copies, pours or compares it handles. They are distinct
    /// members, so fewer than 2³³, which a `u64` holds. Each table's length
    /// is widened to `u64` before the sum, which on a 32-bit target a
    /// `usize` might not hold.
    pub(super) fn entries(&self) -> u64 {
        self.theta.len() as u64 + self.gamma.counts.len() as u64
    }

    /// Adds one copy of `m` to the linear zone, with its weight, and
    /// counts it as a goal when it is in output position.
    #[inline]
    pub(super) fn put(&mut self, m: Member, weight: u64, output: bool) {
        self.gamma.insert(m);
        self.linear = self.linear.saturating_add(weight);
        if output {
            self.outputs = self.outputs.saturating_add(1);
            self.goal = self.goal.saturating_add(weight);
        }
    }

    /// Removes one copy of `m` from the linear zone, with its weight, and
    /// returns whether there was one. `of` gives what [`put`](Self::put)
    /// was given for `m`, its weight and whether it is an output; it is
    /// asked only when there was a copy.
    ///
    /// The sequent's sums must be exact, as they are for one that passed
    /// [`Pass::within`](super::pass::Pass::within). They count `m`, which
    /// was a member, so no subtraction goes below zero.
    #[inline]
    pub(super) fn remove(&mut self, m: Member, of: impl FnOnce() -> (u64, bool)) -> bool {
        if !self.gamma.remove(m) {
            return false;
        }
        let (weight, output) = of();
        self.linear -= weight;
        if output {
            self.outputs -= 1;
            self.goal -= weight;
        }
        true
    }

    /// Adds the linear zone of `other` and its sums, and absorbs when
    /// either does. The unrestricted zones are left as they are.
    #[inline]
    pub(super) fn add_linear(&mut self, other: &mut Self) {
        self.gamma.add(std::mem::take(&mut other.gamma));
        self.outputs = self.outputs.saturating_add(other.outputs);
        self.linear = self.linear.saturating_add(other.linear);
        self.goal = self.goal.saturating_add(other.goal);
        self.any |= other.any;
    }

    /// Counts the outputs and the weights of the linear zone anew, after
    /// the zone was replaced. `of` gives a member's weight and whether it
    /// is in output position.
    pub(super) fn recount(&mut self, of: impl Fn(Member) -> (u32, bool)) {
        let (mut outputs, mut linear, mut goal) = (0usize, 0u64, 0u64);
        for (m, n) in self.gamma.counts() {
            let (weight, output) = of(m);
            // Two factors below 2³², so the product fits a `u64`.
            let weight = u64::from(weight) * u64::from(n);
            linear = linear.saturating_add(weight);
            if output {
                outputs = outputs.saturating_add(n as usize);
                goal = goal.saturating_add(weight);
            }
        }
        (self.outputs, self.linear, self.goal) = (outputs, linear, goal);
    }

    /// Returns the sequent as ids for an error report.
    pub(super) fn to_dyadic(&self) -> Dyadic {
        let mut theta: Vec<Member> = self.theta.iter().collect();
        theta.sort_unstable();
        Dyadic {
            theta,
            gamma: self.gamma.sorted(),
            any: self.any,
        }
    }

    /// Returns the unrestricted occurrences the subproof needs, in no
    /// particular order.
    pub(crate) fn unrestricted(&self) -> impl Iterator<Item = Member> + '_ {
        self.theta.iter()
    }

    /// Returns the linear zone's members with their numbers of copies, in
    /// no particular order.
    pub(crate) fn linear(&self) -> impl Iterator<Item = (Member, u32)> + '_ {
        self.gamma.counts()
    }

    /// Returns how many unrestricted occurrences the subproof needs.
    pub(crate) fn needs(&self) -> usize {
        self.theta.len()
    }

    /// Returns whether a `⊤` above absorbs any further linear context.
    pub(crate) fn absorbs(&self) -> bool {
        self.any
    }

    /// Returns the weight of the standard sequent `⊢ ?Θ, Γ`: its formulas'
    /// weights added up, or `u64::MAX` when that is less. Each zone's sum
    /// is below 2⁶⁴, but the two together need not be.
    pub(crate) fn weight(&self) -> u64 {
        self.linear.saturating_add(self.unrestricted)
    }

    /// Returns the weight of the linear zone's members in output position.
    pub(crate) fn goal_weight(&self) -> u64 {
        self.goal
    }
}