netbuf/

buf.rs

use std::ptr::{copy_nonoverlapping, copy};
use std::ops::{Index, IndexMut, RangeFrom, RangeTo, RangeFull, Range};
use std::cmp::{min, max};
use std::io::{Read, Write, Result};
use std::fmt::{self, Debug};
use std::mem::swap;

use range::RangeArgument;

const READ_MIN: usize = 4096;
const ALLOC_MIN: usize = 16384;

///
/// A buffer object to be used for reading from network
///
/// Assumptions:
///
/// 1. Buffer needs to be growable as sometimes requests are large
///
/// 2. Buffer should deallocate when empty as
///    most of the time connections are idle
///
///      a. Deallocations are cheap as we have a cool memory allocator
///      (jemalloc)
///
///      b. First allocation should be big (i.e. kilobytes not few bytes)
///
/// 3. Should be easy to peek and get a slice as it makes packet parsing easy
///
/// 4. Cheap removing bytes at the start of the buf
///
pub struct Buf {
    data: Option<Box<[u8]>>,
    consumed: usize,
    remaining: usize,
}


// TODO(tailhook) use std::slice::bytes::copy_memory;
fn copy_memory(src: &[u8], dst: &mut [u8]) {
    assert!(src.len() == dst.len());
    unsafe {
        copy_nonoverlapping(src.as_ptr(), dst.as_mut_ptr(), dst.len());
    }
}


impl Buf {
    /// Create empty buffer. It has no preallocated size. The underlying memory
    /// chunk is always deallocated when there are no useful bytes in the
    /// buffer.
    pub fn new() -> Buf {
        Buf {
            data: None,
            consumed: 0,
            remaining: 0,
        }
    }
    fn reserve(&mut self, bytes: usize) {
        self.data = self.data.take().map(|slice| {
            let old_cap = slice.len();
            let old_bytes = old_cap - self.consumed() - self.remaining();

            if self.consumed() > 0 { // let's allocate new slice and move
                let min_size = old_bytes + bytes;

                let mut vec = Vec::with_capacity(max(min_size, old_cap.saturating_mul(2)));
                let cap = vec.capacity();
                unsafe { vec.set_len(cap) };
                copy_memory(&slice[self.consumed()..old_cap - self.remaining()],
                            &mut vec[..old_bytes]);
                self.remaining = cap - old_bytes;
                self.consumed = 0;
                Some(vec.into_boxed_slice())
            } else { // just reallocate
                let mut vec = slice.into_vec();
                vec.reserve(bytes);
                let cap = vec.capacity();
                unsafe { vec.set_len(cap) };
                self.remaining = cap - old_bytes;
                Some(vec.into_boxed_slice())
            }
        }).unwrap_or_else(|| {
            let mut vec = Vec::with_capacity(max(bytes, ALLOC_MIN));
            let cap = vec.capacity();
            unsafe { vec.set_len(cap) };

            self.remaining = cap;
            Some(vec.into_boxed_slice())
        })
    }
    fn reserve_exact(&mut self, bytes: usize) {
        self.data = self.data.take().map(|slice| {
            let old_cap = slice.len();
            let old_bytes = old_cap - self.consumed() - self.remaining();

            if self.consumed() > 0 { // let's allocate new slice and move
                let size = old_bytes + bytes;
                let mut vec = Vec::with_capacity(size);
                let cap = vec.capacity();
                unsafe { vec.set_len(cap) };
                copy_memory(&slice[self.consumed()..old_cap - self.remaining()],
                            &mut vec[..old_bytes]);
                self.remaining = cap - old_bytes;
                self.consumed = 0;
                Some(vec.into_boxed_slice())
            } else { // just reallocate
                let mut vec = slice.into_vec();
                vec.reserve_exact(bytes);
                let cap = vec.capacity();
                unsafe { vec.set_len(cap) };
                self.remaining = cap - old_bytes;
                Some(vec.into_boxed_slice())
            }
        }).unwrap_or_else(|| {
            let mut vec = Vec::with_capacity(bytes);
            let cap = vec.capacity();
            unsafe { vec.set_len(cap) };

            self.remaining = cap;
            Some(vec.into_boxed_slice())
        })
    }
    fn remaining(&self) -> usize {
        self.remaining as usize
    }
    fn consumed(&self) -> usize {
        self.consumed as usize
    }

