ghūl coverage report

Appearance

← Back

src/lexical/token_lookahead.ghul

1
namespace Lexical is
2
use Collections;
3
4
use Logging;
5
6
trait TokenSource is
7
read_token() -> TOKEN_PAIR;
8
expect_format_specifier();
9
si
10
11
// A backtrack to the same token position is only evidence of a
12
// non-terminating speculation loop when no forward progress has been
13
// committed since the last identical backtrack. `progress` is a
14
// monotonic count of tokens consumed outside speculation; two
15
// backtracks over the same span with different progress values mean
16
// the parser genuinely re-parsed that span (a speculative probe
17
// followed by the real parse, say), not that it is stuck. A true
18
// loop never commits progress, so once its progress plateaus the
19
// identical backtracks accumulate at a single progress value and are
20
// still caught.
21
class RECENT_BACKTRACK_STORE() is
22
_recent_backtracks:
23
((from: int, to: int, progress: int),
24
(from: int, to: int, progress: int),
25
(from: int, to: int, progress: int),
26
(from: int, to: int, progress: int),
27
(from: int, to: int, progress: int));
28
29
record_backtrack(from: int, to: int, progress: int) is
30
let count mut = 0;
31
32
if _recent_backtracks.`0.from == from /\
33
_recent_backtracks.`0.to == to /\
34
_recent_backtracks.`0.progress == progress
35
then
36
count = count + 1;
37
fi
38
39
if _recent_backtracks.`1.from == from /\
40
_recent_backtracks.`1.to == to /\
41
_recent_backtracks.`1.progress == progress
42
then
43
count = count + 1;
44
fi
45
46
if _recent_backtracks.`2.from == from /\
47
_recent_backtracks.`2.to == to /\
48
_recent_backtracks.`2.progress == progress
49
then
50
count = count + 1;
51
fi
52
53
if _recent_backtracks.`3.from == from /\
54
_recent_backtracks.`3.to == to /\
55
_recent_backtracks.`3.progress == progress
56
then
57
count = count + 1;
58
fi
59
60
if _recent_backtracks.`4.from == from /\
61
_recent_backtracks.`4.to == to /\
62
_recent_backtracks.`4.progress == progress
63
then
64
count = count + 1;
65
fi
66
67
if count > 1 then
68
debug_always("speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks}) from {System.Diagnostics.StackTrace().to_string().replace_line_endings(" ")}");
69
throw System.Exception("speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks})");
70
elif count > 0 then
71
debug_always("possible speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks}) from {System.Diagnostics.StackTrace().to_string().replace_line_endings(" ")}");
72
fi
73
74
_recent_backtracks = (
75
_recent_backtracks.`1,
76
_recent_backtracks.`2,
77
_recent_backtracks.`3,
78
_recent_backtracks.`4,
79
(from, to, progress)
80
);
81
si
82
si
83
84
class TOKEN_LOOKAHEAD(
85
_queue: TOKEN_QUEUE,
86
_tokenizer: TokenSource
87
) is
88
_mark_stack: STACK[int];
89
_recent_backtracks: RECENT_BACKTRACK_STORE;
90
91
// Monotonic count of tokens dequeued outside speculation — real
92
// forward progress. Used to tell a re-parse of a span apart from
93
// a genuine loop over it (see RECENT_BACKTRACK_STORE).
94
_committed_progress: int;
95
96
init(..) is
97
_mark_stack = STACK();
98
_recent_backtracks = RECENT_BACKTRACK_STORE();
99
si
100
101
// when we first start speculating, we need to tell
102
// the token queue to mark the read position, because
103
// we must not write past it
104
speculate() is
105
if _mark_stack.count == 0 then
106
_queue.speculate_enter();
107
fi
108
109
// FIXME: we can get the token from the previous slot
110
// in the queue
111
_mark_stack.push(_queue.mark());
112
si
113
114
backtrack() -> TOKEN_PAIR => backtrack(true);
115
116
// `check_for_loop` false skips the speculation-loop bookkeeping. Reserve
117
// it for a single, provably-bounded probe that always backtracks the
118
// same span exactly once and so cannot be a loop — a recorded backtrack
119
// there would otherwise stack against the parsers' own speculation over
120
// the same tokens and be mistaken for one.
121
backtrack(check_for_loop: bool) -> TOKEN_PAIR is
122
// we want to carry on reading tokens from the last
123
// saved read position, effectively undoing the
124
// speculation
125
126
let current = _queue.get_read_index();
127
let mark = _mark_stack.pop();
128
129
_queue.release(mark);
130
131
if _mark_stack.count == 0 then
132
_queue.speculate_exit();
133
fi
134
135
let result = _queue.last();
136
137
// Last: record_backtrack throws on a detected speculation loop,
138
// and must not do so until the queue and speculation state above
139
// are consistent — otherwise speculation mode is left stuck on.
140
if check_for_loop then
141
_recent_backtracks.record_backtrack(current, mark, _committed_progress);
142
fi
143
144
return result;
145
si
146
147
commit() is
148
// we want to discard the saved read position, and
149
// carry on reading tokens from the current position
150
151
_mark_stack.pop();
152
153
// if we have no more saved read positions, then we
154
// can tell the token queue it's safe to write past
155
// the speculative read position again
156
if _mark_stack.count == 0 then
157
_queue.speculate_exit();
158
fi
159
si
160
161
expect_format_specifier() is
162
_tokenizer.expect_format_specifier();
163
si
164
165
read_token() -> TOKEN_PAIR is
166
if !_queue.avail then
167
let result = _tokenizer.read_token();
168
169
_queue.enqueue(result);
170
fi
171
172
let result = _queue.dequeue();
173
174
if _mark_stack.count == 0 then
175
_committed_progress = _committed_progress + 1;
176
fi
177
178
return result;
179
si
180
si
181
si