Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 550 insertions, 0 deletions

diff --git a/third_party/rust/range-alloc/.cargo-checksum.json b/third_party/rust/range-alloc/.cargo-checksum.json
new file mode 100644
index 0000000000..187cb6cb08
--- /dev/null
+++ b/third_party/rust/range-alloc/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"2b0e7d63d79821d7a1515971a75adefaa96acef117e15fcdf50b49dda71acd6a","LICENSE.APACHE":"a6cba85bc92e0cff7a450b1d873c0eaa2e9fc96bf472df0247a26bec77bf3ff9","LICENSE.MIT":"ba00052102ed87948bb8822d6e1c496260c83042887b22bb5caad922ec025a60","src/lib.rs":"a62600cbf426d2469333c0ccee16041cf63588cdeb8dad78387e7ab18e70d29e"},"package":"9c8a99fddc9f0ba0a85884b8d14e3592853e787d581ca1816c91349b10e4eeab"}
\ No newline at end of file
diff --git a/third_party/rust/range-alloc/Cargo.toml b/third_party/rust/range-alloc/Cargo.toml
new file mode 100644
index 0000000000..c03c7d2111
--- /dev/null
+++ b/third_party/rust/range-alloc/Cargo.toml
@@ -0,0 +1,23 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2018"
+name = "range-alloc"
+version = "0.1.3"
+authors = ["the gfx-rs Developers"]
+description = "Generic range allocator"
+homepage = "https://github.com/gfx-rs/range-alloc"
+documentation = "https://docs.rs/range-alloc"
+keywords = ["allocator"]
+categories = ["memory-management"]
+license = "MIT OR Apache-2.0"
+repository = "https://github.com/gfx-rs/range-alloc"
diff --git a/third_party/rust/range-alloc/LICENSE.APACHE b/third_party/rust/range-alloc/LICENSE.APACHE
new file mode 100644
index 0000000000..d9a10c0d8e
--- /dev/null
+++ b/third_party/rust/range-alloc/LICENSE.APACHE
@@ -0,0 +1,176 @@
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
diff --git a/third_party/rust/range-alloc/LICENSE.MIT b/third_party/rust/range-alloc/LICENSE.MIT
new file mode 100644
index 0000000000..c706b62c79
--- /dev/null
+++ b/third_party/rust/range-alloc/LICENSE.MIT
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 The gfx-rs developers
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/third_party/rust/range-alloc/src/lib.rs b/third_party/rust/range-alloc/src/lib.rs
new file mode 100644
index 0000000000..767d31e909
--- /dev/null
+++ b/third_party/rust/range-alloc/src/lib.rs
@@ -0,0 +1,329 @@
+use std::{
+    fmt::Debug,
+    iter::Sum,
+    ops::{Add, AddAssign, Range, Sub},
+};
+
+#[derive(Debug)]
+pub struct RangeAllocator<T> {
+    /// The range this allocator covers.
+    initial_range: Range<T>,
+    /// A Vec of ranges in this heap which are unused.
+    /// Must be ordered with ascending range start to permit short circuiting allocation.
+    /// No two ranges in this vec may overlap.
+    free_ranges: Vec<Range<T>>,
+}
+
+#[derive(Clone, Debug, PartialEq)]
+pub struct RangeAllocationError<T> {
+    pub fragmented_free_length: T,
+}
+
+impl<T> RangeAllocator<T>
+where
+    T: Clone + Copy + Add<Output = T> + AddAssign + Sub<Output = T> + Eq + PartialOrd + Debug,
+{
+    pub fn new(range: Range<T>) -> Self {
+        RangeAllocator {
+            initial_range: range.clone(),
+            free_ranges: vec![range],
+        }
+    }
+
+    pub fn initial_range(&self) -> &Range<T> {
+        &self.initial_range
+    }
+
+    pub fn grow_to(&mut self, new_end: T) {
+        if let Some(last_range) = self.free_ranges.last_mut() {
+            last_range.end = new_end;
+        } else {
+            self.free_ranges.push(self.initial_range.end..new_end);
+        }
+
+        self.initial_range.end = new_end;
+    }
+
+    pub fn allocate_range(&mut self, length: T) -> Result<Range<T>, RangeAllocationError<T>> {
+        assert_ne!(length + length, length);
+        let mut best_fit: Option<(usize, Range<T>)> = None;
+
+        // This is actually correct. With the trait bound as it is, we have
+        // no way to summon a value of 0 directly, so we make one by subtracting
+        // something from itself. Once the trait bound can be changed, this can
+        // be fixed.
+        #[allow(clippy::eq_op)]
+        let mut fragmented_free_length = length - length;
+        for (index, range) in self.free_ranges.iter().cloned().enumerate() {
+            let range_length = range.end - range.start;
+            fragmented_free_length += range_length;
+            if range_length < length {
+                continue;
+            } else if range_length == length {
+                // Found a perfect fit, so stop looking.
+                best_fit = Some((index, range));
+                break;
+            }
+            best_fit = Some(match best_fit {
+                Some((best_index, best_range)) => {
+                    // Find best fit for this allocation to reduce memory fragmentation.
+                    if range_length < best_range.end - best_range.start {
+                        (index, range)
+                    } else {
+                        (best_index, best_range.clone())
+                    }
+                }
+                None => (index, range),
+            });
+        }
+        match best_fit {
+            Some((index, range)) => {
+                if range.end - range.start == length {
+                    self.free_ranges.remove(index);
+                } else {
+                    self.free_ranges[index].start += length;
+                }
+                Ok(range.start..(range.start + length))
+            }
+            None => Err(RangeAllocationError {
+                fragmented_free_length,
+            }),
+        }
+    }
+
+    pub fn free_range(&mut self, range: Range<T>) {
+        assert!(self.initial_range.start <= range.start && range.end <= self.initial_range.end);
+        assert!(range.start < range.end);
+
+        // Get insertion position.
+        let i = self
+            .free_ranges
+            .iter()
+            .position(|r| r.start > range.start)
+            .unwrap_or(self.free_ranges.len());
+
+        // Try merging with neighboring ranges in the free list.
+        // Before: |left|-(range)-|right|
+        if i > 0 && range.start == self.free_ranges[i - 1].end {
+            // Merge with |left|.
+            self.free_ranges[i - 1].end =
+                if i < self.free_ranges.len() && range.end == self.free_ranges[i].start {
+                    // Check for possible merge with |left| and |right|.
+                    let right = self.free_ranges.remove(i);
+                    right.end
+                } else {
+                    range.end
+                };
+
+            return;
+        } else if i < self.free_ranges.len() && range.end == self.free_ranges[i].start {
+            // Merge with |right|.
+            self.free_ranges[i].start = if i > 0 && range.start == self.free_ranges[i - 1].end {
+                // Check for possible merge with |left| and |right|.
+                let left = self.free_ranges.remove(i - 1);
+                left.start
+            } else {
+                range.start
+            };
+
+            return;
+        }
+
+        // Debug checks
+        assert!(
+            (i == 0 || self.free_ranges[i - 1].end < range.start)
+                && (i >= self.free_ranges.len() || range.end < self.free_ranges[i].start)
+        );
+
+        self.free_ranges.insert(i, range);
+    }
+
+    /// Returns an iterator over allocated non-empty ranges
+    pub fn allocated_ranges(&self) -> impl Iterator<Item = Range<T>> + '_ {
+        let first = match self.free_ranges.first() {
+            Some(Range { ref start, .. }) if *start > self.initial_range.start => {
+                Some(self.initial_range.start..*start)
+            }
+            None => Some(self.initial_range.clone()),
+            _ => None,
+        };
+
+        let last = match self.free_ranges.last() {
+            Some(Range { end, .. }) if *end < self.initial_range.end => {
+                Some(*end..self.initial_range.end)
+            }
+            _ => None,
+        };
+
+        let mid = self
+            .free_ranges
+            .iter()
+            .zip(self.free_ranges.iter().skip(1))
+            .map(|(ra, rb)| ra.end..rb.start);
+
+        first.into_iter().chain(mid).chain(last)
+    }
+
+    pub fn reset(&mut self) {
+        self.free_ranges.clear();
+        self.free_ranges.push(self.initial_range.clone());
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.free_ranges.len() == 1 && self.free_ranges[0] == self.initial_range
+    }
+}
+
+impl<T: Copy + Sub<Output = T> + Sum> RangeAllocator<T> {
+    pub fn total_available(&self) -> T {
+        self.free_ranges
+            .iter()
+            .map(|range| range.end - range.start)
+            .sum()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_basic_allocation() {
+        let mut alloc = RangeAllocator::new(0..10);
+        // Test if an allocation works
+        assert_eq!(alloc.allocate_range(4), Ok(0..4));
+        assert!(alloc.allocated_ranges().eq(std::iter::once(0..4)));
+        // Free the prior allocation
+        alloc.free_range(0..4);
+        // Make sure the free actually worked
+        assert_eq!(alloc.free_ranges, vec![0..10]);
+        assert!(alloc.allocated_ranges().eq(std::iter::empty()));
+    }
+
+    #[test]
+    fn test_out_of_space() {
+        let mut alloc = RangeAllocator::new(0..10);
+        // Test if the allocator runs out of space correctly
+        assert_eq!(alloc.allocate_range(10), Ok(0..10));
+        assert!(alloc.allocated_ranges().eq(std::iter::once(0..10)));
+        assert!(alloc.allocate_range(4).is_err());
+        alloc.free_range(0..10);
+    }
+
+    #[test]
+    fn test_grow() {
+        let mut alloc = RangeAllocator::new(0..11);
+        // Test if the allocator runs out of space correctly
+        assert_eq!(alloc.allocate_range(10), Ok(0..10));
+        assert!(alloc.allocated_ranges().eq(std::iter::once(0..10)));
+        assert!(alloc.allocate_range(4).is_err());
+        alloc.grow_to(20);
+        assert_eq!(alloc.allocate_range(4), Ok(10..14));
+        alloc.free_range(0..14);
+    }
+
+    #[test]
+    fn test_dont_use_block_that_is_too_small() {
+        let mut alloc = RangeAllocator::new(0..10);
+        // Allocate three blocks then free the middle one and check for correct state
+        assert_eq!(alloc.allocate_range(3), Ok(0..3));
+        assert_eq!(alloc.allocate_range(3), Ok(3..6));
+        assert_eq!(alloc.allocate_range(3), Ok(6..9));
+        alloc.free_range(3..6);
+        assert_eq!(alloc.free_ranges, vec![3..6, 9..10]);
+        assert_eq!(
+            alloc.allocated_ranges().collect::<Vec<Range<i32>>>(),
+            vec![0..3, 6..9]
+        );
+        // Now request space that the middle block can fill, but the end one can't.
+        assert_eq!(alloc.allocate_range(3), Ok(3..6));
+    }
+
+    #[test]
+    fn test_free_blocks_in_middle() {
+        let mut alloc = RangeAllocator::new(0..100);
+        // Allocate many blocks then free every other block.
+        assert_eq!(alloc.allocate_range(10), Ok(0..10));
+        assert_eq!(alloc.allocate_range(10), Ok(10..20));
+        assert_eq!(alloc.allocate_range(10), Ok(20..30));
+        assert_eq!(alloc.allocate_range(10), Ok(30..40));
+        assert_eq!(alloc.allocate_range(10), Ok(40..50));
+        assert_eq!(alloc.allocate_range(10), Ok(50..60));
+        assert_eq!(alloc.allocate_range(10), Ok(60..70));
+        assert_eq!(alloc.allocate_range(10), Ok(70..80));
+        assert_eq!(alloc.allocate_range(10), Ok(80..90));
+        assert_eq!(alloc.allocate_range(10), Ok(90..100));
+        assert_eq!(alloc.free_ranges, vec![]);
+        assert!(alloc.allocated_ranges().eq(std::iter::once(0..100)));
+        alloc.free_range(10..20);
+        alloc.free_range(30..40);
+        alloc.free_range(50..60);
+        alloc.free_range(70..80);
+        alloc.free_range(90..100);
+        // Check that the right blocks were freed.
+        assert_eq!(
+            alloc.free_ranges,
+            vec![10..20, 30..40, 50..60, 70..80, 90..100]
+        );
+        assert_eq!(
+            alloc.allocated_ranges().collect::<Vec<Range<i32>>>(),
+            vec![0..10, 20..30, 40..50, 60..70, 80..90]
+        );
+        // Fragment the memory on purpose a bit.
+        assert_eq!(alloc.allocate_range(6), Ok(10..16));
+        assert_eq!(alloc.allocate_range(6), Ok(30..36));
+        assert_eq!(alloc.allocate_range(6), Ok(50..56));
+        assert_eq!(alloc.allocate_range(6), Ok(70..76));
+        assert_eq!(alloc.allocate_range(6), Ok(90..96));
+        // Check for fragmentation.
+        assert_eq!(
+            alloc.free_ranges,
+            vec![16..20, 36..40, 56..60, 76..80, 96..100]
+        );
+        assert_eq!(
+            alloc.allocated_ranges().collect::<Vec<Range<i32>>>(),
+            vec![0..16, 20..36, 40..56, 60..76, 80..96]
+        );
+        // Fill up the fragmentation
+        assert_eq!(alloc.allocate_range(4), Ok(16..20));
+        assert_eq!(alloc.allocate_range(4), Ok(36..40));
+        assert_eq!(alloc.allocate_range(4), Ok(56..60));
+        assert_eq!(alloc.allocate_range(4), Ok(76..80));
+        assert_eq!(alloc.allocate_range(4), Ok(96..100));
+        // Check that nothing is free.
+        assert_eq!(alloc.free_ranges, vec![]);
+        assert!(alloc.allocated_ranges().eq(std::iter::once(0..100)));
+    }
+
+    #[test]
+    fn test_ignore_block_if_another_fits_better() {
+        let mut alloc = RangeAllocator::new(0..10);
+        // Allocate blocks such that the only free spaces available are 3..6 and 9..10
+        // in order to prepare for the next test.
+        assert_eq!(alloc.allocate_range(3), Ok(0..3));
+        assert_eq!(alloc.allocate_range(3), Ok(3..6));
+        assert_eq!(alloc.allocate_range(3), Ok(6..9));
+        alloc.free_range(3..6);
+        assert_eq!(alloc.free_ranges, vec![3..6, 9..10]);
+        assert_eq!(
+            alloc.allocated_ranges().collect::<Vec<Range<i32>>>(),
+            vec![0..3, 6..9]
+        );
+        // Now request space that can be filled by 3..6 but should be filled by 9..10
+        // because 9..10 is a perfect fit.
+        assert_eq!(alloc.allocate_range(1), Ok(9..10));
+    }
+
+    #[test]
+    fn test_merge_neighbors() {
+        let mut alloc = RangeAllocator::new(0..9);
+        assert_eq!(alloc.allocate_range(3), Ok(0..3));
+        assert_eq!(alloc.allocate_range(3), Ok(3..6));
+        assert_eq!(alloc.allocate_range(3), Ok(6..9));
+        alloc.free_range(0..3);
+        alloc.free_range(6..9);
+        alloc.free_range(3..6);
+        assert_eq!(alloc.free_ranges, vec![0..9]);
+        assert!(alloc.allocated_ranges().eq(std::iter::empty()));
+    }
+}