Debian Codegraph @

lezer-lr/src/token.ts

raw
1 import {Input} from "@lezer/common"
2 import {Stack} from "./stack"
3 import {Seq} from "./constants"
4 import {decodeArray} from "./decode"
5
6 export class CachedToken {
7 start = -1
8 value = -1
9 end = -1
10 extended = -1
11 lookAhead = 0
12 mask = 0
13 context = 0
14 }
15
16 const nullToken = new CachedToken
17
18 /// [Tokenizers](#lr.ExternalTokenizer) interact with the input
19 /// through this interface. It presents the input as a stream of
20 /// characters, tracking lookahead and hiding the complexity of
21 /// [ranges](#common.Parser.parse^ranges) from tokenizer code.
22 export class InputStream {
23 /// @internal
24 chunk = ""
25 /// @internal
26 chunkOff = 0
27 /// @internal
28 chunkPos: number
29 /// Backup chunk
30 private chunk2 = ""
31 private chunk2Pos = 0
32
33 /// The character code of the next code unit in the input, or -1
34 /// when the stream is at the end of the input.
35 next: number = -1
36
37 /// @internal
38 token = nullToken
39
40 /// The current position of the stream. Note that, due to parses
41 /// being able to cover non-contiguous
42 /// [ranges](#common.Parser.startParse), advancing the stream does
43 /// not always mean its position moves a single unit.
44 pos: number
45
46 /// @internal
47 end: number
48
49 private rangeIndex = 0
50 private range: {from: number, to: number}
51
52 /// @internal
53 constructor(
54 /// @internal
55 readonly input: Input,
56 /// @internal
57 readonly ranges: readonly {from: number, to: number}[]
58 ) {
59 this.pos = this.chunkPos = ranges[0].from
60 this.range = ranges[0]
61 this.end = ranges[ranges.length - 1].to
62 this.readNext()
63 }
64
65 /// @internal
66 resolveOffset(offset: number, assoc: -1 | 1) {
67 let range = this.range, index = this.rangeIndex
68 let pos = this.pos + offset
69 while (pos < range.from) {
70 if (!index) return null
71 let next = this.ranges[--index]
72 pos -= range.from - next.to
73 range = next
74 }
75 while (assoc < 0 ? pos > range.to : pos >= range.to) {
76 if (index == this.ranges.length - 1) return null
77 let next = this.ranges[++index]
78 pos += next.from - range.to
79 range = next
80 }
81 return pos
82 }
83
84 /// @internal
85 clipPos(pos: number) {
86 if (pos >= this.range.from && pos < this.range.to) return pos
87 for (let range of this.ranges) if (range.to > pos) return Math.max(pos, range.from)
88 return this.end
89 }
90
91 /// Look at a code unit near the stream position. `.peek(0)` equals
92 /// `.next`, `.peek(-1)` gives you the previous character, and so
93 /// on.
94 ///
95 /// Note that looking around during tokenizing creates dependencies
96 /// on potentially far-away content, which may reduce the
97 /// effectiveness incremental parsing—when looking forward—or even
98 /// cause invalid reparses when looking backward more than 25 code
99 /// units, since the library does not track lookbehind.
100 peek(offset: number) {
101 let idx = this.chunkOff + offset, pos, result
102 if (idx >= 0 && idx < this.chunk.length) {
103 pos = this.pos + offset
104 result = this.chunk.charCodeAt(idx)
105 } else {
106 let resolved = this.resolveOffset(offset, 1)
107 if (resolved == null) return -1
108 pos = resolved
109 if (pos >= this.chunk2Pos && pos < this.chunk2Pos + this.chunk2.length) {
110 result = this.chunk2.charCodeAt(pos - this.chunk2Pos)
111 } else {
112 let i = this.rangeIndex, range = this.range
113 while (range.to <= pos) range = this.ranges[++i]
114 this.chunk2 = this.input.chunk(this.chunk2Pos = pos)
115 if (pos + this.chunk2.length > range.to) this.chunk2 = this.chunk2.slice(0, range.to - pos)
116 result = this.chunk2.charCodeAt(0)
117 }
118 }
119 if (pos >= this.token.lookAhead) this.token.lookAhead = pos + 1
120 return result
121 }
122
123 /// Accept a token. By default, the end of the token is set to the
124 /// current stream position, but you can pass an offset (relative to
125 /// the stream position) to change that.
126 acceptToken(token: number, endOffset = 0) {
127 let end = endOffset ? this.resolveOffset(endOffset, -1) : this.pos
128 if (end == null || end < this.token.start) throw new RangeError("Token end out of bounds")
129 this.token.value = token
130 this.token.end = end
131 }
132
133 /// Accept a token ending at a specific given position.
134 acceptTokenTo(token: number, endPos: number) {
135 this.token.value = token
136 this.token.end = endPos
137 }
138
139 private getChunk() {
140 if (this.pos >= this.chunk2Pos && this.pos < this.chunk2Pos + this.chunk2.length) {
141 let {chunk, chunkPos} = this
142 this.chunk = this.chunk2; this.chunkPos = this.chunk2Pos
143 this.chunk2 = chunk; this.chunk2Pos = chunkPos
144 this.chunkOff = this.pos - this.chunkPos
145 } else {
146 this.chunk2 = this.chunk; this.chunk2Pos = this.chunkPos
147 let nextChunk = this.input.chunk(this.pos)
148 let end = this.pos + nextChunk.length
149 this.chunk = end > this.range.to ? nextChunk.slice(0, this.range.to - this.pos) : nextChunk
150 this.chunkPos = this.pos
151 this.chunkOff = 0
152 }
153 }
154
155 private readNext() {
156 if (this.chunkOff >= this.chunk.length) {
157 this.getChunk()
158 if (this.chunkOff == this.chunk.length) return this.next = -1
159 }
160 return this.next = this.chunk.charCodeAt(this.chunkOff)
161 }
162
163 /// Move the stream forward N (defaults to 1) code units. Returns
164 /// the new value of [`next`](#lr.InputStream.next).
165 advance(n = 1) {
166 this.chunkOff += n
167 while (this.pos + n >= this.range.to) {
168 if (this.rangeIndex == this.ranges.length - 1) return this.setDone()
169 n -= this.range.to - this.pos
170 this.range = this.ranges[++this.rangeIndex]
171 this.pos = this.range.from
172 }
173 this.pos += n
174 if (this.pos >= this.token.lookAhead) this.token.lookAhead = this.pos + 1
175 return this.readNext()
176 }
177
178 private setDone() {
179 this.pos = this.chunkPos = this.end
180 this.range = this.ranges[this.rangeIndex = this.ranges.length - 1]
181 this.chunk = ""
182 return this.next = -1
183 }
184
185 /// @internal
186 reset(pos: number, token?: CachedToken) {
187 if (token) {
188 this.token = token
189 token.start = pos
190 token.lookAhead = pos + 1
191 token.value = token.extended = -1
192 } else {
193 this.token = nullToken
194 }
195 if (this.pos != pos) {
196 this.pos = pos
197 if (pos == this.end) {
198 this.setDone()
199 return this
200 }
201 while (pos < this.range.from) this.range = this.ranges[--this.rangeIndex]
202 while (pos >= this.range.to) this.range = this.ranges[++this.rangeIndex]
203 if (pos >= this.chunkPos && pos < this.chunkPos + this.chunk.length) {
204 this.chunkOff = pos - this.chunkPos
205 } else {
206 this.chunk = ""
207 this.chunkOff = 0
208 }
209 this.readNext()
210 }
211 return this
212 }
213
214 /// @internal
215 read(from: number, to: number) {
216 if (from >= this.chunkPos && to <= this.chunkPos + this.chunk.length)
217 return this.chunk.slice(from - this.chunkPos, to - this.chunkPos)
218 if (from >= this.chunk2Pos && to <= this.chunk2Pos + this.chunk2.length)
219 return this.chunk2.slice(from - this.chunk2Pos, to - this.chunk2Pos)
220 if (from >= this.range.from && to <= this.range.to)
221 return this.input.read(from, to)
222 let result = ""
223 for (let r of this.ranges) {
224 if (r.from >= to) break
225 if (r.to > from) result += this.input.read(Math.max(r.from, from), Math.min(r.to, to))
226 }
227 return result
228 }
229 }
230
231 export interface Tokenizer {
232 /// @internal
233 token(input: InputStream, stack: Stack): void
234 /// @internal
235 contextual: boolean
236 /// @internal
237 fallback: boolean
238 /// @internal
239 extend: boolean
240 }
241
242 /// @internal
243 export class TokenGroup implements Tokenizer {
244 contextual!: boolean
245 fallback!: boolean
246 extend!: boolean
247
248 constructor(readonly data: Readonly<Uint16Array>, readonly id: number) {}
249
250 token(input: InputStream, stack: Stack) {
251 let {parser} = stack.p
252 readToken(this.data, input, stack, this.id, parser.data, parser.tokenPrecTable)
253 }
254 }
255
256 TokenGroup.prototype.contextual = TokenGroup.prototype.fallback = TokenGroup.prototype.extend = false
257
258 /// @hide
259 export class LocalTokenGroup implements Tokenizer {
260 contextual!: boolean
261 fallback!: boolean
262 extend!: boolean
263 readonly data: Readonly<Uint16Array>
264
265 constructor(data: Readonly<Uint16Array> | string, readonly precTable: number, readonly elseToken?: number) {
266 this.data = typeof data == "string" ? decodeArray<Readonly<Uint16Array>>(data) : data
267 }
268
269 token(input: InputStream, stack: Stack) {
270 let start = input.pos, skipped = 0
271 for (;;) {
272 let atEof = input.next < 0, nextPos = input.resolveOffset(1, 1)
273 readToken(this.data, input, stack, 0, this.data, this.precTable)
274 if (input.token.value > -1) break
275 if (this.elseToken == null) return
276 if (!atEof) skipped++
277 if (nextPos == null) break
278 input.reset(nextPos, input.token)
279 }
280 if (skipped) {
281 input.reset(start, input.token)
282 input.acceptToken(this.elseToken!, skipped)
283 }
284 }
285 }
286
287 LocalTokenGroup.prototype.contextual = TokenGroup.prototype.fallback = TokenGroup.prototype.extend = false
288
289 interface ExternalOptions {
290 /// When set to true, mark this tokenizer as depending on the
291 /// current parse stack, which prevents its result from being cached
292 /// between parser actions at the same positions.
293 contextual?: boolean,
294 /// By defaults, when a tokenizer returns a token, that prevents
295 /// tokenizers with lower precedence from even running. When
296 /// `fallback` is true, the tokenizer is allowed to run when a
297 /// previous tokenizer returned a token that didn't match any of the
298 /// current state's actions.
299 fallback?: boolean
300 /// When set to true, tokenizing will not stop after this tokenizer
301 /// has produced a token. (But it will still fail to reach this one
302 /// if a higher-precedence tokenizer produced a token.)
303 extend?: boolean
304 }
305
306 /// `@external tokens` declarations in the grammar should resolve to
307 /// an instance of this class.
308 export class ExternalTokenizer {
309 /// @internal
310 contextual: boolean
311 /// @internal
312 fallback: boolean
313 /// @internal
314 extend: boolean
315
316 /// Create a tokenizer. The first argument is the function that,
317 /// given an input stream, scans for the types of tokens it
318 /// recognizes at the stream's position, and calls
319 /// [`acceptToken`](#lr.InputStream.acceptToken) when it finds
320 /// one.
321 constructor(
322 /// @internal
323 readonly token: (input: InputStream, stack: Stack) => void,
324 options: ExternalOptions = {}
325 ) {
326 this.contextual = !!options.contextual
327 this.fallback = !!options.fallback
328 this.extend = !!options.extend
329 }
330 }
331
332 // Tokenizer data is stored a big uint16 array containing, for each
333 // state:
334 //
335 // - A group bitmask, indicating what token groups are reachable from
336 // this state, so that paths that can only lead to tokens not in
337 // any of the current groups can be cut off early.
338 //
339 // - The position of the end of the state's sequence of accepting
340 // tokens
341 //
342 // - The number of outgoing edges for the state
343 //
344 // - The accepting tokens, as (token id, group mask) pairs
345 //
346 // - The outgoing edges, as (start character, end character, state
347 // index) triples, with end character being exclusive
348 //
349 // This function interprets that data, running through a stream as
350 // long as new states with the a matching group mask can be reached,
351 // and updating `input.token` when it matches a token.
352 function readToken(data: Readonly<Uint16Array>,
353 input: InputStream,
354 stack: Stack,
355 group: number,
356 precTable: Readonly<Uint16Array>,
357 precOffset: number) {
358 let state = 0, groupMask = 1 << group, {dialect} = stack.p.parser
359 scan: for (;;) {
360 if ((groupMask & data[state]) == 0) break
361 let accEnd = data[state + 1]
362 // Check whether this state can lead to a token in the current group
363 // Accept tokens in this state, possibly overwriting
364 // lower-precedence / shorter tokens
365 for (let i = state + 3; i < accEnd; i += 2) if ((data[i + 1] & groupMask) > 0) {
366 let term = data[i]
367 if (dialect.allows(term) &&
368 (input.token.value == -1 || input.token.value == term ||
369 overrides(term, input.token.value, precTable, precOffset))) {
370 input.acceptToken(term)
371 break
372 }
373 }
374 let next = input.next, low = 0, high = data[state + 2]
375 // Special case for EOF
376 if (input.next < 0 && high > low && data[accEnd + high * 3 - 3] == Seq.End) {
377 state = data[accEnd + high * 3 - 1]
378 continue scan
379 }
380 // Do a binary search on the state's edges
381 for (; low < high;) {
382 let mid = (low + high) >> 1
383 let index = accEnd + mid + (mid << 1)
384 let from = data[index], to = data[index + 1] || 0x10000
385 if (next < from) high = mid
386 else if (next >= to) low = mid + 1
387 else { state = data[index + 2]; input.advance(); continue scan }
388 }
389 break
390 }
391 }
392
393 function findOffset(data: Readonly<Uint16Array>, start: number, term: number) {
394 for (let i = start, next; (next = data[i]) != Seq.End; i++)
395 if (next == term) return i - start
396 return -1
397 }
398
399 function overrides(token: number, prev: number, tableData: Readonly<Uint16Array>, tableOffset: number) {
400 let iPrev = findOffset(tableData, tableOffset, prev)
401 return iPrev < 0 || findOffset(tableData, tableOffset, token) < iPrev
402 }