Merging upstream version 1.72.1+dfsg1.

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

10 files changed, 1418 insertions, 139 deletions

diff --git a/vendor/slab/.cargo-checksum.json b/vendor/slab/.cargo-checksum.json
index 112dcc20e..d8e4dd2bc 100644
--- a/vendor/slab/.cargo-checksum.json
+++ b/vendor/slab/.cargo-checksum.json
@@ -1 +1 @@
-{"files":{"CHANGELOG.md":"f6f61243fdf15892a03150fad73f0e9bb959845e91596df87d1733874800f34e","Cargo.toml":"c28fd4f04c85aa8099590d4f3b120902a0466c1cf3cbfa2aace227b8389fc173","LICENSE":"8ce0830173fdac609dfb4ea603fdc002c2f4af0dc9b1a005653f5da9cf534b18","README.md":"8b455097ac90777929da00702b384d9b363bb8535e292df2f98d2f2ff321eff5","src/lib.rs":"a78013cc8ceb83bf096b035cda8710474b0c353bcd52a46e5d27ef0efb636f5c","tests/slab.rs":"f9be8e2a6f54285c61238b0a1cde26f7591a7abad5a22a42ea6d195679c1bd91"},"package":"c111b5bd5695e56cffe5129854aa230b39c93a305372fdbb2668ca2394eea9f8"}
\ No newline at end of file
+{"files":{"CHANGELOG.md":"c882a7b35bdc9c3acaad4b4db53776a0a37a01caa05510a46cb3422628a96061","Cargo.toml":"5e26ff6d3f231db8a60a9d1693556cdb1c14f0dd1266b6c33a445a444ae79248","LICENSE":"8ce0830173fdac609dfb4ea603fdc002c2f4af0dc9b1a005653f5da9cf534b18","README.md":"6e8d6d493aec6526593ae9b05e3b21d3f878c5816a94af9d372598e03406b35f","build.rs":"2c008232a3ae7c83c166f61c2942314717976776a4dba38e9063cd8e57a1b9bd","src/builder.rs":"87e629b1f9853d910389635b27a42391f1681cd5638d81e386215211e8b67847","src/lib.rs":"6f4e73052cb4929231279267450eab3f3b466cb8288c85ed487606d226dd3079","src/serde.rs":"e58650a04644cb732119f50eefe6a3066104b5b41be7074e12525e05e2ad21b7","tests/serde.rs":"bb28112509dbb6949528802d05a1b1e34d2e5ff9d3ba5f62aa801cfb3de7a78e","tests/slab.rs":"8d608a409b8c1543aada79c9817a18e295565e7233df88b412499f27d132c0fe"},"package":"6528351c9bc8ab22353f9d776db39a20288e8d6c37ef8cfe3317cf875eecfc2d"}
\ No newline at end of file
diff --git a/vendor/slab/CHANGELOG.md b/vendor/slab/CHANGELOG.md
index 9a222b41d..db545827a 100644
--- a/vendor/slab/CHANGELOG.md
+++ b/vendor/slab/CHANGELOG.md
@@ -1,3 +1,45 @@
+# 0.4.8 (January 20, 2022)
+
+* Fixed documentation about overflow (#124)
+* Document panic in `get2_mut` (#131)
+* Refactoring (#129, #132)
+
+# 0.4.7 (July 19, 2022)
+
+* Use `#[track_caller]` on Rust 1.46+ (#119)
+* Make `Slab::new` const on Rust 1.39+ (#119)
+
+# 0.4.6 (April 2, 2022)
+
+* Add `Slab::vacant_key` (#114)
+* Fix stacked borrows violation in `Slab::get2_unchecked_mut` (#115)
+
+# 0.4.5 (October 13, 2021)
+
+* Add alternate debug output for listing items in the slab (#108)
+* Fix typo in debug output of IntoIter (#109)
+* Impl 'Clone' for 'Iter' (#110)
+
+# 0.4.4 (August 06, 2021)
+
+* Fix panic in `FromIterator` impl (#102)
+* Fix compatibility with older clippy versions (#104)
+* Add `try_remove` method (#89)
+* Implement `ExactSizeIterator` and `FusedIterator` for iterators (#92)
+
+# 0.4.3 (April 20, 2021)
+
+* Add no_std support for Rust 1.36 and above (#71).
+* Add `get2_mut` and `get2_unchecked_mut` methods (#65).
+* Make `shrink_to_fit()` remove trailing vacant entries (#62).
+* Implement `FromIterator<(usize, T)>` (#62).
+* Implement `IntoIterator<Item = (usize, T)>` (#62).
+* Provide `size_hint()` of the iterators (#62).
+* Make all iterators reversible (#62).
+* Add `key_of()` method (#61)
+* Add `compact()` method (#60)
+* Add support for serde (#85)
+
 # 0.4.2 (January 11, 2019)
 
 * Add `Slab::drain` (#56).
diff --git a/vendor/slab/Cargo.toml b/vendor/slab/Cargo.toml
index 9e9fc4253..8823fb823 100644
--- a/vendor/slab/Cargo.toml
+++ b/vendor/slab/Cargo.toml
@@ -3,22 +3,53 @@
 # 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
+# to registry (e.g., crates.io) dependencies.
 #
-# If you believe there's an error in this file please file an
-# issue against the rust-lang/cargo repository. If you're
-# editing this file be aware that the upstream Cargo.toml
-# will likely look very different (and much more reasonable)
+# 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"
+rust-version = "1.31"
 name = "slab"
-version = "0.4.2"
+version = "0.4.8"
 authors = ["Carl Lerche <me@carllerche.com>"]
+exclude = ["/.*"]
 description = "Pre-allocated storage for a uniform data type"
-homepage = "https://github.com/carllerche/slab"
-documentation = "https://docs.rs/slab/0.4.2/slab/"
 readme = "README.md"
-keywords = ["slab", "allocator"]
-categories = ["memory-management", "data-structures"]
+keywords = [
+    "slab",
+    "allocator",
+    "no_std",
+]
+categories = [
+    "memory-management",
+    "data-structures",
+    "no-std",
+]
 license = "MIT"
-repository = "https://github.com/carllerche/slab"
+repository = "https://github.com/tokio-rs/slab"
+
+[dependencies.serde]
+version = "1.0.95"
+features = ["alloc"]
+optional = true
+default-features = false
+
+[dev-dependencies.rustversion]
+version = "1"
+
+[dev-dependencies.serde]
+version = "1"
+features = ["derive"]
+
+[dev-dependencies.serde_test]
+version = "1"
+
+[build-dependencies.autocfg]
+version = "1"
+
+[features]
+default = ["std"]
+std = []
diff --git a/vendor/slab/README.md b/vendor/slab/README.md
index 2609ffb71..428138937 100644
--- a/vendor/slab/README.md
+++ b/vendor/slab/README.md
@@ -2,10 +2,15 @@
 
 Pre-allocated storage for a uniform data type.
 
-[![Crates.io](https://img.shields.io/crates/v/slab.svg?maxAge=2592000)](https://crates.io/crates/slab)
-[![Build Status](https://travis-ci.org/carllerche/slab.svg?branch=master)](https://travis-ci.org/carllerche/slab)
+[![Crates.io][crates-badge]][crates-url]
+[![Build Status][ci-badge]][ci-url]
 
-[Documentation](https://docs.rs/slab/0.4.2/slab/)
+[crates-badge]: https://img.shields.io/crates/v/slab
+[crates-url]: https://crates.io/crates/slab
+[ci-badge]: https://img.shields.io/github/actions/workflow/status/tokio-rs/slab/ci.yml?branch=master
+[ci-url]: https://github.com/tokio-rs/slab/actions
+
+[Documentation](https://docs.rs/slab)
 
 ## Usage
 
@@ -13,14 +18,12 @@ To use `slab`, first add this to your `Cargo.toml`:
 
 ```toml
 [dependencies]
-slab = "0.4.2"
+slab = "0.4"
 ```
 
 Next, add this to your crate:
 
 ```rust
-extern crate slab;
-
 use slab::Slab;
 
 let mut slab = Slab::new();
diff --git a/vendor/slab/build.rs b/vendor/slab/build.rs
new file mode 100644
index 000000000..b60351aaf
--- /dev/null
+++ b/vendor/slab/build.rs
@@ -0,0 +1,24 @@
+fn main() {
+    let cfg = match autocfg::AutoCfg::new() {
+        Ok(cfg) => cfg,
+        Err(e) => {
+            // If we couldn't detect the compiler version and features, just
+            // print a warning. This isn't a fatal error: we can still build
+            // Slab, we just can't enable cfgs automatically.
+            println!(
+                "cargo:warning=slab: failed to detect compiler features: {}",
+                e
+            );
+            return;
+        }
+    };
+    // Note that this is `no_`*, not `has_*`. This allows treating as the latest
+    // stable rustc is used when the build script doesn't run. This is useful
+    // for non-cargo build systems that don't run the build script.
+    if !cfg.probe_rustc_version(1, 39) {
+        println!("cargo:rustc-cfg=slab_no_const_vec_new");
+    }
+    if !cfg.probe_rustc_version(1, 46) {
+        println!("cargo:rustc-cfg=slab_no_track_caller");
+    }
+}
diff --git a/vendor/slab/src/builder.rs b/vendor/slab/src/builder.rs
new file mode 100644
index 000000000..8e50a2016
--- /dev/null
+++ b/vendor/slab/src/builder.rs
@@ -0,0 +1,63 @@
+use crate::{Entry, Slab};
+
+// Building `Slab` from pairs (usize, T).
+pub(crate) struct Builder<T> {
+    slab: Slab<T>,
+    vacant_list_broken: bool,
+    first_vacant_index: Option<usize>,
+}
+
+impl<T> Builder<T> {
+    pub(crate) fn with_capacity(capacity: usize) -> Self {
+        Self {
+            slab: Slab::with_capacity(capacity),
+            vacant_list_broken: false,
+            first_vacant_index: None,
+        }
+    }
+    pub(crate) fn pair(&mut self, key: usize, value: T) {
+        let slab = &mut self.slab;
+        if key < slab.entries.len() {
+            // iterator is not sorted, might need to recreate vacant list
+            if let Entry::Vacant(_) = slab.entries[key] {
+                self.vacant_list_broken = true;
+                slab.len += 1;
+            }
+            // if an element with this key already exists, replace it.
+            // This is consistent with HashMap and BtreeMap
+            slab.entries[key] = Entry::Occupied(value);
+        } else {
+            if self.first_vacant_index.is_none() && slab.entries.len() < key {
+                self.first_vacant_index = Some(slab.entries.len());
+            }
+            // insert holes as necessary
+            while slab.entries.len() < key {
+                // add the entry to the start of the vacant list
+                let next = slab.next;
+                slab.next = slab.entries.len();
+                slab.entries.push(Entry::Vacant(next));
+            }
+            slab.entries.push(Entry::Occupied(value));
+            slab.len += 1;
+        }
+    }
+
+    pub(crate) fn build(self) -> Slab<T> {
+        let mut slab = self.slab;
+        if slab.len == slab.entries.len() {
+            // no vacant entries, so next might not have been updated
+            slab.next = slab.entries.len();
+        } else if self.vacant_list_broken {
+            slab.recreate_vacant_list();
+        } else if let Some(first_vacant_index) = self.first_vacant_index {
+            let next = slab.entries.len();
+            match &mut slab.entries[first_vacant_index] {
+                Entry::Vacant(n) => *n = next,
+                _ => unreachable!(),
+            }
+        } else {
+            unreachable!()
+        }
+        slab
+    }
+}
diff --git a/vendor/slab/src/lib.rs b/vendor/slab/src/lib.rs
index a3638ca3a..e23ead912 100644
--- a/vendor/slab/src/lib.rs
+++ b/vendor/slab/src/lib.rs
@@ -1,6 +1,14 @@
-#![doc(html_root_url = "https://docs.rs/slab/0.4.2")]
-#![deny(warnings, missing_docs, missing_debug_implementations)]
-#![cfg_attr(test, deny(warnings, unreachable_pub))]
+#![cfg_attr(not(feature = "std"), no_std)]
+#![warn(
+    missing_debug_implementations,
+    missing_docs,
+    rust_2018_idioms,
+    unreachable_pub
+)]
+#![doc(test(
+    no_crate_inject,
+    attr(deny(warnings, rust_2018_idioms), allow(dead_code, unused_variables))
+))]
 
 //! Pre-allocated storage for a uniform data type.
 //!
@@ -102,10 +110,19 @@
 //!
 //! [`Slab::with_capacity`]: struct.Slab.html#with_capacity
 
-use std::iter::IntoIterator;
-use std::ops;
-use std::vec;
-use std::{fmt, mem};
+#[cfg(not(feature = "std"))]
+extern crate alloc;
+#[cfg(feature = "std")]
+extern crate std as alloc;
+
+#[cfg(feature = "serde")]
+mod serde;
+
+mod builder;
+
+use alloc::vec::{self, Vec};
+use core::iter::{self, FromIterator, FusedIterator};
+use core::{fmt, mem, ops, slice};
 
 /// Pre-allocated storage for a uniform data type
 ///
@@ -154,25 +171,43 @@ impl<T> Default for Slab<T> {
 /// assert_eq!("hello", slab[hello].1);
 /// ```
 #[derive(Debug)]
-pub struct VacantEntry<'a, T: 'a> {
+pub struct VacantEntry<'a, T> {
     slab: &'a mut Slab<T>,
     key: usize,
 }
 
+/// A consuming iterator over the values stored in a `Slab`
+pub struct IntoIter<T> {
+    entries: iter::Enumerate<vec::IntoIter<Entry<T>>>,
+    len: usize,
+}
+
 /// An iterator over the values stored in the `Slab`
-pub struct Iter<'a, T: 'a> {
-    entries: std::slice::Iter<'a, Entry<T>>,
-    curr: usize,
+pub struct Iter<'a, T> {
+    entries: iter::Enumerate<slice::Iter<'a, Entry<T>>>,
+    len: usize,
+}
+
+impl<'a, T> Clone for Iter<'a, T> {
+    fn clone(&self) -> Self {
+        Self {
+            entries: self.entries.clone(),
+            len: self.len,
+        }
+    }
 }
 
 /// A mutable iterator over the values stored in the `Slab`
-pub struct IterMut<'a, T: 'a> {
-    entries: std::slice::IterMut<'a, Entry<T>>,
-    curr: usize,
+pub struct IterMut<'a, T> {
+    entries: iter::Enumerate<slice::IterMut<'a, Entry<T>>>,
+    len: usize,
 }
 
 /// A draining iterator for `Slab`
-pub struct Drain<'a, T: 'a>(vec::Drain<'a, Entry<T>>);
+pub struct Drain<'a, T> {
+    inner: vec::Drain<'a, Entry<T>>,
+    len: usize,
+}
 
 #[derive(Clone)]
 enum Entry<T> {
@@ -186,14 +221,35 @@ impl<T> Slab<T> {
     /// The function does not allocate and the returned slab will have no
     /// capacity until `insert` is called or capacity is explicitly reserved.
     ///
+    /// This is `const fn` on Rust 1.39+.
+    ///
     /// # Examples
     ///
     /// ```
     /// # use slab::*;
     /// let slab: Slab<i32> = Slab::new();
     /// ```
-    pub fn new() -> Slab<T> {
-        Slab::with_capacity(0)
+    #[cfg(not(slab_no_const_vec_new))]
+    pub const fn new() -> Self {
+        Self {
+            entries: Vec::new(),
+            next: 0,
+            len: 0,
+        }
+    }
+    /// Construct a new, empty `Slab`.
+    ///
+    /// The function does not allocate and the returned slab will have no
+    /// capacity until `insert` is called or capacity is explicitly reserved.
+    ///
+    /// This is `const fn` on Rust 1.39+.
+    #[cfg(slab_no_const_vec_new)]
+    pub fn new() -> Self {
+        Self {
+            entries: Vec::new(),
+            next: 0,
+            len: 0,
+        }
     }
 
     /// Construct a new, empty `Slab` with the specified capacity.
@@ -259,7 +315,7 @@ impl<T> Slab<T> {
     ///
     /// # Panics
     ///
-    /// Panics if the new capacity overflows `usize`.
+    /// Panics if the new capacity exceeds `isize::MAX` bytes.
     ///
     /// # Examples
     ///
@@ -274,7 +330,7 @@ impl<T> Slab<T> {
         if self.capacity() - self.len >= additional {
             return;
         }
-        let need_add = self.len + additional - self.entries.len();
+        let need_add = additional - (self.entries.len() - self.len);
         self.entries.reserve(need_add);
     }
 
@@ -282,7 +338,7 @@ impl<T> Slab<T> {
     /// more values.
     ///
     /// `reserve_exact` does nothing if the slab already has sufficient capacity
-    /// for `additional` more valus. If more capacity is required, a new segment
+    /// for `additional` more values. If more capacity is required, a new segment
     /// of memory will be allocated and all existing values will be copied into
     /// it.  As such, if the slab is already very large, a call to `reserve` can
     /// end up being expensive.
@@ -293,7 +349,7 @@ impl<T> Slab<T> {
     ///
     /// # Panics
     ///
-    /// Panics if the new capacity overflows `usize`.
+    /// Panics if the new capacity exceeds `isize::MAX` bytes.
     ///
     /// # Examples
     ///
@@ -308,16 +364,19 @@ impl<T> Slab<T> {
         if self.capacity() - self.len >= additional {
             return;
         }
-        let need_add = self.len + additional - self.entries.len();
+        let need_add = additional - (self.entries.len() - self.len);
         self.entries.reserve_exact(need_add);
     }
 
-    /// Shrink the capacity of the slab as much as possible.
+    /// Shrink the capacity of the slab as much as possible without invalidating keys.
     ///
-    /// It will drop down as close as possible to the length but the allocator
-    /// may still inform the vector that there is space for a few more elements.
-    /// Also, since values are not moved, the slab cannot shrink past any stored
-    /// values.
+    /// Because values cannot be moved to a different index, the slab cannot
+    /// shrink past any stored values.
+    /// It will drop down as close as possible to the length but the allocator may
+    /// still inform the underlying vector that there is space for a few more elements.
+    ///
+    /// This function can take O(n) time even when the capacity cannot be reduced
+    /// or the allocation is shrunk in place. Repeated calls run in O(1) though.
     ///
     /// # Examples
     ///
@@ -329,33 +388,175 @@ impl<T> Slab<T> {
     ///     slab.insert(i);
     /// }
     ///
-    /// assert_eq!(slab.capacity(), 10);
     /// slab.shrink_to_fit();
-    /// assert!(slab.capacity() >= 3);
+    /// assert!(slab.capacity() >= 3 && slab.capacity() < 10);
     /// ```
     ///
-    /// In this case, even though two values are removed, the slab cannot shrink
-    /// past the last value.
+    /// The slab cannot shrink past the last present value even if previous
+    /// values are removed:
     ///
     /// ```
     /// # use slab::*;
     /// let mut slab = Slab::with_capacity(10);
     ///
-    /// for i in 0..3 {
+    /// for i in 0..4 {
     ///     slab.insert(i);
     /// }
     ///
     /// slab.remove(0);
-    /// slab.remove(1);
+    /// slab.remove(3);
     ///
-    /// assert_eq!(slab.capacity(), 10);
     /// slab.shrink_to_fit();
-    /// assert!(slab.capacity() >= 3);
+    /// assert!(slab.capacity() >= 3 && slab.capacity() < 10);
     /// ```
     pub fn shrink_to_fit(&mut self) {
+        // Remove all vacant entries after the last occupied one, so that
+        // the capacity can be reduced to what is actually needed.
+        // If the slab is empty the vector can simply be cleared, but that
+        // optimization would not affect time complexity when T: Drop.
+        let len_before = self.entries.len();
+        while let Some(&Entry::Vacant(_)) = self.entries.last() {
+            self.entries.pop();
+        }
+
+        // Removing entries breaks the list of vacant entries,
+        // so it must be repaired
+        if self.entries.len() != len_before {
+            // Some vacant entries were removed, so the list now likely¹
+            // either contains references to the removed entries, or has an
+            // invalid end marker. Fix this by recreating the list.
+            self.recreate_vacant_list();
+            // ¹: If the removed entries formed the tail of the list, with the
+            // most recently popped entry being the head of them, (so that its
+            // index is now the end marker) the list is still valid.
+            // Checking for that unlikely scenario of this infrequently called
+            // is not worth the code complexity.
+        }
+
         self.entries.shrink_to_fit();
     }
 
+    /// Iterate through all entries to recreate and repair the vacant list.
+    /// self.len must be correct and is not modified.
+    fn recreate_vacant_list(&mut self) {
+        self.next = self.entries.len();
+        // We can stop once we've found all vacant entries
+        let mut remaining_vacant = self.entries.len() - self.len;
+        if remaining_vacant == 0 {
+            return;
+        }
+
+        // Iterate in reverse order so that lower keys are at the start of
+        // the vacant list. This way future shrinks are more likely to be
+        // able to remove vacant entries.
+        for (i, entry) in self.entries.iter_mut().enumerate().rev() {
+            if let Entry::Vacant(ref mut next) = *entry {
+                *next = self.next;
+                self.next = i;
+                remaining_vacant -= 1;
+                if remaining_vacant == 0 {
+                    break;
+                }
+            }
+        }
+    }
+
+    /// Reduce the capacity as much as possible, changing the key for elements when necessary.
+    ///
+    /// To allow updating references to the elements which must be moved to a new key,
+    /// this function takes a closure which is called before moving each element.
+    /// The second and third parameters to the closure are the current key and
+    /// new key respectively.
+    /// In case changing the key for one element turns out not to be possible,
+    /// the move can be cancelled by returning `false` from the closure.
+    /// In that case no further attempts at relocating elements is made.
+    /// If the closure unwinds, the slab will be left in a consistent state,
+    /// but the value that the closure panicked on might be removed.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    ///
+    /// let mut slab = Slab::with_capacity(10);
+    /// let a = slab.insert('a');
+    /// slab.insert('b');
+    /// slab.insert('c');
+    /// slab.remove(a);
+    /// slab.compact(|&mut value, from, to| {
+    ///     assert_eq!((value, from, to), ('c', 2, 0));
+    ///     true
+    /// });
+    /// assert!(slab.capacity() >= 2 && slab.capacity() < 10);
+    /// ```
+    ///
+    /// The value is not moved when the closure returns `Err`:
+    ///
+    /// ```
+    /// # use slab::*;
+    ///
+    /// let mut slab = Slab::with_capacity(100);
+    /// let a = slab.insert('a');
+    /// let b = slab.insert('b');
+    /// slab.remove(a);
+    /// slab.compact(|&mut value, from, to| false);
+    /// assert_eq!(slab.iter().next(), Some((b, &'b')));
+    /// ```
+    pub fn compact<F>(&mut self, mut rekey: F)
+    where
+        F: FnMut(&mut T, usize, usize) -> bool,
+    {
+        // If the closure unwinds, we need to restore a valid list of vacant entries
+        struct CleanupGuard<'a, T> {
+            slab: &'a mut Slab<T>,
+            decrement: bool,
+        }
+        impl<T> Drop for CleanupGuard<'_, T> {
+            fn drop(&mut self) {
+                if self.decrement {
+                    // Value was popped and not pushed back on
+                    self.slab.len -= 1;
+                }
+                self.slab.recreate_vacant_list();
+            }
+        }
+        let mut guard = CleanupGuard {
+            slab: self,
+            decrement: true,
+        };
+
+        let mut occupied_until = 0;
+        // While there are vacant entries
+        while guard.slab.entries.len() > guard.slab.len {
+            // Find a value that needs to be moved,
+            // by popping entries until we find an occupied one.
+            // (entries cannot be empty because 0 is not greater than anything)
+            if let Some(Entry::Occupied(mut value)) = guard.slab.entries.pop() {
+                // Found one, now find a vacant entry to move it to
+                while let Some(&Entry::Occupied(_)) = guard.slab.entries.get(occupied_until) {
+                    occupied_until += 1;
+                }
+                // Let the caller try to update references to the key
+                if !rekey(&mut value, guard.slab.entries.len(), occupied_until) {
+                    // Changing the key failed, so push the entry back on at its old index.
+                    guard.slab.entries.push(Entry::Occupied(value));
+                    guard.decrement = false;
+                    guard.slab.entries.shrink_to_fit();
+                    return;
+                    // Guard drop handles cleanup
+                }
+                // Put the value in its new spot
+                guard.slab.entries[occupied_until] = Entry::Occupied(value);
+                // ... and mark it as occupied (this is optional)
+                occupied_until += 1;
+            }
+        }
+        guard.slab.next = guard.slab.len;
+        guard.slab.entries.shrink_to_fit();
+        // Normal cleanup is not necessary
+        mem::forget(guard);
+    }
+
     /// Clear the slab of all values.
     ///
     /// # Examples
@@ -435,10 +636,10 @@ impl<T> Slab<T> {
     /// assert_eq!(iterator.next(), Some((2, &2)));
     /// assert_eq!(iterator.next(), None);
     /// ```
-    pub fn iter(&self) -> Iter<T> {
+    pub fn iter(&self) -> Iter<'_, T> {
         Iter {
-            entries: self.entries.iter(),
-            curr: 0,
+            entries: self.entries.iter().enumerate(),
+            len: self.len,
         }
     }
 
@@ -467,10 +668,10 @@ impl<T> Slab<T> {
     /// assert_eq!(slab[key1], 2);
     /// assert_eq!(slab[key2], 1);
     /// ```
-    pub fn iter_mut(&mut self) -> IterMut<T> {
+    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
         IterMut {
-            entries: self.entries.iter_mut(),
-            curr: 0,
+            entries: self.entries.iter_mut().enumerate(),
+            len: self.len,
         }
     }
 
@@ -491,7 +692,7 @@ impl<T> Slab<T> {
     /// ```
     pub fn get(&self, key: usize) -> Option<&T> {
         match self.entries.get(key) {
-            Some(&Entry::Occupied(ref val)) => Some(val),
+            Some(Entry::Occupied(val)) => Some(val),
             _ => None,
         }
     }
@@ -520,11 +721,68 @@ impl<T> Slab<T> {
         }
     }
 
+    /// Return two mutable references to the values associated with the two
+    /// given keys simultaneously.
+    ///
+    /// If any one of the given keys is not associated with a value, then `None`
+    /// is returned.
+    ///
+    /// This function can be used to get two mutable references out of one slab,
+    /// so that you can manipulate both of them at the same time, eg. swap them.
+    ///
+    /// # Panics
+    ///
+    /// This function will panic if `key1` and `key2` are the same.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// use std::mem;
+    ///
+    /// let mut slab = Slab::new();
+    /// let key1 = slab.insert(1);
+    /// let key2 = slab.insert(2);
+    /// let (value1, value2) = slab.get2_mut(key1, key2).unwrap();
+    /// mem::swap(value1, value2);
+    /// assert_eq!(slab[key1], 2);
+    /// assert_eq!(slab[key2], 1);
+    /// ```
+    pub fn get2_mut(&mut self, key1: usize, key2: usize) -> Option<(&mut T, &mut T)> {
+        assert!(key1 != key2);
+
+        let (entry1, entry2);
+
+        if key1 > key2 {
+            let (slice1, slice2) = self.entries.split_at_mut(key1);
+            entry1 = slice2.get_mut(0);
+            entry2 = slice1.get_mut(key2);
+        } else {
+            let (slice1, slice2) = self.entries.split_at_mut(key2);
+            entry1 = slice1.get_mut(key1);
+            entry2 = slice2.get_mut(0);
+        }
+
+        match (entry1, entry2) {
+            (
+                Some(&mut Entry::Occupied(ref mut val1)),
+                Some(&mut Entry::Occupied(ref mut val2)),
+            ) => Some((val1, val2)),
+            _ => None,
+        }
+    }
+
     /// Return a reference to the value associated with the given key without
     /// performing bounds checking.
     ///
+    /// For a safe alternative see [`get`](Slab::get).
+    ///
     /// This function should be used with care.
     ///
+    /// # Safety
+    ///
+    /// The key must be within bounds.
+    ///
     /// # Examples
     ///
     /// ```
@@ -546,8 +804,14 @@ impl<T> Slab<T> {
     /// Return a mutable reference to the value associated with the given key
     /// without performing bounds checking.
     ///
+    /// For a safe alternative see [`get_mut`](Slab::get_mut).
+    ///
     /// This function should be used with care.
     ///
+    /// # Safety
+    ///
+    /// The key must be within bounds.
+    ///
     /// # Examples
     ///
     /// ```
@@ -569,6 +833,98 @@ impl<T> Slab<T> {
         }
     }
 
+    /// Return two mutable references to the values associated with the two
+    /// given keys simultaneously without performing bounds checking and safety
+    /// condition checking.
+    ///
+    /// For a safe alternative see [`get2_mut`](Slab::get2_mut).
+    ///
+    /// This function should be used with care.
+    ///
+    /// # Safety
+    ///
+    /// - Both keys must be within bounds.
+    /// - The condition `key1 != key2` must hold.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// use std::mem;
+    ///
+    /// let mut slab = Slab::new();
+    /// let key1 = slab.insert(1);
+    /// let key2 = slab.insert(2);
+    /// let (value1, value2) = unsafe { slab.get2_unchecked_mut(key1, key2) };
+    /// mem::swap(value1, value2);
+    /// assert_eq!(slab[key1], 2);
+    /// assert_eq!(slab[key2], 1);
+    /// ```
+    pub unsafe fn get2_unchecked_mut(&mut self, key1: usize, key2: usize) -> (&mut T, &mut T) {
+        debug_assert_ne!(key1, key2);
+        let ptr = self.entries.as_mut_ptr();
+        let ptr1 = ptr.add(key1);
+        let ptr2 = ptr.add(key2);
+        match (&mut *ptr1, &mut *ptr2) {
+            (&mut Entry::Occupied(ref mut val1), &mut Entry::Occupied(ref mut val2)) => {
+                (val1, val2)
+            }
+            _ => unreachable!(),
+        }
+    }
+
+    /// Get the key for an element in the slab.
+    ///
+    /// The reference must point to an element owned by the slab.
+    /// Otherwise this function will panic.
+    /// This is a constant-time operation because the key can be calculated
+    /// from the reference with pointer arithmetic.
+    ///
+    /// # Panics
+    ///
+    /// This function will panic if the reference does not point to an element
+    /// of the slab.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    ///
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert(String::from("foo"));
+    /// let value = &slab[key];
+    /// assert_eq!(slab.key_of(value), key);
+    /// ```
+    ///
+    /// Values are not compared, so passing a reference to a different location
+    /// will result in a panic:
+    ///
+    /// ```should_panic
+    /// # use slab::*;
+    ///
+    /// let mut slab = Slab::new();
+    /// let key = slab.insert(0);
+    /// let bad = &0;
+    /// slab.key_of(bad); // this will panic
+    /// unreachable!();
+    /// ```
+    #[cfg_attr(not(slab_no_track_caller), track_caller)]
+    pub fn key_of(&self, present_element: &T) -> usize {
+        let element_ptr = present_element as *const T as usize;
+        let base_ptr = self.entries.as_ptr() as usize;
+        // Use wrapping subtraction in case the reference is bad
+        let byte_offset = element_ptr.wrapping_sub(base_ptr);
+        // The division rounds away any offset of T inside Entry
+        // The size of Entry<T> is never zero even if T is due to Vacant(usize)
+        let key = byte_offset / mem::size_of::<Entry<T>>();
+        // Prevent returning unspecified (but out of bounds) values
+        if key >= self.entries.len() {
+            panic!("The reference points to a value outside this slab");
+        }
+        // The reference cannot point to a vacant entry, because then it would not be valid
+        key
+    }
+
     /// Insert a value in the slab, returning key assigned to the value.
     ///
     /// The returned key can later be used to retrieve or remove the value using indexed
@@ -577,7 +933,7 @@ impl<T> Slab<T> {
     ///
     /// # Panics
     ///
-    /// Panics if the number of elements in the vector overflows a `usize`.
+    /// Panics if the new storage in the vector exceeds `isize::MAX` bytes.
     ///
     /// # Examples
     ///
@@ -595,6 +951,30 @@ impl<T> Slab<T> {
         key
     }
 
+    /// Returns the key of the next vacant entry.
+    ///
+    /// This function returns the key of the vacant entry which  will be used
+    /// for the next insertion. This is equivalent to
+    /// `slab.vacant_entry().key()`, but it doesn't require mutable access.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    /// assert_eq!(slab.vacant_key(), 0);
+    ///
+    /// slab.insert(0);
+    /// assert_eq!(slab.vacant_key(), 1);
+    ///
+    /// slab.insert(1);
+    /// slab.remove(0);
+    /// assert_eq!(slab.vacant_key(), 0);
+    /// ```
+    pub fn vacant_key(&self) -> usize {
+        self.next
+    }
+
     /// Return a handle to a vacant entry allowing for further manipulation.
     ///
     /// This function is useful when creating values that must contain their
@@ -618,7 +998,7 @@ impl<T> Slab<T> {
     /// assert_eq!(hello, slab[hello].0);
     /// assert_eq!("hello", slab[hello].1);
     /// ```
-    pub fn vacant_entry(&mut self) -> VacantEntry<T> {
+    pub fn vacant_entry(&mut self) -> VacantEntry<'_, T> {
         VacantEntry {
             key: self.next,
             slab: self,
@@ -632,15 +1012,49 @@ impl<T> Slab<T> {
             self.entries.push(Entry::Occupied(val));
             self.next = key + 1;
         } else {
-            let prev = mem::replace(&mut self.entries[key], Entry::Occupied(val));
+            self.next = match self.entries.get(key) {
+                Some(&Entry::Vacant(next)) => next,
+                _ => unreachable!(),
+            };
+            self.entries[key] = Entry::Occupied(val);
+        }
+    }
+
+    /// Tries to remove the value associated with the given key,
+    /// returning the value if the key existed.
+    ///
+    /// The key is then released and may be associated with future stored
+    /// values.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use slab::*;
+    /// let mut slab = Slab::new();
+    ///
+    /// let hello = slab.insert("hello");
+    ///
+    /// assert_eq!(slab.try_remove(hello), Some("hello"));
+    /// assert!(!slab.contains(hello));
+    /// ```
+    pub fn try_remove(&mut self, key: usize) -> Option<T> {
+        if let Some(entry) = self.entries.get_mut(key) {
+            // Swap the entry at the provided value
+            let prev = mem::replace(entry, Entry::Vacant(self.next));
 
             match prev {
-                Entry::Vacant(next) => {
-                    self.next = next;
+                Entry::Occupied(val) => {
+                    self.len -= 1;
+                    self.next = key;
+                    return val.into();
+                }
+                _ => {
+                    // Woops, the entry is actually vacant, restore the state
+                    *entry = prev;
                 }
-                _ => unreachable!(),
             }
         }
+        None
     }
 
     /// Remove and return the value associated with the given key.
@@ -663,22 +1077,9 @@ impl<T> Slab<T> {
     /// assert_eq!(slab.remove(hello), "hello");
     /// assert!(!slab.contains(hello));
     /// ```
+    #[cfg_attr(not(slab_no_track_caller), track_caller)]
     pub fn remove(&mut self, key: usize) -> T {
-        // Swap the entry at the provided value
-        let prev = mem::replace(&mut self.entries[key], Entry::Vacant(self.next));
-
-        match prev {
-            Entry::Occupied(val) => {
-                self.len -= 1;
-                self.next = key;
-                val
-            }
-            _ => {
-                // Woops, the entry is actually vacant, restore the state
-                self.entries[key] = prev;
-                panic!("invalid key");
-            }
-        }
+        self.try_remove(key).expect("invalid key")
     }
 
     /// Return `true` if a value is associated with the given key.
@@ -697,13 +1098,10 @@ impl<T> Slab<T> {
     /// assert!(!slab.contains(hello));
     /// ```
     pub fn contains(&self, key: usize) -> bool {
-        self.entries
-            .get(key)
-            .map(|e| match *e {
-                Entry::Occupied(_) => true,
-                _ => false,
-            })
-            .unwrap_or(false)
+        match self.entries.get(key) {
+            Some(&Entry::Occupied(_)) => true,
+            _ => false,
+        }
     }
 
     /// Retain only the elements specified by the predicate.
@@ -773,33 +1171,51 @@ impl<T> Slab<T> {
     ///
     /// assert!(slab.is_empty());
     /// ```
-    pub fn drain(&mut self) -> Drain<T> {
+    pub fn drain(&mut self) -> Drain<'_, T> {
+        let old_len = self.len;
         self.len = 0;
         self.next = 0;
-        Drain(self.entries.drain(..))
+        Drain {
+            inner: self.entries.drain(..),
+            len: old_len,
+        }
     }
 }
 
 impl<T> ops::Index<usize> for Slab<T> {
     type Output = T;
 
+    #[cfg_attr(not(slab_no_track_caller), track_caller)]
     fn index(&self, key: usize) -> &T {
-        match self.entries[key] {
-            Entry::Occupied(ref v) => v,
+        match self.entries.get(key) {
+            Some(Entry::Occupied(v)) => v,
             _ => panic!("invalid key"),
         }
     }
 }
 
 impl<T> ops::IndexMut<usize> for Slab<T> {
+    #[cfg_attr(not(slab_no_track_caller), track_caller)]
     fn index_mut(&mut self, key: usize) -> &mut T {
-        match self.entries[key] {
-            Entry::Occupied(ref mut v) => v,
+        match self.entries.get_mut(key) {
+            Some(&mut Entry::Occupied(ref mut v)) => v,
             _ => panic!("invalid key"),
         }
     }
 }
 
+impl<T> IntoIterator for Slab<T> {
+    type Item = (usize, T);
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> IntoIter<T> {
+        IntoIter {
+            entries: self.entries.into_iter().enumerate(),
+            len: self.len,
+        }
+    }
+}
+
 impl<'a, T> IntoIterator for &'a Slab<T> {
     type Item = (usize, &'a T);
     type IntoIter = Iter<'a, T>;
@@ -818,46 +1234,102 @@ impl<'a, T> IntoIterator for &'a mut Slab<T> {
     }
 }
 
+/// Create a slab from an iterator of key-value pairs.
+///
+/// If the iterator produces duplicate keys, the previous value is replaced with the later one.
+/// The keys does not need to be sorted beforehand, and this function always
+/// takes O(n) time.
+/// Note that the returned slab will use space proportional to the largest key,
+/// so don't use `Slab` with untrusted keys.
+///
+/// # Examples
+///
+/// ```
+/// # use slab::*;
+///
+/// let vec = vec![(2,'a'), (6,'b'), (7,'c')];
+/// let slab = vec.into_iter().collect::<Slab<char>>();
+/// assert_eq!(slab.len(), 3);
+/// assert!(slab.capacity() >= 8);
+/// assert_eq!(slab[2], 'a');
+/// ```
+///
+/// With duplicate and unsorted keys:
+///
+/// ```
+/// # use slab::*;
+///
+/// let vec = vec![(20,'a'), (10,'b'), (11,'c'), (10,'d')];
+/// let slab = vec.into_iter().collect::<Slab<char>>();
+/// assert_eq!(slab.len(), 3);
+/// assert_eq!(slab[10], 'd');
+/// ```
+impl<T> FromIterator<(usize, T)> for Slab<T> {
+    fn from_iter<I>(iterable: I) -> Self
+    where
+        I: IntoIterator<Item = (usize, T)>,
+    {
+        let iterator = iterable.into_iter();
+        let mut builder = builder::Builder::with_capacity(iterator.size_hint().0);
+
+        for (key, value) in iterator {
+            builder.pair(key, value)
+        }
+        builder.build()
+    }
+}
+
 impl<T> fmt::Debug for Slab<T>
 where
     T: fmt::Debug,
 {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(
-            fmt,
-            "Slab {{ len: {}, cap: {} }}",
-            self.len,
-            self.capacity()
-        )
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if fmt.alternate() {
+            fmt.debug_map().entries(self.iter()).finish()
+        } else {
+            fmt.debug_struct("Slab")
+                .field("len", &self.len)
+                .field("cap", &self.capacity())
+                .finish()
+        }
     }
 }
 
-impl<'a, T: 'a> fmt::Debug for Iter<'a, T>
+impl<T> fmt::Debug for IntoIter<T>
 where
     T: fmt::Debug,
 {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt.debug_struct("IntoIter")
+            .field("remaining", &self.len)
+            .finish()
+    }
+}
+
+impl<T> fmt::Debug for Iter<'_, T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
         fmt.debug_struct("Iter")
-            .field("curr", &self.curr)
-            .field("remaining", &self.entries.len())
+            .field("remaining", &self.len)
             .finish()
     }
 }
 
-impl<'a, T: 'a> fmt::Debug for IterMut<'a, T>
+impl<T> fmt::Debug for IterMut<'_, T>
 where
     T: fmt::Debug,
 {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
         fmt.debug_struct("IterMut")
-            .field("curr", &self.curr)
-            .field("remaining", &self.entries.len())
+            .field("remaining", &self.len)
             .finish()
     }
 }
 
-impl<'a, T: 'a> fmt::Debug for Drain<'a, T> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+impl<T> fmt::Debug for Drain<'_, T> {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
         fmt.debug_struct("Drain").finish()
     }
 }
@@ -890,8 +1362,8 @@ impl<'a, T> VacantEntry<'a, T> {
     pub fn insert(self, val: T) -> &'a mut T {
         self.slab.insert_at(self.key, val);
 
-        match self.slab.entries[self.key] {
-            Entry::Occupied(ref mut v) => v,
+        match self.slab.entries.get_mut(self.key) {
+            Some(&mut Entry::Occupied(ref mut v)) => v,
             _ => unreachable!(),
         }
     }
@@ -922,56 +1394,178 @@ impl<'a, T> VacantEntry<'a, T> {
     }
 }
 
+// ===== IntoIter =====
+
+impl<T> Iterator for IntoIter<T> {
+    type Item = (usize, T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        for (key, entry) in &mut self.entries {
+            if let Entry::Occupied(v) = entry {
+                self.len -= 1;
+                return Some((key, v));
+            }
+        }
+
+        debug_assert_eq!(self.len, 0);
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len, Some(self.len))
+    }
+}
+
+impl<T> DoubleEndedIterator for IntoIter<T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        while let Some((key, entry)) = self.entries.next_back() {
+            if let Entry::Occupied(v) = entry {
+                self.len -= 1;
+                return Some((key, v));
+            }
+        }
+
+        debug_assert_eq!(self.len, 0);
+        None
+    }
+}
+
+impl<T> ExactSizeIterator for IntoIter<T> {
+    fn len(&self) -> usize {
+        self.len
+    }
+}
+
+impl<T> FusedIterator for IntoIter<T> {}
+
 // ===== Iter =====
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = (usize, &'a T);
 
-    fn next(&mut self) -> Option<(usize, &'a T)> {
-        while let Some(entry) = self.entries.next() {
-            let curr = self.curr;
-            self.curr += 1;
+    fn next(&mut self) -> Option<Self::Item> {
+        for (key, entry) in &mut self.entries {
+            if let Entry::Occupied(ref v) = *entry {
+                self.len -= 1;
+                return Some((key, v));
+            }
+        }
 
+        debug_assert_eq!(self.len, 0);
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len, Some(self.len))
+    }
+}
+
+impl<T> DoubleEndedIterator for Iter<'_, T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        while let Some((key, entry)) = self.entries.next_back() {
             if let Entry::Occupied(ref v) = *entry {
-                return Some((curr, v));
+                self.len -= 1;
+                return Some((key, v));
             }
         }
 
+        debug_assert_eq!(self.len, 0);
         None
     }
 }
 
+impl<T> ExactSizeIterator for Iter<'_, T> {
+    fn len(&self) -> usize {
+        self.len
+    }
+}
+
+impl<T> FusedIterator for Iter<'_, T> {}
+
 // ===== IterMut =====
 
 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = (usize, &'a mut T);
 
-    fn next(&mut self) -> Option<(usize, &'a mut T)> {
-        while let Some(entry) = self.entries.next() {
-            let curr = self.curr;
-            self.curr += 1;
+    fn next(&mut self) -> Option<Self::Item> {
+        for (key, entry) in &mut self.entries {
+            if let Entry::Occupied(ref mut v) = *entry {
+                self.len -= 1;
+                return Some((key, v));
+            }
+        }
+
+        debug_assert_eq!(self.len, 0);
+        None
+    }
 
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len, Some(self.len))
+    }
+}
+
+impl<T> DoubleEndedIterator for IterMut<'_, T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        while let Some((key, entry)) = self.entries.next_back() {
             if let Entry::Occupied(ref mut v) = *entry {
-                return Some((curr, v));
+                self.len -= 1;
+                return Some((key, v));
             }
         }
 
+        debug_assert_eq!(self.len, 0);
         None
     }
 }
 
+impl<T> ExactSizeIterator for IterMut<'_, T> {
+    fn len(&self) -> usize {
+        self.len
+    }
+}
+
+impl<T> FusedIterator for IterMut<'_, T> {}
+
 // ===== Drain =====
 
-impl<'a, T> Iterator for Drain<'a, T> {
+impl<T> Iterator for Drain<'_, T> {
     type Item = T;
 
-    fn next(&mut self) -> Option<T> {
-        while let Some(entry) = self.0.next() {
+    fn next(&mut self) -> Option<Self::Item> {
+        for entry in &mut self.inner {
             if let Entry::Occupied(v) = entry {
+                self.len -= 1;
+                return Some(v);
+            }
+        }
+
+        debug_assert_eq!(self.len, 0);
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len, Some(self.len))
+    }
+}
+
+impl<T> DoubleEndedIterator for Drain<'_, T> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        while let Some(entry) = self.inner.next_back() {
+            if let Entry::Occupied(v) = entry {
+                self.len -= 1;
                 return Some(v);
             }
         }
 
+        debug_assert_eq!(self.len, 0);
         None
     }
 }
+
+impl<T> ExactSizeIterator for Drain<'_, T> {
+    fn len(&self) -> usize {
+        self.len
+    }
+}
+
+impl<T> FusedIterator for Drain<'_, T> {}
diff --git a/vendor/slab/src/serde.rs b/vendor/slab/src/serde.rs
new file mode 100644
index 000000000..894d59c11
--- /dev/null
+++ b/vendor/slab/src/serde.rs
@@ -0,0 +1,62 @@
+use core::fmt;
+use core::marker::PhantomData;
+
+use serde::de::{Deserialize, Deserializer, MapAccess, Visitor};
+use serde::ser::{Serialize, SerializeMap, Serializer};
+
+use super::{builder::Builder, Slab};
+
+impl<T> Serialize for Slab<T>
+where
+    T: Serialize,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        let mut map_serializer = serializer.serialize_map(Some(self.len()))?;
+        for (key, value) in self {
+            map_serializer.serialize_key(&key)?;
+            map_serializer.serialize_value(value)?;
+        }
+        map_serializer.end()
+    }
+}
+
+struct SlabVisitor<T>(PhantomData<T>);
+
+impl<'de, T> Visitor<'de> for SlabVisitor<T>
+where
+    T: Deserialize<'de>,
+{
+    type Value = Slab<T>;
+
+    fn expecting(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(fmt, "a map")
+    }
+
+    fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
+    where
+        A: MapAccess<'de>,
+    {
+        let mut builder = Builder::with_capacity(map.size_hint().unwrap_or(0));
+
+        while let Some((key, value)) = map.next_entry()? {
+            builder.pair(key, value)
+        }
+
+        Ok(builder.build())
+    }
+}
+
+impl<'de, T> Deserialize<'de> for Slab<T>
+where
+    T: Deserialize<'de>,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        deserializer.deserialize_map(SlabVisitor(PhantomData))
+    }
+}
diff --git a/vendor/slab/tests/serde.rs b/vendor/slab/tests/serde.rs
new file mode 100644
index 000000000..1d4a204e4
--- /dev/null
+++ b/vendor/slab/tests/serde.rs
@@ -0,0 +1,49 @@
+#![cfg(feature = "serde")]
+#![warn(rust_2018_idioms)]
+
+use serde::{Deserialize, Serialize};
+use serde_test::{assert_tokens, Token};
+use slab::Slab;
+
+#[derive(Debug, Serialize, Deserialize)]
+#[serde(transparent)]
+struct SlabPartialEq<T>(Slab<T>);
+
+impl<T: PartialEq> PartialEq for SlabPartialEq<T> {
+    fn eq(&self, other: &Self) -> bool {
+        self.0.len() == other.0.len()
+            && self
+                .0
+                .iter()
+                .zip(other.0.iter())
+                .all(|(this, other)| this.0 == other.0 && this.1 == other.1)
+    }
+}
+
+#[test]
+fn test_serde_empty() {
+    let slab = Slab::<usize>::new();
+    assert_tokens(
+        &SlabPartialEq(slab),
+        &[Token::Map { len: Some(0) }, Token::MapEnd],
+    );
+}
+
+#[test]
+fn test_serde() {
+    let vec = vec![(1, 2), (3, 4), (5, 6)];
+    let slab: Slab<_> = vec.iter().cloned().collect();
+    assert_tokens(
+        &SlabPartialEq(slab),
+        &[
+            Token::Map { len: Some(3) },
+            Token::U64(1),
+            Token::I32(2),
+            Token::U64(3),
+            Token::I32(4),
+            Token::U64(5),
+            Token::I32(6),
+            Token::MapEnd,
+        ],
+    );
+}
diff --git a/vendor/slab/tests/slab.rs b/vendor/slab/tests/slab.rs
index 5203c95a4..900eed398 100644
--- a/vendor/slab/tests/slab.rs
+++ b/vendor/slab/tests/slab.rs
@@ -1,7 +1,9 @@
-extern crate slab;
+#![warn(rust_2018_idioms)]
 
 use slab::*;
 
+use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
+
 #[test]
 fn insert_get_remove_one() {
     let mut slab = Slab::new();
@@ -82,14 +84,21 @@ fn get_vacant_entry_without_using() {
 }
 
 #[test]
-#[should_panic]
+#[should_panic(expected = "invalid key")]
 fn invalid_get_panics() {
     let slab = Slab::<usize>::with_capacity(1);
-    slab[0];
+    let _ = &slab[0];
+}
+
+#[test]
+#[should_panic(expected = "invalid key")]
+fn invalid_get_mut_panics() {
+    let mut slab = Slab::<usize>::new();
+    let _ = &mut slab[0];
 }
 
 #[test]
-#[should_panic]
+#[should_panic(expected = "invalid key")]
 fn double_remove_panics() {
     let mut slab = Slab::<usize>::with_capacity(1);
     let key = slab.insert(123);
@@ -98,7 +107,7 @@ fn double_remove_panics() {
 }
 
 #[test]
-#[should_panic]
+#[should_panic(expected = "invalid key")]
 fn invalid_remove_panics() {
     let mut slab = Slab::<usize>::with_capacity(1);
     slab.remove(0);
@@ -117,6 +126,34 @@ fn slab_get_mut() {
 }
 
 #[test]
+fn key_of_tagged() {
+    let mut slab = Slab::new();
+    slab.insert(0);
+    assert_eq!(slab.key_of(&slab[0]), 0);
+}
+
+#[test]
+fn key_of_layout_optimizable() {
+    // Entry<&str> doesn't need a discriminant tag because it can use the
+    // nonzero-ness of ptr and store Vacant's next at the same offset as len
+    let mut slab = Slab::new();
+    slab.insert("foo");
+    slab.insert("bar");
+    let third = slab.insert("baz");
+    slab.insert("quux");
+    assert_eq!(slab.key_of(&slab[third]), third);
+}
+
+#[test]
+fn key_of_zst() {
+    let mut slab = Slab::new();
+    slab.insert(());
+    let second = slab.insert(());
+    slab.insert(());
+    assert_eq!(slab.key_of(&slab[second]), second);
+}
+
+#[test]
 fn reserve_does_not_allocate_if_available() {
     let mut slab = Slab::with_capacity(10);
     let mut keys = vec![];
@@ -150,11 +187,35 @@ fn reserve_exact_does_not_allocate_if_available() {
 
     assert!(slab.capacity() - slab.len() == 8);
 
-    slab.reserve(8);
+    slab.reserve_exact(8);
     assert_eq!(10, slab.capacity());
 }
 
 #[test]
+#[should_panic(expected = "capacity overflow")]
+fn reserve_does_panic_with_capacity_overflow() {
+    let mut slab = Slab::with_capacity(10);
+    slab.insert(true);
+    slab.reserve(std::isize::MAX as usize);
+}
+
+#[test]
+#[should_panic(expected = "capacity overflow")]
+fn reserve_does_panic_with_capacity_overflow_bytes() {
+    let mut slab = Slab::with_capacity(10);
+    slab.insert(1u16);
+    slab.reserve((std::isize::MAX as usize) / 2);
+}
+
+#[test]
+#[should_panic(expected = "capacity overflow")]
+fn reserve_exact_does_panic_with_capacity_overflow() {
+    let mut slab = Slab::with_capacity(10);
+    slab.insert(true);
+    slab.reserve_exact(std::isize::MAX as usize);
+}
+
+#[test]
 fn retain() {
     let mut slab = Slab::with_capacity(2);
 
@@ -185,6 +246,43 @@ fn retain() {
 }
 
 #[test]
+fn into_iter() {
+    let mut slab = Slab::new();
+
+    for i in 0..8 {
+        slab.insert(i);
+    }
+    slab.remove(0);
+    slab.remove(4);
+    slab.remove(5);
+    slab.remove(7);
+
+    let vals: Vec<_> = slab
+        .into_iter()
+        .inspect(|&(key, val)| assert_eq!(key, val))
+        .map(|(_, val)| val)
+        .collect();
+    assert_eq!(vals, vec![1, 2, 3, 6]);
+}
+
+#[test]
+fn into_iter_rev() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+
+    let mut iter = slab.into_iter();
+    assert_eq!(iter.next_back(), Some((3, 3)));
+    assert_eq!(iter.next_back(), Some((2, 2)));
+    assert_eq!(iter.next(), Some((0, 0)));
+    assert_eq!(iter.next_back(), Some((1, 1)));
+    assert_eq!(iter.next_back(), None);
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
 fn iter() {
     let mut slab = Slab::new();
 
@@ -209,6 +307,19 @@ fn iter() {
 }
 
 #[test]
+fn iter_rev() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+    slab.remove(0);
+
+    let vals = slab.iter().rev().collect::<Vec<_>>();
+    assert_eq!(vals, vec![(3, &3), (2, &2), (1, &1)]);
+}
+
+#[test]
 fn iter_mut() {
     let mut slab = Slab::new();
 
@@ -218,7 +329,7 @@ fn iter_mut() {
 
     for (i, (key, e)) in slab.iter_mut().enumerate() {
         assert_eq!(i, key);
-        *e = *e + 1;
+        *e += 1;
     }
 
     let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
@@ -227,7 +338,7 @@ fn iter_mut() {
     slab.remove(2);
 
     for (_, e) in slab.iter_mut() {
-        *e = *e + 1;
+        *e += 1;
     }
 
     let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
@@ -235,6 +346,102 @@ fn iter_mut() {
 }
 
 #[test]
+fn iter_mut_rev() {
+    let mut slab = Slab::new();
+
+    for i in 0..4 {
+        slab.insert(i);
+    }
+    slab.remove(2);
+
+    {
+        let mut iter = slab.iter_mut();
+        assert_eq!(iter.next(), Some((0, &mut 0)));
+        let mut prev_key = !0;
+        for (key, e) in iter.rev() {
+            *e += 10;
+            assert!(prev_key > key);
+            prev_key = key;
+        }
+    }
+
+    assert_eq!(slab[0], 0);
+    assert_eq!(slab[1], 11);
+    assert_eq!(slab[3], 13);
+    assert!(!slab.contains(2));
+}
+
+#[test]
+fn from_iterator_sorted() {
+    let mut slab = (0..5).map(|i| (i, i)).collect::<Slab<_>>();
+    assert_eq!(slab.len(), 5);
+    assert_eq!(slab[0], 0);
+    assert_eq!(slab[2], 2);
+    assert_eq!(slab[4], 4);
+    assert_eq!(slab.vacant_entry().key(), 5);
+}
+
+#[test]
+fn from_iterator_new_in_order() {
+    // all new keys come in increasing order, but existing keys are overwritten
+    let mut slab = [(0, 'a'), (1, 'a'), (1, 'b'), (0, 'b'), (9, 'a'), (0, 'c')]
+        .iter()
+        .cloned()
+        .collect::<Slab<_>>();
+    assert_eq!(slab.len(), 3);
+    assert_eq!(slab[0], 'c');
+    assert_eq!(slab[1], 'b');
+    assert_eq!(slab[9], 'a');
+    assert_eq!(slab.get(5), None);
+    assert_eq!(slab.vacant_entry().key(), 8);
+}
+
+#[test]
+fn from_iterator_unordered() {
+    let mut slab = vec![(1, "one"), (50, "fifty"), (3, "three"), (20, "twenty")]
+        .into_iter()
+        .collect::<Slab<_>>();
+    assert_eq!(slab.len(), 4);
+    assert_eq!(slab.vacant_entry().key(), 0);
+    let mut iter = slab.iter();
+    assert_eq!(iter.next(), Some((1, &"one")));
+    assert_eq!(iter.next(), Some((3, &"three")));
+    assert_eq!(iter.next(), Some((20, &"twenty")));
+    assert_eq!(iter.next(), Some((50, &"fifty")));
+    assert_eq!(iter.next(), None);
+}
+
+// https://github.com/tokio-rs/slab/issues/100
+#[test]
+fn from_iterator_issue_100() {
+    let mut slab: slab::Slab<()> = vec![(1, ())].into_iter().collect();
+    assert_eq!(slab.len(), 1);
+    assert_eq!(slab.insert(()), 0);
+    assert_eq!(slab.insert(()), 2);
+    assert_eq!(slab.insert(()), 3);
+
+    let mut slab: slab::Slab<()> = vec![(1, ()), (2, ())].into_iter().collect();
+    assert_eq!(slab.len(), 2);
+    assert_eq!(slab.insert(()), 0);
+    assert_eq!(slab.insert(()), 3);
+    assert_eq!(slab.insert(()), 4);
+
+    let mut slab: slab::Slab<()> = vec![(1, ()), (3, ())].into_iter().collect();
+    assert_eq!(slab.len(), 2);
+    assert_eq!(slab.insert(()), 2);
+    assert_eq!(slab.insert(()), 0);
+    assert_eq!(slab.insert(()), 4);
+
+    let mut slab: slab::Slab<()> = vec![(0, ()), (2, ()), (3, ()), (5, ())]
+        .into_iter()
+        .collect();
+    assert_eq!(slab.len(), 4);
+    assert_eq!(slab.insert(()), 4);
+    assert_eq!(slab.insert(()), 1);
+    assert_eq!(slab.insert(()), 6);
+}
+
+#[test]
 fn clear() {
     let mut slab = Slab::new();
 
@@ -244,9 +451,7 @@ fn clear() {
 
     // clear full
     slab.clear();
-
-    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
-    assert!(vals.is_empty());
+    assert!(slab.is_empty());
 
     assert_eq!(0, slab.len());
     assert_eq!(4, slab.capacity());
@@ -260,9 +465,186 @@ fn clear() {
 
     // clear half-filled
     slab.clear();
+    assert!(slab.is_empty());
+}
 
-    let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect();
-    assert!(vals.is_empty());
+#[test]
+fn shrink_to_fit_empty() {
+    let mut slab = Slab::<bool>::with_capacity(20);
+    slab.shrink_to_fit();
+    assert_eq!(slab.capacity(), 0);
+}
+
+#[test]
+fn shrink_to_fit_no_vacant() {
+    let mut slab = Slab::with_capacity(20);
+    slab.insert(String::new());
+    slab.shrink_to_fit();
+    assert!(slab.capacity() < 10);
+}
+
+#[test]
+fn shrink_to_fit_doesnt_move() {
+    let mut slab = Slab::with_capacity(8);
+    slab.insert("foo");
+    let bar = slab.insert("bar");
+    slab.insert("baz");
+    let quux = slab.insert("quux");
+    slab.remove(quux);
+    slab.remove(bar);
+    slab.shrink_to_fit();
+    assert_eq!(slab.len(), 2);
+    assert!(slab.capacity() >= 3);
+    assert_eq!(slab.get(0), Some(&"foo"));
+    assert_eq!(slab.get(2), Some(&"baz"));
+    assert_eq!(slab.vacant_entry().key(), bar);
+}
+
+#[test]
+fn shrink_to_fit_doesnt_recreate_list_when_nothing_can_be_done() {
+    let mut slab = Slab::with_capacity(16);
+    for i in 0..4 {
+        slab.insert(Box::new(i));
+    }
+    slab.remove(0);
+    slab.remove(2);
+    slab.remove(1);
+    assert_eq!(slab.vacant_entry().key(), 1);
+    slab.shrink_to_fit();
+    assert_eq!(slab.len(), 1);
+    assert!(slab.capacity() >= 4);
+    assert_eq!(slab.vacant_entry().key(), 1);
+}
+
+#[test]
+fn compact_empty() {
+    let mut slab = Slab::new();
+    slab.compact(|_, _, _| panic!());
+    assert_eq!(slab.len(), 0);
+    assert_eq!(slab.capacity(), 0);
+    slab.reserve(20);
+    slab.compact(|_, _, _| panic!());
+    assert_eq!(slab.len(), 0);
+    assert_eq!(slab.capacity(), 0);
+    slab.insert(0);
+    slab.insert(1);
+    slab.insert(2);
+    slab.remove(1);
+    slab.remove(2);
+    slab.remove(0);
+    slab.compact(|_, _, _| panic!());
+    assert_eq!(slab.len(), 0);
+    assert_eq!(slab.capacity(), 0);
+}
+
+#[test]
+fn compact_no_moves_needed() {
+    let mut slab = Slab::new();
+    for i in 0..10 {
+        slab.insert(i);
+    }
+    slab.remove(8);
+    slab.remove(9);
+    slab.remove(6);
+    slab.remove(7);
+    slab.compact(|_, _, _| panic!());
+    assert_eq!(slab.len(), 6);
+    for ((index, &value), want) in slab.iter().zip(0..6) {
+        assert!(index == value);
+        assert_eq!(index, want);
+    }
+    assert!(slab.capacity() >= 6 && slab.capacity() < 10);
+}
+
+#[test]
+fn compact_moves_successfully() {
+    let mut slab = Slab::with_capacity(20);
+    for i in 0..10 {
+        slab.insert(i);
+    }
+    for &i in &[0, 5, 9, 6, 3] {
+        slab.remove(i);
+    }
+    let mut moved = 0;
+    slab.compact(|&mut v, from, to| {
+        assert!(from > to);
+        assert!(from >= 5);
+        assert!(to < 5);
+        assert_eq!(from, v);
+        moved += 1;
+        true
+    });
+    assert_eq!(slab.len(), 5);
+    assert_eq!(moved, 2);
+    assert_eq!(slab.vacant_entry().key(), 5);
+    assert!(slab.capacity() >= 5 && slab.capacity() < 20);
+    let mut iter = slab.iter();
+    assert_eq!(iter.next(), Some((0, &8)));
+    assert_eq!(iter.next(), Some((1, &1)));
+    assert_eq!(iter.next(), Some((2, &2)));
+    assert_eq!(iter.next(), Some((3, &7)));
+    assert_eq!(iter.next(), Some((4, &4)));
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
+fn compact_doesnt_move_if_closure_errors() {
+    let mut slab = Slab::with_capacity(20);
+    for i in 0..10 {
+        slab.insert(i);
+    }
+    for &i in &[9, 3, 1, 4, 0] {
+        slab.remove(i);
+    }
+    slab.compact(|&mut v, from, to| {
+        assert!(from > to);
+        assert_eq!(from, v);
+        v != 6
+    });
+    assert_eq!(slab.len(), 5);
+    assert!(slab.capacity() >= 7 && slab.capacity() < 20);
+    assert_eq!(slab.vacant_entry().key(), 3);
+    let mut iter = slab.iter();
+    assert_eq!(iter.next(), Some((0, &8)));
+    assert_eq!(iter.next(), Some((1, &7)));
+    assert_eq!(iter.next(), Some((2, &2)));
+    assert_eq!(iter.next(), Some((5, &5)));
+    assert_eq!(iter.next(), Some((6, &6)));
+    assert_eq!(iter.next(), None);
+}
+
+#[test]
+fn compact_handles_closure_panic() {
+    let mut slab = Slab::new();
+    for i in 0..10 {
+        slab.insert(i);
+    }
+    for i in 1..6 {
+        slab.remove(i);
+    }
+    let result = catch_unwind(AssertUnwindSafe(|| {
+        slab.compact(|&mut v, from, to| {
+            assert!(from > to);
+            assert_eq!(from, v);
+            if v == 7 {
+                panic!("test");
+            }
+            true
+        })
+    }));
+    match result {
+        Err(ref payload) if payload.downcast_ref() == Some(&"test") => {}
+        Err(bug) => resume_unwind(bug),
+        Ok(()) => unreachable!(),
+    }
+    assert_eq!(slab.len(), 5 - 1);
+    assert_eq!(slab.vacant_entry().key(), 3);
+    let mut iter = slab.iter();
+    assert_eq!(iter.next(), Some((0, &0)));
+    assert_eq!(iter.next(), Some((1, &9)));
+    assert_eq!(iter.next(), Some((2, &8)));
+    assert_eq!(iter.next(), Some((6, &6)));
+    assert_eq!(iter.next(), None);
 }
 
 #[test]
@@ -299,3 +681,32 @@ fn partially_consumed_drain() {
 
     assert!(slab.is_empty())
 }
+
+#[test]
+fn drain_rev() {
+    let mut slab = Slab::new();
+    for i in 0..10 {
+        slab.insert(i);
+    }
+    slab.remove(9);
+
+    let vals: Vec<u64> = slab.drain().rev().collect();
+    assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>());
+}
+
+#[test]
+fn try_remove() {
+    let mut slab = Slab::new();
+
+    let key = slab.insert(1);
+
+    assert_eq!(slab.try_remove(key), Some(1));
+    assert_eq!(slab.try_remove(key), None);
+    assert_eq!(slab.get(key), None);
+}
+
+#[rustversion::since(1.39)]
+#[test]
+fn const_new() {
+    static _SLAB: Slab<()> = Slab::new();
+}