Coverage for gws-app/gws/lib/cql/parser.py: 98%

1"""CQL2-Text parser."""

3import re

4import datetime

7def parse(s: str):

8 """Parse a CQL2-Text expression.

10 Args:

11 s: CQL2-Text expression.

13 Returns:

14 A parse tree of nested lists, see the package documentation.

16 Raises:

17 ParseError: If the expression is invalid.

18 """

20 parser = _Parser()

21 return parser.parse(s)

24class ParseError(Exception):

25 """A CQL2-Text expression is invalid. The message contains the error position."""

27 pass

30class Node:

31 """Node types of the parse tree."""

33 AND = 'AND'

34 ARRAY = 'ARRAY'

35 BETWEEN = 'BETWEEN'

36 BOOL = 'BOOL'

37 DATE = 'DATE'

38 FLOAT = 'FLOAT'

39 FUNCTION = 'FUNCTION'

40 IN = 'IN'

41 INT = 'INT'

42 IS_NULL = 'IS_NULL'

43 LIKE = 'LIKE'

44 NAME = 'NAME'

45 NEG = 'NEG'

46 NOT = 'NOT'

47 NOT_BETWEEN = 'NOT_BETWEEN'

48 NOT_IN = 'NOT_IN'

49 NOT_LIKE = 'NOT_LIKE'

50 NOT_NULL = 'NOT_NULL'

51 OR = 'OR'

52 STRING = 'STRING'

53 TIMESTAMP = 'TIMESTAMP'

54 USER_FUNCTION = 'USER_FUNCTION'

55 WKT = 'WKT'

58class C:

59 """Operator, keyword and function sets of the parser."""

61 LITERALS = {

62 Node.ARRAY,

63 Node.BOOL,

64 Node.DATE,

65 Node.FLOAT,

66 Node.INT,

67 Node.STRING,

68 Node.TIMESTAMP,

69 Node.WKT,

70 }

71 """Literal node types."""

73 COMPARISON_OPERATORS = {'=', '<>', '!=', '<', '<=', '>', '>='}

74 """Comparison operators."""

75 NOT_EQUAL_OPERATORS = {'<>', '!='}

76 """Not-equal operators, emitted as ``<>``."""

77 ADDITIVE_OPERATORS = {'+', '-'}

78 """Additive operators, also used as unary signs."""

79 MULTIPLICATIVE_OPERATORS = {'*', '/', '%'}

80 """Multiplicative operators."""

81 POWER_OPERATORS = {'^'}

82 """Power operators."""

84 OPERATORS = COMPARISON_OPERATORS | ADDITIVE_OPERATORS | MULTIPLICATIVE_OPERATORS | POWER_OPERATORS

85 """All operators."""

87 KEYWORDS = {

88 'and',

89 'or',

90 'not',

91 'is',

92 'like',

93 'between',

94 'in',

95 }

96 """Reserved keywords."""

98 PREDICATE_KEYWORDS = {

99 'not',

100 'is',

101 'like',

102 'between',

103 'in',

104 }

105 """Keywords that can follow an operand in a predicate."""

106

107 WKT_KEYWORDS = {

108 'point',

109 'linestring',

110 'polygon',

111 'multipoint',

112 'multilinestring',

113 'multipolygon',

114 'geometrycollection',

115 }

116 """Geometry types that start a WKT literal."""

117

118 FUNCTIONS = {

119 's_intersects': 2,

120 's_contains': 2,

121 's_crosses': 2,

122 's_disjoint': 2,

123 's_equals': 2,

124 's_overlaps': 2,

125 's_touches': 2,

126 's_within': 2,

127 't_after': 2,

128 't_before': 2,

129 't_contains': 2,

130 't_disjoint': 2,

131 't_during': 2,

132 't_equals': 2,

133 't_finishedby': 2,

134 't_finishes': 2,

135 't_intersects': 2,

136 't_meets': 2,

137 't_metby': 2,

138 't_overlappedby': 2,

139 't_overlaps': 2,

140 't_startedby': 2,

141 't_starts': 2,

142 'a_contains': 2,

143 'a_containedby': 2,

144 'a_equals': 2,

145 'a_overlaps': 2,

146 'bbox': 4,

147 'date': 1,

148 'timestamp': 1,

149 'interval': 2,

150 'casei': 1,

151 'accenti': 1,

152 }

