diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /third_party/rust/jsparagus-parser/src/queue_stack.rs | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/jsparagus-parser/src/queue_stack.rs')
-rw-r--r-- | third_party/rust/jsparagus-parser/src/queue_stack.rs | 256 |
1 files changed, 256 insertions, 0 deletions
diff --git a/third_party/rust/jsparagus-parser/src/queue_stack.rs b/third_party/rust/jsparagus-parser/src/queue_stack.rs new file mode 100644 index 0000000000..f56e2e1b66 --- /dev/null +++ b/third_party/rust/jsparagus-parser/src/queue_stack.rs @@ -0,0 +1,256 @@ +//! 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); + } +} |