Quelle  queue_stack.rs

//! This module implements a Stack, which is useful for implementing a parser
//! with variable lookahead, as it would allow to pop elements which are below
//! the top-element, and maintain a top counter which would be in charge of
//! moving these elements once shifted.
use std::ptr;

/// This container implements a stack and a queue in a single vector:
///   - stack: buf[..top]
///   - queue: buf[top + gap..]
///
/// This structure is meant to avoid moving data when the head of the queue is
/// transfered to the top of the stack. Also, sometimes we need to set items
/// aside from the top of a stack, and then push them back onto the stack later.
/// The queue is for storing these set-aside values. Since they live in the same
/// buffer as the stack, values can be "set aside" and "pushed back on" without
/// moving them at all.
///
/// In the context of an LR parser, the stack contains shifted elements, and the
/// queue contains the lookahead. If the lexer is completely independent of the
/// parser, all tokens could be queued before starting the parser.
///
/// The following statements describe how this structure is meant to be used and
/// is described as a stack and a queue displayed as follow:
///    [...stack...] <gap> [...queue...]
///
/// New elements are always inserted in the queue with `enqueue`:
///    [a, b] <no gap> []
///    * enqueue(c)
///    [a, b] <no gap> [c]
///
/// These elements are then moved to the stack with `shift`:
///    [a, b] <no gap> [c]
///    * shift()
///    [a, b, c] <no gap> []
///
/// The stack top can be set aside in the queue with `unshift`:
///    [a, b, c] <no gap> []
///    * unshift()
///    [a, b] <no gap> [c]
///
/// The stack top can be removed with `pop`:
///    [a, b] <no gap> [c]
///    * pop() -> b
///    [a] <gap: 1> [c]
///    * pop() -> a
///    [] <gap: 2> [c]
///
/// New elements can be added to the front of the queue with `push_next`, which
/// also moves the content of the queue to ensure that `shift` can be used
/// afterward:
///    [] <gap: 2> [c]
///    * push_next(d)
///    [] <no gap> [d, c]
///
/// These operations are used by LR parser, to add lookahead with `enqueue`, to
/// shift tokens with `shift`, to save tokens to be replayed with `unshift`, to
/// reduce a set of tokens and replace it by a non-terminal with `pop` and
/// `push_next`.
pub struct QueueStack<T> {
    /// Buffer containing the stack and the queue.
    ///
    ///   [a, b, c, d, e, f, g, h, i, j]
    ///    '-----------'<------>'-----'
    ///       stack     ^  gap   queue
    ///                 |
    ///            top -'
    buf: Vec<T>,
    /// Length of the stack, self.buf[top - 1] being the last element of the
    /// stack.
    top: usize,
    /// Length of the gap between the stack top and the queue head.
    gap: usize,
}

impl<T> QueueStack<T> {
    /// Create a queue and stack with the given number of reserved elements.
    pub fn with_capacity(n: usize) -> QueueStack<T> {
        QueueStack {
            buf: Vec::with_capacity(n),
            top: 0,
            gap: 0,
        }
    }

    /// Add an element to the back of the queue.
    pub fn enqueue(&mut self, value: T) {
        self.buf.push(value);
    }

    /// Add an element to the front of the queue.
    pub fn push_next(&mut self, value: T) {
        self.compact_with_gap(1);
        self.gap -= 1;
        unsafe {
            // Write over the gap without reading nor dropping the old entry.
            let ptr = self.buf.as_mut_ptr().add(self.top + self.gap);
            ptr.write(value);
        }
    }

    /// Whether elements can be shifted.
    pub fn can_shift(&self) -> bool {
        self.gap == 0 && !self.queue_empty()
    }

    /// Whether elements can be unshifted.
    pub fn can_unshift(&self) -> bool {
        self.gap == 0 && !self.stack_empty()
    }