    /// Mark the first `bytes` of the buffer as read. Basically it's shaving
    /// off bytes from the buffer, but does it efficiently. When there are
    /// no more bytes in the buffer it's deallocated.
    ///
    /// Note: Buffer currently doesn't shrink when calling this method. It's
    /// assumed that all bytes will be consumed shortly. In case you're
    /// appending to the buffer after consume, old data is discarded.
    ///
    /// # Panics
    ///
    /// Panics if `bytes` is larger than current length of buffer
    pub fn consume(&mut self, bytes: usize) {
        let ln = self.len();
        assert!(bytes <= ln);
        if bytes == ln {
            *self = Buf::new();
        } else {
            self.consumed += bytes;
        }
    }

    /// Allows removing an arbitrary range of bytes
    ///
    /// A more comprehensive version of `consume()`. It's occasionally useful
    /// if your data is in frames/chunks but you want to buffer the whole body
    /// anyway. E.g. in http chunked encoding you have each chunk prefixed by
    /// its length, but that doesn't mean you can't buffer the whole request
    /// into memory. This method allows you to continue reading the next chunk
    /// into the same buffer while removing the chunk length.
    ///
    /// Note: it's not super efficient, as it requires to move (copy) bytes
    /// after the range, in case range is neither at the start nor at the
    /// end of buffer. Still it should be faster than copying everything
    /// to yet another buffer.
    ///
    /// We never shrink the buffer here (except when it becomes empty, to
    /// keep this invariant), assuming that you will receive more data into
    /// the buffer shortly.
    ///
    /// The `RangeArgument` type is a temporary type until rust provides
    /// the one in standard library, you should use the range syntax directly:
    ///
    /// ```ignore
    ///     buf.remove_range(5..7)
    /// ```
    ///
    /// # Panics
    ///
    /// Panics if range is invalid for the buffer
    pub fn remove_range<R: Into<RangeArgument>>(&mut self, range: R) {
        use range::RangeArgument::*;
        match range.into() {
            RangeTo(x) | Range(0, x) => self.consume(x),
            RangeFrom(0) => *self = Buf::new(),
            RangeFrom(x) => {
                let ln = self.len();
                assert!(x <= ln);
                self.remaining += ln - x;
            }
            Range(x, y) => {
                let ln = self.len();
                if x == y { return; }
                assert!(x < y);
                let removed_bytes = y - x;
                assert!(y <= ln);
                let start = self.consumed() + x;
                let end = self.consumed() + y;
                if let Some(ref mut data) = self.data {
                    let dlen = data.len();
                    unsafe {
                        copy(data[end..].as_ptr(),
                            data[start..dlen - removed_bytes].as_mut_ptr(),
                            dlen - end);
                    }
                    self.remaining += removed_bytes;
                } else {
                    panic!("Not-existent buffere where data exists");
                }
            }
        }
    }


    /// Capacity of the buffer. I.e. the bytes it is allocated for. Use for
    /// debugging or for calculating memory usage. Note it's not guaranteed
    /// that you can write `buf.capacity() - buf.len()` bytes without resize
    pub fn capacity(&self) -> usize {
        self.data.as_ref().map(|x| x.len()).unwrap_or(0)
    }

    /// Number of useful bytes in the buffer
    pub fn len(&self) -> usize {
        self.data.as_ref()
        .map(|x| x.len() - self.consumed() - self.remaining())
        .unwrap_or(0)
    }

    /// If buffer is empty. Potentially a little bit faster than
    /// getting `len()`
    pub fn is_empty(&self) -> bool {
        self.data.is_none()
    }

