new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".travis.yml":"e684c9479b485343f5b932e8f9de7ac046accfb4c1e3c534e6e0fb9e0c8d919b","Cargo.toml":"a30078c3db5bccf6a567ad9ae78a6258d18b990034eda7e4ce8f4b3041ff2aa9","LICENSE-APACHE":"8173d5c29b4f956d532781d2b86e4e30f83e6b7878dce18c919451d6ba707c90","LICENSE-MIT":"c9a75f18b9ab2927829a208fc6aa2cf4e63b8420887ba29cdb265d6619ae82d5","README.md":"d3a2993cd15ac201b30c86fe69f2bb692b386875eace571715007637d7ca7abf","deploy-docs.sh":"7b66111b124c1c7e59cb84cf110d98b5cb783bd35a676e970d9b3035e55f7dfd","src/lib.rs":"7276279f7008dd633d0bb90cc0ff73de170b89d69644fb21c35728c94e913c4d"},"package":"d9bf6104718e80d7b26a68fdbacff3481cfc05df670821affc7e9cbc1884400c"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/.travis.yml
@@ -0,0 +1,18 @@
+language: rust
+sudo: false
+matrix:
+ include:
+ - rust: stable
+ - rust: nightly
+ env: FEATURES="--features nightly"
+script:
+ - cargo build $FEATURES
+ - cargo test $FEATURES
+ - cargo doc --no-deps
+after_success: |
+ [ "$TRAVIS_RUST_VERSION" = nightly ] &&
+ [ "$TRAVIS_BRANCH" = master ] &&
+ [ "$TRAVIS_PULL_REQUEST" = false ] &&
+ bash deploy-docs.sh
+notifications:
+ webhooks: http://huon.me:54857/travis
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/Cargo.toml
@@ -0,0 +1,20 @@
+[package]
+name = "bit-set"
+version = "0.4.0"
+authors = ["Alexis Beingessner <a.beingessner@gmail.com>"]
+license = "MIT/Apache-2.0"
+description = "A set of bits"
+repository = "https://github.com/contain-rs/bit-set"
+homepage = "https://github.com/contain-rs/bit-set"
+documentation = "https://contain-rs.github.io/bit-set/bit_set"
+keywords = ["data-structures", "bitset"]
+readme = "README.md"
+
+[dev-dependencies]
+rand = "0.3"
+
+[dependencies]
+bit-vec = "0.4"
+
+[features]
+nightly = []
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/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.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2016 The Rust Project Developers
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/README.md
@@ -0,0 +1,6 @@
+A Set of bits.
+
+Documentation is available at https://contain-rs.github.io/bit-set/bit_set.
+
+[](https://travis-ci.org/contain-rs/bit-set)
+[](https://crates.io/crates/bit-set)
new file mode 100755
--- /dev/null
+++ b/third_party/rust/bit-set/deploy-docs.sh
@@ -0,0 +1,20 @@
+#!/bin/bash
+
+set -o errexit -o nounset
+
+rev=$(git rev-parse --short HEAD)
+
+cd target/doc
+
+git init
+git config user.email 'FlashCat@users.noreply.github.com'
+git config user.name 'FlashCat'
+git remote add upstream "https://${GH_TOKEN}@github.com/${TRAVIS_REPO_SLUG}.git"
+git fetch upstream gh-pages
+git reset upstream/gh-pages
+
+touch .
+
+git add -A .
+git commit -m "rebuild pages at ${rev}"
+git push -q upstream HEAD:gh-pages
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-set/src/lib.rs
@@ -0,0 +1,1436 @@
+// Copyright 2012-2014 The Rust Project Developers. 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.
+
+//! An implementation of a set using a bit vector as an underlying
+//! representation for holding unsigned numerical elements.
+//!
+//! It should also be noted that the amount of storage necessary for holding a
+//! set of objects is proportional to the maximum of the objects when viewed
+//! as a `usize`.
+//!
+//! # Examples
+//!
+//! ```
+//! use bit_set::BitSet;
+//!
+//! // It's a regular set
+//! let mut s = BitSet::new();
+//! s.insert(0);
+//! s.insert(3);
+//! s.insert(7);
+//!
+//! s.remove(7);
+//!
+//! if !s.contains(7) {
+//! println!("There is no 7");
+//! }
+//!
+//! // Can initialize from a `BitVec`
+//! let other = BitSet::from_bytes(&[0b11010000]);
+//!
+//! s.union_with(&other);
+//!
+//! // Print 0, 1, 3 in some order
+//! for x in s.iter() {
+//! println!("{}", x);
+//! }
+//!
+//! // Can convert back to a `BitVec`
+//! let bv = s.into_bit_vec();
+//! assert!(bv[3]);
+//! ```
+
+#![cfg_attr(all(test, feature = "nightly"), feature(test))]
+#[cfg(all(test, feature = "nightly"))] extern crate test;
+#[cfg(all(test, feature = "nightly"))] extern crate rand;
+extern crate bit_vec;
+
+use bit_vec::{BitVec, Blocks, BitBlock};
+use std::cmp::Ordering;
+use std::cmp;
+use std::fmt;
+use std::hash;
+use std::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};
+
+type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
+
+/// Computes how many blocks are needed to store that many bits
+fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
+ // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
+ // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
+ // one too many. So we need to check if that's the case. We can do that by computing if
+ // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
+ // superior modulo operator on a power of two to this.
+ //
+ // Note that we can technically avoid this branch with the expression
+ // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
+ if bits % B::bits() == 0 {
+ bits / B::bits()
+ } else {
+ bits / B::bits() + 1
+ }
+}
+
+// Take two BitVec's, and return iterators of their words, where the shorter one
+// has been padded with 0's
+fn match_words<'a, 'b, B: BitBlock>(a: &'a BitVec<B>, b: &'b BitVec<B>)
+ -> (MatchWords<'a, B>, MatchWords<'b, B>)
+{
+ let a_len = a.storage().len();
+ let b_len = b.storage().len();
+
+ // have to uselessly pretend to pad the longer one for type matching
+ if a_len < b_len {
+ (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)),
+ b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)))
+ } else {
+ (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
+ b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)))
+ }
+}
+
+pub struct BitSet<B = u32> {
+ bit_vec: BitVec<B>,
+}
+
+impl<B: BitBlock> Clone for BitSet<B> {
+ fn clone(&self) -> Self {
+ BitSet {
+ bit_vec: self.bit_vec.clone(),
+ }
+ }
+
+ fn clone_from(&mut self, other: &Self) {
+ self.bit_vec.clone_from(&other.bit_vec);
+ }
+}
+
+impl<B: BitBlock> Default for BitSet<B> {
+ #[inline]
+ fn default() -> Self { BitSet { bit_vec: Default::default() } }
+}
+
+impl<B: BitBlock> FromIterator<usize> for BitSet<B> {
+ fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
+ let mut ret = Self::default();
+ ret.extend(iter);
+ ret
+ }
+}
+
+impl<B: BitBlock> Extend<usize> for BitSet<B> {
+ #[inline]
+ fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
+ for i in iter {
+ self.insert(i);
+ }
+ }
+}
+
+impl<B: BitBlock> PartialOrd for BitSet<B> {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ self.iter().partial_cmp(other)
+ }
+}
+
+impl<B: BitBlock> Ord for BitSet<B> {
+ #[inline]
+ fn cmp(&self, other: &Self) -> Ordering {
+ self.iter().cmp(other)
+ }
+}
+
+impl<B: BitBlock> PartialEq for BitSet<B> {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ self.iter().eq(other)
+ }
+}
+
+impl<B: BitBlock> Eq for BitSet<B> {}
+
+impl BitSet<u32> {
+ /// Creates a new empty `BitSet`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// ```
+ #[inline]
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ /// Creates a new `BitSet` with initially no contents, able to
+ /// hold `nbits` elements without resizing.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::with_capacity(100);
+ /// assert!(s.capacity() >= 100);
+ /// ```
+ #[inline]
+ pub fn with_capacity(nbits: usize) -> Self {
+ let bit_vec = BitVec::from_elem(nbits, false);
+ Self::from_bit_vec(bit_vec)
+ }
+
+ /// Creates a new `BitSet` from the given bit vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// extern crate bit_vec;
+ /// extern crate bit_set;
+ ///
+ /// fn main() {
+ /// use bit_vec::BitVec;
+ /// use bit_set::BitSet;
+ ///
+ /// let bv = BitVec::from_bytes(&[0b01100000]);
+ /// let s = BitSet::from_bit_vec(bv);
+ ///
+ /// // Print 1, 2 in arbitrary order
+ /// for x in s.iter() {
+ /// println!("{}", x);
+ /// }
+ /// }
+ /// ```
+ #[inline]
+ pub fn from_bit_vec(bit_vec: BitVec) -> Self {
+ BitSet { bit_vec: bit_vec }
+ }
+
+ pub fn from_bytes(bytes: &[u8]) -> Self {
+ BitSet { bit_vec: BitVec::from_bytes(bytes) }
+ }
+}
+
+impl<B: BitBlock> BitSet<B> {
+
+ /// Returns the capacity in bits for this bit vector. Inserting any
+ /// element less than this amount will not trigger a resizing.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::with_capacity(100);
+ /// assert!(s.capacity() >= 100);
+ /// ```
+ #[inline]
+ pub fn capacity(&self) -> usize {
+ self.bit_vec.capacity()
+ }
+
+ /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
+ /// of `BitSet` this means reallocations will not occur as long as all inserted elements
+ /// are less than `len`.
+ ///
+ /// The collection may reserve more space to avoid frequent reallocations.
+ ///
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// s.reserve_len(10);
+ /// assert!(s.capacity() >= 10);
+ /// ```
+ pub fn reserve_len(&mut self, len: usize) {
+ let cur_len = self.bit_vec.len();
+ if len >= cur_len {
+ self.bit_vec.reserve(len - cur_len);
+ }
+ }
+
+ /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
+ /// In the case of `BitSet` this means reallocations will not occur as long as all inserted
+ /// elements are less than `len`.
+ ///
+ /// Note that the allocator may give the collection more space than it requests. Therefore
+ /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future
+ /// insertions are expected.
+ ///
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// s.reserve_len_exact(10);
+ /// assert!(s.capacity() >= 10);
+ /// ```
+ pub fn reserve_len_exact(&mut self, len: usize) {
+ let cur_len = self.bit_vec.len();
+ if len >= cur_len {
+ self.bit_vec.reserve_exact(len - cur_len);
+ }
+ }
+
+ /// Consumes this set to return the underlying bit vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// s.insert(0);
+ /// s.insert(3);
+ ///
+ /// let bv = s.into_bit_vec();
+ /// assert!(bv[0]);
+ /// assert!(bv[3]);
+ /// ```
+ #[inline]
+ pub fn into_bit_vec(self) -> BitVec<B> {
+ self.bit_vec
+ }
+
+ /// Returns a reference to the underlying bit vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// s.insert(0);
+ ///
+ /// let bv = s.get_ref();
+ /// assert_eq!(bv[0], true);
+ /// ```
+ #[inline]
+ pub fn get_ref(&self) -> &BitVec<B> {
+ &self.bit_vec
+ }
+
+ #[inline]
+ fn other_op<F>(&mut self, other: &Self, mut f: F) where F: FnMut(B, B) -> B {
+ // Unwrap BitVecs
+ let self_bit_vec = &mut self.bit_vec;
+ let other_bit_vec = &other.bit_vec;
+
+ let self_len = self_bit_vec.len();
+ let other_len = other_bit_vec.len();
+
+ // Expand the vector if necessary
+ if self_len < other_len {
+ self_bit_vec.grow(other_len - self_len, false);
+ }
+
+ // virtually pad other with 0's for equal lengths
+ let other_words = {
+ let (_, result) = match_words(self_bit_vec, other_bit_vec);
+ result
+ };
+
+ // Apply values found in other
+ for (i, w) in other_words {
+ let old = self_bit_vec.storage()[i];
+ let new = f(old, w);
+ unsafe {
+ self_bit_vec.storage_mut()[i] = new;
+ }
+ }
+ }
+
+ /// Truncates the underlying vector to the least length required.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut s = BitSet::new();
+ /// s.insert(32183231);
+ /// s.remove(32183231);
+ ///
+ /// // Internal storage will probably be bigger than necessary
+ /// println!("old capacity: {}", s.capacity());
+ ///
+ /// // Now should be smaller
+ /// s.shrink_to_fit();
+ /// println!("new capacity: {}", s.capacity());
+ /// ```
+ #[inline]
+ pub fn shrink_to_fit(&mut self) {
+ let bit_vec = &mut self.bit_vec;
+ // Obtain original length
+ let old_len = bit_vec.storage().len();
+ // Obtain coarse trailing zero length
+ let n = bit_vec.storage().iter().rev().take_while(|&&n| n == B::zero()).count();
+ // Truncate
+ let trunc_len = cmp::max(old_len - n, 1);
+ unsafe {
+ bit_vec.storage_mut().truncate(trunc_len);
+ bit_vec.set_len(trunc_len * B::bits());
+ }
+ }
+
+ /// Iterator over each usize stored in the `BitSet`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let s = BitSet::from_bytes(&[0b01001010]);
+ ///
+ /// // Print 1, 4, 6 in arbitrary order
+ /// for x in s.iter() {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[inline]
+ pub fn iter(&self) -> Iter<B> {
+ Iter(BlockIter::from_blocks(self.bit_vec.blocks()))
+ }
+
+ /// Iterator over each usize stored in `self` union `other`.
+ /// See [union_with](#method.union_with) for an efficient in-place version.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = BitSet::from_bytes(&[0b01101000]);
+ /// let b = BitSet::from_bytes(&[0b10100000]);
+ ///
+ /// // Print 0, 1, 2, 4 in arbitrary order
+ /// for x in a.union(&b) {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[inline]
+ pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> {
+ fn or<B: BitBlock>(w1: B, w2: B) -> B { w1 | w2 }
+
+ Union(BlockIter::from_blocks(TwoBitPositions {
+ set: self.bit_vec.blocks(),
+ other: other.bit_vec.blocks(),
+ merge: or,
+ }))
+ }
+
+ /// Iterator over each usize stored in `self` intersect `other`.
+ /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = BitSet::from_bytes(&[0b01101000]);
+ /// let b = BitSet::from_bytes(&[0b10100000]);
+ ///
+ /// // Print 2
+ /// for x in a.intersection(&b) {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[inline]
+ pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> {
+ fn bitand<B: BitBlock>(w1: B, w2: B) -> B { w1 & w2 }
+ let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
+
+ Intersection(BlockIter::from_blocks(TwoBitPositions {
+ set: self.bit_vec.blocks(),
+ other: other.bit_vec.blocks(),
+ merge: bitand,
+ }).take(min))
+ }
+
+ /// Iterator over each usize stored in the `self` setminus `other`.
+ /// See [difference_with](#method.difference_with) for an efficient in-place version.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = BitSet::from_bytes(&[0b01101000]);
+ /// let b = BitSet::from_bytes(&[0b10100000]);
+ ///
+ /// // Print 1, 4 in arbitrary order
+ /// for x in a.difference(&b) {
+ /// println!("{}", x);
+ /// }
+ ///
+ /// // Note that difference is not symmetric,
+ /// // and `b - a` means something else.
+ /// // This prints 0
+ /// for x in b.difference(&a) {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[inline]
+ pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> {
+ fn diff<B: BitBlock>(w1: B, w2: B) -> B { w1 & !w2 }
+
+ Difference(BlockIter::from_blocks(TwoBitPositions {
+ set: self.bit_vec.blocks(),
+ other: other.bit_vec.blocks(),
+ merge: diff,
+ }))
+ }
+
+ /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
+ /// See [symmetric_difference_with](#method.symmetric_difference_with) for
+ /// an efficient in-place version.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = BitSet::from_bytes(&[0b01101000]);
+ /// let b = BitSet::from_bytes(&[0b10100000]);
+ ///
+ /// // Print 0, 1, 4 in arbitrary order
+ /// for x in a.symmetric_difference(&b) {
+ /// println!("{}", x);
+ /// }
+ /// ```
+ #[inline]
+ pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> {
+ fn bitxor<B: BitBlock>(w1: B, w2: B) -> B { w1 ^ w2 }
+
+ SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
+ set: self.bit_vec.blocks(),
+ other: other.bit_vec.blocks(),
+ merge: bitxor,
+ }))
+ }
+
+ /// Unions in-place with the specified other bit vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = 0b01101000;
+ /// let b = 0b10100000;
+ /// let res = 0b11101000;
+ ///
+ /// let mut a = BitSet::from_bytes(&[a]);
+ /// let b = BitSet::from_bytes(&[b]);
+ /// let res = BitSet::from_bytes(&[res]);
+ ///
+ /// a.union_with(&b);
+ /// assert_eq!(a, res);
+ /// ```
+ #[inline]
+ pub fn union_with(&mut self, other: &Self) {
+ self.other_op(other, |w1, w2| w1 | w2);
+ }
+
+ /// Intersects in-place with the specified other bit vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = 0b01101000;
+ /// let b = 0b10100000;
+ /// let res = 0b00100000;
+ ///
+ /// let mut a = BitSet::from_bytes(&[a]);
+ /// let b = BitSet::from_bytes(&[b]);
+ /// let res = BitSet::from_bytes(&[res]);
+ ///
+ /// a.intersect_with(&b);
+ /// assert_eq!(a, res);
+ /// ```
+ #[inline]
+ pub fn intersect_with(&mut self, other: &Self) {
+ self.other_op(other, |w1, w2| w1 & w2);
+ }
+
+ /// Makes this bit vector the difference with the specified other bit vector
+ /// in-place.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = 0b01101000;
+ /// let b = 0b10100000;
+ /// let a_b = 0b01001000; // a - b
+ /// let b_a = 0b10000000; // b - a
+ ///
+ /// let mut bva = BitSet::from_bytes(&[a]);
+ /// let bvb = BitSet::from_bytes(&[b]);
+ /// let bva_b = BitSet::from_bytes(&[a_b]);
+ /// let bvb_a = BitSet::from_bytes(&[b_a]);
+ ///
+ /// bva.difference_with(&bvb);
+ /// assert_eq!(bva, bva_b);
+ ///
+ /// let bva = BitSet::from_bytes(&[a]);
+ /// let mut bvb = BitSet::from_bytes(&[b]);
+ ///
+ /// bvb.difference_with(&bva);
+ /// assert_eq!(bvb, bvb_a);
+ /// ```
+ #[inline]
+ pub fn difference_with(&mut self, other: &Self) {
+ self.other_op(other, |w1, w2| w1 & !w2);
+ }
+
+ /// Makes this bit vector the symmetric difference with the specified other
+ /// bit vector in-place.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let a = 0b01101000;
+ /// let b = 0b10100000;
+ /// let res = 0b11001000;
+ ///
+ /// let mut a = BitSet::from_bytes(&[a]);
+ /// let b = BitSet::from_bytes(&[b]);
+ /// let res = BitSet::from_bytes(&[res]);
+ ///
+ /// a.symmetric_difference_with(&b);
+ /// assert_eq!(a, res);
+ /// ```
+ #[inline]
+ pub fn symmetric_difference_with(&mut self, other: &Self) {
+ self.other_op(other, |w1, w2| w1 ^ w2);
+ }
+
+/*
+ /// Moves all elements from `other` into `Self`, leaving `other` empty.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut a = BitSet::new();
+ /// a.insert(2);
+ /// a.insert(6);
+ ///
+ /// let mut b = BitSet::new();
+ /// b.insert(1);
+ /// b.insert(3);
+ /// b.insert(6);
+ ///
+ /// a.append(&mut b);
+ ///
+ /// assert_eq!(a.len(), 4);
+ /// assert_eq!(b.len(), 0);
+ /// assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
+ /// ```
+ pub fn append(&mut self, other: &mut Self) {
+ self.union_with(other);
+ other.clear();
+ }
+
+ /// Splits the `BitSet` into two at the given key including the key.
+ /// Retains the first part in-place while returning the second part.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_set::BitSet;
+ ///
+ /// let mut a = BitSet::new();
+ /// a.insert(2);
+ /// a.insert(6);
+ /// a.insert(1);
+ /// a.insert(3);
+ ///
+ /// let b = a.split_off(3);
+ ///
+ /// assert_eq!(a.len(), 2);
+ /// assert_eq!(b.len(), 2);
+ /// assert_eq!(a, BitSet::from_bytes(&[0b01100000]));
+ /// assert_eq!(b, BitSet::from_bytes(&[0b00010010]));
+ /// ```
+ pub fn split_off(&mut self, at: usize) -> Self {
+ let mut other = BitSet::new();
+
+ if at == 0 {
+ swap(self, &mut other);
+ return other;
+ } else if at >= self.bit_vec.len() {
+ return other;
+ }
+
+ // Calculate block and bit at which to split
+ let w = at / BITS;
+ let b = at % BITS;
+
+ // Pad `other` with `w` zero blocks,
+ // append `self`'s blocks in the range from `w` to the end to `other`
+ other.bit_vec.storage_mut().extend(repeat(0u32).take(w)
+ .chain(self.bit_vec.storage()[w..].iter().cloned()));
+ other.bit_vec.nbits = self.bit_vec.nbits;
+
+ if b > 0 {
+ other.bit_vec.storage_mut()[w] &= !0 << b;
+ }
+
+ // Sets `bit_vec.len()` and fixes the last block as well
+ self.bit_vec.truncate(at);
+
+ other
+ }
+*/
+
+ /// Returns the number of set bits in this set.
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones() as usize)
+ }
+
+ /// Returns whether there are no bits set in this set
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.bit_vec.none()
+ }
+
+ /// Clears all bits in this set
+ #[inline]
+ pub fn clear(&mut self) {
+ self.bit_vec.clear();
+ }
+
+ /// Returns `true` if this set contains the specified integer.
+ #[inline]
+ pub fn contains(&self, value: usize) -> bool {
+ let bit_vec = &self.bit_vec;
+ value < bit_vec.len() && bit_vec[value]
+ }
+
+ /// Returns `true` if the set has no elements in common with `other`.
+ /// This is equivalent to checking for an empty intersection.
+ #[inline]
+ pub fn is_disjoint(&self, other: &Self) -> bool {
+ self.intersection(other).next().is_none()
+ }
+
+ /// Returns `true` if the set is a subset of another.
+ #[inline]
+ pub fn is_subset(&self, other: &Self) -> bool {
+ let self_bit_vec = &self.bit_vec;
+ let other_bit_vec = &other.bit_vec;
+ let other_blocks = blocks_for_bits::<B>(other_bit_vec.len());
+
+ // Check that `self` intersect `other` is self
+ self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
+ // Make sure if `self` has any more blocks than `other`, they're all 0
+ self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
+ }
+
+ /// Returns `true` if the set is a superset of another.
+ #[inline]
+ pub fn is_superset(&self, other: &Self) -> bool {
+ other.is_subset(self)
+ }
+
+ /// Adds a value to the set. Returns `true` if the value was not already
+ /// present in the set.
+ pub fn insert(&mut self, value: usize) -> bool {
+ if self.contains(value) {
+ return false;
+ }
+
+ // Ensure we have enough space to hold the new element
+ let len = self.bit_vec.len();
+ if value >= len {
+ self.bit_vec.grow(value - len + 1, false)
+ }
+
+ self.bit_vec.set(value, true);
+ return true;
+ }
+
+ /// Removes a value from the set. Returns `true` if the value was
+ /// present in the set.
+ pub fn remove(&mut self, value: usize) -> bool {
+ if !self.contains(value) {
+ return false;
+ }
+
+ self.bit_vec.set(value, false);
+
+ return true;
+ }
+}
+
+impl<B: BitBlock> fmt::Debug for BitSet<B> {
+ fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+ fmt.debug_set().entries(self).finish()
+ }
+}
+
+impl<B: BitBlock> hash::Hash for BitSet<B> {
+ fn hash<H: hash::Hasher>(&self, state: &mut H) {
+ for pos in self {
+ pos.hash(state);
+ }
+ }
+}
+
+#[derive(Clone)]
+struct BlockIter<T, B> {
+ head: B,
+ head_offset: usize,
+ tail: T,
+}
+
+impl<T, B: BitBlock> BlockIter<T, B> where T: Iterator<Item=B> {
+ fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
+ let h = blocks.next().unwrap_or(B::zero());
+ BlockIter {tail: blocks, head: h, head_offset: 0}
+ }
+}
+
+/// An iterator combining two `BitSet` iterators.
+#[derive(Clone)]
+struct TwoBitPositions<'a, B: 'a> {
+ set: Blocks<'a, B>,
+ other: Blocks<'a, B>,
+ merge: fn(B, B) -> B,
+}
+
+/// An iterator for `BitSet`.
+#[derive(Clone)]
+pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
+#[derive(Clone)]
+pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
+#[derive(Clone)]
+pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>);
+#[derive(Clone)]
+pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
+#[derive(Clone)]
+pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
+
+impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B> where T: Iterator<Item=B> {
+ type Item = usize;
+
+ fn next(&mut self) -> Option<usize> {
+ while self.head == B::zero() {
+ match self.tail.next() {
+ Some(w) => self.head = w,
+ None => return None
+ }
+ self.head_offset += B::bits();
+ }
+
+ // from the current block, isolate the
+ // LSB and subtract 1, producing k:
+ // a block with a number of set bits
+ // equal to the index of the LSB
+ let k = (self.head & (!self.head + B::one())) - B::one();
+ // update block, removing the LSB
+ self.head = self.head & (self.head - B::one());
+ // return offset + (index of LSB)
+ Some(self.head_offset + (B::count_ones(k) as usize))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ match self.tail.size_hint() {
+ (_, Some(h)) => (0, Some(1 + h * B::bits())),
+ _ => (0, None)
+ }
+ }
+}
+
+impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> {
+ type Item = B;
+
+ fn next(&mut self) -> Option<B> {
+ match (self.set.next(), self.other.next()) {
+ (Some(a), Some(b)) => Some((self.merge)(a, b)),
+ (Some(a), None) => Some((self.merge)(a, B::zero())),
+ (None, Some(b)) => Some((self.merge)(B::zero(), b)),
+ _ => return None
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let (a, au) = self.set.size_hint();
+ let (b, bu) = self.other.size_hint();
+
+ let upper = match (au, bu) {
+ (Some(au), Some(bu)) => Some(cmp::max(au, bu)),
+ _ => None
+ };
+
+ (cmp::max(a, b), upper)
+ }
+}
+
+impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
+ type Item = usize;
+
+ #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
+}
+
+impl<'a, B: BitBlock> Iterator for Union<'a, B> {
+ type Item = usize;
+
+ #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
+}
+
+impl<'a, B: BitBlock> Iterator for Intersection<'a, B> {
+ type Item = usize;
+
+ #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
+}
+
+impl<'a, B: BitBlock> Iterator for Difference<'a, B> {
+ type Item = usize;
+
+ #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
+}
+
+impl<'a, B: BitBlock> Iterator for SymmetricDifference<'a, B> {
+ type Item = usize;
+
+ #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
+}
+
+impl<'a, B: BitBlock> IntoIterator for &'a BitSet<B> {
+ type Item = usize;
+ type IntoIter = Iter<'a, B>;
+
+ fn into_iter(self) -> Iter<'a, B> {
+ self.iter()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use std::cmp::Ordering::{Equal, Greater, Less};
+ use super::BitSet;
+ use bit_vec::BitVec;
+
+ #[test]
+ fn test_bit_set_show() {
+ let mut s = BitSet::new();
+ s.insert(1);
+ s.insert(10);
+ s.insert(50);
+ s.insert(2);
+ assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
+ }
+
+ #[test]
+ fn test_bit_set_from_usizes() {
+ let usizes = vec![0, 2, 2, 3];
+ let a: BitSet = usizes.into_iter().collect();
+ let mut b = BitSet::new();
+ b.insert(0);
+ b.insert(2);
+ b.insert(3);
+ assert_eq!(a, b);
+ }
+
+ #[test]
+ fn test_bit_set_iterator() {
+ let usizes = vec![0, 2, 2, 3];
+ let bit_vec: BitSet = usizes.into_iter().collect();
+
+ let idxs: Vec<_> = bit_vec.iter().collect();
+ assert_eq!(idxs, [0, 2, 3]);
+
+ let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
+ let real: Vec<_> = (0..10000/2).map(|x| x*2).collect();
+
+ let idxs: Vec<_> = long.iter().collect();
+ assert_eq!(idxs, real);
+ }
+
+ #[test]
+ fn test_bit_set_frombit_vec_init() {
+ let bools = [true, false];
+ let lengths = [10, 64, 100];
+ for &b in &bools {
+ for &l in &lengths {
+ let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
+ assert_eq!(bitset.contains(1), b);
+ assert_eq!(bitset.contains((l-1)), b);
+ assert!(!bitset.contains(l));
+ }
+ }
+ }
+
+ #[test]
+ fn test_bit_vec_masking() {
+ let b = BitVec::from_elem(140, true);
+ let mut bs = BitSet::from_bit_vec(b);
+ assert!(bs.contains(139));
+ assert!(!bs.contains(140));
+ assert!(bs.insert(150));
+ assert!(!bs.contains(140));
+ assert!(!bs.contains(149));
+ assert!(bs.contains(150));
+ assert!(!bs.contains(151));
+ }
+
+ #[test]
+ fn test_bit_set_basic() {
+ let mut b = BitSet::new();
+ assert!(b.insert(3));
+ assert!(!b.insert(3));
+ assert!(b.contains(3));
+ assert!(b.insert(4));
+ assert!(!b.insert(4));
+ assert!(b.contains(3));
+ assert!(b.insert(400));
+ assert!(!b.insert(400));
+ assert!(b.contains(400));
+ assert_eq!(b.len(), 3);
+ }
+
+ #[test]
+ fn test_bit_set_intersection() {
+ let mut a = BitSet::new();
+ let mut b = BitSet::new();
+
+ assert!(a.insert(11));
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(77));
+ assert!(a.insert(103));
+ assert!(a.insert(5));
+
+ assert!(b.insert(2));
+ assert!(b.insert(11));
+ assert!(b.insert(77));
+ assert!(b.insert(5));
+ assert!(b.insert(3));
+
+ let expected = [3, 5, 11, 77];
+ let actual: Vec<_> = a.intersection(&b).collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn test_bit_set_difference() {
+ let mut a = BitSet::new();
+ let mut b = BitSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(5));
+ assert!(a.insert(200));
+ assert!(a.insert(500));
+
+ assert!(b.insert(3));
+ assert!(b.insert(200));
+
+ let expected = [1, 5, 500];
+ let actual: Vec<_> = a.difference(&b).collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn test_bit_set_symmetric_difference() {
+ let mut a = BitSet::new();
+ let mut b = BitSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(5));
+ assert!(a.insert(9));
+ assert!(a.insert(11));
+
+ assert!(b.insert(3));
+ assert!(b.insert(9));
+ assert!(b.insert(14));
+ assert!(b.insert(220));
+
+ let expected = [1, 5, 11, 14, 220];
+ let actual: Vec<_> = a.symmetric_difference(&b).collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn test_bit_set_union() {
+ let mut a = BitSet::new();
+ let mut b = BitSet::new();
+ assert!(a.insert(1));
+ assert!(a.insert(3));
+ assert!(a.insert(5));
+ assert!(a.insert(9));
+ assert!(a.insert(11));
+ assert!(a.insert(160));
+ assert!(a.insert(19));
+ assert!(a.insert(24));
+ assert!(a.insert(200));
+
+ assert!(b.insert(1));
+ assert!(b.insert(5));
+ assert!(b.insert(9));
+ assert!(b.insert(13));
+ assert!(b.insert(19));
+
+ let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
+ let actual: Vec<_> = a.union(&b).collect();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ fn test_bit_set_subset() {
+ let mut set1 = BitSet::new();
+ let mut set2 = BitSet::new();
+
+ assert!(set1.is_subset(&set2)); // {} {}
+ set2.insert(100);
+ assert!(set1.is_subset(&set2)); // {} { 1 }
+ set2.insert(200);
+ assert!(set1.is_subset(&set2)); // {} { 1, 2 }
+ set1.insert(200);
+ assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 }
+ set1.insert(300);
+ assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 }
+ set2.insert(300);
+ assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 }
+ set2.insert(400);
+ assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 }
+ set2.remove(100);
+ assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 }
+ set2.remove(300);
+ assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 }
+ set1.remove(300);
+ assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 }
+ }
+
+ #[test]
+ fn test_bit_set_is_disjoint() {
+ let a = BitSet::from_bytes(&[0b10100010]);
+ let b = BitSet::from_bytes(&[0b01000000]);
+ let c = BitSet::new();
+ let d = BitSet::from_bytes(&[0b00110000]);
+
+ assert!(!a.is_disjoint(&d));
+ assert!(!d.is_disjoint(&a));
+
+ assert!(a.is_disjoint(&b));
+ assert!(a.is_disjoint(&c));
+ assert!(b.is_disjoint(&a));
+ assert!(b.is_disjoint(&c));
+ assert!(c.is_disjoint(&a));
+ assert!(c.is_disjoint(&b));
+ }
+
+ #[test]
+ fn test_bit_set_union_with() {
+ //a should grow to include larger elements
+ let mut a = BitSet::new();
+ a.insert(0);
+ let mut b = BitSet::new();
+ b.insert(5);
+ let expected = BitSet::from_bytes(&[0b10000100]);
+ a.union_with(&b);
+ assert_eq!(a, expected);
+
+ // Standard
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let mut b = BitSet::from_bytes(&[0b01100010]);
+ let c = a.clone();
+ a.union_with(&b);
+ b.union_with(&c);
+ assert_eq!(a.len(), 4);
+ assert_eq!(b.len(), 4);
+ }
+
+ #[test]
+ fn test_bit_set_intersect_with() {
+ // Explicitly 0'ed bits
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let mut b = BitSet::from_bytes(&[0b00000000]);
+ let c = a.clone();
+ a.intersect_with(&b);
+ b.intersect_with(&c);
+ assert!(a.is_empty());
+ assert!(b.is_empty());
+
+ // Uninitialized bits should behave like 0's
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let mut b = BitSet::new();
+ let c = a.clone();
+ a.intersect_with(&b);
+ b.intersect_with(&c);
+ assert!(a.is_empty());
+ assert!(b.is_empty());
+
+ // Standard
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let mut b = BitSet::from_bytes(&[0b01100010]);
+ let c = a.clone();
+ a.intersect_with(&b);
+ b.intersect_with(&c);
+ assert_eq!(a.len(), 2);
+ assert_eq!(b.len(), 2);
+ }
+
+ #[test]
+ fn test_bit_set_difference_with() {
+ // Explicitly 0'ed bits
+ let mut a = BitSet::from_bytes(&[0b00000000]);
+ let b = BitSet::from_bytes(&[0b10100010]);
+ a.difference_with(&b);
+ assert!(a.is_empty());
+
+ // Uninitialized bits should behave like 0's
+ let mut a = BitSet::new();
+ let b = BitSet::from_bytes(&[0b11111111]);
+ a.difference_with(&b);
+ assert!(a.is_empty());
+
+ // Standard
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let mut b = BitSet::from_bytes(&[0b01100010]);
+ let c = a.clone();
+ a.difference_with(&b);
+ b.difference_with(&c);
+ assert_eq!(a.len(), 1);
+ assert_eq!(b.len(), 1);
+ }
+
+ #[test]
+ fn test_bit_set_symmetric_difference_with() {
+ //a should grow to include larger elements
+ let mut a = BitSet::new();
+ a.insert(0);
+ a.insert(1);
+ let mut b = BitSet::new();
+ b.insert(1);
+ b.insert(5);
+ let expected = BitSet::from_bytes(&[0b10000100]);
+ a.symmetric_difference_with(&b);
+ assert_eq!(a, expected);
+
+ let mut a = BitSet::from_bytes(&[0b10100010]);
+ let b = BitSet::new();
+ let c = a.clone();
+ a.symmetric_difference_with(&b);
+ assert_eq!(a, c);
+
+ // Standard
+ let mut a = BitSet::from_bytes(&[0b11100010]);
+ let mut b = BitSet::from_bytes(&[0b01101010]);
+ let c = a.clone();
+ a.symmetric_difference_with(&b);
+ b.symmetric_difference_with(&c);
+ assert_eq!(a.len(), 2);
+ assert_eq!(b.len(), 2);
+ }
+
+ #[test]
+ fn test_bit_set_eq() {
+ let a = BitSet::from_bytes(&[0b10100010]);
+ let b = BitSet::from_bytes(&[0b00000000]);
+ let c = BitSet::new();
+
+ assert!(a == a);
+ assert!(a != b);
+ assert!(a != c);
+ assert!(b == b);
+ assert!(b == c);
+ assert!(c == c);
+ }
+
+ #[test]
+ fn test_bit_set_cmp() {
+ let a = BitSet::from_bytes(&[0b10100010]);
+ let b = BitSet::from_bytes(&[0b00000000]);
+ let c = BitSet::new();
+
+ assert_eq!(a.cmp(&b), Greater);
+ assert_eq!(a.cmp(&c), Greater);
+ assert_eq!(b.cmp(&a), Less);
+ assert_eq!(b.cmp(&c), Equal);
+ assert_eq!(c.cmp(&a), Less);
+ assert_eq!(c.cmp(&b), Equal);
+ }
+
+ #[test]
+ fn test_bit_vec_remove() {
+ let mut a = BitSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.remove(1));
+
+ assert!(a.insert(100));
+ assert!(a.remove(100));
+
+ assert!(a.insert(1000));
+ assert!(a.remove(1000));
+ a.shrink_to_fit();
+ }
+
+ #[test]
+ fn test_bit_vec_clone() {
+ let mut a = BitSet::new();
+
+ assert!(a.insert(1));
+ assert!(a.insert(100));
+ assert!(a.insert(1000));
+
+ let mut b = a.clone();
+
+ assert!(a == b);
+
+ assert!(b.remove(1));
+ assert!(a.contains(1));
+
+ assert!(a.remove(1000));
+ assert!(b.contains(1000));
+ }
+
+/*
+ #[test]
+ fn test_bit_set_append() {
+ let mut a = BitSet::new();
+ a.insert(2);
+ a.insert(6);
+
+ let mut b = BitSet::new();
+ b.insert(1);
+ b.insert(3);
+ b.insert(6);
+
+ a.append(&mut b);
+
+ assert_eq!(a.len(), 4);
+ assert_eq!(b.len(), 0);
+ assert!(b.capacity() >= 6);
+
+ assert_eq!(a, BitSet::from_bytes(&[0b01110010]));
+ }
+
+ #[test]
+ fn test_bit_set_split_off() {
+ // Split at 0
+ let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01101011, 0b10101101]);
+
+ let b = a.split_off(0);
+
+ assert_eq!(a.len(), 0);
+ assert_eq!(b.len(), 21);
+
+ assert_eq!(b, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01101011, 0b10101101]);
+
+ // Split behind last element
+ let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01101011, 0b10101101]);
+
+ let b = a.split_off(50);
+
+ assert_eq!(a.len(), 21);
+ assert_eq!(b.len(), 0);
+
+ assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01101011, 0b10101101]));
+
+ // Split at arbitrary element
+ let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01101011, 0b10101101]);
+
+ let b = a.split_off(34);
+
+ assert_eq!(a.len(), 12);
+ assert_eq!(b.len(), 9);
+
+ assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
+ 0b00110011, 0b01000000]));
+ assert_eq!(b, BitSet::from_bytes(&[0, 0, 0, 0,
+ 0b00101011, 0b10101101]));
+ }
+*/
+}
+
+#[cfg(all(test, feature = "nightly"))]
+mod bench {
+ use super::BitSet;
+ use bit_vec::BitVec;
+ use rand::{Rng, thread_rng, ThreadRng};
+
+ use test::{Bencher, black_box};
+
+ const BENCH_BITS: usize = 1 << 14;
+ const BITS: usize = 32;
+
+ fn rng() -> ThreadRng {
+ thread_rng()
+ }
+
+ #[bench]
+ fn bench_bit_vecset_small(b: &mut Bencher) {
+ let mut r = rng();
+ let mut bit_vec = BitSet::new();
+ b.iter(|| {
+ for _ in 0..100 {
+ bit_vec.insert((r.next_u32() as usize) % BITS);
+ }
+ black_box(&bit_vec);
+ });
+ }
+
+ #[bench]
+ fn bench_bit_vecset_big(b: &mut Bencher) {
+ let mut r = rng();
+ let mut bit_vec = BitSet::new();
+ b.iter(|| {
+ for _ in 0..100 {
+ bit_vec.insert((r.next_u32() as usize) % BENCH_BITS);
+ }
+ black_box(&bit_vec);
+ });
+ }
+
+ #[bench]
+ fn bench_bit_vecset_iter(b: &mut Bencher) {
+ let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS,
+ |idx| {idx % 3 == 0}));
+ b.iter(|| {
+ let mut sum = 0;
+ for idx in &bit_vec {
+ sum += idx as usize;
+ }
+ sum
+ })
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".travis.yml":"26dbdd3f33aeefa6216804c025626b8e2bef5c05103410faa5e6e93f20331cbe","Cargo.toml":"6376bd862fc4827a77190427180ccf86cda76907bf3bd935601840cd03ab48da","LICENSE-APACHE":"8173d5c29b4f956d532781d2b86e4e30f83e6b7878dce18c919451d6ba707c90","LICENSE-MIT":"7b63ecd5f1902af1b63729947373683c32745c16a10e8e6292e2e2dcd7e90ae0","README.md":"2a42423b7acd5af0ee7f47dcc430b267cfe4661ced77131af2d6e97e6a15377a","benches/extern.rs":"30152d15cc55493d06396baf9eebb90c8f32b314f0dc77398ac8a121bd5ff917","crusader.sh":"e656dcb62d5122a64d55f837992e63cfd3beee37cf74c5ab6ff178a3c7ef943e","deploy-docs.sh":"7b66111b124c1c7e59cb84cf110d98b5cb783bd35a676e970d9b3035e55f7dfd","src/bench.rs":"a24345464fdbc70b5b877d13fa1b9da809ba4917e592d5de69f01b8b1340e8bb","src/lib.rs":"b784632ce3f6a16314d1d759310f297941fb5577192ba48a10ae3c6893dd5e24"},"package":"02b4ff8b16e6076c3e14220b39fbc1fabb6737522281a388998046859400895f"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/.travis.yml
@@ -0,0 +1,19 @@
+language: rust
+sudo: false
+matrix:
+ include:
+ - rust: stable
+ - rust: nightly
+ env: FEATURES="--features nightly"
+script:
+ - cargo build $FEATURES
+ - cargo test $FEATURES
+ - cargo doc --no-deps
+ - bash crusader.sh
+after_success: |
+ [ "$TRAVIS_RUST_VERSION" = nightly ] &&
+ [ "$TRAVIS_BRANCH" = master ] &&
+ [ "$TRAVIS_PULL_REQUEST" = false ] &&
+ bash deploy-docs.sh
+notifications:
+ webhooks: http://huon.me:54857/travis
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/Cargo.toml
@@ -0,0 +1,17 @@
+[package]
+name = "bit-vec"
+version = "0.4.4"
+authors = ["Alexis Beingessner <a.beingessner@gmail.com>"]
+license = "MIT/Apache-2.0"
+description = "A vector of bits"
+repository = "https://github.com/contain-rs/bit-vec"
+homepage = "https://github.com/contain-rs/bit-vec"
+documentation = "https://contain-rs.github.io/bit-vec/bit_vec"
+keywords = ["data-structures", "bitvec", "bitmask", "bitmap", "bit"]
+readme = "README.md"
+
+[dev-dependencies]
+rand = "0.3.15"
+
+[features]
+nightly = []
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/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.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2015 The Rust Project Developers
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/README.md
@@ -0,0 +1,6 @@
+A Vec of bits.
+
+Documentation is available at https://contain-rs.github.io/bit-vec/bit_vec.
+
+[](https://travis-ci.org/contain-rs/bit-vec)
+[](https://crates.io/crates/bit-vec)
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/benches/extern.rs
@@ -0,0 +1,22 @@
+// Copyright 2012-2014 The Rust Project Developers. 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.
+
+#![cfg(all(test, feature = "nightly"))]
+
+#![feature(test)]
+
+extern crate test;
+extern crate rand;
+extern crate bit_vec;
+
+pub use bit_vec::BitVec;
+
+#[path = "../src/bench.rs"]
+mod bench;
new file mode 100755
--- /dev/null
+++ b/third_party/rust/bit-vec/crusader.sh
@@ -0,0 +1,11 @@
+#!/bin/bash
+
+git clone https://github.com/brson/cargo-crusader
+cd cargo-crusader
+cargo build --release
+export PATH=$PATH:`pwd`/target/release/
+cd ../
+
+cargo crusader
+
+exit
new file mode 100755
--- /dev/null
+++ b/third_party/rust/bit-vec/deploy-docs.sh
@@ -0,0 +1,20 @@
+#!/bin/bash
+
+set -o errexit -o nounset
+
+rev=$(git rev-parse --short HEAD)
+
+cd target/doc
+
+git init
+git config user.email 'FlashCat@users.noreply.github.com'
+git config user.name 'FlashCat'
+git remote add upstream "https://${GH_TOKEN}@github.com/${TRAVIS_REPO_SLUG}.git"
+git fetch upstream gh-pages
+git reset upstream/gh-pages
+
+touch .
+
+git add -A .
+git commit -m "rebuild pages at ${rev}"
+git push -q upstream HEAD:gh-pages
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/src/bench.rs
@@ -0,0 +1,116 @@
+// Copyright 2012-2014 The Rust Project Developers. 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::BitVec;
+use rand::{Rng, weak_rng, XorShiftRng};
+
+use test::{Bencher, black_box};
+
+const BENCH_BITS : usize = 1 << 14;
+const U32_BITS: usize = 32;
+
+fn rng() -> XorShiftRng {
+ weak_rng()
+}
+
+#[bench]
+fn bench_usize_small(b: &mut Bencher) {
+ let mut r = rng();
+ let mut bit_vec = 0 as usize;
+ b.iter(|| {
+ for _ in 0..100 {
+ bit_vec |= 1 << ((r.next_u32() as usize) % U32_BITS);
+ }
+ black_box(&bit_vec);
+ });
+}
+
+#[bench]
+fn bench_bit_set_big_fixed(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_u32() as usize) % BENCH_BITS, true);
+ }
+ black_box(&bit_vec);
+ });
+}
+
+#[bench]
+fn bench_bit_set_big_variable(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_u32() as usize) % BENCH_BITS, r.gen());
+ }
+ black_box(&bit_vec);
+ });
+}
+
+#[bench]
+fn bench_bit_set_small(b: &mut Bencher) {
+ let mut r = rng();
+ let mut bit_vec = BitVec::from_elem(U32_BITS, false);
+ b.iter(|| {
+ for _ in 0..100 {
+ bit_vec.set((r.next_u32() as usize) % U32_BITS, true);
+ }
+ black_box(&bit_vec);
+ });
+}
+
+#[bench]
+fn bench_bit_vec_big_union(b: &mut Bencher) {
+ let mut b1 = BitVec::from_elem(BENCH_BITS, false);
+ let b2 = BitVec::from_elem(BENCH_BITS, false);
+ b.iter(|| {
+ b1.union(&b2)
+ })
+}
+
+#[bench]
+fn bench_bit_vec_small_iter(b: &mut Bencher) {
+ let bit_vec = BitVec::from_elem(U32_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(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_from_elem(b: &mut Bencher) {
+ let cap = black_box(BENCH_BITS);
+ let bit = black_box(true);
+ b.iter(|| {
+ // create a BitVec and popcount it
+ BitVec::from_elem(cap, bit).blocks()
+ .fold(0, |acc, b| acc + b.count_ones())
+ });
+ b.bytes = cap as u64 / 8;
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/bit-vec/src/lib.rs
@@ -0,0 +1,2111 @@
+// Copyright 2012-2014 The Rust Project Developers. 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.
+
+// FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for
+// maintenance), they should be in separate files/modules, with BitSet only
+// using BitVec's public API. This will be hard for performance though, because
+// `BitVec` will not want to leak its internal representation while its internal
+// representation as `u32`s must be assumed for best performance.
+
+// FIXME(tbu-): `BitVec`'s methods shouldn't be `union`, `intersection`, but
+// rather `or` and `and`.
+
+// (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`.
+
+//! Collections implemented with bit vectors.
+//!
+//! # Examples
+//!
+//! This is a simple example of the [Sieve of Eratosthenes][sieve]
+//! which calculates prime numbers up to a given limit.
+//!
+//! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
+//!
+//! ```
+//! use bit_vec::BitVec;
+//!
+//! let max_prime = 10000;
+//!
+//! // Store the primes as a BitVec
+//! let primes = {
+//! // Assume all numbers are prime to begin, and then we
+//! // cross off non-primes progressively
+//! let mut bv = BitVec::from_elem(max_prime, true);
+//!
+//! // Neither 0 nor 1 are prime
+//! bv.set(0, false);
+//! bv.set(1, false);
+//!
+//! for i in 2.. 1 + (max_prime as f64).sqrt() as usize {
+//! // if i is a prime
+//! if bv[i] {
+//! // Mark all multiples of i as non-prime (any multiples below i * i
+//! // will have been marked as non-prime previously)
+//! for j in i.. {
+//! if i * j >= max_prime {
+//! break;
+//! }
+//! bv.set(i * j, false)
+//! }
+//! }
+//! }
+//! bv
+//! };
+//!
+//! // Simple primality tests below our max bound
+//! let print_primes = 20;
+//! print!("The primes below {} are: ", print_primes);
+//! for x in 0..print_primes {
+//! if primes.get(x).unwrap_or(false) {
+//! print!("{} ", x);
+//! }
+//! }
+//! println!("");
+//!
+//! let num_primes = primes.iter().filter(|x| *x).count();
+//! println!("There are {} primes below {}", num_primes, max_prime);
+//! assert_eq!(num_primes, 1_229);
+//! ```
+
+#![cfg_attr(all(test, feature = "nightly"), feature(test))]
+#[cfg(all(test, feature = "nightly"))] extern crate test;
+#[cfg(all(test, feature = "nightly"))] extern crate rand;
+
+use std::cmp::Ordering;
+use std::cmp;
+use std::fmt;
+use std::hash;
+use std::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat};
+use std::iter::FromIterator;
+use std::slice;
+use std::{u8, usize};
+
+type MutBlocks<'a, B> = slice::IterMut<'a, B>;
+type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
+
+use std::ops::*;
+
+/// Abstracts over a pile of bits (basically unsigned primitives)
+pub trait BitBlock:
+ Copy +
+ Add<Self, Output=Self> +
+ Sub<Self, Output=Self> +
+ Shl<usize, Output=Self> +
+ Shr<usize, Output=Self> +
+ Not<Output=Self> +
+ BitAnd<Self, Output=Self> +
+ BitOr<Self, Output=Self> +
+ BitXor<Self, Output=Self> +
+ Rem<Self, Output=Self> +
+ Eq +
+ Ord +
+ hash::Hash +
+{
+ /// How many bits it has
+ fn bits() -> usize;
+ /// How many bytes it has
+ #[inline]
+ fn bytes() -> usize { Self::bits() / 8 }
+ /// Convert a byte into this type (lowest-order bits set)
+ fn from_byte(byte: u8) -> Self;
+ /// Count the number of 1's in the bitwise repr
+ fn count_ones(self) -> usize;
+ /// Get `0`
+ fn zero() -> Self;
+ /// Get `1`
+ fn one() -> Self;
+}
+
+macro_rules! bit_block_impl {
+ ($(($t: ty, $size: expr)),*) => ($(
+ impl BitBlock for $t {
+ #[inline]
+ fn bits() -> usize { $size }
+ #[inline]
+ fn from_byte(byte: u8) -> Self { byte as $t }
+ #[inline]
+ fn count_ones(self) -> usize { self.count_ones() as usize }
+ #[inline]
+ fn one() -> Self { 1 }
+ #[inline]
+ fn zero() -> Self { 0 }
+ }
+ )*)
+}
+
+bit_block_impl!{
+ (u8, 8),
+ (u16, 16),
+ (u32, 32),
+ (u64, 64),
+ (usize, std::mem::size_of::<usize>() * 8)
+}
+
+
+fn reverse_bits(byte: u8) -> u8 {
+ let mut result = 0;
+ for i in 0..u8::bits() {
+ result = result | ((byte >> i) & 1) << (u8::bits() - 1 - i);
+ }
+ result
+}
+
+static TRUE: bool = true;
+static FALSE: bool = false;
+
+/// The bitvector type.
+///
+/// # Examples
+///
+/// ```
+/// use bit_vec::BitVec;
+///
+/// let mut bv = BitVec::from_elem(10, false);
+///
+/// // insert all primes less than 10
+/// bv.set(2, true);
+/// bv.set(3, true);
+/// bv.set(5, true);
+/// bv.set(7, true);
+/// println!("{:?}", bv);
+/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
+///
+/// // flip all values in bitvector, producing non-primes less than 10
+/// bv.negate();
+/// println!("{:?}", bv);
+/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
+///
+/// // reset bitvector to empty
+/// bv.clear();
+/// println!("{:?}", bv);
+/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
+/// ```
+pub struct BitVec<B=u32> {
+ /// Internal representation of the bit vector
+ storage: Vec<B>,
+ /// The number of valid bits in the internal representation
+ nbits: usize
+}
+
+// FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
+impl<B: BitBlock> Index<usize> for BitVec<B> {
+ type Output = bool;
+
+ #[inline]
+ fn index(&self, i: usize) -> &bool {
+ if self.get(i).expect("index out of bounds") {
+ &TRUE
+ } else {
+ &FALSE
+ }
+ }
+}
+
+/// Computes how many blocks are needed to store that many bits
+fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
+ // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
+ // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
+ // one too many. So we need to check if that's the case. We can do that by computing if
+ // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
+ // superior modulo operator on a power of two to this.
+ //
+ // Note that we can technically avoid this branch with the expression
+ // `(nbits + U32_BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
+ if bits % B::bits() == 0 {
+ bits / B::bits()
+ } else {
+ bits / B::bits() + 1
+ }
+}
+
+/// 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())
+}
+
+type B = u32;
+
+impl BitVec<u32> {
+
+ /// Creates an empty `BitVec`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ /// let mut bv = BitVec::new();
+ /// ```
+ #[inline]
+ pub fn new() -> Self {
+ Default::default()
+ }
+
+ /// Creates a `BitVec` that holds `nbits` elements, setting each element
+ /// to `bit`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(10, false);
+ /// assert_eq!(bv.len(), 10);
+ /// for x in bv.iter() {
+ /// assert_eq!(x, false);
+ /// }
+ /// ```
+ #[inline]
+ pub fn from_elem(nbits: usize, bit: bool) -> Self {
+ let nblocks = blocks_for_bits::<B>(nbits);
+ let mut bit_vec = BitVec {
+ storage: vec![if bit { !B::zero() } else { B::zero() }; nblocks],
+ nbits: nbits
+ };
+ bit_vec.fix_last_block();
+ bit_vec
+ }
+
+ /// Constructs a new, empty `BitVec` with the specified capacity.
+ ///
+ /// The bitvector will be able to hold at least `capacity` bits without
+ /// reallocating. If `capacity` is 0, it will not allocate.
+ ///
+ /// It is important to note that this function does not specify the
+ /// *length* of the returned bitvector, but only the *capacity*.
+ #[inline]
+ pub fn with_capacity(nbits: usize) -> Self {
+ BitVec {
+ storage: Vec::with_capacity(blocks_for_bits::<B>(nbits)),
+ nbits: 0,
+ }
+ }
+
+ /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
+ /// with the most significant bits of each byte coming first. Each
+ /// bit becomes `true` if equal to 1 or `false` if equal to 0.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]);
+ /// assert!(bv.eq_vec(&[true, false, true, false,
+ /// false, false, false, false,
+ /// false, false, false, true,
+ /// false, false, true, false]));
+ /// ```
+ 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 = 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 = last_word |
+ (B::from_byte(reverse_bits(byte)) << (i * 8));
+ }
+ bit_vec.storage.push(last_word);
+ }
+
+ bit_vec
+ }
+
+ /// Creates a `BitVec` of the specified length where the value at each index
+ /// is `f(index)`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 });
+ /// assert!(bv.eq_vec(&[true, false, true, false, true]));
+ /// ```
+ #[inline]
+ pub fn from_fn<F>(len: usize, mut f: F) -> Self
+ where F: FnMut(usize) -> bool
+ {
+ let mut bit_vec = BitVec::from_elem(len, false);
+ for i in 0..len {
+ bit_vec.set(i, f(i));
+ }
+ bit_vec
+ }
+}
+
+impl<B: BitBlock> BitVec<B> {
+ /// Applies the given operation to the blocks of self and other, and sets
+ /// self to be the result. This relies on the caller not to corrupt the
+ /// last word.
+ #[inline]
+ fn process<F>(&mut self, other: &BitVec<B>, mut op: F) -> bool
+ where F: FnMut(B, B) -> B {
+ assert_eq!(self.len(), other.len());
+ // This could theoretically be a `debug_assert!`.
+ assert_eq!(self.storage.len(), other.storage.len());
+ let mut changed_bits = B::zero();
+ for (a, b) in self.blocks_mut().zip(other.blocks()) {
+ let w = op(*a, b);
+ changed_bits = changed_bits | (*a ^ w);
+ *a = w;
+ }
+ changed_bits != B::zero()
+ }
+
+ /// Iterator over mutable refs to the underlying blocks of data.
+ #[inline]
+ fn blocks_mut(&mut self) -> MutBlocks<B> {
+ // (2)
+ self.storage.iter_mut()
+ }
+
+ /// Iterator over the underlying blocks of data
+ #[inline]
+ pub fn blocks(&self) -> Blocks<B> {
+ // (2)
+ Blocks{iter: self.storage.iter()}
+ }
+
+ /// Exposes the raw block storage of this BitVec
+ ///
+ /// Only really intended for BitSet.
+ #[inline]
+ pub fn storage(&self) -> &[B] {
+ &self.storage
+ }
+
+ /// 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
+ }
+
+ /// An operation might screw up the unused bits in the last block of the
+ /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
+ fn fix_last_block(&mut self) {
+ let extra_bits = self.len() % B::bits();
+ if extra_bits > 0 {
+ let mask = (B::one() << extra_bits) - B::one();
+ let storage_len = self.storage.len();
+ let block = &mut self.storage[storage_len - 1];
+ *block = *block & mask;
+ }
+ }
+
+
+ /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let bv = BitVec::from_bytes(&[0b01100000]);
+ /// assert_eq!(bv.get(0), Some(false));
+ /// assert_eq!(bv.get(1), Some(true));
+ /// assert_eq!(bv.get(100), None);
+ ///
+ /// // Can also use array indexing
+ /// assert_eq!(bv[1], true);
+ /// ```
+ #[inline]
+ pub fn get(&self, i: usize) -> Option<bool> {
+ if i >= self.nbits {
+ return None;
+ }
+ let w = i / B::bits();
+ let b = i % B::bits();
+ self.storage.get(w).map(|&block|
+ (block & (B::one() << b)) != B::zero()
+ )
+ }
+
+ /// Sets the value of a bit at an index `i`.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `i` is out of bounds.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(5, false);
+ /// bv.set(3, true);
+ /// assert_eq!(bv[3], true);
+ /// ```
+ #[inline]
+ pub fn set(&mut self, i: usize, x: bool) {
+ assert!(i < self.nbits, "index out of bounds: {:?} >= {:?}", i, self.nbits);
+ let w = i / B::bits();
+ let b = i % B::bits();
+ let flag = B::one() << b;
+ let val = if x { self.storage[w] | flag }
+ else { self.storage[w] & !flag };
+ self.storage[w] = val;
+ }
+
+ /// Sets all bits to 1.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let before = 0b01100000;
+ /// let after = 0b11111111;
+ ///
+ /// let mut bv = BitVec::from_bytes(&[before]);
+ /// bv.set_all();
+ /// assert_eq!(bv, BitVec::from_bytes(&[after]));
+ /// ```
+ #[inline]
+ pub fn set_all(&mut self) {
+ for w in &mut self.storage { *w = !B::zero(); }
+ self.fix_last_block();
+ }
+
+ /// Flips all bits.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let before = 0b01100000;
+ /// let after = 0b10011111;
+ ///
+ /// let mut bv = BitVec::from_bytes(&[before]);
+ /// bv.negate();
+ /// assert_eq!(bv, BitVec::from_bytes(&[after]));
+ /// ```
+ #[inline]
+ pub fn negate(&mut self) {
+ for w in &mut self.storage { *w = !*w; }
+ self.fix_last_block();
+ }
+
+ /// Calculates the union of two bitvectors. This acts like the bitwise `or`
+ /// function.
+ ///
+ /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
+ /// the same length. Returns `true` if `self` changed.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the bitvectors are of different lengths.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let a = 0b01100100;
+ /// let b = 0b01011010;
+ /// let res = 0b01111110;
+ ///
+ /// let mut a = BitVec::from_bytes(&[a]);
+ /// let b = BitVec::from_bytes(&[b]);
+ ///
+ /// assert!(a.union(&b));
+ /// assert_eq!(a, BitVec::from_bytes(&[res]));
+ /// ```
+ #[inline]
+ pub fn union(&mut self, other: &Self) -> bool {
+ self.process(other, |w1, w2| (w1 | w2))
+ }
+
+ /// Calculates the intersection of two bitvectors. This acts like the
+ /// bitwise `and` function.
+ ///
+ /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
+ /// must be the same length. Returns `true` if `self` changed.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the bitvectors are of different lengths.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let a = 0b01100100;
+ /// let b = 0b01011010;
+ /// let res = 0b01000000;
+ ///
+ /// let mut a = BitVec::from_bytes(&[a]);
+ /// let b = BitVec::from_bytes(&[b]);
+ ///
+ /// assert!(a.intersect(&b));
+ /// assert_eq!(a, BitVec::from_bytes(&[res]));
+ /// ```
+ #[inline]
+ pub fn intersect(&mut self, other: &Self) -> bool {
+ self.process(other, |w1, w2| (w1 & w2))
+ }
+
+ /// Calculates the difference between two bitvectors.
+ ///
+ /// Sets each element of `self` to the value of that element minus the
+ /// element of `other` at the same index. Both bitvectors must be the same
+ /// length. Returns `true` if `self` changed.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the bitvectors are of different length.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let a = 0b01100100;
+ /// let b = 0b01011010;
+ /// let a_b = 0b00100100; // a - b
+ /// let b_a = 0b00011010; // b - a
+ ///
+ /// let mut bva = BitVec::from_bytes(&[a]);
+ /// let bvb = BitVec::from_bytes(&[b]);
+ ///
+ /// assert!(bva.difference(&bvb));
+ /// assert_eq!(bva, BitVec::from_bytes(&[a_b]));
+ ///
+ /// let bva = BitVec::from_bytes(&[a]);
+ /// let mut bvb = BitVec::from_bytes(&[b]);
+ ///
+ /// assert!(bvb.difference(&bva));
+ /// assert_eq!(bvb, BitVec::from_bytes(&[b_a]));
+ /// ```
+ #[inline]
+ pub fn difference(&mut self, other: &Self) -> bool {
+ self.process(other, |w1, w2| (w1 & !w2))
+ }
+
+ /// Returns `true` if all bits are 1.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(5, true);
+ /// assert_eq!(bv.all(), true);
+ ///
+ /// bv.set(1, false);
+ /// assert_eq!(bv.all(), false);
+ /// ```
+ #[inline]
+ pub fn all(&self) -> bool {
+ let mut last_word = !B::zero();
+ // Check that every block but the last is all-ones...
+ self.blocks().all(|elem| {
+ let tmp = last_word;
+ last_word = elem;
+ tmp == !B::zero()
+ // and then check the last one has enough ones
+ }) && (last_word == mask_for_bits(self.nbits))
+ }
+
+ /// Returns an iterator over the elements of the vector in order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]);
+ /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
+ /// ```
+ #[inline]
+ pub fn iter(&self) -> Iter<B> {
+ Iter { bit_vec: self, range: 0..self.nbits }
+ }
+
+/*
+ /// Moves all bits from `other` into `Self`, leaving `other` empty.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # #![feature(collections, bit_vec_append_split_off)]
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut a = BitVec::from_bytes(&[0b10000000]);
+ /// let mut b = BitVec::from_bytes(&[0b01100001]);
+ ///
+ /// a.append(&mut b);
+ ///
+ /// assert_eq!(a.len(), 16);
+ /// assert_eq!(b.len(), 0);
+ /// assert!(a.eq_vec(&[true, false, false, false, false, false, false, false,
+ /// false, true, true, false, false, false, false, true]));
+ /// ```
+ pub fn append(&mut self, other: &mut Self) {
+ let b = self.len() % B::bits();
+
+ 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));
+ }
+ }
+ }
+
+ /// Splits the `BitVec` into two at the given bit,
+ /// retaining the first half in-place and returning the second one.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `at` is out of bounds.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # #![feature(collections, bit_vec_append_split_off)]
+ /// use bit_vec::BitVec;
+ /// let mut a = BitVec::new();
+ /// a.push(true);
+ /// a.push(false);
+ /// a.push(false);
+ /// a.push(true);
+ ///
+ /// let b = a.split_off(2);
+ ///
+ /// assert_eq!(a.len(), 2);
+ /// assert_eq!(b.len(), 2);
+ /// assert!(a.eq_vec(&[true, false]));
+ /// assert!(b.eq_vec(&[false, true]));
+ /// ```
+ pub fn split_off(&mut self, at: usize) -> Self {
+ assert!(at <= self.len(), "`at` out of bounds");
+
+ let mut other = BitVec::new();
+
+ if at == 0 {
+ 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
+ }
+*/
+
+ /// Returns `true` if all bits are 0.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(10, false);
+ /// assert_eq!(bv.none(), true);
+ ///
+ /// bv.set(3, true);
+ /// assert_eq!(bv.none(), false);
+ /// ```
+ #[inline]
+ pub fn none(&self) -> bool {
+ self.blocks().all(|w| w == B::zero())
+ }
+
+ /// Returns `true` if any bit is 1.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(10, false);
+ /// assert_eq!(bv.any(), false);
+ ///
+ /// bv.set(3, true);
+ /// assert_eq!(bv.any(), true);
+ /// ```
+ #[inline]
+ pub fn any(&self) -> bool {
+ !self.none()
+ }
+
+ /// Organises the bits into bytes, such that the first bit in the
+ /// `BitVec` becomes the high-order bit of the first byte. If the
+ /// size of the `BitVec` is not a multiple of eight then trailing bits
+ /// will be filled-in with `false`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// 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]);
+ /// ```
+ pub fn to_bytes(&self) -> Vec<u8> {
+ // Oh lord, we're mapping this to bytes bit-by-bit!
+ fn bit<B: BitBlock>(bit_vec: &BitVec<B>, byte: usize, bit: usize) -> u8 {
+ let offset = byte * 8 + bit;
+ if offset >= bit_vec.nbits {
+ 0
+ } else {
+ (bit_vec[offset] as u8) << (7 - bit)
+ }
+ }
+
+ let len = self.nbits / 8 +
+ if self.nbits % 8 == 0 { 0 } else { 1 };
+ (0..len).map(|i|
+ bit(self, i, 0) |
+ bit(self, i, 1) |
+ bit(self, i, 2) |
+ bit(self, i, 3) |
+ bit(self, i, 4) |
+ bit(self, i, 5) |
+ bit(self, i, 6) |
+ bit(self, i, 7)
+ ).collect()
+ }
+
+ /// Compares a `BitVec` to a slice of `bool`s.
+ /// Both the `BitVec` and slice must have the same length.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the `BitVec` and slice are of different length.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let bv = BitVec::from_bytes(&[0b10100000]);
+ ///
+ /// assert!(bv.eq_vec(&[true, false, true, false,
+ /// false, false, false, false]));
+ /// ```
+ #[inline]
+ pub fn eq_vec(&self, v: &[bool]) -> bool {
+ assert_eq!(self.nbits, v.len());
+ self.iter().zip(v.iter().cloned()).all(|(b1, b2)| b1 == b2)
+ }
+
+ /// Shortens a `BitVec`, dropping excess elements.
+ ///
+ /// If `len` is greater than the vector's current length, this has no
+ /// effect.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_bytes(&[0b01001011]);
+ /// bv.truncate(2);
+ /// assert!(bv.eq_vec(&[false, true]));
+ /// ```
+ #[inline]
+ pub fn truncate(&mut self, len: usize) {
+ if len < self.len() {
+ self.nbits = len;
+ // This fixes (2).
+ self.storage.truncate(blocks_for_bits::<B>(len));
+ self.fix_last_block();
+ }
+ }
+
+ /// Reserves capacity for at least `additional` more bits to be inserted in the given
+ /// `BitVec`. The collection may reserve more space to avoid frequent reallocations.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new capacity overflows `usize`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(3, false);
+ /// bv.reserve(10);
+ /// assert_eq!(bv.len(), 3);
+ /// assert!(bv.capacity() >= 13);
+ /// ```
+ #[inline]
+ pub fn reserve(&mut self, additional: usize) {
+ let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
+ let storage_len = self.storage.len();
+ if desired_cap > self.capacity() {
+ self.storage.reserve(blocks_for_bits::<B>(desired_cap) - storage_len);
+ }
+ }
+
+ /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
+ /// given `BitVec`. Does nothing if the capacity is already sufficient.
+ ///
+ /// Note that the allocator may give the collection more space than it requests. Therefore
+ /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
+ /// insertions are expected.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new capacity overflows `usize`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_elem(3, false);
+ /// bv.reserve(10);
+ /// assert_eq!(bv.len(), 3);
+ /// assert!(bv.capacity() >= 13);
+ /// ```
+ #[inline]
+ pub fn reserve_exact(&mut self, additional: usize) {
+ let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
+ let storage_len = self.storage.len();
+ if desired_cap > self.capacity() {
+ self.storage.reserve_exact(blocks_for_bits::<B>(desired_cap) - storage_len);
+ }
+ }
+
+ /// Returns the capacity in bits for this bit vector. Inserting any
+ /// element less than this amount will not trigger a resizing.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::new();
+ /// bv.reserve(10);
+ /// assert!(bv.capacity() >= 10);
+ /// ```
+ #[inline]
+ pub fn capacity(&self) -> usize {
+ self.storage.capacity().checked_mul(B::bits()).unwrap_or(usize::MAX)
+ }
+
+ /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the new len overflows a `usize`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_bytes(&[0b01001011]);
+ /// bv.grow(2, true);
+ /// assert_eq!(bv.len(), 10);
+ /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);
+ /// ```
+ pub fn grow(&mut self, n: usize, value: bool) {
+ // Note: we just bulk set all the bits in the last word in this fn in multiple places
+ // which is technically wrong if not all of these bits are to be used. However, at the end
+ // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
+
+ let new_nbits = self.nbits.checked_add(n).expect("capacity overflow");
+ let new_nblocks = blocks_for_bits::<B>(new_nbits);
+ let full_value = if value { !B::zero() } else { B::zero() };
+
+ // Correct the old tail word, setting or clearing formerly unused bits
+ let num_cur_blocks = blocks_for_bits::<B>(self.nbits);
+ if self.nbits % B::bits() > 0 {
+ let mask = mask_for_bits::<B>(self.nbits);
+ if value {
+ let block = &mut self.storage[num_cur_blocks - 1];
+ *block = *block | !mask;
+ } else {
+ // Extra bits are already zero by invariant.
+ }
+ }
+
+ // Fill in words after the old tail word
+ let stop_idx = cmp::min(self.storage.len(), new_nblocks);
+ for idx in num_cur_blocks..stop_idx {
+ self.storage[idx] = full_value;
+ }
+
+ // Allocate new words, if needed
+ if new_nblocks > self.storage.len() {
+ let to_add = new_nblocks - self.storage.len();
+ self.storage.extend(repeat(full_value).take(to_add));
+ }
+
+ // Adjust internal bit count
+ self.nbits = new_nbits;
+
+ self.fix_last_block();
+ }
+
+ /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::from_bytes(&[0b01001001]);
+ /// assert_eq!(bv.pop(), Some(true));
+ /// assert_eq!(bv.pop(), Some(false));
+ /// assert_eq!(bv.len(), 6);
+ /// ```
+ #[inline]
+ pub fn pop(&mut self) -> Option<bool> {
+ if self.is_empty() {
+ None
+ } else {
+ let i = self.nbits - 1;
+ let ret = self[i];
+ // (3)
+ self.set(i, false);
+ self.nbits = i;
+ if self.nbits % B::bits() == 0 {
+ // (2)
+ self.storage.pop();
+ }
+ Some(ret)
+ }
+ }
+
+ /// Pushes a `bool` onto the end.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use bit_vec::BitVec;
+ ///
+ /// let mut bv = BitVec::new();
+ /// bv.push(true);
+ /// bv.push(false);
+ /// assert!(bv.eq_vec(&[true, false]));
+ /// ```
+ #[inline]
+ pub fn push(&mut self, elem: bool) {
+ if self.nbits % B::bits() == 0 {
+ self.storage.push(B::zero());
+ }
+ let insert_pos = self.nbits;
+ self.nbits = self.nbits.checked_add(1).expect("Capacity overflow");
+ self.set(insert_pos, elem);
+ }
+
+ /// Returns the total number of bits in this vector
+ #[inline]
+ pub fn len(&self) -> usize { self.nbits }
+
+ /// 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;
+ }
+
+ /// Returns true if there are no bits in this vector
+ #[inline]
+ pub fn is_empty(&self) -> bool { self.len() == 0 }
+
+ /// Clears all bits in this vector.
+ #[inline]
+ pub fn clear(&mut self) {
+ for w in &mut self.storage { *w = B::zero(); }
+ }
+}
+
+impl<B: BitBlock> Default for BitVec<B> {
+ #[inline]
+ fn default() -> Self { BitVec { storage: Vec::new(), nbits: 0 } }
+}
+
+impl<B: BitBlock> FromIterator<bool> for BitVec<B> {
+ #[inline]
+ fn from_iter<I: IntoIterator<Item=bool>>(iter: I) -> Self {
+ let mut ret: Self = Default::default();
+ ret.extend(iter);
+ ret
+ }
+}
+
+impl<B: BitBlock> Extend<bool> for BitVec<B> {
+ #[inline]
+ fn extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I) {
+ let iterator = iterable.into_iter();
+ let (min, _) = iterator.size_hint();
+ self.reserve(min);
+ for element in iterator {
+ self.push(element)
+ }
+ }
+}
+
+impl<B: BitBlock> Clone for BitVec<B> {
+ #[inline]
+ fn clone(&self) -> Self {
+ BitVec { storage: self.storage.clone(), nbits: self.nbits }
+ }
+
+ #[inline]
+ fn clone_from(&mut self, source: &Self) {
+ self.nbits = source.nbits;
+ self.storage.clone_from(&source.storage);
+ }
+}
+
+impl<B: BitBlock> PartialOrd for BitVec<B> {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl<B: BitBlock> Ord for BitVec<B> {
+ #[inline]
+ fn cmp(&self, other: &Self) -> Ordering {
+ let mut a = self.iter();
+ let mut b = other.iter();
+ loop {
+ match (a.next(), b.next()) {
+ (Some(x), Some(y)) => match x.cmp(&y) {
+ Ordering::Equal => {}
+ otherwise => return otherwise,
+ },
+ (None, None) => return Ordering::Equal,
+ (None, _) => return Ordering::Less,
+ (_, None) => return Ordering::Greater,
+ }
+ }
+ }
+}
+
+impl<B: BitBlock> fmt::Debug for BitVec<B> {
+ fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+ for bit in self {
+ try!(write!(fmt, "{}", if bit { 1 } else { 0 }));
+ }
+ Ok(())
+ }
+}
+
+impl<B: BitBlock> hash::Hash for BitVec<B> {
+ #[inline]
+ fn hash<H: hash::Hasher>(&self, state: &mut H) {
+ self.nbits.hash(state);
+ for elem in self.blocks() {
+ elem.hash(state);
+ }
+ }
+}
+
+impl<B: BitBlock> cmp::PartialEq for BitVec<B> {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ if self.nbits != other.nbits {
+ return false;
+ }
+ self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2)
+ }
+}
+
+impl<B: BitBlock> cmp::Eq for BitVec<B> {}
+
+/// An iterator for `BitVec`.
+#[derive(Clone)]
+pub struct Iter<'a, B: 'a = u32> {
+ bit_vec: &'a BitVec<B>,
+ range: Range<usize>,
+}
+
+impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
+ type Item = bool;
+
+ #[inline]
+ fn next(&mut self) -> Option<bool> {
+ // NB: indexing is slow for extern crates when it has to go through &TRUE or &FALSE
+ // variables. get is more direct, and unwrap is fine since we're sure of the range.
+ self.range.next().map(|i| self.bit_vec.get(i).unwrap())
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.range.size_hint()
+ }
+}
+
+impl<'a, B: BitBlock> DoubleEndedIterator for Iter<'a, B> {
+ #[inline]
+ fn next_back(&mut self) -> Option<bool> {
+ self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
+ }
+}
+
+impl<'a, B: BitBlock> ExactSizeIterator for Iter<'a, B> {}
+
+
+impl<'a, B: BitBlock> IntoIterator for &'a BitVec<B> {
+ type Item = bool;
+ type IntoIter = Iter<'a, B>;
+
+ #[inline]
+ fn into_iter(self) -> Iter<'a, B> {
+ self.iter()
+ }
+}
+
+
+pub struct IntoIter<B=u32> {
+ bit_vec: BitVec<B>,
+ range: Range<usize>,
+}
+
+impl<B: BitBlock> Iterator for IntoIter<B> {
+ type Item = bool;
+
+ #[inline]
+ fn next(&mut self) -> Option<bool> {
+ self.range.next().map(|i| self.bit_vec.get(i).unwrap())
+ }
+}
+
+impl<B: BitBlock> DoubleEndedIterator for IntoIter<B> {
+ #[inline]
+ fn next_back(&mut self) -> Option<bool> {
+ self.range.next_back().map(|i| self.bit_vec.get(i).unwrap())
+ }
+}
+
+impl<B: BitBlock> ExactSizeIterator for IntoIter<B> {}
+
+impl<B: BitBlock> IntoIterator for BitVec<B> {
+ type Item = bool;
+ type IntoIter = IntoIter<B>;
+
+ #[inline]
+ fn into_iter(self) -> IntoIter<B> {
+ let nbits = self.nbits;
+ IntoIter { bit_vec: self, range: 0..nbits }
+ }
+}
+
+/// An iterator over the blocks of a `BitVec`.
+#[derive(Clone)]
+pub struct Blocks<'a, B: 'a> {
+ iter: slice::Iter<'a, B>,
+}
+
+impl<'a, B: BitBlock> Iterator for Blocks<'a, B> {
+ type Item = B;
+
+ #[inline]
+ fn next(&mut self) -> Option<B> {
+ self.iter.next().cloned()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<'a, B: BitBlock> DoubleEndedIterator for Blocks<'a, B> {
+ #[inline]
+ fn next_back(&mut self) -> Option<B> {
+ self.iter.next_back().cloned()
+ }
+}
+
+impl<'a, B: BitBlock> ExactSizeIterator for Blocks<'a, B> {}
+
+
+
+
+
+
+
+
+
+
+
+#[cfg(test)]
+mod tests {
+ use super::{BitVec, Iter};
+
+ // 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!(v0 != v1);
+ }
+
+ #[test]
+ fn test_equal_greatly_differing_sizes() {
+ let v0 = BitVec::from_elem(10, false);
+ let v1 = BitVec::from_elem(110, false);
+ assert!(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_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]));
+ }
+
+/* nightly
+ #[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(all(test, feature = "nightly"))] mod bench;
+
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".travis.yml":"6e70ae4b5d8502c24bb3d1ee196785db1b820fdb3ea8086aba5243f239f8c9aa","COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.toml":"aba38921b5097e7e364561a0ca4969d0efcd6f348c2c3d09f209d10a79b8127a","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","Makefile":"a45a128685a2ae7d4fa39d310786674417ee113055ef290a11f88002285865fc","README.md":"f8c016a7214f6669b1db2c9fd0e089d7dd1031255f74a8a4583abf1b8a4a3810","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","examples/read_names.rs":"c43924aec3e9bb6e3dd56b679302fbc54b952d2d42dc5d861d122976ee70468b","examples/select.rs":"f170cf4babd6a3f78b6d90014df042d439b85ae21dd48547ad39fa87030fc99f","examples/simple.rs":"90026db031e024cd0f6824618ddbccf9c8ab7f53ca922c973a6cb6eed0cb9f73","examples/sleep.rs":"958af1439b20c553a8f3abaffaafab1b6b30ac82d21980a2a4ae760430982c7e","examples/test_block_specific.rs":"0475dd32b950690121d10da1dafda0dfffc67445f04024dd601217bafcc45db0","examples/test_many.rs":"d734dc3785b47cb7b00807773556fbb7f4844e62e5383af08bde8279cdc7c6c4","examples/test_many_to_one.rs":"c262c59cf628bc3e1d192039df12a3b3ad6a24e5cd0fe8118a151d5c48abeb76","examples/test_one.rs":"b9d1cd8d370d5e12a730bcbb81711106a540180895f10e13583d3ea0ccfce759","examples/test_one_not_other.rs":"3c7c7f1d34d0daedf59b6a9c4427faac654428d6ca5cf59806019e0e439ea509","examples/test_sleep.rs":"b3e8c52a567907aca4ee2b32b214876283e85cb009dd48a638741abf4609fe4b","examples/test_usr1.rs":"e307699c40283fde09c86e14aef2fa0fe1acaa00d7eb04601467ad0456714c25","run-example-tests":"b4dc95f9ed378084ed10d10588ec78d153e7d1a6ebe3708ecfc173370969540d","src/lib.rs":"0c8f753886aabb710081d9ed0e222a6af0fd6f24ca5bda94081ecbb29395ab99"},"package":"f1f1e11f6e1c14c9e805a87c622cb8fcb636283b3119a2150af390cc6702d7fe"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/.travis.yml
@@ -0,0 +1,11 @@
+language: rust
+rust:
+ - 1.16.0
+ - stable
+ - beta
+ - nightly
+script:
+ - cargo build --verbose
+ - cargo doc
+ - cargo test --verbose
+ - ./run-example-tests
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/COPYING
@@ -0,0 +1,3 @@
+This project is dual-licensed under the Unlicense and MIT licenses.
+
+You may use this code under the terms of either license.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/Cargo.toml
@@ -0,0 +1,34 @@
+# 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 = "chan-signal"
+version = "0.3.1"
+authors = ["Andrew Gallant <jamslam@gmail.com>"]
+description = "Listen to OS signals with channels."
+homepage = "https://github.com/BurntSushi/chan-signal"
+documentation = "https://docs.rs/chan-signal"
+readme = "README.md"
+keywords = ["os", "signal", "channel", "select"]
+license = "Unlicense/MIT"
+repository = "https://github.com/BurntSushi/chan-signal"
+[dependencies.chan]
+version = "0.1"
+
+[dependencies.bit-set]
+version = "0.4"
+
+[dependencies.libc]
+version = "0.2"
+
+[dependencies.lazy_static]
+version = "0.2"
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/LICENSE-MIT
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Andrew Gallant
+
+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.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/Makefile
@@ -0,0 +1,14 @@
+all:
+ echo Nothing to do...
+
+ctags:
+ ctags --recurse --options=ctags.rust --languages=Rust
+
+docs:
+ cargo doc
+ in-dir ./target/doc fix-perms
+ rscp ./target/doc/* gopher:~/www/burntsushi.net/rustdoc/
+
+push:
+ git push origin master
+ git push github master
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/README.md
@@ -0,0 +1,95 @@
+This crate provies experimental support for responding to OS signals using
+[channels](https://github.com/BurntSushi/chan). Currently, this only works on
+Unix based systems, but I'd appreciate help adding Windows support.
+
+[](https://travis-ci.org/BurntSushi/chan-signal)
+[](https://crates.io/crates/chan-signal)
+
+Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
+
+
+### Documentation
+
+https://docs.rs/chan-signal
+
+
+### Example
+
+Use is really simple. Just ask the `chan_signal` crate to create a channel
+subscribed to a set of signals. When a signal is sent to the process it will
+be delivered to the channel.
+
+```rust
+use chan_signal::Signal;
+
+let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+
+// Blocks until this process is sent an INT or TERM signal.
+// Since the channel is never closed, we can unwrap the received value.
+signal.recv().unwrap();
+```
+
+### A realer example
+
+When combined with `chan_select!` from the `chan` crate, one can easily
+integrate signals with the rest of your program. For example, consider a
+main function that waits for either normal completion of work (which is done
+in a separate thread) or for a signal to be delivered:
+
+```rust
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use std::thread;
+use std::time::Duration;
+
+use chan_signal::Signal;
+
+fn main() {
+ // Signal gets a value when the OS sent a INT or TERM signal.
+ let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+ // When our work is complete, send a sentinel value on `sdone`.
+ let (sdone, rdone) = chan::sync(0);
+ // Run work.
+ thread::spawn(move || run(sdone));
+
+ // Wait for a signal or for work to be done.
+ chan_select! {
+ signal.recv() -> signal => {
+ println!("received signal: {:?}", signal)
+ },
+ rdone.recv() => {
+ println!("Program completed normally.");
+ }
+ }
+}
+
+fn run(_sdone: chan::Sender<()>) {
+ println!("Running work for 5 seconds.");
+ println!("Can you send a signal quickly enough?");
+ // Do some work.
+ thread::sleep(Duration::from_secs(5));
+
+ // _sdone gets dropped which closes the channel and causes `rdone`
+ // to unblock.
+}
+```
+
+This is much easier than registering a signal handler because:
+
+1. Signal handlers run asynchronously.
+2. The code you're permitted to execute in a signal handler is extremely
+ constrained (e.g., no allocation), so it is difficult to integrate
+ it with the rest of your program.
+
+Using channels, you can invent whatever flow you like and handle OS signals
+just like anything else.
+
+
+### How it works
+
+TL;DR - Spawn a thread, block on `sigwait`, deliver signals, repeat.
+
+It's
+[explained a bit more in the docs](http://burntsushi.net/rustdoc/chan_signal/#how-it-works).
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/UNLICENSE
@@ -0,0 +1,24 @@
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+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 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.
+
+For more information, please refer to <http://unlicense.org/>
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/read_names.rs
@@ -0,0 +1,81 @@
+// This example demonstrates how to do something almost useful with OS signals.
+// This program asks the user to inputs names. It then outputs these names
+// once the user inputs EOF. The catch is that it will *also* output these
+// names if the user sends the process SIGINT or SIGTERM.
+//
+// This is hard or impossible to do with regular asynchronous signal handlers.
+// But with a channel based API, it's easy to integrate with the rest of
+// your control flow.
+
+#![allow(deprecated)] // for connect=>join in 1.3
+
+#[macro_use] extern crate chan;
+extern crate chan_signal;
+
+use std::error::Error;
+use std::io::{self, BufRead, Write};
+use std::process;
+use std::thread;
+
+use chan_signal::{Signal, notify};
+
+fn main() {
+ // It is imperative that we start listening for signals as soon as
+ // possible. In particular, if `notify` is called after another thread
+ // has spawned, then signal masking won't be applied to it and signal
+ // handling won't work.
+ //
+ // See "Signal mask and pending signals" section of signal(7).
+ let signal = notify(&[Signal::INT, Signal::TERM]);
+ match run(signal) {
+ Ok(mut names) => {
+ names.sort();
+ println!("You entered {} names: {}",
+ names.len(), names.connect(", "));
+ }
+ Err(err) => {
+ writeln!(&mut io::stderr(), "{}", err).unwrap();
+ process::exit(1);
+ }
+ }
+}
+
+type Result<T> = ::std::result::Result<T, Box<Error+Send+Sync>>;
+
+fn run(signal: chan::Receiver<Signal>) -> Result<Vec<String>> {
+ let lines = read_stdin_lines();
+ let mut names = vec![];
+ println!("Please enter some names, each on a new line:");
+ loop {
+ chan_select! {
+ lines.recv() -> line => {
+ match line {
+ // If the channel closed (i.e., reads EOF), then quit
+ // the loop and print what we've got.
+ //
+ // The rightward drift is painful...
+ None => break,
+ Some(line) => names.push(try!(line).trim().to_owned()),
+ }
+ },
+ // If we get SIGINT or SIGTERM, just stop the loop and print
+ // what we've got so far.
+ signal.recv() => break,
+ }
+ }
+ Ok(names)
+}
+
+// Spawns a new thread to read lines and sends the result on the returned
+// channel.
+fn read_stdin_lines() -> chan::Receiver<io::Result<String>> {
+ let (s, r) = chan::sync(0);
+ let stdin = io::stdin();
+ thread::spawn(move || {
+ let stdin = stdin.lock();
+ for line in stdin.lines() {
+ s.send(line);
+ }
+ });
+ r
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/select.rs
@@ -0,0 +1,34 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use std::thread;
+use std::time::Duration;
+
+use chan_signal::Signal;
+
+fn main() {
+ // Signal gets a value when the OS sent a INT or TERM signal.
+ let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+ // When our work is complete, send a sentinel value on `sdone`.
+ let (sdone, rdone) = chan::sync(0);
+ // Run work.
+ thread::spawn(move || run(sdone));
+
+ // Wait for a signal or for work to be done.
+ chan_select! {
+ signal.recv() -> signal => {
+ println!("received signal: {:?}", signal)
+ },
+ rdone.recv() => {
+ println!("Program completed normally.");
+ }
+ }
+}
+
+fn run(_sdone: chan::Sender<()>) {
+ println!("Running work for 5 seconds.");
+ println!("Can you send a signal quickly enough?");
+ // Do some work.
+ thread::sleep(Duration::from_secs(5));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/simple.rs
@@ -0,0 +1,16 @@
+// This is a minimal example that demonstrates how to listen and respond to
+// OS signals. Namely, it requests to be notified about a SIGINT (usually
+// ^C in your terminal) and blocks until it gets one.
+
+#[macro_use] extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, notify};
+
+fn main() {
+ let signal = notify(&[Signal::INT]);
+ println!("Send a INT signal my way!");
+ // block until we get a signal
+ assert_eq!(signal.recv(), Some(Signal::INT));
+ println!("Thanks :]");
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/sleep.rs
@@ -0,0 +1,16 @@
+#[macro_use] extern crate chan;
+extern crate chan_signal;
+
+use std::thread;
+use std::time::Duration;
+
+use chan_signal::{Signal, notify};
+
+fn main() {
+ let signal = notify(&[Signal::INT]);
+ println!("Send a INT signal my way!");
+ thread::spawn(move || thread::sleep(Duration::from_secs(10)));
+ // block until we get a signal
+ assert_eq!(signal.recv(), Some(Signal::INT));
+ println!("Thanks :]");
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_block_specific.rs
@@ -0,0 +1,23 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let r_usr1 = chan_signal::notify(&[Signal::USR1, Signal::ALRM]);
+ kill_this(Signal::USR1);
+ kill_this(Signal::ALRM);
+ assert_eq!(r_usr1.recv(), Some(Signal::USR1));
+ assert_eq!(r_usr1.recv(), Some(Signal::ALRM));
+
+ let (s, r_usr2) = chan::sync(1);
+ chan_signal::notify_on(&s, Signal::USR2);
+ kill_this(Signal::USR2);
+ assert_eq!(r_usr2.recv(), Some(Signal::USR2));
+
+ // The following will terminate the process, as it is NOT blocked
+ // by the main thread.
+ kill_this(Signal::TERM);
+ unreachable!();
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_many.rs
@@ -0,0 +1,16 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let (s1, r1) = chan::sync(1);
+ let (s2, r2) = chan::sync(1);
+ chan_signal::notify_on(&s1, Signal::HUP);
+ chan_signal::notify_on(&s2, Signal::TERM);
+ kill_this(Signal::HUP);
+ assert_eq!(r1.recv(), Some(Signal::HUP));
+ kill_this(Signal::TERM);
+ assert_eq!(r2.recv(), Some(Signal::TERM));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_many_to_one.rs
@@ -0,0 +1,15 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let (s1, r1) = chan::sync(1);
+ let (s2, r2) = chan::sync(1);
+ chan_signal::notify_on(&s1, Signal::HUP);
+ chan_signal::notify_on(&s2, Signal::HUP);
+ kill_this(Signal::HUP);
+ assert_eq!(r1.recv(), Some(Signal::HUP));
+ assert_eq!(r2.recv(), Some(Signal::HUP));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_one.rs
@@ -0,0 +1,12 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let (s, r) = chan::sync(1);
+ chan_signal::notify_on(&s, Signal::HUP);
+ kill_this(Signal::HUP);
+ assert_eq!(r.recv(), Some(Signal::HUP));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_one_not_other.rs
@@ -0,0 +1,15 @@
+
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this, block};
+
+fn main() {
+ block(&[Signal::TERM]);
+ let (s, r) = chan::sync(1);
+ chan_signal::notify_on(&s, Signal::HUP);
+ kill_this(Signal::TERM);
+ kill_this(Signal::HUP);
+ assert_eq!(r.recv(), Some(Signal::HUP));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_sleep.rs
@@ -0,0 +1,17 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use std::thread;
+use std::time::Duration;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let (s, r) = chan::sync(1);
+ chan_signal::notify_on(&s, Signal::HUP);
+ thread::spawn(move || thread::sleep(Duration::from_secs(10)));
+ thread::sleep(Duration::from_millis(500));
+ kill_this(Signal::HUP);
+ assert_eq!(r.recv(), Some(Signal::HUP));
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/examples/test_usr1.rs
@@ -0,0 +1,12 @@
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::{Signal, kill_this};
+
+fn main() {
+ let (s, r) = chan::sync(1);
+ chan_signal::notify_on(&s, Signal::USR1);
+ kill_this(Signal::USR1);
+ assert_eq!(r.recv(), Some(Signal::USR1));
+}
new file mode 100755
--- /dev/null
+++ b/third_party/rust/chan-signal/run-example-tests
@@ -0,0 +1,6 @@
+#!/bin/sh
+
+for t in ./examples/test_*.rs; do
+ filename=$(basename "$t")
+ cargo run --example ${filename%*.rs}
+done
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan-signal/src/lib.rs
@@ -0,0 +1,518 @@
+/*!
+This crate provides a simplistic interface to subscribe to operating system
+signals through a channel API. Use is extremely simple:
+
+```no_run
+use chan_signal::Signal;
+
+let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+
+// Blocks until this process is sent an INT or TERM signal.
+// Since the channel is never closed, we can unwrap the received value.
+signal.recv().unwrap();
+```
+
+
+# Example
+
+When combined with `chan_select!` from the `chan` crate, one can easily
+integrate signals with the rest of your program. For example, consider a
+main function that waits for either normal completion of work (which is done
+in a separate thread) or for a signal to be delivered:
+
+```no_run
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::Signal;
+
+fn main() {
+ // Signal gets a value when the OS sent a INT or TERM signal.
+ let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+ // When our work is complete, send a sentinel value on `sdone`.
+ let (sdone, rdone) = chan::sync(0);
+ // Run work.
+ ::std::thread::spawn(move || run(sdone));
+
+ // Wait for a signal or for work to be done.
+ chan_select! {
+ signal.recv() -> signal => {
+ println!("received signal: {:?}", signal)
+ },
+ rdone.recv() => {
+ println!("Program completed normally.");
+ }
+ }
+}
+
+fn run(_sdone: chan::Sender<()>) {
+ // Do some work.
+ ::std::thread::sleep_ms(1000);
+ // Quit normally.
+ // Note that we don't need to send any values. We just let the
+ // sending channel drop, which closes the channel, which causes
+ // the receiver to synchronize immediately and always.
+}
+```
+
+You can see this example in action by running `cargo run --example select`
+in the root directory of this crate's
+[repository](https://github.com/BurntSushi/chan-signal).
+
+# Platform support (no Windows support)
+
+This should work on Unix platforms supported by Rust itself.
+
+There is no Windows support at all. I welcome others to either help me add it
+or help educate me so that I may one day add it.
+
+
+# How it works
+
+Overview: uses the "spawn a thread and block on `sigwait`" approach. In
+particular, it avoids standard asynchronous signal handling because it is
+very difficult to do anything non-trivial inside a signal handler.
+
+After a call to `notify`/`notify_on` (or `block`), the given signals are set
+to *blocked*. This is necessary for synchronous signal handling using `sigwait`.
+
+After the first call to `notify` (or `notify_on'), a new thread is spawned and
+immediately blocks on a call to `sigwait`. It is only unblocked when one of the
+signals that were masked previously by calls to `notify` etc. arrives, which now
+cannot be delivered directly to any of the threads of the process, and therefore
+unblocks the waiting signal watcher thread. Once it's unblocked, it sends the
+signal on all subscribed channels via a non-blocking send. Once all channels
+have been visited, the thread blocks on `sigwait` again.
+
+This approach has some restrictions. Namely, your program must comply with the
+following:
+
+* Any and all threads spawned in your program **must** come after the first
+ call to `notify` (or `notify_on`). This is so all spawned threads inherit
+ the blocked status of signals. If a thread starts before `notify` is called,
+ it will not have the correct signal mask. When a signal is delivered, the
+ result is indeterminate.
+* No other threads may call `sigwait`. When a signal is delivered, only one
+ `sigwait` is indeterminately unblocked.
+
+
+# Future work
+
+This crate exposes the simplest API I could think of. As a result, a few
+additions may be warranted:
+
+* Expand the set of signals. (Requires figuring out platform differences.)
+* Allow channel unsubscription.
+* Allow callers to reset the signal mask? (Seems hard.)
+* Support Windows.
+*/
+#![deny(missing_docs)]
+
+extern crate bit_set;
+#[macro_use] extern crate chan;
+#[macro_use] extern crate lazy_static;
+extern crate libc;
+
+use std::collections::HashMap;
+use std::io;
+use std::mem;
+use std::ptr;
+use std::sync::Mutex;
+use std::thread;
+
+use bit_set::BitSet;
+use chan::Sender;
+use libc::{
+ // POSIX.1-2008, minus SIGPOLL (not in some BSD, use SIGIO)
+ SIGHUP, SIGINT, SIGQUIT, SIGILL, SIGABRT, SIGFPE, SIGKILL,
+ SIGSEGV, SIGPIPE, SIGALRM, SIGTERM, SIGUSR1, SIGUSR2,
+ SIGCHLD, SIGCONT, SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU,
+ SIGBUS, SIGPROF, SIGSYS, SIGTRAP, SIGURG, SIGVTALRM,
+ SIGXCPU, SIGXFSZ,
+
+ // Common Extensions (SIGINFO and SIGEMT not in libc)
+ SIGIO,
+ SIGWINCH,
+
+ SIG_BLOCK,
+ SIG_SETMASK,
+};
+use libc::kill;
+use libc::getpid;
+
+lazy_static! {
+ static ref HANDLERS: Mutex<HashMap<Sender<Signal>, BitSet>> = {
+ init();
+ Mutex::new(HashMap::new())
+ };
+}
+
+/// Create a new channel subscribed to the given signals.
+///
+/// The channel returned is never closed.
+///
+/// This is a convenience function for subscribing to multiple signals at once.
+/// See the documentation of `notify_on` for details.
+///
+/// The channel returned has a small buffer to prevent signals from being
+/// dropped.
+///
+/// **THIS MUST BE CALLED BEFORE ANY OTHER THREADS ARE SPAWNED IN YOUR
+/// PROCESS.**
+///
+/// # Example
+///
+/// ```no_run
+/// use chan_signal::Signal;
+///
+/// let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+///
+/// // Blocks until this process is sent an INT or TERM signal.
+/// // Since the channel is never closed, we can unwrap the received value.
+/// signal.recv().unwrap();
+/// ```
+pub fn notify(signals: &[Signal]) -> chan::Receiver<Signal> {
+ let (s, r) = chan::sync(100);
+ for &sig in signals {
+ notify_on(&s, sig);
+ }
+ // dropping `s` is OK because `notify_on` acquires one.
+ r
+}
+
+/// Subscribe to a signal on a channel.
+///
+/// When `signal` is delivered to this process, it will be sent on the channel
+/// given.
+///
+/// Note that a signal is sent using a non-blocking send. Namely, if the
+/// channel's buffer is full (or it has no buffer) and it isn't ready to
+/// rendezvous, then the signal will be dropped.
+///
+/// There is currently no way to unsubscribe. Moreover, the channel given
+/// here will be alive for the lifetime of the process. Therefore, the channel
+/// will never be closed.
+///
+/// **THIS MUST BE CALLED BEFORE ANY OTHER THREADS ARE SPAWNED IN YOUR
+/// PROCESS.**
+pub fn notify_on(chan: &Sender<Signal>, signal: Signal) {
+ let mut subs = HANDLERS.lock().unwrap();
+ if subs.contains_key(chan) {
+ subs.get_mut(chan).unwrap().insert(signal.as_sig() as usize);
+ } else {
+ let mut sigs = BitSet::new();
+ sigs.insert(signal.as_sig() as usize);
+ subs.insert((*chan).clone(), sigs);
+ }
+
+ // Make sure that the signal that we want notifications on is blocked
+ // It does not matter if we block the same signal twice.
+ block(&[signal]);
+}
+
+/// Block all given signals without receiving notifications.
+///
+/// If a signal has also been passed to `notify`/`notify_on` this function
+/// does not have any effect in terms of that signal.
+///
+/// **THIS MUST BE CALLED BEFORE ANY OTHER THREADS ARE SPAWNED IN YOUR
+/// PROCESS.**
+pub fn block(signals: &[Signal]) {
+ let mut block = SigSet::empty();
+ for signal in signals {
+ block.add(signal.as_sig()).unwrap();
+ }
+ block.thread_block_signals().unwrap();
+}
+
+/// Block all subscribable signals.
+///
+/// Calling this function effectively restores the default behavior of
+/// version <= 0.2.0 of this library.
+///
+/// **THIS MUST BE CALLED BEFORE ANY OTHER THREADS ARE SPAWNED IN YOUR
+/// PROCESS.**
+pub fn block_all_subscribable() {
+ SigSet::subscribable().thread_block_signals().unwrap();
+}
+
+fn init() {
+ // First:
+ // Get the curren thread_mask. (We cannot just overwrite the threadmask with
+ // an empty one because this function is executed lazily.
+ let saved_mask = SigSet::current().unwrap();
+
+ // Then:
+ // Block all signals in this thread. The signal mask will then be inherited
+ // by the worker thread.
+ SigSet::subscribable().thread_set_signal_mask().unwrap();
+ thread::spawn(move || {
+ let mut listen = SigSet::subscribable();
+
+ loop {
+ let sig = listen.wait().unwrap();
+ let subs = HANDLERS.lock().unwrap();
+ for (s, sigs) in subs.iter() {
+ if !sigs.contains(sig as usize) {
+ continue;
+ }
+ chan_select! {
+ default => {},
+ s.send(Signal::new(sig)) => {},
+ }
+ }
+ }
+ });
+
+ // Now:
+ // Reset to the previously saved sigmask.
+ // This whole procedure is necessary, as we cannot rely on the worker thread
+ // starting fast enough to set its signal mask. Otherwise an early SIGTERM or
+ // similar may take down the process even though the main thread has blocked
+ // the signal.
+ saved_mask.thread_set_signal_mask().unwrap();
+}
+
+/// Kill the current process. (Only used in tests.)
+#[doc(hidden)]
+pub fn kill_this(sig: Signal) {
+ unsafe { kill(getpid(), sig.as_sig()); }
+}
+
+type Sig = libc::c_int;
+
+/// The set of subscribable signals.
+///
+/// After the first call to `notify_on` (or `notify`), precisely this set of
+/// signals are set to blocked status.
+#[allow(missing_docs)]
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum Signal {
+ HUP,
+ INT,
+ QUIT,
+ ILL,
+ ABRT,
+ FPE,
+ KILL,
+ SEGV,
+ PIPE,
+ ALRM,
+ TERM,
+ USR1,
+ USR2,
+ CHLD,
+ CONT,
+ STOP,
+ TSTP,
+ TTIN,
+ TTOU,
+ BUS,
+ PROF,
+ SYS,
+ TRAP,
+ URG,
+ VTALRM,
+ XCPU,
+ XFSZ,
+ IO,
+ WINCH,
+ #[doc(hidden)]
+ __NonExhaustiveMatch,
+}
+
+impl Signal {
+ fn new(sig: Sig) -> Signal {
+ match sig {
+ SIGHUP => Signal::HUP,
+ SIGINT => Signal::INT,
+ SIGQUIT => Signal::QUIT,
+ SIGILL => Signal::ILL,
+ SIGABRT => Signal::ABRT,
+ SIGFPE => Signal::FPE,
+ SIGKILL => Signal::KILL,
+ SIGSEGV => Signal::SEGV,
+ SIGPIPE => Signal::PIPE,
+ SIGALRM => Signal::ALRM,
+ SIGTERM => Signal::TERM,
+ SIGUSR1 => Signal::USR1,
+ SIGUSR2 => Signal::USR2,
+ SIGCHLD => Signal::CHLD,
+ SIGCONT => Signal::CONT,
+ SIGSTOP => Signal::STOP,
+ SIGTSTP => Signal::TSTP,
+ SIGTTIN => Signal::TTIN,
+ SIGTTOU => Signal::TTOU,
+ SIGBUS => Signal::BUS,
+ SIGPROF => Signal::PROF,
+ SIGSYS => Signal::SYS,
+ SIGTRAP => Signal::TRAP,
+ SIGURG => Signal::URG,
+ SIGVTALRM => Signal::VTALRM,
+ SIGXCPU => Signal::XCPU,
+ SIGXFSZ => Signal::XFSZ,
+ SIGIO => Signal::IO,
+ SIGWINCH => Signal::WINCH,
+ sig => panic!("unsupported signal number: {}", sig),
+ }
+ }
+
+ fn as_sig(self) -> Sig {
+ match self {
+ Signal::HUP => SIGHUP,
+ Signal::INT => SIGINT,
+ Signal::QUIT => SIGQUIT,
+ Signal::ILL => SIGILL,
+ Signal::ABRT => SIGABRT,
+ Signal::FPE => SIGFPE,
+ Signal::KILL => SIGKILL,
+ Signal::SEGV => SIGSEGV,
+ Signal::PIPE => SIGPIPE,
+ Signal::ALRM => SIGALRM,
+ Signal::TERM => SIGTERM,
+ Signal::USR1 => SIGUSR1,
+ Signal::USR2 => SIGUSR2,
+ Signal::CHLD => SIGCHLD,
+ Signal::CONT => SIGCONT,
+ Signal::STOP => SIGSTOP,
+ Signal::TSTP => SIGTSTP,
+ Signal::TTIN => SIGTTIN,
+ Signal::TTOU => SIGTTOU,
+ Signal::BUS => SIGBUS,
+ Signal::PROF => SIGPROF,
+ Signal::SYS => SIGSYS,
+ Signal::TRAP => SIGTRAP,
+ Signal::URG => SIGURG,
+ Signal::VTALRM => SIGVTALRM,
+ Signal::XCPU => SIGXCPU,
+ Signal::XFSZ => SIGXFSZ,
+ Signal::IO => SIGIO,
+ Signal::WINCH => SIGWINCH,
+ Signal::__NonExhaustiveMatch => unreachable!(),
+ }
+ }
+}
+
+/// Safe wrapper around `sigset_t`.
+struct SigSet(sigset_t);
+
+impl SigSet {
+ fn empty() -> SigSet {
+ let mut set = unsafe { mem::uninitialized() };
+ unsafe { sigemptyset(&mut set) };
+ SigSet(set)
+ }
+
+ fn current() -> io::Result<SigSet> {
+ let mut set = unsafe { mem::uninitialized() };
+ let ecode = unsafe {
+ pthread_sigmask(SIG_SETMASK, ptr::null_mut(), &mut set)
+ };
+ ok_errno(SigSet(set), ecode)
+ }
+
+ /// Creates a new signal set with precisely the signals we're limited
+ /// to subscribing to.
+ fn subscribable() -> SigSet {
+ let mut set = SigSet::empty();
+ set.add(SIGHUP).unwrap();
+ set.add(SIGINT).unwrap();
+ set.add(SIGQUIT).unwrap();
+ set.add(SIGILL).unwrap();
+ set.add(SIGABRT).unwrap();
+ set.add(SIGFPE).unwrap();
+ set.add(SIGKILL).unwrap();
+ set.add(SIGSEGV).unwrap();
+ set.add(SIGPIPE).unwrap();
+ set.add(SIGALRM).unwrap();
+ set.add(SIGTERM).unwrap();
+ set.add(SIGUSR1).unwrap();
+ set.add(SIGUSR2).unwrap();
+ set.add(SIGCHLD).unwrap();
+ set.add(SIGCONT).unwrap();
+ set.add(SIGSTOP).unwrap();
+ set.add(SIGTSTP).unwrap();
+ set.add(SIGTTIN).unwrap();
+ set.add(SIGTTOU).unwrap();
+ set.add(SIGBUS).unwrap();
+ set.add(SIGPROF).unwrap();
+ set.add(SIGSYS).unwrap();
+ set.add(SIGTRAP).unwrap();
+ set.add(SIGURG).unwrap();
+ set.add(SIGVTALRM,).unwrap();
+ set.add(SIGXCPU).unwrap();
+ set.add(SIGXFSZ).unwrap();
+ set.add(SIGIO).unwrap();
+ set.add(SIGWINCH).unwrap();
+ set
+ }
+
+ fn add(&mut self, sig: Sig) -> io::Result<()> {
+ unsafe { ok_errno((), sigaddset(&mut self.0, sig)) }
+ }
+
+ fn wait(&mut self) -> io::Result<Sig> {
+ let mut sig: Sig = 0;
+ let errno = unsafe { sigwait(&mut self.0, &mut sig) };
+ ok_errno(sig, errno)
+ }
+
+ fn thread_block_signals(&self) -> io::Result<()> {
+ let ecode = unsafe {
+ pthread_sigmask(SIG_BLOCK, &self.0, ptr::null_mut())
+ };
+ ok_errno((), ecode)
+ }
+
+ fn thread_set_signal_mask(&self) -> io::Result<()> {
+ let ecode = unsafe {
+ pthread_sigmask(SIG_SETMASK, &self.0, ptr::null_mut())
+ };
+ ok_errno((), ecode)
+ }
+}
+
+fn ok_errno<T>(ok: T, ecode: libc::c_int) -> io::Result<T> {
+ if ecode != 0 { Err(io::Error::from_raw_os_error(ecode)) } else { Ok(ok) }
+}
+
+extern {
+ fn sigwait(set: *mut sigset_t, sig: *mut Sig) -> Sig;
+ fn sigaddset(set: *mut sigset_t, sig: Sig) -> libc::c_int;
+ fn sigemptyset(set: *mut sigset_t) -> libc::c_int;
+ fn pthread_sigmask(
+ how: libc::c_int,
+ set: *const sigset_t,
+ oldset: *mut sigset_t,
+ ) -> libc::c_int;
+}
+
+// Most of this was lifted out of rust-lang:rust/src/libstd/sys/unix/c.rs.
+
+#[cfg(all(target_os = "linux", target_pointer_width = "32"))]
+#[repr(C)]
+struct sigset_t {
+ __val: [libc::c_ulong; 32],
+}
+
+#[cfg(all(target_os = "linux", target_pointer_width = "64"))]
+#[repr(C)]
+struct sigset_t {
+ __val: [libc::c_ulong; 16],
+}
+
+#[cfg(target_os = "android")]
+type sigset_t = libc::c_ulong;
+
+#[cfg(any(target_os = "macos", target_os = "ios"))]
+type sigset_t = u32;
+
+#[cfg(any(target_os = "freebsd", target_os = "dragonfly"))]
+#[repr(C)]
+struct sigset_t {
+ bits: [u32; 4],
+}
+
+#[cfg(any(target_os = "bitrig", target_os = "netbsd", target_os = "openbsd"))]
+type sigset_t = libc::c_uint;
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/.cargo-checksum.json
@@ -0,0 +1,1 @@
+{"files":{".travis.yml":"e6f655077e6181529f3303055921b4cdb8c9c6625d664d4f7d04a9fa572b1088","BENCHMARKS.md":"a3e0d71aa2d0feabea68017419f45cf17dd1bb267c8cdeb9e416098de05565c6","COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.toml":"1c5f29c5cdbe22d4dcb794207c568cd3c636903d2cb372cb78b8563aa80f0357","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","Makefile":"a45a128685a2ae7d4fa39d310786674417ee113055ef290a11f88002285865fc","README.md":"f3c02bb6a55ab19bbfdcc1ca8cb5021f7004153f1750758f6d91364a9f094267","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","benches/throughput.rs":"52ef281222b14397a9f92dec6c1b20fde2667ceacf0084c0513ac40c06d3eab1","ctags.rust":"3d128d3cc59f702e68953ba2fe6c3f46bc6991fc575308db060482d5da0c79f3","examples/default.rs":"62e7f966a222ee11ccee50ef4bcbde975617ee87472eca1d5a326448ce2a8390","examples/fibonacci.rs":"b871785c5cef41fa3b9ee005610b25866c436521261ed2df151deb76f26f603d","examples/leaky_buffer.rs":"e5b2f7abde66198699c104ae955f7718267681b2ff3b6331ca6341248e734134","examples/nested_select.rs":"4ba785658eab4d7d0352992a274e957766c64e3893e4df4625678dab579b9d1e","examples/web.rs":"021ec1655b911398b3042ea9a2a88932df157378c81926ab8208e6ff45eb9007","session.vim":"95cb1d7caf0ff7fbe76ec911988d908ddd883381c925ba64b537695bc9f021c4","src/lib.rs":"0d6f3549fea76b2eabccf152d81653e2bec96ac6bea85cac4315321e871f4f7e","src/notifier.rs":"a2053fa219f67c0462f027e561a09579b160bd4f968067df42ec84cdb6e72668","src/select.rs":"edfb07db540d1b2d133d5b0299e84816667b472aa270ecc83cb75772ff5f9c6a","src/tracker.rs":"93ba26613e346f45423716a32959640b05eb27e31bf11d54cf9a09e39ae00ab7","src/wait_group.rs":"264a7c2a8501c3b262af7fa96c98c968ce29a67a9b106db4852fe941c1d4326f"},"package":"9af7c487bb99c929ba2715b1a3a7bf45f5062bf5b6eae5d32b292a96c5865172"}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/.travis.yml
@@ -0,0 +1,14 @@
+language: rust
+rust:
+ - stable
+ - beta
+ - nightly
+script:
+ - cargo build --verbose
+ - cargo doc
+ - if [ "$TRAVIS_RUST_VERSION" = "nightly" ]; then
+ cargo test --verbose --features nightly;
+ cargo bench --verbose;
+ else
+ cargo test --verbose;
+ fi
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/BENCHMARKS.md
@@ -0,0 +1,26 @@
+```
+test mpsc_chan_async ... bench: 356,330 ns/iter (+/- 37,373) = 2 MB/s
+test mpsc_chan_sync_buffered ... bench: 16,186,014 ns/iter (+/- 962,562)
+test mpsc_chan_sync_buffered_all ... bench: 371,997 ns/iter (+/- 20,529) = 2 MB/s
+test mpsc_chan_sync_unbuffered ... bench: 25,843,510 ns/iter (+/- 3,365,831)
+test select_no_init_chan_async ... bench: 1,221,417 ns/iter (+/- 84,438)
+test select_no_init_chan_sync_buffered ... bench: 5,116,771 ns/iter (+/- 442,794)
+test select_no_init_chan_sync_buffered_all ... bench: 1,238,522 ns/iter (+/- 74,315)
+test select_no_init_chan_sync_unbuffered ... bench: 5,281,292 ns/iter (+/- 611,475)
+test select_with_init_chan_async ... bench: 759,107 ns/iter (+/- 68,027) = 1 MB/s
+test select_with_init_chan_sync_buffered ... bench: 7,015,030 ns/iter (+/- 814,833)
+test select_with_init_chan_sync_buffered_all ... bench: 769,810 ns/iter (+/- 66,908) = 1 MB/s
+test select_with_init_chan_sync_unbuffered ... bench: 8,829,461 ns/iter (+/- 938,300)
+test spsc_chan_async ... bench: 324,128 ns/iter (+/- 10,292) = 3 MB/s
+test spsc_chan_sync_buffered ... bench: 12,186,476 ns/iter (+/- 1,400,514)
+test spsc_chan_sync_buffered_all ... bench: 345,468 ns/iter (+/- 4,002) = 2 MB/s
+test spsc_chan_sync_unbuffered ... bench: 13,158,969 ns/iter (+/- 607,033)
+test std_mpsc_chan_async ... bench: 152,193 ns/iter (+/- 17,694) = 6 MB/s
+test std_mpsc_chan_sync_buffered ... bench: 13,696,283 ns/iter (+/- 1,576,489)
+test std_mpsc_chan_sync_buffered_all ... bench: 202,740 ns/iter (+/- 17,262) = 4 MB/s
+test std_mpsc_chan_sync_unbuffered ... bench: 13,980,354 ns/iter (+/- 2,057,872)
+test std_spsc_chan_async ... bench: 160,074 ns/iter (+/- 19,480) = 6 MB/s
+test std_spsc_chan_sync_buffered ... bench: 13,613,480 ns/iter (+/- 1,937,164)
+test std_spsc_chan_sync_buffered_all ... bench: 259,622 ns/iter (+/- 9,902) = 3 MB/s
+test std_spsc_chan_sync_unbuffered ... bench: 13,609,904 ns/iter (+/- 1,998,175)
+```
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/COPYING
@@ -0,0 +1,3 @@
+This project is dual-licensed under the Unlicense and MIT licenses.
+
+You may use this code under the terms of either license.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/Cargo.toml
@@ -0,0 +1,30 @@
+# 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 = "chan"
+version = "0.1.21"
+authors = ["Andrew Gallant <jamslam@gmail.com>"]
+description = "Multi-producer, multi-consumer channels with select."
+homepage = "https://github.com/BurntSushi/chan"
+documentation = "http://burntsushi.net/rustdoc/chan/"
+readme = "README.md"
+keywords = ["channel", "asynchronous", "mpmc", "golang", "select"]
+license = "Unlicense/MIT"
+repository = "https://github.com/BurntSushi/chan"
+[dependencies.rand]
+version = "0.3"
+[dev-dependencies.hyper]
+version = "0.7"
+
+[features]
+nightly = []
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/LICENSE-MIT
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Andrew Gallant
+
+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.
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/Makefile
@@ -0,0 +1,14 @@
+all:
+ echo Nothing to do...
+
+ctags:
+ ctags --recurse --options=ctags.rust --languages=Rust
+
+docs:
+ cargo doc
+ in-dir ./target/doc fix-perms
+ rscp ./target/doc/* gopher:~/www/burntsushi.net/rustdoc/
+
+push:
+ git push origin master
+ git push github master
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/README.md
@@ -0,0 +1,133 @@
+This crate provides experimental support for multi-producer/multi-consumer
+channels. This includes rendezvous, synchronous and asynchronous channels.
+
+Channels are never complete without a way to synchronize on multiple channels
+at the same time. Therefore, this crate provides a `chan_select!` macro that
+can select on any combination of channel send or receive operations.
+
+[](https://travis-ci.org/BurntSushi/chan)
+[](https://crates.io/crates/chan)
+
+Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
+
+
+### Documentation
+
+Please help me improve the documentation!
+
+[http://burntsushi.net/rustdoc/chan/](http://burntsushi.net/rustdoc/chan/)
+
+
+### Example: selecting on multiple channels
+
+```rust
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+
+fn main() {
+ let tick = chan::tick_ms(100);
+ let boom = chan::after_ms(500);
+ loop {
+ chan_select! {
+ default => { println!(" ."); thread::sleep_ms(50); },
+ tick.recv() => println!("tick."),
+ boom.recv() => { println!("BOOM!"); return; },
+ }
+ }
+}
+```
+
+
+### Example: wait for OS signals
+
+This requires the `chan-signal` crate on crates.io.
+
+```rust
+#[macro_use]
+extern crate chan;
+extern crate chan_signal;
+
+use chan_signal::Signal;
+use std::thread;
+
+fn main() {
+ // Signal gets a value when the OS sent a INT or TERM signal.
+ let signal = chan_signal::notify(&[Signal::INT, Signal::TERM]);
+ // When our work is complete, send a sentinel value on `sdone`.
+ let (sdone, rdone) = chan::sync(0);
+ // Run work.
+ thread::spawn(move || run(sdone));
+
+ // Wait for a signal or for work to be done.
+ chan_select! {
+ signal.recv() -> signal => {
+ println!("received signal: {:?}", signal)
+ },
+ rdone.recv() => {
+ println!("Program completed normally.");
+ }
+ }
+}
+
+fn run(_sdone: chan::Sender<()>) {
+ println!("Running work for 5 seconds.");
+ println!("Can you send a signal quickly enough?");
+ // Do some work.
+ thread::sleep_ms(5000);
+
+ // _sdone gets dropped which closes the channel and causes `rdone`
+ // to unblock.
+}
+```
+
+
+### Differences with `std::sync::mpsc`
+
+Rust's standard library has a multi-producer/single-consumer channel. Here are
+the differences (which I believe amount to a massive increase in ergonomics):
+
+* `chan` channels are multi-producer/multi-consumer, so you can clone senders
+ and receivers with reckless abandon.
+* `chan` uses **no `unsafe` code**.
+* `chan`'s asynchronous channels have lower throughput than `std::sync::mpsc`.
+ (Run the benchmarks with `cargo bench`.)
+* `chan`'s synchronous channels have comparable throughput with
+ `std::sync::mpsc`.
+* `chan` has a select macro that works on stable and can synchronize across
+ channel send *or* receive operations. It also supports a "default" case
+ that is executed when all channel operations are blocked. (This effectively
+ replaces uses of `try_send`/`try_recv` in `std::sync::mpsc`. Indeed, `chan`
+ omits these methods entirely.)
+* `chan`'s send operations will deadlock if all receivers have been dropped.
+ This is a deliberate choice inspired by Go. I'm open to changing it.
+* `chan`'s channels implement `Sync`. When we get a working scoped API, you
+ won't need to clone channels to pass them into other threads (when you can
+ prove that the channel outlives the thread of course).
+
+
+### Motivation
+
+The purpose of this crate is to provide a safe concurrent abstraction for
+communicating sequential processes. Performance takes a second seat to
+semantics and ergonomics. If you're looking for high performance
+synchronization, `chan` is probably not the right fit.
+
+Moreover, `chan` synchronizes across operating system threads, so in order to
+spin up multiple concurrent routines, you need to launch a thread for each one.
+This may be more cost than you're willing to pay.
+
+Bottom line: `chan` doesn't have any place in a high performance web server,
+but it might have a place in structuring coarse grained concurrency in
+applications.
+
+
+### Also...
+
+[chan-signal](https://github.com/BurntSushi/chan-signal) is a Rust library
+for using channels in `chan` to receive OS signals. (Unix only at the moment.)
+
+[cmail](https://github.com/BurntSushi/rust-cmail) is a program to periodically
+email the output of long running commands. I ported this from an
+[earlier version that I wrote in Go](https://github.com/BurntSushi/cmail).
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/UNLICENSE
@@ -0,0 +1,24 @@
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+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 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.
+
+For more information, please refer to <http://unlicense.org/>
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/benches/throughput.rs
@@ -0,0 +1,228 @@
+#![feature(test)]
+
+#[macro_use]
+extern crate chan;
+extern crate rand;
+extern crate test;
+
+use std::sync::Arc;
+use std::sync::mpsc;
+use std::thread;
+
+use rand::Rng;
+use test::Bencher;
+
+fn get_data() -> Vec<u8> {
+ rand::thread_rng().gen_iter().take(1000).collect()
+}
+
+fn get_data_sum<I: IntoIterator<Item=u8>>(xs: I) -> u64 {
+ xs.into_iter().fold(0, |sum, x| sum + (x as u64))
+}
+
+macro_rules! bench_chan_spsc {
+ ($name:ident, $cons:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let data = Arc::new(get_data());
+ let sum = get_data_sum(data.iter().cloned());
+ b.bytes = data.len() as u64;
+ b.iter(|| {
+ let data = data.clone();
+ let (s, r) = $cons;
+ thread::spawn(move || {
+ for &datum in &*data {
+ let _ = s.send(datum);
+ }
+ });
+ assert_eq!(sum, get_data_sum(r.iter()));
+ });
+ }
+ }
+}
+
+bench_chan_spsc!(spsc_chan_sync_unbuffered, chan::sync(0));
+bench_chan_spsc!(spsc_chan_sync_buffered, chan::sync(1));
+bench_chan_spsc!(spsc_chan_sync_buffered_all, chan::sync(1000));
+bench_chan_spsc!(spsc_chan_async, chan::async());
+bench_chan_spsc!(std_spsc_chan_sync_unbuffered, mpsc::sync_channel(0));
+bench_chan_spsc!(std_spsc_chan_sync_buffered, mpsc::sync_channel(1));
+bench_chan_spsc!(std_spsc_chan_sync_buffered_all, mpsc::sync_channel(1000));
+bench_chan_spsc!(std_spsc_chan_async, mpsc::channel());
+
+macro_rules! bench_chan_mpsc {
+ ($name:ident, $cons:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let data = Arc::new(get_data());
+ let sum = get_data_sum(data.iter().cloned());
+ b.bytes = data.len() as u64;
+ b.iter(|| {
+ let (s, r) = $cons;
+ for i in 0..4 {
+ let data = data.clone();
+ let s = s.clone();
+ let start = i * (data.len() / 4);
+ let end = start + (data.len() / 4);
+ thread::spawn(move || {
+ for &datum in &(&*data)[start..end] {
+ let _ = s.send(datum);
+ }
+ });
+ }
+ drop(s);
+ assert_eq!(sum, get_data_sum(r.iter()));
+ });
+ }
+ }
+}
+
+bench_chan_mpsc!(mpsc_chan_sync_unbuffered, chan::sync(0));
+bench_chan_mpsc!(mpsc_chan_sync_buffered, chan::sync(1));
+bench_chan_mpsc!(mpsc_chan_sync_buffered_all, chan::sync(1000));
+bench_chan_mpsc!(mpsc_chan_async, chan::async());
+bench_chan_mpsc!(std_mpsc_chan_sync_unbuffered, mpsc::sync_channel(0));
+bench_chan_mpsc!(std_mpsc_chan_sync_buffered, mpsc::sync_channel(1));
+bench_chan_mpsc!(std_mpsc_chan_sync_buffered_all, mpsc::sync_channel(1000));
+bench_chan_mpsc!(std_mpsc_chan_async, mpsc::channel());
+
+macro_rules! bench_select_no_init {
+ ($name:ident, $cons:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let data = Arc::new(get_data());
+ let sum = get_data_sum(data.iter().cloned());
+ b.bytes = data.len() as u64;
+ b.iter(|| {
+ let mut rs = vec![];
+ for i in 0..4 {
+ let (s, r) = $cons;
+ rs.push(r);
+ let data = data.clone();
+ let start = i * (data.len() / 4);
+ let end = start + (data.len() / 4);
+ thread::spawn(move || {
+ for &datum in &(&*data)[start..end] {
+ let _ = s.send(datum);
+ }
+ });
+ }
+ let mut recv = vec![];
+ let (r0, r1, r2, r3) = (&rs[0], &rs[1], &rs[2], &rs[3]);
+ let mut done = &mut [false, false, false, false];
+ loop {
+ chan_select! {
+ r0.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[0] = true;
+ }
+ },
+ r1.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[1] = true;
+ }
+ },
+ r2.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[2] = true;
+ }
+ },
+ r3.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[3] = true;
+ }
+ },
+ }
+ if done.iter().all(|&b| b) {
+ break;
+ }
+ }
+ assert_eq!(sum, get_data_sum(recv.into_iter()));
+ });
+ }
+ }
+}
+
+bench_select_no_init!(select_no_init_chan_sync_unbuffered, chan::sync(0));
+bench_select_no_init!(select_no_init_chan_sync_buffered, chan::sync(1));
+bench_select_no_init!(select_no_init_chan_sync_buffered_all, chan::sync(1000));
+bench_select_no_init!(select_no_init_chan_async, chan::async());
+
+macro_rules! bench_select_with_init {
+ ($name:ident, $cons:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ let data = Arc::new(get_data());
+ let sum = get_data_sum(data.iter().cloned());
+ b.bytes = data.len() as u64;
+ b.iter(|| {
+ let mut rs = vec![];
+ for i in 0..4 {
+ let (s, r) = $cons;
+ rs.push(r);
+ let data = data.clone();
+ let start = i * (data.len() / 4);
+ let end = start + (data.len() / 4);
+ thread::spawn(move || {
+ for &datum in &(&*data)[start..end] {
+ let _ = s.send(datum);
+ }
+ });
+ }
+ let mut recv = vec![];
+ let (r0, r1, r2, r3) = (&rs[0], &rs[1], &rs[2], &rs[3]);
+ let mut done = &mut [false, false, false, false];
+ let mut sel = chan::Select::new();
+ loop {
+ chan_select! {sel,
+ r0.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[0] = true;
+ }
+ },
+ r1.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[1] = true;
+ }
+ },
+ r2.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[2] = true;
+ }
+ },
+ r3.recv() -> d => {
+ if let Some(d) = d {
+ recv.push(d);
+ } else {
+ done[3] = true;
+ }
+ },
+ }
+ if done.iter().all(|&b| b) {
+ break;
+ }
+ }
+ assert_eq!(sum, get_data_sum(recv.into_iter()));
+ });
+ }
+ }
+}
+
+bench_select_with_init!(select_with_init_chan_sync_unbuffered, chan::sync(0));
+bench_select_with_init!(select_with_init_chan_sync_buffered, chan::sync(1));
+bench_select_with_init!(select_with_init_chan_sync_buffered_all, chan::sync(1000));
+bench_select_with_init!(select_with_init_chan_async, chan::async());
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/ctags.rust
@@ -0,0 +1,11 @@
+--langdef=Rust
+--langmap=Rust:.rs
+--regex-Rust=/^[ \t]*(#\[[^\]]\][ \t]*)*(pub[ \t]+)?(extern[ \t]+)?("[^"]+"[ \t]+)?(unsafe[ \t]+)?fn[ \t]+([a-zA-Z0-9_]+)/\6/f,functions,function definitions/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?type[ \t]+([a-zA-Z0-9_]+)/\2/T,types,type definitions/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?enum[ \t]+([a-zA-Z0-9_]+)/\2/g,enum,enumeration names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?struct[ \t]+([a-zA-Z0-9_]+)/\2/s,structure names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?mod[ \t]+([a-zA-Z0-9_]+)/\2/m,modules,module names/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?static[ \t]+([a-zA-Z0-9_]+)/\2/c,consts,static constants/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?trait[ \t]+([a-zA-Z0-9_]+)/\2/t,traits,traits/
+--regex-Rust=/^[ \t]*(pub[ \t]+)?impl([ \t\n]+<.*>)?[ \t]+([a-zA-Z0-9_]+)/\3/i,impls,trait implementations/
+--regex-Rust=/^[ \t]*macro_rules![ \t]+([a-zA-Z0-9_]+)/\1/d,macros,macro definitions/
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/examples/default.rs
@@ -0,0 +1,20 @@
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+use std::time::Duration;
+
+fn main() {
+ let tick = chan::tick_ms(100);
+ let boom = chan::after_ms(500);
+ loop {
+ chan_select! {
+ default => {
+ println!(" .");
+ thread::sleep(Duration::from_millis(50));
+ },
+ tick.recv() => println!("tick."),
+ boom.recv() => { println!("BOOM!"); return; },
+ }
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/examples/fibonacci.rs
@@ -0,0 +1,35 @@
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+
+use chan::{Receiver, Sender};
+
+fn fibonacci(c: Sender<u64>, quit: Receiver<()>) {
+ let (mut x, mut y) = (0, 1);
+ loop {
+ chan_select! {
+ c.send(x) => {
+ let oldx = x;
+ x = y;
+ y = oldx + y;
+ },
+ quit.recv() => {
+ println!("quit");
+ return;
+ }
+ }
+ }
+}
+
+fn main() {
+ let (csend, crecv) = chan::sync(0);
+ let (qsend, qrecv) = chan::sync(0);
+ thread::spawn(move || {
+ for _ in 0..10 {
+ println!("{}", crecv.recv().unwrap());
+ }
+ qsend.send(());
+ });
+ fibonacci(csend, qrecv);
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/examples/leaky_buffer.rs
@@ -0,0 +1,41 @@
+// From http://golang.org/doc/effective_go.html#leaky_buffer
+
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+use std::time::Duration;
+
+use chan::{Receiver, Sender};
+
+type Buffer = Vec<u8>;
+
+fn main() {
+ let (free_send, free_recv) = chan::sync(100);
+ let (serv_send, serv_recv) = chan::sync(0);
+
+ thread::spawn(move || client(free_recv, serv_send));
+ thread::spawn(move || server(free_send, serv_recv));
+ thread::sleep(Duration::from_millis(500));
+}
+
+fn client(free_list: Receiver<Buffer>, server_chan: Sender<Buffer>) {
+ loop {
+ let buf;
+ chan_select! {
+ default => buf = Vec::with_capacity(1024),
+ free_list.recv() -> b => buf = b.unwrap(),
+ }
+ server_chan.send(buf);
+ }
+}
+
+fn server(free_list: Sender<Buffer>, server_chan: Receiver<Buffer>) {
+ loop {
+ let buf = server_chan.recv().unwrap();
+ chan_select! {
+ default => {},
+ free_list.send(buf) => {},
+ }
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/examples/nested_select.rs
@@ -0,0 +1,68 @@
+// This example demonstrates how to use nested selects.
+//
+// The `select!` macro is not very good, which means you need to name the
+// channels differently in nested invocations (blech).
+//
+// The nested select here is used to "give priority" to the s1/r1 channel.
+// If you run this program, you should see lots of receives on r1 near
+// the beginning with few receives on r2. Once r1 is exhausted, r2 is finally
+// allowed to consume data.
+
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+use std::time::Duration;
+
+fn main() {
+ let (s1, r1) = chan::sync(0);
+ let (s2, r2) = chan::sync(0);
+ let (s1, s2) = (s1.clone(), s2.clone());
+ let wg = chan::WaitGroup::new();
+ wg.add(2);
+ let (wg1, wg2) = (wg.clone(), wg.clone());
+ thread::spawn(move || {
+ for i in 0..10 {
+ s1.send(i);
+ thread::sleep(Duration::from_millis(10));
+ }
+ wg1.done();
+ });
+ thread::spawn(move || {
+ for i in 0..10 {
+ s2.send(i * 5);
+ thread::sleep(Duration::from_millis(100));
+ }
+ wg2.done();
+ });
+ let done = {
+ let (s, r) = chan::sync(0);
+ thread::spawn(move || {
+ wg.wait();
+ s.send(());
+ });
+ r
+ };
+ loop {
+ let (r1b, r2b) = (&r1, &r2);
+ chan_select! {
+ default => {
+ chan_select! {
+ r1b.recv() -> v1 => match v1 {
+ None => {}
+ Some(v1) => println!("r1: {:?}", v1),
+ },
+ r2b.recv() -> v2 => match v2 {
+ None => {}
+ Some(v2) => println!("r2: {:?}", v2),
+ },
+ done.recv() => break,
+ }
+ },
+ r1.recv() -> v1 => match v1 {
+ None => {}
+ Some(v1) => println!("r1: {:?}", v1),
+ },
+ }
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/examples/web.rs
@@ -0,0 +1,69 @@
+extern crate chan;
+extern crate hyper;
+
+use std::env::args;
+use std::error::Error;
+use std::io::Read;
+use std::thread;
+
+use hyper::client::Client;
+
+fn main() {
+ let page_links = vec![
+ "http://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html",
+ "http://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html",
+ "http://doc.rust-lang.org/std/sync/struct.Arc.html",
+ "http://doc.rust-lang.org/std/sync/struct.Condvar.html",
+ "http://doc.rust-lang.org/std/sync/type.LockResult.html",
+ "http://doc.rust-lang.org/std/",
+ "http://fooledya.404",
+ "http://doc.rust-lang.org/std/macro.select!.html",
+ "http://doc.rust-lang.org/std/macro.assert!.html",
+ "http://doc.rust-lang.org/std/macro.assert_eq!.html",
+ "http://doc.rust-lang.org/std/macro.cfg!.html",
+ "http://doc.rust-lang.org/std/macro.column!.html",
+ "http://doc.rust-lang.org/std/macro.concat!.html",
+ "http://doc.rust-lang.org/std/macro.concat_idents!.html",
+ "http://doc.rust-lang.org/std/macro.debug_assert!.html",
+ "http://burntsushi.net/stuff/dne.html",
+ "http://doc.rust-lang.org/std/macro.debug_assert_eq!.html",
+ "http://doc.rust-lang.org/std/macro.env!.html",
+ "http://doc.rust-lang.org/std/macro.file!.html",
+ ];
+ let rpages = {
+ let (slinks, rlinks) = chan::sync(0);
+ let (spages, rpages) = chan::sync(0);
+ thread::spawn(move || {
+ for link in page_links {
+ slinks.send(link);
+ }
+ });
+ for _ in 0..args().nth(1).map(|s| s.parse().unwrap()).unwrap_or(4) {
+ let rlinks = rlinks.clone();
+ let spages = spages.clone();
+ thread::spawn(move || {
+ let cli = Client::new();
+ for link in rlinks {
+ spages.send((link, get_page(&cli, &link)));
+ }
+ });
+ }
+ rpages
+ };
+ for (link, page) in rpages {
+ match page {
+ Err(err) => println!("Could not fetch {}: {}", link, err),
+ Ok(page) => println!("{}, {}", page.len(), link),
+ }
+ }
+}
+
+fn get_page(cli: &Client, link: &str) -> Result<String, Box<Error+Send+Sync>> {
+ let mut resp = try!(cli.get(link).send());
+ if !resp.status.is_success() {
+ return Err(From::from(resp.status.to_string()));
+ }
+ let mut page = String::with_capacity(1024);
+ try!(resp.read_to_string(&mut page));
+ Ok(page)
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/session.vim
@@ -0,0 +1,1 @@
+au BufWritePost *.rs silent!make ctags > /dev/null 2>&1
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/src/lib.rs
@@ -0,0 +1,1760 @@
+/*!
+This crate provides an implementation of a multi-producer, multi-consumer
+channel. Channels come in three varieties:
+
+1. Asynchronous channels. Sends never block. Its buffer is only limited by the
+ available resources on the system.
+2. Synchronous buffered channels. Sends block when the buffer is full. The
+ buffer is depleted by receiving on the channel.
+3. Rendezvous channels (synchronous channels without a buffer). Sends block
+ until a receive has consumed the value sent. When a sender and receiver
+ synchronize, they are said to *rendezvous*.
+
+Asynchronous channels are created with `chan::async()`. Synchronous channels
+are created with `chan::sync(k)` where `k` is the buffer size. Rendezvous
+channels are created with `chan::sync(0)`.
+
+All channels are split into the same two types upon creation: a `Sender` and
+a `Receiver`. Additional senders and receivers can be created with reckless
+abandon by calling `clone`.
+
+When all senders are dropped, the channel is closed and no other sends are
+possible. In a channel with a buffer, receivers continue to consume values
+until the buffer is empty, at which point, a `None` value is always returned
+immediately.
+
+No special semantics are enforced when all receivers are dropped. Asynchronous
+sends will continue to work. Synchronous sends will block indefinitely when
+the buffer is full. A send on a rendezvous channel will also block
+indefinitely. (**NOTE**: This could be changed!)
+
+All channels satisfy *both* `Send` and `Sync` and can be freely mixed in
+`chan_select!`. Said differently, the synchronization semantics of a channel
+are encoded upon construction, but are otherwise indistinguishable to the
+type system.
+
+Values sent on channels are subject to the normal restrictions Rust has on
+values crossing thread boundaries. i.e., Values must implement `Send` and/or
+`Sync`. (An `Rc<T>` *cannot* be sent on a channel, but a channel can be sent
+on a channel!)
+
+
+# Example: rendezvous channel
+
+A simple example demonstrating a rendezvous channel:
+
+```
+use std::thread;
+
+let (send, recv) = chan::sync(0);
+thread::spawn(move || send.send(5));
+assert_eq!(recv.recv(), Some(5)); // blocks until the previous send occurs
+```
+
+
+# Example: synchronous channel
+
+Similarly, an example demonstrating a synchronous channel:
+
+```
+let (send, recv) = chan::sync(1);
+send.send(5); // doesn't block because of the buffer
+assert_eq!(recv.recv(), Some(5));
+```
+
+
+# Example: multiple producers and multiple consumers
+
+An example demonstrating multiple consumers and multiple producers:
+
+```
+use std::thread;
+
+let r = {
+ let (s, r) = chan::sync(0);
+ for letter in vec!['a', 'b', 'c', 'd'] {
+ let s = s.clone();
+ thread::spawn(move || {
+ for _ in 0..10 {
+ s.send(letter);
+ }
+ });
+ }
+ // This extra lexical scope will drop the initial
+ // sender we created. Thus, the channel will be
+ // closed when all threads spawned above has completed.
+ r
+};
+
+// A wait group lets us synchronize the completion of multiple threads.
+let wg = chan::WaitGroup::new();
+for _ in 0..4 {
+ wg.add(1);
+ let wg = wg.clone();
+ let r = r.clone();
+ thread::spawn(move || {
+ for letter in r {
+ println!("Received letter: {}", letter);
+ }
+ wg.done();
+ });
+}
+
+// If this was the end of the process and we didn't call `wg.wait()`, then
+// the process might quit before all of the consumers were done.
+// `wg.wait()` will block until all `wg.done()` calls have finished.
+wg.wait();
+```
+
+
+# Example: Select on multiple channel sends/receives
+
+An example showing how to use `chan_select!` to synchronize on sends
+or receives.
+
+```
+#[macro_use]
+extern crate chan;
+
+use std::thread;
+
+// Emits the fibonacci sequence on the given channel until `quit` receives
+// a sentinel value.
+fn fibonacci(s: chan::Sender<u64>, quit: chan::Receiver<()>) {
+ let (mut x, mut y) = (0, 1);
+ loop {
+ // Select will block until at least one of `s.send` or `quit.recv`
+ // is ready to succeed. At which point, it will choose exactly one
+ // send/receive to synchronize.
+ chan_select! {
+ s.send(x) => {
+ let oldx = x;
+ x = y;
+ y = oldx + y;
+ },
+ quit.recv() => {
+ println!("quit");
+ return;
+ }
+ }
+ }
+}
+
+fn main() {
+ let (s, r) = chan::sync(0);
+ let (qs, qr) = chan::sync(0);
+ // Spawn a thread and ask for the first 10 numbers in the fibonacci
+ // sequence.
+ thread::spawn(move || {
+ for _ in 0..10 {
+ println!("{}", r.recv().unwrap());
+ }
+ // Dropping all sending channels causes the receive channel to
+ // immediately and always synchronize (because the channel is closed).
+ drop(qs);
+ });
+ fibonacci(s, qr);
+}
+```
+
+
+# Example: non-blocking sends/receives
+
+This crate specifically does not expose methods like `try_send` or `try_recv`.
+Instead, you should prefer using `chan_select!` to perform a non-blocking
+send or receive. This can be done by telling select what to do when no
+synchronization events are available.
+
+```
+# #[macro_use] extern crate chan; fn main() {
+let (s, _) = chan::sync(0);
+chan_select! {
+ default => println!("Send failed."),
+ s.send("some data") => println!("Send succeeded."),
+}
+# }
+```
+
+When `chan_select!` first runs, it will check if `s.send(...)` can succeed
+*without blocking*. If so, `chan_select!` will permit the channels to
+rendezvous. However, if there is no `recv` call to accept the send, then
+`chan_select!` will immediately execute the `default` arm.
+
+
+# Example: the sentinel channel idiom
+
+When writing concurrent programs with `chan`, you will often find that you need
+to somehow "wait" until some operation is done. For example, let's say you want
+to run a function in a separate thread, but wait until it completes. Here's
+one way to do it:
+
+```rust
+use std::thread;
+
+fn do_work(done: chan::Sender<()>) {
+ // do something
+
+ // signal that we're done.
+ done.send(());
+}
+
+fn main() {
+ let (sdone, rdone) = chan::sync(0);
+ thread::spawn(move || do_work(sdone));
+ // block until work is done, and then quit the program.
+ rdone.recv();
+}
+```
+
+In effect, we've created a new channel that sends unit values. When we're
+done doing work, we send a unit value and `main` waits for it to be delivered.
+
+Another way of achieving the same thing is to simply close the channel. Once
+the channel is closed, any previously blocked receive operations become
+immediately unblocked. What's even cooler is that channels are closed
+automatically when all senders are dropped. So the new program looks something
+like this:
+
+```rust
+use std::thread;
+
+fn do_work(_done: chan::Sender<()>) {
+ // do something
+}
+
+fn main() {
+ let (sdone, rdone) = chan::sync(0);
+ thread::spawn(move || do_work(sdone));
+ // block until work is done, and then quit the program.
+ rdone.recv();
+}
+```
+
+We no longer need to explicitly do anything with the `_done` channel. We give
+`do_work` ownership of the channel, but as soon as the function stops
+executing, `_done` is dropped, the channel is closed and `rdone.recv()`
+unblocks.
+
+
+# Example: I want more!
+
+There are some examples in this crate's repository:
+https://github.com/BurntSushi/chan/tree/master/examples
+
+Here is a nice example using the `chan-signal` crate to read lines from
+stdin while gracefully quitting after receiving a `INT` or `TERM`
+signal:
+https://github.com/BurntSushi/chan-signal/blob/master/examples/read_names.rs
+
+A non-trivial program for periodically sending email with the output of
+running a command: https://github.com/BurntSushi/rust-cmail (The source is
+commented more heavily than normal.)
+
+
+# When are channel operations non-blocking?
+
+Non-blocking in this context means "a send/recv operation can synchronize
+immediately." (Under the hood, a mutex may still be acquired, which could
+block.)
+
+The following is a list of all cases where a channel operation is considered
+non-blocking:
+
+* A send on a synchronous channel whose buffer is not full.
+* A receive on a synchronous channel with a non-empty buffer.
+* A send on an asynchronous channel.
+* A rendezvous send or recv when a corresponding recv or send operation is
+already blocked, respectively.
+* A receive on any closed channel.
+
+Non-blocking semantics are important because they affect the behavior of
+`chan_select!`. In particular, a `chan_select!` with a `default` arm will
+execute the `default` case if and only if all other operations are blocked.
+
+
+# Which channel type should I use?
+
+[From Ken Kahn](http://www.eros-os.org/pipermail/e-lang/2003-January/008183.html):
+
+> About 25 years ago I went to dinner with Carl Hewitt and Robin Milner (of
+> CSS and pi calculus fame) and they were arguing about synchronous vs.
+> asynchronous communication primitives. Carl used the post office metaphor
+> while Robin used the telephone. Both quickly admitted that one can implement
+> one in the other.
+
+With three channel types to choose from, it may not always be clear which one
+you should use. In fact, there has been a long debate over which are better.
+Here are some rough guidelines:
+
+* Historically, asynchronous channels have been associated with the actor
+model, which means they're a little out of place in a library inspired by
+communicating sequential processes. Nevertheless, an unconstrained buffer can
+be occasionally useful.
+* Synchronous channels are useful because their stricter synchronization
+semantics can make it easier to reason about the flow of your program. In
+particular, with a rendezvous channel, one knows that a `send` unblocks only
+when a corresponding `recv` consumes the sent value. This makes it *feel*
+an awful lot like a function call!
+
+
+# Warning: leaks
+
+Channels can be leaked! In particular, if all receivers have been dropped,
+then any future sends will block. Usually this is indicative of a bug in your
+program.
+
+For example, consider a "generator" style pattern where a thread produces
+values on a channel and another thread consumes in an iterator.
+
+```no_run
+use std::thread;
+
+let (s, r) = chan::sync(0);
+
+thread::spawn(move || {
+ for val in r {
+ if val >= 2 {
+ break;
+ }
+ }
+});
+
+s.send(1);
+s.send(2);
+// This will deadlock because the loop in the thread
+// above quits after receiving `2`.
+s.send(3);
+```
+
+If the iterator loop quits early, the channel's buffer could fill up, which
+will indefinitely block all future send operations.
+
+(These leaks/deadlocks are detectable in most circumstances, and a `send`
+operation could be made to wake up and either return an error or panic. The
+semantics here are still experimental.)
+
+
+# Warning: more leaks
+
+It will always be possible to leak a channel in safe code regardless of the
+channel's semantics. For example:
+
+```no_run
+use std::mem::forget;
+
+let (s, r) = chan::sync::<()>(0);
+forget(s);
+// Blocks forever because the channel is never closed.
+r.recv();
+```
+
+In this case, it is impossible for the channel to close because the internal
+reference count will never reach `0`.
+
+
+# Warning: performance
+
+The primary purpose of this crate is to provide a safe, concurrent abstraction.
+Notably, it is *not* a zero-cost abstraction. It is not even a near-zero-cost
+abstraction. Throughput on a channel is startlingly low (see the benchmarks
+in this crate's repository). Therefore, the channels provided in this crate
+are most useful as a means to structure concurrent programs at a coarse level.
+
+If your requirements call for performant synchronization of data, `chan` is not
+the crate you're looking for.
+
+
+# Prior art
+
+The semantics encoded in the channels provided by this crate should mirror or
+closely mirror the semantics provided by channels in Go. This includes
+select statements! The major difference between concurrent programs written
+with `chan` and concurrent programs written with Go is that Go programs can
+benefit from being fast and loose with creating goroutines. In `chan`, each
+"goroutine" is just an OS thread.
+
+In terms of writing code:
+
+1. Go programs will feature explicit closing of channels. In `chan`, channels
+ are closed **only** when all senders have been dropped.
+2. Since there is no such thing as a "nil" channel in `chan`, the semantics Go
+ has for nil channels (both sends and receives block indefinitely) do not
+ exist in `chan`.
+3. `chan` does not expose `len` or `cap` methods. (For no reason other than
+ to start with a totally minimal API. In particular, calling `len` or `cap`
+ on a channel is often The Wrong Thing. But not always. So this restriction
+ may be lifted in the future.)
+4. In `chan`, all channels are either senders or receivers. There is no
+ "bidirectional" channel. This is manifest in how channel memory is managed:
+ channels are closed when all senders are dropped.
+
+Of course, Go is not the origin of these ideas, but it has been the
+strongest influence on the design of this library, and at least one of its
+authors has done substantial research on the integration of CSP and programming
+languages.
+*/
+
+#![deny(missing_docs)]
+
+extern crate rand;
+
+use std::collections::VecDeque;
+use std::fmt;
+use std::hash::{Hash, Hasher};
+use std::ops::Drop;
+use std::sync::{Arc, Condvar, Mutex, MutexGuard};
+use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize, Ordering};
+use std::thread;
+use std::time::Duration;
+
+use notifier::Notifier;
+pub use select::{Select, SelectRecvHandle, SelectSendHandle};
+use tracker::Tracker;
+pub use wait_group::WaitGroup;
+
+// This enables us to (in practice) uniquely identify any particular channel.
+// A better approach would be to use the pointer's address in memory, but it
+// looks like `Arc` doesn't support that (yet?).
+//
+// Any other ideas? ---AG
+//
+// N.B. This is combined with ChannelId to distinguish between the sending
+// and receiving halves of a channel.
+static NEXT_CHANNEL_ID: AtomicUsize = ATOMIC_USIZE_INIT;
+
+mod notifier;
+mod select;
+mod tracker;
+mod wait_group;
+
+/// Create a synchronous channel with a possibly empty buffer.
+///
+/// When the `size` is zero, the buffer is empty and the channel becomes a
+/// rendezvous channel. A rendezvous channel blocks send operations until
+/// a corresponding receive operation consumes the sent value.
+///
+/// When the `size` is non-zero, the send operations will only block when the
+/// buffer is full. Send operations only unblock when a receive operation
+/// removes an element from the buffer.
+///
+/// Values are guaranteed to be received in the same order that they are sent.
+///
+/// The send and receive values returned can be cloned arbitrarily (i.e.,
+/// multi-producer/multi-consumer) and moved to other threads.
+///
+/// When all senders are dropped, the channel is closed automatically. No
+/// more values may be sent on a closed channel. Once a channel is closed and
+/// the buffer is empty, all receive operations return `None` immediately.
+/// (If a channel is closed and there are still values in the buffer, then
+/// receive operations will retrieve those first.)
+///
+/// When all receivers are dropped, no special action is taken. When the buffer
+/// is full, all subsequent send operations will block indefinitely.
+///
+/// # Examples
+///
+/// An example of a rendezvous channel:
+///
+/// ```
+/// use std::thread;
+///
+/// let (send, recv) = chan::sync(0);
+/// thread::spawn(move || send.send(5));
+/// assert_eq!(recv.recv(), Some(5)); // blocks until the previous send occurs
+/// ```
+///
+/// An example of a synchronous buffered channel:
+///
+/// ```
+/// let (send, recv) = chan::sync(1);
+///
+/// send.send(5); // doesn't block because of the buffer
+/// assert_eq!(recv.recv(), Some(5));
+///
+/// drop(send); // closes the channel
+/// assert_eq!(recv.recv(), None);
+/// ```
+pub fn sync<T>(size: usize) -> (Sender<T>, Receiver<T>) {
+ let send = Channel::new(size, false);
+ let recv = send.clone();
+ (send.into_sender(), recv.into_receiver())
+}
+
+/// Create an asynchronous channel with an unbounded buffer.
+///
+/// Since the buffer is unbounded, send operations always succeed immediately.
+///
+/// Receive operations succeed only when there is at least one value in the
+/// buffer.
+///
+/// Values are guaranteed to be received in the same order that they are sent.
+///
+/// The send and receive values returned can be cloned arbitrarily (i.e.,
+/// multi-producer/multi-consumer) and moved to other threads.
+///
+/// When all senders are dropped, the channel is closed automatically. No
+/// more values may be sent on a closed channel. Once a channel is closed and
+/// the buffer is empty, all receive operations return `None` immediately.
+/// (If a channel is closed and there are still values in the buffer, then
+/// receive operations will retrieve those first.)
+///
+/// When all receivers are dropped, no special action is taken. When the buffer
+/// is full, all subsequent send operations will block indefinitely.
+///
+/// # Example
+///
+/// Asynchronous channels are nice when you just want to enqueue a bunch
+/// of values up front:
+///
+/// ```
+/// let (s, r) = chan::async();
+///
+/// for i in 0..10 {
+/// s.send(i);
+/// }
+///
+/// drop(s); // closing the channel lets the iterator stop
+/// let numbers: Vec<i32> = r.iter().collect();
+/// assert_eq!(numbers, (0..10).collect::<Vec<i32>>());
+/// ```
+///
+/// (Others should help me come up with more compelling examples of
+/// asynchronous channels.)
+pub fn async<T>() -> (Sender<T>, Receiver<T>) {
+ let send = Channel::new(0, true);
+ let recv = send.clone();
+ (send.into_sender(), recv.into_receiver())
+}
+
+/// Creates a new rendezvous channel that is dropped after a timeout.
+///
+/// When the channel is dropped, any receive operation on the returned channel
+/// will be unblocked.
+///
+/// # Example
+///
+/// ```
+/// use std::time::Duration;
+///
+/// let wait = chan::after(Duration::from_millis(1000));
+/// // Unblocks after 1 second.
+/// wait.recv();
+/// ```
+pub fn after(duration: Duration) -> Receiver<()> {
+ let (send, recv) = sync(0);
+ thread::spawn(move || {
+ thread::sleep(duration);
+ drop(send);
+ });
+ recv
+}
+
+/// Creates a new rendezvous channel that is dropped after a timeout.
+///
+/// `duration` is specified in milliseconds.
+///
+/// When the channel is dropped, any receive operation on the returned channel
+/// will be unblocked.
+///
+/// N.B. This will eventually be deprecated when we get a proper duration type.
+///
+/// # Example
+///
+/// ```
+/// let wait = chan::after_ms(1000);
+/// // Unblocks after 1 second.
+/// wait.recv();
+/// ```
+pub fn after_ms(duration: u32) -> Receiver<()> {
+ #![allow(deprecated)]
+ let (send, recv) = sync(0);
+ thread::spawn(move || {
+ thread::sleep_ms(duration);
+ drop(send);
+ });
+ recv
+}
+
+/// Creates a new rendezvous channel that is "ticked" every duration.
+///
+/// When `duration` is `0`, no ticks are ever sent.
+///
+/// When `duration` is non-zero, then a new channel is created and sent at
+/// every duration. When the sent channel is dropped, the timer is reset
+/// and the process repeats after the duration.
+///
+/// This is especially convenient because it keeps the ticking in sync with
+/// the code that uses it. Namely, the ticks won't "build up."
+///
+/// N.B. There is no way to reclaim the resources used by this function.
+/// If you stop receiving on the channel returned, then the thread spawned by
+/// `tick_ms` will block indefinitely.
+///
+/// # Examples
+///
+/// This is most useful when used in `chan_select!` because the received
+/// sentinel channel gets dropped only after the correspond arm has
+/// executed. At which point, the ticker is reset and waits to tick until
+/// `duration` milliseconds lapses *after* the `chan_select!` arm is executed.
+///
+/// ```
+/// # #[macro_use] extern crate chan; fn main() {
+/// use std::thread;
+/// use std::time::Duration;
+///
+/// let tick = chan::tick(Duration::from_millis(100));
+/// let boom = chan::after(Duration::from_millis(500));
+/// loop {
+/// chan_select! {
+/// default => {
+/// println!(" .");
+/// thread::sleep(Duration::from_millis(50));
+/// },
+/// tick.recv() => println!("tick."),
+/// boom.recv() => { println!("BOOM!"); return; },
+/// }
+/// }
+/// # }
+/// ```
+pub fn tick(duration: Duration) -> Receiver<Sender<()>> {
+ let (send, recv) = sync(0);
+ if duration.as_secs() == 0 && duration.subsec_nanos() == 0 {
+ // Leak the send channel so that it never gets closed and
+ // `recv` never synchronizes.
+ ::std::mem::forget(send);
+ } else {
+ thread::spawn(move || {
+ loop {
+ thread::sleep(duration);
+ let (sdone, rdone) = sync(0);
+ send.send(sdone);
+ // Block until `sdone` gets closed by the caller.
+ rdone.recv();
+ }
+ });
+ }
+ recv
+}
+
+/// Creates a new rendezvous channel that is "ticked" every duration.
+///
+/// `duration` is specified in milliseconds.
+///
+/// When `duration` is `0`, no ticks are ever sent.
+///
+/// When `duration` is non-zero, then a new channel is created and sent at
+/// every duration. When the sent channel is dropped, the timer is reset
+/// and the process repeats after the duration.
+///
+/// This is especially convenient because it keeps the ticking in sync with
+/// the code that uses it. Namely, the ticks won't "build up."
+///
+/// N.B. There is no way to reclaim the resources used by this function.
+/// If you stop receiving on the channel returned, then the thread spawned by
+/// `tick_ms` will block indefinitely.
+///
+/// # Examples
+///
+/// This is most useful when used in `chan_select!` because the received
+/// sentinel channel gets dropped only after the correspond arm has
+/// executed. At which point, the ticker is reset and waits to tick until
+/// `duration` milliseconds lapses *after* the `chan_select!` arm is executed.
+///
+/// ```
+/// # #[macro_use] extern crate chan; fn main() {
+/// use std::thread;
+/// use std::time::Duration;
+///
+/// let tick = chan::tick_ms(100);
+/// let boom = chan::after_ms(500);
+/// loop {
+/// chan_select! {
+/// default => {
+/// println!(" .");
+/// thread::sleep(Duration::from_millis(50));
+/// },
+/// tick.recv() => println!("tick."),
+/// boom.recv() => { println!("BOOM!"); return; },
+/// }
+/// }
+/// # }
+/// ```
+pub fn tick_ms(duration: u32) -> Receiver<Sender<()>> {
+ #![allow(deprecated)]
+ let (send, recv) = sync(0);
+ if duration == 0 {
+ // Leak the send channel so that it never gets closed and
+ // `recv` never synchronizes.
+ ::std::mem::forget(send);
+ } else {
+ thread::spawn(move || {
+ loop {
+ thread::sleep_ms(duration);
+ let (sdone, rdone) = sync(0);
+ send.send(sdone);
+ // Block until `sdone` gets closed by the caller.
+ rdone.recv();
+ }
+ });
+ }
+ recv
+}
+
+/// A value that uniquely identifies one half of a channel.
+///
+/// For any `s: Sender<T>`, `s.id() == s.clone().id()`. Similarly for
+/// any `r: Receiver<T>`.
+#[doc(hidden)]
+#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct ChannelId(ChannelKey);
+
+#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+enum ChannelKey {
+ Sender(u64),
+ Receiver(u64),
+}
+
+impl ChannelId {
+ fn sender(id: u64) -> ChannelId {
+ ChannelId(ChannelKey::Sender(id))
+ }
+
+ fn receiver(id: u64) -> ChannelId {
+ ChannelId(ChannelKey::Receiver(id))
+ }
+}
+
+/// An iterator over values received in a channel.
+pub struct Iter<T> {
+ chan: Receiver<T>,
+}
+
+impl<T> Iterator for Iter<T> {
+ type Item = T;
+ fn next(&mut self) -> Option<T> { self.chan.recv() }
+}
+
+impl<T> IntoIterator for Receiver<T> {
+ type Item = T;
+ type IntoIter = Iter<T>;
+ fn into_iter(self) -> Iter<T> { Iter { chan: self } }
+}
+
+impl<'a, T> IntoIterator for &'a Receiver<T> {
+ type Item = T;
+ type IntoIter = Iter<T>;
+ fn into_iter(self) -> Iter<T> { self.iter() }
+}
+
+/// The sending half of a channel.
+///
+/// Senders can be cloned any number of times and sent to other threads.
+///
+/// Senders also implement `Sync`, which means they can be shared among threads
+/// without cloning if the channels can be proven to outlive the execution
+/// of the threads.
+///
+/// When all sending halves of a channel are dropped, the channel is closed
+/// automatically. When a channel is closed, no new values can be sent on the
+/// channel. Also, all receive operations either return any values left in the
+/// buffer or return immediately with `None`.
+#[derive(Debug)]
+pub struct Sender<T>(Channel<T>);
+
+/// The receiving half of a channel.
+///
+/// Receivers can be cloned any number of times and sent to other threads.
+///
+/// Receivers also implement `Sync`, which means they can be shared among
+/// threads without cloning if the channels can be proven to outlive the
+/// execution of the threads.
+///
+/// When all receiving halves of a channel are dropped, no special action is
+/// taken. If the buffer in the channel is full, all sends will block
+/// indefinitely.
+#[derive(Debug)]
+pub struct Receiver<T>(Channel<T>);
+
+/// All senders and receivers are just newtypes around a more base channel.
+///
+/// i.e., All senders and receivers have direct access to any underlying
+/// buffer.
+#[derive(Debug)]
+struct Channel<T>(Arc<Inner<T>>);
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+enum ChannelType {
+ Async,
+ Rendezvous,
+ Buffered,
+}
+
+struct Inner<T> {
+ /// An auto-incrementing id.
+ id: u64,
+ /// Manages subscriptions to channels (e.g., from a `chan_select!`).
+ notify: Notifier,
+ /// Tracks reference counts of senders and receivers.
+ track: Tracker,
+ /// A condition variable on the contents of `data`.
+ cond: Condvar,
+ /// The capacity of a synchronous buffer. This corresponds to the number
+ /// of elements allowed in the buffer before send operations block.
+ ///
+ /// For asynchronous and rendezvous channels, this is always 0.
+ cap: usize,
+ /// The type of the channel.
+ ty: ChannelType,
+ /// Synchronized data in the channel. e.g., the queued values.
+ data: Mutex<Data<T>>,
+}
+
+#[derive(Debug)]
+struct Data<T> {
+ /// Whether the channel is closed or not. Once set to `true` it can never
+ /// be changed.
+ closed: bool,
+ /// The number of senders waiting. (Currently only used in rendezvous
+ /// channels.)
+ waiting_send: usize,
+ /// The number of receivers waiting. (Currently only used in rendezvous
+ /// channels.)
+ waiting_recv: usize,
+ /// The actual data stored by the user.
+ user: UserData<T>,
+}
+
+#[derive(Debug)]
+enum UserData<T> {
+ /// Used for rendezvous channels. We only need to ever store one value.
+ One(Option<T>),
+ /// A ring buffer for synchronous channels.
+ /// There's definitely a more efficient representation, but I don't think
+ /// we really care.
+ Ring { queue: Vec<Option<T>>, pos: usize, len: usize },
+ /// An unbounded queue for asynchronous channels.
+ Queue(VecDeque<T>),
+}
+
+// The SendOp and RecvOp types unify the return values of all channel
+// operations. Their primary purpose is to permit the caller to retrieve the
+// channel's lock after the channel operation is done without the lock ever
+// being released. (This is critical functionality for `Select`.)
+//
+// N.B. The `WouldBlock` variants are only constructed if a non-blocking
+// operation is used (i.e., try_send or try_recv).
+
+struct SendOp<'a, T: 'a> {
+ lock: MutexGuard<'a, Data<T>>,
+ kind: SendOpKind<T>,
+}
+
+#[derive(Debug)]
+enum SendOpKind<T> {
+ Ok,
+ Closed(T),
+ WouldBlock(T),
+}
+
+struct RecvOp<'a, T: 'a> {
+ lock: MutexGuard<'a, Data<T>>,
+ kind: RecvOpKind<T>,
+}
+
+#[derive(Debug)]
+enum RecvOpKind<T> {
+ Ok(T),
+ Closed,
+ WouldBlock,
+}
+
+impl<T> Sender<T> {
+ /// Send a value on this channel.
+ ///
+ /// If this is an asnychronous channel, `send` never blocks.
+ ///
+ /// If this is a synchronous channel, `send` only blocks when the buffer
+ /// is full.
+ ///
+ /// If this is a rendezvous channel, `send` blocks until a corresponding
+ /// `recv` retrieves `val`.
+ ///
+ /// Values are guaranteed to be received in the same order that they
+ /// are sent.
+ ///
+ /// This operation will never `panic!` but it can deadlock.
+ pub fn send(&self, val: T) {
+ self.send_op(self.inner().lock(), false, val).unwrap()
+ }
+
+ fn try_send(&self, val: T) -> Result<(), T> {
+ self.send_op(self.inner().lock(), true, val).into_result()
+ }
+
+ fn send_op<'a>(
+ &'a self,
+ data: MutexGuard<'a, Data<T>>,
+ try: bool,
+ val: T,
+ ) -> SendOp<'a, T> {
+ match self.inner().ty {
+ ChannelType::Async => self.inner().async_send(data, val),
+ ChannelType::Rendezvous => {
+ self.inner().rendezvous_send(data, try, val)
+ }
+ ChannelType::Buffered => {
+ self.inner().buffered_send(data, try, val)
+ }
+ }
+ }
+
+ fn inner(&self) -> &Inner<T> {
+ &(self.0).0
+ }
+
+ fn id(&self) -> ChannelId {
+ ChannelId::sender(self.inner().id)
+ }
+}
+
+impl<T> Receiver<T> {
+ /// Receive a value on this channel.
+ ///
+ /// If this is an asnychronous channel, `recv` only blocks when the
+ /// buffer is empty.
+ ///
+ /// If this is a synchronous channel, `recv` only blocks when the buffer
+ /// is empty.
+ ///
+ /// If this is a rendezvous channel, `recv` blocks until a corresponding
+ /// `send` sends a value.
+ ///
+ /// For all channels, if the channel is closed and the buffer is empty,
+ /// then `recv` always and immediately returns `None`. (If the buffer is
+ /// non-empty on a closed channel, then values from the buffer are
+ /// returned.)
+ ///
+ /// Values are guaranteed to be received in the same order that they
+ /// are sent.
+ ///
+ /// This operation will never `panic!` but it can deadlock if the channel
+ /// is never closed.
+ pub fn recv(&self) -> Option<T> {
+ self.recv_op(self.inner().lock(), false).unwrap()
+ }
+
+ fn try_recv(&self) -> Result<Option<T>, ()> {
+ self.recv_op(self.inner().lock(), true).into_result()
+ }
+
+ fn recv_op<'a>(
+ &'a self,
+ data: MutexGuard<'a, Data<T>>,
+ try: bool,
+ ) -> RecvOp<'a, T> {
+ self.inner().recv(data, try)
+ }
+
+ /// Return an iterator for receiving values on this channel.
+ ///
+ /// This iterator yields values (blocking if necessary) until the channel
+ /// is closed.
+ pub fn iter(&self) -> Iter<T> { Iter { chan: self.clone() } }
+
+ fn inner(&self) -> &Inner<T> {
+ &(self.0).0
+ }
+
+ fn id(&self) -> ChannelId {
+ ChannelId::receiver(self.inner().id)
+ }
+}
+
+impl<T> Channel<T> {
+ fn new(size: usize, async: bool) -> Channel<T> {
+ let (user, ty) = if async {
+ (
+ UserData::Queue(VecDeque::with_capacity(1024)),
+ ChannelType::Async,
+ )
+ } else if size == 0 {
+ (UserData::One(None), ChannelType::Rendezvous)
+ } else {
+ let mut queue = Vec::with_capacity(size);
+ for _ in 0..size { queue.push(None); }
+ (
+ UserData::Ring { queue: queue, pos: 0, len: 0 },
+ ChannelType::Buffered,
+ )
+ };
+ Channel(Arc::new(Inner {
+ id: NEXT_CHANNEL_ID.fetch_add(1, Ordering::SeqCst) as u64,
+ notify: Notifier::new(),
+ track: Tracker::new(),
+ cond: Condvar::new(),
+ cap: size,
+ ty: ty,
+ data: Mutex::new(Data {
+ closed: false,
+ waiting_send: 0,
+ waiting_recv: 0,
+ user: user,
+ }),
+ }))
+ }
+
+ fn into_sender(self) -> Sender<T> {
+ self.0.track.add_sender();
+ Sender(self)
+ }
+
+ fn into_receiver(self) -> Receiver<T> {
+ self.0.track.add_receiver();
+ Receiver(self)
+ }
+}
+
+impl<T> Inner<T> {
+ fn lock(&self) -> MutexGuard<Data<T>> {
+ self.data.lock().unwrap()
+ }
+
+ fn close(&self) {
+ let mut data = self.lock();
+ data.closed = true;
+ self.notify();
+ }
+
+ fn notify(&self) {
+ self.cond.notify_all();
+ self.notify.notify();
+ }
+
+ // The following are all of the core channel operations wrapped up in a
+ // pretty bow. They all follow a reasonably similar pattern (with the
+ // rendezvous `send` diverging the most) which is roughly:
+ //
+ // 1. Accept locked access to the channel's data.
+ // 2. Check if the operation can continue. (For sends, we block if the
+ // buffer is full. For receives, we block if the buffer is empty.)
+ // 2a. If we need to block, then we release the mutex given to us and
+ // block on a condition variable.
+ // 2b. When awoken, go to (2).
+ // 3. If we don't need to block, then we are guaranteed to synchronize*
+ // either by adding a value to the buffer or removing a value.
+ // 4. Wake all other senders and receivers that are blocked on the
+ // same condition variable mentioned in (2a).
+ //
+ // * Not true for sending on rendezvous channels, since we need to make
+ // sure that a recv consumes the value.
+ //
+ // Interestingly, the recv operation for all three types of channels
+ // is exactly the same (modulo the underlying data structure).
+
+ fn recv<'a>(
+ &'a self,
+ mut data: MutexGuard<'a, Data<T>>,
+ try: bool,
+ ) -> RecvOp<'a, T> {
+ while data.user.len() == 0 {
+ if data.closed {
+ return RecvOp::closed(data);
+ }
+ if try {
+ return RecvOp::blocked(data);
+ }
+ if self.ty == ChannelType::Rendezvous {
+ self.notify();
+ }
+ data.waiting_recv += 1;
+ data = self.cond.wait(data).unwrap();
+ data.waiting_recv -= 1;
+ }
+ let val = data.user.pop();
+ self.notify();
+ RecvOp::ok(data, val)
+ }
+
+ // The asynchronous send is the easiest. Just push the data and notify.
+ fn async_send<'a>(
+ &'a self,
+ mut data: MutexGuard<'a, Data<T>>,
+ val: T,
+ ) -> SendOp<'a, T> {
+ data.user.push(val);
+ self.notify();
+ SendOp::ok(data)
+ }
+
+ // Buffered send is pretty much the dual of recv.
+ fn buffered_send<'a>(
+ &'a self,
+ mut data: MutexGuard<'a, Data<T>>,
+ try: bool,
+ val: T,
+ ) -> SendOp<'a, T> {
+ while data.user.len() == self.cap {
+ if data.closed {
+ return SendOp::closed(data, val);
+ }
+ if try {
+ return SendOp::blocked(data, val);
+ }
+ data = self.cond.wait(data).unwrap();
+ }
+ if data.closed {
+ return SendOp::closed(data, val);
+ }
+ data.user.push(val);
+ self.notify();
+ SendOp::ok(data)
+ }
+
+ // Rendezvous send is the trickiest because we need to:
+ //
+ // 1) Make sure no other senders interfere. We do this by ensuring
+ // that there are no other waiting senders before trying to
+ // synchronize with a receiver.
+ // 2) Wait for a receiver to consume the sent value. We do this by
+ // waiting on the condition variable until the value we put
+ // in the buffer is gone.
+ fn rendezvous_send<'a>(
+ &'a self,
+ mut data: MutexGuard<'a, Data<T>>,
+ try: bool,
+ val: T,
+ ) -> SendOp<'a, T> {
+ while data.waiting_send == 1 || data.user.len() == 1 {
+ if try {
+ return SendOp::blocked(data, val);
+ }
+ data = self.cond.wait(data).unwrap();
+ }
+ // invariant: at most one sender can be here.
+ if data.closed {
+ return SendOp::closed(data, val);
+ }
+ if try && data.waiting_recv == 0 {
+ return SendOp::blocked(data, val);
+ }
+ data.user.push(val);
+ // We need to wake up any blocked receivers so they get a chance to
+ // grab the value we pushed.
+ self.notify();
+ while data.user.len() == 1 {
+ data.waiting_send += 1;
+ data = self.cond.wait(data).unwrap();
+ data.waiting_send -= 1;
+ }
+ // And now we need to make sure we wake up any previous blocked
+ // senders so they get a shot at synchronizing.
+ self.notify();
+ SendOp::ok(data)
+ }
+}
+
+impl<T> UserData<T> {
+ fn push(&mut self, val: T) {
+ match *self {
+ UserData::One(ref mut val_loc) => *val_loc = Some(val),
+ UserData::Ring { ref mut queue, pos, ref mut len } => {
+ let cap = queue.len();
+ assert!(*len < cap);
+ queue[(pos + *len) % cap] = Some(val);
+ *len += 1;
+ }
+ UserData::Queue(ref mut deque) => deque.push_back(val),
+ }
+ }
+
+ fn pop(&mut self) -> T {
+ match *self {
+ UserData::One(ref mut val) => val.take().unwrap(),
+ UserData::Ring { ref mut queue, ref mut pos, ref mut len } => {
+ let cap = queue.len();
+ assert!(*len <= cap);
+ assert!(*len > 0);
+ let val = queue[*pos].take().expect("non-null item in queue");
+ *pos = (*pos + 1) % cap;
+ *len -= 1;
+ val
+ }
+ UserData::Queue(ref mut deque) => deque.pop_front().unwrap(),
+ }
+ }
+
+ fn len(&self) -> usize {
+ match *self {
+ UserData::One(ref val) => if val.is_some() { 1 } else { 0 },
+ UserData::Ring { len, .. } => len,
+ UserData::Queue(ref deque) => deque.len(),
+ }
+ }
+}
+
+impl<'a, T> SendOp<'a, T> {
+ fn ok(lock: MutexGuard<'a, Data<T>>) -> SendOp<'a, T> {
+ SendOp { lock: lock, kind: SendOpKind::Ok }
+ }
+
+ fn closed(lock: MutexGuard<'a, Data<T>>, val: T) -> SendOp<'a, T> {
+ SendOp { lock: lock, kind: SendOpKind::Closed(val) }
+ }
+
+ fn blocked(lock: MutexGuard<'a, Data<T>>, val: T) -> SendOp<'a, T> {
+ SendOp { lock: lock, kind: SendOpKind::WouldBlock(val) }
+ }
+
+ fn unwrap(self) {
+ self.into_result().ok().unwrap();
+ }
+
+ fn into_result(self) -> Result<(), T> {
+ self.into_result_lock().1
+ }
+
+ fn into_result_lock(self) -> (MutexGuard<'a, Data<T>>, Result<(), T>) {
+ match self.kind {
+ SendOpKind::Ok => (self.lock, Ok(())),
+ SendOpKind::WouldBlock(val) => (self.lock, Err(val)),
+ SendOpKind::Closed(_) => {
+ // If we're here, then there was a `send` on a closed
+ // channel. But the only way a channel gets closed is if
+ // all values that can `send` have been dropped.
+ //
+ // Unless there's a way to cause a destructor to run while
+ // still retaining a valid reference to the sender, this should
+ // be impossible (or there's a bug in my code).
+ drop(self.lock); // avoid poisoning?
+ panic!("cannot send on a closed channel");
+ }
+ }
+ }
+}
+
+impl<'a, T> RecvOp<'a, T> {
+ fn ok(lock: MutexGuard<'a, Data<T>>, val: T) -> RecvOp<'a, T> {
+ RecvOp { lock: lock, kind: RecvOpKind::Ok(val) }
+ }
+
+ fn closed(lock: MutexGuard<'a, Data<T>>) -> RecvOp<'a, T> {
+ RecvOp { lock: lock, kind: RecvOpKind::Closed }
+ }
+
+ fn blocked(lock: MutexGuard<'a, Data<T>>) -> RecvOp<'a, T> {
+ RecvOp { lock: lock, kind: RecvOpKind::WouldBlock }
+ }
+
+ fn unwrap(self) -> Option<T> {
+ self.into_result().ok().unwrap()
+ }
+
+ fn into_result(self) -> Result<Option<T>, ()> {
+ self.into_result_lock().1
+ }
+
+ fn into_result_lock(self)
+ -> (MutexGuard<'a, Data<T>>, Result<Option<T>, ()>) {
+ (self.lock, match self.kind {
+ RecvOpKind::Ok(val) => Ok(Some(val)),
+ RecvOpKind::WouldBlock => Err(()),
+ RecvOpKind::Closed => Ok(None),
+ })
+ }
+}
+
+impl<T> Clone for Channel<T> {
+ fn clone(&self) -> Channel<T> {
+ Channel(self.0.clone())
+ }
+}
+
+impl<T> Clone for Sender<T> {
+ fn clone(&self) -> Sender<T> {
+ self.0.clone().into_sender()
+ }
+}
+
+impl<T> Clone for Receiver<T> {
+ fn clone(&self) -> Receiver<T> {
+ self.0.clone().into_receiver()
+ }
+}
+
+impl<T> Drop for Sender<T> {
+ fn drop(&mut self) {
+ self.inner().track.remove_sender(|| self.inner().close());
+ }
+}
+
+impl<T> Drop for Receiver<T> {
+ fn drop(&mut self) {
+ self.inner().track.remove_receiver(|| ());
+ }
+}
+
+impl<T> Hash for Sender<T> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.id().hash(state);
+ }
+}
+
+impl<T> Hash for Receiver<T> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.id().hash(state);
+ }
+}
+
+impl<T> PartialEq for Sender<T> {
+ fn eq(&self, other: &Sender<T>) -> bool {
+ self.id() == other.id()
+ }
+}
+
+
+impl<T> PartialEq for Receiver<T> {
+ fn eq(&self, other: &Receiver<T>) -> bool {
+ self.id() == other.id()
+ }
+}
+
+impl<T> Eq for Sender<T> {}
+impl<T> Eq for Receiver<T> {}
+
+impl<T: fmt::Debug> fmt::Debug for Inner<T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let data = self.data.lock().unwrap();
+ try!(writeln!(f, "SyncInner {{"));
+ try!(writeln!(f, " id: {:?},", self.id));
+ try!(writeln!(f, " cap: {:?},", self.cap));
+ try!(writeln!(f, " notify: {:?},", self.notify));
+ try!(writeln!(f, " data: {:?},", &*data));
+ write!(f, "}}")
+ }
+}
+
+/// Synchronize on at most one channel send or receive operation.
+///
+/// This is a *heterogeneous* select. Namely, it supports any mix of
+/// asynchronous, synchronous or rendezvous channels, any mix of send or
+/// receive operations and any mix of types on channels.
+///
+/// Here is how select operates:
+///
+/// 1. It first examines all send and receive operations. If one or more of
+/// them can succeed without blocking, then it randomly selects *one*,
+/// executes the operation and runs the code in the corresponding arm.
+/// 2. If all operations are blocked and there is a `default` arm, then the
+/// code in the `default` arm is executed.
+/// 3. If all operations are blocked and there is no `default` arm, then
+/// `Select` will subscribe to all channels involved. `Select` will be
+/// notified when state in one of the channels has changed. This will wake
+/// `Select` up, and it will retry the steps in (1). If all operations remain
+/// blocked, then (3) is repeated.
+///
+///
+/// # Example
+///
+/// Which one synchronizes first?
+///
+/// ```
+/// # #[macro_use] extern crate chan; fn main() {
+/// use std::thread;
+///
+/// let (asend, arecv) = chan::sync(0);
+/// let (bsend, brecv) = chan::sync(0);
+///
+/// thread::spawn(move || asend.send(5));
+/// thread::spawn(move || brecv.recv());
+///
+/// chan_select! {
+/// arecv.recv() -> val => {
+/// println!("arecv received: {:?}", val);
+/// },
+/// bsend.send(10) => {
+/// println!("bsend sent");
+/// },
+/// }
+/// # }
+/// ```
+///
+/// See the "failure modes" section below for more examples of the syntax.
+///
+///
+/// # Example: empty select
+///
+/// An empty select, `chan_select! {}` will block indefinitely.
+///
+///
+/// # Warning
+///
+/// `chan_select!` is simultaneously the most wonderful and horrifying thing
+/// in this crate.
+///
+/// It is wonderful because it is essential for the
+/// composition of channel operations in a concurrent program. Without select,
+/// channels becomes much less expressive.
+///
+/// It is horrifying because the macro used to define it is *extremely*
+/// sensitive. My hope is that it is simply my own lack of creativity at fault
+/// and that others can help me fix it, but we may just be fundamentally stuck
+/// with something like this until a proper compiler plugin can rescue us.
+///
+///
+/// # Failure modes
+///
+/// When I say that this macro is sensitive, what I mean is, "if you misstep
+/// on the syntax, you will be slapped upside the head with an irrelevant
+/// error message."
+///
+/// Consider this:
+///
+/// ```ignore
+/// chan_select! {
+/// default => {
+/// println!(" .");
+/// thread::sleep(Duration::from_millis(50));
+/// }
+/// tick.recv() => println!("tick."),
+/// boom.recv() => { println!("BOOM!"); return; },
+/// }
+/// ```
+///
+/// The compiler will tell you that the "recursion limit reached while
+/// expanding the macro."
+///
+/// The actual problem is that **every** arm requires a trailing comma,
+/// regardless of whether the arm is wrapped in a `{ ... }` or not. So it
+/// should be written `default => { ... },`. (I'm told that various highly
+/// skilled individuals could remove this restriction.)
+///
+/// Here's another. Can you spot the problem? I swear it's not commas this
+/// time.
+///
+/// ```ignore
+/// chan_select! {
+/// tick.recv() => println!("tick."),
+/// boom.recv() => { println!("BOOM!"); return; },
+/// default => {
+/// println!(" .");
+/// thread::sleep(Duration::from_millis(50));
+/// },
+/// }
+/// ```
+///
+/// This produces the same "recursion limit" error as above.
+///
+/// The actual problem is that the `default` arm *must* come first (or it must
+/// be omitted completely).
+///
+/// Yet another:
+///
+/// ```ignore
+/// chan_select! {
+/// default => {
+/// println!(" .");
+/// thread::sleep(Duration::from_millis(50));
+/// },
+/// tick().recv() => println!("tick."),
+/// boom.recv() => { println!("BOOM!"); return; },
+/// }
+/// ```
+///
+/// Again, you'll get the same "recursion limit" error.
+///
+/// The actual problem is that the channel operations must be of the form
+/// `ident.recv()` or `ident.send()`. You cannot use an arbitrary expression
+/// in place of `ident` that evaluates to a channel! To fix this, you must
+/// rebind `tick()` to an identifier outside of `chan_select!`.
+#[macro_export]
+macro_rules! chan_select {
+ ($select:ident, default => $default:expr, $(
+ $chan:ident.$meth:ident($($send:expr)*)
+ $(-> $name:pat)* => $code:expr,
+ )+) => {
+ chan_select!(
+ $select,
+ default => $default,
+ $($chan.$meth($($send)*) $(-> $name)* => $code),+);
+ };
+ ($select:ident, default => $default:expr, $(
+ $chan:ident.$meth:ident($($send:expr)*)
+ $(-> $name:pat)* => $code:expr
+ ),+) => {{
+ let sel = &mut $select;
+ $(let $chan = sel.$meth(&$chan $(, $send)*);)+
+ let which = sel.try_select();
+ $(if which == Some($chan.id()) {
+ $(let $name = $chan.into_value();)*
+ $code
+ } else)+
+ { $default }
+ }};
+ ($select:ident, $(
+ $chan:ident.$meth:ident($($send:expr)*)
+ $(-> $name:pat)* => $code:expr,
+ )+) => {
+ chan_select!(
+ $select,
+ $($chan.$meth($($send)*) $(-> $name)* => $code),+);
+ };
+ ($select:ident, $(
+ $chan:ident.$meth:ident($($send:expr)*)
+ $(-> $name:pat)* => $code:expr
+ ),+) => {{
+ let sel = &mut $select;
+ $(let $chan = sel.$meth(&$chan $(, $send)*);)+
+ let which = sel.select();
+ $(if which == $chan.id() {
+ $(let $name = $chan.into_value();)*
+ $code
+ } else)+
+ { unreachable!() }
+ }};
+ (default => $default:expr) => {{ $default }};
+ (default => $default:expr,) => {{ $default }};
+ ($select:ident, default => $default:expr) => {{ $default }};
+ ($select:ident, default => $default:expr,) => {{ $default }};
+ ($select:ident) => {{
+ let sel = &mut $select;
+ sel.select(); // blocks forever
+ }};
+ () => {{
+ let sel = $crate::Select::new();
+ chan_select!(sel);
+ }};
+ ($($tt:tt)*) => {{
+ let mut sel = $crate::Select::new();
+ chan_select!(sel, $($tt)*);
+ }};
+}
+
+#[cfg(test)]
+mod tests {
+ use std::thread;
+ use std::time::Duration;
+
+ use super::{WaitGroup, async, sync};
+
+ #[test]
+ fn simple() {
+ let (send, recv) = sync(1);
+ send.send(5);
+ assert_eq!(recv.recv(), Some(5));
+ }
+
+ #[test]
+ fn simple_rendezvous() {
+ let (send, recv) = sync(0);
+ thread::spawn(move || send.send(5));
+ assert_eq!(recv.recv(), Some(5));
+ }
+
+ #[test]
+ fn simple_async() {
+ let (send, recv) = async();
+ send.send(5);
+ assert_eq!(recv.recv(), Some(5));
+ }
+
+ #[test]
+ fn simple_iter() {
+ let (send, recv) = sync(1);
+ thread::spawn(move || {
+ for i in 0..100 {
+ send.send(i);
+ }
+ });
+ let recvd: Vec<i32> = recv.iter().collect();
+ assert_eq!(recvd, (0..100).collect::<Vec<i32>>());
+ }
+
+ #[test]
+ fn simple_iter_rendezvous() {
+ let (send, recv) = sync(0);
+ thread::spawn(move || {
+ for i in 0..100 {
+ send.send(i);
+ }
+ });
+ let recvd: Vec<i32> = recv.iter().collect();
+ assert_eq!(recvd, (0..100).collect::<Vec<i32>>());
+ }
+
+ #[test]
+ fn simple_iter_async() {
+ let (send, recv) = async();
+ thread::spawn(move || {
+ for i in 0..100 {
+ send.send(i);
+ }
+ });
+ let recvd: Vec<i32> = recv.iter().collect();
+ assert_eq!(recvd, (0..100).collect::<Vec<i32>>());
+ }
+
+ #[test]
+ fn simple_try() {
+ let (send, recv) = sync(1);
+ send.try_send(5).is_err();
+ recv.try_recv().is_err();
+ }
+
+ #[test]
+ fn simple_try_rendezvous() {
+ let (send, recv) = sync(0);
+ send.try_send(5).is_err();
+ recv.try_recv().is_err();
+ }
+
+ #[test]
+ fn simple_try_async() {
+ let (send, recv) = async();
+ recv.try_recv().is_err();
+ send.try_send(5).is_ok();
+ }
+
+ #[test]
+ fn select_manual() {
+ let (s1, r1) = sync(1);
+ let (s2, r2) = sync(1);
+ s1.send(1);
+ s2.send(2);
+
+ let mut sel = ::Select::new();
+ let sel = &mut sel;
+ let c1 = sel.recv(&r1);
+ let c2 = sel.recv(&r2);
+ let which = sel.select();
+ if which == c1.id() {
+ println!("r1");
+ } else if which == c2.id() {
+ println!("r2");
+ } else {
+ unreachable!();
+ }
+ }
+
+ #[test]
+ fn select() {
+ let (sticka, rticka) = sync(1);
+ let (stickb, rtickb) = sync(1);
+ let (stickc, rtickc) = sync(1);
+ let (send, recv) = sync(0);
+ thread::spawn(move || {
+ loop {
+ sticka.send("ticka");
+ thread::sleep(Duration::from_millis(100));
+ println!("RECV: {:?}", recv.recv());
+ }
+ });
+ thread::spawn(move || {
+ loop {
+ stickb.send("tickb");
+ thread::sleep(Duration::from_millis(50));
+ }
+ });
+ thread::spawn(move || {
+ thread::sleep(Duration::from_millis(1000));
+ stickc.send(());
+ });
+
+ loop {
+ let mut stop = false;
+ chan_select! {
+ rticka.recv() -> val => println!("{:?}", val),
+ rtickb.recv() -> val => println!("{:?}", val),
+ rtickc.recv() => stop = true,
+ send.send("fubar".to_owned()) => println!("SENT!"),
+ }
+ if stop {
+ break;
+ }
+ }
+ println!("select done!");
+ }
+
+ // Regression test: https://github.com/BurntSushi/chan/issues/6
+ #[test]
+ fn select_no_leak_recv() {
+ let (s0, r0) = sync::<i32>(0);
+ let s1 = s0.clone();
+ thread::spawn(move || {
+ thread::sleep(Duration::from_millis(500));
+ s1.send(1);
+ });
+
+ // No subscriptions made yet.
+ assert_eq!(s0.inner().notify.len(), 0);
+
+ {
+ let mut sel = ::Select::new();
+ let sel = &mut sel;
+ let c = sel.recv(&r0);
+ assert_eq!(c.id(), sel.select());
+ // Select hasn't been dropped yet and therefore hasn't
+ // unsubscribed.
+ assert_eq!(s0.inner().notify.len(), 1);
+ }
+
+ // Select should have been dropped and should have unsubscribed itself.
+ assert_eq!(s0.inner().notify.len(), 0);
+ }
+
+ // Regression test: https://github.com/BurntSushi/chan/issues/6
+ #[test]
+ fn select_no_leak_send() {
+ let (s0, r0) = sync::<i32>(0);
+ let r1 = r0.clone();
+ thread::spawn(move || {
+ thread::sleep(Duration::from_millis(500));
+ r1.recv();
+ });
+
+ // No subscriptions made yet.
+ assert_eq!(s0.inner().notify.len(), 0);
+
+ {
+ let mut sel = ::Select::new();
+ let sel = &mut sel;
+ let c = sel.send(&s0, 1);
+ assert_eq!(c.id(), sel.select());
+ // Select hasn't been dropped yet and therefore hasn't
+ // unsubscribed.
+ assert_eq!(s0.inner().notify.len(), 1);
+ }
+
+ // Select should have been dropped and should have unsubscribed itself.
+ assert_eq!(s0.inner().notify.len(), 0);
+ }
+
+ #[test]
+ fn mpmc() {
+ let (send, recv) = sync(1);
+ for i in 0..4 {
+ let send = send.clone();
+ thread::spawn(move || {
+ for work in vec!['a', 'b', 'c'] {
+ send.send((i, work));
+ }
+ });
+ }
+ let wg_done = WaitGroup::new();
+ for i in 0..4 {
+ wg_done.add(1);
+ let wg_done = wg_done.clone();
+ let recv = recv.clone();
+ thread::spawn(move || {
+ for (sent_from, work) in recv {
+ println!("sent from {} to {}, work: {}",
+ sent_from, i, work);
+ }
+ println!("worker {} done!", i);
+ wg_done.done();
+ });
+ }
+ drop(send);
+ wg_done.wait();
+ println!("mpmc done!");
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/src/notifier.rs
@@ -0,0 +1,82 @@
+use std::collections::HashMap;
+use std::fmt;
+use std::sync::{Arc, Condvar, Mutex, RwLock};
+
+// This data structure is used to track subscriptions to channels.
+//
+// The flow is that when a "select" like construct is made, then it must
+// tell the channels it wants to synchronize with to notify it when some
+// activity occurs (which may cause the "select" to resolve one of the
+// synchronization events). This is managed by a simple pub/sub model below.
+//
+// This implementation is extremely naive and probably very inefficient.
+// Notably, *every* channel send/recv calls `notify`, which needs to acquire
+// a lock and broadcast to every select's condition variable.
+//
+// N.B. next_id does checked arithmetic, so if one channel is exposed to
+// 2^64 subscribers (not necessarily at the same time), then the program
+// will crash. This seems like a bad limitation, but like I said, this is
+// a naive implementation.
+
+pub struct Notifier(RwLock<Inner>);
+
+struct Inner {
+ next_id: u64,
+ subscriptions: HashMap<u64, Subscription>,
+}
+
+struct Subscription {
+ mutex: Arc<Mutex<()>>,
+ cond: Arc<Condvar>,
+}
+
+impl Notifier {
+ pub fn new() -> Notifier {
+ Notifier(RwLock::new(Inner {
+ next_id: 0,
+ subscriptions: HashMap::new(),
+ }))
+ }
+
+ pub fn notify(&self) {
+ let notify = self.0.read().unwrap();
+ for sub in notify.subscriptions.values() {
+ let _lock = sub.mutex.lock().unwrap();
+ sub.cond.notify_all();
+ }
+ }
+
+ pub fn subscribe(
+ &self,
+ mutex: Arc<Mutex<()>>,
+ condvar: Arc<Condvar>,
+ ) -> u64 {
+ let mut notify = self.0.write().unwrap();
+ let id = notify.next_id;
+ notify.next_id = notify.next_id.checked_add(1).unwrap();
+ notify.subscriptions.insert(id, Subscription {
+ mutex: mutex,
+ cond: condvar,
+ });
+ id
+ }
+
+ pub fn unsubscribe(&self, key: u64) {
+ let mut notify = self.0.write().unwrap();
+ notify.subscriptions.remove(&key);
+ }
+
+ #[cfg(test)]
+ pub fn len(&self) -> usize {
+ let notify = self.0.read().unwrap();
+ notify.subscriptions.len()
+ }
+}
+
+impl fmt::Debug for Notifier {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let notify = self.0.read().unwrap();
+ writeln!(f, "Notifier({:?})",
+ notify.subscriptions.keys().collect::<Vec<_>>())
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/src/select.rs
@@ -0,0 +1,382 @@
+use std::cell::RefCell;
+use std::collections::btree_map::{BTreeMap, Entry};
+use std::rc::Rc;
+use std::sync::{Arc, Condvar, Mutex, MutexGuard};
+
+use rand::{self, Rng};
+
+use {ChannelId, Receiver, Sender, Data};
+
+/// Select encapsulates synchronization on at most one channel operation.
+///
+/// This type was *specifically built* to work inside a macro like
+/// `chan_select!`. As a result, it is extremely unergonomic to use manually
+/// without the macro (see the `select_manual` test). Therefore, it is hidden
+/// from the public API. It is, in every sense of the word, an implementation
+/// detail.
+///
+/// If we want to expose a select interface not built on a macro then it
+/// probably shouldn't be this one. However, doing it in a way that is both
+/// ergonomic and hetergeneous is probably tricky.
+#[doc(hidden)]
+pub struct Select<'c> {
+ /// A condition variable that is notified when one of the participating
+ /// channels has a synchronization event.
+ cond: Arc<Condvar>,
+ /// A mutex for guarding notification from channels.
+ cond_mutex: Arc<Mutex<()>>,
+ /// The set of all arms.
+ choices: BTreeMap<ChannelId, Box<Choice + 'c>>,
+ /// Scratch space for quickly shuffling the order in which we try to
+ /// synchronize an operation in select.
+ ids: Option<Vec<ChannelId>>,
+}
+
+/// The result of adding a send operation to `Select`.
+///
+/// This exposes a uniform interface with `SelectRecvHandle`. Namely, the id
+/// of the underlying channel can be accessed.
+#[doc(hidden)]
+#[derive(Debug)]
+pub struct SelectSendHandle<'s, T: 's> {
+ chan: &'s Sender<T>,
+}
+
+/// The result of adding a recv operation to `Select`.
+///
+/// This exposes a uniform interface with `SelectRecvHandle`. Namely, the id
+/// of the underlying channel can be accessed.
+///
+/// This also stores a reference to the value that has been received. The
+/// value is shared with a `Choice` in `Select`'s map of subscribed channels.
+#[doc(hidden)]
+#[derive(Debug)]
+pub struct SelectRecvHandle<'r, T: 'r> {
+ chan: &'r Receiver<T>,
+ val: Rc<RefCell<Option<Option<T>>>>,
+}
+
+/// Expose a uniform interface over send and receive operations.
+///
+/// In particular, this trait is used to *erase* the type parameter in the
+/// `Receiver` and `Sender` types. This is essential to building a hetergeneous
+/// select.
+trait Choice {
+ /// Subscribe the owning `Select` to the channel in this choice.
+ fn subscribe(&mut self, mutex: Arc<Mutex<()>>, condvar: Arc<Condvar>);
+ /// Unsubscribe the owning `Select` from the channel in this choice.
+ fn unsubscribe(&self);
+ /// Return the subscription identifier.
+ fn subscription(&self) -> Option<u64>;
+ /// Attempt to synchronize.
+ ///
+ /// Returns `true` if and only if the operation synchronized.
+ fn try(&mut self) -> bool;
+ /// Lock the underlying channel.
+ fn lock(&mut self);
+ /// Unlock the underlying channel.
+ fn unlock(&mut self);
+}
+
+struct SendChoice<'s, T: 's> {
+ chan: &'s Sender<T>,
+ guard: Option<MutexGuard<'s, Data<T>>>,
+ id: Option<u64>,
+ val: Option<T>,
+}
+
+struct RecvChoice<'r, T: 'r> {
+ chan: &'r Receiver<T>,
+ guard: Option<MutexGuard<'r, Data<T>>>,
+ id: Option<u64>,
+ val: Rc<RefCell<Option<Option<T>>>>,
+}
+
+impl<'c> Select<'c> {
+ /// Create a new `Select`.
+ pub fn new() -> Select<'c> {
+ Select {
+ cond: Arc::new(Condvar::new()),
+ cond_mutex: Arc::new(Mutex::new(())),
+ choices: BTreeMap::new(),
+ ids: None,
+ }
+ }
+
+ fn is_subscribed(&self) -> bool {
+ self.choices.is_empty()
+ || self.choices.values().next().unwrap().subscription().is_some()
+ }
+
+ /// Perform a select. Block until exactly one channel operation
+ /// synchronizes.
+ pub fn select(&mut self) -> ChannelId {
+ self.maybe_try_select(false).unwrap()
+ }
+
+ /// Perform a select. If all channel operations are blocked, return `None`.
+ /// (N.B. This will *never* subscribe to channels.)
+ pub fn try_select(&mut self) -> Option<ChannelId> {
+ self.maybe_try_select(true)
+ }
+
+ fn maybe_try_select(&mut self, try: bool) -> Option<ChannelId> {
+ fn try_sync<'c>(
+ ids: &mut Option<Vec<ChannelId>>,
+ choices: &mut BTreeMap<ChannelId, Box<Choice + 'c>>,
+ ) -> Option<ChannelId> {
+ let ids = ids.as_mut().unwrap();
+ rand::thread_rng().shuffle(ids);
+ for key in ids {
+ if choices.get_mut(key).unwrap().try() {
+ return Some(*key);
+ }
+ }
+ None
+ }
+
+ // This is our initial try. If `try` is `true` (i.e., there is a
+ // `default` arm), then we quit if the initial try fails.
+ if self.ids.is_none() {
+ self.ids = Some(self.choices.keys().cloned().collect());
+ }
+ if let Some(key) = try_sync(&mut self.ids, &mut self.choices) {
+ return Some(key);
+ }
+ if try {
+ return None;
+ }
+ // At this point, we've tried to pick one of the
+ // synchronization events without initiating a subscription,
+ // but nothing succeeded. Before we sit and wait, we need to
+ // tell all of our channels to notify us when something
+ // changes.
+ if !self.is_subscribed() {
+ for (_, choice) in &mut self.choices {
+ choice.subscribe(self.cond_mutex.clone(), self.cond.clone());
+ }
+ }
+
+ // This is an extremely delicate dance.
+ //
+ // The key is that before we do anything, we need to make sure all
+ // involved channels are synchronized. We achieve this by acquiring
+ // the mutex inside of each channel.
+ //
+ // Once that's done, we can attempt to synchronize at most one of the
+ // channel operations. If we succeed, then we unlock all of the
+ // channels and return the id of the choice that synchronized.
+ //
+ // If we don't succeed, then we need to block and wait for something
+ // to happen until we try again. Doing this is tricky.
+ //
+ // The key is that when a channel synchronizes, it will notify any
+ // subscribed `Select` instances because a synchronization means
+ // something has changed and `Select` should try to synchronize one
+ // of its channel operations.
+ //
+ // However, it is critical that a channel only notify `Select` when
+ // `Select` is ready to receive notifications. i.e., we must
+ // synchronize the channel's notification with `Select`'s wait on
+ // the condition variable.
+ //
+ // Therefore, after we've tried synchronization and failed, we need
+ // to lock `Select`'s mutex *before unlocking the channels*. This
+ // will prevent channels from trying to notify `Select` before it is
+ // ready to receive a notification. (If it misses a notification then
+ // we risk deadlock.)
+ //
+ // Once `Select` is locked, we unlock all of the channels, unlock
+ // the `Select` and block. This guarantees that notifications to this
+ // `Select` are synchronized with waiting on the condition variable.
+ //
+ // Once the condition variable is notified, we repeat the process.
+ loop {
+ for (_, choice) in &mut self.choices {
+ choice.lock();
+ }
+ if let Some(key) = try_sync(&mut self.ids, &mut self.choices) {
+ for (_, choice) in &mut self.choices {
+ choice.unlock();
+ }
+ return Some(key);
+ }
+ let cond_lock = self.cond_mutex.lock().unwrap();
+ for (_, choice) in &mut self.choices {
+ choice.unlock();
+ }
+ drop(self.cond.wait(cond_lock).unwrap());
+ }
+ }
+
+ /// Register a new send operation with the select.
+ pub fn send<'s: 'c, T>(
+ &mut self,
+ chan: &'s Sender<T>,
+ val: T,
+ ) -> SelectSendHandle<'s, T> {
+ let mut choice = SendChoice {
+ chan: chan,
+ guard: None,
+ id: None,
+ val: Some(val),
+ };
+ match self.choices.entry(chan.id()) {
+ Entry::Occupied(mut prev_choice) => {
+ choice.id = prev_choice.get().subscription();
+ *prev_choice.get_mut() = Box::new(choice);
+ }
+ Entry::Vacant(spot) => {
+ assert!(self.ids.is_none(),
+ "cannot add new channels after initial select");
+ spot.insert(Box::new(choice));
+ }
+ }
+ SelectSendHandle { chan: chan }
+ }
+
+ /// Register a new receive operation with the select.
+ pub fn recv<'r: 'c, T>(
+ &mut self,
+ chan: &'r Receiver<T>,
+ ) -> SelectRecvHandle<'r, T> {
+ let mut choice = RecvChoice {
+ chan: chan,
+ guard: None,
+ id: None,
+ val: Rc::new(RefCell::new(None)),
+ };
+ let handle_val_loc = choice.val.clone();
+ match self.choices.entry(chan.id()) {
+ Entry::Occupied(mut prev_choice) => {
+ choice.id = prev_choice.get().subscription();
+ *prev_choice.get_mut() = Box::new(choice);
+ }
+ Entry::Vacant(spot) => {
+ assert!(self.ids.is_none(),
+ "cannot add new channels after initial select");
+ spot.insert(Box::new(choice));
+ }
+ }
+ SelectRecvHandle { chan: chan, val: handle_val_loc }
+ }
+}
+
+impl<'c> Drop for Select<'c> {
+ fn drop(&mut self) {
+ for (_, choice) in &mut self.choices {
+ choice.unsubscribe();
+ }
+ }
+}
+
+impl<'s, T> Choice for SendChoice<'s, T> {
+ fn subscribe(&mut self, mutex: Arc<Mutex<()>>, condvar: Arc<Condvar>) {
+ self.id = Some(self.chan.inner().notify.subscribe(mutex, condvar));
+ }
+
+ fn unsubscribe(&self) {
+ if let Some(id) = self.id {
+ self.chan.inner().notify.unsubscribe(id)
+ }
+ }
+
+ fn subscription(&self) -> Option<u64> {
+ self.id
+ }
+
+ fn try(&mut self) -> bool {
+ let v = match self.val.take() {
+ Some(v) => v,
+ None => return false,
+ };
+ // If this choice has been locked, then we need to use that lock
+ // when trying to synchronize. We must also be careful to put the
+ // lock back where it was. Dropping it would be disastrous!
+ let try = match self.guard.take() {
+ None => self.chan.try_send(v),
+ Some(g) => {
+ let op = self.chan.send_op(g, true, v);
+ let (lock, result) = op.into_result_lock();
+ self.guard = Some(lock);
+ result
+ }
+ };
+ match try {
+ Ok(()) => true,
+ Err(v) => { self.val = Some(v); false }
+ }
+ }
+
+ fn lock(&mut self) {
+ self.guard = Some(self.chan.inner().lock());
+ }
+
+ fn unlock(&mut self) {
+ self.guard.take();
+ }
+}
+
+impl<'r, T> Choice for RecvChoice<'r, T> {
+ fn subscribe(&mut self, mutex: Arc<Mutex<()>>, condvar: Arc<Condvar>) {
+ self.id = Some(self.chan.inner().notify.subscribe(mutex, condvar));
+ }
+
+ fn unsubscribe(&self) {
+ if let Some(id) = self.id {
+ self.chan.inner().notify.unsubscribe(id)
+ }
+ }
+
+ fn subscription(&self) -> Option<u64> {
+ self.id
+ }
+
+ fn try(&mut self) -> bool {
+ // If this choice has been locked, then we need to use that lock
+ // when trying to synchronize. We must also be careful to put the
+ // lock back where it was. Dropping it would be disastrous!
+ let try = match self.guard.take() {
+ None => self.chan.try_recv(),
+ Some(g) => {
+ let op = self.chan.recv_op(g, true);
+ let (lock, result) = op.into_result_lock();
+ self.guard = Some(lock);
+ result
+ }
+ };
+ match try {
+ Ok(v) => { *self.val.borrow_mut() = Some(v); true }
+ Err(()) => false,
+ }
+ }
+
+ fn lock(&mut self) {
+ self.guard = Some(self.chan.inner().lock());
+ }
+
+ fn unlock(&mut self) {
+ self.guard.take();
+ }
+}
+
+impl<'s, T> SelectSendHandle<'s, T> {
+ /// Return the id of the underlying channel.
+ pub fn id(&self) -> ChannelId {
+ self.chan.id()
+ }
+}
+
+impl<'r, T> SelectRecvHandle<'r, T> {
+ /// Return the id of the underlying channel.
+ pub fn id(&self) -> ChannelId {
+ self.chan.id()
+ }
+
+ /// Return the retrieved value.
+ ///
+ /// Panics if this channel was not chosen to synchronize.
+ pub fn into_value(self) -> Option<T> {
+ self.val.borrow_mut().take().unwrap()
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/src/tracker.rs
@@ -0,0 +1,56 @@
+use std::sync::atomic::{AtomicUsize, Ordering};
+
+// A tracker that reference counts the two sides of a channel.
+//
+// After writing this, it seems like a blatant (and naive) reproduction of
+// `Arc`. Can we instead just use `Arc` with a `Drop` impl on the inner type?
+
+pub struct Tracker {
+ senders: AtomicUsize,
+ receivers: AtomicUsize,
+}
+
+impl Tracker {
+ pub fn new() -> Tracker {
+ Tracker {
+ senders: AtomicUsize::new(0),
+ receivers: AtomicUsize::new(0),
+ }
+ }
+
+ pub fn add_sender(&self) {
+ self.senders.fetch_add(1, Ordering::SeqCst);
+ }
+
+ pub fn add_receiver(&self) {
+ self.receivers.fetch_add(1, Ordering::SeqCst);
+ }
+
+ pub fn remove_sender<F: FnMut()>(&self, mut at_zero: F) {
+ let prev = self.senders.fetch_sub(1, Ordering::SeqCst);
+ assert!(prev > 0);
+ if prev == 1 {
+ at_zero();
+ }
+ }
+
+ pub fn remove_receiver<F: FnMut()>(&self, mut at_zero: F) {
+ let prev = self.receivers.fetch_sub(1, Ordering::SeqCst);
+ assert!(prev > 0);
+ if prev == 1 {
+ at_zero();
+ }
+ }
+
+ // We may want these methods for detecting deadlock and returning an error.
+
+ #[allow(dead_code)]
+ pub fn any_senders(&self) -> bool {
+ self.senders.load(Ordering::SeqCst) > 0
+ }
+
+ #[allow(dead_code)]
+ pub fn any_receivers(&self) -> bool {
+ self.receivers.load(Ordering::SeqCst) > 0
+ }
+}
new file mode 100644
--- /dev/null
+++ b/third_party/rust/chan/src/wait_group.rs
@@ -0,0 +1,84 @@
+use std::fmt;
+use std::sync::{Arc, Condvar, Mutex};
+
+/// `WaitGroup` provides synchronization on the completion of threads.
+///
+/// For each thread involved in the synchronization, `add(1)` should be
+/// called. Just before a thread terminates, it should call `done`.
+/// To synchronize, call `wait`, which will block until the number of `done`
+/// calls corresponds to the number of `add(1)` calls.
+///
+/// # Example
+///
+/// ```
+/// use std::thread;
+///
+/// let wg = chan::WaitGroup::new();
+///
+/// for _ in 0..4 {
+/// wg.add(1);
+/// let wg = wg.clone();
+/// thread::spawn(move || {
+/// // do some work.
+///
+/// // And now call done.
+/// wg.done();
+/// });
+/// }
+/// // Blocks until `wg.done()` is called for each thread we spawned.
+/// wg.wait()
+/// ```
+#[derive(Clone)]
+pub struct WaitGroup(Arc<WaitGroupInner>);
+
+struct WaitGroupInner {
+ cond: Condvar,
+ count: Mutex<i32>,
+}
+
+impl WaitGroup {
+ /// Create a new wait group.
+ pub fn new() -> WaitGroup {
+ WaitGroup(Arc::new(WaitGroupInner {
+ cond: Condvar::new(),
+ count: Mutex::new(0),
+ }))
+ }
+
+ /// Add a new thread to the waitgroup.
+ ///
+ /// # Failure
+ ///
+ /// If the internal count drops below `0` as a result of calling `add`,
+ /// then this function panics.
+ pub fn add(&self, delta: i32) {
+ let mut count = self.0.count.lock().unwrap();
+ *count += delta;
+ assert!(*count >= 0);
+ self.0.cond.notify_all();
+ }
+
+ /// Mark a thread as having finished.
+ ///
+ /// (This is equivalent to calling `add(-1)`.)
+ pub fn done(&self) {
+ self.add(-1);
+ }
+
+ /// Wait until all threads have completed.
+ ///
+ /// This unblocks when the internal count is `0`.
+ pub fn wait(&self) {
+ let mut count = self.0.count.lock().unwrap();
+ while *count > 0 {
+ count = self.0.cond.wait(count).unwrap();
+ }
+ }
+}
+
+impl fmt::Debug for WaitGroup {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let count = self.0.count.lock().unwrap();
+ write!(f, "WaitGroup {{ count: {:?} }}", *count)
+ }
+}