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