    fn future_slice<'x>(&'x mut self) -> &'x mut [u8] {
        let rem = self.remaining();
        self.data.as_mut()
        .map(|x| {
            let upto = x.len();
            &mut x[upto - rem .. upto]
        })
        .unwrap()
    }

    /// Extend buffer. Note unlike `Write::write()` and `read_from()` this
    /// method reserves as small as possible a chunk of memory. So it's
    /// inefficien to grow with this method.  You may use the Write trait to
    /// grow incrementally.
    pub fn extend(&mut self, buf: &[u8]) {
        if buf.len() == 0 { return; }
        if self.remaining() < buf.len() {
            self.reserve_exact(buf.len());
        }
        copy_memory(buf, &mut self.future_slice()[..buf.len()]);
        self.remaining -= buf.len();
    }

    /// Read some bytes from stream (object implementing `Read`) into buffer
    ///
    /// Note this does *not* continue to read until getting `WouldBlock`. It
    /// passes all errors as is. It preallocates some chunk to read into
    /// buffer. It may be possible that the stream still has bytes buffered
    /// after this method returns. This method is expected either to be called
    /// until `WouldBlock` is returned or is used with level-triggered polling.
    pub fn read_from<R:Read>(&mut self, stream: &mut R) -> Result<usize> {
        if self.remaining() < READ_MIN {
            self.reserve(READ_MIN);
        }
        let bytes = match stream.read(self.future_slice()) {
            res @ Ok(0) | res @ Err(_) => {
                self.consume(0);
                return res;
            }
            Ok(x) => x,
        };
        debug_assert!(bytes <= self.remaining());
        self.remaining -= bytes;
        Ok(bytes)
    }

    /// Reads no more than max bytes into buffer and returns boolean flag
    /// of whether max bytes are reached
    ///
    /// Except for the limit on number of bytes and slightly different
    /// allocation strategy, this method has the same considerations as
    /// read_from
    ///
    /// Note this method might be used for two purposes:
    ///
    /// 1. Limit number of bytes buffered until parser can process data
    ///   (for example HTTP header size, which is number of bytes read before
    ///   `\r\n\r\n` delimiter reached)
    /// 2. Wait until exact number of bytes are fully received
    ///
    /// Since we support (1) we don't preallocate buffer for exact size of
    /// the `max` value. It also helps a little in case (2) for minimizing
    /// DDoS attack vector. If that doesn't suit you, you may wish to use
    /// `Vec::with_capacity()` for the purpose of (2).
    ///
    /// On the contrary we don't overallocate more than `max` bytes, so if
    /// you expect data to go after exact number of bytes read, it might be
    /// better to use `read_from()` and check buffer length.
    ///
    pub fn read_max_from<R:Read>(&mut self, max: usize, stream: &mut R)
        -> Result<bool>
    {
        let todo = max.saturating_sub(self.len());
        if todo == 0 {
            return Ok(true);
        }
        if self.remaining() < READ_MIN {
            if self.capacity().saturating_mul(2) < max {
                // TODO is too large we may never need so big buffer
                self.reserve(READ_MIN);
            } else {
                self.reserve_exact(todo);
            }
        }
        let res = {
            let slc = self.future_slice();
            let do_now = min(slc.len(), todo);
            stream.read(&mut slc[..do_now])
        };
        let bytes = match res {
            Ok(0) => {
                self.consume(0);
                return Ok(false);
            }
            Err(e) => {
                self.consume(0);
                return Err(e);
            }
            Ok(x) => x,
        };
        debug_assert!(bytes <= self.remaining());
        self.remaining -= bytes;
        Ok(self.len() >= max)
    }

    /// Write contents of buffer to the stream (object implementing
    /// the Write trait). We assume that stream is non-blocking, use
    /// `Write::write` (instead of `Write::write_all`) and return all errors
    /// to the caller (including `WouldBlock` or `Interrupted`).
    ///
    /// In addition to returning the number of bytes written, it also
    /// `consume()`s those bytes from the buffer, so it's safe to retry calling
    /// the method at any moment. Also it's a common pattern to append more
    /// data to the buffer between calls.
    pub fn write_to<W:Write>(&mut self, sock: &mut W) -> Result<usize> {
        let bytes = match sock.write(&self[..]) {
            Ok(bytes) => bytes,
            Err(e) => return Err(e),
        };
        self.consume(bytes);
        Ok(bytes)
    }

    /// Splits buffer into two at the given index.
    ///
    /// `self` contains bytes `[0, at)` and the returned `Buf` contains
    /// bytes `[at, len)`.
    ///
    /// Reallocates smaller part of buffer.
    ///
    /// # Panics
    ///
    /// Panics if at > len.
    ///
    /// # Examples
    /// ```rust
    /// let mut buf = netbuf::Buf::new();
    /// buf.extend(b"Hello World!");
    /// let tail = buf.split_off(6);
    /// assert_eq!(&buf[..], b"Hello ");
    /// assert_eq!(&tail[..], b"World!");
    /// ```
    pub fn split_off(&mut self, at: usize) -> Buf {
        assert!(at <= self.len());
        let mut tail = Buf::new();
        match self.data.as_ref().map(|x| x.len() - at > at) {
            Some(true) => { // re-allocate self;
                swap(&mut tail, self);
                if at > 0 {
                    self.extend(&tail[..at]);
                    tail.consume(at);
                }
            },
            Some(false) => { // allocate for tail;
                tail.extend(&self[at..]);
                self.remove_range(at..);
            },
            None => {}
        }
        tail
    }

    /// Returns the byte at the index, or `None` if the index is
    /// out of bounds.
    pub fn get(&self, index: usize) -> Option<u8> {
        if index >= self.len() {
            return None;
        }
        let consumed = self.consumed();
        if let Some(ref data) = self.data {
            Some(data[consumed + index])
        } else {
            None
        }
    }

    /// Returns a mutable reference to the byte at the index, or
    /// `None` if the index is out of bounds.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut u8> {
        if index >= self.len() {
            return None;
        }
        let consumed = self.consumed();
        if let Some(ref mut data) = self.data {
            Some(&mut data[consumed + index])
        } else {
            None
        }
    }

}