153 """Standard functions and their number of arguments."""

154

155 ARRAY_FUNCTIONS = {

156 'a_contains',

157 'a_containedby',

158 'a_equals',

159 'a_overlaps',

160 }

161 """Functions whose parenthesized arguments are array literals."""

162

163 PATTERN_FUNCTIONS = {

164 'casei',

165 'accenti',

166 }

167 """Functions allowed as a ``LIKE`` pattern."""

168

169##

170

171

172class _Token:

173 """A token with its type, value and position in the input."""

174

175 def __init__(self, type: str, value, pos: int):

176 self.type = type

177 self.value = value

178 self.index = pos

179

180 def __repr__(self):

181 return f'_Token({self.type}, {self.value!r}, {self.index})'

182

183

184_TOKENS = [

185 ('WHITESPACE', r'\s+'),

186 ('TIMESTAMP', r'\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}(?:\.\d+)?Z?'),

187 ('DATE', r'\d{4}-\d{2}-\d{2}'),

188 ('NUMBER', r'-?\d+\.?\d*(?:[eE][+-]?\d+)?'),

189 ('STRING', r"'(?:[^'\\]|\\.|'')*'"),

190 ('QUOTED', r'"(?:[^"\\]|\\.|"")*"'),

191 ('IDENT', r'[a-zA-Z_][a-zA-Z0-9_]*'),

192 ('', r'<=|>=|<>|!=|[()[\],.+\-*/%^<>=]'),

193]

194

195

196class _Parser:

197 """Recursive descent parser for CQL2-Text."""

198

199 def __init__(self):

200 self.tokens = []

201 self.index = 0

202

203 def parse(self, s: str):

204 """Parse an expression and check that all input is consumed."""

205 self.tokens = list(self.tokenize(s))

206 self.tokens.append(_Token('EOF', None, len(s)))

207 self.index = 0

208

209 e = self.parse_boolean_expression()

210 if self.tok().type != 'EOF':

211 raise self.error(f'unexpected token')

212 return e

213

214 def error(self, message: str, pos=None):

215 if pos is None:

216 pos = self.tok().index

217 return ParseError(f'Parse error: {message} ({pos})')

218

219 def tokenize(self, s):

220 """Yield the tokens of the input, without whitespace."""

221 pos = 0

222 while pos < len(s):

223 tok = None

224 for typ, pattern in _TOKENS:

225 r = re.compile(pattern)

226 m = r.match(s, pos=pos)

227 if m:

228 v = m.group(0)

229 tok = _Token(typ or v, v, pos)

230 pos = m.end()

231 break

232 if tok is None:

233 raise self.error(f'unexpected character', pos)

234 if tok.type != 'WHITESPACE':

235 yield tok

236

237 ##

238

239 def tok(self) -> _Token:

240 if self.index < len(self.tokens):

241 return self.tokens[self.index]

242 return self.tokens[-1]

243

244 def peek(self, n=1) -> _Token:

245 if self.index + n < len(self.tokens):

246 return self.tokens[self.index + n]

247 return self.tokens[-1]

248

249 def pop(self) -> _Token:

250 tok = self.tok()

251 self.index += 1

252 return tok

253

254 def expect(self, token_type: str) -> _Token:

255 tok = self.tok()

256 if tok.type != token_type:

257 raise self.error(f'expected {token_type}, got {tok.type}')

258 return self.pop()

259

260 def is_a(self, token_type: str) -> bool:

261 tok = self.tok()

