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

use super::{Forest, OccId};
use std::fmt::{Debug, Formatter, Result as FmtResult};
use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, Sub, SubAssign};

/// A set of occurrence ids of one forest: a bitset with one bit per
/// occurrence, whose width is fixed when it is made. Sets of the same
/// forest have the same width, so they compare, hash and combine word by
/// word.
///
/// Sets of different widths combine too, as the sets of ids they are: a
/// narrower set holds nothing beyond its width, so the words it lacks count
/// as empty. An operation never widens the set it changes. An
/// intersection and a difference always fit. A union with a member beyond
/// the set's width cannot fit, and it panics in every build, so no union
/// ever lacks a member. Different widths are no error as such: inclusion
/// and disjointness have an answer for any two sets, and the operations
/// agree with those answers.
///
/// Equality, order and hash are of the words, so two sets of different
/// widths are different values even with the same members.
#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct OccSet {
    /// Bit `i` of word `i / 64` is set when occurrence `i` is a member.
    words: Box<[u64]>,
}

impl Clone for OccSet {
    fn clone(&self) -> Self {
        Self {
            words: self.words.clone(),
        }
    }

    /// Copies `source` into this set's own words when the widths agree,
    /// as they always do between sets of one forest. A search copies sets
    /// at every step and must not allocate for it.
    fn clone_from(&mut self, source: &Self) {
        if self.words.len() == source.words.len() {
            self.words.copy_from_slice(&source.words);
        } else {
            self.words = source.words.clone();
        }
    }
}

impl OccSet {
    /// Returns the empty set over `len` occurrence ids.
    pub(crate) fn empty(len: usize) -> Self {
        Self {
            words: vec![0; len.div_ceil(64)].into_boxed_slice(),
        }
    }

    /// Returns the set over `len` occurrence ids that holds the given ones.
    pub(crate) fn of(len: usize, ids: impl IntoIterator<Item = OccId>) -> Self {
        let mut set = Self::empty(len);
        set.extend(ids);
        set
    }

    /// Returns the number of ids the set can hold, which is its width rounded
    /// up to a multiple of 64.
    pub(crate) fn capacity(&self) -> usize {
        self.words.len() * 64
    }

    /// Returns the words of the bitset, lowest ids first.
    pub(crate) fn words(&self) -> &[u64] {
        &self.words
    }

    /// Returns the word and the bit mask that hold `o`.
    fn locate(o: OccId) -> (usize, u64) {
        (o.index() / 64, 1 << (o.get() % 64))
    }

    /// Adds `o` and returns whether it was absent.
    pub(crate) fn insert(&mut self, o: OccId) -> bool {
        let (w, bit) = Self::locate(o);
        let absent = self.words[w] & bit == 0;
        self.words[w] |= bit;
        absent
    }

    /// Removes `o` and returns whether it was present.
    pub(crate) fn remove(&mut self, o: OccId) -> bool {
        let (w, bit) = Self::locate(o);
        let present = self.words[w] & bit != 0;
        self.words[w] &= !bit;
        present
    }

    /// Adds `o` if it is absent and removes it otherwise.
    #[cfg(test)]
    pub(crate) fn toggle(&mut self, o: OccId) {
        let (w, bit) = Self::locate(o);
        self.words[w] ^= bit;
    }

    /// Returns whether `o` is a member.
    pub(crate) fn contains(&self, o: OccId) -> bool {
        let (w, bit) = Self::locate(o);
        self.words[w] & bit != 0
    }

    /// Removes every member.
    pub(crate) fn clear(&mut self) {
        self.words.fill(0);
    }

    /// Returns whether the set has no member.
    pub(crate) fn is_empty(&self) -> bool {
        self.words.iter().all(|&w| w == 0)
    }

    /// Returns the number of members.
    pub(crate) fn len(&self) -> usize {
        self.words.iter().map(|w| w.count_ones() as usize).sum()
    }

    /// Returns the smallest member, if any.
    #[cfg(test)]
    pub(crate) fn first(&self) -> Option<OccId> {
        self.iter().next()
    }