impl Debug for Buf {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Buf {{ len={}; consumed={}; remaining={} }}",
               self.len(), self.consumed(), self.remaining())
    }
}

impl AsRef<[u8]> for Buf {
    fn as_ref(&self) -> &[u8] {
        &self[..]
    }
}

impl Into<Vec<u8>> for Buf {
    fn into(mut self) -> Vec<u8> {
        if self.consumed == 0 {
            self.data.take().map(|slice| {
                let mut vec = slice.into_vec();
                if self.remaining > 0 {
                    let nlen = vec.len() - self.remaining();
                    unsafe { vec.set_len(nlen) };
                }
                vec
            }).unwrap_or_else(Vec::new)
        } else {
            self[..].to_vec()
        }
    }
}

impl Index<usize> for Buf {
    type Output = u8;
    fn index<'x>(&'x self, index: usize) -> &'x u8 {
        if let Some(ref data) = self.data {
            return &data[self.consumed() + index]
        }
        panic!("cannot index empty buffer");

    }
}

impl Index<RangeFull> for Buf {
    type Output = [u8];
    fn index<'x>(&'x self, _idx: RangeFull) -> &'x[u8] {
        self.data.as_ref()
        .map(|x| &x[self.consumed()..x.len() - self.remaining()])
        .unwrap_or(b"")
    }
}

impl Index<RangeTo<usize>> for Buf {
    type Output = [u8];
    fn index<'x>(&'x self, slice: RangeTo<usize>) -> &'x[u8] {
        let idx = slice.end;
        if idx == 0 {
            return b"";
        }
        assert!(idx <= self.len());
        &self.data.as_ref().unwrap()[self.consumed()..self.consumed() + idx]
    }
}

impl Index<RangeFrom<usize>> for Buf {
    type Output = [u8];
    fn index<'x>(&'x self, slice: RangeFrom<usize>) -> &'x[u8] {
        let idx = slice.start;
        if idx == self.len() {
            return b"";
        }
        assert!(idx <= self.len());
        let buf = &self.data.as_ref().unwrap();
        &buf[self.consumed() + idx .. buf.len() - self.remaining()]
    }
}

impl Index<Range<usize>> for Buf {
    type Output = [u8];
    fn index<'x>(&'x self, slice: Range<usize>) -> &'x[u8] {
        let start = slice.start;
        let end = slice.end;
        if end == 0 {
            return b"";
        }
        assert!(end <= self.len());
        assert!(start <= end);
        let buf = &self.data.as_ref().unwrap();
        &buf[self.consumed() + start .. self.consumed() + end]
    }
}

impl IndexMut<usize> for Buf {
    fn index_mut<'x>(&'x mut self, index: usize) -> &'x mut u8 {
        let consumed = self.consumed();
        if let Some(ref mut data) = self.data {
            return &mut data[consumed + index]
        }
        panic!("cannot index empty buffer");
    }
}

impl IndexMut<RangeFull> for Buf {
    fn index_mut<'x>(&'x mut self, _idx: RangeFull) -> &'x mut[u8] {
        let consumed = self.consumed();
        let remaining = self.remaining();
        self.data.as_mut()
        .map(|x| {
            let len = x.len();
            &mut x[consumed..len - remaining]
        })
        .unwrap_or(&mut [])
    }
}

impl IndexMut<RangeTo<usize>> for Buf {
    fn index_mut<'x>(&'x mut self, slice: RangeTo<usize>) -> &'x mut[u8] {
        let idx = slice.end;
        if idx == 0 {
            return &mut [];
        }
        assert!(idx <= self.len());
        let consumed = self.consumed();
        &mut self.data.as_mut().unwrap()[consumed..consumed + idx]
    }
}