262 return tok.type == token_type

263

264 def is_ident(self, value: str) -> bool:

265 tok = self.tok()

266 return tok.type == 'IDENT' and tok.value.upper() == value.upper()

267

268 def expect_ident(self, value: str) -> _Token:

269 tok = self.tok()

270 if tok.type != 'IDENT' or tok.value.upper() != value.upper():

271 raise self.error(f'expected {value}, got {tok}')

272 return self.pop()

273

274 ##

275

276 def parse_boolean_expression(self):

277 return self.parse_or_expression()

278

279 def parse_or_expression(self):

280 args = [self.parse_and_expression()]

281 while self.is_ident('OR'):

282 self.pop()

283 args.append(self.parse_and_expression())

284 return [Node.OR, *args] if len(args) > 1 else args[0]

285

286 def parse_and_expression(self):

287 args = [self.parse_not_expression()]

288 while self.is_ident('AND'):

289 self.pop()

290 args.append(self.parse_not_expression())

291 return [Node.AND, *args] if len(args) > 1 else args[0]

292

293 def parse_not_expression(self):

294 if self.is_ident('NOT'):

295 self.pop()

296 e = self.parse_not_expression()

297 return [Node.NOT, e]

298 return self.parse_primary_expression()

299

300 def parse_primary_expression(self):

301 if self.is_a('('):

302 # a parenthesized group is a boolean expression, unless it turns out

303 # to be an operand, like in "(a + b) * c = 1"

304 index = self.index

305 self.pop()

306 e = self.parse_boolean_expression()

307 self.expect(')')

308 if not self.is_operand_follower():

309 return e

310 self.index = index

311 return self.parse_predicate()

312

313 def is_operand_follower(self):

314 """Check if the current token can follow an operand, i.e. is an operator or a predicate keyword."""

315 tok = self.tok()

316 if tok.type in C.OPERATORS:

317 return True

318 return tok.type == 'IDENT' and tok.value.lower() in C.PREDICATE_KEYWORDS

319

320 def parse_predicate(self):

321 tok = self.tok()

322 if tok.type == 'EOF':

323 raise self.error('unexpected end of expression')

324

325 e = self.parse_expression()

326

327 if self.is_ident('NOT'):

328 self.pop()

329 if self.is_ident('LIKE'):

330 return self.parse_like_predicate(e, True)

331 if self.is_ident('BETWEEN'):

332 return self.parse_between_predicate(e, True)

333 if self.is_ident('IN'):

334 return self.parse_in_predicate(e, True)

335 raise self.error(f'unexpected {self.tok().type!r}')

336

337 if self.is_ident('IS'):

338 return self.parse_is_null_predicate(e)

339 if self.is_ident('LIKE'):

340 return self.parse_like_predicate(e, False)

341 if self.is_ident('BETWEEN'):

342 return self.parse_between_predicate(e, False)

343 if self.is_ident('IN'):

344 return self.parse_in_predicate(e, False)

345

346 return self.parse_comparison_predicate(e)

347

348 def parse_comparison_predicate(self, e):

349 tok = self.tok()

350 if tok.type in C.COMPARISON_OPERATORS:

351 self.pop()

352 b = self.parse_expression()

353 op = '<>' if tok.type in C.NOT_EQUAL_OPERATORS else tok.type

354 return [op, e, b]

355 return e

356

357 def parse_like_predicate(self, e, is_not):

358 self.expect_ident('LIKE')

359 pattern = self.parse_pattern_expression()

360 return [Node.NOT_LIKE if is_not else Node.LIKE, e, pattern]

361

362 def parse_pattern_expression(self):

363 if self.is_a('IDENT') and self.tok().value.lower() in C.PATTERN_FUNCTIONS and self.peek().type == '(':

364 return self.parse_postfix_expression()

365 return self.parse_string_literal()

366

367 def parse_between_predicate(self, e, is_not):

