Repository: vercel/next.js
Pull request: Turbopack: Rewrite IntervalMap using a BTreeMap

Changes:
- Rewrote using a `BTreeMap`. This makes `update` `O(log n)`. It was previously `O(n)` which could give accidentally-quadratic time complexity when inserting `n` intervals. We don't think we have enough SST files for this to have been an issue, but how this data structure is used could change over time, and it was a bit risky.
- There was some implicit `Option<T>` behavior in `IntervalMap` making it act like a sparse array. This made the type signature and behavior of some of its methods confusing. Removed that from `IntervalMap` and made the few callsites that actually need it explicitly use `Option<T>`.
- Added a small `NaiveIntervalMap` implementation along with a narrowly bounded `TinyInt` type, and prove the correctness of `replace`, `update`, and `iter` by exhaustively comparing against it.
- Added logic to merge adjacent intervals. This isn't really needed given how the map is currently used, but it's a possible optimization for some use-cases, and it helped align the behavior with `NaiveIntervalMap`.
- Use `RangeInclusive<T>` or `impl RangeBounds<T>` instead of just `(u64, u64)` so that the inclusive/exclusive behaviors are always as explicit as possible.

The implementation is not entirely optimal, but in part that's because it avoids using the nightly `btree_cursors` feature. However, the big-O time complexity should still be optimal.

Some additional minor changes to `turbopack/crates/turbo-persistence/src/compaction/selector.rs`:

- Avoid implicitly-overflowing `as u64` casts, prefer `from` and `try_from`.
- Make `spread` return a `u128`, since that's slightly more correct than a `saturating_add`, the callsites were casting it to a `u128` anyways.
- Add some more comments that are hopefully correct.

Closes PACK-4984

