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

//! The wire forms of earlier releases and levels, read by this one.
//! `wire/level-1.txt` is the JSON lock (`lock/json.txt`) as version 0.1.0
//! wrote it, followed by the disproofs of every refutation and a proof and
//! a disproof of a goal off the roots, as 0.1.0 wrote them, one `NAME:
//! JSON` per line, `wire/level-2.txt` the forms level 2 added and
//! `wire/level-3.txt` those level 3 added, `wire/level-4.txt` those
//! level 4 added, `wire/level-5.txt` those level 5 added,
//! `wire/level-6.txt` those level 6 added, `wire/level-7.txt` those
//! level 7 added, `wire/level-8.txt` those level 8 added,
//! `wire/level-11.txt` those level 11 added, `wire/level-12.txt` the
//! ordinary outcomes of level 12, `wire/level-13.txt` a Kripke model and
//! an outcome that holds one (at level 12); none is ever
//! rewritten: where
//! the lock moves on, these files stay. Every
//! line of a form that is read back reads through
//! `wire::upgrade`, and writes the same bytes again; an outcome reads back
//! as the proof or the disproof it holds. A release that fails here can no
//! longer read what an earlier one wrote at a level it claims, which its
//! wire level promises.
#![cfg(all(feature = "serialize", feature = "interactive"))]

use deduxit::wire::{self, Readable};
use deduxit::{
    Limits,
    linear::{
        Disproof, Engine, IllSequent, Interactive, MellStructure, Outcome, Proof, ProofStructure,
        Sequent,
    },
};

/// Reads one document of the form `T`.
fn read<T: Readable>(name: &str, json: &str) -> T {
    let mut document = serde_json::Deserializer::from_str(json);
    let value = wire::upgrade(&mut document, &Limits::default())
        .unwrap_or_else(|error| panic!("{name}: {error}"));
    document.end().unwrap();
    value
}

/// Reads one document of the form `T` and asserts that it writes the same
/// bytes again, but for the version of deduxit that wrote it (an
/// outcome's `deduxit`, which no reader reads): this build writes its own.
fn again<T: Readable + serde::Serialize>(name: &str, json: &str) {
    let value: T = read(name, json);
    assert_eq!(
        serde_json::to_string(&value).unwrap(),
        written_now(json),
        "{name}"
    );
}

/// The document with its first `"deduxit"` key, the top level's, naming
/// this build's version.
fn written_now(json: &str) -> String {
    const KEY: &str = r#""deduxit":""#;
    let Some(start) = json.find(KEY).map(|at| at + KEY.len()) else {
        return json.to_owned();
    };
    let end = start + json[start..].find('"').unwrap();
    format!(
        "{}{}{}",
        &json[..start],
        env!("CARGO_PKG_VERSION"),
        &json[end..]
    )
}

/// Every line of the first release's forms reads, and a form read back
/// writes what it read.
#[test]
fn the_first_release_reads() {
    let lines = include_str!("wire/level-1.txt");
    let mut read_back = 0;
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        let verdict = |v: &str| json.contains(&format!(r#""verdict":"{v}""#));
        match name.split('-').next().unwrap() {
            "sequent" => again::<Sequent>(name, json),
            "proof" => again::<Proof>(name, json),
            "disproof" => again::<Disproof>(name, json),
            "structure" => again::<ProofStructure>(name, json),
            "session" => again::<Interactive>(name, json),
            "outcome" if verdict("proved") => {
                let _: Proof = read(name, json);
            }
            "outcome" if verdict("unprovable") => {
                let _: Disproof = read(name, json);
            }
            // An unknown outcome holds no proof or disproof;
            // `outcomes_read_back` reads it as an outcome.
            "outcome" => continue,
            other => panic!("{name}: no form {other}"),
        }
        read_back += 1;
    }
    assert_eq!(read_back, 37, "every line but the three unknown outcomes");
}

/// The forms level 2 added, as the release that made it wrote them: the
/// classical refutation of a disproof and of an unprovable outcome. Never
/// rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_second_level_reads() {
    let lines = include_str!("wire/level-2.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "disproof" => again::<Disproof>(name, json),
            "outcome" => {
                let _: Disproof = read(name, json);
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 2);
}

/// The forms level 3 added, as the release that made it wrote them: the
/// refutation by a saturated set of a disproof and of an unprovable
/// outcome. Never rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_third_level_reads() {
    let lines = include_str!("wire/level-3.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "disproof" => again::<Disproof>(name, json),
            "outcome" => {
                let disproof: Disproof = read(name, json);
                assert_eq!(disproof.check(), Ok(()), "{name}");
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 2);
}

/// The forms level 4 added, as the release that made it wrote them: a
/// proof structure with boxes. Never rewritten, as `wire/level-1.txt` is
/// not.
#[test]
fn the_fourth_level_reads() {
    let lines = include_str!("wire/level-4.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "structure" => {
                again::<MellStructure>(name, json);
                let net: MellStructure = read(name, json);
                assert_eq!(net.is_correct(|_| false), Ok(()), "{name}");
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 1);
}

/// The forms level 5 added, as the release that made it wrote them: an
/// intuitionistic sequent. Never rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_fifth_level_reads() {
    let lines = include_str!("wire/level-5.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "sequent" => {
                again::<IllSequent>(name, json);
                let sequent: IllSequent = read(name, json);
                assert_eq!(sequent.to_string(), "!(A ⊸ B), ⊤, 0 ⊢ (A ⊗ 1) & (B ⊕ ⊤)");
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 1);
}

