Skip to main content

meshoptimizer_rs/
workspace.rs

1use crate::Error;
2use alloc::vec::Vec;
3use core::mem::size_of;
4
5/// Per-call limits for crate-owned heap storage and counted work.
6#[derive(Clone, Copy, Debug, PartialEq, Eq)]
7pub struct Limits {
8    /// Maximum output plus retained scratch capacity, excluding caller buffers
9    /// and allocator overhead. Defaults to 1 GiB. Scratch is reused when it fits;
10    /// unused retained storage and excess active capacity are reclaimed under
11    /// limit pressure.
12    pub max_bytes: usize,
13    /// Maximum counted record visits. Defaults to 2^34.
14    pub max_work: u64,
15}
16
17impl Default for Limits {
18    fn default() -> Self {
19        Self {
20            max_bytes: 1 << 30,
21            max_work: 1 << 34,
22        }
23    }
24}
25
26/// Resource measurements for the most recent algorithm call.
27#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
28pub struct Usage {
29    /// Crate-owned output bytes plus retained heap scratch capacity.
30    pub bytes: usize,
31    /// Counted record visits actually performed, including validation.
32    pub work: u64,
33}
34
35#[derive(Clone, Copy, Debug, Default)]
36pub(crate) struct CacheVertex {
37    pub(crate) live: u32,
38    pub(crate) offset: u32,
39    pub(crate) score: f32,
40}
41
42/// Policy for retaining reusable algorithm scratch between calls.
43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
44pub enum Retention {
45    /// Reuse scratch across calls and algorithm families (the default).
46    #[default]
47    Reuse,
48    /// Release the previous family's scratch when simplify, cache or overdraw
49    /// acquires storage, release simplify position quadrics on return, and defer
50    /// initialization of simplify ordering entries until needed.
51    ///
52    /// Measured on 214e: peak RSS 2.85 → 2.20 GiB, with simplify-heavy chains
53    /// taking up to 1.20× wall time.
54    /// Other algorithm families keep their existing retention behavior.
55    Lean,
56}
57
58/// Reusable fallibly allocated scratch storage and per-call resource limits.
59///
60/// Cache work counts topology/index validation, each adjacency initialization,
61/// insertion, search and score update, and each cache/emission visit. Overdraw
62/// work counts validation, cache simulation, geometry and counting-sort record
63/// visits, and copied indices. Fixed scalar arithmetic inside a visit is not
64/// counted separately. Simplification counts validation, position/hash and
65/// adjacency visits, edge searches, classification, quadric and attribute
66/// accumulation, collapse ranking/sorting/flip checks, and remapping visits.
67/// Its typed scratch is allocated fallibly and retained after successful calls;
68/// retained scratch is reused when it fits and released under limit pressure,
69/// including excess capacity in buffers the current call uses.
70/// Use [`Self::set_retention`] to opt into [`Retention::Lean`].
71/// Usage reports peak storage including all retained workspace buffers. Scale
72/// computation is allocation-free and has no workspace argument.
73/// Limits never disable checked size arithmetic.
74#[derive(Debug, Default)]
75pub struct Workspace {
76    limits: Limits,
77    pub(crate) lod_error_limited: bool,
78    active: [bool; 5],
79    family: Option<ScratchFamily>,
80    retention: Retention,
81    usage: Usage,
82    pub(crate) has_retained: bool,
83    pub(crate) simplify: Option<crate::simplify::State>,
84    pub(crate) sloppy: Option<crate::simplify::SloppyScratch>,
85    pub(crate) vertices: Vec<CacheVertex>,
86    pub(crate) integers: Vec<u32>,
87    pub(crate) floats: Vec<f32>,
88    pub(crate) flags: Vec<u8>,
89    pub(crate) keys: Vec<u16>,
90}
91
92// Only the LOD-chain families opt into switching; codecs and other algorithms
93// retain their existing workspace behavior.
94#[derive(Clone, Copy, Debug, PartialEq, Eq)]
95pub(crate) enum ScratchFamily {
96    Simplify,
97    Cache,
98    Overdraw,
99}
100
101impl Workspace {
102    /// Create an empty workspace with explicit limits.
103    pub fn new(limits: Limits) -> Self {
104        Self {
105            limits,
106            ..Self::default()
107        }
108    }
109    pub(crate) fn set_lod_limits(&mut self, limits: Limits) {
110        self.limits = limits;
111    }
112    /// Replace the last call's measurements with a composite call's totals.
113    pub(crate) fn set_lod_usage(&mut self, usage: Usage) {
114        self.usage = usage;
115    }
116    /// Current scratch retention policy.
117    pub const fn retention(&self) -> Retention {
118        self.retention
119    }
120    /// Set the retention policy, releasing scratch and resetting measurements
121    /// if the policy changes. Limits are preserved; [`Self::clear`] and
122    /// [`Self::set_limits`] preserve this policy.
123    pub fn set_retention(&mut self, retention: Retention) {
124        if self.retention != retention {
125            self.clear();
126            self.retention = retention;
127        }
128    }
129    /// Current per-call limits.
130    pub const fn limits(&self) -> Limits {
131        self.limits
132    }
133    /// Set limits and release scratch so a lower budget is effective immediately.
134    pub fn set_limits(&mut self, limits: Limits) {
135        self.clear();
136        self.limits = limits;
137    }
138    /// Release all retained scratch allocations and reset measurements.
139    pub fn clear(&mut self) {
140        self.simplify = None;
141        self.sloppy = None;
142        self.vertices = Vec::new();
143        self.integers = Vec::new();
144        self.floats = Vec::new();
145        self.flags = Vec::new();
146        self.keys = Vec::new();
147        self.usage = Usage::default();
148        self.has_retained = false;
149        self.family = None;
150    }
151    #[inline]
152    pub(crate) fn acquire(&mut self, family: ScratchFamily) {
153        if self.retention == Retention::Lean && self.family != Some(family) {
154            // Acquisition precedes reservations, so none of the previous
155            // contents belong to the current call. Preserve its measurements,
156            // work counter and limits; clear() would reset the measurements.
157            self.simplify = None;
158            self.sloppy = None;
159            self.vertices = Vec::new();
160            self.integers = Vec::new();
161            self.floats = Vec::new();
162            self.flags = Vec::new();
163            self.keys = Vec::new();
164            self.has_retained = false;
165            self.family = Some(family);
166        }
167    }
168    /// Measurements for the most recent call, including a failed call's work.
169    pub const fn usage(&self) -> Usage {
170        self.usage
171    }
172    #[inline]
173    pub(crate) fn begin(&mut self) -> Work {
174        self.usage = Usage::default();
175        self.active = [false; 5];
176        Work {
177            remaining: self.limits.max_work,
178            limit: self.limits.max_work,
179        }
180    }
181    #[inline]
182    pub(crate) fn finish(&mut self, work: &Work) {
183        self.usage.work = work.limit - work.remaining;
184    }
185    // Local budgets re-read capacities after pressure can evict unused buffers.
186    #[inline]
187    pub(crate) fn retained_bytes(&self) -> Result<usize, Error> {
188        if !self.has_retained {
189            debug_assert!(self.simplify.is_none() && self.sloppy.is_none());
190            debug_assert_eq!(
191                self.integers.capacity()
192                    | self.floats.capacity()
193                    | self.flags.capacity()
194                    | self.keys.capacity()
195                    | self.vertices.capacity(),
196                0
197            );
198            return Ok(0);
199        }
200        total(
201            [
202                self.integers.capacity(),
203                self.floats.capacity(),
204                self.flags.capacity(),
205                self.keys.capacity(),
206            ],
207            checked_bytes(self.vertices.capacity(), size_of::<CacheVertex>())?
208                .checked_add(
209                    self.simplify
210                        .as_ref()
211                        .map_or(Ok(0), |s| s.capacity_bytes())?,
212                )
213                .ok_or(Error::SizeOverflow)?
214                .checked_add(self.sloppy.as_ref().map_or(Ok(0), |s| s.capacity_bytes())?)
215                .ok_or(Error::SizeOverflow)?,
216        )
217    }
218    #[inline]
219    pub(crate) fn charge_owned(&mut self, owned: usize) -> Result<(), Error> {
220        let mut bytes = self
221            .retained_bytes()?
222            .checked_add(owned)
223            .ok_or(Error::SizeOverflow)?;
224        if bytes > self.limits.max_bytes {
225            // Local typed scratch has already been taken out of the workspace.
226            // Buffers prepared by this call remain live and must stay charged.
227            self.simplify = None;
228            self.sloppy = None;
229            if !self.active[0] {
230                self.integers = Vec::new();
231            }
232            if !self.active[1] {
233                self.floats = Vec::new();
234            }
235            if !self.active[2] {
236                self.flags = Vec::new();
237            }
238            if !self.active[3] {
239                self.keys = Vec::new();
240            }
241            if !self.active[4] {
242                self.vertices = Vec::new();
243            }
244            bytes = self
245                .retained_bytes()?
246                .checked_add(owned)
247                .ok_or(Error::SizeOverflow)?;
248            if bytes > self.limits.max_bytes {
249                self.shrink_active()?;
250                bytes = self
251                    .retained_bytes()?
252                    .checked_add(owned)
253                    .ok_or(Error::SizeOverflow)?;
254            }
255        }
256        if bytes > self.limits.max_bytes {
257            return Err(Error::LimitExceeded);
258        }
259        self.usage.bytes = self.usage.bytes.max(bytes);
260        Ok(())
261    }
262    fn shrink_active(&mut self) -> Result<(), Error> {
263        shrink(&mut self.integers, self.active[0])?;
264        shrink(&mut self.floats, self.active[1])?;
265        shrink(&mut self.flags, self.active[2])?;
266        shrink(&mut self.keys, self.active[3])?;
267        shrink(&mut self.vertices, self.active[4])
268    }
269    #[cfg(any(feature = "clusterlod", feature = "parallel"))]
270    pub(crate) fn release_unused(&mut self) {
271        self.simplify = None;
272        self.sloppy = None;
273        self.vertices = Vec::new();
274        self.integers = Vec::new();
275        self.floats = Vec::new();
276        self.flags = Vec::new();
277        self.keys = Vec::new();
278    }
279    #[inline]
280    pub(crate) fn charge_retained(&mut self) -> Result<(), Error> {
281        self.charge_owned(0)
282    }
283    pub(crate) fn prepare(&mut self, lengths: [usize; 4], output: usize) -> Result<(), Error> {
284        self.prepare_cache(lengths, 0, output)
285    }
286    pub(crate) fn prepare_remap(&mut self, vertices: usize, output: usize) -> Result<(), Error> {
287        let previous = self.integers.len();
288        self.prepare_cache_value([vertices, 0, 0, 0], 0, output, u32::MAX)?;
289        self.integers[..previous.min(vertices)].fill(u32::MAX);
290        Ok(())
291    }
292    pub(crate) fn prepare_cache(
293        &mut self,
294        lengths: [usize; 4],
295        vertices: usize,
296        output: usize,
297    ) -> Result<(), Error> {
298        self.prepare_cache_value(lengths, vertices, output, 0)
299    }
300    #[inline(always)]
301    pub(crate) fn prepare_timestamps(&mut self, count: usize) -> Result<(), Error> {
302        self.prepare_cache_value([count, 0, 0, 0], 0, 0, 0)
303    }
304    #[inline(always)]
305    fn prepare_cache_value(
306        &mut self,
307        lengths: [usize; 4],
308        vertices: usize,
309        output: usize,
310        integer_value: u32,
311    ) -> Result<(), Error> {
312        let [i, f, b, k] = lengths;
313        let mut simplify_bytes = self
314            .simplify
315            .as_ref()
316            .map_or(Ok(0), |s| s.capacity_bytes())?
317            .checked_add(self.sloppy.as_ref().map_or(Ok(0), |s| s.capacity_bytes())?)
318            .ok_or(Error::SizeOverflow)?;
319        let vertex_bytes = checked_bytes(
320            vertices.max(self.vertices.capacity()),
321            size_of::<CacheVertex>(),
322        )?;
323        let owned = output
324            .checked_add(vertex_bytes)
325            .and_then(|n| n.checked_add(simplify_bytes))
326            .ok_or(Error::SizeOverflow)?;
327        let bytes = total(
328            [
329                i.max(self.integers.capacity()),
330                f.max(self.floats.capacity()),
331                b.max(self.flags.capacity()),
332                k.max(self.keys.capacity()),
333            ],
334            owned,
335        )?;
336        if bytes > self.limits.max_bytes {
337            self.simplify = None;
338            self.sloppy = None;
339            if (!self.active[0] || i == 0) && self.integers.capacity() > i {
340                self.integers = Vec::new();
341            }
342            if (!self.active[1] || f == 0) && self.floats.capacity() > f {
343                self.floats = Vec::new();
344            }
345            if (!self.active[2] || b == 0) && self.flags.capacity() > b {
346                self.flags = Vec::new();
347            }
348            if (!self.active[3] || k == 0) && self.keys.capacity() > k {
349                self.keys = Vec::new();
350            }
351            if (!self.active[4] || vertices == 0) && self.vertices.capacity() > vertices {
352                self.vertices = Vec::new();
353            }
354            simplify_bytes = 0;
355            let minimum = total(
356                [
357                    i.max(self.integers.capacity()),
358                    f.max(self.floats.capacity()),
359                    b.max(self.flags.capacity()),
360                    k.max(self.keys.capacity()),
361                ],
362                output
363                    .checked_add(checked_bytes(
364                        vertices.max(self.vertices.capacity()),
365                        size_of::<CacheVertex>(),
366                    )?)
367                    .ok_or(Error::SizeOverflow)?,
368            )?;
369            if minimum > self.limits.max_bytes {
370                let needed = total(
371                    lengths,
372                    output
373                        .checked_add(checked_bytes(vertices, size_of::<CacheVertex>())?)
374                        .ok_or(Error::SizeOverflow)?,
375                )?;
376                if needed > self.limits.max_bytes {
377                    return Err(Error::LimitExceeded);
378                }
379                // These prefixes already contain this call's data. Shrink their
380                // allocations in place instead of discarding still-live values.
381                self.integers.truncate(i);
382                self.floats.truncate(f);
383                self.flags.truncate(b);
384                self.keys.truncate(k);
385                self.vertices.truncate(vertices);
386                self.shrink_active()?;
387                let minimum = total(
388                    [
389                        i.max(self.integers.capacity()),
390                        f.max(self.floats.capacity()),
391                        b.max(self.flags.capacity()),
392                        k.max(self.keys.capacity()),
393                    ],
394                    output
395                        .checked_add(checked_bytes(
396                            vertices.max(self.vertices.capacity()),
397                            size_of::<CacheVertex>(),
398                        )?)
399                        .ok_or(Error::SizeOverflow)?,
400                )?;
401                if minimum > self.limits.max_bytes {
402                    return Err(Error::LimitExceeded);
403                }
404            }
405        }
406        self.active = [i != 0, f != 0, b != 0, k != 0, vertices != 0];
407        self.has_retained |= i != 0 || f != 0 || b != 0 || k != 0 || vertices != 0;
408        reserve(&mut self.vertices, vertices)?;
409        reserve_value(&mut self.integers, i, integer_value)?;
410        reserve(&mut self.floats, f)?;
411        reserve(&mut self.flags, b)?;
412        reserve(&mut self.keys, k)?;
413        let actual = total(
414            [
415                self.integers.capacity(),
416                self.floats.capacity(),
417                self.flags.capacity(),
418                self.keys.capacity(),
419            ],
420            output
421                .checked_add(checked_bytes(
422                    self.vertices.capacity(),
423                    size_of::<CacheVertex>(),
424                )?)
425                .and_then(|n| n.checked_add(simplify_bytes))
426                .ok_or(Error::SizeOverflow)?,
427        )?;
428        if actual > self.limits.max_bytes {
429            self.clear();
430            return Err(Error::LimitExceeded);
431        }
432        self.usage.bytes = self.usage.bytes.max(actual);
433        Ok(())
434    }
435}
436
437// Vec shrinking preserves the live prefix and never grows the allocation.
438// An allocator may refuse to shrink; do not misreport that as a byte-limit error.
439pub(crate) fn shrink<T>(v: &mut Vec<T>, active: bool) -> Result<(), Error> {
440    if active && v.capacity() > v.len() {
441        v.shrink_to_fit();
442        if v.capacity() > v.len() {
443            return Err(Error::AllocationFailed);
444        }
445    }
446    Ok(())
447}
448
449#[inline(always)]
450fn total(lengths: [usize; 4], output: usize) -> Result<usize, Error> {
451    let mut sum = output;
452    for (len, size) in lengths.into_iter().zip([4, 4, 1, 2]) {
453        let bytes = checked_bytes(len, size)?;
454        sum = sum.checked_add(bytes).ok_or(Error::SizeOverflow)?;
455    }
456    Ok(sum)
457}
458
459// Codec-only wiring: account retained geometry scratch without resizing any
460// vector. Raw decoding requires no heap scratch and preserves the workspace.
461impl Workspace {
462    #[inline]
463    pub(crate) fn account_codec(&mut self, output: usize) -> Result<(), Error> {
464        self.charge_owned(output)
465    }
466}
467
468#[inline]
469pub(crate) fn checked_bytes(len: usize, size: usize) -> Result<usize, Error> {
470    let bytes = len.checked_mul(size).ok_or(Error::SizeOverflow)?;
471    if bytes > isize::MAX as usize {
472        return Err(Error::SizeOverflow);
473    }
474    Ok(bytes)
475}
476
477#[inline(always)]
478fn reserve<T: Default + Clone>(v: &mut Vec<T>, len: usize) -> Result<(), Error> {
479    reserve_value(v, len, T::default())
480}
481fn reserve_value<T: Clone>(v: &mut Vec<T>, len: usize, value: T) -> Result<(), Error> {
482    checked_bytes(len, size_of::<T>())?;
483    if len > v.capacity() {
484        v.try_reserve_exact(len.saturating_sub(v.len()))
485            .map_err(|_| Error::AllocationFailed)?;
486    }
487    v.resize(len, value);
488    Ok(())
489}
490
491pub(crate) fn output(len: usize) -> Result<Vec<u32>, Error> {
492    checked_bytes(len, 4)?;
493    let mut v = Vec::new();
494    reserve(&mut v, len)?;
495    Ok(v)
496}
497pub(crate) fn output_sentinel(len: usize) -> Result<Vec<u32>, Error> {
498    checked_bytes(len, 4)?;
499    let mut v = Vec::new();
500    reserve_value(&mut v, len, u32::MAX)?;
501    Ok(v)
502}
503
504pub(crate) struct Work {
505    remaining: u64,
506    limit: u64,
507}
508impl Work {
509    /// Upper bound after normal/tangent input validation: all hash probes,
510    /// two adjacency visits per corner, all possible corner pairs, one face
511    /// visit and one accumulation visit per corner. Overflow selects staging.
512    pub(crate) fn covers_corner_generation(
513        &self,
514        vertices: usize,
515        buckets: usize,
516        corners: usize,
517    ) -> bool {
518        let bound = (|| {
519            let vertices = u64::try_from(vertices).ok()?;
520            let buckets = u64::try_from(buckets).ok()?;
521            let corners = u64::try_from(corners).ok()?;
522            vertices
523                .checked_mul(buckets)?
524                .checked_add(corners.checked_mul(corners.saturating_sub(1))? / 2)?
525                .checked_add(corners.checked_mul(3)?)?
526                .checked_add(corners / 3)
527        })();
528        bound.is_some_and(|visits| visits <= self.remaining)
529    }
530
531    #[inline]
532    pub(crate) fn covers(&self, count: usize) -> Result<bool, Error> {
533        Ok(u64::try_from(count).map_err(|_| Error::SizeOverflow)? <= self.remaining)
534    }
535
536    #[inline(always)]
537    pub(crate) fn scan<T>(
538        &mut self,
539        values: impl ExactSizeIterator<Item = T>,
540        visit: impl FnMut(T) -> Result<(), Error>,
541    ) -> Result<(), Error> {
542        self.scan_units(values, 1, visit)
543    }
544    /// Each callback has the same pre-visit charge. Keep that granularity on
545    /// exhaustion, including callbacks that fail before completing their work.
546    #[inline(always)]
547    pub(crate) fn scan_units<T>(
548        &mut self,
549        values: impl ExactSizeIterator<Item = T>,
550        units: usize,
551        mut visit: impl FnMut(T) -> Result<(), Error>,
552    ) -> Result<(), Error> {
553        let count = u64::try_from(values.len()).map_err(|_| Error::SizeOverflow)?;
554        let unit_count = u64::try_from(units).map_err(|_| Error::SizeOverflow)?;
555        if let Some(visits) = count
556            .checked_mul(unit_count)
557            .filter(|&v| v <= self.remaining)
558        {
559            for (i, value) in values.enumerate() {
560                if let Err(error) = visit(value) {
561                    self.remaining -= (i as u64 + 1) * unit_count;
562                    return Err(error);
563                }
564            }
565            self.remaining -= visits;
566            Ok(())
567        } else {
568            for value in values {
569                self.add(units)?;
570                visit(value)?;
571            }
572            Ok(())
573        }
574    }
575    /// Precharge a fixed scan only when every visit fits. The caller must
576    /// execute every visit without a fallible callback on this path.
577    #[inline]
578    pub(crate) fn precharge(&mut self, count: usize, units: usize) -> Result<bool, Error> {
579        let count = u64::try_from(count).map_err(|_| Error::SizeOverflow)?;
580        let units = u64::try_from(units).map_err(|_| Error::SizeOverflow)?;
581        if let Some(visits) = count.checked_mul(units).filter(|&v| v <= self.remaining) {
582            self.remaining -= visits;
583            Ok(true)
584        } else {
585            Ok(false)
586        }
587    }
588    /// Number of records whose full per-record search bound fits.
589    #[inline]
590    pub(crate) fn batch(&self, count: usize, units: usize) -> Result<usize, Error> {
591        let units = u64::try_from(units).map_err(|_| Error::SizeOverflow)?;
592        let count = u64::try_from(count).map_err(|_| Error::SizeOverflow)?;
593        let allowed = self
594            .remaining
595            .min(usize::MAX as u64)
596            .checked_div(units)
597            .map_or(count, |n| count.min(n));
598        usize::try_from(allowed).map_err(|_| Error::SizeOverflow)
599    }
600    /// Count a bounded search once when every possible visit fits. The limited
601    /// path checks before each callback, preserving its observable prefix.
602    #[inline(always)]
603    pub(crate) fn search(
604        &mut self,
605        count: usize,
606        mut found: impl FnMut(usize) -> bool,
607    ) -> Result<Option<usize>, Error> {
608        if self.covers(count)? {
609            for i in 0..count {
610                if found(i) {
611                    self.add(i + 1)?;
612                    return Ok(Some(i));
613                }
614            }
615            self.add(count)?;
616        } else {
617            for i in 0..count {
618                self.add(1)?;
619                if found(i) {
620                    return Ok(Some(i));
621                }
622            }
623        }
624        Ok(None)
625    }
626    /// Validate an index stream with a vectorizable fast path for valid data.
627    /// Replay the scalar scan for the first invalid index or a tight fuel limit
628    /// so the error and charged prefix stay unchanged.
629    #[inline]
630    pub(crate) fn indices(&mut self, indices: &[u32], vertices: usize) -> Result<(), Error> {
631        if self.covers(indices.len())?
632            && indices
633                .iter()
634                .copied()
635                .max()
636                .is_none_or(|index| (index as usize) < vertices)
637        {
638            self.add(indices.len())
639        } else {
640            self.scan(indices.iter().copied(), |index| {
641                if index as usize >= vertices {
642                    Err(Error::IndexOutOfBounds)
643                } else {
644                    Ok(())
645                }
646            })
647        }
648    }
649    /// Test a conservative bound without narrowing or overflowing it.
650    #[inline]
651    pub(crate) fn covers_wide(&self, bound: u128) -> bool {
652        bound <= u128::from(self.remaining)
653    }
654    /// Charge the visits an unchecked pass tallied when they fit and report
655    /// whether they did. A fitting pass would have charged the same visits
656    /// through `add` without exhausting the budget; otherwise nothing is
657    /// charged and the caller replays its checked pass.
658    #[inline]
659    pub(crate) fn settle(&mut self, visits: u128) -> bool {
660        match u64::try_from(visits) {
661            Ok(visits) if visits <= self.remaining => {
662                self.remaining -= visits;
663                true
664            }
665            _ => false,
666        }
667    }
668    // Caller has proved that all charges in its operation fit the remaining budget.
669    #[inline(always)]
670    pub(crate) fn add_covered(&mut self, count: usize) {
671        self.remaining -= count as u64;
672    }
673    #[inline]
674    pub(crate) fn add(&mut self, count: usize) -> Result<(), Error> {
675        let count = u64::try_from(count).map_err(|_| Error::SizeOverflow)?;
676        if count > self.remaining {
677            return self.exhausted(count);
678        }
679        self.remaining -= count;
680        Ok(())
681    }
682    // Settle an already-covered cache-kernel reservation to its actual visits.
683    // Only cache.rs calls this, after proving and prepaying its complete bound.
684    #[inline]
685    pub(crate) fn refund_cache(&mut self, count: usize) {
686        debug_assert!(count as u64 <= self.limit - self.remaining);
687        self.remaining += count as u64;
688    }
689    #[cold]
690    #[inline(never)]
691    fn exhausted(&self, count: u64) -> Result<(), Error> {
692        // Preserve both the failed visit's count and the overflow error.
693        (self.limit - self.remaining)
694            .checked_add(count)
695            .ok_or(Error::SizeOverflow)?;
696        Err(Error::LimitExceeded)
697    }
698}
699
700pub(crate) fn topology(indices: &[u32], vertices: usize, work: &mut Work) -> Result<(), Error> {
701    if !indices.len().is_multiple_of(3) {
702        return Err(Error::InvalidTopology);
703    }
704    // Upstream adjacency offsets and triangle identifiers are u32.
705    if vertices > u32::MAX as usize || indices.len() > u32::MAX as usize {
706        return Err(Error::SizeOverflow);
707    }
708    checked_bytes(vertices, 4)?;
709    checked_bytes(indices.len(), 4)?;
710    work.indices(indices, vertices)
711}
712
713// Additive 0.3 accounting: processing modules use local typed scratch and do not
714// resize the workspace's cache/overdraw buffers.
715impl Workspace {
716    #[inline]
717    pub(crate) fn processing_storage(&mut self, bytes: usize) -> Result<(), Error> {
718        self.charge_owned(bytes)
719    }
720}
721
722// Child operation totals are u64 even on 32-bit targets.
723#[cfg(any(feature = "clusterlod", feature = "parallel"))]
724impl Work {
725    #[inline]
726    pub(crate) fn add_processing(&mut self, count: u64) -> Result<(), Error> {
727        if count > self.remaining {
728            return self.exhausted(count);
729        }
730        self.remaining -= count;
731        Ok(())
732    }
733}
734
735#[cfg(test)]
736mod tests {
737    use super::*;
738
739    #[test]
740    fn active_capacity_reclamation_preserves_live_prefixes_and_fitting_reuse() {
741        let mut ws = Workspace::new(Limits {
742            max_bytes: 128,
743            ..Limits::default()
744        });
745        for (lengths, vertices) in [
746            ([16, 0, 0, 0], 0),
747            ([0, 16, 0, 0], 0),
748            ([0, 0, 64, 0], 0),
749            ([0, 0, 0, 32], 0),
750            ([0; 4], 5),
751        ] {
752            ws.clear();
753            ws.begin();
754            ws.prepare_cache(lengths, vertices, 0).unwrap();
755            ws.begin();
756            let needed = lengths.map(|n| usize::from(n != 0));
757            ws.prepare_cache(needed, usize::from(vertices != 0), 0)
758                .unwrap();
759            let capacities = (
760                ws.integers.capacity(),
761                ws.floats.capacity(),
762                ws.flags.capacity(),
763                ws.keys.capacity(),
764                ws.vertices.capacity(),
765            );
766            ws.integers.fill(17);
767            ws.floats.fill(2.5);
768            ws.flags.fill(19);
769            ws.keys.fill(23);
770            ws.vertices.fill(CacheVertex {
771                live: 29,
772                ..CacheVertex::default()
773            });
774            ws.prepare_cache(needed, usize::from(vertices != 0), 0)
775                .unwrap();
776            assert_eq!(
777                capacities,
778                (
779                    ws.integers.capacity(),
780                    ws.floats.capacity(),
781                    ws.flags.capacity(),
782                    ws.keys.capacity(),
783                    ws.vertices.capacity()
784                )
785            );
786            ws.charge_owned(116).unwrap();
787            assert!(ws.usage().bytes <= 128);
788            assert!(ws.integers.iter().all(|&v| v == 17));
789            assert!(ws.floats.iter().all(|&v| v.to_bits() == 2.5f32.to_bits()));
790            assert!(ws.flags.iter().all(|&v| v == 19));
791            assert!(ws.keys.iter().all(|&v| v == 23));
792            assert!(ws.vertices.iter().all(|v| v.live == 29));
793            assert_eq!(ws.charge_owned(128), Err(Error::LimitExceeded));
794        }
795    }
796
797    #[test]
798    fn simplify_then_cache_releases_retained_scratch_under_pressure() {
799        use crate::{
800            optimize_vertex_cache_in_place, simplify, Positions, SimplifyOptions, SimplifySettings,
801        };
802        // Unshared triangles keep the simplified stream large, as in a082.
803        let positions: Vec<_> = (0..4096)
804            .flat_map(|i| {
805                let x = i as f32 * 2.0;
806                [[x, 0.0, 0.0], [x + 1.0, 0.0, 0.0], [x, 1.0, 0.0]]
807            })
808            .collect();
809        let indices: Vec<_> = (0..positions.len() as u32).collect();
810        let settings = SimplifySettings {
811            target_index_count: indices.len() / 2,
812            target_error: 0.01,
813            options: SimplifyOptions::EMPTY,
814        };
815        let mut fresh = Workspace::default();
816        let expected = simplify(
817            &indices,
818            Positions::from_packed(&positions),
819            settings,
820            &mut fresh,
821        )
822        .unwrap();
823        let simplify_peak = fresh.usage().bytes;
824        fresh.clear();
825        let mut expected_cache = expected.indices.clone();
826        optimize_vertex_cache_in_place(&mut expected_cache, positions.len(), &mut fresh).unwrap();
827        let limits = Limits {
828            max_bytes: simplify_peak.max(fresh.usage().bytes),
829            ..Limits::default()
830        };
831        let mut reused = Workspace::new(limits);
832        let actual = simplify(
833            &indices,
834            Positions::from_packed(&positions),
835            settings,
836            &mut reused,
837        )
838        .unwrap();
839        assert_eq!(actual.indices, expected.indices);
840        assert_eq!(actual.error.to_bits(), expected.error.to_bits());
841        let retained = reused.retained_bytes().unwrap();
842        // Establish the regression's premise rather than just exercise reuse.
843        let cache_demand = fresh.usage().bytes;
844        assert!(retained + cache_demand > limits.max_bytes);
845        let mut actual_cache = actual.indices;
846        optimize_vertex_cache_in_place(&mut actual_cache, positions.len(), &mut reused).unwrap();
847        assert_eq!(actual_cache, expected_cache);
848    }
849
850    #[test]
851    fn precharged_scans_and_batches_fit_their_counter_width() {
852        for units in [0, 1, 3, 99] {
853            for limit in 0..=units * 5 + 1 {
854                let mut scalar = Work {
855                    remaining: limit as u64,
856                    limit: limit as u64,
857                };
858                let mut batched = Work {
859                    remaining: limit as u64,
860                    limit: limit as u64,
861                };
862                let mut expected_prefix = Vec::new();
863                let mut actual_prefix = Vec::new();
864                let expected: Result<(), Error> = (|| {
865                    for i in 0..5 {
866                        scalar.add(units)?;
867                        expected_prefix.push(i);
868                    }
869                    Ok(())
870                })();
871                let actual: Result<(), Error> = (|| {
872                    let charged = batched.precharge(5, units)?;
873                    for i in 0..5 {
874                        if !charged {
875                            batched.add(units)?;
876                        }
877                        actual_prefix.push(i);
878                    }
879                    Ok(())
880                })();
881                assert_eq!(actual, expected);
882                assert_eq!(actual_prefix, expected_prefix);
883                assert_eq!(batched.remaining, scalar.remaining);
884            }
885        }
886        let huge = Work {
887            remaining: u64::MAX,
888            limit: u64::MAX,
889        };
890        for units in [1, 2, 99, usize::MAX] {
891            let count = huge.batch(usize::MAX, units).unwrap();
892            assert!(count.checked_mul(units).is_some());
893            assert!(count as u64 * units as u64 <= huge.remaining);
894        }
895    }
896
897    #[test]
898    fn fixed_charge_scans_preserve_failure_prefixes() {
899        for units in [0, 1, 3, 99] {
900            for limit in 0..=units * 5 + 1 {
901                for failure in 0..=5 {
902                    let mut scalar = Work {
903                        remaining: limit as u64,
904                        limit: limit as u64,
905                    };
906                    let mut batched = Work {
907                        remaining: limit as u64,
908                        limit: limit as u64,
909                    };
910                    let mut expected_prefix = Vec::new();
911                    let mut actual_prefix = Vec::new();
912                    let expected = (|| {
913                        for i in 0..5 {
914                            scalar.add(units)?;
915                            expected_prefix.push(i);
916                            if i == failure {
917                                return Err(Error::InvalidParameter);
918                            }
919                        }
920                        Ok(())
921                    })();
922                    let actual = batched.scan_units(0..5, units, |i| {
923                        actual_prefix.push(i);
924                        if i == failure {
925                            Err(Error::InvalidParameter)
926                        } else {
927                            Ok(())
928                        }
929                    });
930                    assert_eq!(actual, expected);
931                    assert_eq!(batched.remaining, scalar.remaining);
932                    assert_eq!(actual_prefix, expected_prefix);
933                }
934            }
935        }
936    }
937
938    #[test]
939    fn bounded_search_preserves_the_checked_callback_prefix() {
940        for limit in 0..8 {
941            for match_at in 0..8 {
942                let mut scalar = Work {
943                    remaining: limit,
944                    limit,
945                };
946                let mut batched = Work {
947                    remaining: limit,
948                    limit,
949                };
950                let mut scalar_visits = Vec::new();
951                let mut batched_visits = Vec::new();
952                let expected = (|| {
953                    for i in 0..5 {
954                        scalar.add(1)?;
955                        scalar_visits.push(i);
956                        if i == match_at {
957                            return Ok(Some(i));
958                        }
959                    }
960                    Ok(None)
961                })();
962                let actual = batched.search(5, |i| {
963                    batched_visits.push(i);
964                    i == match_at
965                });
966                assert_eq!(actual, expected);
967                assert_eq!(batched.remaining, scalar.remaining);
968                assert_eq!(batched_visits, scalar_visits);
969            }
970        }
971    }
972    #[test]
973    fn scan_preserves_failures_work_and_side_effects() {
974        for limit in 0..=8 {
975            for fail_at in 0usize..=5 {
976                let mut scalar = Work {
977                    remaining: limit,
978                    limit,
979                };
980                let mut scanned = Work {
981                    remaining: limit,
982                    limit,
983                };
984                let mut scalar_sum = 0;
985                let mut scanned_sum = 0;
986                let visit = |i, sum: &mut usize| {
987                    *sum += i + 1;
988                    if i == fail_at {
989                        Err(Error::NumericalFailure)
990                    } else {
991                        Ok(())
992                    }
993                };
994                let expected = (|| {
995                    for i in 0..5 {
996                        scalar.add(1)?;
997                        visit(i, &mut scalar_sum)?;
998                    }
999                    Ok(())
1000                })();
1001                let actual = scanned.scan(0..5, |i| visit(i, &mut scanned_sum));
1002                assert_eq!(actual, expected);
1003                assert_eq!(scanned.remaining, scalar.remaining);
1004                assert_eq!(scanned_sum, scalar_sum);
1005            }
1006        }
1007    }
1008
1009    #[test]
1010    fn index_fast_path_preserves_first_error_and_fuel_prefix() {
1011        for values in [&[][..], &[0, 1, 2], &[0, 7, 1], &[7, 0, 1]] {
1012            for limit in 0..=8 {
1013                let mut scalar = Work {
1014                    remaining: limit,
1015                    limit,
1016                };
1017                let mut fast = Work {
1018                    remaining: limit,
1019                    limit,
1020                };
1021                let expected = (|| {
1022                    for &index in values {
1023                        scalar.add(1)?;
1024                        if index >= 3 {
1025                            return Err(Error::IndexOutOfBounds);
1026                        }
1027                    }
1028                    Ok(())
1029                })();
1030                assert_eq!(fast.indices(values, 3), expected);
1031                assert_eq!(fast.remaining, scalar.remaining);
1032            }
1033        }
1034    }
1035}