Changed files:
filename: turbopack/crates/turbo-persistence/src/compaction/interval_map.rs
patch: @@ -1,183 +1,422 @@
-struct IntervalPoint<T> {
-    start: u64,
-    value: Option<T>,
+use std::{
+    collections::{BTreeMap, btree_map},
+    iter::Peekable,
+    ops::{Bound, RangeBounds, RangeInclusive},
+};
+
+/// Values that can be used as the bound of an interval.
+///
+/// Currently only implemented for `u64`.
+pub trait IntervalBound: Copy + Ord {
+    fn bound_min() -> Self;
+    fn bound_max() -> Self;
+    fn checked_increment(&self) -> Option<Self>;
+    fn checked_decrement(&self) -> Option<Self>;
+}
+
+impl IntervalBound for u64 {
+    fn bound_min() -> Self {
+        Self::MIN
+    }
+    fn bound_max() -> Self {
+        Self::MAX
+    }
+    fn checked_increment(&self) -> Option<Self> {
+        self.checked_add(1)
+    }
+    fn checked_decrement(&self) -> Option<Self> {
+        self.checked_sub(1)
+    }
 }
 
-pub struct IntervalMap<T> {
-    intervals: Vec<IntervalPoint<T>>,
+fn into_range_inclusive<B>(bounds: impl RangeBounds<B>) -> RangeInclusive<B>
+where
+    B: IntervalBound,
+{
+    let start = match bounds.start_bound() {
+        Bound::Included(b) => *b,
+        Bound::Excluded(b) => b.checked_increment().unwrap_or_else(B::bound_max),
+        Bound::Unbounded => B::bound_min(),
+    };
+
+    let end = match bounds.end_bound() {
+        Bound::Included(b) => *b,
+        Bound::Excluded(b) => b.checked_decrement().unwrap_or_else(B::bound_min),
+        Bound::Unbounded => B::bound_max(),
+    };
+
+    start..=end
 }
 
-impl<T> Default for IntervalMap<T> {
+/// This is a conceptually more efficient version of an array `[T: u64::MAX]` (or `[T:
+/// B::bound_max()]`), where entries are deduplicated using a variation on [run-length
+/// encoding][rle].
+///
+/// Ranges can be split or merged by [`IntervalMap::update`] and [`IntervalMap::replace`].
+///
+/// [rle]: https://en.wikipedia.org/wiki/Run-length_encoding
+pub struct IntervalMap<T, B = u64> {
+    /// Represents the start of non-overlapping ranges with values.
+    ///
+    /// When constructing `IntervalMap`, we add a `Default::default()` interval starting at
+    /// `B::bound_min()`.
+    ///
+    /// Each interval extends until the start of the next one (exclusive). The last span in the map
+    /// extends to `B::bound_max()` (inclusive).
+    interval_starts: BTreeMap<B, T>,
+}
+
+impl<T, B> Default for IntervalMap<T, B>
+where
+    T: Default,
+    B: IntervalBound,
+{
     fn default() -> Self {
-        Self {
-            intervals: Vec::new(),
-        }
+        Self::new()
     }
 }
 
-impl<T> IntervalMap<T> {
+impl<T, B> IntervalMap<T, B>
+where
+    T: Default,
+    B: IntervalBound,
+{
+    /// Creates a new [`IntervalMap`] with a [`Default::default`] value spanning from
+    /// [`IntervalBound::bound_min`] to [`IntervalBound::bound_max`] (inclusive). Typically, that's
+    /// `0..=u64::MAX`.
+    ///
+    /// Note: Unlike many stdlib collections, this collection will perform an allocation during
+    /// construction. This could be avoided in the future by special-casing of the initial default
+    /// interval as a lazily constructed or stack allocated value.
     pub fn new() -> Self {
-        Default::default()
+        let mut interval_starts = BTreeMap::new();
+        interval_starts.insert(B::bound_min(), Default::default());
+        Self { interval_starts }
     }
+}
 
-    /// Ensures that there is an interval point at the specified location.
-    fn ensure_point(&mut self, location: u64) -> usize
-    where
-        T: Clone,
-    {
-        match self
-            .intervals
-            .binary_search_by_key(&location, |point| point.start)
-        {
-            Ok(index) => index,
-            Err(index) => {
-                // If the location does not exist, we need to insert a new interval
-                let value = if index > 0 {
-                    self.intervals[index - 1].value.clone()
-                } else {
-                    None
-                };
-                self.intervals.insert(
-                    index,
-                    IntervalPoint {
-                        start: location,
-                        value,
-                    },
-                );
-                index
-            }
-        }
+impl<T, B> IntervalMap<T, B>
+where
+    B: Ord,
+{
+    /// Returns the largest value that's less than ([`Bound::Excluded`]) or equal to
+    /// ([`Bound::Included`]) the given `bound`.
+    ///
+    /// It is guaranteed to return a value, as there's always an interval starting at
+    /// [`IntervalBound::bound_min`].
+    ///
+    /// This is an approximation of the nightly-only `BTreeMap::upper_bound` API, but it returns a
+    /// key-value pair instead of a cursor.
+    ///
+    /// Panics if `bound` is `Bound::Excluded(IntervalBound::bound_min())`, as that would imply an
+    /// empty range.
+    fn upper_bound(&self, bound: Bound<&B>) -> Option<(&B, &T)> {
+        self.interval_starts
+            .range((Bound::Unbounded, bound))
+            .next_back()
     }
+}
 
-    /// Applies the update function to all values in the specified range.
-    pub fn update(&mut self, range: &(u64, u64), mut update: impl FnMut(&mut T))
-    where
-        T: Default + Clone,
-    {
-        let start = range.0;
-        let end = range.1;
-        if start > end {
+impl<T, B> IntervalMap<T, B>
+where
+    B: IntervalBound,
+    T: Clone + Eq,
+{
+    /// Applies the update function to all values in the specified range. It doesn't iterate over
+    /// every value one-by-one, but instead it iterates over intersecting ranges.
+    ///
+    /// Newly equal intervals are merged.
+    pub fn update(&mut self, range: impl RangeBounds<B>, mut update: impl FnMut(&mut T)) {
+        let range = into_range_inclusive(range);
+        let start_bound = *range.start();
+        let end_bound = *range.end();
+        if start_bound > end_bound {
             return;
         }
 
-        let start = self.ensure_point(start);
-        if end == u64::MAX {
-            for i in start..self.intervals.len() {
-                update(self.intervals[i].value.get_or_insert_default());
+        let tail = end_bound.checked_increment().map(|tb| {
+            (
+                tb,
+                self.upper_bound(Bound::Included(&tb))
+                    .expect("at least one interval starting at `B::bound_min`")
+                    .1
+                    .clone(),
+            )
+        });
+
+        // defer insertions and removals to avoid multiple simultaneous mutable borrows
+        let mut updated_start_value = None;
+        let mut remove_list = Vec::new();
+
+        // N.B. `prev_value` can be `None` if `start_bound` is `B::bound_min()`
+        // this value must be cloned because we mutably borrow `interval_starts` below
+        let prev_value = self
+            .upper_bound(Bound::Excluded(&start_bound))
+            .map(|(_, v)| v.clone());
+
+        let mut starts_iter = self
+            .interval_starts
+            .range_mut((Bound::Included(start_bound), Bound::Included(end_bound)))
+            .peekable();
+
+        // insert or update an interval starting at `start_bound`
+        let mut prev_value_inner;
+        let mut prev_value =
+            if let Some((_, cur_value)) = starts_iter.next_if(|(b, _)| *b == &start_bound) {
+                update(cur_value);
+
+                if Some(&*cur_value) == prev_value.as_ref() {
+                    // merge identical adjacent intervals
+                    remove_list.push(start_bound);
+                }
+
+                cur_value
+            } else {
+                prev_value_inner = prev_value.expect(
+                    "there's no interval starting at `start_bound`, so there must be one before it",
+                );
+
+                let mut cur_value = prev_value_inner.clone();
+                update(&mut cur_value);
+                if cur_value != prev_value_inner {
+                    // only start a new interval if it's different
+                    updated_start_value.get_or_insert(cur_value)
+                } else {
+                    &mut prev_value_inner
+                }
+            };
+
+        // update existing intervals from start_bound (exclusive) to end_bound (inclusive)
+        if start_bound < end_bound {
+            for (cur_bound, cur_value) in starts_iter {
+                update(cur_value);
+                if cur_value == prev_value {
+                    remove_list.push(*cur_bound);
+                }
+                prev_value = cur_value;
             }
-        } else {
-            let end = self.ensure_point(end + 1);
+        }
 
-            for i in start..end {
-                update(self.intervals[i].value.get_or_insert_default());
+        // don't modify any intervals following the ones we updated
+        if let Some((tail_bound, tail_value)) = tail {
+            if prev_value != &tail_value {
+                self.interval_starts.insert(tail_bound, tail_value);
+            } else {
+                // there *might* be a no-longer-needed interval start here, try to remove it
+                remove_list.push(tail_bound);
             }
         }
-    }
 
-    /// Tests if any values in the specified range satisfy the predicate.
-    pub fn test(&self, range: &(u64, u64), mut predicate: impl FnMut(&T) -> bool) -> bool {
-        let start = range.0;
-        let end = range.1;
-        if start > end {
-            return false;
+        // apply deferred insertions and removals
+        for pos in remove_list {
+            self.interval_starts.remove(&pos);
+        }
+        if let Some(start_value) = updated_start_value {
+            self.interval_starts.insert(start_bound, start_value);
         }
+    }
 
-        let start_index = match self
-            .intervals
-            .binary_search_by_key(&start, |point| point.start)
-        {
-            Ok(index) => index,
-            Err(0) => 0,
-            Err(index) => index - 1,
-        };
-
-        let end_index = match self
-            .intervals
-            .binary_search_by_key(&end, |point| point.start)
+    pub fn replace(&mut self, bounds: impl RangeBounds<B>, value: T) {
+        // it would be more efficient to implement this directly, but this is good enough for our
+        // current use-cases
+        self.update(bounds, |v| *v = value.clone());
+    }
+}
+
+impl<T, B> IntervalMap<T, B>
+where
+    B: IntervalBound,
+{
+    /// Returns an iterator over all the intervals intersecting with the given range and their
+    /// associated values.
+    pub fn iter_intersecting(&self, range: impl RangeBounds<B>) -> IntervalMapIterator<'_, T, B> {
+        fn inner<T, B>(
+            this: &IntervalMap<T, B>,
+            range: RangeInclusive<B>,
+        ) -> IntervalMapIterator<'_, T, B>
+        where
+            B: IntervalBound,
         {
-            Ok(index) => index + 1,
-            Err(index) => index,
-        };
-
-        for i in start_index..end_index {
-            if let Some(value) = &self.intervals[i].value
-                && predicate(value)
-            {
-                return true;
+            // the first intersecting range may begin before `range.start()`
+            let (start_position, _) = this
+                .upper_bound(Bound::Included(range.start()))
+                .expect("at least one interval starting at `B::bound_min`");
+            IntervalMapIterator {
+                starts_iter: this.interval_starts.range(start_position..).peekable(),
+                end_bound: *range.end(),
             }
         }
-        false
+        // slightly reduce monomorphization
+        inner(self, into_range_inclusive(range))
     }
 
-    /// Returns an iterator over the ranges and their associated values.
-    pub fn ranges(&self) -> impl Iterator<Item = ((u64, u64), &T)> {
-        (0..self.intervals.len()).filter_map(move |i| {
-            let start = self.intervals[i].start;
-            let end = if i + 1 < self.intervals.len() {
-                self.intervals[i + 1].start - 1
-            } else {
-                u64::MAX
-            };
-            self.intervals[i]
-                .value
-                .as_ref()
-                .map(|value| ((start, end), value))
-        })
+    /// Returns an iterator over all the intervals and their associated values.
+    pub fn iter(&self) -> IntervalMapIterator<'_, T, B> {
+        IntervalMapIterator {
+            starts_iter: self.interval_starts.range(..).peekable(),
+            end_bound: B::bound_max(),
+        }
+    }
+}
+
+pub struct IntervalMapIterator<'a, T, B> {
+    /// An iterator of `interval_starts` with an unbounded end.
+    starts_iter: Peekable<btree_map::Range<'a, B, T>>,
+    end_bound: B,
+}
+
+impl<'a, T, B> Iterator for IntervalMapIterator<'a, T, B>
+where
+    B: IntervalBound,
+{
+    type Item = (RangeInclusive<B>, &'a T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let (start_bound, value) = self.starts_iter.next()?;
+        if start_bound > &self.end_bound {
+            return None;
+        }
+        let bound_end = self
+            .starts_iter
+            .peek()
+            .map(|entry| entry.0.checked_decrement().unwrap_or_else(B::bound_min))
+            .unwrap_or_else(|| B::bound_max());
+        Some(((*start_bound)..=bound_end, value))
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
+    use crate::compaction::naive_interval_map::{NaiveIntervalMap, TinyInt};
 
     #[test]
     fn test_interval_map() {
         let mut map = IntervalMap::new();
-        map.update(&(5, 15), |v| *v |= 1);
-        map.update(&(10, 15), |v| *v |= 2);
-        map.update(&(10, 20), |v| *v |= 4);
-        map.update(&(0, u64::MAX), |v| *v |= 8);
-        map.update(&(15, 20), |v| *v |= 16);
+        map.update(5..=15, |v| *v |= 1);
+        map.update(10..=15, |v| *v |= 2);
+        map.update(10..=20, |v| *v |= 4);
+        map.update(0..=u64::MAX, |v| *v |= 8);
+        map.update(15..=20, |v| *v |= 16);
+        map.update(25..=30, |v| *v |= 32);
+
+        let result: Vec<_> = map.iter().collect();
+        let expected = vec![
+            (0..=4, &8),
+            (5..=9, &(1 | 8)),
+            (10..=14, &(1 | 2 | 4 | 8)),
+            (15..=15, &(1 | 2 | 4 | 8 | 16)),
+            (16..=20, &(4 | 8 | 16)),
+            (21..=24, &8),
+            (25..=30, &(8 | 32)),
+            (31..=u64::MAX, &8),
+        ];
+        assert_eq!(result, expected);
+
+        // re-use expecting from above
+        let result: Vec<_> = map.iter_intersecting(..).collect();
+        assert_eq!(result, expected);
 
+        let result: Vec<_> = map.iter_intersecting(14..=20).collect();
         let expected = vec![
-            ((0, 4), &8),
-            ((5, 9), &(1 | 8)),
-            ((10, 14), &(1 | 2 | 4 | 8)),
-            ((15, 15), &(1 | 2 | 4 | 8 | 16)),
-            ((16, 20), &(4 | 8 | 16)),
-            ((21, u64::MAX), &8),
+            (10..=14, &(1 | 2 | 4 | 8)),
+            (15..=15, &(1 | 2 | 4 | 8 | 16)),
+            (16..=20, &(4 | 8 | 16)),
         ];
-        let result: Vec<_> = map.ranges().collect();
         assert_eq!(result, expected);
 
-        // test the `test` method
-        assert!(map.test(&(0, 10), |v| *v & 1 != 0));
-        assert!(map.test(&(0, 10), |v| *v & 2 != 0));
-        assert!(map.test(&(0, 50), |v| *v & 4 != 0));
-        assert!(map.test(&(15, 15), |v| *v & 16 != 0));
-        assert!(map.test(&(0, 15), |v| *v & 16 != 0));
-        assert!(map.test(&(20, 20), |v| *v & 16 != 0));
-        assert!(map.test(&(20, u64::MAX), |v| *v & 16 != 0));
-        assert!(map.test(&(0, u64::MAX), |v| *v & 8 != 0));
-        assert!(map.test(&(0, 0), |v| *v & 8 != 0));
-        assert!(map.test(&(u64::MAX, u64::MAX), |v| *v & 8 != 0));
-        assert!(map.test(&(123, 1234), |v| *v & 8 != 0));
+        let result: Vec<_> = map.iter_intersecting(..=0).collect();
+        let expected = vec![(0..=4, &8)];
+        assert_eq!(result, expected);
+
+        let result: Vec<_> = map.iter_intersecting(u64::MAX..).collect();
+        let expected = vec![(31..=u64::MAX, &8)];
+        assert_eq!(result, expected);
+
+        assert!(map.iter_intersecting(0..=10).any(|(_, v)| *v & 1 != 0));
+        assert!(map.iter_intersecting(0..=10).any(|(_, v)| *v & 2 != 0));
+        assert!(!map.iter_intersecting(0..10).any(|(_, v)| *v & 2 != 0));
+        assert!(map.iter_intersecting(0..=50).any(|(_, v)| *v & 4 != 0));
+        assert!(map.iter_intersecting(15..=15).all(|(_, v)| *v & 16 != 0));
+        assert!(!map.iter_intersecting(0..=15).all(|(_, v)| *v & 16 != 0));
+        assert!(map.iter_intersecting(0..=15).any(|(_, v)| *v & 16 != 0));
+        assert!(map.iter_intersecting(20..=20).all(|(_, v)| *v & 16 != 0));
+        assert!(map.iter_intersecting(20..).any(|(_, v)| *v & 16 != 0));
+        assert!(map.iter_intersecting(..).all(|(_, v)| *v & 8 != 0));
+        assert!(map.iter_intersecting(0..=0).all(|(_, v)| *v & 8 != 0));
+        assert!(map.iter_intersecting(u64::MAX..).all(|(_, v)| *v & 8 != 0));
+        assert!(map.iter_intersecting(123..=1234).all(|(_, v)| *v & 8 != 0));
     }
 
     #[test]
     fn test_interval_map_empty() {
         let map: IntervalMap<u32> = IntervalMap::new();
-        let result: Vec<_> = map.ranges().collect();
-        assert!(result.is_empty());
+        let result: Vec<_> = map.iter().collect();
+
+        assert_eq!(result.len(), 1);
+        assert_eq!(result[0], (0..=u64::MAX, &0));
     }
 
     #[test]
     fn test_interval_map_single_point() {
         let mut map: IntervalMap<u32> = IntervalMap::new();
-        map.update(&(10, 10), |v| *v += 1);
+        map.replace(10..=10, 1);
 
-        let result: Vec<_> = map.ranges().collect();
-        assert_eq!(result.len(), 1);
-        assert_eq!(result[0], ((10, 10), &1));
+        let expected = vec![(0..=9, &0), (10..=10, &1), (11..=u64::MAX, &0)];
+        let result: Vec<_> = map.iter().collect();
+        assert_eq!(result, expected);
+    }
+
+    fn for_all_tiny_int_ranges<T: Copy>(
+        values: impl IntoIterator<Item = T>,
+        mut cb: impl FnMut((RangeInclusive<TinyInt>, T)),
+    ) {
+        for value in values {
+            for start in 0..=TinyInt::MAX.0 {
+                for end in start..=TinyInt::MAX.0 {
+                    cb((TinyInt(start)..=TinyInt(end), value));
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_exhaustive_replace_versus_naive() {
+        for_all_tiny_int_ranges([0, 1], |a| {
+            for_all_tiny_int_ranges([1, 2], |b| {
+                for_all_tiny_int_ranges([2, 3], |c| {
+                    let mut real_map = IntervalMap::<u32, TinyInt>::new();
+                    let mut naive_map = NaiveIntervalMap::<u32, TinyInt>::new();
+                    for (range, value) in [&a, &b, &c] {
+                        real_map.replace(range.clone(), *value);
+                        naive_map.replace(range.clone(), *value);
+                    }
+                    assert_eq!(
+                        real_map.iter().collect::<Vec<_>>(),
+                        naive_map.iter().collect::<Vec<_>>(),
+                    )
+                });
+            });
+        });
+    }
+
+    #[test]
+    fn test_exhaustive_update_versus_naive() {
+        for_all_tiny_int_ranges([1, 2], |a| {
+            for_all_tiny_int_ranges([2, 4], |b| {
+                for_all_tiny_int_ranges([4, 8], |c| {
+                    let mut real_map = IntervalMap::<u32, TinyInt>::new();
+                    let mut naive_map = NaiveIntervalMap::<u32, TinyInt>::new();
+                    for (range, flag) in [&a, &b, &c] {
+                        real_map.update(range.clone(), |v| *v |= flag);
+                        naive_map.update(range.clone(), |v| *v |= flag);
+                    }
+                    assert_eq!(
+                        real_map.iter().collect::<Vec<_>>(),
+                        naive_map.iter().collect::<Vec<_>>(),
+                    )
+                });
+            });
+        });
     }
 }

filename: turbopack/crates/turbo-persistence/src/compaction/mod.rs
patch: @@ -1,2 +1,5 @@
 mod interval_map;
 pub mod selector;
+
+#[cfg(test)]
+mod naive_interval_map;

filename: turbopack/crates/turbo-persistence/src/compaction/naive_interval_map.rs
patch: @@ -0,0 +1,120 @@
+use std::{
+    fmt::{self, Display},
+    iter::Peekable,
+    ops::{RangeBounds, RangeInclusive},
+    slice,
+};
+
+use crate::compaction::interval_map::IntervalBound;
+
+/// An integer with a very limited range to allow for exhaustive unit tests of
+/// all possible values.
+#[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
+pub struct TinyInt(pub u8);
+
+impl TinyInt {
+    pub const MIN: TinyInt = TinyInt(0);
+    pub const MAX: TinyInt = TinyInt(6);
+}
+
+impl IntervalBound for TinyInt {
+    fn bound_min() -> Self {
+        Self::MIN
+    }
+    fn bound_max() -> Self {
+        Self::MAX
+    }
+    fn checked_increment(&self) -> Option<Self> {
+        if self < &Self::bound_max() {
+            Some(Self(self.0 + 1))
+        } else {
+            None
+        }
+    }
+    fn checked_decrement(&self) -> Option<Self> {
+        if self > &Self::bound_min() {
+            Some(Self(self.0 - 1))
+        } else {
+            None
+        }
+    }
+}
+
+impl Display for TinyInt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{}", self.0)
+    }
+}
+
+/// An impractically slow but very simple implementation of `IntervalMap` used as a known-good
+/// version for testing the correctness of `IntervalMap`.
+#[allow(dead_code)]
+pub struct NaiveIntervalMap<T, B = TinyInt> {
+    values: Vec<(B, T)>,
+}
+
+impl<T, B> NaiveIntervalMap<T, B>
+where
+    T: Default,
+    B: IntervalBound,
+{
+    pub fn new() -> Self {
+        let mut values = Vec::new();
+        let mut pos = Some(B::bound_min());
+        while let Some(cur) = &pos {
+            values.push((*cur, T::default()));
+            pos = cur.checked_increment();
+        }
+
+        Self { values }
+    }
+}
+
+impl<T, B> NaiveIntervalMap<T, B>
+where
+    B: IntervalBound,
+    T: Clone,
+{
+    pub fn update(&mut self, bounds: impl RangeBounds<B>, mut update: impl FnMut(&mut T)) {
+        for (pos, cur_value) in &mut self.values {
+            if bounds.contains(pos) {
+                update(cur_value);
+            }
+        }
+    }
+
+    pub fn replace(&mut self, bounds: impl RangeBounds<B>, value: T) {
+        self.update(bounds, |v| *v = value.clone());
+    }
+}
+
+impl<T, B> NaiveIntervalMap<T, B>
+where
+    B: IntervalBound,
+{
+    pub fn iter(&self) -> NaiveIntervalMapIterator<'_, T, B> {
+        NaiveIntervalMapIterator {
+            values_iter: self.values.iter().peekable(),
+        }
+    }
+}
+pub struct NaiveIntervalMapIterator<'a, T, B> {
+    values_iter: Peekable<slice::Iter<'a, (B, T)>>,
+}
+
+impl<'a, T, B> Iterator for NaiveIntervalMapIterator<'a, T, B>
+where
+    B: IntervalBound,
+    T: Eq,
+{
+    type Item = (RangeInclusive<B>, &'a T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let (start_pos, cur_value) = self.values_iter.next()?;
+        let mut end_pos = *start_pos;
+        while self.values_iter.peek().is_some_and(|(_, v)| v == cur_value) {
+            end_pos = self.values_iter.next().unwrap().0;
+        }
+        Some(((*start_pos)..=end_pos, cur_value))
+    }
+}

filename: turbopack/crates/turbo-persistence/src/compaction/selector.rs
patch: @@ -1,35 +1,37 @@
+use std::ops::RangeInclusive;
+
 use smallvec::{SmallVec, smallvec};
 
 use crate::compaction::interval_map::IntervalMap;
 
-type Range = (u64, u64);
-
-/// The trait for the input of the compaction algorithm.
+/// Represents part of a database (i.e. an SST file) with a range of keys (i.e. hashes) and a size
+/// of that data in bytes.
 pub trait Compactable {
-    /// Returns the range of the compactable.
-    fn range(&self) -> Range;
+    /// The range of keys stored in this database segment.
+    fn range(&self) -> RangeInclusive<u64>;
 
-    /// Returns the size of the compactable.
+    /// The size of the compactable database segment in bytes.
     fn size(&self) -> u64;
 }
 
-fn is_overlapping(a: &Range, b: &Range) -> bool {
-    a.0 <= b.1 && b.0 <= a.1
+fn is_overlapping(a: &RangeInclusive<u64>, b: &RangeInclusive<u64>) -> bool {
+    a.start() <= b.end() && b.start() <= a.end()
 }
 
-fn spread(range: &Range) -> u64 {
-    (range.1 - range.0).saturating_add(1)
+fn spread(range: &RangeInclusive<u64>) -> u128 {
+    // the spread of `0..=u64::MAX` is `u64::MAX + 1`, so this could overflow as u64
+    u128::from(range.end() - range.start()) + 1
 }
 
 /// Extends the range `a` to include the range `b`, returns `true` if the range was extended.
-fn extend_range(a: &mut Range, b: &Range) -> bool {
+fn extend_range(a: &mut RangeInclusive<u64>, b: &RangeInclusive<u64>) -> bool {
     let mut extended = false;
-    if b.0 < a.0 {
-        a.0 = b.0;
+    if b.start() < a.start() {
+        *a = (*b.start())..=(*a.end());
         extended = true;
     }
-    if b.1 > a.1 {
-        a.1 = b.1;
+    if b.end() > a.end() {
+        *a = (*a.start())..=(*b.end());
         extended = true;
     }
     extended
@@ -53,22 +55,24 @@ pub struct CompactableMetrics {
 /// Computes metrics about the compactables.
 pub fn compute_metrics<T: Compactable>(
     compactables: &[T],
-    full_range: Range,
+    full_range: RangeInclusive<u64>,
 ) -> CompactableMetrics {
-    let mut interval_map: IntervalMap<(DuplicationInfo, usize)> = IntervalMap::new();
+    let mut interval_map = IntervalMap::<Option<(DuplicationInfo, usize)>>::new();
     let mut coverage = 0.0f32;
     for c in compactables {
         let range = c.range();
         coverage += spread(&range) as f32;
-        interval_map.update(&range, |(dup_info, count)| {
+        interval_map.update(range.clone(), |value| {
+            let (dup_info, count) = value.get_or_insert_default();
             dup_info.add(c.size(), &range);
             *count += 1;
         });
     }
     let full_spread = spread(&full_range) as f32;
 
     let (duplicated_size, duplication, overlap) = interval_map
-        .ranges()
+        .iter()
+        .flat_map(|(range, value)| Some((range, value.as_ref()?)))
         .map(|(range, (dup_info, count))| {
             let duplicated_size = dup_info.duplication(&range);
             let total_size = dup_info.size(&range);
@@ -138,39 +142,57 @@ impl Default for CompactConfig {
     }
 }
 
-#[derive(Clone, Default)]
+#[derive(Clone, Default, Eq, PartialEq)]
 struct DuplicationInfo {
+    /// The sum of all encountered scaled sizes.
     total_size: u64,
+    /// The largest encountered single scaled size.
     max_size: u64,
 }
 
 impl DuplicationInfo {
-    fn duplication(&self, range: &Range) -> u64 {
+    /// Get a value in the range `0..=u64` that represents the estimated amount of duplication
+    /// across the given range. The units are arbitrary, but linear.
+    fn duplication(&self, range: &RangeInclusive<u64>) -> u64 {
         if self.total_size == 0 {
             return 0;
         }
-        ((self.total_size - self.max_size) as u128 * spread(range) as u128 / (u64::MAX as u128 + 1))
-            as u64
+        // the maximum numerator value is `u64::MAX + 1`
+        u64::try_from(
+            u128::from(self.total_size - self.max_size) * spread(range)
+                / (u128::from(u64::MAX) + 1),
+        )
+        .expect("should not overflow, denominator was `u64::MAX+1`")
     }
 
-    fn size(&self, range: &Range) -> u64 {
+    /// The estimated size (in bytes) of a database segment containing `range` keys.
+    fn size(&self, range: &RangeInclusive<u64>) -> u64 {
         if self.total_size == 0 {
             return 0;
         }
-        (self.total_size as u128 * spread(range) as u128 / (u64::MAX as u128 + 1)) as u64
+        // the maximum numerator value is `u64::MAX + 1`
+        u64::try_from(u128::from(self.total_size) * spread(range) / (u128::from(u64::MAX) + 1))
+            .expect("should not overflow, denominator was `u64::MAX+1`")
     }
 
-    fn add(&mut self, size: u64, range: &Range) {
+    fn add(&mut self, size: u64, range: &RangeInclusive<u64>) {
+        // Assumption: `size` is typically much smaller than `spread(range)`. The spread is some
+        // fraction of `u64` (the full possible key-space), but no SST file is anywhere close to
+        // `u64::MAX` bytes.
+
         // Scale size to full range:
-        let scaled_size = (size as u128 * (u64::MAX as u128 + 1) / spread(range) as u128) as u64;
+        let scaled_size =
+            u64::try_from(u128::from(size) * (u128::from(u64::MAX) + 1) / spread(range))
+                .unwrap_or(u64::MAX);
         self.total_size = self.total_size.saturating_add(scaled_size);
         self.max_size = self.max_size.max(scaled_size);
     }
 }
 
-fn total_duplication_size(duplication: &IntervalMap<DuplicationInfo>) -> u64 {
+fn total_duplication_size(duplication: &IntervalMap<Option<DuplicationInfo>>) -> u64 {
     duplication
-        .ranges()
+        .iter()
+        .flat_map(|(range, info)| Some((range, info.as_ref()?)))
         .map(|(range, info)| info.duplication(&range))
         .sum()
 }
@@ -216,7 +238,7 @@ pub fn get_merge_segments<T: Compactable>(
         'search: loop {
             let mut current_set = smallvec![start_index];
             let mut current_size = start_compactable.size();
-            let mut duplication: IntervalMap<DuplicationInfo> = IntervalMap::new();
+            let mut duplication = IntervalMap::<Option<DuplicationInfo>>::new();
             let mut current_skip = 0;
 
             // We will capture compactables in the current_range until we find a optimal merge
@@ -304,8 +326,8 @@ pub fn get_merge_segments<T: Compactable>(
                 // set.
                 current_set.push(next_index);
                 current_size += size;
-                duplication.update(&range, |dup_info| {
-                    dup_info.add(size, &range);
+                duplication.update(range.clone(), |dup_info| {
+                    dup_info.get_or_insert_default().add(size, &range);
                 });
             }
         }
@@ -321,23 +343,19 @@ pub fn get_merge_segments<T: Compactable>(
 
     // Remove single compectable segments that don't overlap with previous segments. We don't need
     // to touch them.
-    // TODO: Technically it's a bit inefficient to use an IntervalMap here, but
-    // it's not very hot code anyway.
-    let mut used_ranges: IntervalMap<bool> = IntervalMap::new();
+    let mut used_ranges = IntervalMap::<bool>::new();
     merge_segments.retain(|segment| {
         // Remove a single element segments which doesn't overlap with previous used ranges.
         if segment.len() == 1 {
             let range = compactables[segment[0]].range();
-            if !used_ranges.test(&range, |in_use| *in_use) {
+            if !used_ranges.iter_intersecting(range).any(|(_, v)| *v) {
                 return false;
             }
         }
         // Mark the ranges of the segment as used.
         for i in segment {
             let range = compactables[*i].range();
-            used_ranges.update(&range, |in_use| {
-                *in_use = true;
-            });
+            used_ranges.replace(range, true);
         }
         true
     });
@@ -357,24 +375,27 @@ mod tests {
     use super::*;
 
     struct TestCompactable {
-        range: Range,
+        range: RangeInclusive<u64>,
         size: u64,
     }
 
     impl Compactable for TestCompactable {
-        fn range(&self) -> Range {
-            self.range
+        fn range(&self) -> RangeInclusive<u64> {
+            self.range.clone()
         }
 
         fn size(&self) -> u64 {
             self.size
         }
     }
 
-    fn compact<const N: usize>(ranges: [(u64, u64); N], config: &CompactConfig) -> Vec<Vec<usize>> {
+    fn compact<const N: usize>(
+        ranges: [RangeInclusive<u64>; N],
+        config: &CompactConfig,
+    ) -> Vec<Vec<usize>> {
         let compactables = ranges
-            .iter()
-            .map(|&range| TestCompactable { range, size: 100 })
+            .into_iter()
+            .map(|range| TestCompactable { range, size: 100 })
             .collect::<Vec<_>>();
         let jobs = get_merge_segments(&compactables, config);
         jobs.into_iter()
@@ -386,15 +407,15 @@ mod tests {
     fn test_compaction_jobs_by_count() {
         let merge_jobs = compact(
             [
-                (0, 10),
-                (10, 30),
-                (9, 13),
-                (0, 30),
-                (40, 44),
-                (41, 42),
-                (41, 47),
-                (90, 100),
-                (30, 40),
+                0..=10,
+                10..=30,
+                9..=13,
+                0..=30,
+                40..=44,
+                41..=42,
+                41..=47,
+                90..=100,
+                30..=40,
             ],
             &CompactConfig {
                 min_merge_count: 2,
@@ -413,15 +434,15 @@ mod tests {
     fn test_compaction_jobs_by_size() {
         let merge_jobs = compact(
             [
-                (0, 10),
-                (10, 30),
-                (9, 13),
-                (0, 30),
-                (40, 44),
-                (41, 42),
-                (41, 47),
-                (90, 100),
-                (30, 40),
+                0..=10,
+                10..=30,
+                9..=13,
+                0..=30,
+                40..=44,
+                41..=42,
+                41..=47,
+                90..=100,
+                30..=40,
             ],
             &CompactConfig {
                 min_merge_count: 2,
@@ -440,15 +461,15 @@ mod tests {
     fn test_compaction_jobs_full() {
         let merge_jobs = compact(
             [
-                (0, 10),
-                (10, 30),
-                (9, 13),
-                (0, 30),
-                (40, 44),
-                (41, 42),
-                (41, 47),
-                (90, 100),
-                (30, 40),
+                0..=10,
+                10..=30,
+                9..=13,
+                0..=30,
+                40..=44,
+                41..=42,
+                41..=47,
+                90..=100,
+                30..=40,
             ],
             &CompactConfig {
                 min_merge_count: 2,
@@ -467,15 +488,15 @@ mod tests {
     fn test_compaction_jobs_big() {
         let merge_jobs = compact(
             [
-                (0, 10),
-                (10, 30),
-                (9, 13),
-                (0, 30),
-                (40, 44),
-                (41, 42),
-                (41, 47),
-                (90, 100),
-                (30, 40),
+                0..=10,
+                10..=30,
+                9..=13,
+                0..=30,
+                40..=44,
+                41..=42,
+                41..=47,
+                90..=100,
+                30..=40,
             ],
             &CompactConfig {
                 min_merge_count: 2,
@@ -494,15 +515,15 @@ mod tests {
     fn test_compaction_jobs_small() {
         let merge_jobs = compact(
             [
-                (0, 10),
-                (10, 30),
-                (9, 13),
-                (0, 30),
-                (40, 44),
-                (41, 42),
-                (41, 47),
-                (90, 100),
-                (30, 40),
+                0..=10,
+                10..=30,
+                9..=13,
+                0..=30,
+                40..=44,
+                41..=42,
+                41..=47,
+                90..=100,
+                30..=40,
             ],
             &CompactConfig {
                 min_merge_count: 2,
@@ -526,8 +547,8 @@ mod tests {
         for (i, c) in compactables.iter().enumerate() {
             let range = c.range();
             let size = c.size();
-            let start = (range.0 / char_width) as usize;
-            let end = (range.1 / char_width) as usize;
+            let start = usize::try_from(range.start() / char_width).unwrap();
+            let end = usize::try_from(range.end() / char_width).unwrap();
             let mut line = format!("{i:>3} | ");
             for j in 0..WIDTH {
                 if j >= start && j <= end {
@@ -568,7 +589,7 @@ mod tests {
 
         for _ in 0..ITERATIONS {
             let total_size = containers.iter().map(|c| c.keys.len()).sum::<usize>();
-            let metrics = compute_metrics(&containers, (0, KEY_RANGE));
+            let metrics = compute_metrics(&containers, 0..=KEY_RANGE);
             debug_print_compactables(&containers, KEY_RANGE);
             println!(
                 "size: {}, coverage: {}, overlap: {}, duplication: {}, items: {}",
@@ -599,7 +620,7 @@ mod tests {
                 do_compact(&mut containers, jobs, batch_index);
                 number_of_compactions += 1;
 
-                let new_metrics = compute_metrics(&containers, (0, KEY_RANGE));
+                let new_metrics = compute_metrics(&containers, 0..=KEY_RANGE);
                 println!(
                     "Compaction done: coverage: {} ({}), overlap: {} ({}), duplication: {} ({})",
                     new_metrics.coverage,
@@ -630,7 +651,7 @@ mod tests {
         }
         println!("Number of compactions: {number_of_compactions}");
 
-        let metrics = compute_metrics(&containers, (0, KEY_RANGE));
+        let metrics = compute_metrics(&containers, 0..=KEY_RANGE);
         assert!(number_of_compactions < 40);
         assert!(containers.len() < 30);
         assert!(metrics.duplication < 0.5);
@@ -649,8 +670,8 @@ mod tests {
     }
 
     impl Compactable for Container {
-        fn range(&self) -> Range {
-            (self.keys[0], *self.keys.last().unwrap())
+        fn range(&self) -> RangeInclusive<u64> {
+            (self.keys[0])..=(*self.keys.last().unwrap())
         }
 
         fn size(&self) -> u64 {
@@ -660,7 +681,7 @@ mod tests {
 
     impl Debug for Container {
         fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-            let (l, r) = self.range();
+            let (l, r) = self.range().into_inner();
             write!(
                 f,
                 "#{} {}b {l} - {r} ({})",

filename: turbopack/crates/turbo-persistence/src/db.rs
patch: @@ -5,6 +5,7 @@ use std::{
     fs::{self, File, OpenOptions, ReadDir},
     io::{BufWriter, Write},
     mem::{MaybeUninit, swap, transmute},
+    ops::RangeInclusive,
     path::{Path, PathBuf},
     sync::{
         Arc,
@@ -747,8 +748,8 @@ impl TurboPersistence {
         }
 
         impl Compactable for SstWithRange {
-            fn range(&self) -> (u64, u64) {
-                (self.range.min_hash, self.range.max_hash)
+            fn range(&self) -> RangeInclusive<u64> {
+                self.range.min_hash..=self.range.max_hash
             }
 
             fn size(&self) -> u64 {
@@ -823,7 +824,7 @@ impl TurboPersistence {
                 }
 
                 {
-                    let metrics = compute_metrics(&ssts_with_ranges, (0, u64::MAX));
+                    let metrics = compute_metrics(&ssts_with_ranges, 0..=u64::MAX);
                     let guard = log_mutex.lock();
                     let mut log = self.open_log()?;
                     writeln!(
@@ -839,7 +840,7 @@ impl TurboPersistence {
                         writeln!(log, "  merge")?;
                         for i in job.iter() {
                             let seq = ssts_with_ranges[*i].seq;
-                            let (min, max) = ssts_with_ranges[*i].range();
+                            let (min, max) = ssts_with_ranges[*i].range().into_inner();
                             writeln!(log, "    {seq:08} {min:016x}-{max:016x}")?;
                         }
                     }