Appearance
| 1 | namespace Lexical is | |
| 2 | use Collections | |
| 3 | ||
| 4 | use Logging | |
| 5 | ||
| 6 | // Open so the unit-test assembly can stand in for it. Nothing | |
| 7 | // outside this compilation implements it otherwise. | |
| 8 | trait TokenSource open is | |
| 9 | read_token() -> TOKEN_PAIR | |
| 10 | expect_format_specifier() | |
| 11 | si | |
| 12 | ||
| 13 | // A backtrack to the same token position is only evidence of a | |
| 14 | // non-terminating speculation loop when no forward progress has been | |
| 15 | // committed since the last identical backtrack. `progress` is a | |
| 16 | // monotonic count of tokens consumed outside speculation; two | |
| 17 | // backtracks over the same span with different progress values mean | |
| 18 | // the parser genuinely re-parsed that span (a speculative probe | |
| 19 | // followed by the real parse, say), not that it is stuck. A true | |
| 20 | // loop never commits progress, so once its progress plateaus the | |
| 21 | // identical backtracks accumulate at a single progress value and are | |
| 22 | // still caught. | |
| 23 | class RECENT_BACKTRACK_STORE() is | |
| 24 | _recent_backtracks: | |
| 25 | ((from: int, to: int, progress: int), | |
| 26 | (from: int, to: int, progress: int), | |
| 27 | (from: int, to: int, progress: int), | |
| 28 | (from: int, to: int, progress: int), | |
| 29 | (from: int, to: int, progress: int)) | |
| 30 | ||
| 31 | record_backtrack(from: int, to: int, progress: int) is | |
| 32 | let count mut = 0 | |
| 33 | ||
| 34 | if _recent_backtracks.`0.from == from /\ | |
| 35 | _recent_backtracks.`0.to == to /\ | |
| 36 | _recent_backtracks.`0.progress == progress | |
| 37 | then | |
| 38 | count = count + 1 | |
| 39 | fi | |
| 40 | ||
| 41 | if _recent_backtracks.`1.from == from /\ | |
| 42 | _recent_backtracks.`1.to == to /\ | |
| 43 | _recent_backtracks.`1.progress == progress | |
| 44 | then | |
| 45 | count = count + 1 | |
| 46 | fi | |
| 47 | ||
| 48 | if _recent_backtracks.`2.from == from /\ | |
| 49 | _recent_backtracks.`2.to == to /\ | |
| 50 | _recent_backtracks.`2.progress == progress | |
| 51 | then | |
| 52 | count = count + 1 | |
| 53 | fi | |
| 54 | ||
| 55 | if _recent_backtracks.`3.from == from /\ | |
| 56 | _recent_backtracks.`3.to == to /\ | |
| 57 | _recent_backtracks.`3.progress == progress | |
| 58 | then | |
| 59 | count = count + 1 | |
| 60 | fi | |
| 61 | ||
| 62 | if _recent_backtracks.`4.from == from /\ | |
| 63 | _recent_backtracks.`4.to == to /\ | |
| 64 | _recent_backtracks.`4.progress == progress | |
| 65 | then | |
| 66 | count = count + 1 | |
| 67 | fi | |
| 68 | ||
| 69 | if count > 1 then | |
| 70 | debug_always("speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks}) from {System.Diagnostics.StackTrace().to_string().replace_line_endings(" ")}") | |
| 71 | throw System.Exception("speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks})") | |
| 72 | elif count > 0 then | |
| 73 | // A repeat is a near miss rather than a fault - a | |
| 74 | // speculation that legitimately retries the same span | |
| 75 | // reaches here - so it is a trace for whoever is | |
| 76 | // debugging the parser, not something to put on a user's | |
| 77 | // error output. The loop itself is caught above. | |
| 78 | debug("possible speculative parsing loop backtracking from {from} to {to} ({_recent_backtracks}) from {System.Diagnostics.StackTrace().to_string().replace_line_endings(" ")}") | |
| 79 | fi | |
| 80 | ||
| 81 | _recent_backtracks = ( | |
| 82 | _recent_backtracks.`1, | |
| 83 | _recent_backtracks.`2, | |
| 84 | _recent_backtracks.`3, | |
| 85 | _recent_backtracks.`4, | |
| 86 | (from, to, progress) | |
| 87 | ) | |
| 88 | si | |
| 89 | si | |
| 90 | ||
| 91 | class TOKEN_LOOKAHEAD( | |
| 92 | _queue: TOKEN_QUEUE, | |
| 93 | _tokenizer: TokenSource | |
| 94 | ) is | |
| 95 | _mark_stack: STACK[int] | |
| 96 | _recent_backtracks: RECENT_BACKTRACK_STORE | |
| 97 | ||
| 98 | // Monotonic count of tokens dequeued outside speculation — real | |
| 99 | // forward progress. Used to tell a re-parse of a span apart from | |
| 100 | // a genuine loop over it (see RECENT_BACKTRACK_STORE). | |
| 101 | _committed_progress: int | |
| 102 | ||
| 103 | // End line of the last token read from the tokenizer, for stamping | |
| 104 | // TOKEN_PAIR.first_on_line on each fresh token. Replayed tokens | |
| 105 | // keep the stamp they were given when first read. | |
| 106 | _last_end_line: int | |
| 107 | ||
| 108 | // Kind of the last token read from the tokenizer, for stamping | |
| 109 | // TOKEN_PAIR.follows_string the same way. | |
| 110 | _last_token: TOKEN | |
| 111 | ||
| 112 | // Start column of the first token on each source line, recorded as | |
| 113 | // that token is first read. A fact about the source, so replays | |
| 114 | // and backtracks leave it alone. | |
| 115 | _line_indents: MAP[int, int] | |
| 116 | ||
| 117 | init(..) is | |
| 118 | _mark_stack = STACK() | |
| 119 | _recent_backtracks = RECENT_BACKTRACK_STORE() | |
| 120 | _line_indents = MAP() | |
| 121 | si | |
| 122 | ||
| 123 | // Indentation of a source line whose first token has been read: | |
| 124 | // the column that token starts at. | |
| 125 | indent_of_line(line: int) -> int is | |
| 126 | let indent: int mut = _ | |
| 127 | ||
| 128 | if _line_indents.try_get_value(line, indent ref) then | |
| 129 | return indent | |
| 130 | fi | |
| 131 | ||
| 132 | return 1 | |
| 133 | si | |
| 134 | ||
| 135 | // when we first start speculating, we need to tell | |
| 136 | // the token queue to mark the read position, because | |
| 137 | // we must not write past it | |
| 138 | speculate() is | |
| 139 | if _mark_stack.count == 0 then | |
| 140 | _queue.speculate_enter() | |
| 141 | fi | |
| 142 | ||
| 143 | // FIXME: we can get the token from the previous slot | |
| 144 | // in the queue | |
| 145 | _mark_stack.push(_queue.mark()) | |
| 146 | si | |
| 147 | ||
| 148 | backtrack() -> TOKEN_PAIR => backtrack(true) | |
| 149 | ||
| 150 | // `check_for_loop` false skips the speculation-loop bookkeeping. Reserve | |
| 151 | // it for a single, provably-bounded probe that always backtracks the | |
| 152 | // same span exactly once and so cannot be a loop — a recorded backtrack | |
| 153 | // there would otherwise stack against the parsers' own speculation over | |
| 154 | // the same tokens and be mistaken for one. | |
| 155 | backtrack(check_for_loop: bool) -> TOKEN_PAIR is | |
| 156 | // we want to carry on reading tokens from the last | |
| 157 | // saved read position, effectively undoing the | |
| 158 | // speculation | |
| 159 | ||
| 160 | let current = _queue.get_read_index() | |
| 161 | let mark = _mark_stack.pop() | |
| 162 | ||
| 163 | _queue.release(mark) | |
| 164 | ||
| 165 | if _mark_stack.count == 0 then | |
| 166 | _queue.speculate_exit() | |
| 167 | fi | |
| 168 | ||
| 169 | let result = _queue.last() | |
| 170 | ||
| 171 | // Last: record_backtrack throws on a detected speculation loop, | |
| 172 | // and must not do so until the queue and speculation state above | |
| 173 | // are consistent — otherwise speculation mode is left stuck on. | |
| 174 | if check_for_loop then | |
| 175 | _recent_backtracks.record_backtrack(current, mark, _committed_progress) | |
| 176 | fi | |
| 177 | ||
| 178 | return result | |
| 179 | si | |
| 180 | ||
| 181 | commit() is | |
| 182 | // we want to discard the saved read position, and | |
| 183 | // carry on reading tokens from the current position | |
| 184 | ||
| 185 | _mark_stack.pop() | |
| 186 | ||
| 187 | // if we have no more saved read positions, then we | |
| 188 | // can tell the token queue it's safe to write past | |
| 189 | // the speculative read position again | |
| 190 | if _mark_stack.count == 0 then | |
| 191 | _queue.speculate_exit() | |
| 192 | fi | |
| 193 | si | |
| 194 | ||
| 195 | expect_format_specifier() is | |
| 196 | _tokenizer.expect_format_specifier() | |
| 197 | si | |
| 198 | ||
| 199 | read_token() -> TOKEN_PAIR is | |
| 200 | if !_queue.avail then | |
| 201 | let result = _tokenizer.read_token() | |
| 202 | ||
| 203 | result.first_on_line = result.location.start_line > _last_end_line | |
| 204 | result.follows_string = | |
| 205 | _last_token == TOKEN.STRING_LITERAL \/ _last_token == TOKEN.EXIT_STRING | |
| 206 | ||
| 207 | if result.first_on_line then | |
| 208 | _line_indents[result.location.start_line] = result.location.start_column | |
| 209 | fi | |
| 210 | ||
| 211 | _last_end_line = result.location.end_line | |
| 212 | _last_token = result.token | |
| 213 | ||
| 214 | _queue.enqueue(result) | |
| 215 | fi | |
| 216 | ||
| 217 | let result = _queue.dequeue() | |
| 218 | ||
| 219 | if _mark_stack.count == 0 then | |
| 220 | _committed_progress = _committed_progress + 1 | |
| 221 | fi | |
| 222 | ||
| 223 | return result | |
| 224 | si | |
| 225 | si | |
| 226 | si |