/// The forms level 6 added, as the release that made it wrote them: a
/// proof with a cut and a session with one, whose sequents hold their cut
/// formulas. Never rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_sixth_level_reads() {
    let lines = include_str!("wire/level-6.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "proof" => {
                again::<Proof>(name, json);
                let proof: Proof = read(name, json);
                assert_eq!(
                    proof.check(deduxit::linear::Mode::CLASSICAL),
                    Ok(()),
                    "{name}"
                );
                assert_eq!(proof.sequent().cuts().len(), 1, "{name}");
            }
            "session" => {
                again::<Interactive>(name, json);
                let session: Interactive = read(name, json);
                assert_eq!(session.goals().count(), 1, "{name}");
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 2);
}

/// Every document of level 7, the first-order sequent in its one-sided and
/// its intuitionistic form, reads and writes the same bytes again.
#[test]
fn the_seventh_level_reads() {
    let lines = include_str!("wire/level-7.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "sequent" => {
                again::<Sequent>(name, json);
                let sequent: Sequent = read(name, json);
                assert!(sequent.is_first_order(), "{name}");
            }
            "intuitionistic" => {
                again::<IllSequent>(name, json);
                let sequent: IllSequent = read(name, json);
                assert!(sequent.sequent().fragment().has_quantifiers(), "{name}");
            }
            other => panic!("{other}: no form of level 7"),
        }
    }
}

/// Every document of level 8, the forms of ordinary logic (a sequent, a
/// derivation of LK and a proof in progress in LJ), reads and writes the
/// same bytes again; the derivation still checks and the proof in
/// progress still has its open goal. Never rewritten, as
/// `wire/level-1.txt` is not.
#[test]
fn the_eighth_level_reads() {
    use deduxit::ordinary;
    let lines = include_str!("wire/level-8.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "sequent" => again::<ordinary::Sequent>(name, json),
            "derivation" => {
                again::<ordinary::Derivation>(name, json);
                let derivation: ordinary::Derivation = read(name, json);
                assert_eq!(derivation.check(&Limits::default(), |_| false), Ok(()));
            }
            "session" => {
                again::<ordinary::Interactive>(name, json);
                let session: ordinary::Interactive = read(name, json);
                assert_eq!(session.goals().count(), 1, "{name}");
            }
            other => panic!("{other}: no form of level 8"),
        }
    }
    assert_eq!(lines.lines().count(), 3);
}

/// The forms level 11 added, as the release that made it wrote them: the
/// refutation by the basis of a backward search, of a disproof and of an
/// unprovable outcome, which still checks. Never rewritten, as
/// `wire/level-1.txt` is not.
#[test]
fn the_eleventh_level_reads() {
    let lines = include_str!("wire/level-11.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "disproof" => {
                again::<Disproof>(name, json);
                let disproof: Disproof = read(name, json);
                assert_eq!(disproof.check(), Ok(()), "{name}");
            }
            "outcome" => {
                let disproof: Disproof = read(name, json);
                assert_eq!(disproof.check(), Ok(()), "{name}");
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 2);
}

/// Every ordinary outcome of level 12 (LJT's, the embedding's with the
/// image's proof nested, the SAT solver's refutation) reads and writes
/// the same bytes again, and a derivation it holds still checks. Never
/// rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_twelfth_level_reads() {
    use deduxit::ordinary;
    let lines = include_str!("wire/level-12.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        again::<ordinary::Outcome>(name, json);
        let outcome: ordinary::Outcome = read(name, json);
        if let ordinary::Verdict::Valid(evidence) = &outcome.verdict {
            let derivation = evidence.derivation().unwrap();
            assert_eq!(derivation.check(&Limits::default(), |_| false), Ok(()));
        }
    }
    assert_eq!(lines.lines().count(), 3);
}

