axiolid_overlay/
budget.rs

1//! A memory budget for the straight-edge boolean (#338).
2//!
3//! [`crate::overlay_within`] and [`crate::union_soup_within`] read the
4//! caller's [`axiolid_contracts::ExecutionOptions::memory_budget_bytes`].
5//! The subdivision charges what it is about to hold before it allocates
6//! it, and refuses with [`OverlayRefusal::BudgetExceeded`] as soon as the
7//! charges pass the budget:
8//!
9//! - the operands' rings, by vertex, before they are snapped and reduced;
10//! - the edges, before their boxes, trees and winding parts are built;
11//! - every point a pair of edges meets at, before it is recorded (the
12//!   pairs come from the box tree, so this stops a soup whose edges cross
13//!   far more often than its output has corners before those crossings
14//!   are held);
15//! - the pieces, counted from the recorded points, before any is built;
16//! - each piece's rings and carriers, as they are found.
17//!
18//! The charges are upper bounds on the heap each holds, measured with a
19//! counting allocator by `tests/overlay_budget.rs` (which also checks that
20//! a call never holds more than its budget, refused or not), so a call
21//! admitted holds at most its budget in the subdivision, and a refused
22//! call stops before it. Without a budget nothing is refused: the charges
23//! are counted and never compared. The rounding and settling of the
24//! output hold about the output, which no budget refuses.
25
26use crate::OverlayError;
27
28/// Bytes charged per input vertex: the copies the snap and the chain
29/// reduction take, and the rings handed to the subdivision.
30pub(crate) const PER_VERTEX: usize = 320;
31/// Bytes charged per edge of the subdivision: the edge, its boxes in the
32/// edge tree, its winding part and tree, and its first two stops.
33pub(crate) const PER_EDGE: usize = 2_000;
34/// Bytes charged per point recorded on an edge: the meeting, with room
35/// for its vector to double.
36pub(crate) const PER_MEETING: usize = 400;
37/// Bytes charged per crossing computed once for repeated segments.
38pub(crate) const PER_SHARED_CROSSING: usize = 200;
39/// Bytes charged per piece: the piece, its raw edge, its stop, its
40/// interned vertex and its share of the linking.
41pub(crate) const PER_PIECE: usize = 600;
42/// Bytes charged per ring containing or carrying a piece.
43pub(crate) const PER_MEMBER: usize = 40;
44
45/// Why a budgeted overlay gave no result.
46#[derive(Debug, Clone, PartialEq, Eq)]
47#[non_exhaustive]
48pub enum OverlayRefusal {
49    /// An operand failed the overlay's checks, as [`crate::overlay_with`]
50    /// and [`crate::union_soup_with`] refuse it.
51    Invalid(OverlayError),
52    /// The subdivision would hold more than the memory budget: refused
53    /// before allocating past it. `needed` is what had been charged when
54    /// the budget was passed, a lower bound on what the operation needs;
55    /// `budget` is the caller's.
56    BudgetExceeded {
57        /// Bytes charged when the budget was passed.
58        needed: usize,
59        /// The caller's memory budget in bytes.
60        budget: usize,
61    },
62}
63
64impl From<OverlayError> for OverlayRefusal {
65    fn from(error: OverlayError) -> Self {
66        Self::Invalid(error)
67    }
68}
69
70impl std::fmt::Display for OverlayRefusal {
71    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
72        match self {
73            Self::Invalid(error) => write!(f, "invalid overlay operand: {error}"),
74            Self::BudgetExceeded { needed, budget } => write!(
75                f,
76                "overlay exceeded its memory budget: {needed} bytes charged, {budget} allowed"
77            ),
78        }
79    }
80}
81
82impl std::error::Error for OverlayRefusal {
83    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
84        match self {
85            Self::Invalid(error) => Some(error),
86            Self::BudgetExceeded { .. } => None,
87        }
88    }
89}
90
91/// The running charge against an optional budget.
92#[derive(Debug, Clone, Copy)]
93pub(crate) struct Charge {
94    budget: Option<usize>,
95    used: usize,
96}
97
98impl Charge {
99    /// No budget: every charge is admitted.
100    pub(crate) const fn unlimited() -> Self {
101        Self {
102            budget: None,
103            used: 0,
104        }
105    }
106
107    /// A charge against `budget` bytes, if any.
108    pub(crate) const fn within(budget: Option<usize>) -> Self {
109        Self { budget, used: 0 }
110    }
111
112    /// Charge `count` items of `each` bytes before allocating them.
113    pub(crate) fn add(&mut self, count: usize, each: usize) -> Result<(), OverlayRefusal> {
114        self.used = self.used.saturating_add(count.saturating_mul(each));
115        match self.budget {
116            Some(budget) if self.used > budget => Err(OverlayRefusal::BudgetExceeded {
117                needed: self.used,
118                budget,
119            }),
120            _ => Ok(()),
121        }
122    }
123}
124
125/// The error of an unbudgeted call: an unlimited charge never refuses.
126pub(crate) fn unbudgeted(refusal: OverlayRefusal) -> OverlayError {
127    match refusal {
128        OverlayRefusal::Invalid(error) => error,
129        OverlayRefusal::BudgetExceeded { .. } => {
130            unreachable!("an unlimited charge admits every charge")
131        }
132    }
133}
axiolid_overlay/budget.rs

axiolid_overlay/
budget.rs
