mozpdb 0.2.7

// Copyright 2017 pdb Developers
//
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://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 msf::PageNumber;
use source::SourceSlice;

/// Represents a list of `PageNumbers`, which are likely (but not certainly) sequential, and which
/// will be presented as a slice of `SourceSlice`s.
#[derive(Debug)]
pub struct PageList {
    page_size: usize,
    source_slices: Vec<SourceSlice>,
    last_page: Option<PageNumber>,
    truncated: bool,
}

impl PageList {
    /// Create a new PageList for a given page size.
    pub fn new(page_size: usize) -> PageList {
        PageList{
            page_size: page_size,
            source_slices: Vec::new(),
            last_page: None,
            truncated: false,
        }
    }

    /// Add a page to the PageList. If this page number is sequential with the previous page number,
    /// it will be combined into the previous `SourceSlice` for efficiency.
    pub fn push(&mut self, page: PageNumber) {
        assert!(!self.truncated);

        let is_continuous = match self.last_page {
            Some(n) => { (n + 1) == page }
            None => { false }
        };

        if is_continuous {
            // extend by one page
            debug_assert!(self.source_slices.len() > 0);
            let last_slice = self.source_slices.last_mut().unwrap();
            last_slice.size += self.page_size;
        } else {
            self.source_slices.push(SourceSlice{
                offset: (self.page_size as u64) * (page as u64),
                size: self.page_size,
            });
        }

        self.last_page = Some(page);
    }

    /// Truncate the `PageList` to request only a certain number of bytes, regardless of how many
    /// pages were pushed. Truncatation is optional, but it must be last; `push()` may not be
    /// called after `truncate()`.
    pub fn truncate(&mut self, bytes: usize) {
        let mut bytes = bytes;
        let mut new_slices: Vec<SourceSlice> = Vec::new();

        for slice in &self.source_slices {
            let mut slice: SourceSlice = *slice;
            if bytes > 0 {
                // we need something from this slice
                // restrict this slice to the number of bytes remaining
                if slice.size > bytes {
                    slice.size = bytes;
                }

                // keep it
                new_slices.push(slice);

                // subtract the number of bytes in this slice
                bytes -= slice.size;

            } else {
                // we're done
                break
            }
        }

        self.source_slices = new_slices;
        self.truncated = true;
    }

    /// Return the total length of this PageList.
    pub fn len(&self) -> usize {
        self.source_slices.iter()
            .fold(0 as usize, |acc,s| acc + s.size)
    }

    /// Return a slice of SourceSlices.
    pub fn source_slices(&self) -> &[SourceSlice] {
        self.source_slices.as_slice()
    }
}

#[cfg(test)]
mod tests {
    use msf::page_list::*;
    use source::SourceSlice;

    #[test]
    fn test_push() {
        let mut list = PageList::new(4096);

        // PageList should coalesce sequential pages
        list.push(0);
        list.push(1);
        let expected = vec![SourceSlice { offset: 0, size: 8192 }];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 8192);

        // PageList should handle nonsequential runs too
        list.push(4);
        list.push(5);
        let expected = vec![
            SourceSlice { offset: 0, size: 8192 },
            SourceSlice { offset: 16384, size: 8192 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 16384);

        // ...including nonsequential runs that go backwards
        list.push(2);
        let expected = vec![
            SourceSlice { offset: 0, size: 8192 },
            SourceSlice { offset: 16384, size: 8192 },
            SourceSlice { offset: 8192, size: 4096 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 20480);

        // ...and runs that repeat themselves
        list.push(2);
        let expected = vec![
            SourceSlice { offset: 0, size: 8192 },
            SourceSlice { offset: 16384, size: 8192 },
            SourceSlice { offset: 8192, size: 4096 },
            SourceSlice { offset: 8192, size: 4096 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 24576);
    }

    #[test]
    fn test_truncate() {
        let mut list = PageList::new(4096);
        list.push(0);
        list.push(1);
        list.push(4);
        list.push(5);
        list.push(2);
        list.push(2);
        assert_eq!(list.len(), 24576);

        // truncation should do nothing when it's truncating more than is described
        list.truncate(25000);
        let expected = vec![
            SourceSlice { offset: 0, size: 8192 },
            SourceSlice { offset: 16384, size: 8192 },
            SourceSlice { offset: 8192, size: 4096 },
            SourceSlice { offset: 8192, size: 4096 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 24576);

        // it's usually employed to reduce the size of the last slice...
        list.truncate(24000);
        let expected = vec![
            SourceSlice{ offset: 0, size: 8192 },
            SourceSlice{ offset: 16384, size: 8192 },
            SourceSlice{ offset: 8192, size: 4096 },
            SourceSlice{ offset: 8192, size: 3520 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 24000);

        // ...but it should be able to lop off entire slices too
        list.truncate(10000);
        let expected = vec![
            SourceSlice{ offset: 0, size: 8192 },
            SourceSlice{ offset: 16384, size: 1808 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 10000);

        // and again, it shouldn't do anything if we re-truncate to a larger size
        list.truncate(12000);
        let expected = vec![
            SourceSlice{ offset: 0, size: 8192 },
            SourceSlice{ offset: 16384, size: 1808 },
        ];
        assert_eq!(list.source_slices(), expected.as_slice());
        assert_eq!(list.len(), 10000);

        // finally, we should be able to truncate the entire PageList down to nothing
        list.truncate(0);
        assert_eq!(list.source_slices().len(), 0);
        assert_eq!(list.len(), 0);
    }

    #[test]
    #[should_panic]
    fn test_push_after_truncate() {
        // push after truncate isn't permitted
        let mut list = PageList::new(4096);
        list.push(5);
        list.truncate(2000);
        assert!(true);  // so far so good

        // bam!
        list.push(6);
    }
}