    /// Transfer an element from the top of the stack to the front of the queue.
    ///
    /// The gap must be empty. This does not move the value from one address to
    /// another in memory; it just adjusts the boundary between the stack and
    /// the queue.
    ///
    /// # Panics
    /// If the stack is empty or there is a gap.
    pub fn unshift(&mut self) {
        assert!(self.can_unshift());
        self.top -= 1;
    }

    /// Transfer an element from the front of the queue to the top of the stack.
    ///
    /// The gap must be empty. This does not move the value from one address to
    /// another in memory; it just adjusts the boundary between the stack and
    /// the queue.
    ///
    /// # Panics
    /// If the queue is empty or there is a gap.
    #[inline(always)]
    pub fn shift(&mut self) {
        assert!(self.can_shift());
        self.top += 1;
    }

    /// Remove the top element of the stack and return it, or None if the stack
    /// is empty.
    ///
    /// This increases the gap size by 1.
    pub fn pop(&mut self) -> Option<T> {
        if self.top == 0 {
            None
        } else {
            self.top -= 1;
            self.gap += 1;
            unsafe {
                // Take ownership of the content.
                let ptr = self.buf.as_mut_ptr().add(self.top);
                Some(ptr.read())
            }
        }
    }

    /// Set the gap size to `new_gap`, memmove-ing the contents of the queue as
    /// needed.
    fn compact_with_gap(&mut self, new_gap: usize) {
        assert!(new_gap <= (std::isize::MAX as usize));
        assert!(self.gap <= (std::isize::MAX as usize));
        let diff = new_gap as isize - self.gap as isize;
        if diff == 0 {
            return;
        }
        // Ensure there is enough capacity.
        if diff > 0 {
            self.buf.reserve(diff as usize);
        }
        // Number of elements to be copied.
        let count = self.queue_len();
        let new_len = self.top + new_gap + count;
        assert!(new_len < self.buf.capacity());
        unsafe {
            let src_ptr = self.buf.as_mut_ptr().add(self.top + self.gap);
            let dst_ptr = src_ptr.offset(diff);

            // Shift everything down/up to have the expected gap.
            ptr::copy(src_ptr, dst_ptr, count);

            // Update the buffer length to newly copied elements.
            self.buf.set_len(new_len);
            // Update the gap to the new gap value.
            self.gap = new_gap;
        }
        debug_assert_eq!(self.queue_len(), count);
    }

    /// Returns a reference to the front element of the queue.
    pub fn next(&self) -> Option<&T> {
        if self.queue_empty() {
            None
        } else {
            Some(&self.buf[self.top + self.gap])
        }
    }

    /// Returns a reference to the top element of the stack.
    #[allow(dead_code)]
    pub fn top(&self) -> Option<&T> {
        if self.top == 0 {
            None
        } else {
            Some(&self.buf[self.top - 1])
        }
    }

    /// Returns a mutable reference to the top of the stack.
    #[allow(dead_code)]
    pub fn top_mut(&mut self) -> Option<&mut T> {
        if self.top == 0 {
            None
        } else {
            Some(&mut self.buf[self.top - 1])
        }
    }

    /// Number of elements in the stack.
    pub fn stack_len(&self) -> usize {
        self.top
    }

    /// Number of elements in the queue.
    pub fn queue_len(&self) -> usize {
        self.buf.len() - self.top - self.gap
    }

    /// Whether the stack is empty.
    pub fn stack_empty(&self) -> bool {
        self.top == 0
    }

    /// Whether the queue is empty.
    pub fn queue_empty(&self) -> bool {
        self.top == self.buf.len()
    }

    /// Create a slice which corresponds the stack.
    pub fn stack_slice(&self) -> &[T] {
        &self.buf[..self.top]
    }

    /// Create a slice which corresponds the queue.
    #[allow(dead_code)]
    pub fn queue_slice(&self) -> &[T] {
        &self.buf[self.top + self.gap..]
    }
}

impl<T> Drop for QueueStack<T> {
    fn drop(&mut self) {
        // QueueStack contains a gap of non-initialized values, before releasing
        // the vector, we move all initialized values from the queue into the
        // remaining gap.
        self.compact_with_gap(0);
    }
}