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

//! The parallel runtime. Each search runs on a thread pool, built for it
//! or lent by a [`Pool`] the caller keeps across searches. The workers
//! poll atomic stop flags, and a driver polls the caller's stop condition
//! on the calling thread while the pool searches. The engines own the
//! rest: the shared memo, the cubes and each worker's state. Nothing here
//! is global.

use super::{Work, lock};
use crate::Error;
use rayon::{ThreadPool, ThreadPoolBuilder};
use std::fmt::{Debug, Formatter, Result as FmtResult};
use std::ops::Deref;
use std::sync::atomic::{AtomicBool, AtomicU32, Ordering};
use std::sync::mpsc::{RecvTimeoutError, channel};
use std::sync::{Arc, Mutex, MutexGuard};
use std::time::Duration;

/// How long the driver waits for the result before it polls the caller's
/// stop condition again.
const POLL: Duration = Duration::from_millis(1);

/// Returns how many threads a search uses of the `jobs` its options name:
/// no more than the machine runs at once, where the platform tells how
/// many that is.
pub(crate) fn threads(jobs: usize) -> usize {
    if jobs <= 1 {
        return jobs;
    }
    std::thread::available_parallelism().map_or(jobs, |machine| jobs.min(machine.get()))
}

/// The most runtimes a [`Pool`] keeps between searches. One search holds
/// two at most, for the two searches of the default bias, and two
/// parallel searches running at once through one pool hold four. A kept
/// runtime's threads sleep, but each holds its stack's mapping and a
/// thread of the process. So a pool keeps no more than it can lend at
/// once.
const MAX_KEPT: usize = 4;

/// Thread pools kept across searches, for a caller that runs many
/// parallel searches one after another, such as a batch of sequents.
///
/// A search with this handle in its options
/// ([`Options::pool`](super::Options::pool)) borrows a kept pool of
/// exactly the threads it runs on, or builds one. It gives the pool back
/// when it ends, so the threads start once, not once per search. A search
/// on a kept pool is the same search as on a fresh one. A kept pool is
/// lent to one search at a time, so searches that run at once through one
/// handle each run on pools of their own. At most four pools are kept.
/// Their threads end when the last clone of the handle is dropped and no
/// search holds them. Clones share the pools; nothing is global.
///
/// Needs the cargo feature `parallel` (off by default).
///
/// # Examples
///
/// Two searches on two threads each, the second on the threads the first
/// started:
///
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
/// use deduxit::linear::search::Pool;
/// use deduxit::linear::{Mode, Options, Sequent, Verdict, prove};
///
/// let options = Options::default().with_jobs(2).with_pool(Some(Pool::new()));
/// for text in ["A |- A", "A, B |- A * B"] {
///     let sequent: Sequent = text.parse()?;
///     let outcome = prove(&sequent, Mode::CLASSICAL, &options)?;
///     assert!(matches!(outcome.verdict, Verdict::Proved(_)));
/// }
/// # Ok::<(), deduxit::Error>(())
/// ```
#[derive(Clone, Default)]
pub struct Pool {
    /// The shared state.
    inner: Arc<Kept>,
}

/// What the clones of a [`Pool`] share.
#[derive(Default)]
struct Kept {
    /// The runtimes no search holds, the most recently given back last.
    idle: Mutex<Vec<Runtime>>,
    /// How many runtimes the pool has built.
    #[cfg(test)]
    built: std::sync::atomic::AtomicUsize,
}

impl Pool {
    /// Returns an empty pool, which builds its thread pools as searches
    /// ask for them.
    pub fn new() -> Self {
        Self::default()
    }

    /// Locks the idle runtimes. A panic elsewhere leaves the list whole,
    /// since each change of it is one push or one removal.
    fn idle(&self) -> MutexGuard<'_, Vec<Runtime>> {
        lock(&self.inner.idle)
    }

    /// Gives a runtime back for later searches, dropping the one given
    /// back longest ago when the pool is full.
    fn give_back(&self, runtime: Runtime) {
        let evicted = {
            let mut idle = self.idle();
            idle.push(runtime);
            (idle.len() > MAX_KEPT).then(|| idle.remove(0))
        };
        // Its threads are told to end outside the lock.
        drop(evicted);
    }
}

impl PartialEq for Pool {
    /// Whether the two handles are clones of one pool.
    fn eq(&self, other: &Self) -> bool {
        Arc::ptr_eq(&self.inner, &other.inner)
    }
}

impl Eq for Pool {}

impl Debug for Pool {
    /// Writes the pool's address and the thread counts of its idle pools.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        let threads: Vec<usize> = self.idle().iter().map(Runtime::threads).collect();
        f.debug_struct("Pool")
            .field("at", &Arc::as_ptr(&self.inner))
            .field("idle", &threads)
            .finish()
    }
}

