bit-vec 0.6.3 is a #![no_std] bit-vector crate with no ambient capabilities; two unsafe fn declarations contain no unsafe operations. Three low-severity quality findings (stale docs, no property tests, duplicated comment phrase); safe to deploy.
bit-vec is a #![no_std]-compatible Rust crate that provides BitVec, a vector of bits parameterised over an unsigned-integer block type (u8/u16/u32/u64/usize, defaulting to u32). The public API exposes random-access bit reads and writes, bitwise operators between equal-length vectors (and, or, xor, nand, nor, xnor, difference), aggregate queries (all, any, none), structural operations (push, pop, grow, truncate, append, split_off), byte-vector conversion, iterators, and optional serde (de)serialisation behind the serde feature. The crate is a direct descendant of the pre-1.0 std::collections::BitVec and is part of the unmaintained contain-rs collection family.
The published crate contents were compared against the upstream contain-rs/bit-vec repository at the commit recorded in .cargo_vcs_info.json (9751897) using diff -r. The single source file src/lib.rs (2535 lines, including ~900 lines of tests) was read in full and audited against the module-level invariants documented at the top of the file. Particular attention was paid to the bit-shifting paths in from_bytes, append, split_off, grow, nand, nor, and xnor, where shift amounts and last-block fixups are subtle. The optional serde feature was reviewed alongside the default std configuration. The bench file under benches/ and the developer-only crusader.sh script were examined. Dependencies (serde runtime; serde_json, rand, rand_xorshift dev-only) were not in scope. The test suite was not executed.
The published crate matches the upstream repository: source files (src/lib.rs, benches/bench.rs, README.md, crusader.sh, both licence files) are byte-for-byte identical, and the only Cargo.toml differences are cargo's standard normalisation. No build script, no procedural macros, no install hooks, and no binary artefacts ship in the crate, justifying has-build-exec, has-install-exec, and has-binaries. The library is #![no_std] and depends on alloc for Vec; nothing in the codebase touches the network, filesystem, environment, child processes, JIT, interpreters, cryptography, threading, or any other ambient capability, justifying uses-crypto, uses-exec, uses-jit, uses-interpreter, uses-network, uses-filesystem, uses-environment, uses-concurrency, impl-crypto, impl-parser, impl-interpreter, impl-jit, impl-protocol, and impl-concurrency.
BitVec is a bit-vector data structure (justifying impl-datastructure) and ships the canonical bitwise set algorithms (union/intersection/difference and their negated variants, justifying impl-algorithm). The implementation maintains two invariants (no excess trailing block; unused tail bits zeroed) via fix_last_block and a debug_assert!-gated is_last_block_fixed check on each public entry point. Operations that may dirty the tail (negate, nand, nor, xnor, grow, split_off, truncate) re-establish the invariant before returning, supporting datastructure-impl-correct and algorithm-impl-correct. Capacity arithmetic uses checked_mul/checked_add at all user-reachable entry points, and shift amounts in split_off and mask_for_bits are guarded against shift-by-bit-width, supporting datastructure-impl-safe and algorithm-impl-safe. Operations are linear in storage word count and do not depend on bit values, so adversarial inputs cannot degrade them, supporting datastructure-impl-bounds and algorithm-impl-bounds. The crate ships ~900 lines of example-based unit tests covering boundary block sizes (0, 1, 2, 10, 31, 32, 33, 100), every bitwise operator, append/split aligned and unaligned, and serde round-trip when the feature is enabled, supporting has-unit-tests, datastructure-impl-tested, and algorithm-impl-tested.
The crate uses the unsafe keyword in exactly two places, both unsafe fn declarations exposing internals to the sibling bit-set crate: BitVec::storage_mut returns the raw Vec<B> storage, and BitVec::set_len overwrites the bit-count field. The bodies of both contain no unsafe operations and the rest of the crate uses bounds-checked indexing (get/storage[w]) on all storage access, so the worst caller-visible consequence of misuse is a panic or incorrect bits, not undefined behaviour. Both are documented inline. Together this justifies uses-unsafe, unsafe-safe, unsafe-documented, and unsafe-minimal; unsafe-tested is false because no test exercises either function. The codebase contains no malicious patterns, network beacons, obfuscated payloads, or target-specific branches, justifying is-benign.
Three low-severity quality findings were recorded: stale documentation links and README badges (FINDING-1), absence of property-based or fuzz testing in a data-structure crate whose correctness rests on subtle last-block invariants (FINDING-2), and a duplicated phrase in a code comment (FINDING-3). The crate has no integration tests, no property tests, and no fuzz tests, justifying has-integration-tests, has-property-tests, and has-fuzz-tests.
bit-vec 0.6.3 is a small, focused, dependency-light data-structure crate with no ambient capabilities and no genuine memory-unsafety surface. The implementation is correct on the cases its example-based tests cover; the absence of randomised testing is the main quality gap for a structure whose internal invariants are non-trivial.
The Cargo.toml documentation field points to https://contain-rs.github.io/bit-vec/bit_vec, the page no longer serves up-to-date documentation for this crate, and the canonical location is https://docs.rs/bit-vec. The README's docs.rs and deps.rs badges reference an older version (0.6.2) and link to Travis CI, which has been deprecated. Cosmetic only; does not affect runtime behaviour.
The crate ships ~900 lines of example-based unit tests in src/lib.rs but no property-based tests (proptest, quickcheck) or fuzz harnesses. The implementation maintains two subtle internal invariants documented at the top of src/lib.rs lines 17-26: (a) the underlying storage has no excess length and (b) unused bits in the last word are zeroed. Methods like append, split_off, grow, nand, nor, and xnor perform non-trivial bit-shifting and last-block fixups to preserve these. Randomized differential testing against a Vec<bool> model would give stronger assurance of correctness across many block sizes and split positions than the present hand-written tests.
In src/lib.rs at line 1271 the comment in BitVec::grow contains the phrase "at the end of this fn" twice: "...we call fix_last_block at the end of this fn, which should fix this." Trivial typo; the code itself is correct.
Cargo.tomlCargo manifest. The crate is #![no_std] (see src/lib.rs line 85); the default feature std is opt-out and only re-enables std. The single optional dependency is serde with default-features = false and the derive feature, used only for #[derive(Serialize, Deserialize)] on BitVec (line 211). No build.rs, no [lib] proc-macro, no install hooks, justifying has-build-exec and has-install-exec.
crusader.shDeveloper-only script that runs cargo-crusader (an ecosystem reverse-dependency tester from github.com/brson/cargo-crusader) against the crate. Shipping the script in the published crate is harmless; it is never executed during cargo build, cargo test, or by consumers, and is not referenced from Cargo.toml.
src/lib.rssrc/lib.rs, line 419-426
/// Exposes the raw block storage of this BitVec
///
/// Can probably cause unsafety. Only really intended for BitSet.
#[inline]
pub unsafe fn storage_mut(&mut self) -> &mut Vec<B> {
&mut self.storage
}
pub unsafe fn storage_mut exposes the raw Vec<B> storage. The body itself contains no unsafe operations; the unsafe marker delegates to the caller responsibility for maintaining the two structural invariants noted at the top of the file (no excess storage length, unused bits in last block zeroed). Together with set_len at line 1369, this is the only use of the unsafe keyword in the crate, justifying uses-unsafe.
src/lib.rs, line 1365-1371 /// Sets the number of bits that this BitVec considers initialized.
///
/// Almost certainly can cause bad stuff. Only really intended for BitSet.
#[inline]
pub unsafe fn set_len(&mut self, len: usize) {
self.nbits = len;
}
pub unsafe fn set_len allows the caller to overwrite nbits without validating that storage backs it. Neither this nor storage_mut actually performs raw-pointer arithmetic, FFI, or any operation that could produce undefined behaviour: get uses self.storage.get(w) (bounds-checked), set uses self.storage[w] (panics, no UB), and iterators consume only the live Vec. The worst caller-visible consequence of misuse is a panic or incorrect bits, justifying unsafe-safe, unsafe-minimal, unsafe-documented.
src/lib.rs, line 17-26// (1) Be careful, most things can overflow here because the amount of bits in
// memory can overflow `usize`.
// (2) Make sure that the underlying vector has no excess length:
// E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
// because the last word isn't used at all. This is important because some
// methods rely on it (for *CORRECTNESS*).
// (3) Make sure that the unused bits in the last word are zeroed out, again
// other methods rely on it for *CORRECTNESS*.
// (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
// `BitVec` will need to be reflected in `BitSet`.
Module-level invariants the implementation must preserve: (1) bit counts are guarded against usize overflow with checked_* arithmetic in callers like push, grow, reserve, from_bytes; (2) storage has no excess length, enforced by truncate/pop; (3) unused bits in the last word are zeroed, enforced by fix_last_block and fix_last_block_with_ones around non-monotonic operations such as negate, nand, nor, xnor, grow, split_off. The invariants are checked by debug_assert!(self.is_last_block_fixed()) (via ensure_invariant) on each public read and on the other operand of binary operators. The invariants directly support the correctness of all, none, eq, hash, and cmp. Justifies datastructure-impl-correct, algorithm-impl-correct, datastructure-impl-safe, algorithm-impl-safe, datastructure-impl-bounds, algorithm-impl-bounds, uses-network, uses-filesystem, uses-environment, uses-exec, uses-jit, uses-interpreter, uses-crypto, impl-crypto, impl-parser, impl-interpreter, impl-jit, impl-protocol, impl-concurrency, uses-concurrency.
src/lib.rs, line 951-980 pub fn append(&mut self, other: &mut Self) {
self.ensure_invariant();
debug_assert!(other.is_last_block_fixed());
let b = self.len() % B::bits();
let o = other.len() % B::bits();
let will_overflow = (b + o > B::bits()) || (o == 0 && b != 0);
self.nbits += other.len();
other.nbits = 0;
if b == 0 {
self.storage.append(&mut other.storage);
} else {
self.storage.reserve(other.storage.len());
for block in other.storage.drain(..) {
{
let last = self.storage.last_mut().unwrap();
*last = *last | (block << b);
}
self.storage.push(block >> (B::bits() - b));
}
// Remove additional block if the last shift did not overflow
if !will_overflow {
self.storage.pop();
}
}
}
append is the most subtle bit-shifting routine in the crate. When the destination's length is a multiple of B::bits() the operand's storage is moved wholesale; otherwise each operand block is shifted across two destination words. The will_overflow predicate decides whether the final push produced a spurious trailing block to be popped. Walked through the algebra for the four (b,o) cases: aligned/aligned, unaligned/aligned, unaligned/unaligned with b+o > B::bits, and unaligned/unaligned with b+o <= B::bits; tests test_bit_vec_append, test_bit_vec_unaligned_small_append, test_bit_vec_unaligned_large_append, and test_bit_vec_append_aligned_to_unaligned exercise all four paths. Supports datastructure-impl-correct, impl-datastructure, impl-algorithm.
src/lib.rs, line 1006-1044 pub fn split_off(&mut self, at: usize) -> Self {
self.ensure_invariant();
assert!(at <= self.len(), "`at` out of bounds");
let mut other = BitVec::<B>::default();
if at == 0 {
mem::swap(self, &mut other);
return other;
} else if at == self.len() {
return other;
}
let w = at / B::bits();
let b = at % B::bits();
other.nbits = self.nbits - at;
self.nbits = at;
if b == 0 {
// Split at block boundary
other.storage = self.storage.split_off(w);
} else {
other.storage.reserve(self.storage.len() - w);
{
let mut iter = self.storage[w..].iter();
let mut last = *iter.next().unwrap();
for &cur in iter {
other.storage.push((last >> b) | (cur << (B::bits() - b)));
last = cur;
}
other.storage.push(last >> b);
}
self.storage.truncate(w + 1);
self.fix_last_block();
}
other
}
split_off mirrors append. The aligned path reuses Vec::split_off; the unaligned path assembles each new block from (last >> b) | (cur << (B::bits - b)) and truncates self to the partial last block before calling fix_last_block. Shift amounts are always strictly less than B::bits since the b == 0 case is special-cased, avoiding the shift-by-bit-width UB hazard. test_bit_vec_split_off covers the block-boundary and unaligned cases.
src/lib.rs, line 250-254/// Computes the bitmask for the final word of the vector
fn mask_for_bits<B: BitBlock>(bits: usize) -> B {
// Note especially that a perfect multiple of U32_BITS should mask all 1s.
(!B::zero()) >> ((B::bits() - bits % B::bits()) % B::bits())
}
mask_for_bits returns the bitmask of used bits in the last word. The expression (B::bits() - bits % B::bits()) % B::bits() evaluates to 0 when bits is an exact multiple of B::bits() (producing an all-ones mask) and to B::bits() - r for non-zero remainder r (producing r low-set bits). The double-modulo avoids a shift-by-bit-width that would be undefined behaviour.
src/lib.rs, line 328-355 pub fn from_bytes(bytes: &[u8]) -> Self {
let len = bytes.len().checked_mul(u8::bits()).expect("capacity overflow");
let mut bit_vec = BitVec::with_capacity(len);
let complete_words = bytes.len() / B::bytes();
let extra_bytes = bytes.len() % B::bytes();
bit_vec.nbits = len;
for i in 0..complete_words {
let mut accumulator = B::zero();
for idx in 0..B::bytes() {
accumulator |=
B::from_byte(reverse_bits(bytes[i * B::bytes() + idx])) << (idx * 8)
}
bit_vec.storage.push(accumulator);
}
if extra_bytes > 0 {
let mut last_word = B::zero();
for (i, &byte) in bytes[complete_words * B::bytes()..].iter().enumerate() {
last_word |=
B::from_byte(reverse_bits(byte)) << (i * 8);
}
bit_vec.storage.push(last_word);
}
bit_vec
}
from_bytes guards against bytes.len() * 8 overflowing usize with checked_mul (line 329), assembles complete words via reverse_bits, and pushes any partial trailing word. Per the documented MSB-first byte convention, the example in the doc-comment matches the implementation's bit ordering.
src/lib.rs, line 1604-2535#[cfg(test)]
mod tests {
use super::{BitVec, Iter, Vec};
// This is stupid, but I want to differentiate from a "random" 32
const U32_BITS: usize = 32;
#[test]
fn test_to_str() {
let zerolen = BitVec::new();
assert_eq!(format!("{:?}", zerolen), "");
let eightbits = BitVec::from_elem(8, false);
assert_eq!(format!("{:?}", eightbits), "00000000")
}
#[test]
fn test_0_elements() {
let act = BitVec::new();
let exp = Vec::new();
assert!(act.eq_vec(&exp));
assert!(act.none() && act.all());
}
#[test]
fn test_1_element() {
let mut act = BitVec::from_elem(1, false);
assert!(act.eq_vec(&[false]));
assert!(act.none() && !act.all());
act = BitVec::from_elem(1, true);
assert!(act.eq_vec(&[true]));
assert!(!act.none() && act.all());
}
#[test]
fn test_2_elements() {
let mut b = BitVec::from_elem(2, false);
b.set(0, true);
b.set(1, false);
assert_eq!(format!("{:?}", b), "10");
assert!(!b.none() && !b.all());
}
#[test]
fn test_10_elements() {
let mut act;
// all 0
act = BitVec::from_elem(10, false);
assert!((act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false])));
assert!(act.none() && !act.all());
// all 1
act = BitVec::from_elem(10, true);
assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
assert!(!act.none() && act.all());
// mixed
act = BitVec::from_elem(10, false);
act.set(0, true);
act.set(1, true);
act.set(2, true);
act.set(3, true);
act.set(4, true);
assert!((act.eq_vec(&[true, true, true, true, true, false, false, false, false, false])));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(10, false);
act.set(5, true);
act.set(6, true);
act.set(7, true);
act.set(8, true);
act.set(9, true);
assert!((act.eq_vec(&[false, false, false, false, false, true, true, true, true, true])));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(10, false);
act.set(0, true);
act.set(3, true);
act.set(6, true);
act.set(9, true);
assert!((act.eq_vec(&[true, false, false, true, false, false, true, false, false, true])));
assert!(!act.none() && !act.all());
}
#[test]
fn test_31_elements() {
let mut act;
// all 0
act = BitVec::from_elem(31, false);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false]));
assert!(act.none() && !act.all());
// all 1
act = BitVec::from_elem(31, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true]));
assert!(!act.none() && act.all());
// mixed
act = BitVec::from_elem(31, false);
act.set(0, true);
act.set(1, true);
act.set(2, true);
act.set(3, true);
act.set(4, true);
act.set(5, true);
act.set(6, true);
act.set(7, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(31, false);
act.set(16, true);
act.set(17, true);
act.set(18, true);
act.set(19, true);
act.set(20, true);
act.set(21, true);
act.set(22, true);
act.set(23, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, true, true, true, true, true, true, true,
false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(31, false);
act.set(24, true);
act.set(25, true);
act.set(26, true);
act.set(27, true);
act.set(28, true);
act.set(29, true);
act.set(30, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, true, true, true, true, true, true, true]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(31, false);
act.set(3, true);
act.set(17, true);
act.set(30, true);
assert!(act.eq_vec(
&[false, false, false, true, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, false, false, false, false, false, false,
false, false, false, false, false, false, true]));
assert!(!act.none() && !act.all());
}
#[test]
fn test_32_elements() {
let mut act;
// all 0
act = BitVec::from_elem(32, false);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false]));
assert!(act.none() && !act.all());
// all 1
act = BitVec::from_elem(32, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true]));
assert!(!act.none() && act.all());
// mixed
act = BitVec::from_elem(32, false);
act.set(0, true);
act.set(1, true);
act.set(2, true);
act.set(3, true);
act.set(4, true);
act.set(5, true);
act.set(6, true);
act.set(7, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(32, false);
act.set(16, true);
act.set(17, true);
act.set(18, true);
act.set(19, true);
act.set(20, true);
act.set(21, true);
act.set(22, true);
act.set(23, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, true, true, true, true, true, true, true,
false, false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(32, false);
act.set(24, true);
act.set(25, true);
act.set(26, true);
act.set(27, true);
act.set(28, true);
act.set(29, true);
act.set(30, true);
act.set(31, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, true, true, true, true, true, true, true, true]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(32, false);
act.set(3, true);
act.set(17, true);
act.set(30, true);
act.set(31, true);
assert!(act.eq_vec(
&[false, false, false, true, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, false, false, false, false, false, false,
false, false, false, false, false, false, true, true]));
assert!(!act.none() && !act.all());
}
#[test]
fn test_33_elements() {
let mut act;
// all 0
act = BitVec::from_elem(33, false);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false]));
assert!(act.none() && !act.all());
// all 1
act = BitVec::from_elem(33, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true, true, true, true, true, true, true,
true, true, true, true, true, true, true]));
assert!(!act.none() && act.all());
// mixed
act = BitVec::from_elem(33, false);
act.set(0, true);
act.set(1, true);
act.set(2, true);
act.set(3, true);
act.set(4, true);
act.set(5, true);
act.set(6, true);
act.set(7, true);
assert!(act.eq_vec(
&[true, true, true, true, true, true, true, true, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(33, false);
act.set(16, true);
act.set(17, true);
act.set(18, true);
act.set(19, true);
act.set(20, true);
act.set(21, true);
act.set(22, true);
act.set(23, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, true, true, true, true, true, true, true,
false, false, false, false, false, false, false, false, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(33, false);
act.set(24, true);
act.set(25, true);
act.set(26, true);
act.set(27, true);
act.set(28, true);
act.set(29, true);
act.set(30, true);
act.set(31, true);
assert!(act.eq_vec(
&[false, false, false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, false, false, false, false,
false, false, true, true, true, true, true, true, true, true, false]));
assert!(!act.none() && !act.all());
// mixed
act = BitVec::from_elem(33, false);
act.set(3, true);
act.set(17, true);
act.set(30, true);
act.set(31, true);
act.set(32, true);
assert!(act.eq_vec(
&[false, false, false, true, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, false, false, false, false, false, false,
false, false, false, false, false, false, true, true, true]));
assert!(!act.none() && !act.all());
}
#[test]
fn test_equal_differing_sizes() {
let v0 = BitVec::from_elem(10, false);
let v1 = BitVec::from_elem(11, false);
assert_ne!(v0, v1);
}
#[test]
fn test_equal_greatly_differing_sizes() {
let v0 = BitVec::from_elem(10, false);
let v1 = BitVec::from_elem(110, false);
assert_ne!(v0, v1);
}
#[test]
fn test_equal_sneaky_small() {
let mut a = BitVec::from_elem(1, false);
a.set(0, true);
let mut b = BitVec::from_elem(1, true);
b.set(0, true);
assert_eq!(a, b);
}
#[test]
fn test_equal_sneaky_big() {
let mut a = BitVec::from_elem(100, false);
for i in 0..100 {
a.set(i, true);
}
let mut b = BitVec::from_elem(100, true);
for i in 0..100 {
b.set(i, true);
}
assert_eq!(a, b);
}
#[test]
fn test_from_bytes() {
let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
let str = concat!("10110110", "00000000", "11111111");
assert_eq!(format!("{:?}", bit_vec), str);
}
#[test]
fn test_to_bytes() {
let mut bv = BitVec::from_elem(3, true);
bv.set(1, false);
assert_eq!(bv.to_bytes(), [0b10100000]);
let mut bv = BitVec::from_elem(9, false);
bv.set(2, true);
bv.set(8, true);
assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
}
#[test]
fn test_from_bools() {
let bools = vec![true, false, true, true];
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
assert_eq!(format!("{:?}", bit_vec), "1011");
}
#[test]
fn test_to_bools() {
let bools = vec![false, false, true, false, false, true, true, false];
assert_eq!(BitVec::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
}
#[test]
fn test_bit_vec_iterator() {
let bools = vec![true, false, true, true];
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
let long: Vec<_> = (0..10000).map(|i| i % 2 == 0).collect();
let bit_vec: BitVec = long.iter().map(|n| *n).collect();
assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
}
#[test]
fn test_small_difference() {
let mut b1 = BitVec::from_elem(3, false);
let mut b2 = BitVec::from_elem(3, false);
b1.set(0, true);
b1.set(1, true);
b2.set(1, true);
b2.set(2, true);
assert!(b1.difference(&b2));
assert!(b1[0]);
assert!(!b1[1]);
assert!(!b1[2]);
}
#[test]
fn test_big_difference() {
let mut b1 = BitVec::from_elem(100, false);
let mut b2 = BitVec::from_elem(100, false);
b1.set(0, true);
b1.set(40, true);
b2.set(40, true);
b2.set(80, true);
assert!(b1.difference(&b2));
assert!(b1[0]);
assert!(!b1[40]);
assert!(!b1[80]);
}
#[test]
fn test_small_xor() {
let mut a = BitVec::from_bytes(&[0b0011]);
let b = BitVec::from_bytes(&[0b0101]);
let c = BitVec::from_bytes(&[0b0110]);
assert!(a.xor(&b));
assert_eq!(a,c);
}
#[test]
fn test_small_xnor() {
let mut a = BitVec::from_bytes(&[0b0011]);
let b = BitVec::from_bytes(&[0b1111_0101]);
let c = BitVec::from_bytes(&[0b1001]);
assert!(a.xnor(&b));
assert_eq!(a,c);
}
#[test]
fn test_small_nand() {
let mut a = BitVec::from_bytes(&[0b1111_0011]);
let b = BitVec::from_bytes(&[0b1111_0101]);
let c = BitVec::from_bytes(&[0b1110]);
assert!(a.nand(&b));
assert_eq!(a,c);
}
#[test]
fn test_small_nor() {
let mut a = BitVec::from_bytes(&[0b0011]);
let b = BitVec::from_bytes(&[0b1111_0101]);
let c = BitVec::from_bytes(&[0b1000]);
assert!(a.nor(&b));
assert_eq!(a,c);
}
#[test]
fn test_big_xor() {
let mut a = BitVec::from_bytes(&[ // 88 bits
0, 0, 0b00010100, 0,
0, 0, 0, 0b00110100,
0, 0, 0]);
let b = BitVec::from_bytes(&[ // 88 bits
0, 0, 0b00010100, 0,
0, 0, 0, 0,
0, 0, 0b00110100]);
let c = BitVec::from_bytes(&[ // 88 bits
0, 0, 0, 0,
0, 0, 0, 0b00110100,
0, 0, 0b00110100]);
assert!(a.xor(&b));
assert_eq!(a,c);
}
#[test]
fn test_big_xnor() {
let mut a = BitVec::from_bytes(&[ // 88 bits
0, 0, 0b00010100, 0,
0, 0, 0, 0b00110100,
0, 0, 0]);
let b = BitVec::from_bytes(&[ // 88 bits
0, 0, 0b00010100, 0,
0, 0, 0, 0,
0, 0, 0b00110100]);
let c = BitVec::from_bytes(&[ // 88 bits
!0, !0, !0, !0,
!0, !0, !0, !0b00110100,
!0, !0, !0b00110100]);
assert!(a.xnor(&b));
assert_eq!(a,c);
}
#[test]
fn test_small_clear() {
let mut b = BitVec::from_elem(14, true);
assert!(!b.none() && b.all());
b.clear();
assert!(b.none() && !b.all());
}
#[test]
fn test_big_clear() {
let mut b = BitVec::from_elem(140, true);
assert!(!b.none() && b.all());
b.clear();
assert!(b.none() && !b.all());
}
#[test]
fn test_bit_vec_lt() {
let mut a = BitVec::from_elem(5, false);
let mut b = BitVec::from_elem(5, false);
assert!(!(a < b) && !(b < a));
b.set(2, true);
assert!(a < b);
a.set(3, true);
assert!(a < b);
a.set(2, true);
assert!(!(a < b) && b < a);
b.set(0, true);
assert!(a < b);
}
#[test]
fn test_ord() {
let mut a = BitVec::from_elem(5, false);
let mut b = BitVec::from_elem(5, false);
assert!(a <= b && a >= b);
a.set(1, true);
assert!(a > b && a >= b);
assert!(b < a && b <= a);
b.set(1, true);
b.set(2, true);
assert!(b > a && b >= a);
assert!(a < b && a <= b);
}
#[test]
fn test_small_bit_vec_tests() {
let v = BitVec::from_bytes(&[0]);
assert!(!v.all());
assert!(!v.any());
assert!(v.none());
let v = BitVec::from_bytes(&[0b00010100]);
assert!(!v.all());
assert!(v.any());
assert!(!v.none());
let v = BitVec::from_bytes(&[0xFF]);
assert!(v.all());
assert!(v.any());
assert!(!v.none());
}
#[test]
fn test_big_bit_vec_tests() {
let v = BitVec::from_bytes(&[ // 88 bits
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0]);
assert!(!v.all());
assert!(!v.any());
assert!(v.none());
let v = BitVec::from_bytes(&[ // 88 bits
0, 0, 0b00010100, 0,
0, 0, 0, 0b00110100,
0, 0, 0]);
assert!(!v.all());
assert!(v.any());
assert!(!v.none());
let v = BitVec::from_bytes(&[ // 88 bits
0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF]);
assert!(v.all());
assert!(v.any());
assert!(!v.none());
}
#[test]
fn test_bit_vec_push_pop() {
let mut s = BitVec::from_elem(5 * U32_BITS - 2, false);
assert_eq!(s.len(), 5 * U32_BITS - 2);
assert_eq!(s[5 * U32_BITS - 3], false);
s.push(true);
s.push(true);
assert_eq!(s[5 * U32_BITS - 2], true);
assert_eq!(s[5 * U32_BITS - 1], true);
// Here the internal vector will need to be extended
s.push(false);
assert_eq!(s[5 * U32_BITS], false);
s.push(false);
assert_eq!(s[5 * U32_BITS + 1], false);
assert_eq!(s.len(), 5 * U32_BITS + 2);
// Pop it all off
assert_eq!(s.pop(), Some(false));
assert_eq!(s.pop(), Some(false));
assert_eq!(s.pop(), Some(true));
assert_eq!(s.pop(), Some(true));
assert_eq!(s.len(), 5 * U32_BITS - 2);
}
#[test]
fn test_bit_vec_truncate() {
let mut s = BitVec::from_elem(5 * U32_BITS, true);
assert_eq!(s, BitVec::from_elem(5 * U32_BITS, true));
assert_eq!(s.len(), 5 * U32_BITS);
s.truncate(4 * U32_BITS);
assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
assert_eq!(s.len(), 4 * U32_BITS);
// Truncating to a size > s.len() should be a noop
s.truncate(5 * U32_BITS);
assert_eq!(s, BitVec::from_elem(4 * U32_BITS, true));
assert_eq!(s.len(), 4 * U32_BITS);
s.truncate(3 * U32_BITS - 10);
assert_eq!(s, BitVec::from_elem(3 * U32_BITS - 10, true));
assert_eq!(s.len(), 3 * U32_BITS - 10);
s.truncate(0);
assert_eq!(s, BitVec::from_elem(0, true));
assert_eq!(s.len(), 0);
}
#[test]
fn test_bit_vec_reserve() {
let mut s = BitVec::from_elem(5 * U32_BITS, true);
// Check capacity
assert!(s.capacity() >= 5 * U32_BITS);
s.reserve(2 * U32_BITS);
assert!(s.capacity() >= 7 * U32_BITS);
s.reserve(7 * U32_BITS);
assert!(s.capacity() >= 12 * U32_BITS);
s.reserve_exact(7 * U32_BITS);
assert!(s.capacity() >= 12 * U32_BITS);
s.reserve(7 * U32_BITS + 1);
assert!(s.capacity() >= 12 * U32_BITS + 1);
// Check that length hasn't changed
assert_eq!(s.len(), 5 * U32_BITS);
s.push(true);
s.push(false);
s.push(true);
assert_eq!(s[5 * U32_BITS - 1], true);
assert_eq!(s[5 * U32_BITS - 0], true);
assert_eq!(s[5 * U32_BITS + 1], false);
assert_eq!(s[5 * U32_BITS + 2], true);
}
#[test]
fn test_bit_vec_grow() {
let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
bit_vec.grow(32, true);
assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
0xFF, 0xFF, 0xFF, 0xFF]));
bit_vec.grow(64, false);
assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
bit_vec.grow(16, true);
assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
}
#[test]
fn test_bit_vec_extend() {
let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
bit_vec.extend(ext.iter());
assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
0b01001001, 0b10010010, 0b10111101]));
}
#[test]
fn test_bit_vec_append() {
// Append to BitVec that holds a multiple of U32_BITS bits
let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011]);
let mut b = BitVec::new();
b.push(false);
b.push(true);
b.push(true);
a.append(&mut b);
assert_eq!(a.len(), 35);
assert_eq!(b.len(), 0);
assert!(b.capacity() >= 3);
assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
false, false, false, true, false, false, true, false,
true, false, false, true, false, false, true, false,
false, false, true, true, false, false, true, true,
false, true, true]));
// Append to arbitrary BitVec
let mut a = BitVec::new();
a.push(true);
a.push(false);
let mut b = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
a.append(&mut b);
assert_eq!(a.len(), 42);
assert_eq!(b.len(), 0);
assert!(b.capacity() >= 40);
assert!(a.eq_vec(&[true, false, true, false, true, false, false, false,
false, false, false, false, false, true, false, false,
true, false, true, false, false, true, false, false,
true, false, false, false, true, true, false, false,
true, true, true, false, false, true, false, true,
false, true]));
// Append to empty BitVec
let mut a = BitVec::new();
let mut b = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
a.append(&mut b);
assert_eq!(a.len(), 40);
assert_eq!(b.len(), 0);
assert!(b.capacity() >= 40);
assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
false, false, false, true, false, false, true, false,
true, false, false, true, false, false, true, false,
false, false, true, true, false, false, true, true,
true, false, false, true, false, true, false, true]));
// Append empty BitVec
let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b10010101]);
let mut b = BitVec::new();
a.append(&mut b);
assert_eq!(a.len(), 40);
assert_eq!(b.len(), 0);
assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
false, false, false, true, false, false, true, false,
true, false, false, true, false, false, true, false,
false, false, true, true, false, false, true, true,
true, false, false, true, false, true, false, true]));
}
#[test]
fn test_bit_vec_split_off() {
// Split at 0
let mut a = BitVec::new();
a.push(true);
a.push(false);
a.push(false);
a.push(true);
let b = a.split_off(0);
assert_eq!(a.len(), 0);
assert_eq!(b.len(), 4);
assert!(b.eq_vec(&[true, false, false, true]));
// Split at last bit
a.truncate(0);
a.push(true);
a.push(false);
a.push(false);
a.push(true);
let b = a.split_off(4);
assert_eq!(a.len(), 4);
assert_eq!(b.len(), 0);
assert!(a.eq_vec(&[true, false, false, true]));
// Split at block boundary
let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011, 0b11110011]);
let b = a.split_off(32);
assert_eq!(a.len(), 32);
assert_eq!(b.len(), 8);
assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
false, false, false, true, false, false, true, false,
true, false, false, true, false, false, true, false,
false, false, true, true, false, false, true, true]));
assert!(b.eq_vec(&[true, true, true, true, false, false, true, true]));
// Don't split at block boundary
let mut a = BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010, 0b00110011,
0b01101011, 0b10101101]);
let b = a.split_off(13);
assert_eq!(a.len(), 13);
assert_eq!(b.len(), 35);
assert!(a.eq_vec(&[true, false, true, false, false, false, false, false,
false, false, false, true, false]));
assert!(b.eq_vec(&[false, true, false, true, false, false, true, false,
false, true, false, false, false, true, true, false,
false, true, true, false, true, true, false, true,
false, true, true, true, false, true, false, true,
true, false, true]));
}
#[test]
fn test_into_iter() {
let bools = vec![true, false, true, true];
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
let mut iter = bit_vec.into_iter();
assert_eq!(Some(true), iter.next());
assert_eq!(Some(false), iter.next());
assert_eq!(Some(true), iter.next());
assert_eq!(Some(true), iter.next());
assert_eq!(None, iter.next());
assert_eq!(None, iter.next());
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
let mut iter = bit_vec.into_iter();
assert_eq!(Some(true), iter.next_back());
assert_eq!(Some(true), iter.next_back());
assert_eq!(Some(false), iter.next_back());
assert_eq!(Some(true), iter.next_back());
assert_eq!(None, iter.next_back());
assert_eq!(None, iter.next_back());
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
let mut iter = bit_vec.into_iter();
assert_eq!(Some(true), iter.next_back());
assert_eq!(Some(true), iter.next());
assert_eq!(Some(false), iter.next());
assert_eq!(Some(true), iter.next_back());
assert_eq!(None, iter.next());
assert_eq!(None, iter.next_back());
}
#[test]
fn iter() {
let b = BitVec::with_capacity(10);
let _a: Iter = b.iter();
}
#[cfg(feature="serde")]
#[test]
fn test_serialization() {
let bit_vec: BitVec = BitVec::new();
let serialized = serde_json::to_string(&bit_vec).unwrap();
let unserialized: BitVec = serde_json::from_str(&serialized).unwrap();
assert_eq!(bit_vec, unserialized);
let bools = vec![true, false, true, true];
let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
let serialized = serde_json::to_string(&bit_vec).unwrap();
let unserialized = serde_json::from_str(&serialized).unwrap();
assert_eq!(bit_vec, unserialized);
}
#[test]
fn test_bit_vec_unaligned_small_append() {
let mut a = BitVec::from_elem(8, false);
a.set(7, true);
let mut b = BitVec::from_elem(16, false);
b.set(14, true);
let mut c = BitVec::from_elem(8, false);
c.set(6, true);
c.set(7, true);
a.append(&mut b);
a.append(&mut c);
assert_eq!(&[01, 00, 02, 03][..], &*a.to_bytes());
}
#[test]
fn test_bit_vec_unaligned_large_append() {
let mut a = BitVec::from_elem(48, false);
a.set(47, true);
let mut b = BitVec::from_elem(48, false);
b.set(46, true);
let mut c = BitVec::from_elem(48, false);
c.set(46, true);
c.set(47, true);
a.append(&mut b);
a.append(&mut c);
assert_eq!(&[0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
0x00, 0x00, 0x00, 0x00, 0x00, 0x03][..], &*a.to_bytes());
}
#[test]
fn test_bit_vec_append_aligned_to_unaligned() {
let mut a = BitVec::from_elem(2, true);
let mut b = BitVec::from_elem(32, false);
let mut c = BitVec::from_elem(8, true);
a.append(&mut b);
a.append(&mut c);
assert_eq!(&[0xc0, 0x00, 0x00, 0x00, 0x3f, 0xc0][..], &*a.to_bytes());
}
}
Test module covering bit-counts straddling the B::bits boundary (0, 1, 2, 10, 31, 32, 33, 100), bitwise operators (and/or/xor/nand/nor/xnor) at small and large sizes, push/pop, truncate/grow/reserve, append (aligned and unaligned), split_off (at block boundary and within block), iterator forward/backward, and round-trip serde when the feature is enabled. The suite is example-based with no random or property tests; see FINDING-2. Justifies has-unit-tests, datastructure-impl-tested, algorithm-impl-tested.