/// The forms level 13 added, a Kripke model, and an ordinary outcome that
/// holds one (still written at level 12: the key raises no level), read
/// and write the same bytes again, and the outcome's
/// countermodel still refutes its sequent. Never rewritten, as
/// `wire/level-1.txt` is not.
#[test]
fn the_thirteenth_level_reads() {
    use deduxit::{kripke, ordinary};
    let lines = include_str!("wire/level-13.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "model" => again::<kripke::Model>(name, json),
            "outcome" => {
                again::<ordinary::Outcome>(name, json);
                let outcome: ordinary::Outcome = read(name, json);
                let countermodel = outcome.countermodel.expect("a countermodel");
                assert_eq!(
                    countermodel.check(outcome.logic, &deduxit::Limits::default(), |_| false),
                    Ok(())
                );
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 2);
}

/// The forms level 14 adds, a truth table and a tableau, read alone and
/// in an outcome of their method, and write the same bytes again; the
/// table read is the one computed from its sequent, and the outcome's
/// evidence still holds. Never rewritten, as `wire/level-1.txt` is not.
#[test]
fn the_fourteenth_level_reads() {
    use deduxit::ordinary;
    let limits = deduxit::Limits::default();
    let lines = include_str!("wire/level-14.txt");
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "table" => {
                again::<ordinary::TruthTable>(name, json);
                let table: ordinary::TruthTable = read(name, json);
                assert_eq!(table.falsifying(), [2], "{name}");
            }
            "tableau" => {
                again::<ordinary::Tableau>(name, json);
                let tableau: ordinary::Tableau = read(name, json);
                assert!(tableau.is_closed(), "{name}");
            }
            "outcome" => {
                again::<ordinary::Outcome>(name, json);
                let outcome: ordinary::Outcome = read(name, json);
                match (&outcome.verdict, &outcome.countermodel) {
                    (ordinary::Verdict::Valid(evidence), None) => {
                        let derivation = evidence.derivation().unwrap();
                        assert_eq!(derivation.check(&limits, |_| false), Ok(()), "{name}");
                    }
                    (ordinary::Verdict::NotValid, Some(countermodel)) => assert_eq!(
                        countermodel.check(outcome.logic, &limits, |_| false),
                        Ok(()),
                        "{name}"
                    ),
                    other => panic!("{name}: {other:?}"),
                }
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 4);
    // A verdict its own tableau does not bear out is refused.
    let valid = lines
        .lines()
        .find(|l| l.starts_with("outcome-tableau"))
        .unwrap();
    let forged = valid
        .split_once(": ")
        .unwrap()
        .1
        .replace("\"valid\"", "\"not_valid\"");
    assert!(serde_json::from_str::<ordinary::Outcome>(&forged).is_err());
}

/// Every outcome the JSON lock holds (each verdict, refutation and reason,
/// at levels 1 and 2) reads as an `Outcome` and writes the same bytes
/// again; one the first release wrote reads too, as does an engine this
/// build does not know.
#[test]
fn outcomes_read_back() {
    let mut levels = std::collections::BTreeSet::new();
    for line in include_str!("lock/json.txt").lines() {
        let (name, json) = line.split_once(": ").unwrap();
        if name.starts_with("outcome-") {
            again::<Outcome>(name, json);
            let level: serde_json::Value = serde_json::from_str(json).unwrap();
            levels.insert(level["version"].as_u64().unwrap());
        }
    }
    assert_eq!(levels.into_iter().collect::<Vec<_>>(), [1, 2]);
    for line in include_str!("wire/level-1.txt").lines() {
        let (name, json) = line.split_once(": ").unwrap();
        if name.starts_with("outcome-") {
            let _: Outcome = read(name, json);
        }
    }

    let (name, json) = include_str!("lock/json.txt")
        .lines()
        .find_map(|line| {
            line.split_once(": ")
                .filter(|(name, _)| *name == "outcome-mll")
        })
        .unwrap();
    let later = json.replace(r#""engine":"focus""#, r#""engine":"sat""#);
    assert_ne!(later, json);
    let outcome: Outcome = read(name, &later);
    assert_eq!(outcome.engine, Engine::Unknown);
}

/// The forms level 15 adds, a rule file and derivations in a calculus
/// given as data, read and written again byte for byte, each derivation
/// checked in its calculus. Never rewritten, as `wire/level-1.txt` is
/// not.
#[test]
fn the_fifteenth_level_reads() {
    use deduxit::rules::{Calculus, Derivation, LK};
    let lines = include_str!("wire/level-15.txt");
    let mut calculi: Vec<Calculus> = vec![read("lk", LK)];
    for line in lines.lines() {
        let (name, json) = line.split_once(": ").unwrap();
        match name.split('-').next().unwrap() {
            "calculus" => {
                again::<Calculus>(name, json);
                calculi.push(read(name, json));
            }
            "derivation" => {
                again::<Derivation>(name, json);
                let derivation: Derivation = read(name, json);
                let calculus = calculi
                    .iter()
                    .find(|c| c.name() == derivation.calculus())
                    .unwrap_or_else(|| panic!("{name}: no calculus"));
                assert_eq!(
                    derivation.check(calculus, &Limits::default(), |_| false),
                    Ok(()),
                    "{name}"
                );
            }
            other => panic!("{name}: no form {other}"),
        }
    }
    assert_eq!(lines.lines().count(), 3);
}