Line data Source code
1 : //! The LR probes of the completion.
2 : //!
3 : //! The probes run the automaton without grammar actions, only the state numbers matter:
4 : //! - [`parse_until_with_snapshot`] parses up to the cursor token, returns the expected symbols there
5 : //! and a snapshot of the state stack,
6 : //! - [`parse_until_after`] feeds a symbol at the cursor and returns the expected symbols after it,
7 : //! - [`probe_suffix_batch`] and [`probe_suffix_sequence`] replay the tokens after the cursor from a
8 : //! snapshot to test whether candidate symbols fit the rest of the script.
9 :
10 : use super::driver::{lac_check, table_action, Action, StateId};
11 : use crate::scanner::Symbol;
12 : use crate::symbol_kind::*;
13 : use crate::tables::*;
14 : use crate::SymbolKind;
15 :
16 : /// A completion replay stops after this many reductions without a shift. A restored prefix can enter
17 : /// nullable reduction cycles that a regular parse never reaches.
18 : const MAX_REDUCTIONS_WITHOUT_SHIFT: usize = 128;
19 :
20 : /// The state stack before the read of the cursor token
21 : #[derive(Clone, Debug, Default)]
22 : pub struct PrefixSnapshot {
23 : /// The states, bottom to top
24 : pub state_stack: Vec<StateId>,
25 : /// Did the prefix parse reach the cursor without failing or accepting first?
26 : pub reached_target: bool,
27 : }
28 :
29 : /// The expected symbols at the cursor and the snapshot they were computed from
30 : #[derive(Clone, Debug, Default)]
31 : pub struct ExpectedAtCursor {
32 : /// The tokens the parser would eventually shift at the cursor, empty if the cursor was not reached
33 : pub expected: Vec<SymbolKind>,
34 : /// The state stack before the read of the cursor token
35 : pub prefix: PrefixSnapshot,
36 : }
37 :
38 : /// How a fed symbol fits the tokens after the cursor
39 : #[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
40 : pub struct SuffixProbe {
41 : /// Did the next real token shift after the fed symbols?
42 : pub k1_compatible: bool,
43 : /// The number of real tokens shifted before an error or the accept
44 : pub depth_consumed: u16,
45 : /// Did the replay accept?
46 : pub reached_eof: bool,
47 : }
48 :
49 : /// The token reader of the probes, a `TokenStream` without semantic values
50 : struct Tokens<'a> {
51 : /// The scanned symbols
52 : symbols: &'a [Symbol],
53 : /// The index of the next symbol to read, EOF past the end
54 : next_index: u32,
55 : }
56 :
57 : impl Tokens<'_> {
58 142698 : fn next(&mut self) -> SymbolKind {
59 142698 : match self.symbols.get(self.next_index as usize) {
60 142203 : Some(symbol) => {
61 142203 : self.next_index += 1;
62 142203 : symbol.kind
63 : }
64 495 : None => S_YYEOF,
65 : }
66 142698 : }
67 : }
68 :
69 : /// The hooks of the driver
70 : trait Policy {
71 : /// Inspect or replace a token that was just read. `pre_index` is the token index before the read,
72 : /// rewind `tokens` to it to read the real token again later.
73 : fn on_lookahead_read(&mut self, states: &[StateId], next: &mut SymbolKind, pre_index: u32, tokens: &mut Tokens, stop: &mut bool);
74 32818 : fn on_shifted(&mut self, _kind: SymbolKind) {}
75 0 : fn on_accept(&mut self) {}
76 : /// Stop instead of recovering from an error?
77 6 : fn short_circuit_on_error(&mut self, _states: &[StateId]) -> bool {
78 6 : false
79 6 : }
80 : }
81 :
82 : /// Run the automaton without actions
83 21109 : fn drive<P: Policy>(policy: &mut P, states: &mut Vec<StateId>, tokens: &mut Tokens) {
84 21109 : let mut lookahead: Option<SymbolKind> = None;
85 21109 : let mut lac_established = false;
86 21109 : let mut scratch = Vec::new();
87 21109 : let mut errstatus = 0;
88 21109 : let mut reductions_without_shift = 0;
89 :
90 : enum Label {
91 : NewState,
92 : Default,
93 : Reduce(usize),
94 : ErrLab,
95 : ErrLab1,
96 : }
97 21109 : let mut label = Label::NewState;
98 : loop {
99 2037466 : label = match label {
100 : Label::NewState => {
101 786179 : let state = *states.last().unwrap();
102 786179 : if state == YYFINAL {
103 12389 : policy.on_accept();
104 12389 : return;
105 773790 : }
106 773790 : if YYPACT[state as usize] as i32 == YYPACT_NINF {
107 259818 : Label::Default
108 : } else {
109 513972 : let kind = match lookahead {
110 371274 : Some(kind) => kind,
111 : None => {
112 142698 : let pre_index = tokens.next_index;
113 142698 : let mut next = tokens.next();
114 142698 : let mut stop = false;
115 142698 : policy.on_lookahead_read(states, &mut next, pre_index, tokens, &mut stop);
116 142698 : if stop {
117 405 : return;
118 142293 : }
119 142293 : lookahead = Some(next);
120 142293 : next
121 : }
122 : };
123 513567 : if kind == S_YYerror {
124 : // The scanner already reported the error, recover directly
125 0 : lookahead = Some(S_YYUNDEF);
126 0 : Label::ErrLab1
127 : } else {
128 513567 : let mut establish = |states: &[StateId]| {
129 379619 : if !lac_established {
130 84047 : lac_established = true;
131 84047 : return lac_check(states, kind, &mut scratch);
132 295572 : }
133 295572 : true
134 379619 : };
135 513567 : match table_action(state, kind) {
136 : None => {
137 360347 : if establish(states) {
138 351974 : Label::Default
139 : } else {
140 8373 : Label::ErrLab
141 : }
142 : }
143 0 : Some(Action::Error) => Label::ErrLab,
144 19272 : Some(Action::Reduce(rule)) => {
145 19272 : if establish(states) {
146 19272 : Label::Reduce(rule)
147 : } else {
148 0 : Label::ErrLab
149 : }
150 : }
151 133948 : Some(Action::Shift(next)) => {
152 133948 : if errstatus > 0 {
153 0 : errstatus -= 1;
154 133948 : }
155 133948 : states.push(next);
156 133948 : lookahead = None;
157 133948 : lac_established = false;
158 133948 : reductions_without_shift = 0;
159 133948 : policy.on_shifted(kind);
160 133948 : Label::NewState
161 : }
162 : }
163 : }
164 : }
165 : }
166 611792 : Label::Default => match YYDEFACT[*states.last().unwrap() as usize] as usize {
167 0 : 0 => Label::ErrLab,
168 611792 : rule => Label::Reduce(rule),
169 : },
170 631064 : Label::Reduce(rule) => {
171 631064 : reductions_without_shift += 1;
172 631064 : if reductions_without_shift > MAX_REDUCTIONS_WITHOUT_SHIFT {
173 0 : return;
174 631064 : }
175 631064 : let len = YYR2[rule] as usize;
176 631064 : let n = states.len();
177 631064 : let next = super::driver::goto_state(states[n - 1 - len], YYR1[rule] as SymbolKind);
178 631064 : states.truncate(n - len);
179 631064 : states.push(next);
180 631064 : Label::NewState
181 : }
182 : Label::ErrLab => {
183 8373 : if policy.short_circuit_on_error(states) {
184 8315 : return;
185 58 : }
186 58 : if errstatus == 3 {
187 30 : match lookahead {
188 0 : Some(S_YYEOF) => return,
189 30 : Some(_) => lookahead = None,
190 0 : None => {}
191 : }
192 28 : }
193 58 : Label::ErrLab1
194 : }
195 : Label::ErrLab1 => {
196 58 : errstatus = 3;
197 58 : let next = loop {
198 114 : if let Some(Action::Shift(next)) = table_action(*states.last().unwrap(), S_YYerror) {
199 58 : break next;
200 56 : }
201 56 : if states.len() == 1 {
202 0 : return;
203 56 : }
204 56 : states.pop();
205 : };
206 58 : lac_established = false;
207 58 : states.push(next);
208 58 : Label::NewState
209 : }
210 : };
211 : }
212 21109 : }
213 :
214 : /// All tokens that the parser would eventually shift
215 5899 : pub fn collect_expected_symbols(states: &[StateId]) -> Vec<SymbolKind> {
216 5899 : let mut scratch = Vec::new();
217 5899 : (0..YYNTOKENS as SymbolKind)
218 3014389 : .filter(|&t| t != S_YYerror && t != S_YYUNDEF && lac_check(states, t, &mut scratch))
219 5899 : .collect()
220 5899 : }
221 :
222 : /// Capture the state stack when the cursor token would be read
223 : struct PrefixCapture<'a> {
224 : /// The symbol index of the cursor token
225 : target: u32,
226 : /// The captured snapshot
227 : out: &'a mut PrefixSnapshot,
228 : }
229 :
230 : impl Policy for PrefixCapture<'_> {
231 2214 : fn on_lookahead_read(&mut self, states: &[StateId], _next: &mut SymbolKind, pre_index: u32, _tokens: &mut Tokens, stop: &mut bool) {
232 2214 : if pre_index >= self.target {
233 405 : self.out.reached_target = true;
234 405 : self.out.state_stack.extend_from_slice(states);
235 405 : *stop = true;
236 1810 : }
237 2214 : }
238 : }
239 :
240 : /// Parse until the cursor token and collect the expected symbols there
241 405 : pub fn parse_until_with_snapshot(symbols: &[Symbol], target: u32) -> ExpectedAtCursor {
242 405 : let mut out = ExpectedAtCursor::default();
243 405 : let mut states = vec![0];
244 405 : let mut tokens = Tokens { symbols, next_index: 0 };
245 405 : drive(&mut PrefixCapture { target, out: &mut out.prefix }, &mut states, &mut tokens);
246 405 : if out.prefix.reached_target && !out.prefix.state_stack.is_empty() {
247 405 : out.expected = collect_expected_symbols(&out.prefix.state_stack);
248 405 : }
249 405 : out
250 405 : }
251 :
252 : /// Replace the cursor token with a symbol, then inject COMPLETE_HERE to collect the expected
253 : /// symbols after it at the next error
254 : struct CollectAfter {
255 : /// The symbol index of the cursor token
256 : target: u32,
257 : /// The symbol that replaces the cursor token
258 : feed: SymbolKind,
259 : /// 0 = parsing, 1 = fed the symbol, 2 = injected COMPLETE_HERE
260 : phase: u8,
261 : /// The expected symbols after the fed symbol, collected at the first error after COMPLETE_HERE
262 : expected: Vec<SymbolKind>,
263 : }
264 :
265 : impl Policy for CollectAfter {
266 36533 : fn on_lookahead_read(&mut self, _states: &[StateId], next: &mut SymbolKind, pre_index: u32, _tokens: &mut Tokens, _stop: &mut bool) {
267 36533 : if self.phase == 1 {
268 5494 : *next = S_COMPLETE_HERE;
269 5494 : self.phase = 2;
270 5494 : return;
271 31039 : }
272 31039 : if self.phase == 0 && pre_index >= self.target {
273 5494 : *next = self.feed;
274 5494 : self.phase = 1;
275 25545 : }
276 36533 : }
277 5546 : fn short_circuit_on_error(&mut self, states: &[StateId]) -> bool {
278 5546 : if self.phase == 2 {
279 5494 : self.expected = collect_expected_symbols(states);
280 5494 : return true;
281 52 : }
282 52 : false
283 5546 : }
284 : }
285 :
286 : /// Parse until the cursor token, feed a symbol instead, and collect the expected symbols after it
287 5494 : pub fn parse_until_after(symbols: &[Symbol], target: u32, feed: SymbolKind) -> Vec<SymbolKind> {
288 5494 : let mut policy = CollectAfter {
289 5494 : target,
290 5494 : feed,
291 5494 : phase: 0,
292 5494 : expected: Vec::new(),
293 5494 : };
294 5494 : let mut states = vec![0];
295 5494 : let mut tokens = Tokens { symbols, next_index: 0 };
296 5494 : drive(&mut policy, &mut states, &mut tokens);
297 5494 : policy.expected
298 5494 : }
299 :
300 : /// Feed symbols at the cursor and count the real tokens that shift after them
301 : struct SuffixProbePolicy<'a> {
302 : /// The symbols fed at the cursor
303 : feed: &'a [SymbolKind],
304 : /// Does the first fed symbol replace the cursor token instead of being inserted before it?
305 : replace_target: bool,
306 : /// The probe result
307 : probe: SuffixProbe,
308 : /// The number of fed symbols
309 : fed_count: usize,
310 : /// The number of fed symbols that shifted
311 : feed_shifted: usize,
312 : }
313 :
314 : impl Policy for SuffixProbePolicy<'_> {
315 103951 : fn on_lookahead_read(&mut self, _states: &[StateId], next: &mut SymbolKind, pre_index: u32, tokens: &mut Tokens, _stop: &mut bool) {
316 103951 : if self.fed_count < self.feed.len() {
317 : // Only the first fed symbol replaces the target, all other fed symbols are insertions
318 15249 : let consumes_target = self.replace_target && self.fed_count == 0;
319 15249 : if !consumes_target {
320 39 : tokens.next_index = pre_index;
321 15210 : }
322 15249 : *next = self.feed[self.fed_count];
323 15249 : self.fed_count += 1;
324 88702 : }
325 103951 : }
326 101130 : fn on_shifted(&mut self, kind: SymbolKind) {
327 101130 : if self.feed_shifted < self.feed.len() {
328 15249 : self.feed_shifted += 1;
329 15249 : return;
330 85881 : }
331 85881 : if kind != S_YYEOF {
332 73492 : if self.probe.depth_consumed == 0 {
333 13596 : self.probe.k1_compatible = true;
334 60630 : }
335 73492 : self.probe.depth_consumed = self.probe.depth_consumed.saturating_add(1);
336 12389 : }
337 101130 : }
338 12389 : fn on_accept(&mut self) {
339 12389 : self.probe.reached_eof = true;
340 12389 : }
341 2821 : fn short_circuit_on_error(&mut self, _states: &[StateId]) -> bool {
342 : // Recovering would consume the whole suffix without telling anything about the candidate
343 2821 : self.fed_count >= 1
344 2821 : }
345 : }
346 :
347 : /// Probe a sequence of symbols fed at the cursor against the tokens after it
348 15214 : pub fn probe_suffix_sequence(symbols: &[Symbol], target: u32, prefix: &PrefixSnapshot, feed: &[SymbolKind], replace_target: bool) -> SuffixProbe {
349 15214 : if !prefix.reached_target || feed.is_empty() {
350 4 : return SuffixProbe::default();
351 15210 : }
352 15210 : let mut states = prefix.state_stack.clone();
353 15210 : if states.is_empty() {
354 0 : return SuffixProbe::default();
355 15210 : }
356 : // Advance the tokens to the target
357 15210 : let next_index = target.min(symbols.len() as u32);
358 15210 : let mut tokens = Tokens { symbols, next_index };
359 15210 : let mut policy = SuffixProbePolicy {
360 15210 : feed,
361 15210 : replace_target,
362 15210 : probe: SuffixProbe::default(),
363 15210 : fed_count: 0,
364 15210 : feed_shifted: 0,
365 15210 : };
366 15210 : drive(&mut policy, &mut states, &mut tokens);
367 15210 : policy.probe
368 15214 : }
369 :
370 : /// Probe every symbol on its own
371 42 : pub fn probe_suffix_batch(symbols: &[Symbol], target: u32, prefix: &PrefixSnapshot, feed: &[SymbolKind], replace_target: bool) -> Vec<SuffixProbe> {
372 42 : if feed.is_empty() || !prefix.reached_target {
373 0 : return vec![SuffixProbe::default(); feed.len()];
374 42 : }
375 42 : feed.iter()
376 15171 : .map(|&kind| probe_suffix_sequence(symbols, target, prefix, &[kind], replace_target))
377 42 : .collect()
378 42 : }
|