    /// Returns the members in the words `lo..hi`, in ascending order. When
    /// the words outside that range are empty, these are all the members.
    pub(crate) fn iter_words(&self, lo: usize, hi: usize) -> Iter<'_> {
        let words = &self.words[..hi];
        Iter {
            words,
            index: lo,
            current: words.get(lo).copied().unwrap_or(0),
        }
    }

    /// Empties the words `lo..hi`.
    pub(crate) fn clear_words(&mut self, lo: usize, hi: usize) {
        self.words[lo..hi].fill(0);
    }

    /// Makes the words `lo..hi` those of `other`, a set of the same width.
    pub(crate) fn copy_words(&mut self, other: &Self, lo: usize, hi: usize) {
        self.words[lo..hi].copy_from_slice(&other.words[lo..hi]);
    }

    /// Returns the members in ascending order.
    pub(crate) fn iter(&self) -> Iter<'_> {
        Iter {
            words: &self.words,
            index: 0,
            current: self.words.first().copied().unwrap_or(0),
        }
    }

    /// Adds every member of `other`.
    ///
    /// # Panics
    ///
    /// If `other` is wider and has a member beyond this set's width, which
    /// this set cannot hold: dropping it would give a union that lacks a
    /// member.
    pub(crate) fn union_with(&mut self, other: &Self) {
        let beyond = other.beyond(self);
        if let Some(i) = beyond.iter().position(|&w| w != 0) {
            let member = (self.words.len() + i) * 64 + beyond[i].trailing_zeros() as usize;
            panic!(
                "a union with occurrence {member}, which a set of {} ids cannot hold",
                self.capacity()
            );
        }
        self.zip_with(other, |a, b| a | b);
    }

    /// Keeps only the members `other` has too. A narrower `other` has none
    /// of the members beyond its width.
    pub(crate) fn intersect_with(&mut self, other: &Self) {
        self.zip_with(other, |a, b| a & b);
        let shared = self.words.len().min(other.words.len());
        self.words[shared..].fill(0);
    }

    /// Removes every member of `other`, whatever its width.
    pub(crate) fn difference_with(&mut self, other: &Self) {
        self.zip_with(other, |a, b| a & !b);
    }

    /// Combines the words both sets have, pair by pair, and leaves this
    /// set's words beyond the width of `other` as they are.
    fn zip_with(&mut self, other: &Self, f: impl Fn(u64, u64) -> u64) {
        for (a, b) in self.words.iter_mut().zip(&other.words) {
            *a = f(*a, *b);
        }
    }

    /// Returns the words of this set beyond the width of `other`: none
    /// unless this set is the wider one.
    fn beyond(&self, other: &Self) -> &[u64] {
        self.words.get(other.words.len()..).unwrap_or_default()
    }

    /// Returns whether every member is a member of `other`: never, when
    /// this set has a member beyond the width of `other`.
    #[cfg(test)]
    pub(crate) fn is_subset(&self, other: &Self) -> bool {
        let mut shared = self.words.iter().zip(&other.words);
        shared.all(|(a, b)| a & !b == 0) && self.beyond(other).iter().all(|&w| w == 0)
    }

    /// Returns whether no member is a member of `other`. Members beyond the
    /// width of the narrower set are members of one set only.
    #[cfg(test)]
    pub(crate) fn is_disjoint(&self, other: &Self) -> bool {
        self.words.iter().zip(&other.words).all(|(a, b)| a & b == 0)
    }
}

impl Extend<OccId> for OccSet {
    /// Adds every id.
    fn extend<I: IntoIterator<Item = OccId>>(&mut self, ids: I) {
        for o in ids {
            self.insert(o);
        }
    }
}

impl<'a> IntoIterator for &'a OccSet {
    type Item = OccId;
    type IntoIter = Iter<'a>;

    /// Returns the members in ascending order.
    fn into_iter(self) -> Iter<'a> {
        self.iter()
    }
}

impl Debug for OccSet {
    /// Writes the members in ascending order, as `{0, 3, 7}`.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        f.debug_set().entries(self.iter().map(|o| o.get())).finish()
    }
}

