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 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
94pub(crate) enum ScratchFamily {
95 Simplify,
96 Cache,
97 Overdraw,
98}
99
100impl Workspace {
101 pub fn new(limits: Limits) -> Self {
103 Self {
104 limits,
105 ..Self::default()
106 }
107 }
108 pub const fn retention(&self) -> Retention {
110 self.retention
111 }
112 pub fn set_retention(&mut self, retention: Retention) {
116 if self.retention != retention {
117 self.clear();
118 self.retention = retention;
119 }
120 }
121 pub const fn limits(&self) -> Limits {
123 self.limits
124 }
125 pub fn set_limits(&mut self, limits: Limits) {
127 self.clear();
128 self.limits = limits;
129 }
130 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 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 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 #[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 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 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
429pub(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
451impl 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 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 #[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 #[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 #[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 #[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 #[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 #[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 (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 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
681impl Workspace {
684 #[inline]
685 pub(crate) fn processing_storage(&mut self, bytes: usize) -> Result<(), Error> {
686 self.charge_owned(bytes)
687 }
688}
689
690#[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 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 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}