impl IndexMut<RangeFrom<usize>> for Buf {
    fn index_mut<'x>(&'x mut self, slice: RangeFrom<usize>) -> &'x mut[u8] {
        let idx = slice.start;
        if idx == self.len() {
            return &mut [];
        }
        assert!(idx <= self.len());
        let consumed = self.consumed();
        let remaining = self.remaining();
        let buf = self.data.as_mut().unwrap();
        let len = buf.len();
        &mut buf[consumed + idx .. len - remaining]
    }
}

impl IndexMut<Range<usize>> for Buf {
    fn index_mut<'x>(&'x mut self, slice: Range<usize>) -> &'x mut[u8] {
        let start = slice.start;
        let end = slice.end;
        if end == 0 {
            return &mut [];
        }
        assert!(end <= self.len());
        assert!(start <= end);
        let consumed = self.consumed();
        let buf = self.data.as_mut().unwrap();
        &mut buf[consumed + start .. consumed + end]
    }
}

impl Write for Buf {
    fn write(&mut self, buf: &[u8]) -> Result<usize> {
        if buf.len() == 0 {
            return Ok(0);
        }
        if self.remaining() < buf.len() {
            self.reserve(buf.len());
        }
        copy_memory(buf, &mut self.future_slice()[..buf.len()]);
        self.remaining -= buf.len();
        Ok(buf.len())
    }
    fn flush(&mut self) -> Result<()> { Ok(()) }
}

impl Default for Buf {
    fn default() -> Self {
        Buf::new()
    }
}

#[cfg(test)]
mod test {
    use std::mem::size_of;
    use std::io::{self, Read, Write};
    use super::Buf;
    use super::ALLOC_MIN;
    use mockstream::SharedMockStream;

    struct ReadErr;

    impl Read for ReadErr {
        fn read(&mut self, _: &mut [u8]) -> Result<usize, io::Error> {
            Err(io::Error::new(io::ErrorKind::WouldBlock, "fake would block"))
        }
    }

    #[test]
    #[cfg(target_arch="x86_64")]
    fn size32() {
        assert_eq!(size_of::<Buf>(), 32);
    }

    #[test]
    #[cfg(target_arch="x86")]
    fn size32() {
        assert_eq!(size_of::<Buf>(), 16);
    }

    #[test]
    fn empty() {
        let buf = Buf::new();
        assert_eq!(&buf[..], b"");
        assert_eq!(format!("{:?}", buf), "Buf { len=0; consumed=0; remaining=0 }")
    }

    #[test]
    fn read_from_empty() {
        let mut s = SharedMockStream::new();
        let mut buf = Buf::new();
        assert_eq!(buf.read_from(&mut s).unwrap(), 0);
        assert!(buf.is_empty());
        assert_eq!(&buf[..], b"");
        assert_eq!(format!("{:?}", buf), "Buf { len=0; consumed=0; remaining=0 }")
    }

    #[test]
    fn read_from_err() {
        let mut buf = Buf::new();
        buf.read_from(&mut ReadErr).unwrap_err();
        assert!(buf.is_empty());
        assert_eq!(&buf[..], b"");
        assert_eq!(format!("{:?}", buf), "Buf { len=0; consumed=0; remaining=0 }")
    }

    #[test]
    fn read_max_from_empty() {
        let mut s = SharedMockStream::new();
        let mut buf = Buf::new();
        assert_eq!(buf.read_max_from(1024, &mut s).unwrap(), false);
        assert!(buf.is_empty());
        assert_eq!(&buf[..], b"");
        assert_eq!(format!("{:?}", buf), "Buf { len=0; consumed=0; remaining=0 }")
    }

    #[test]
    fn read_max_from_err() {
        let mut buf = Buf::new();
        buf.read_max_from(1024, &mut ReadErr).unwrap_err();
        assert!(buf.is_empty());
        assert_eq!(&buf[..], b"");
        assert_eq!(format!("{:?}", buf), "Buf { len=0; consumed=0; remaining=0 }")
    }

    #[test]
    fn read_from() {
        let mut s = SharedMockStream::new();
        s.push_bytes_to_read(b"hello");
        let mut buf = Buf::new();
        assert_eq!(buf.read_from(&mut s).unwrap(), 5);
        assert_eq!(&buf[..], b"hello");
    }