impl BitOrAssign<&OccSet> for OccSet {
    /// Adds every member of `other`, and panics as
    /// [`union_with`](OccSet::union_with) does.
    fn bitor_assign(&mut self, other: &OccSet) {
        self.union_with(other);
    }
}

impl BitAndAssign<&OccSet> for OccSet {
    /// Keeps only the members `other` has too.
    fn bitand_assign(&mut self, other: &OccSet) {
        self.intersect_with(other);
    }
}

impl SubAssign<&OccSet> for OccSet {
    /// Removes every member of `other`.
    fn sub_assign(&mut self, other: &OccSet) {
        self.difference_with(other);
    }
}

impl BitOr for &OccSet {
    type Output = OccSet;

    /// The union, as wide as the wider of the two sets.
    fn bitor(self, other: Self) -> OccSet {
        let (wider, narrower) = if self.words.len() < other.words.len() {
            (other, self)
        } else {
            (self, other)
        };
        let mut set = wider.clone();
        set |= narrower;
        set
    }
}

impl BitAnd for &OccSet {
    type Output = OccSet;

    /// The intersection, as wide as the left set.
    fn bitand(self, other: Self) -> OccSet {
        let mut set = self.clone();
        set &= other;
        set
    }
}

impl Sub for &OccSet {
    type Output = OccSet;

    /// The difference: the members of the left set that the right one
    /// lacks, as wide as the left set.
    fn sub(self, other: Self) -> OccSet {
        let mut set = self.clone();
        set -= other;
        set
    }
}

/// The members of an [`OccSet`] in ascending order.
#[derive(Clone, Debug)]
pub(crate) struct Iter<'a> {
    /// The set's words, of which those after `index` are still to visit.
    words: &'a [u64],
    /// The word `current` was taken from.
    index: usize,
    /// The bits of word `index` not yet yielded.
    current: u64,
}

impl Iterator for Iter<'_> {
    type Item = OccId;

    /// Returns the next member.
    fn next(&mut self) -> Option<OccId> {
        while self.current == 0 {
            self.index += 1;
            self.current = *self.words.get(self.index)?;
        }
        let bit = self.current.trailing_zeros();
        self.current &= self.current - 1;
        Some(OccId::new((self.index * 64) as u32 + bit))
    }

    /// Returns the exact number of members left.
    fn size_hint(&self) -> (usize, Option<usize>) {
        let rest = self.words.get(self.index + 1..).unwrap_or_default();
        let n = self.current.count_ones() as usize
            + rest.iter().map(|w| w.count_ones() as usize).sum::<usize>();
        (n, Some(n))
    }
}

impl ExactSizeIterator for Iter<'_> {}

