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 150260 : fn next(&mut self) -> SymbolKind {
59 150260 : match self.symbols.get(self.next_index as usize) {
60 149747 : Some(symbol) => {
61 149747 : self.next_index += 1;
62 149747 : symbol.kind
63 : }
64 513 : None => S_YYEOF,
65 : }
66 150260 : }
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 35873 : fn on_shifted(&mut self, _kind: SymbolKind) {}
75 0 : fn on_accept(&mut self) {}
76 : /// Stop instead of recovering from an error?
77 9 : fn short_circuit_on_error(&mut self, _states: &[StateId]) -> bool {
78 9 : false
79 9 : }
80 : }
81 :
82 : /// Run the automaton without actions
83 22345 : fn drive<P: Policy>(policy: &mut P, states: &mut Vec<StateId>, tokens: &mut Tokens) {
84 22345 : let mut lookahead: Option<SymbolKind> = None;
85 22345 : let mut lac_established = false;
86 22345 : let mut scratch = Vec::new();
87 22345 : let mut errstatus = 0;
88 22345 : let mut reductions_without_shift = 0;
89 :
90 : enum Label {
91 : NewState,
92 : Default,
93 : Reduce(usize),
94 : ErrLab,
95 : ErrLab1,
96 : }
97 22345 : let mut label = Label::NewState;
98 : loop {
99 2171489 : label = match label {
100 : Label::NewState => {
101 836937 : let state = *states.last().unwrap();
102 836937 : if state == YYFINAL {
103 13467 : policy.on_accept();
104 13467 : return;
105 823470 : }
106 823470 : if YYPACT[state as usize] as i32 == YYPACT_NINF {
107 275464 : Label::Default
108 : } else {
109 548006 : let kind = match lookahead {
110 397746 : Some(kind) => kind,
111 : None => {
112 150260 : let pre_index = tokens.next_index;
113 150260 : let mut next = tokens.next();
114 150260 : let mut stop = false;
115 150260 : policy.on_lookahead_read(states, &mut next, pre_index, tokens, &mut stop);
116 150260 : if stop {
117 408 : return;
118 149852 : }
119 149852 : lookahead = Some(next);
120 149852 : next
121 : }
122 : };
123 547598 : 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 547598 : let mut establish = |states: &[StateId]| {
129 406245 : if !lac_established {
130 89063 : lac_established = true;
131 89063 : return lac_check(states, kind, &mut scratch);
132 317182 : }
133 317182 : true
134 406245 : };
135 547598 : match table_action(state, kind) {
136 : None => {
137 385849 : if establish(states) {
138 377324 : Label::Default
139 : } else {
140 8525 : Label::ErrLab
141 : }
142 : }
143 0 : Some(Action::Error) => Label::ErrLab,
144 20396 : Some(Action::Reduce(rule)) => {
145 20396 : if establish(states) {
146 20396 : Label::Reduce(rule)
147 : } else {
148 0 : Label::ErrLab
149 : }
150 : }
151 141353 : Some(Action::Shift(next)) => {
152 141353 : if errstatus > 0 {
153 0 : errstatus -= 1;
154 141353 : }
155 141353 : states.push(next);
156 141353 : lookahead = None;
157 141353 : lac_established = false;
158 141353 : reductions_without_shift = 0;
159 141353 : policy.on_shifted(kind);
160 141353 : Label::NewState
161 : }
162 : }
163 : }
164 : }
165 : }
166 652788 : Label::Default => match YYDEFACT[*states.last().unwrap() as usize] as usize {
167 0 : 0 => Label::ErrLab,
168 652788 : rule => Label::Reduce(rule),
169 : },
170 673184 : Label::Reduce(rule) => {
171 673184 : reductions_without_shift += 1;
172 673184 : if reductions_without_shift > MAX_REDUCTIONS_WITHOUT_SHIFT {
173 0 : return;
174 673184 : }
175 673184 : let len = YYR2[rule] as usize;
176 673184 : let n = states.len();
177 673184 : let next = super::driver::goto_state(states[n - 1 - len], YYR1[rule] as SymbolKind);
178 673184 : states.truncate(n - len);
179 673184 : states.push(next);
180 673184 : Label::NewState
181 : }
182 : Label::ErrLab => {
183 8525 : if policy.short_circuit_on_error(states) {
184 8470 : return;
185 55 : }
186 55 : if errstatus == 3 {
187 29 : match lookahead {
188 0 : Some(S_YYEOF) => return,
189 29 : Some(_) => lookahead = None,
190 0 : None => {}
191 : }
192 26 : }
193 55 : Label::ErrLab1
194 : }
195 : Label::ErrLab1 => {
196 55 : errstatus = 3;
197 55 : let next = loop {
198 107 : if let Some(Action::Shift(next)) = table_action(*states.last().unwrap(), S_YYerror) {
199 55 : break next;
200 52 : }
201 52 : if states.len() == 1 {
202 0 : return;
203 52 : }
204 52 : states.pop();
205 : };
206 55 : lac_established = false;
207 55 : states.push(next);
208 55 : Label::NewState
209 : }
210 : };
211 : }
212 22345 : }
213 :
214 : /// All tokens that the parser would eventually shift
215 5898 : pub fn collect_expected_symbols(states: &[StateId]) -> Vec<SymbolKind> {
216 5898 : let mut scratch = Vec::new();
217 5898 : (0..YYNTOKENS as SymbolKind)
218 3019776 : .filter(|&t| t != S_YYerror && t != S_YYUNDEF && lac_check(states, t, &mut scratch))
219 5898 : .collect()
220 5898 : }
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 2284 : fn on_lookahead_read(&mut self, states: &[StateId], _next: &mut SymbolKind, pre_index: u32, _tokens: &mut Tokens, stop: &mut bool) {
232 2284 : if pre_index >= self.target {
233 408 : self.out.reached_target = true;
234 408 : self.out.state_stack.extend_from_slice(states);
235 408 : *stop = true;
236 1876 : }
237 2284 : }
238 : }
239 :
240 : /// Parse until the cursor token and collect the expected symbols there
241 408 : pub fn parse_until_with_snapshot(symbols: &[Symbol], target: u32) -> ExpectedAtCursor {
242 408 : let mut out = ExpectedAtCursor::default();
243 408 : let mut states = vec![0];
244 408 : let mut tokens = Tokens { symbols, next_index: 0 };
245 408 : drive(&mut PrefixCapture { target, out: &mut out.prefix }, &mut states, &mut tokens);
246 408 : if out.prefix.reached_target && !out.prefix.state_stack.is_empty() {
247 408 : out.expected = collect_expected_symbols(&out.prefix.state_stack);
248 408 : }
249 408 : out
250 408 : }
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 39516 : fn on_lookahead_read(&mut self, _states: &[StateId], next: &mut SymbolKind, pre_index: u32, _tokens: &mut Tokens, _stop: &mut bool) {
267 39516 : if self.phase == 1 {
268 5490 : *next = S_COMPLETE_HERE;
269 5490 : self.phase = 2;
270 5490 : return;
271 34026 : }
272 34026 : if self.phase == 0 && pre_index >= self.target {
273 5490 : *next = self.feed;
274 5490 : self.phase = 1;
275 28536 : }
276 39516 : }
277 5536 : fn short_circuit_on_error(&mut self, states: &[StateId]) -> bool {
278 5536 : if self.phase == 2 {
279 5490 : self.expected = collect_expected_symbols(states);
280 5490 : return true;
281 46 : }
282 46 : false
283 5536 : }
284 : }
285 :
286 : /// Parse until the cursor token, feed a symbol instead, and collect the expected symbols after it
287 5490 : pub fn parse_until_after(symbols: &[Symbol], target: u32, feed: SymbolKind) -> Vec<SymbolKind> {
288 5490 : let mut policy = CollectAfter {
289 5490 : target,
290 5490 : feed,
291 5490 : phase: 0,
292 5490 : expected: Vec::new(),
293 5490 : };
294 5490 : let mut states = vec![0];
295 5490 : let mut tokens = Tokens { symbols, next_index: 0 };
296 5490 : drive(&mut policy, &mut states, &mut tokens);
297 5490 : policy.expected
298 5490 : }
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 108460 : fn on_lookahead_read(&mut self, _states: &[StateId], next: &mut SymbolKind, pre_index: u32, tokens: &mut Tokens, _stop: &mut bool) {
316 108460 : if self.fed_count < self.feed.len() {
317 : // Only the first fed symbol replaces the target, all other fed symbols are insertions
318 16498 : let consumes_target = self.replace_target && self.fed_count == 0;
319 16498 : if !consumes_target {
320 51 : tokens.next_index = pre_index;
321 16447 : }
322 16498 : *next = self.feed[self.fed_count];
323 16498 : self.fed_count += 1;
324 91962 : }
325 108460 : }
326 105480 : fn on_shifted(&mut self, kind: SymbolKind) {
327 105480 : if self.feed_shifted < self.feed.len() {
328 16498 : self.feed_shifted += 1;
329 16498 : return;
330 88982 : }
331 88982 : if kind != S_YYEOF {
332 75515 : if self.probe.depth_consumed == 0 {
333 14673 : self.probe.k1_compatible = true;
334 61576 : }
335 75515 : self.probe.depth_consumed = self.probe.depth_consumed.saturating_add(1);
336 13467 : }
337 105480 : }
338 13467 : fn on_accept(&mut self) {
339 13467 : self.probe.reached_eof = true;
340 13467 : }
341 2980 : fn short_circuit_on_error(&mut self, _states: &[StateId]) -> bool {
342 : // Recovering would consume the whole suffix without telling anything about the candidate
343 2980 : self.fed_count >= 1
344 2980 : }
345 : }
346 :
347 : /// Probe a sequence of symbols fed at the cursor against the tokens after it
348 16451 : pub fn probe_suffix_sequence(symbols: &[Symbol], target: u32, prefix: &PrefixSnapshot, feed: &[SymbolKind], replace_target: bool) -> SuffixProbe {
349 16451 : if !prefix.reached_target || feed.is_empty() {
350 4 : return SuffixProbe::default();
351 16447 : }
352 16447 : let mut states = prefix.state_stack.clone();
353 16447 : if states.is_empty() {
354 0 : return SuffixProbe::default();
355 16447 : }
356 : // Advance the tokens to the target
357 16447 : let next_index = target.min(symbols.len() as u32);
358 16447 : let mut tokens = Tokens { symbols, next_index };
359 16447 : let mut policy = SuffixProbePolicy {
360 16447 : feed,
361 16447 : replace_target,
362 16447 : probe: SuffixProbe::default(),
363 16447 : fed_count: 0,
364 16447 : feed_shifted: 0,
365 16447 : };
366 16447 : drive(&mut policy, &mut states, &mut tokens);
367 16447 : policy.probe
368 16451 : }
369 :
370 : /// Probe every symbol on its own
371 47 : pub fn probe_suffix_batch(symbols: &[Symbol], target: u32, prefix: &PrefixSnapshot, feed: &[SymbolKind], replace_target: bool) -> Vec<SuffixProbe> {
372 47 : if feed.is_empty() || !prefix.reached_target {
373 0 : return vec![SuffixProbe::default(); feed.len()];
374 47 : }
375 47 : feed.iter()
376 16396 : .map(|&kind| probe_suffix_sequence(symbols, target, prefix, &[kind], replace_target))
377 47 : .collect()
378 47 : }
|
