1use crate::Error;
2use alloc::vec::Vec;
3use core::mem::size_of;
4
5#[derive(Clone, Copy, Debug, PartialEq, Eq)]
7pub struct Limits {
8 pub max_bytes: usize,
13 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
28pub struct Usage {
29 pub bytes: usize,
31 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
44pub enum Retention {
45 #[default]
47 Reuse,
48 Lean,
56}
57
58#[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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
95pub(crate) enum ScratchFamily {
96 Simplify,
97 Cache,
98 Overdraw,
99}
100
101impl Workspace {
102 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 pub(crate) fn set_lod_usage(&mut self, usage: Usage) {
114 self.usage = usage;
115 }
116 pub const fn retention(&self) -> Retention {
118 self.retention
119 }
120 pub fn set_retention(&mut self, retention: Retention) {
124 if self.retention != retention {
125 self.clear();
126 self.retention = retention;
127 }
128 }
129 pub const fn limits(&self) -> Limits {
131 self.limits
132 }
133 pub fn set_limits(&mut self, limits: Limits) {
135 self.clear();
136 self.limits = limits;
137 }
138 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 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 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 #[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 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 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
437pub(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
459impl 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 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 #[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 #[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 #[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 #[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 #[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 #[inline]
651 pub(crate) fn covers_wide(&self, bound: u128) -> bool {
652 bound <= u128::from(self.remaining)
653 }
654 #[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 #[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 #[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 (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 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
713impl Workspace {
716 #[inline]
717 pub(crate) fn processing_storage(&mut self, bytes: usize) -> Result<(), Error> {
718 self.charge_owned(bytes)
719 }
720}
721
722#[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 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 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}