    #[test]
    fn read_max_from() {
        let mut s = SharedMockStream::new();
        s.push_bytes_to_read(b"hello");
        let mut buf = Buf::new();
        s.push_bytes_to_read(b"hello world");
        assert!(!buf.read_max_from(1024*1024, &mut s).unwrap());
        assert_eq!(&buf[..], b"hellohello world");
        assert!(buf.capacity() < ALLOC_MIN*2);
        s.push_bytes_to_read(b" from me!Oh, crap!");
        assert!(buf.read_max_from(25, &mut s).unwrap());
        assert_eq!(&buf[..], b"hellohello world from me!");
        assert!(buf.capacity() < ALLOC_MIN*2);
        assert!(buf.read_max_from(25, &mut s).unwrap());
        assert_eq!(&buf[..], b"hellohello world from me!");
        assert!(buf.capacity() < ALLOC_MIN*2);
        buf.consume(5);
        assert!(buf.read_max_from(22, &mut s).unwrap());
        assert_eq!(&buf[..], b"hello world from me!Oh");
        assert!(buf.capacity() < ALLOC_MIN*2);
    }

    #[test]
    fn two_reads() {
        let mut s = SharedMockStream::new();
        s.push_bytes_to_read(b"hello");
        let mut buf = Buf::new();
        buf.read_from(&mut s).unwrap();
        s.push_bytes_to_read(b" world");
        buf.read_from(&mut s).unwrap();
        assert_eq!(&buf[..], b"hello world");
        assert_eq!(buf.capacity(), ALLOC_MIN);
    }

    #[test]
    fn realloc() {
        let mut s = SharedMockStream::new();
        s.push_bytes_to_read(b"hello");
        let mut buf = Buf::new();
        buf.read_from(&mut s).unwrap();
        s.push_bytes_to_read(&b"abcdefg".iter().cloned().cycle().take(1024*1024)
            .collect::<Vec<_>>()[..]);
        buf.read_from(&mut s).unwrap();
        assert_eq!(&buf[..9], b"helloabcd");
        assert_eq!(buf.len(), ALLOC_MIN);
        assert_eq!(buf.capacity(), ALLOC_MIN);
        buf.read_from(&mut s).unwrap();
        assert_eq!(buf.len(), buf.capacity());
        assert!(buf.capacity() >= 32768);
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        buf.read_from(&mut s).unwrap();
        println!("Capacity {}", buf.capacity());
        assert_eq!(buf.len(), 1048576 + 5);
        assert!(buf.capacity() >= buf.len());
        assert!(buf.capacity() <= 2100000);
        assert_eq!(&buf[buf.len()-10..], b"bcdefgabcd");
    }

    #[test]
    fn two_writes() {
        let mut buf = Buf::new();
        assert_eq!(buf.write(b"hello").unwrap(), 5);
        assert_eq!(buf.write(b" world").unwrap(), 6);
        assert_eq!(&buf[..], b"hello world");
        assert_eq!(buf.capacity(), ALLOC_MIN);
    }

