Skip to main content

deduxit/
limits.rs

1// deduxit © Fabian Lukas Grubmüller 2026
2// Licensed under the EUPL
3
4//! The resources a call may use, what a long call tells its stop, and why
5//! a call was refused without an answer.
6//!
7//! Every long call of the crate takes a [`Limits`] and a stop. The stop is
8//! a closure `FnMut(Progress) -> bool`. The call asks it after a bounded
9//! amount of work, and ends when it returns `true`; `|_| false` never
10//! stops. The crate reads no clock. A front end with a deadline reads its
11//! own clock in the stop, as often as the work done ([`Progress::work`])
12//! says it should. A call that a bound or the stop ends answers with a
13//! [`Refusal`], which is never a verdict on its input.
14//!
15//! The long calls, the fields of [`Limits`] that bound each, and how often
16//! each asks its stop:
17//!
18//! | call | bound by | asks the stop |
19//! |---|---|---|
20//! | `Sequent::parse_within`, `lltp::read`, `mist::read`, `ordinary::Sequent::parse_within`, `ordinary::read_tptp`, `wire::upgrade`, `wire::Within` | `occurrences` | never: linear in the input |
21//! | `Forest::within`, `Interactive::within`, `ordinary::translate` | `occurrences` | never: linear in the bound |
22//! | `search::prove_within`, `search::prove_goal` | `memory_bytes`, `recursion_depth`, `occurrences`, `work` (the search's and the check's) | at every node an engine searches, and in its long passes |
23//! | `search::batch::run`, `search::batch::prove` | each search's limits, the batch's memory shared out | through each problem's work, and `Results::cancel` |
24//! | `Proof::check_within` | `memory_bytes`, `work` | every 4 096 nodes or 65 536 units of work |
25//! | `proofs::cut::step`, `proofs::cut::eliminate` | `cut::Options::steps` and `nodes`; `memory_bytes` and `work` for each check, `memory_bytes` for a step's specialized erasure and the proof it makes | between steps, as each check does, and every 4 096 places a specialized erasure makes |
26//! | `Proof::derivation_size`, `Proof::derivation_within`, `Interactive::derivation_within` | `derivation_bytes`, `memory_bytes` | as the check, then at every inference built |
27//! | `Interactive::close`, `close_with`, `close_all`, `proof` | the search's and the derivation's | as the search and the derivation |
28//! | `ProofStructure::is_correct` | none: its memory is linear in the structure | at every round of the criterion |
29//! | `ProofStructure::from_proof`, `ProofStructure::sequentialize` | `memory_bytes` | at every node, at every stage |
30//! | `ordinary::Image::read_back`, `ordinary::Derivation::check` | `derivation_bytes`, `memory_bytes`; `work` inferences checked | at every inference |
31//! | `ordinary::decide` | all of the above it runs | as each step |
32//! | `ordinary::Interactive::within` | `occurrences` | never: linear in the bound |
33//! | `ordinary::Interactive::apply` | `derivation_bytes` of the start, for the run of structural rules an axiom or a shared rule makes, by an estimate before it is made | never: within the bound |
34//! | `ordinary::Interactive::close`, `hint` | as `ordinary::decide`; `derivation_bytes` for the graft | as `ordinary::decide` |
35//! | `ordinary::Interactive::derivation_within`, `finished` | `derivation_bytes` by an estimate before anything is built; `work` for the check | before building, then as the check |
36//! | `export::{latex, typst, svg, rocq}::write`, `Derivation::write_text`, `write_steps` | the derivation's, when it was made | at every inference written |
37//! | `export::{latex, typst, svg}::sequent` | `derivation_bytes`, by an estimate before anything is laid out | never: linear in the estimate |
38//! | `export::svg::net` | `derivation_bytes` | as the criterion |
39//! | `export::{png, pdf}::from_svg` | `memory_bytes`, the pixel bound of the options | never: refused before the render starts |
40
41use crate::errors::counted;
42use std::fmt::{self, Display, Formatter};
43
44#[cfg(feature = "serialize")]
45use serde::{Deserialize, Serialize};
46
47/// The resources a call may use, which the library enforces. `None` in an
48/// optional field means no bound. The defaults are the named constants.
49#[non_exhaustive]
50#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
51#[cfg_attr(
52    feature = "serialize",
53    derive(Serialize, Deserialize),
54    serde(default, deny_unknown_fields)
55)]
56pub struct Limits {
57    /// The most bytes a call holds at once: a search's growing structures,
58    /// a check's pass, a derivation's making, a render's estimate.
59    ///
60    /// A search counts its input too, the sequent and its forest. Other
61    /// calls do not: there the input is bounded by
62    /// [`occurrences`](Self::occurrences). The proof returned, the threads'
63    /// stacks and the allocator's own overhead are never counted.
64    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
65    pub memory_bytes: Option<u64>,
66    /// The most subformula occurrences a sequent may unfold to, on every
67    /// reader and wherever a forest is built. The text readers also refuse
68    /// a text nested deeper than the bound (more `(` or `~` open at once),
69    /// as if it had that many occurrences.
70    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
71    pub occurrences: Option<u64>,
72    /// The most first-order terms a sequent's atoms may unfold to
73    /// ([`Sequent::fo_size`](crate::linear::Sequent::fo_size)), and the most
74    /// entries a proof's instance table may hold, on every reader. A short
75    /// document of shared terms can name an atom of exponential length.
76    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
77    pub terms: Option<u64>,
78    /// The most bytes a derivation, or the drawing of a net or a sequent,
79    /// may be estimated at. Past it nothing is made.
80    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
81    pub derivation_bytes: Option<u64>,
82    /// The most units of work a call may do. The unit depends on the
83    /// call:
84    /// - the proof checker counts a node, or an entry of a sequent its
85    ///   rules handle;
86    /// - the ordinary checker counts an inference;
87    /// - a search counts its engine's unit, which each
88    ///   [`Engine`](crate::linear::search::Engine) variant names. Where
89    ///   another engine takes a goal over at an engine's limit, the units of
90    ///   both count together.
91    ///
92    /// A search past the bound is unknown with `Reason::WorkLimit`, and so
93    /// is a search whose proof's check passes it. A check alone refuses
94    /// with `Error::Check(CheckError::Refused)`.
95    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
96    pub work: Option<u64>,
97    /// The most atoms a truth table may have: its rows double with each.
98    /// [`DEFAULT_TABLE_ATOMS`](Self::DEFAULT_TABLE_ATOMS) by default.
99    pub table_atoms: Option<u32>,
100    /// The deepest recursion on any one stack. Every thread the library
101    /// starts is sized for it ([`stack_bytes`](Self::stack_bytes)).
102    ///
103    /// The focused engine takes a level per asynchronous phase, per stable
104    /// sequent and per focus. A chain of `⅋`, `⊥` and `?` rules, or of
105    /// forced splits, takes none. So a formula copied `k` times on a
106    /// branch takes `k` focus levels. The additive path takes a level per
107    /// pair.
108    pub recursion_depth: u32,
109    /// The bounds of a workspace of linked values
110    /// (`deduxit::workspace`), each refused at its edge.
111    pub workspace: WorkspaceLimits,
112}
113
114impl Limits {
115    /// The default memory bound: one gibibyte.
116    pub const DEFAULT_MEMORY_BYTES: u64 = 1 << 30;
117    /// The default bound on occurrences: fifty million, above the largest
118    /// problem of the LLTP library (27.8 million). A forest takes about
119    /// 25 bytes an occurrence.
120    pub const DEFAULT_OCCURRENCES: u64 = 50_000_000;
121    /// The default bound on first-order terms: as many as occurrences, so
122    /// that a sequent's terms take no more room than its forest.
123    pub const DEFAULT_TERMS: u64 = 50_000_000;
124    /// The default bound on a derivation's estimated size: 64 mebibytes.
125    pub const DEFAULT_DERIVATION_BYTES: u64 = 64 << 20;
126    /// The default bound on a truth table's atoms: ten, so 1024 rows, about
127    /// as many as a reader scans; a table that large is refused unless the
128    /// bound is raised.
129    pub const DEFAULT_TABLE_ATOMS: u32 = 10;
130    /// The default recursion depth: 2048 levels, which fit a main
131    /// thread's stack of 8 MiB in an optimized build.
132    pub const DEFAULT_RECURSION_DEPTH: u32 = 2048;
133
134    /// No bound but the default recursion depth, which every stack needs.
135    pub const UNBOUNDED: Self = Self {
136        memory_bytes: None,
137        occurrences: None,
138        terms: None,
139        derivation_bytes: None,
140        work: None,
141        table_atoms: None,
142        recursion_depth: Self::DEFAULT_RECURSION_DEPTH,
143        workspace: WorkspaceLimits::UNBOUNDED,
144    };
145
146    /// The stack one level of the search's recursion may take: twice the
147    /// most it was measured to take on x86-64. The deepest was a Mix of
148    /// pairs whose parts are recursed into (6.5 KiB unoptimized, 1.4 KiB
149    /// optimized), against a chain of tensors whose splits are searched
150    /// (5.8 KiB, 1.2 KiB) and nested `&` (1.4 KiB, 0.4 KiB).
151    const PER_LEVEL: usize = if cfg!(debug_assertions) { 13312 } else { 3072 };
152
153    /// What a thread needs besides the recursion: the frames of its caller,
154    /// the search's set-up and the check of its proof.
155    const RESERVE: usize = 1 << 20;
156
157    /// Returns the stack a thread needs to recurse to
158    /// [`recursion_depth`](Self::recursion_depth), at least a main
159    /// thread's 8 MiB.
160    #[must_use]
161    pub const fn stack_bytes(&self) -> usize {
162        let needed = (self.recursion_depth as usize)
163            .saturating_mul(Self::PER_LEVEL)
164            .saturating_add(Self::RESERVE);
165        if needed > 8 << 20 { needed } else { 8 << 20 }
166    }
167
168    /// Returns the deepest recursion a stack of `bytes` holds. It is the
169    /// inverse of [`stack_bytes`](Self::stack_bytes) above its floor of
170    /// 8 MiB.
171    #[must_use]
172    pub const fn recursion_depth_for_stack(bytes: usize) -> u32 {
173        let levels = bytes.saturating_sub(Self::RESERVE) / Self::PER_LEVEL;
174        if levels > u32::MAX as usize {
175            u32::MAX
176        } else {
177            levels as u32
178        }
179    }
180
181    /// Returns the limits with another memory bound.
182    #[must_use]
183    pub const fn with_memory_bytes(mut self, memory_bytes: Option<u64>) -> Self {
184        self.memory_bytes = memory_bytes;
185        self
186    }
187
188    /// Returns the limits with another bound on occurrences.
189    #[must_use]
190    pub const fn with_occurrences(mut self, occurrences: Option<u64>) -> Self {
191        self.occurrences = occurrences;
192        self
193    }
194
195    /// Returns the limits with another bound on first-order terms.
196    #[must_use]
197    pub const fn with_terms(mut self, terms: Option<u64>) -> Self {
198        self.terms = terms;
199        self
200    }
201
202    /// Returns the limits with another bound on a derivation's size.
203    #[must_use]
204    pub const fn with_derivation_bytes(mut self, derivation_bytes: Option<u64>) -> Self {
205        self.derivation_bytes = derivation_bytes;
206        self
207    }
208
209    /// Returns the limits with another bound on a search's work.
210    #[must_use]
211    pub const fn with_work(mut self, work: Option<u64>) -> Self {
212        self.work = work;
213        self
214    }
215
216    /// Returns the limits with another bound on a truth table's atoms.
217    #[must_use]
218    pub const fn with_table_atoms(mut self, table_atoms: Option<u32>) -> Self {
219        self.table_atoms = table_atoms;
220        self
221    }
222
223    /// Returns the limits with another recursion depth.
224    #[must_use]
225    pub const fn with_recursion_depth(mut self, recursion_depth: u32) -> Self {
226        self.recursion_depth = recursion_depth;
227        self
228    }
229
230    /// Returns the limits with other bounds of a workspace.
231    #[must_use]
232    pub const fn with_workspace(mut self, workspace: WorkspaceLimits) -> Self {
233        self.workspace = workspace;
234        self
235    }
236}
237
238impl Default for Limits {
239    /// Returns the default bounds, each a named constant.
240    fn default() -> Self {
241        Self {
242            memory_bytes: Some(Self::DEFAULT_MEMORY_BYTES),
243            occurrences: Some(Self::DEFAULT_OCCURRENCES),
244            terms: Some(Self::DEFAULT_TERMS),
245            derivation_bytes: Some(Self::DEFAULT_DERIVATION_BYTES),
246            work: None,
247            table_atoms: Some(Self::DEFAULT_TABLE_ATOMS),
248            recursion_depth: Self::DEFAULT_RECURSION_DEPTH,
249            workspace: WorkspaceLimits::default(),
250        }
251    }
252}
253
254/// The bounds of a workspace: how much of each thing it holds at once.
255/// `None` in a field means no bound.
256#[non_exhaustive]
257#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
258#[cfg_attr(
259    feature = "serialize",
260    derive(Serialize, Deserialize),
261    serde(default, deny_unknown_fields)
262)]
263pub struct WorkspaceLimits {
264    /// The most nodes alive.
265    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
266    pub nodes: Option<u64>,
267    /// The most records of runs kept; the oldest that no node shows and no
268    /// edit names give way first.
269    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
270    pub records: Option<u64>,
271    /// The most edits that undo can take back; the oldest is forgotten
272    /// past it, and a document past it is refused.
273    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
274    pub log: Option<u64>,
275    /// The most bytes of the values held, as their JSON's length.
276    #[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
277    pub bytes: Option<u64>,
278}
279
280impl WorkspaceLimits {
281    /// The default bound on nodes.
282    pub const DEFAULT_NODES: u64 = 1024;
283    /// The default bound on records.
284    pub const DEFAULT_RECORDS: u64 = 4096;
285    /// The default bound on the edits undo keeps.
286    pub const DEFAULT_LOG: u64 = 256;
287    /// The default bound on the values' bytes: 64 mebibytes.
288    pub const DEFAULT_BYTES: u64 = 64 << 20;
289
290    /// No bound.
291    pub const UNBOUNDED: Self = Self {
292        nodes: None,
293        records: None,
294        log: None,
295        bytes: None,
296    };
297
298    /// Returns the bounds with another bound on nodes.
299    #[must_use]
300    pub const fn with_nodes(mut self, nodes: Option<u64>) -> Self {
301        self.nodes = nodes;
302        self
303    }
304
305    /// Returns the bounds with another bound on records.
306    #[must_use]
307    pub const fn with_records(mut self, records: Option<u64>) -> Self {
308        self.records = records;
309        self
310    }
311
312    /// Returns the bounds with another bound on the edits kept.
313    #[must_use]
314    pub const fn with_log(mut self, log: Option<u64>) -> Self {
315        self.log = log;
316        self
317    }
318
319    /// Returns the bounds with another bound on bytes.
320    #[must_use]
321    pub const fn with_bytes(mut self, bytes: Option<u64>) -> Self {
322        self.bytes = bytes;
323        self
324    }
325}
326
327impl Default for WorkspaceLimits {
328    /// Returns the default bounds, each a named constant.
329    fn default() -> Self {
330        Self {
331            nodes: Some(Self::DEFAULT_NODES),
332            records: Some(Self::DEFAULT_RECORDS),
333            log: Some(Self::DEFAULT_LOG),
334            bytes: Some(Self::DEFAULT_BYTES),
335        }
336    }
337}
338
339/// What a [`Refusal::Workspace`] counts.
340#[non_exhaustive]
341#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
342#[cfg_attr(
343    feature = "serialize",
344    derive(Serialize),
345    serde(rename_all = "snake_case")
346)]
347pub enum Held {
348    /// Nodes alive.
349    Nodes,
350    /// Records of runs kept.
351    Records,
352    /// Edits in the log, of a document read.
353    Log,
354    /// Bytes of the values held.
355    Bytes,
356}
357
358impl Held {
359    /// Returns the settings key of its bound.
360    pub const fn setting(self) -> &'static str {
361        match self {
362            Self::Nodes => "limits.workspace.nodes",
363            Self::Records => "limits.workspace.records",
364            Self::Log => "limits.workspace.log",
365            Self::Bytes => "limits.workspace.bytes",
366        }
367    }
368
369    /// Returns its name in the plural, for a message.
370    const fn plural(self) -> &'static str {
371        match self {
372            Self::Nodes => "nodes",
373            Self::Records => "records",
374            Self::Log => "edits",
375            Self::Bytes => "bytes",
376        }
377    }
378}
379
380/// What a long call tells its stop each time it asks it.
381#[non_exhaustive]
382#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
383#[cfg_attr(feature = "serialize", derive(Serialize))]
384pub struct Progress {
385    /// The units of work done since the previous poll, in the unit of
386    /// [`Limits::work`].
387    pub work: u64,
388    /// The units of work done since the call began.
389    pub done: u64,
390    /// The bytes the call holds now, by its own count. The proof checker's
391    /// pass and the calls built on it fill it in. The net calls give their
392    /// estimate, and the criterion alone its working memory. A search
393    /// leaves it zero, since the two searches of its default bias each
394    /// count their own share.
395    pub held_bytes: u64,
396    /// What the call is doing.
397    pub phase: Phase,
398    /// The place of the item being worked on, in a call that runs several:
399    /// a goal of a session's `close_all`. Zero for every other call.
400    pub item: u32,
401}
402
403impl Progress {
404    /// Returns the progress of a call in `phase` that has done `done`
405    /// units of work, `work` of them since the previous poll.
406    pub(crate) const fn new(phase: Phase, work: u64, done: u64) -> Self {
407        Self {
408            work,
409            done,
410            held_bytes: 0,
411            phase,
412            item: 0,
413        }
414    }
415}
416
417/// What a long call is doing when it asks its stop or is refused.
418#[non_exhaustive]
419#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
420#[cfg_attr(
421    feature = "serialize",
422    derive(Serialize),
423    serde(rename_all = "snake_case")
424)]
425pub enum Phase {
426    /// Reading an input.
427    #[default]
428    Read,
429    /// Searching for a proof.
430    Search,
431    /// Refuting a sequent after a search.
432    Refute,
433    /// Checking a proof.
434    Check,
435    /// Making a derivation.
436    View,
437    /// Writing a derivation in a format.
438    Write,
439    /// Rendering a drawing.
440    Render,
441    /// Building or judging a proof net.
442    Net,
443    /// Reading a proof back as one of ordinary logic or as a lambda-term.
444    ReadBack,
445    /// Eliminating the cuts of a proof.
446    Eliminate,
447}
448
449impl Phase {
450    /// Returns the phase as a lowercase noun phrase, as messages use it.
451    pub const fn name(self) -> &'static str {
452        match self {
453            Self::Read => "reading",
454            Self::Search => "search",
455            Self::Refute => "refutation",
456            Self::Check => "check",
457            Self::View => "derivation",
458            Self::Write => "writing",
459            Self::Render => "render",
460            Self::Net => "net",
461            Self::ReadBack => "read-back",
462            Self::Eliminate => "elimination",
463        }
464    }
465}
466
467/// What a count of [`Refusal::Index`] counts: the spaces whose indices
468/// have a fixed width.
469#[non_exhaustive]
470#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
471#[cfg_attr(
472    feature = "serialize",
473    derive(Serialize),
474    serde(rename_all = "snake_case")
475)]
476pub enum Space {
477    /// The atoms of a sequent.
478    Atom,
479    /// The terms of a sequent's arena.
480    Term,
481    /// The nodes of a proof.
482    Node,
483    /// The occurrences of a forest.
484    Occurrence,
485    /// The members of a sequent of a proof, a derivation or a session.
486    Member,
487    /// The vertices of a proof structure.
488    Vertex,
489    /// The inferences of a derivation.
490    Inference,
491    /// The formulas of an ordinary arena.
492    Formula,
493    /// The symbols of a sequent's first-order tables.
494    Symbol,
495    /// The worlds of a Kripke model.
496    World,
497    /// The scopes of a derivation in a calculus given as data.
498    Scope,
499}
500
501impl Space {
502    /// Returns the noun that names one member of the space.
503    pub(crate) const fn singular(self) -> &'static str {
504        match self {
505            Self::Atom => "atom",
506            Self::Term => "term",
507            Self::Node => "node",
508            Self::Occurrence => "occurrence",
509            Self::Member => "member",
510            Self::Vertex => "vertex",
511            Self::Inference => "inference",
512            Self::Formula => "formula",
513            Self::Symbol => "symbol",
514            Self::World => "world",
515            Self::Scope => "scope",
516        }
517    }
518
519    /// Returns the plural noun that counts members of the space.
520    pub const fn plural(self) -> &'static str {
521        match self {
522            Self::Atom => "atoms",
523            Self::Term => "terms",
524            Self::Node => "nodes",
525            Self::Occurrence => "occurrences",
526            Self::Member => "members",
527            Self::Vertex => "vertices",
528            Self::Inference => "inferences",
529            Self::Formula => "formulas",
530            Self::Symbol => "symbols",
531            Self::World => "worlds",
532            Self::Scope => "scopes",
533        }
534    }
535}
536
537/// Which bound of cut elimination a [`Refusal::Elimination`] reached.
538#[non_exhaustive]
539#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
540#[cfg_attr(
541    feature = "serialize",
542    derive(Serialize),
543    serde(rename_all = "snake_case")
544)]
545pub enum Bound {
546    /// The number of steps.
547    Steps,
548    /// The nodes of a proof a step makes.
549    Nodes,
550    /// The vertices of a proof net a step makes.
551    Vertices,
552}
553
554/// Why a call was given up without an answer: a bound, set or default,
555/// refused it, or the caller's stop ended it. A refusal says nothing of
556/// the input. With the bound lifted, the call may answer.
557#[non_exhaustive]
558#[derive(Clone, Debug, PartialEq, Eq)]
559#[cfg_attr(
560    feature = "serialize",
561    derive(Serialize),
562    serde(tag = "kind", rename_all = "snake_case")
563)]
564pub enum Refusal {
565    /// The caller's stop ended the call.
566    #[non_exhaustive]
567    Stopped {
568        /// What the call was doing.
569        phase: Phase,
570    },
571    /// The call would have held more memory than its bound.
572    #[non_exhaustive]
573    Memory {
574        /// What the call was doing.
575        phase: Phase,
576        /// The bound, [`Limits::memory_bytes`].
577        limit_bytes: u64,
578        /// What the call would have needed, where it was estimated before
579        /// anything was made.
580        needed_bytes: Option<u64>,
581    },
582    /// A sequent unfolds to more occurrences than the bound. The count is
583    /// exact, or the number at which counting stopped.
584    #[non_exhaustive]
585    Occurrences {
586        /// How many occurrences, or a number past the bound.
587        occurrences: u64,
588        /// The bound, [`Limits::occurrences`].
589        limit: u64,
590    },
591    /// A sequent's atoms unfold to more first-order terms than the bound,
592    /// or a proof's instance table holds more entries. The count is exact,
593    /// or the number at which counting stopped.
594    #[non_exhaustive]
595    Terms {
596        /// How many terms or entries, or a number past the bound.
597        terms: u64,
598        /// The bound, [`Limits::terms`].
599        limit: u64,
600    },
601    /// An output is estimated past its bound. Nothing was made.
602    #[non_exhaustive]
603    Output {
604        /// What was to be made: a derivation, a drawing.
605        what: &'static str,
606        /// The estimate.
607        estimate_bytes: u64,
608        /// The bound, [`Limits::derivation_bytes`].
609        limit_bytes: u64,
610        /// The least a smaller form of the output would take, where one
611        /// was tried: a compact derivation's lower bound.
612        least_bytes: Option<u64>,
613    },
614    /// A call did the most work its bound allows.
615    #[non_exhaustive]
616    Work {
617        /// The bound, [`Limits::work`].
618        limit: u64,
619    },
620    /// An image would have more pixels than its options allow.
621    #[non_exhaustive]
622    Pixels {
623        /// The image's pixels.
624        pixels: u64,
625        /// The bound of the image's options.
626        limit: u64,
627    },
628    /// Cut elimination reached its bound on steps or on a proof's nodes.
629    #[non_exhaustive]
630    Elimination {
631        /// The bound reached.
632        what: Bound,
633        /// Its value, [`cut::Options::steps`](crate::linear::proofs::cut::Options::steps)
634        /// or [`cut::Options::nodes`](crate::linear::proofs::cut::Options::nodes).
635        limit: u64,
636    },
637    /// A truth table would have more atoms than the bound, and so more
638    /// rows than it allows.
639    #[non_exhaustive]
640    Atoms {
641        /// The sequent's atoms.
642        atoms: u64,
643        /// The bound, [`Limits::table_atoms`].
644        limit: u64,
645    },
646    /// A workspace would hold more than a bound of
647    /// [`Limits::workspace`] allows.
648    #[non_exhaustive]
649    Workspace {
650        /// What is counted.
651        what: Held,
652        /// The count.
653        count: u64,
654        /// The bound.
655        limit: u64,
656    },
657    /// A count passes what a representation's indices can name, whatever
658    /// the bounds say.
659    #[non_exhaustive]
660    Index {
661        /// What is counted.
662        what: Space,
663        /// The count, or a number past the most.
664        count: u64,
665        /// The most the representation holds.
666        most: u64,
667    },
668}
669
670impl Refusal {
671    /// Returns the stable name of the refusal that a program branches on.
672    pub const fn code(&self) -> &'static str {
673        match self {
674            Self::Stopped { .. } => "stopped",
675            Self::Memory { .. } => "memory_limit",
676            Self::Occurrences { .. } => "too_many_occurrences",
677            Self::Terms { .. } => "too_many_terms",
678            Self::Output { .. } => "output_too_large",
679            Self::Work { .. } => "work_limit",
680            Self::Pixels { .. } => "too_many_pixels",
681            Self::Elimination { .. } => "elimination_limit",
682            Self::Atoms { .. } => "too_many_atoms",
683            Self::Workspace { .. } => "workspace_limit",
684            Self::Index { .. } => "index_limit",
685        }
686    }
687
688    /// Returns the settings key whose bound refused the call. `None` for
689    /// the stop and for a representation's width, which no setting lifts.
690    pub const fn setting(&self) -> Option<&'static str> {
691        match self {
692            Self::Memory { .. } => Some("limits.memory_bytes"),
693            Self::Occurrences { .. } => Some("limits.occurrences"),
694            Self::Terms { .. } => Some("limits.terms"),
695            Self::Output { .. } => Some("limits.derivation_bytes"),
696            Self::Work { .. } => Some("limits.work"),
697            Self::Atoms { .. } => Some("limits.table_atoms"),
698            Self::Workspace { what, .. } => Some(what.setting()),
699            Self::Pixels { .. } => Some("styles.png.pixels"),
700            Self::Elimination {
701                what: Bound::Steps, ..
702            } => Some("cut.steps"),
703            Self::Elimination {
704                what: Bound::Nodes | Bound::Vertices,
705                ..
706            } => Some("cut.nodes"),
707            Self::Stopped { .. } | Self::Index { .. } => None,
708        }
709    }
710
711    /// Returns whether the caller's stop ended the call, not a bound.
712    pub const fn is_stop(&self) -> bool {
713        matches!(self, Self::Stopped { .. })
714    }
715}
716
717impl Display for Refusal {
718    /// Writes the reason in a sentence without a full stop.
719    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
720        match self {
721            Self::Stopped { phase } => write!(f, "the {} was stopped", phase.name()),
722            Self::Memory {
723                phase,
724                limit_bytes,
725                needed_bytes: Some(needed),
726            } => write!(
727                f,
728                "the {} would take {}, more than the memory limit of {}",
729                phase.name(),
730                counted(*needed, "byte", "bytes"),
731                counted(*limit_bytes, "byte", "bytes")
732            ),
733            Self::Memory {
734                phase,
735                limit_bytes,
736                needed_bytes: None,
737            } => write!(
738                f,
739                "the {} takes more than the memory limit of {}",
740                phase.name(),
741                counted(*limit_bytes, "byte", "bytes")
742            ),
743            Self::Occurrences { occurrences, limit } => write!(
744                f,
745                "the sequent unfolds to at least {}, more than the limit of {limit}",
746                counted(
747                    *occurrences,
748                    "subformula occurrence",
749                    "subformula occurrences"
750                )
751            ),
752            Self::Terms { terms, limit } => write!(
753                f,
754                "the first-order terms unfold to at least {}, more than the limit of {limit}",
755                counted(*terms, "term", "terms")
756            ),
757            Self::Output {
758                what,
759                estimate_bytes,
760                limit_bytes,
761                least_bytes,
762            } => {
763                write!(
764                    f,
765                    "the {what} is estimated at {}, more than the limit of {limit_bytes}",
766                    counted(*estimate_bytes, "byte", "bytes")
767                )?;
768                match least_bytes {
769                    Some(least) => write!(
770                        f,
771                        ", and a compact one at {} at least",
772                        counted(*least, "byte", "bytes")
773                    ),
774                    None => Ok(()),
775                }
776            }
777            Self::Work { limit } => {
778                write!(
779                    f,
780                    "the call did the most work allowed, {}",
781                    counted(*limit, "unit", "units")
782                )
783            }
784            Self::Pixels { pixels, limit } => write!(
785                f,
786                "the image would have {}, more than the limit of {limit}",
787                counted(*pixels, "pixel", "pixels")
788            ),
789            Self::Elimination {
790                what: Bound::Steps,
791                limit,
792            } => write!(f, "the elimination took the most steps allowed, {limit}"),
793            Self::Elimination {
794                what: Bound::Nodes,
795                limit,
796            } => write!(
797                f,
798                "the next step of the elimination makes a proof of more than {}",
799                counted(*limit, "node", "nodes")
800            ),
801            Self::Elimination {
802                what: Bound::Vertices,
803                limit,
804            } => write!(
805                f,
806                "the next step of the elimination makes a net of more than {}",
807                counted(*limit, "vertex", "vertices")
808            ),
809            Self::Atoms { atoms, limit } => write!(
810                f,
811                "the truth table of {} would have 2^{atoms} rows, more than the limit of {} \
812                 allows",
813                counted(*atoms, "atom", "atoms"),
814                counted(*limit, "atom", "atoms")
815            ),
816            Self::Workspace { what, count, limit } => write!(
817                f,
818                "the workspace would hold {count} {}, more than the limit of {limit}",
819                what.plural()
820            ),
821            Self::Index { what, count, most } => write!(
822                f,
823                "{count} {} are more than this representation can index ({most})",
824                what.plural()
825            ),
826        }
827    }
828}
829
830impl std::error::Error for Refusal {}
831
832/// Turns a stop into the plain condition that a loop asks once per unit
833/// of work in `phase`. Each call tells the stop one unit and the units
834/// done.
835pub(crate) fn counting(
836    mut stop: impl FnMut(Progress) -> bool,
837    phase: Phase,
838) -> impl FnMut() -> bool {
839    let mut done = 0u64;
840    move || {
841        done = done.saturating_add(1);
842        stop(Progress::new(phase, 1, done))
843    }
844}