/// A runtime a search holds. It is lent by a [`Pool`], which takes it back
/// when this is dropped, or built for the search alone and dropped with
/// it. The drop comes on a return, an error or a panic, after every task
/// on the runtime has ended.
pub(crate) struct Lent<'p> {
    /// The runtime, until it is given back.
    runtime: Option<Runtime>,
    /// The pool it goes back to, if any.
    pool: Option<&'p Pool>,
}

impl<'p> Lent<'p> {
    /// Takes a runtime of `threads` workers (at least one) whose stacks
    /// have at least `stack_size` bytes: an idle one of `pool`, or a new
    /// one, as [`Runtime::new`] builds it.
    ///
    /// # Errors
    ///
    /// [`Error::ThreadPool`] when a new pool's threads cannot start.
    pub(crate) fn take(
        pool: Option<&'p Pool>,
        threads: usize,
        stack_size: usize,
    ) -> Result<Self, Error> {
        let threads = threads.max(1);
        let kept = pool.and_then(|pool| {
            let mut idle = pool.idle();
            let at = idle
                .iter()
                .rposition(|r| r.threads == threads && r.stack_size >= stack_size)?;
            Some(idle.remove(at))
        });
        let runtime = match kept {
            Some(runtime) => runtime,
            None => {
                let runtime = Runtime::new(threads, stack_size)?;
                #[cfg(test)]
                if let Some(pool) = pool {
                    pool.inner.built.fetch_add(1, Ordering::Relaxed);
                }
                runtime
            }
        };
        Ok(Self {
            runtime: Some(runtime),
            pool,
        })
    }
}

impl Deref for Lent<'_> {
    type Target = Runtime;

    /// The runtime held.
    fn deref(&self) -> &Runtime {
        self.runtime
            .as_ref()
            .expect("a lent runtime is taken only when it is dropped")
    }
}

impl Drop for Lent<'_> {
    /// Gives the runtime back to its pool, if it came from one. Every
    /// task on it has ended, since a search's scopes end before it does.
    fn drop(&mut self) {
        if let (Some(runtime), Some(pool)) = (self.runtime.take(), self.pool) {
            pool.give_back(runtime);
        }
    }
}

/// The thread pool a parallel search runs on: `threads` workers whose
/// stacks fit the recursion limit. It is built for one search and dropped
/// with it, or kept by a [`Pool`].
pub(crate) struct Runtime {
    /// The pool.
    pub(crate) pool: ThreadPool,
    /// How many workers it has.
    threads: usize,
    /// The size of each worker's stack, in bytes.
    stack_size: usize,
    /// Per worker, the recursion depth of the engine that waits at a scope
    /// on its thread: a task the thread runs meanwhile sits on that
    /// engine's frames. Only the worker itself writes its own.
    depths: Box<[AtomicU32]>,
}

impl Runtime {
    /// Starts a pool of `threads` workers with stacks of `stack_size`
    /// bytes, or says why it cannot ([`Error::ThreadPool`]).
    pub(crate) fn new(threads: usize, stack_size: usize) -> Result<Self, Error> {
        let threads = threads.max(1);
        let pool = ThreadPoolBuilder::new()
            .num_threads(threads)
            .stack_size(stack_size)
            .thread_name(|i| format!("deduxit-search-{i}"))
            .build()
            .map_err(|e| Error::ThreadPool {
                threads,
                message: e.to_string(),
            })?;
        Ok(Self {
            pool,
            threads,
            stack_size,
            depths: (0..threads).map(|_| AtomicU32::new(0)).collect(),
        })
    }

    /// Returns how many workers the pool has.
    pub(crate) fn threads(&self) -> usize {
        self.threads
    }

    /// Returns the recursion depth on the calling thread's stack below
    /// what it runs now: that of the engine waiting at a scope there, or
    /// zero on a thread outside the pool. A task that a waiting thread
    /// steals starts from this depth. So its recursion counts on top of the
    /// frames it sits on, and the recursion limit holds for the stack.
    pub(crate) fn depth_here(&self) -> u32 {
        self.pool
            .current_thread_index()
            .map_or(0, |i| self.depths[i].load(Ordering::Relaxed))
    }