    #[test]
    fn two_extends() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.extend(b" world");
        assert_eq!(&buf[..], b"hello world");
        assert_eq!(buf.capacity(), 11);
    }

    #[test]
    fn write_extend() {
        let mut buf = Buf::new();
        buf.write(b"hello").unwrap();
        buf.extend(b" world");
        assert_eq!(&buf[..], b"hello world");
        assert_eq!(buf.capacity(), ALLOC_MIN);
    }

    #[test]
    fn extend_write() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.write(b" world").unwrap();
        assert_eq!(&buf[..], b"hello world");
        let cap = buf.capacity();
        // We don't know exact allocation policy for vec
        // So this check is fuzzy
        assert!(cap >= 11);
        assert!(cap < 256);
    }

    #[test]
    fn extend_empty() {
        let mut buf = Buf::new();
        buf.extend(b"");
        assert_eq!(&buf[..], b"");
        assert_eq!(buf.len(), 0);
        assert_eq!(buf.capacity(), 0);
    }

    #[test]
    fn into() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.write(b" world").unwrap();
        let vec: Vec<u8> = buf.into();
        assert_eq!(&vec[..], b"hello world");
        let cap = vec.capacity();
        // We don't know exact allocation policy for vec
        // So this check is fuzzy
        assert!(cap >= 11);
        assert!(cap < 256);
    }

    #[test]
    fn consumed_into() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.write(b" world").unwrap();
        buf.consume(6);
        let vec: Vec<u8> = buf.into();
        assert_eq!(&vec[..], b"world");
        assert_eq!(vec.capacity(), 5);
    }
    #[test]
    fn write_to() {
        let mut s = SharedMockStream::new();
        let mut buf = Buf::new();
        buf.extend(b"hello world");
        assert_eq!(buf.write_to(&mut s).unwrap(), 11);
        assert_eq!(&s.pop_bytes_written()[..], b"hello world");
    }

    #[test]
    fn empty_write_to_empty() {
        let mut buf = Buf::new();
        let mut empty = Buf::new();
        assert_eq!(empty.write_to(&mut buf).unwrap(), 0);
    }

    #[test]
    fn extend_consume_extend() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.consume(3);
        buf.extend(b" world");
        assert_eq!(&buf[..], b"lo world");
        assert_eq!(buf.capacity(), 8);
    }

    #[test]
    fn extend_consume_write() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.consume(3);
        buf.write(b"Some larger string for you").unwrap();
        assert_eq!(&buf[..], b"loSome larger string for you");
        assert_eq!(buf.capacity(), 28);
    }

    #[test]
    fn consume_all() {
        let mut buf = Buf::new();
        buf.extend(b"hello");
        buf.write(b" world").unwrap();
        buf.consume(11);
        assert_eq!(buf.capacity(), 0);
        assert_eq!(&buf[..], b"");
        let vec: Vec<u8> = buf.into();
        assert_eq!(&vec[..], b"");
        assert_eq!(vec.capacity(), 0);
    }

    #[test]
    fn index() {
        let mut buf = Buf::new();
        buf.extend(b"Hello World!");
        assert_eq!(buf[0], b'H');
        assert_eq!(buf[6], b'W');
        buf.consume(2);
        assert_eq!(buf[2], b'o');
        assert_eq!(buf[8], b'd');
    }

    #[test]
    fn index_mut() {
        let mut buf = Buf::new();
        buf.extend(b"Hello World!");
        assert_eq!(buf[0], b'H');
        buf[0] = b'h';
        assert_eq!(buf[6], b'W');
        buf[6] = b'M';
        assert_eq!(&buf[..], b"hello Morld!");
        buf.consume(2);
        buf[1] = b'e';
        buf[5] = b'e';
        buf[8] = b'e';
        assert_eq!(&buf[..], b"leo Merle!");
    }

    #[test]
    fn get() {
        let mut buf = Buf::new();
        assert_eq!(buf.get(0), None);
        buf.extend(b"Hello World!");
        assert_eq!(buf.get(0), Some(b'H'));
        assert_eq!(buf.get(6), Some(b'W'));
        assert_eq!(buf.get(11), Some(b'!'));
        assert_eq!(buf.get(12), None);
        buf.consume(2);
        assert_eq!(buf.get(2), Some(b'o'));
        assert_eq!(buf.get(8), Some(b'd'));
        assert_eq!(buf.get(9), Some(b'!'));
        assert_eq!(buf.get(10), None);
    }

    #[test]
    fn get_mut() {
        let mut buf = Buf::new();
        assert_eq!(buf.get_mut(0), None);
        buf.extend(b"Hello World!");
        assert_eq!(buf.get_mut(0), Some(&mut b'H'));
        if let Some(x) = buf.get_mut(0) { *x = b'h'; }
        assert_eq!(buf.get_mut(6), Some(&mut b'W'));
        if let Some(x) = buf.get_mut(6) { *x = b'M'; }
        assert_eq!(&buf[..], b"hello Morld!");
        assert_eq!(buf.get_mut(11), Some(&mut b'!'));
        assert_eq!(buf.get_mut(12), None);
        buf.consume(2);
        if let Some(x) = buf.get_mut(1) { *x = b'e'; }
        if let Some(x) = buf.get_mut(5) { *x = b'e'; }
        if let Some(x) = buf.get_mut(8) { *x = b'e'; }
        assert_eq!(&buf[..], b"leo Merle!");
        assert_eq!(buf.get_mut(9), Some(&mut b'!'));
        assert_eq!(buf.get_mut(10), None);
    }

    #[test]
    fn ranges() {
        let mut buf = Buf::new();
        buf.extend(b"Hello world!");
        assert_eq!(&buf[..], b"Hello world!");
        assert_eq!(&buf[..0], b"");
        assert_eq!(&buf[..5], b"Hello");
        assert_eq!(&buf[..12], b"Hello world!");
        assert_eq!(&buf[..7], b"Hello w");
        assert_eq!(&buf[0..], b"Hello world!");
        assert_eq!(&buf[3..], b"lo world!");
        assert_eq!(&buf[6..], b"world!");
        assert_eq!(&buf[12..], b"");
        assert_eq!(&buf[0..0], b"");
        assert_eq!(&buf[2..8], b"llo wo");
        assert_eq!(&buf[0..12], b"Hello world!");
        assert_eq!(&buf[0..5], b"Hello");
        assert_eq!(&buf[7..12], b"orld!");
        assert_eq!(&buf[3..3], b"");
        assert_eq!(&buf[3..9], b"lo wor");
    }

    #[test]
    fn consume_ranges() {
        let mut buf = Buf::new();
        buf.extend(b"Crappy stuff");
        buf.extend(b"Hello world!");
        buf.consume(12);
        assert_eq!(&buf[..], b"Hello world!");
        assert_eq!(&buf[..0], b"");
        assert_eq!(&buf[..5], b"Hello");
        assert_eq!(&buf[..12], b"Hello world!");
        assert_eq!(&buf[..7], b"Hello w");
        assert_eq!(&buf[0..], b"Hello world!");
        assert_eq!(&buf[3..], b"lo world!");
        assert_eq!(&buf[6..], b"world!");
        assert_eq!(&buf[12..], b"");
        assert_eq!(&buf[2..8], b"llo wo");
        assert_eq!(&buf[0..12], b"Hello world!");
        assert_eq!(&buf[0..5], b"Hello");
        assert_eq!(&buf[7..12], b"orld!");
        assert_eq!(&buf[3..3], b"");
        assert_eq!(&buf[3..9], b"lo wor");
    }

    #[test]
    fn remove_ranges() {
        let mut buf = Buf::new();
        buf.extend(b"Crappy stuff");
        buf.extend(b"Hello world!");
        assert_eq!(&buf[..], b"Crappy stuffHello world!");
        buf.remove_range(..4);
        assert_eq!(&buf[..], b"py stuffHello world!");
        buf.remove_range(3..8);
        assert_eq!(&buf[..], b"py Hello world!");
        buf.remove_range(7..14);
        assert_eq!(&buf[..], b"py Hell!");
        buf.remove_range(7..);
        assert_eq!(&buf[..], b"py Hell");
        let end = buf.len();
        buf.remove_range(2..end);
        assert_eq!(&buf[..], b"py");
    }

    #[test]
    fn mut_ranges() {
        let mut buf = Buf::new();
        buf.extend(b"Crappy stuff");
        buf.extend(b"Hello world!");
        buf.consume(12);
        buf[..].clone_from_slice(b"HELLO WORLD.");
        assert_eq!(&buf[..], b"HELLO WORLD.");
        buf[..5].clone_from_slice(b"hell!");
        assert_eq!(&buf[..], b"hell! WORLD.");
        buf[4..10].clone_from_slice(b"o worl");
        assert_eq!(&buf[..], b"hello worlD.");
        buf[10..].clone_from_slice(b"d!");
        assert_eq!(&buf[..], b"hello world!");
    }

    #[test]
    fn split_off_realloc_self() {
        let mut buf = Buf::new();
        buf.reserve_exact(20);
        buf.extend(b"Hello World");
        let tail = buf.split_off(5);
        assert_eq!(&buf[..], b"Hello");
        assert_eq!(buf.consumed(), 0);
        assert_eq!(buf.len(), 5);

        assert_eq!(&tail[..], b" World");
        assert_eq!(tail.consumed(), 5);
        assert_eq!(tail.len(), 6);
    }

    #[test]
    fn split_off_alloc_tail() {
        let mut buf = Buf::new();
        buf.reserve_exact(20);
        buf.extend(b"Hello World!...");
        assert_eq!(buf.capacity(), 20);

        let tail = buf.split_off(11);
        assert_eq!(&buf[..], b"Hello World");
        assert_eq!(buf.capacity(), 20);
        assert_eq!(buf.consumed(), 0);
        assert_eq!(buf.len(), 11);

        assert_eq!(&tail[..], b"!...");
        assert_eq!(tail.capacity(), 4);
        assert_eq!(tail.consumed(), 0);
        assert_eq!(tail.len(), 4);

        let mut buf = Buf::new();
        buf.extend(b"abcdefg");
        let tail = buf.split_off(0);
        assert_eq!(&tail[..], b"abcdefg");
        assert_eq!(&buf[..], b"");
    }
}