368 self.expect_ident('BETWEEN')

369 a = self.parse_expression()

370 self.expect_ident('AND')

371 b = self.parse_expression()

372 return [Node.NOT_BETWEEN if is_not else Node.BETWEEN, e, a, b]

373

374 def parse_in_predicate(self, e, is_not):

375 self.expect_ident('IN')

376 if self.is_a('('):

377 self.pop()

378 a = self.parse_list(')')

379 elif self.is_a('['):

380 self.pop()

381 a = self.parse_list(']')

382 else:

383 raise self.error('expected ( or [ after IN')

384 return [Node.NOT_IN if is_not else Node.IN, e, *a]

385

386 def parse_is_null_predicate(self, e):

387 self.expect_ident('IS')

388 is_not = False

389 if self.is_ident('NOT'):

390 self.pop()

391 is_not = True

392 self.expect_ident('NULL')

393 return [Node.NOT_NULL if is_not else Node.IS_NULL, e]

394

395 def parse_expression(self):

396 return self.parse_additive_expression()

397

398 def parse_additive_expression(self):

399 a = self.parse_multiplicative_expression()

400 while self.tok().type in C.ADDITIVE_OPERATORS:

401 op = self.pop().value

402 b = self.parse_multiplicative_expression()

403 a = [op, a, b]

404 return a

405

406 def parse_multiplicative_expression(self):

407 a = self.parse_power_expression()

408 while self.tok().type in C.MULTIPLICATIVE_OPERATORS:

409 op = self.pop().value

410 b = self.parse_power_expression()

411 a = [op, a, b]

412 return a

413

414 def parse_power_expression(self):

415 a = self.parse_unary_expression()

416 while self.tok().type in C.POWER_OPERATORS:

417 op = self.pop().value

418 b = self.parse_unary_expression()

419 a = [op, a, b]

420 return a

421

422 def parse_unary_expression(self):

423 if self.tok().type in C.ADDITIVE_OPERATORS:

424 op = self.pop().value

425 e = self.parse_unary_expression()

426 if op == '-':

427 return [Node.NEG, e]

428 return e

429 return self.parse_postfix_expression()

430

431 def parse_postfix_expression(self):

432 pos = self.tok().index

433 e = self.parse_atom()

434 if self.is_a('('):

435 self.pop()

436 return self.parse_call(e, pos)

437 return e

438

439 def parse_call(self, head, pos):

440 if head[0] != Node.NAME:

441 raise self.error('invalid function name', pos)

442

443 name = '.'.join(head[1:])

444 key = name.lower()

445

446 if key in C.ARRAY_FUNCTIONS:

447 args = self.parse_array_argument_list()

448 else:

449 args = self.parse_list(')')

450

451 if key not in C.FUNCTIONS:

452 return [Node.USER_FUNCTION, name, *args]

453

454 if len(args) != C.FUNCTIONS[key]:

455 raise self.error(f'invalid number of arguments for {name!r}', pos)

456 return [Node.FUNCTION, key, *args]

457

458 def parse_atom(self):

459 tok = self.tok()

460

461 if tok.type == 'EOF':

462 raise self.error('unexpected EOF')

463

464 if self.is_a('('):

465 self.pop()

466 expr = self.parse_boolean_expression()

467 self.expect(')')

468 return expr

469

470 if self.is_a('['):

471 self.pop()

472 return [Node.ARRAY, *self.parse_list(']')]

473 if self.is_a('NUMBER'):

474 return self.parse_number_literal()

475 if self.is_a('STRING'):

476 return self.parse_string_literal()

477 if self.is_a('TIMESTAMP'):

478 return self.parse_timestamp_literal()

479 if self.is_a('DATE'):

480 return self.parse_date_literal()

481 if self.is_ident('TRUE') or self.is_ident('FALSE'):

482 return [Node.BOOL, self.pop().value.upper() == 'TRUE']

