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}