Adding upstream version 115.7.0esr.upstream/115.7.0esr

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

8 files changed, 1961 insertions, 0 deletions

diff --git a/third_party/rust/smallbitvec/.cargo-checksum.json b/third_party/rust/smallbitvec/.cargo-checksum.json
new file mode 100644
index 0000000000..260228b30d
--- /dev/null
+++ b/third_party/rust/smallbitvec/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"2c3c147df069479810f3ec05588d3b180fb703c76d01d11688c46ad7a1a7f188","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"daa94322de7eab889e055932396160395bd8e3af82f56ae8c419d3049111da72","README.md":"4ac9c9b88726f6bcc3b454d61ce75a8224bd430584b765e304be9aa21815c327","benches/bench.rs":"5b446ae8a38d32ad08e06eafc93c3f158674d54e94b21005f871b35dd449cd39","src/lib.rs":"aed4abd2c1c347b38f89b61853ad15fa000abed0316f6f88bf680184cbb7f041","src/tests.rs":"f993740d6656eed737a1b0c7d15b10556c1ddc0ee62d91ff19aa6ad35dcb31e4"},"package":"75ce4f9dc4a41b4c3476cc925f1efb11b66df373a8fde5d4b8915fa91b5d995e"}
\ No newline at end of file
diff --git a/third_party/rust/smallbitvec/Cargo.toml b/third_party/rust/smallbitvec/Cargo.toml
new file mode 100644
index 0000000000..d6bd1266c6
--- /dev/null
+++ b/third_party/rust/smallbitvec/Cargo.toml
@@ -0,0 +1,28 @@
+# 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 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)
+
+[package]
+name = "smallbitvec"
+version = "2.5.1"
+authors = ["Matt Brubeck <mbrubeck@limpet.net>"]
+description = "A bit vector optimized for size and inline storage"
+documentation = "https://docs.rs/smallbitvec"
+readme = "README.md"
+keywords = ["bitvec", "bitmap", "vec", "data-structures"]
+categories = ["data-structures"]
+license = "MIT / Apache-2.0"
+repository = "https://github.com/servo/smallbitvec"
+[dev-dependencies.bit-vec]
+version = "0.4.4"
+
+[dev-dependencies.rand]
+version = "0.4.2"
diff --git a/third_party/rust/smallbitvec/LICENSE-APACHE b/third_party/rust/smallbitvec/LICENSE-APACHE
new file mode 100644
index 0000000000..16fe87b06e
--- /dev/null
+++ b/third_party/rust/smallbitvec/LICENSE-APACHE
@@ -0,0 +1,201 @@
+                              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
+
+APPENDIX: How to apply the Apache License to your work.
+
+   To apply the Apache License to your work, attach the following
+   boilerplate notice, with the fields enclosed by brackets "[]"
+   replaced with your own identifying information. (Don't include
+   the brackets!)  The text should be enclosed in the appropriate
+   comment syntax for the file format. We also recommend that a
+   file or class name and description of purpose be included on the
+   same "printed page" as the copyright notice for easier
+   identification within third-party archives.
+
+Copyright [yyyy] [name of copyright owner]
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+	http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/third_party/rust/smallbitvec/LICENSE-MIT b/third_party/rust/smallbitvec/LICENSE-MIT
new file mode 100644
index 0000000000..a9d616611d
--- /dev/null
+++ b/third_party/rust/smallbitvec/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2017 Matt Brubeck
+
+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/smallbitvec/README.md b/third_party/rust/smallbitvec/README.md
new file mode 100644
index 0000000000..e4cc18152a
--- /dev/null
+++ b/third_party/rust/smallbitvec/README.md
@@ -0,0 +1,9 @@
+# smallbitvec
+
+A bit vector that is only one word wide, and can store data either inline or
+on the heap.  Like the `bit-vec` crate but optimized for small inline size and
+reduced allocations.
+
+* [Documentation](https://docs.rs/smallbitvec)
+* [crates.io](https://crates.io/crates/smallbitvec)
+* [Release notes](https://github.com/servo/smallbitvec/releases)
diff --git a/third_party/rust/smallbitvec/benches/bench.rs b/third_party/rust/smallbitvec/benches/bench.rs
new file mode 100644
index 0000000000..de44b6dc68
--- /dev/null
+++ b/third_party/rust/smallbitvec/benches/bench.rs
@@ -0,0 +1,239 @@
+// Copyright 2012-2014 The Rust Project Developers.
+// Copyright 2017 Matt Brubeck.
+// See the COPYRIGHT file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(test)]
+
+extern crate bit_vec;
+extern crate rand;
+extern crate smallbitvec;
+extern crate test;
+
+use std::hash::{Hash, Hasher};
+
+use bit_vec::BitVec;
+use rand::{weak_rng, Rng, XorShiftRng};
+use smallbitvec::SmallBitVec;
+use test::{black_box, Bencher};
+
+const BENCH_BITS: usize = 1 << 14;
+const USIZE_BITS: usize = ::std::mem::size_of::<usize>() * 8;
+
+fn rng() -> XorShiftRng {
+    weak_rng()
+}
+
+#[bench]
+fn bench_bit_set_big_fixed_bv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set((r.next_u64() as usize) % BENCH_BITS, true);
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_bit_set_big_fixed_sbv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set(r.next_u64() as usize % BENCH_BITS, true);
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_big_set_big_variable_bv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set((r.next_u64() as usize) % BENCH_BITS, r.gen());
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_bit_set_big_variable_sbv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set(r.next_u64() as usize % BENCH_BITS, r.gen());
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_bit_set_small_bv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = BitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set((r.next_u64() as usize) % USIZE_BITS, true);
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_bit_set_small_sbv(b: &mut Bencher) {
+    let mut r = rng();
+    let mut bit_vec = SmallBitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| {
+        for _ in 0..100 {
+            bit_vec.set(r.next_u64() as usize % USIZE_BITS, true);
+        }
+        black_box(&bit_vec);
+    });
+}
+
+#[bench]
+fn bench_bit_vec_small_eq_bv(b: &mut Bencher) {
+    let x = BitVec::from_elem(USIZE_BITS, false);
+    let y = BitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| x == y);
+}
+
+#[bench]
+fn bench_bit_vec_small_eq_sbv(b: &mut Bencher) {
+    let x = SmallBitVec::from_elem(USIZE_BITS, false);
+    let y = SmallBitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| x == y);
+}
+
+#[bench]
+fn bench_bit_vec_big_eq_bv(b: &mut Bencher) {
+    let x = BitVec::from_elem(BENCH_BITS, false);
+    let y = BitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| x == y);
+}
+
+#[bench]
+fn bench_bit_vec_big_eq_sbv(b: &mut Bencher) {
+    let x = SmallBitVec::from_elem(BENCH_BITS, false);
+    let y = SmallBitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| x == y);
+}
+
+#[bench]
+fn bench_bit_vec_small_iter_bv(b: &mut Bencher) {
+    let bit_vec = BitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| {
+        let mut sum = 0;
+        for _ in 0..10 {
+            for pres in &bit_vec {
+                sum += pres as usize;
+            }
+        }
+        sum
+    })
+}
+
+#[bench]
+fn bench_bit_vec_small_iter_sbv(b: &mut Bencher) {
+    let bit_vec = SmallBitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| {
+        let mut sum = 0;
+        for _ in 0..10 {
+            for pres in &bit_vec {
+                sum += pres as usize;
+            }
+        }
+        sum
+    })
+}
+
+#[bench]
+fn bench_bit_vec_big_iter_bv(b: &mut Bencher) {
+    let bit_vec = BitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        let mut sum = 0;
+        for pres in &bit_vec {
+            sum += pres as usize;
+        }
+        sum
+    })
+}
+
+#[bench]
+fn bench_bit_vec_big_iter_sbv(b: &mut Bencher) {
+    let bit_vec = SmallBitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        let mut sum = 0;
+        for pres in &bit_vec {
+            sum += pres as usize;
+        }
+        sum
+    })
+}
+
+#[bench]
+fn bench_from_elem_bv(b: &mut Bencher) {
+    let cap = black_box(BENCH_BITS);
+    let bit = black_box(true);
+    b.iter(|| BitVec::from_elem(cap, bit));
+    b.bytes = cap as u64 / 8;
+}
+
+#[bench]
+fn bench_from_elem_sbv(b: &mut Bencher) {
+    let cap = black_box(BENCH_BITS);
+    let bit = black_box(true);
+    b.iter(|| SmallBitVec::from_elem(cap, bit));
+    b.bytes = cap as u64 / 8;
+}
+
+#[bench]
+fn bench_remove_small(b: &mut Bencher) {
+    b.iter(|| {
+        let mut v = SmallBitVec::from_elem(USIZE_BITS, false);
+        for _ in 0..USIZE_BITS {
+            v.remove(0);
+        }
+    });
+}
+
+#[bench]
+fn bench_remove_big(b: &mut Bencher) {
+    b.iter(|| {
+        let mut v = SmallBitVec::from_elem(BENCH_BITS, false);
+        for _ in 0..200 {
+            v.remove(0);
+        }
+    });
+}
+
+#[bench]
+fn bench_hash_small(b: &mut Bencher) {
+    let mut hasher = std::collections::hash_map::DefaultHasher::new();
+    let v = SmallBitVec::from_elem(USIZE_BITS, false);
+    b.iter(|| {
+        v.hash(&mut hasher);
+    });
+    black_box(hasher.finish());
+}
+
+#[bench]
+fn bench_hash_big(b: &mut Bencher) {
+    let mut hasher = std::collections::hash_map::DefaultHasher::new();
+    let v = SmallBitVec::from_elem(BENCH_BITS, false);
+    b.iter(|| {
+        v.hash(&mut hasher);
+    });
+    black_box(hasher.finish());
+}
diff --git a/third_party/rust/smallbitvec/src/lib.rs b/third_party/rust/smallbitvec/src/lib.rs
new file mode 100644
index 0000000000..49c443d668
--- /dev/null
+++ b/third_party/rust/smallbitvec/src/lib.rs
@@ -0,0 +1,1061 @@
+// Copyright 2017 Matt Brubeck. See the COPYRIGHT file at the top-level
+// directory of this distribution and at http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! [`SmallBitVec`] is a bit vector, a vector of single-bit values stored compactly in memory.
+//!
+//! SmallBitVec grows dynamically, like the standard `Vec<T>` type.  It can hold up to about one
+//! word of bits inline (without a separate heap allocation).  If the number of bits exceeds this
+//! inline capacity, it will allocate a buffer on the heap.
+//!
+//! [`SmallBitVec`]: struct.SmallBitVec.html
+//!
+//! # Example
+//!
+//! ```
+//! use smallbitvec::SmallBitVec;
+//!
+//! let mut v = SmallBitVec::new();
+//! v.push(true);
+//! v.push(false);
+//!
+//! assert_eq!(v[0], true);
+//! assert_eq!(v[1], false);
+//! ```
+
+#![no_std]
+
+extern crate alloc;
+
+use alloc::{vec, vec::Vec, boxed::Box};
+
+use core::cmp::max;
+use core::fmt;
+use core::hash;
+use core::iter::{DoubleEndedIterator, ExactSizeIterator, FromIterator};
+use core::mem::{forget, replace, size_of};
+use core::ops::{Index, Range};
+use core::slice;
+
+/// Creates a [`SmallBitVec`] containing the arguments.
+///
+/// `sbvec!` allows `SmallBitVec`s to be defined with the same syntax as array expressions.
+/// There are two forms of this macro:
+///
+/// - Create a [`SmallBitVec`] containing a given list of elements:
+///
+/// ```
+/// # #[macro_use] extern crate smallbitvec;
+/// # use smallbitvec::SmallBitVec;
+/// # fn main() {
+/// let v = sbvec![true, false, true];
+/// assert_eq!(v[0], true);
+/// assert_eq!(v[1], false);
+/// assert_eq!(v[2], true);
+/// # }
+/// ```
+///
+/// - Create a [`SmallBitVec`] from a given element and size:
+///
+/// ```
+/// # #[macro_use] extern crate smallbitvec;
+/// # use smallbitvec::SmallBitVec;
+/// # fn main() {
+/// let v = sbvec![true; 3];
+/// assert!(v.into_iter().eq(vec![true, true, true].into_iter()));
+/// # }
+/// ```
+
+#[macro_export]
+macro_rules! sbvec {
+    ($elem:expr; $n:expr) => (
+        $crate::SmallBitVec::from_elem($n, $elem)
+    );
+    ($($x:expr),*) => (
+        [$($x),*].iter().cloned().collect::<$crate::SmallBitVec>()
+    );
+    ($($x:expr,)*) => (
+        sbvec![$($x),*]
+    );
+}
+
+
+// FIXME: replace this with `debug_assert!` when it’s usable in `const`:
+// * https://github.com/rust-lang/rust/issues/49146
+// * https://github.com/rust-lang/rust/issues/51999
+macro_rules! const_debug_assert_le {
+    ($left: ident <= $right: expr) =>  {
+        #[cfg(debug_assertions)]
+        // Causes an `index out of bounds` panic if `$left` is too large
+        [(); $right + 1][$left];
+    }
+}
+
+#[cfg(test)]
+mod tests;
+
+/// A resizable bit vector, optimized for size and inline storage.
+///
+/// `SmallBitVec` is exactly one word wide. Depending on the required capacity, this word
+/// either stores the bits inline, or it stores a pointer to a separate buffer on the heap.
+pub struct SmallBitVec {
+    data: usize,
+}
+
+/// Total number of bits per word.
+#[inline(always)]
+const fn inline_bits() -> usize {
+    size_of::<usize>() * 8
+}
+
+/// For an inline vector, all bits except two can be used as storage capacity:
+///
+/// - The rightmost bit is set to zero to signal an inline vector.
+/// - The position of the rightmost nonzero bit encodes the length.
+#[inline(always)]
+const fn inline_capacity() -> usize {
+    inline_bits() - 2
+}
+
+/// Left shift amount to access the nth bit
+#[inline(always)]
+const fn inline_shift(n: usize) -> usize {
+    const_debug_assert_le!(n <= inline_capacity());
+    // The storage starts at the leftmost bit.
+    inline_bits() - 1 - n
+}
+
+/// An inline vector with the nth bit set.
+#[inline(always)]
+const fn inline_index(n: usize) -> usize {
+    1 << inline_shift(n)
+}
+
+/// An inline vector with the leftmost `n` bits set.
+#[inline(always)]
+fn inline_ones(n: usize) -> usize {
+    if n == 0 {
+        0
+    } else {
+        !0 << (inline_bits() - n)
+    }
+}
+
+/// If the rightmost bit of `data` is set, then the remaining bits of `data`
+/// are a pointer to a heap allocation.
+const HEAP_FLAG: usize = 1;
+
+/// The allocation will contain a `Header` followed by a [Storage] buffer.
+type Storage = usize;
+
+/// The number of bits in one `Storage`.
+#[inline(always)]
+fn bits_per_storage() -> usize {
+    size_of::<Storage>() * 8
+}
+
+/// Data stored at the start of the heap allocation.
+///
+/// `Header` must have the same alignment as `Storage`.
+struct Header {
+    /// The number of bits in this bit vector.
+    len: Storage,
+
+    /// The number of elements in the [usize] buffer that follows this header.
+    buffer_len: Storage,
+}
+
+impl Header {
+    /// Create a heap allocation with enough space for a header,
+    /// plus a buffer of at least `cap` bits, each initialized to `val`.
+    fn new(cap: usize, len: usize, val: bool) -> *mut Header {
+        let alloc_len = header_len() + buffer_len(cap);
+        let init = if val { !0 } else { 0 };
+
+        let v: Vec<Storage> = vec![init; alloc_len];
+
+        let buffer_len = v.capacity() - header_len();
+        let header_ptr = v.as_ptr() as *mut Header;
+
+        forget(v);
+
+        unsafe {
+            (*header_ptr).len = len;
+            (*header_ptr).buffer_len = buffer_len;
+        }
+        header_ptr
+    }
+}
+
+/// The number of `Storage` elements to allocate to hold a header.
+#[inline(always)]
+fn header_len() -> usize {
+    size_of::<Header>() / size_of::<Storage>()
+}
+
+/// The minimum number of `Storage` elements to hold at least `cap` bits.
+#[inline(always)]
+fn buffer_len(cap: usize) -> usize {
+    (cap + bits_per_storage() - 1) / bits_per_storage()
+}
+
+/// A typed representation of a `SmallBitVec`'s internal storage.
+///
+/// The layout of the data inside both enum variants is a private implementation detail.
+pub enum InternalStorage {
+    /// The internal representation of a `SmallBitVec` that has not spilled to a
+    /// heap allocation.
+    Inline(usize),
+
+    /// The contents of the heap allocation of a spilled `SmallBitVec`.
+    Spilled(Box<[usize]>),
+}
+
+impl SmallBitVec {
+    /// Create an empty vector.
+    #[inline]
+    pub const fn new() -> SmallBitVec {
+        SmallBitVec {
+            data: inline_index(0),
+        }
+    }
+
+    /// Create a vector containing `len` bits, each set to `val`.
+    #[inline]
+    pub fn from_elem(len: usize, val: bool) -> SmallBitVec {
+        if len <= inline_capacity() {
+            return SmallBitVec {
+                data: if val {
+                    inline_ones(len + 1)
+                } else {
+                    inline_index(len)
+                },
+            };
+        }
+        let header_ptr = Header::new(len, len, val);
+        SmallBitVec {
+            data: (header_ptr as usize) | HEAP_FLAG,
+        }
+    }
+
+    /// Create an empty vector with enough storage pre-allocated to store at least `cap` bits
+    /// without resizing.
+    #[inline]
+    pub fn with_capacity(cap: usize) -> SmallBitVec {
+        // Use inline storage if possible.
+        if cap <= inline_capacity() {
+            return SmallBitVec::new();
+        }
+
+        // Otherwise, allocate on the heap.
+        let header_ptr = Header::new(cap, 0, false);
+        SmallBitVec {
+            data: (header_ptr as usize) | HEAP_FLAG,
+        }
+    }
+
+    /// The number of bits stored in this bit vector.
+    #[inline]
+    pub fn len(&self) -> usize {
+        if self.is_inline() {
+            // The rightmost nonzero bit is a sentinel.  All bits to the left of
+            // the sentinel bit are the elements of the bit vector.
+            inline_bits() - self.data.trailing_zeros() as usize - 1
+        } else {
+            self.header().len
+        }
+    }
+
+    /// Returns `true` if this vector contains no bits.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// The number of bits that can be stored in this bit vector without re-allocating.
+    #[inline]
+    pub fn capacity(&self) -> usize {
+        if self.is_inline() {
+            inline_capacity()
+        } else {
+            self.header().buffer_len * bits_per_storage()
+        }
+    }
+
+    /// Get the nth bit in this bit vector.
+    #[inline]
+    pub fn get(&self, n: usize) -> Option<bool> {
+        if n < self.len() {
+            Some(unsafe { self.get_unchecked(n) })
+        } else {
+            None
+        }
+    }
+
+    /// Get the last bit in this bit vector.
+    #[inline]
+    pub fn last(&self) -> Option<bool> {
+        self.len().checked_sub(1).map(|n| unsafe { self.get_unchecked(n) })
+    }
+
+    /// Get the nth bit in this bit vector, without bounds checks.
+    #[inline]
+    pub unsafe fn get_unchecked(&self, n: usize) -> bool {
+        if self.is_inline() {
+            self.data & inline_index(n) != 0
+        } else {
+            let buffer = self.buffer();
+            let i = n / bits_per_storage();
+            let offset = n % bits_per_storage();
+            *buffer.get_unchecked(i) & (1 << offset) != 0
+        }
+    }
+
+    /// Set the nth bit in this bit vector to `val`.  Panics if the index is out of bounds.
+    #[inline]
+    pub fn set(&mut self, n: usize, val: bool) {
+        assert!(n < self.len(), "Index {} out of bounds", n);
+        unsafe {
+            self.set_unchecked(n, val);
+        }
+    }
+
+    /// Set the nth bit in this bit vector to `val`, without bounds checks.
+    #[inline]
+    pub unsafe fn set_unchecked(&mut self, n: usize, val: bool) {
+        if self.is_inline() {
+            if val {
+                self.data |= inline_index(n);
+            } else {
+                self.data &= !inline_index(n);
+            }
+        } else {
+            let buffer = self.buffer_mut();
+            let i = n / bits_per_storage();
+            let offset = n % bits_per_storage();
+            if val {
+                *buffer.get_unchecked_mut(i) |= 1 << offset;
+            } else {
+                *buffer.get_unchecked_mut(i) &= !(1 << offset);
+            }
+        }
+    }
+
+    /// Append a bit to the end of the vector.
+    ///
+    /// ```
+    /// use smallbitvec::SmallBitVec;
+    /// let mut v = SmallBitVec::new();
+    /// v.push(true);
+    ///
+    /// assert_eq!(v.len(), 1);
+    /// assert_eq!(v.get(0), Some(true));
+    /// ```
+    #[inline]
+    pub fn push(&mut self, val: bool) {
+        let idx = self.len();
+        if idx == self.capacity() {
+            self.reserve(1);
+        }
+        unsafe {
+            self.set_len(idx + 1);
+            self.set_unchecked(idx, val);
+        }
+    }
+
+    /// Remove the last bit from the vector and return it, if there is one.
+    ///
+    /// ```
+    /// use smallbitvec::SmallBitVec;
+    /// let mut v = SmallBitVec::new();
+    /// v.push(false);
+    ///
+    /// assert_eq!(v.pop(), Some(false));
+    /// assert_eq!(v.len(), 0);
+    /// assert_eq!(v.pop(), None);
+    /// ```
+    #[inline]
+    pub fn pop(&mut self) -> Option<bool> {
+        self.len().checked_sub(1).map(|last| unsafe {
+            let val = self.get_unchecked(last);
+            self.set_len(last);
+            val
+        })
+    }
+
+    /// Remove and return the bit at index `idx`, shifting all later bits toward the front.
+    ///
+    /// Panics if the index is out of bounds.
+    #[inline]
+    pub fn remove(&mut self, idx: usize) -> bool {
+        let len = self.len();
+        let val = self[idx];
+
+        if self.is_inline() {
+            // Shift later bits, including the length bit, toward the front.
+            let mask = !inline_ones(idx);
+            let new_vals = (self.data & mask) << 1;
+            self.data = (self.data & !mask) | (new_vals & mask);
+        } else {
+            let first = idx / bits_per_storage();
+            let offset = idx % bits_per_storage();
+            let count = buffer_len(len);
+            {
+                // Shift bits within the first storage block.
+                let buf = self.buffer_mut();
+                let mask = !0 << offset;
+                let new_vals = (buf[first] & mask) >> 1;
+                buf[first] = (buf[first] & !mask) | (new_vals & mask);
+            }
+            // Shift bits in subsequent storage blocks.
+            for i in (first + 1)..count {
+                // Move the first bit into the previous block.
+                let bit_idx = i * bits_per_storage();
+                unsafe {
+                    let first_bit = self.get_unchecked(bit_idx);
+                    self.set_unchecked(bit_idx - 1, first_bit);
+                }
+                // Shift the remaining bits.
+                self.buffer_mut()[i] >>= 1;
+            }
+            // Decrement the length.
+            unsafe {
+                self.set_len(len - 1);
+            }
+        }
+        val
+    }
+
+    /// Remove all elements from the vector, without deallocating its buffer.
+    #[inline]
+    pub fn clear(&mut self) {
+        unsafe {
+            self.set_len(0);
+        }
+    }
+
+    /// Reserve capacity for at least `additional` more elements to be inserted.
+    ///
+    /// May reserve more space than requested, to avoid frequent reallocations.
+    ///
+    /// Panics if the new capacity overflows `usize`.
+    ///
+    /// Re-allocates only if `self.capacity() < self.len() + additional`.
+    #[inline]
+    pub fn reserve(&mut self, additional: usize) {
+        let old_cap = self.capacity();
+        let new_cap = self.len()
+            .checked_add(additional)
+            .expect("capacity overflow");
+        if new_cap <= old_cap {
+            return;
+        }
+        // Ensure the new capacity is at least double, to guarantee exponential growth.
+        let double_cap = old_cap.saturating_mul(2);
+        self.reallocate(max(new_cap, double_cap));
+    }
+
+    /// Set the length of the vector. The length must not exceed the capacity.
+    ///
+    /// If this makes the vector longer, then the values of its new elements
+    /// are not specified.
+    #[inline]
+    unsafe fn set_len(&mut self, len: usize) {
+        debug_assert!(len <= self.capacity());
+        if self.is_inline() {
+            let sentinel = inline_index(len);
+            let mask = !(sentinel - 1);
+            self.data |= sentinel;
+            self.data &= mask;
+        } else {
+            self.header_mut().len = len;
+        }
+    }
+
+    /// Returns an iterator that yields the bits of the vector in order, as `bool` values.
+    #[inline]
+    pub fn iter(&self) -> Iter {
+        Iter {
+            vec: self,
+            range: 0..self.len(),
+        }
+    }
+
+    /// Returns an immutable view of a range of bits from this vec.
+    /// ```
+    /// #[macro_use] extern crate smallbitvec;
+    /// let v = sbvec![true, false, true];
+    /// let r = v.range(1..3);
+    /// assert_eq!(r[1], true);
+    /// ```
+    #[inline]
+    pub fn range(&self, range: Range<usize>) -> VecRange {
+        assert!(range.end <= self.len(), "range out of bounds");
+        VecRange { vec: &self, range }
+    }
+
+    /// Returns true if all the bits in the vec are set to zero/false.
+    ///
+    /// On an empty vector, returns true.
+    #[inline]
+    pub fn all_false(&self) -> bool {
+        let mut len = self.len();
+        if len == 0 {
+            return true;
+        }
+
+        if self.is_inline() {
+            let mask = inline_ones(len);
+            self.data & mask == 0
+        } else {
+            for &storage in self.buffer() {
+                if len >= bits_per_storage() {
+                    if storage != 0 {
+                        return false;
+                    }
+                    len -= bits_per_storage();
+                } else {
+                    let mask = (1 << len) - 1;
+                    if storage & mask != 0 {
+                        return false;
+                    }
+                    break;
+                }
+            }
+            true
+        }
+    }
+
+    /// Returns true if all the bits in the vec are set to one/true.
+    ///
+    /// On an empty vector, returns true.
+    #[inline]
+    pub fn all_true(&self) -> bool {
+        let mut len = self.len();
+        if len == 0 {
+            return true;
+        }
+
+        if self.is_inline() {
+            let mask = inline_ones(len);
+            self.data & mask == mask
+        } else {
+            for &storage in self.buffer() {
+                if len >= bits_per_storage() {
+                    if storage != !0 {
+                        return false;
+                    }
+                    len -= bits_per_storage();
+                } else {
+                    let mask = (1 << len) - 1;
+                    if storage & mask != mask {
+                        return false;
+                    }
+                    break;
+                }
+            }
+            true
+        }
+    }
+
+    /// Shorten the vector, keeping the first `len` elements and dropping the rest.
+    ///
+    /// If `len` is greater than or equal to the vector's current length, this has no
+    /// effect.
+    ///
+    /// This does not re-allocate.
+    pub fn truncate(&mut self, len: usize) {
+        unsafe {
+            if len < self.len() {
+                self.set_len(len);
+            }
+        }
+    }
+
+    /// Resizes the vector so that its length is equal to `len`.
+    ///
+    /// If `len` is less than the current length, the vector simply truncated.
+    ///
+    /// If `len` is greater than the current length, `value` is appended to the
+    /// vector until its length equals `len`.
+    pub fn resize(&mut self, len: usize, value: bool) {
+        let old_len = self.len();
+
+        if len > old_len {
+            unsafe {
+                self.reallocate(len);
+                self.set_len(len);
+                for i in old_len..len {
+                    self.set(i, value);
+                }
+            }
+        } else {
+            self.truncate(len);
+        }
+    }
+
+    /// Resize the vector to have capacity for at least `cap` bits.
+    ///
+    /// `cap` must be at least as large as the length of the vector.
+    fn reallocate(&mut self, cap: usize) {
+        let old_cap = self.capacity();
+        if cap <= old_cap {
+            return;
+        }
+        assert!(self.len() <= cap);
+
+        if self.is_heap() {
+            let old_buffer_len = self.header().buffer_len;
+            let new_buffer_len = buffer_len(cap);
+
+            let old_alloc_len = header_len() + old_buffer_len;
+            let new_alloc_len = header_len() + new_buffer_len;
+
+            let old_ptr = self.header_raw() as *mut Storage;
+            let mut v = unsafe { Vec::from_raw_parts(old_ptr, old_alloc_len, old_alloc_len) };
+            v.resize(new_alloc_len, 0);
+            v.shrink_to_fit();
+            self.data = v.as_ptr() as usize | HEAP_FLAG;
+            forget(v);
+
+            self.header_mut().buffer_len = new_buffer_len;
+        } else {
+            let old_self = replace(self, SmallBitVec::with_capacity(cap));
+            unsafe {
+                self.set_len(old_self.len());
+                for i in 0..old_self.len() {
+                    self.set_unchecked(i, old_self.get_unchecked(i));
+                }
+            }
+        }
+    }
+
+    /// If the vector owns a heap allocation, returns a pointer to the start of the allocation.
+    ///
+    /// The layout of the data at this allocation is a private implementation detail.
+    #[inline]
+    pub fn heap_ptr(&self) -> Option<*const usize> {
+        if self.is_heap() {
+            Some((self.data & !HEAP_FLAG) as *const Storage)
+        } else {
+            None
+        }
+    }
+
+    /// Converts this `SmallBitVec` into its internal representation.
+    ///
+    /// The layout of the data inside both enum variants is a private implementation detail.
+    #[inline]
+    pub fn into_storage(self) -> InternalStorage {
+        if self.is_heap() {
+            let alloc_len = header_len() + self.header().buffer_len;
+            let ptr = self.header_raw() as *mut Storage;
+            let slice = unsafe { Box::from_raw(slice::from_raw_parts_mut(ptr, alloc_len)) };
+            forget(self);
+            InternalStorage::Spilled(slice)
+        } else {
+            InternalStorage::Inline(self.data)
+        }
+    }
+
+    /// Creates a `SmallBitVec` directly from the internal storage of another
+    /// `SmallBitVec`.
+    ///
+    /// # Safety
+    ///
+    /// This is highly unsafe.  `storage` needs to have been previously generated
+    /// via `SmallBitVec::into_storage` (at least, it's highly likely to be
+    /// incorrect if it wasn't.)  Violating this may cause problems like corrupting the
+    /// allocator's internal data structures.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # use smallbitvec::{InternalStorage, SmallBitVec};
+    ///
+    /// fn main() {
+    ///     let v = SmallBitVec::from_elem(200, false);
+    ///
+    ///     // Get the internal representation of the SmallBitVec.
+    ///     // unless we transfer its ownership somewhere else.
+    ///     let storage = v.into_storage();
+    ///
+    ///     /// Make a copy of the SmallBitVec's data.
+    ///     let cloned_storage = match storage {
+    ///         InternalStorage::Spilled(vs) => InternalStorage::Spilled(vs.clone()),
+    ///         inline => inline,
+    ///     };
+    ///
+    ///     /// Create a new SmallBitVec from the coped storage.
+    ///     let v = unsafe { SmallBitVec::from_storage(cloned_storage) };
+    /// }
+    /// ```
+    pub unsafe fn from_storage(storage: InternalStorage) -> SmallBitVec {
+        match storage {
+            InternalStorage::Inline(data) => SmallBitVec { data },
+            InternalStorage::Spilled(vs) => {
+                let ptr = Box::into_raw(vs);
+                SmallBitVec {
+                    data: (ptr as *mut usize as usize) | HEAP_FLAG,
+                }
+            }
+        }
+    }
+
+    /// If the rightmost bit is set, then we treat it as inline storage.
+    #[inline]
+    fn is_inline(&self) -> bool {
+        self.data & HEAP_FLAG == 0
+    }
+
+    /// Otherwise, `data` is a pointer to a heap allocation.
+    #[inline]
+    fn is_heap(&self) -> bool {
+        !self.is_inline()
+    }
+
+    /// Get the header of a heap-allocated vector.
+    #[inline]
+    fn header_raw(&self) -> *mut Header {
+        assert!(self.is_heap());
+        (self.data & !HEAP_FLAG) as *mut Header
+    }
+
+    #[inline]
+    fn header_mut(&mut self) -> &mut Header {
+        unsafe { &mut *self.header_raw() }
+    }
+
+    #[inline]
+    fn header(&self) -> &Header {
+        unsafe { &*self.header_raw() }
+    }
+
+    /// Get the buffer of a heap-allocated vector.
+    #[inline]
+    fn buffer_raw(&self) -> *mut [Storage] {
+        unsafe {
+            let header_ptr = self.header_raw();
+            let buffer_len = (*header_ptr).buffer_len;
+            let buffer_ptr = (header_ptr as *mut Storage)
+                .offset((size_of::<Header>() / size_of::<Storage>()) as isize);
+            slice::from_raw_parts_mut(buffer_ptr, buffer_len)
+        }
+    }
+
+    #[inline]
+    fn buffer_mut(&mut self) -> &mut [Storage] {
+        unsafe { &mut *self.buffer_raw() }
+    }
+
+    #[inline]
+    fn buffer(&self) -> &[Storage] {
+        unsafe { &*self.buffer_raw() }
+    }
+}
+
+// Trait implementations:
+
+impl fmt::Debug for SmallBitVec {
+    #[inline]
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_list()
+            .entries(self.iter().map(|b| b as u8))
+            .finish()
+    }
+}
+
+impl Default for SmallBitVec {
+    #[inline]
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl PartialEq for SmallBitVec {
+    fn eq(&self, other: &Self) -> bool {
+        // Compare by inline representation
+        if self.is_inline() && other.is_inline() {
+            return self.data == other.data;
+        }
+
+        let len = self.len();
+        if len != other.len() {
+            return false;
+        }
+
+        // Compare by heap representation
+        if self.is_heap() && other.is_heap() {
+            let buf0 = self.buffer();
+            let buf1 = other.buffer();
+
+            let full_blocks = len / bits_per_storage();
+            let remainder = len % bits_per_storage();
+
+            if buf0[..full_blocks] != buf1[..full_blocks] {
+                return false;
+            }
+
+            if remainder != 0 {
+                let mask = (1 << remainder) - 1;
+                if buf0[full_blocks] & mask != buf1[full_blocks] & mask {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        // Representations differ; fall back to bit-by-bit comparison
+        Iterator::eq(self.iter(), other.iter())
+    }
+}
+
+impl Eq for SmallBitVec {}
+
+impl Drop for SmallBitVec {
+    fn drop(&mut self) {
+        if self.is_heap() {
+            unsafe {
+                let header_ptr = self.header_raw();
+                let alloc_ptr = header_ptr as *mut Storage;
+                let alloc_len = header_len() + (*header_ptr).buffer_len;
+                Vec::from_raw_parts(alloc_ptr, alloc_len, alloc_len);
+            }
+        }
+    }
+}
+
+impl Clone for SmallBitVec {
+    fn clone(&self) -> Self {
+        if self.is_inline() {
+            return SmallBitVec { data: self.data };
+        }
+
+        let buffer_len = self.header().buffer_len;
+        let alloc_len = header_len() + buffer_len;
+        let ptr = self.header_raw() as *mut Storage;
+        let raw_allocation = unsafe { slice::from_raw_parts(ptr, alloc_len) };
+
+        let v = raw_allocation.to_vec();
+        let header_ptr = v.as_ptr() as *mut Header;
+        forget(v);
+        SmallBitVec {
+            data: (header_ptr as usize) | HEAP_FLAG,
+        }
+    }
+}
+
+impl Index<usize> for SmallBitVec {
+    type Output = bool;
+
+    #[inline(always)]
+    fn index(&self, i: usize) -> &bool {
+        assert!(i < self.len(), "index out of range");
+        if self.get(i).unwrap() {
+            &true
+        } else {
+            &false
+        }
+    }
+}
+
+impl hash::Hash for SmallBitVec {
+    #[inline]
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        let len = self.len();
+        len.hash(state);
+        if self.is_inline() {
+            reverse_bits(self.data & inline_ones(len)).hash(state);
+        } else {
+            let full_blocks = len / bits_per_storage();
+            let remainder = len % bits_per_storage();
+            let buffer = self.buffer();
+            if full_blocks != 0 {
+                buffer[..full_blocks].hash(state);
+            }
+            if remainder != 0 {
+                let mask = (1 << remainder) - 1;
+                (buffer[full_blocks] & mask).hash(state);
+            }
+        }
+    }
+}
+
+impl Extend<bool> for SmallBitVec {
+    #[inline]
+    fn extend<I: IntoIterator<Item = bool>>(&mut self, iter: I) {
+        let iter = iter.into_iter();
+
+        let (min, _) = iter.size_hint();
+        assert!(min <= usize::max_value(), "capacity overflow");
+        self.reserve(min);
+
+        for element in iter {
+            self.push(element)
+        }
+    }
+}
+
+impl FromIterator<bool> for SmallBitVec {
+    #[inline]
+    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
+        let mut v = SmallBitVec::new();
+        v.extend(iter);
+        v
+    }
+}
+
+impl IntoIterator for SmallBitVec {
+    type Item = bool;
+    type IntoIter = IntoIter;
+
+    #[inline]
+    fn into_iter(self) -> IntoIter {
+        IntoIter {
+            range: 0..self.len(),
+            vec: self,
+        }
+    }
+}
+
+impl<'a> IntoIterator for &'a SmallBitVec {
+    type Item = bool;
+    type IntoIter = Iter<'a>;
+
+    #[inline]
+    fn into_iter(self) -> Iter<'a> {
+        self.iter()
+    }
+}
+
+/// An iterator that owns a SmallBitVec and yields its bits as `bool` values.
+///
+/// Returned from [`SmallBitVec::into_iter`][1].
+///
+/// [1]: struct.SmallBitVec.html#method.into_iter
+pub struct IntoIter {
+    vec: SmallBitVec,
+    range: Range<usize>,
+}
+
+impl Iterator for IntoIter {
+    type Item = bool;
+
+    #[inline]
+    fn next(&mut self) -> Option<bool> {
+        self.range
+            .next()
+            .map(|i| unsafe { self.vec.get_unchecked(i) })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.range.size_hint()
+    }
+}
+
+impl DoubleEndedIterator for IntoIter {
+    #[inline]
+    fn next_back(&mut self) -> Option<bool> {
+        self.range
+            .next_back()
+            .map(|i| unsafe { self.vec.get_unchecked(i) })
+    }
+}
+
+impl ExactSizeIterator for IntoIter {}
+
+/// An iterator that borrows a SmallBitVec and yields its bits as `bool` values.
+///
+/// Returned from [`SmallBitVec::iter`][1].
+///
+/// [1]: struct.SmallBitVec.html#method.iter
+pub struct Iter<'a> {
+    vec: &'a SmallBitVec,
+    range: Range<usize>,
+}
+
+impl<'a> Default for Iter<'a> {
+    #[inline]
+    fn default() -> Self {
+        const EMPTY: &'static SmallBitVec = &SmallBitVec::new();
+        Self {
+            vec: EMPTY,
+            range: 0..0,
+        }
+    }
+}
+
+impl<'a> Iterator for Iter<'a> {
+    type Item = bool;
+
+    #[inline]
+    fn next(&mut self) -> Option<bool> {
+        self.range
+            .next()
+            .map(|i| unsafe { self.vec.get_unchecked(i) })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.range.size_hint()
+    }
+}
+
+impl<'a> DoubleEndedIterator for Iter<'a> {
+    #[inline]
+    fn next_back(&mut self) -> Option<bool> {
+        self.range
+            .next_back()
+            .map(|i| unsafe { self.vec.get_unchecked(i) })
+    }
+}
+
+impl<'a> ExactSizeIterator for Iter<'a> {}
+
+/// An immutable view of a range of bits from a borrowed SmallBitVec.
+///
+/// Returned from [`SmallBitVec::range`][1].
+///
+/// [1]: struct.SmallBitVec.html#method.range
+#[derive(Debug, Clone)]
+pub struct VecRange<'a> {
+    vec: &'a SmallBitVec,
+    range: Range<usize>,
+}
+
+impl<'a> VecRange<'a> {
+    #[inline]
+    pub fn iter(&self) -> Iter<'a> {
+        Iter {
+            vec: self.vec,
+            range: self.range.clone(),
+        }
+    }
+}
+
+impl<'a> Index<usize> for VecRange<'a> {
+    type Output = bool;
+
+    #[inline]
+    fn index(&self, i: usize) -> &bool {
+        let vec_i = i + self.range.start;
+        assert!(vec_i < self.range.end, "index out of range");
+        &self.vec[vec_i]
+    }
+}
+
+fn reverse_bits(mut value: usize) -> usize {
+    let mut result = 0;
+    for _ in 0..inline_bits() {
+        result <<= 1;
+        result |= value & 1;
+        value >>= 1;
+    }
+    result
+}
diff --git a/third_party/rust/smallbitvec/src/tests.rs b/third_party/rust/smallbitvec/src/tests.rs
new file mode 100644
index 0000000000..a1906c0217
--- /dev/null
+++ b/third_party/rust/smallbitvec/src/tests.rs
@@ -0,0 +1,397 @@
+// Copyright 2017 Matt Brubeck. See the COPYRIGHT file at the top-level
+// directory of this distribution and at http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use super::*;
+
+use alloc::format;
+
+#[cfg(target_pointer_width = "32")]
+#[test]
+fn test_inline_capacity() {
+    assert_eq!(inline_capacity(), 30);
+}
+
+#[cfg(target_pointer_width = "64")]
+#[test]
+fn test_inline_capacity() {
+    assert_eq!(inline_capacity(), 62);
+}
+
+#[test]
+fn new() {
+    let v = SmallBitVec::new();
+    assert_eq!(v.len(), 0);
+    assert_eq!(v.capacity(), inline_capacity());
+    assert!(v.is_empty());
+    assert!(v.is_inline());
+}
+
+#[test]
+fn with_capacity_inline() {
+    for cap in 0..(inline_capacity() + 1) {
+        let v = SmallBitVec::with_capacity(cap);
+        assert_eq!(v.len(), 0);
+        assert_eq!(v.capacity(), inline_capacity());
+        assert!(v.is_inline());
+    }
+}
+
+#[test]
+fn with_capacity_heap() {
+    let cap = inline_capacity() + 1;
+    let v = SmallBitVec::with_capacity(cap);
+    assert_eq!(v.len(), 0);
+    assert!(v.capacity() > inline_capacity());
+    assert!(v.is_heap());
+}
+
+#[test]
+fn set_len_inline() {
+    let mut v = SmallBitVec::new();
+    for i in 0..(inline_capacity() + 1) {
+        unsafe {
+            v.set_len(i);
+        }
+        assert_eq!(v.len(), i);
+    }
+    for i in (0..(inline_capacity() + 1)).rev() {
+        unsafe {
+            v.set_len(i);
+        }
+        assert_eq!(v.len(), i);
+    }
+}
+
+#[test]
+fn set_len_heap() {
+    let mut v = SmallBitVec::with_capacity(500);
+    unsafe {
+        v.set_len(30);
+    }
+    assert_eq!(v.len(), 30);
+}
+
+#[test]
+fn push_many() {
+    let mut v = SmallBitVec::new();
+    for i in 0..500 {
+        v.push(i % 3 == 0);
+    }
+    assert_eq!(v.len(), 500);
+
+    for i in 0..500 {
+        assert_eq!(v.get(i).unwrap(), (i % 3 == 0), "{}", i);
+        assert_eq!(v[i], v.get(i).unwrap());
+    }
+}
+
+#[test]
+#[should_panic(expected = "index out of range")]
+fn index_out_of_bounds() {
+    let v = SmallBitVec::new();
+    v[0];
+}
+
+#[test]
+#[should_panic(expected = "index out of range")]
+fn index_out_of_bounds_nonempty() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v[1 << 32];
+}
+
+#[test]
+fn get_out_of_bounds() {
+    let v = SmallBitVec::new();
+    assert!(v.get(0).is_none());
+}
+
+#[test]
+#[should_panic]
+fn set_out_of_bounds() {
+    let mut v = SmallBitVec::new();
+    v.set(2, false);
+}
+
+#[test]
+fn all_false() {
+    let mut v = SmallBitVec::new();
+    assert!(v.all_false());
+    for _ in 0..100 {
+        v.push(false);
+        assert!(v.all_false());
+
+        let mut v2 = v.clone();
+        v2.push(true);
+        assert!(!v2.all_false());
+    }
+}
+
+#[test]
+fn all_true() {
+    let mut v = SmallBitVec::new();
+    assert!(v.all_true());
+    for _ in 0..100 {
+        v.push(true);
+        assert!(v.all_true());
+
+        let mut v2 = v.clone();
+        v2.push(false);
+        assert!(!v2.all_true());
+    }
+}
+
+#[test]
+fn iter() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(false);
+
+    let mut i = v.iter();
+    assert_eq!(i.next(), Some(true));
+    assert_eq!(i.next(), Some(false));
+    assert_eq!(i.next(), Some(false));
+    assert_eq!(i.next(), None);
+}
+
+#[test]
+fn into_iter() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(false);
+
+    let mut i = v.into_iter();
+    assert_eq!(i.next(), Some(true));
+    assert_eq!(i.next(), Some(false));
+    assert_eq!(i.next(), Some(false));
+    assert_eq!(i.next(), None);
+}
+
+#[test]
+fn iter_back() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(false);
+
+    let mut i = v.iter();
+    assert_eq!(i.next_back(), Some(false));
+    assert_eq!(i.next_back(), Some(false));
+    assert_eq!(i.next_back(), Some(true));
+    assert_eq!(i.next(), None);
+}
+
+#[test]
+fn range() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(false);
+    v.push(true);
+
+    let r = v.range(0..2);
+    let mut ri = r.iter();
+    assert_eq!(ri.next(), Some(true));
+    assert_eq!(ri.next(), Some(false));
+    assert_eq!(ri.next(), None);
+    assert_eq!(r[0], true);
+}
+
+#[test]
+#[should_panic(expected = "range out of bounds")]
+fn range_oob() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+
+    v.range(0..2);
+}
+
+#[test]
+#[should_panic(expected = "index out of range")]
+fn range_index_oob() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(true);
+
+    let r = v.range(1..2);
+    r[1];
+}
+
+#[test]
+fn debug() {
+    let mut v = SmallBitVec::new();
+    v.push(true);
+    v.push(false);
+    v.push(false);
+
+    assert_eq!(format!("{:?}", v), "[1, 0, 0]")
+}
+
+#[test]
+fn from_elem() {
+    for len in 0..100 {
+        let ones = SmallBitVec::from_elem(len, true);
+        assert_eq!(ones.len(), len);
+        assert!(ones.all_true());
+
+        let zeros = SmallBitVec::from_elem(len, false);
+        assert_eq!(zeros.len(), len);
+        assert!(zeros.all_false());
+    }
+}
+
+#[test]
+fn remove() {
+    let mut v = SmallBitVec::new();
+    v.push(false);
+    v.push(true);
+    v.push(false);
+    v.push(false);
+    v.push(true);
+
+    assert_eq!(v.remove(1), true);
+    assert_eq!(format!("{:?}", v), "[0, 0, 0, 1]");
+    assert_eq!(v.remove(0), false);
+    assert_eq!(format!("{:?}", v), "[0, 0, 1]");
+    v.remove(2);
+    assert_eq!(format!("{:?}", v), "[0, 0]");
+    v.remove(1);
+    assert_eq!(format!("{:?}", v), "[0]");
+    v.remove(0);
+    assert_eq!(format!("{:?}", v), "[]");
+}
+
+#[test]
+fn remove_big() {
+    let mut v = SmallBitVec::from_elem(256, false);
+    v.set(100, true);
+    v.set(255, true);
+    v.remove(0);
+    assert_eq!(v.len(), 255);
+    assert_eq!(v.get(0).unwrap(), false);
+    assert_eq!(v.get(99).unwrap(), true);
+    assert_eq!(v.get(100).unwrap(), false);
+    assert_eq!(v.get(253).unwrap(), false);
+    assert_eq!(v.get(254).unwrap(), true);
+
+    v.remove(254);
+    assert_eq!(v.len(), 254);
+    assert_eq!(v.get(0).unwrap(), false);
+    assert_eq!(v.get(99).unwrap(), true);
+    assert_eq!(v.get(100).unwrap(), false);
+    assert_eq!(v.get(253).unwrap(), false);
+
+    v.remove(99);
+    assert_eq!(v, SmallBitVec::from_elem(253, false));
+}
+
+#[test]
+fn eq() {
+    assert_eq!(sbvec![], sbvec![]);
+    assert_eq!(sbvec![true], sbvec![true]);
+    assert_eq!(sbvec![false], sbvec![false]);
+
+    assert_ne!(sbvec![], sbvec![false]);
+    assert_ne!(sbvec![true], sbvec![]);
+    assert_ne!(sbvec![true], sbvec![false]);
+    assert_ne!(sbvec![false], sbvec![true]);
+
+    assert_eq!(sbvec![true, false], sbvec![true, false]);
+    assert_eq!(sbvec![true; 400], sbvec![true; 400]);
+    assert_eq!(sbvec![false; 400], sbvec![false; 400]);
+
+    assert_ne!(sbvec![true, false], sbvec![true, true]);
+    assert_ne!(sbvec![true; 400], sbvec![true; 401]);
+    assert_ne!(sbvec![false; 401], sbvec![false; 400]);
+}
+
+#[test]
+fn truncate_inline() {
+    let mut v = sbvec![false, true, false, false, true];
+    v.truncate(10);
+    assert_eq!(v.len(), 5);
+    v.truncate(3);
+    assert_eq!(v, sbvec![false, true, false]);
+    v.truncate(0);
+    assert_eq!(v, sbvec![]);
+}
+
+#[test]
+fn truncate_large() {
+    let mut v = SmallBitVec::from_elem(256, false);
+    v.set(2, true);
+    v.set(100, true);
+    v.set(255, true);
+    v.truncate(500);
+    assert_eq!(v.len(), 256);
+    v.truncate(150);
+    assert_eq!(v.len(), 150);
+    assert_eq!(v.get(0).unwrap(), false);
+    assert_eq!(v.get(99).unwrap(), false);
+    assert_eq!(v.get(100).unwrap(), true);
+    assert_eq!(v.get(101).unwrap(), false);
+    assert_eq!(v.get(149).unwrap(), false);
+    v.truncate(5);
+    assert_eq!(v.len(), 5);
+    assert_eq!(v, sbvec![false, false, true, false, false]);
+}
+
+#[test]
+fn resize() {
+    let mut v = sbvec![false, true, false, false, true];
+    v.resize(3, false);
+    assert_eq!(v, sbvec![false, true, false]);
+    v.resize(8, true);
+    assert_eq!(v, sbvec![false, true, false, true, true, true, true, true]);
+    v.resize(100, false);
+    assert_eq!(v.len(), 100);
+    assert_eq!(v.get(0).unwrap(), false);
+    assert_eq!(v.get(1).unwrap(), true);
+    assert_eq!(v.get(2).unwrap(), false);
+    assert_eq!(v.get(3).unwrap(), true);
+    assert_eq!(v.get(4).unwrap(), true);
+    assert_eq!(v.get(7).unwrap(), true);
+    assert_eq!(v.get(8).unwrap(), false);
+    assert_eq!(v.get(9).unwrap(), false);
+    assert_eq!(v.get(98).unwrap(), false);
+    assert_eq!(v.get(99).unwrap(), false);
+}
+
+#[test]
+fn hash() {
+    extern crate std;
+    use core::hash::{Hash, Hasher};
+
+    let v1 = sbvec![true, false, true, false, true, true, true];
+    let mut v2 = v1.clone();
+    v2.reserve(100_000);
+    assert_eq!(v1, v2);
+
+    let hash = |v: &SmallBitVec| {
+        let mut hasher = std::collections::hash_map::DefaultHasher::new();
+        v.hash(&mut hasher);
+        hasher.finish()
+    };
+
+    assert_eq!(hash(&v1), hash(&v2));
+
+    let mut v3 = v1.clone();
+    v3.push(false);
+    assert_ne!(hash(&v1), hash(&v3));
+
+    let mut v4 = v2.clone();
+    v4.push(false);
+    assert_ne!(hash(&v2), hash(&v4));
+
+    assert_eq!(v3, v4);
+    assert_eq!(hash(&v3), hash(&v4));
+}