1// SPDX-License-Identifier: MIT
2
3package expr
4
5import (
6 "fmt"
7 "math"
8 "strings"
9 "unicode/utf16"
10)
11
12// TokenType is the kind of a lexical token.
13type TokenType int
14
15// The token types, in the order of the reference implementation.
16const (
17 TokenUnknown TokenType = iota
18 TokenLeftParen
19 TokenRightParen
20 TokenLeftBracket
21 TokenRightBracket
22 TokenComma
23 TokenDot
24 TokenBang
25 TokenBangEqual
26 TokenEqualEqual
27 TokenGreater
28 TokenGreaterEqual
29 TokenLess
30 TokenLessEqual
31 TokenAnd
32 TokenOr
33 TokenStar
34 TokenNumber
35 TokenString
36 TokenIdentifier
37 TokenTrue
38 TokenFalse
39 TokenNull
40 TokenEOF
41)
42
43var tokenTypeNames = [...]string{
44 "UNKNOWN", "LEFT_PAREN", "RIGHT_PAREN", "LEFT_BRACKET", "RIGHT_BRACKET",
45 "COMMA", "DOT", "BANG", "BANG_EQUAL", "EQUAL_EQUAL", "GREATER",
46 "GREATER_EQUAL", "LESS", "LESS_EQUAL", "AND", "OR", "STAR", "NUMBER",
47 "STRING", "IDENTIFIER", "TRUE", "FALSE", "NULL", "EOF",
48}
49
50func (t TokenType) String() string {
51 if t >= 0 && int(t) < len(tokenTypeNames) {
52 return tokenTypeNames[t]
53 }
54 return fmt.Sprintf("TokenType(%d)", int(t))
55}
56
57// Range is the extent of a token. Both positions are on the line where the
58// token ends, as in the reference implementation.
59type Range struct {
60 Start, End Position
61}
62
63// Token is a lexical token.
64type Token struct {
65 Type TokenType
66 Lexeme string
67 Range Range
68 // Value is the number of a TokenNumber, as a [Number], or the unescaped
69 // text of a TokenString, as a [String]; nil for other tokens.
70 Value Value
71}
72
73// Lex splits an expression into tokens the way the JavaScript reference's
74// lexer does, ending with a TokenEOF token. [Parse] does not use it: it
75// follows the C# runner, whose tokenizer is context sensitive and lazy (see
76// parse_runner.go). Lex is kept because the oracle tests replay the reference's
77// tokens with it.
78func Lex(input string) ([]Token, error) {
79 if exceedsUTF16Len(input, MaxExpressionLength) {
80 // The reference throws a bare Error("ErrorExceededMaxLength") here,
81 // not the descriptive ExpressionError the parser would build. The
82 // length is checked before the input is converted so that a huge
83 // input costs no allocation.
84 return nil, &Error{Type: ErrorExceededMaxLength, Message: "ErrorExceededMaxLength"}
85 }
86 units := utf16.Encode([]rune(input))
87 lx := &lexer{input: string(utf16.Decode(units)), units: units}
88 if err := lx.lex(); err != nil {
89 return nil, err
90 }
91 return lx.tokens, nil
92}
93
94// lexer is a line-by-line port of Lexer in lexer.js. It works on UTF-16 code
95// units so that positions match the reference.
96type lexer struct {
97 input string
98 units []uint16
99 start int
100 offset int
101 line int
102 lastLineOffset int
103 tokens []Token
104}
105
106func (l *lexer) lex() error {
107 for !l.atEnd() {
108 l.start = l.offset
109 c := l.next()
110 var err error
111 switch c {
112 case '(':
113 l.addToken(TokenLeftParen, nil)
114 case ')':
115 l.addToken(TokenRightParen, nil)
116 case '[':
117 l.addToken(TokenLeftBracket, nil)
118 case ']':
119 l.addToken(TokenRightBracket, nil)
120 case ',':
121 l.addToken(TokenComma, nil)
122 case '.':
123 p := l.previous()
124 if p != TokenIdentifier && p != TokenRightBracket && p != TokenRightParen && p != TokenStar {
125 err = l.consumeNumber()
126 } else {
127 l.addToken(TokenDot, nil)
128 }
129 case '-', '+':
130 err = l.consumeNumber()
131 case '!':
132 l.addToken(l.pick('=', TokenBangEqual, TokenBang), nil)
133 case '=':
134 if !l.match('=') {
135 // Illegal; continue reading until a boundary and report it.
136 err = l.consumeIdentifier()
137 break
138 }
139 l.addToken(TokenEqualEqual, nil)
140 case '<':
141 l.addToken(l.pick('=', TokenLessEqual, TokenLess), nil)
142 case '>':
143 l.addToken(l.pick('=', TokenGreaterEqual, TokenGreater), nil)
144 case '&':
145 if !l.match('&') {
146 err = l.consumeIdentifier()
147 break
148 }
149 l.addToken(TokenAnd, nil)
150 case '|':
151 if !l.match('|') {
152 err = l.consumeIdentifier()
153 break
154 }
155 l.addToken(TokenOr, nil)
156 case '*':
157 l.addToken(TokenStar, nil)
158 case ' ', '\r', '\t':
159 // Whitespace is ignored. Only these three characters and the
160 // newline are: other Unicode spaces (U+00A0, \v, \f...) are not
161 // skipped here and fall through to the identifier rule.
162 case '\n':
163 l.line++
164 l.lastLineOffset = l.offset
165 case '\'':
166 err = l.consumeString()
167 default:
168 if c >= '0' && c <= '9' {
169 err = l.consumeNumber()
170 } else {
171 err = l.consumeIdentifier()
172 }
173 }
174 if err != nil {
175 return err
176 }
177 }
178 l.tokens = append(l.tokens, Token{Type: TokenEOF, Range: l.rng()})
179 return nil
180}
181
182func (l *lexer) pos() Position {
183 return Position{Line: l.line, Column: l.start - l.lastLineOffset}
184}
185
186func (l *lexer) rng() Range {
187 return Range{
188 Start: l.pos(),
189 End: Position{Line: l.line, Column: l.offset - l.lastLineOffset},
190 }
191}
192
193func (l *lexer) atEnd() bool { return l.offset >= len(l.units) }
194
195// peek returns the next unit without consuming it, or 0 at the end.
196func (l *lexer) peek() uint16 {
197 if l.atEnd() {
198 return 0
199 }
200 return l.units[l.offset]
201}
202
203func (l *lexer) peekNext() uint16 {
204 if l.offset+1 >= len(l.units) {
205 return 0
206 }
207 return l.units[l.offset+1]
208}
209
210func (l *lexer) previous() TokenType {
211 if len(l.tokens) == 0 {
212 return TokenEOF
213 }
214 return l.tokens[len(l.tokens)-1].Type
215}
216
217func (l *lexer) next() uint16 {
218 c := l.units[l.offset]
219 l.offset++
220 return c
221}
222
223func (l *lexer) match(expected uint16) bool {
224 if l.atEnd() || l.units[l.offset] != expected {
225 return false
226 }
227 l.offset++
228 return true
229}
230
231// pick consumes expected if it is next and returns yes, otherwise no.
232func (l *lexer) pick(expected uint16, yes, no TokenType) TokenType {
233 if l.match(expected) {
234 return yes
235 }
236 return no
237}
238
239func (l *lexer) substring(from, to int) string {
240 return string(utf16.Decode(l.units[from:to]))
241}
242
243func (l *lexer) addToken(t TokenType, v Value) {
244 l.tokens = append(l.tokens, Token{
245 Type: t,
246 Lexeme: l.substring(l.start, l.offset),
247 Range: l.rng(),
248 Value: v,
249 })
250}
251
252func (l *lexer) unexpected(lexeme string) *Error {
253 return &Error{
254 Type: ErrorUnexpectedSymbol,
255 Message: fmt.Sprintf("Unexpected symbol: '%s'. Located at position %d within expression: %s", lexeme, l.start+1, l.input),
256 Pos: l.pos(),
257 Token: lexeme,
258 }
259}
260
261func (l *lexer) consumeNumber() error {
262 for !l.atEnd() && (!isBoundary(l.peek()) || l.peek() == '.') {
263 l.next()
264 }
265 lexeme := l.substring(l.start, l.offset)
266 v := parseNumber(lexeme)
267 if math.IsNaN(v) {
268 return l.unexpected(lexeme)
269 }
270 l.addToken(TokenNumber, Number(v))
271 return nil
272}
273
274func (l *lexer) consumeString() error {
275 for (l.peek() != '\'' || l.peekNext() == '\'') && !l.atEnd() {
276 if l.peek() == '\n' {
277 l.line++
278 }
279 if l.peek() == '\'' && l.peekNext() == '\'' {
280 // Escaped quote: consume the first of the pair here.
281 l.next()
282 }
283 l.next()
284 }
285 if l.atEnd() {
286 return l.unexpected(l.substring(l.start, len(l.units)))
287 }
288 l.next() // closing quote
289 value := l.substring(l.start+1, l.offset-1)
290 // Every doubled quote is one quote. The JavaScript reference calls
291 // value.replace("''", "'") with a string pattern, which replaces only the
292 // first pair ('a''b''c' is a'b''c there); the C# runner, which is what
293 // runs on github.com, appends one quote per pair
294 // (Tokens/LexicalAnalyzer.cs ReadStringToken, "Escaped single quote"), and
295 // this package follows it. See PORTING.md.
296 value = strings.ReplaceAll(value, "''", "'")
297 l.addToken(TokenString, String(value))
298 return nil
299}
300
301func (l *lexer) consumeIdentifier() error {
302 for !l.atEnd() && !isBoundary(l.peek()) {
303 l.next()
304 }
305 tokenType := TokenIdentifier
306 var tokenValue Value
307 lexeme := l.substring(l.start, l.offset)
308 if l.previous() != TokenDot {
309 switch lexeme {
310 case "true":
311 tokenType = TokenTrue
312 case "false":
313 tokenType = TokenFalse
314 case "null":
315 tokenType = TokenNull
316 case "NaN":
317 tokenType = TokenNumber
318 tokenValue = Number(nan)
319 case "Infinity":
320 tokenType = TokenNumber
321 tokenValue = Number(posInf)
322 }
323 }
324 if !isLegalIdentifier(lexeme) {
325 return l.unexpected(lexeme)
326 }
327 l.addToken(tokenType, tokenValue)
328 return nil
329}
330
331// isBoundary reports whether c ends a number or identifier.
332func isBoundary(c uint16) bool {
333 switch c {
334 case '(', '[', ')', ']', ',', '.', '!', '>', '<', '=', '&', '|':
335 return true
336 }
337 return isJSSpace(rune(c))
338}
339
340// isLegalIdentifier reports whether s matches [A-Za-z_][A-Za-z0-9_-]*.
341func isLegalIdentifier(s string) bool {
342 if s == "" {
343 return false
344 }
345 for i := 0; i < len(s); i++ {
346 c := s[i]
347 switch {
348 case c >= 'a' && c <= 'z', c >= 'A' && c <= 'Z', c == '_':
349 case i > 0 && (c >= '0' && c <= '9' || c == '-'):
350 default:
351 return false
352 }
353 }
354 return true
355}