1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
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);
}
}
|