    /// Records that an engine at `depth` waits at a scope on the calling
    /// thread until the returned guard is dropped, which restores what the
    /// thread recorded before.
    pub(crate) fn waiting(&self, depth: u32) -> Waiting<'_> {
        let saved = self.pool.current_thread_index().map(|i| {
            let before = self.depths[i].swap(depth, Ordering::Relaxed);
            (i, before)
        });
        Waiting {
            runtime: self,
            saved,
        }
    }

    /// Runs `work` on the pool, given the root of the stop flags, and
    /// returns its result. Meanwhile the calling thread polls `stop` once
    /// a millisecond and raises the flag when it fires, so the caller's
    /// condition needs to be neither `Send` nor fast. A panic in `work`
    /// propagates to the caller.
    pub(crate) fn drive<T: Send>(
        &self,
        stop: &mut dyn FnMut(u64) -> bool,
        done: &Work,
        work: impl FnOnce(Flags<'_>) -> T + Send,
    ) -> T {
        let flag = AtomicBool::new(false);
        let (sender, receiver) = channel();
        let result = self.pool.in_place_scope(|scope| {
            let flag = &flag;
            scope.spawn(move |_| {
                let result = work(Flags::root(flag, done));
                // The receiver is gone only when the caller's loop ended,
                // which it does only on a result.
                let _ = sender.send(result);
            });
            // The caller's stop may panic: the work then stops too.
            let _raise = RaiseOnPanic(flag);
            loop {
                match receiver.recv_timeout(POLL) {
                    Ok(result) => return Some(result),
                    Err(RecvTimeoutError::Timeout) => {
                        // The workers count their own work, so this poll
                        // tells of none.
                        if stop(0) {
                            flag.store(true, Ordering::Relaxed);
                        }
                    }
                    // The task ended without a result: it panicked, and the
                    // scope resumes the panic once the loop lets it end.
                    Err(RecvTimeoutError::Disconnected) => return None,
                }
            }
        });
        result.expect("a task that ends without a result panicked, which the scope propagates")
    }
}

/// A thread's recorded depth while an engine waits at a scope there.
pub(crate) struct Waiting<'a> {
    /// The runtime.
    runtime: &'a Runtime,
    /// The worker's index and the depth recorded before.
    saved: Option<(usize, u32)>,
}

impl Drop for Waiting<'_> {
    /// Restores the depth recorded before the wait.
    fn drop(&mut self) {
        if let Some((i, before)) = self.saved {
            self.runtime.depths[i].store(before, Ordering::Relaxed);
        }
    }
}

/// Records a worker's reason for giving up. The first reason recorded
/// stays, except that a stop gives way to any later reason, which is then
/// the reason.
pub(crate) fn record(slot: &mut Option<super::Reason>, reason: super::Reason) {
    if slot.is_none_or(|old| old == super::Reason::Stopped) {
        *slot = Some(reason);
    }
}

/// Raises a flag when a panic drops it, so the tasks the flag reaches stop
/// at their next poll. A scope runs every task it spawned to its end
/// before it lets a panic go on. Without the flag, that is the whole
/// search below the panic.
pub(crate) struct RaiseOnPanic<'a>(pub(crate) &'a AtomicBool);

impl Drop for RaiseOnPanic<'_> {
    /// Raises the flag if the thread is panicking.
    fn drop(&mut self) {
        if std::thread::panicking() {
            self.0.store(true, Ordering::Relaxed);
        }
    }
}