impl Forest {
    /// Returns the empty set over this forest's occurrences.
    pub(crate) fn empty_set(&self) -> OccSet {
        OccSet::empty(self.len())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hash::HashSet;

    /// Wraps a raw id.
    const fn o(id: u32) -> OccId {
        OccId::new(id)
    }

    /// Members go in and out, across word boundaries, and come back in
    /// order.
    #[test]
    fn membership() {
        let mut s = OccSet::empty(130);
        assert_eq!(s.capacity(), 192);
        assert!(s.is_empty());
        assert_eq!(s.len(), 0);
        assert_eq!(s.first(), None);
        assert!(s.insert(o(129)));
        assert!(s.insert(o(64)));
        assert!(s.insert(o(3)));
        assert!(!s.insert(o(3)));
        assert!(s.contains(o(3)) && s.contains(o(64)) && s.contains(o(129)));
        assert!(!s.contains(o(63)) && !s.contains(o(65)));
        assert_eq!(s.len(), 3);
        assert_eq!(s.first(), Some(o(3)));
        assert_eq!(s.iter().collect::<Vec<_>>(), [o(3), o(64), o(129)]);
        assert_eq!(s.iter().len(), 3);
        assert_eq!(format!("{s:?}"), "{3, 64, 129}");
        assert!(s.remove(o(64)));
        assert!(!s.remove(o(64)));
        s.toggle(o(0));
        s.toggle(o(3));
        assert_eq!(s.iter().collect::<Vec<_>>(), [o(0), o(129)]);
        s.clear();
        assert!(s.is_empty());
        assert_eq!(OccSet::empty(0).iter().count(), 0);
    }

    /// Union, intersection, difference and the inclusion tests agree with
    /// their definitions on members.
    #[test]
    fn algebra() {
        let a = OccSet::of(70, [o(1), o(2), o(65)]);
        let b = OccSet::of(70, [o(2), o(3), o(69)]);
        assert_eq!(
            (&a | &b).iter().collect::<Vec<_>>(),
            [o(1), o(2), o(3), o(65), o(69)]
        );
        assert_eq!((&a & &b).iter().collect::<Vec<_>>(), [o(2)]);
        assert_eq!((&a - &b).iter().collect::<Vec<_>>(), [o(1), o(65)]);
        assert!(!a.is_subset(&b));
        assert!((&a & &b).is_subset(&a));
        assert!(!a.is_disjoint(&b));
        assert!((&a - &b).is_disjoint(&b));
        let mut c = a.clone();
        c |= &b;
        assert_eq!(c, &a | &b);
        c &= &b;
        assert_eq!(c, b);
        c -= &a;
        assert_eq!(c, &b - &a);
        let mut d = OccSet::empty(70);
        d.extend([o(65), o(1), o(2)]);
        assert_eq!(d, a);
    }

    /// Sets of different widths combine as the sets of ids they are: the
    /// narrower one has nothing beyond its width, and a set that changes
    /// keeps its own.
    #[test]
    fn different_widths() {
        let narrow = OccSet::of(64, [o(1), o(2)]);
        let wide = OccSet::of(200, [o(2), o(130)]);
        let members = |s: &OccSet| s.iter().map(OccId::get).collect::<Vec<_>>();
        assert!(
            !wide.is_subset(&narrow),
            "130 is no member of the narrow set"
        );
        assert!(!narrow.is_subset(&wide));
        assert!(OccSet::of(200, [o(2)]).is_subset(&narrow));
        assert!(OccSet::of(64, [o(2)]).is_subset(&wide));
        assert!(!wide.is_disjoint(&narrow) && !narrow.is_disjoint(&wide));
        assert!(OccSet::of(200, [o(130)]).is_disjoint(&narrow));
        assert!(narrow.is_disjoint(&OccSet::of(200, [o(130)])));

        let (meet, other) = (&wide & &narrow, &narrow & &wide);
        assert_eq!((members(&meet), meet.capacity()), (vec![2], 256));
        assert_eq!((members(&other), other.capacity()), (vec![2], 64));
        let (rest, other) = (&wide - &narrow, &narrow - &wide);
        assert_eq!((members(&rest), rest.capacity()), (vec![130], 256));
        assert_eq!((members(&other), other.capacity()), (vec![1], 64));
        let (join, other) = (&wide | &narrow, &narrow | &wide);
        assert_eq!((members(&join), join.capacity()), (vec![1, 2, 130], 256));
        assert_eq!(join, other);
        // A wider set without a member beyond the narrow one's width fits.
        let mut fits = narrow.clone();
        fits |= &OccSet::of(200, [o(3)]);
        assert_eq!((members(&fits), fits.capacity()), (vec![1, 2, 3], 64));
    }

    /// A union that the set's width cannot hold panics in every build, and
    /// names the member.
    #[test]
    #[should_panic(expected = "a union with occurrence 130, which a set of 64 ids cannot hold")]
    fn a_union_loses_no_member() {
        let mut narrow = OccSet::of(64, [o(1)]);
        narrow |= &OccSet::of(200, [o(2), o(130)]);
    }

    /// Equal sets are equal and hash alike; the words are what gets hashed.
    #[test]
    fn hashing() {
        let mut seen = HashSet::default();
        assert!(seen.insert(OccSet::of(100, [o(5), o(80)])));
        assert!(!seen.insert(OccSet::of(100, [o(80), o(5)])));
        assert!(seen.insert(OccSet::of(100, [o(5)])));
        assert_eq!(OccSet::of(100, [o(5), o(80)]).words(), [1 << 5, 1 << 16]);
    }
}