Remove `array_vec.rs`.

`SparseBitSet` is the only remaining user of `ArrayVec`. This commit
switches it to using `SmallVec`, and removes `array_vec.rs`.

Why the switch? Although `SparseBitSet` is size-limited and doesn't need
the ability to spill to the heap, `SmallVec` has many more features than
`ArrayVec`. In particular, it's now possible to keep `SparseBitSet`'s
elements in sorted order, which gives in-order iteration, which is a
requirement for the next commit.

1 files changed, 0 insertions, 305 deletions

diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
deleted file mode 100644
index 45fb5657061..00000000000
--- a/src/librustc_data_structures/array_vec.rs
+++ /dev/null
@@ -1,305 +0,0 @@
-// Copyright 2016 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.
-
-//! A stack-allocated vector, allowing storage of N elements on the stack.
-
-use std::marker::Unsize;
-use std::iter::Extend;
-use std::ptr::{self, drop_in_place, NonNull};
-use std::ops::{Deref, DerefMut, Range};
-use std::hash::{Hash, Hasher};
-use std::slice;
-use std::fmt;
-use std::mem;
-use std::mem::ManuallyDrop;
-use std::ops::Bound::{Excluded, Included, Unbounded};
-use std::ops::RangeBounds;
-
-pub unsafe trait Array {
-    type Element;
-    type PartialStorage: Unsize<[ManuallyDrop<Self::Element>]>;
-    const LEN: usize;
-}
-
-unsafe impl<T> Array for [T; 1] {
-    type Element = T;
-    type PartialStorage = [ManuallyDrop<T>; 1];
-    const LEN: usize = 1;
-}
-
-unsafe impl<T> Array for [T; 8] {
-    type Element = T;
-    type PartialStorage = [ManuallyDrop<T>; 8];
-    const LEN: usize = 8;
-}
-
-unsafe impl<T> Array for [T; 32] {
-    type Element = T;
-    type PartialStorage = [ManuallyDrop<T>; 32];
-    const LEN: usize = 32;
-}
-
-pub struct ArrayVec<A: Array> {
-    count: usize,
-    values: A::PartialStorage
-}
-
-impl<A> Hash for ArrayVec<A>
-    where A: Array,
-          A::Element: Hash {
-    fn hash<H>(&self, state: &mut H) where H: Hasher {
-        (&self[..]).hash(state);
-    }
-}
-
-impl<A> Clone for ArrayVec<A>
-    where A: Array,
-          A::Element: Clone {
-    fn clone(&self) -> Self {
-        let mut v = ArrayVec::new();
-        v.extend(self.iter().cloned());
-        v
-    }
-}
-
-impl<A: Array> ArrayVec<A> {
-    pub fn new() -> Self {
-        ArrayVec {
-            count: 0,
-            values: unsafe { ::std::mem::uninitialized() },
-        }
-    }
-
-    pub fn len(&self) -> usize {
-        self.count
-    }
-
-    pub unsafe fn set_len(&mut self, len: usize) {
-        self.count = len;
-    }
-
-    /// Panics when the stack vector is full.
-    pub fn push(&mut self, el: A::Element) {
-        let arr = &mut self.values as &mut [ManuallyDrop<_>];
-        arr[self.count] = ManuallyDrop::new(el);
-        self.count += 1;
-    }
-
-    pub fn pop(&mut self) -> Option<A::Element> {
-        if self.count > 0 {
-            let arr = &mut self.values as &mut [ManuallyDrop<_>];
-            self.count -= 1;
-            unsafe {
-                let value = ptr::read(&*arr[self.count]);
-                Some(value)
-            }
-        } else {
-            None
-        }
-    }
-
-    pub fn drain<R>(&mut self, range: R) -> Drain<A>
-        where R: RangeBounds<usize>
-    {
-        // Memory safety
-        //
-        // When the Drain is first created, it shortens the length of
-        // the source vector to make sure no uninitialized or moved-from elements
-        // are accessible at all if the Drain's destructor never gets to run.
-        //
-        // Drain will ptr::read out the values to remove.
-        // When finished, remaining tail of the vec is copied back to cover
-        // the hole, and the vector length is restored to the new length.
-        //
-        let len = self.len();
-        let start = match range.start_bound() {
-            Included(&n) => n,
-            Excluded(&n) => n + 1,
-            Unbounded    => 0,
-        };
-        let end = match range.end_bound() {
-            Included(&n) => n + 1,
-            Excluded(&n) => n,
-            Unbounded    => len,
-        };
-        assert!(start <= end);
-        assert!(end <= len);
-
-        unsafe {
-            // set self.vec length's to start, to be safe in case Drain is leaked
-            self.set_len(start);
-            // Use the borrow in the IterMut to indicate borrowing behavior of the
-            // whole Drain iterator (like &mut T).
-            let range_slice = {
-                let arr = &mut self.values as &mut [ManuallyDrop<<A as Array>::Element>];
-                slice::from_raw_parts_mut(arr.as_mut_ptr().add(start),
-                                          end - start)
-            };
-            Drain {
-                tail_start: end,
-                tail_len: len - end,
-                iter: range_slice.iter(),
-                array_vec: NonNull::from(self),
-            }
-        }
-    }
-}
-
-impl<A> Default for ArrayVec<A>
-    where A: Array {
-    fn default() -> Self {
-        ArrayVec::new()
-    }
-}
-
-impl<A> fmt::Debug for ArrayVec<A>
-    where A: Array,
-          A::Element: fmt::Debug {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        self[..].fmt(f)
-    }
-}
-
-impl<A: Array> Deref for ArrayVec<A> {
-    type Target = [A::Element];
-    fn deref(&self) -> &Self::Target {
-        unsafe {
-            slice::from_raw_parts(&self.values as *const _ as *const A::Element, self.count)
-        }
-    }
-}
-
-impl<A: Array> DerefMut for ArrayVec<A> {
-    fn deref_mut(&mut self) -> &mut [A::Element] {
-        unsafe {
-            slice::from_raw_parts_mut(&mut self.values as *mut _ as *mut A::Element, self.count)
-        }
-    }
-}
-
-impl<A: Array> Drop for ArrayVec<A> {
-    fn drop(&mut self) {
-        unsafe {
-            drop_in_place(&mut self[..])
-        }
-    }
-}
-
-impl<A: Array> Extend<A::Element> for ArrayVec<A> {
-    fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
-        for el in iter {
-            self.push(el);
-        }
-    }
-}
-
-pub struct Iter<A: Array> {
-    indices: Range<usize>,
-    store: A::PartialStorage,
-}
-
-impl<A: Array> Drop for Iter<A> {
-    fn drop(&mut self) {
-        self.for_each(drop);
-    }
-}
-
-impl<A: Array> Iterator for Iter<A> {
-    type Item = A::Element;
-
-    fn next(&mut self) -> Option<A::Element> {
-        let arr = &self.store as &[ManuallyDrop<_>];
-        unsafe {
-            self.indices.next().map(|i| ptr::read(&*arr[i]))
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.indices.size_hint()
-    }
-}
-
-pub struct Drain<'a, A: Array>
-        where A::Element: 'a
-{
-    tail_start: usize,
-    tail_len: usize,
-    iter: slice::Iter<'a, ManuallyDrop<A::Element>>,
-    array_vec: NonNull<ArrayVec<A>>,
-}
-
-impl<'a, A: Array> Iterator for Drain<'a, A> {
-    type Item = A::Element;
-
-    #[inline]
-    fn next(&mut self) -> Option<A::Element> {
-        self.iter.next().map(|elt| unsafe { ptr::read(&**elt) })
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.iter.size_hint()
-    }
-}
-
-impl<'a, A: Array> Drop for Drain<'a, A> {
-    fn drop(&mut self) {
-        // exhaust self first
-        self.for_each(drop);
-
-        if self.tail_len > 0 {
-            unsafe {
-                let source_array_vec: &mut ArrayVec<A> = self.array_vec.as_mut();
-                // memmove back untouched tail, update to new length
-                let start = source_array_vec.len();
-                let tail = self.tail_start;
-                {
-                    let arr =
-                        &mut source_array_vec.values as &mut [ManuallyDrop<<A as Array>::Element>];
-                    let src = arr.as_ptr().add(tail);
-                    let dst = arr.as_mut_ptr().add(start);
-                    ptr::copy(src, dst, self.tail_len);
-                };
-                source_array_vec.set_len(start + self.tail_len);
-            }
-        }
-    }
-}
-
-impl<A: Array> IntoIterator for ArrayVec<A> {
-    type Item = A::Element;
-    type IntoIter = Iter<A>;
-    fn into_iter(self) -> Self::IntoIter {
-        let store = unsafe {
-            ptr::read(&self.values)
-        };
-        let indices = 0..self.count;
-        mem::forget(self);
-        Iter {
-            indices,
-            store,
-        }
-    }
-}
-
-impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
-    type Item = &'a A::Element;
-    type IntoIter = slice::Iter<'a, A::Element>;
-    fn into_iter(self) -> Self::IntoIter {
-        self.iter()
-    }
-}
-
-impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
-    type Item = &'a mut A::Element;
-    type IntoIter = slice::IterMut<'a, A::Element>;
-    fn into_iter(self) -> Self::IntoIter {
-        self.iter_mut()
-    }
-}