metrale_grammar/earley/
queue.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// ProcessQueue — the Earley parser's per-advance processing queue plus
4// the visited-set deduplicator. Port of `RepeatDetector` and the
5// `tmp_process_state_queue_` / `tmp_states_visited_in_queue_` machinery
6// from `cpp/earley_parser.{h,cc}`.
7
8use std::collections::VecDeque;
9
10use ahash::AHashSet;
11
12use super::state::ParserState;
13
14/// Below this many distinct states the C++ `RepeatDetector` scans a
15/// small vector; above it, it switches to a hash set. We always use a
16/// hash set — `AHashSet` makes the small-N case cheap enough that the
17/// dual representation is not worth the complexity. Behavior (which
18/// states are reported visited) is identical.
19///
20/// FIFO queue of states awaiting predict/complete, with an attached
21/// visited set so a state is enqueued at most once per advance round.
22#[derive(Debug, Default)]
23pub struct ProcessQueue {
24    queue: VecDeque<ParserState>,
25    visited: AHashSet<ParserState>,
26}
27
28impl ProcessQueue {
29    /// An empty queue.
30    pub fn new() -> Self {
31        Self::default()
32    }
33
34    /// Clear the visited set (called at the start of each advance).
35    /// The queue itself is asserted empty by the caller.
36    pub fn clear_visited(&mut self) {
37        self.visited.clear();
38    }
39
40    /// True if `state` has already been seen this round.
41    pub fn is_visited(&self, state: &ParserState) -> bool {
42        self.visited.contains(state)
43    }
44
45    /// Enqueue `state` for predict/complete unless already visited.
46    /// Returns true if it was newly enqueued.
47    pub fn enqueue(&mut self, state: ParserState) -> bool {
48        if self.visited.insert(state) {
49            self.queue.push_back(state);
50            true
51        } else {
52            false
53        }
54    }
55
56    /// Mark `state` visited without enqueuing it for processing.
57    /// Returns true if it was newly marked. Mirrors the C++
58    /// `EnqueueWithoutProcessing` visited-set side effect; the caller
59    /// is responsible for adding the state to the scanable list.
60    pub fn mark_visited(&mut self, state: ParserState) -> bool {
61        self.visited.insert(state)
62    }
63
64    /// Pop the next state to process, or `None` when drained.
65    pub fn pop(&mut self) -> Option<ParserState> {
66        self.queue.pop_front()
67    }
68
69    /// True if no states are pending.
70    pub fn is_empty(&self) -> bool {
71        self.queue.is_empty()
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    fn st(id: i32) -> ParserState {
80        ParserState::new(id, 0, 0, 0, 0)
81    }
82
83    #[test]
84    fn enqueue_dedups() {
85        let mut q = ProcessQueue::new();
86        assert!(q.enqueue(st(1)));
87        assert!(!q.enqueue(st(1)));
88        assert!(q.enqueue(st(2)));
89        assert_eq!(q.pop(), Some(st(1)));
90        assert_eq!(q.pop(), Some(st(2)));
91        assert_eq!(q.pop(), None);
92    }
93
94    #[test]
95    fn fifo_order() {
96        let mut q = ProcessQueue::new();
97        for i in 0..5 {
98            q.enqueue(st(i));
99        }
100        for i in 0..5 {
101            assert_eq!(q.pop(), Some(st(i)));
102        }
103    }
104
105    #[test]
106    fn clear_visited_allows_reenqueue() {
107        let mut q = ProcessQueue::new();
108        q.enqueue(st(1));
109        q.pop();
110        assert!(!q.enqueue(st(1)));
111        q.clear_visited();
112        assert!(q.enqueue(st(1)));
113    }
114
115    #[test]
116    fn mark_visited_blocks_enqueue() {
117        let mut q = ProcessQueue::new();
118        assert!(q.mark_visited(st(7)));
119        assert!(!q.mark_visited(st(7)));
120        assert!(!q.enqueue(st(7)));
121        assert!(q.is_visited(&st(7)));
122    }
123}
metrale_grammar/earley/queue.rs

metrale_grammar/earley/
queue.rs