483 if self.is_a('IDENT') and self.tok().value.lower() in C.WKT_KEYWORDS:

484 p = self.peek()

485 if p.type == '(' or (p.type == 'IDENT' and p.value.upper() == 'Z'):

486 return self.parse_geometry_literal()

487 if self.is_a('IDENT') or self.is_a('QUOTED'):

488 return self.parse_name()

489

490 raise self.error(f'unexpected token: {tok.type}')

491

492 def parse_name(self):

493 parts = []

494

495 while True:

496 tok = self.tok()

497 if tok.type == 'QUOTED':

498 parts.append(self.unquote(self.pop().value))

499 elif tok.type == 'IDENT':

500 parts.append(self.pop().value)

501 else:

502 raise self.error(f'expected identifier')

503 if self.is_a('.'):

504 self.pop()

505 continue

506 break

507

508 return [Node.NAME, *parts]

509

510 def parse_number(self):

511 val = self.expect('NUMBER').value

512 if '.' in val or 'e' in val.lower():

513 return float(val)

514 return int(val)

515

516 def parse_number_literal(self):

517 val = self.parse_number()

518 return [Node.FLOAT if isinstance(val, float) else Node.INT, val]

519

520 def parse_string_literal(self):

521 val = self.expect('STRING').value

522 return [Node.STRING, self.unquote(val)]

523

524 def parse_timestamp_literal(self):

525 val = self.pop().value

526 if val.endswith('Z'):

527 val = val[:-1] + '+00:00'

528 try:

529 return [Node.TIMESTAMP, datetime.datetime.fromisoformat(val)]

530 except ValueError:

531 raise self.error(f'invalid timestamp')

532

533 def parse_date_literal(self):

534 val = self.pop().value

535 try:

536 year, month, day = val.split('-')

537 return [Node.DATE, datetime.date(int(year), int(month), int(day))]

538 except ValueError:

539 raise self.error(f'invalid date')

540

541 def parse_geometry_literal(self):

542 """Collect the tokens of a WKT literal into a normalized WKT string."""

543 parts = []

544 parens = 0

545 has_word = False

546

547 while True:

548 if self.is_a('IDENT'):

549 if has_word:

550 parts.append(' ')

551 parts.append(self.pop().value.upper())

552 has_word = True

553 elif self.is_a('NUMBER'):

554 if has_word:

555 parts.append(' ')

556 parts.append(str(self.parse_number()))

557 has_word = True

558 elif self.is_a(','):

559 self.pop()

560 parts.append(', ')

561 has_word = False

562 elif self.is_a('('):

563 self.pop()

564 parts.append('(')

565 has_word = False

566 parens += 1

567 elif self.is_a(')'):

568 self.pop()

569 parts.append(')')

570 has_word = False

571 parens -= 1

572 if parens == 0:

573 break

574 else:

575 break

576

577 return [Node.WKT, ''.join(parts)]

578

579 def parse_array_argument_list(self):

580 elements = []

581 if not self.is_a(')'):

582 elements.append(self.parse_array_argument())

583 while self.is_a(','):

584 self.pop()

585 elements.append(self.parse_array_argument())

586 self.expect(')')

587 return elements

588

589 def parse_array_argument(self):

590 """Parse an argument of an array function, a parenthesized list being an array."""

591 if self.is_a('('):

592 self.pop()

593 return [Node.ARRAY, *self.parse_list(')')]

594 return self.parse_expression()

595

596 def parse_list(self, end):

597 elements = []

598 if not self.is_a(end):

599 elements.append(self.parse_expression())

600 while self.is_a(','):

601 self.pop()

602 elements.append(self.parse_expression())

603 self.expect(end)

604 return elements

605

606 def unquote(self, s: str):

607 """Remove the quotes of a quoted string and unescape doubled and backslash-escaped quotes."""

608 quote = s[0]

609 return s[1:-1].replace('\\' + quote, quote).replace(quote + quote, quote)