/// Runs two pieces of work at once, each on a pool of its own and given
/// the root of its own stop flags, and returns both results. The calling
/// thread polls `stop` once a millisecond, as [`Runtime::drive`] does, and
/// raises both flags when it fires. A result that `settles` the matter
/// raises the other work's flag, so the other returns as soon as it polls.
/// A panic in either raises the other's flag too, and propagates to the
/// caller once both have ended.
pub(crate) fn race<T: Send>(
    runtimes: (&Runtime, &Runtime),
    stop: &mut dyn FnMut(u64) -> bool,
    done: &Work,
    work: (
        impl FnOnce(Flags<'_>) -> T + Send,
        impl FnOnce(Flags<'_>) -> T + Send,
    ),
    settles: impl Fn(&T) -> bool,
) -> (T, T) {
    let flags = [AtomicBool::new(false), AtomicBool::new(false)];
    let (sender, receiver) = channel();
    let mut results = (None, None);
    runtimes.0.pool.in_place_scope(|first| {
        runtimes.1.pool.in_place_scope(|second| {
            let flags = &flags;
            let other = sender.clone();
            first.spawn(move |_| {
                let _other = RaiseOnPanic(&flags[1]);
                let _ = sender.send((0, work.0(Flags::root(&flags[0], done))));
            });
            second.spawn(move |_| {
                let _other = RaiseOnPanic(&flags[0]);
                let _ = other.send((1, work.1(Flags::root(&flags[1], done))));
            });
            let _raise = [RaiseOnPanic(&flags[0]), RaiseOnPanic(&flags[1])];
            while results.0.is_none() || results.1.is_none() {
                match receiver.recv_timeout(POLL) {
                    Ok((i, result)) => {
                        if settles(&result) {
                            flags[1 - i].store(true, Ordering::Relaxed);
                        }
                        if i == 0 {
                            results.0 = Some(result);
                        } else {
                            results.1 = Some(result);
                        }
                    }
                    Err(RecvTimeoutError::Timeout) => {
                        if stop(0) {
                            flags[0].store(true, Ordering::Relaxed);
                            flags[1].store(true, Ordering::Relaxed);
                        }
                    }
                    // Both tasks ended and one without a result: it
                    // panicked, and its scope resumes the panic.
                    Err(RecvTimeoutError::Disconnected) => break,
                }
            }
        });
    });
    match results {
        (Some(first), Some(second)) => (first, second),
        _ => unreachable!("a task that ends without a result panicked, which its scope propagates"),
    }
}

/// The stop flags a worker polls: its own, which a sibling raises to
/// cancel it once their common alternative is settled, and its
/// ancestors', up to the root flag that the driver raises for the
/// caller's stop condition. A chain is as long as the nesting of parallel
/// choices, a few links at most.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Flags<'a> {
    /// This level's flag.
    flag: &'a AtomicBool,
    /// The enclosing level's flags.
    parent: Option<&'a Flags<'a>>,
    /// The search's work, which every worker adds to at its polls.
    work: &'a Work,
}

impl<'a> Flags<'a> {
    /// The root of a chain: the driver's flag, and the search's work.
    pub(crate) fn root(flag: &'a AtomicBool, work: &'a Work) -> Self {
        Self {
            flag,
            parent: None,
            work,
        }
    }

    /// A level below this one, with a flag of its own.
    pub(crate) fn child<'b>(&'b self, flag: &'b AtomicBool) -> Flags<'b>
    where
        'a: 'b,
    {
        Flags {
            flag,
            parent: Some(self),
            work: self.work,
        }
    }

    /// Counts `units` of work into the worker's `counted`, and returns
    /// whether the worker stops: the work passed its bound, or a flag of
    /// the chain is raised.
    #[inline(never)]
    pub(crate) fn fired(
        &self,
        units: u64,
        counted: &mut crate::linear::search::Counted<'_>,
    ) -> bool {
        counted.add(units);
        counted.passed() || self.raised()
    }

    /// A count of the search's work for a worker of this chain.
    pub(crate) const fn counted(&self) -> crate::linear::search::Counted<'a> {
        crate::linear::search::Counted::new(self.work)
    }

    /// Whether any flag of the chain is raised.
    pub(crate) fn raised(&self) -> bool {
        let mut level = Some(self);
        while let Some(flags) = level {
            if flags.flag.load(Ordering::Relaxed) {
                return true;
            }
            level = flags.parent;
        }
        false
    }
}

#[cfg(all(test, feature = "parse"))]
mod tests {
    use super::{Pool, threads};
    use crate::linear::fragment::Mode;
    use crate::linear::search::{Engine, Options, Verdict, prove};
    use std::sync::atomic::Ordering;

    /// Searches through one pool, on the net engine (forced) and on the
    /// focused one, share the one runtime the first built, and each
    /// verdict is that of a search on a runtime of its own.
    #[test]
    fn searches_share_a_kept_runtime() {
        let pool = Pool::new();
        let alone = Options::default().with_jobs(2);
        let pooled = alone.clone().with_pool(Some(pool.clone()));
        // A machine of one processor runs every search sequentially.
        let built = usize::from(threads(2) > 1);
        let cases = [
            ("a & b, c |- c * (b & a)", Engine::Focus, true),
            ("a * b |- b * a", Engine::Net, true),
            ("a + b, c |- c * (a & b)", Engine::Focus, false),
        ];
        for (text, engine, provable) in cases {
            let sequent = text.parse().unwrap();
            let forced = Some(engine).filter(|&e| e == Engine::Net);
            let (alone, pooled) = (
                alone.clone().with_engine(forced),
                pooled.clone().with_engine(forced),
            );
            let fresh = prove(&sequent, Mode::CLASSICAL, &alone).unwrap();
            let kept = prove(&sequent, Mode::CLASSICAL, &pooled).unwrap();
            assert_eq!(kept.engine, engine, "{text}");
            for outcome in [&fresh, &kept] {
                let verdict = &outcome.verdict;
                assert_eq!(matches!(verdict, Verdict::Proved(_)), provable, "{text}");
                assert_eq!(
                    matches!(verdict, Verdict::Unprovable(_)),
                    !provable,
                    "{text}"
                );
            }
            assert_eq!(pool.inner.built.load(Ordering::Relaxed), built, "{text}");
            assert_eq!(pool.idle().len(), built, "{text}");
        }
    }
}