Appearance
| 1 | namespace Lexical is | |
| 2 | use Collections | |
| 3 | ||
| 4 | use Logging | |
| 5 | ||
| 6 | class TOKEN_QUEUE is | |
| 7 | _buffer: LIST[TOKEN_PAIR] | |
| 8 | _speculate_index: int | |
| 9 | _read_index: int // points at the last token read | |
| 10 | _write_index: int // points at the last token written | |
| 11 | _size: int | |
| 12 | ||
| 13 | count: int => (_write_index - _read_index + _size) & (_size - 1) | |
| 14 | ||
| 15 | avail: bool => count > 0 | |
| 16 | ||
| 17 | is_speculating: bool => _speculate_index != -1 | |
| 18 | ||
| 19 | _peek_offset(index: int) -> int => | |
| 20 | (_read_index + index) & (_size - 1) | |
| 21 | ||
| 22 | _next_index(index: int) -> int => | |
| 23 | (index + 1) & (_size - 1) | |
| 24 | ||
| 25 | _prev_index(index: int) -> int => | |
| 26 | (index - 1) & (_size - 1) | |
| 27 | ||
| 28 | init(size: int) is | |
| 29 | assert size > 0 else "token queue size must be greater than 0" | |
| 30 | assert (size & (size - 1)) == 0 else "token queue size must be a power of 2" | |
| 31 | ||
| 32 | _size = size | |
| 33 | _read_index = 0 | |
| 34 | _write_index = 0 | |
| 35 | _speculate_index = -1 | |
| 36 | ||
| 37 | _buffer = LIST[TOKEN_PAIR](_size) | |
| 38 | ||
| 39 | // LIST's size argument reserves capacity rather than adding | |
| 40 | // elements, so the slots have to exist before any is assigned. | |
| 41 | // Backtracking to the start of the input reads a slot no token | |
| 42 | // has been written to, so the filler is a real token meaning | |
| 43 | // "nothing has been read yet". | |
| 44 | for i in 0.._size do | |
| 45 | _buffer.add(TOKEN_PAIR(TOKEN.FIRST, Source.LOCATION.internal, "")) | |
| 46 | od | |
| 47 | si | |
| 48 | ||
| 49 | speculate_enter() is | |
| 50 | assert _speculate_index == -1 else "already speculating" | |
| 51 | _speculate_index = _read_index | |
| 52 | si | |
| 53 | ||
| 54 | speculate_exit() is | |
| 55 | assert _speculate_index != -1 else "not speculating" | |
| 56 | _speculate_index = -1 | |
| 57 | si | |
| 58 | ||
| 59 | get_read_index() -> int => _read_index | |
| 60 | ||
| 61 | mark() -> int is | |
| 62 | assert _speculate_index != -1 else "not speculating" | |
| 63 | ||
| 64 | return _read_index | |
| 65 | si | |
| 66 | ||
| 67 | release(index: int) is | |
| 68 | assert _speculate_index != -1 else "not speculating" | |
| 69 | _read_index = index | |
| 70 | si | |
| 71 | ||
| 72 | last() -> TOKEN_PAIR => _buffer[_read_index] | |
| 73 | ||
| 74 | enqueue(token: TOKEN_PAIR) is | |
| 75 | let new_write_index = _next_index(_write_index) | |
| 76 | ||
| 77 | assert new_write_index != _read_index /\ new_write_index != _speculate_index else "token queue overflow" | |
| 78 | ||
| 79 | _write_index = new_write_index | |
| 80 | ||
| 81 | _buffer[_write_index] = token | |
| 82 | si | |
| 83 | ||
| 84 | dequeue() -> TOKEN_PAIR is | |
| 85 | assert _read_index != _write_index else "token queue underflow" | |
| 86 | ||
| 87 | _read_index = _next_index(_read_index) | |
| 88 | ||
| 89 | let result = _buffer[_read_index] | |
| 90 | ||
| 91 | return result | |
| 92 | si | |
| 93 | si | |
| 94 | si |