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

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

2 

3import re 

4import datetime 

5 

6 

7def parse(s: str): 

8 """Parse a CQL2-Text expression. 

9 

10 Args: 

11 s: CQL2-Text expression. 

12 

13 Returns: 

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

15 

16 Raises: 

17 ParseError: If the expression is invalid. 

18 """ 

19 

20 parser = _Parser() 

21 return parser.parse(s) 

22 

23 

24class ParseError(Exception): 

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

26 

27 pass 

28 

29 

30class Node: 

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

32 

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 NOT = 'NOT' 

46 NOT_BETWEEN = 'NOT_BETWEEN' 

47 NOT_IN = 'NOT_IN' 

48 NOT_LIKE = 'NOT_LIKE' 

49 NOT_NULL = 'NOT_NULL' 

50 OR = 'OR' 

51 STRING = 'STRING' 

52 TIMESTAMP = 'TIMESTAMP' 

53 USER_FUNCTION = 'USER_FUNCTION' 

54 WKT = 'WKT' 

55 

56 

57class C: 

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

59 

60 LITERALS = { 

61 Node.ARRAY, 

62 Node.BOOL, 

63 Node.DATE, 

64 Node.FLOAT, 

65 Node.INT, 

66 Node.STRING, 

67 Node.TIMESTAMP, 

68 Node.WKT, 

69 } 

70 """Literal node types.""" 

71 

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

73 """Comparison operators.""" 

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

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

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

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

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

79 """Multiplicative operators.""" 

80 POWER_OPERATORS = {'^'} 

81 """Power operators.""" 

82 

83 OPERATORS = COMPARISON_OPERATORS | ADDITIVE_OPERATORS | MULTIPLICATIVE_OPERATORS | POWER_OPERATORS 

84 """All operators.""" 

85 

86 KEYWORDS = { 

87 'and', 

88 'or', 

89 'not', 

90 'is', 

91 'like', 

92 'between', 

93 'in', 

94 } 

95 """Reserved keywords.""" 

96 

97 PREDICATE_KEYWORDS = { 

98 'not', 

99 'is', 

100 'like', 

101 'between', 

102 'in', 

103 } 

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

105 

106 WKT_KEYWORDS = { 

107 'point', 

108 'linestring', 

109 'polygon', 

110 'multipoint', 

111 'multilinestring', 

112 'multipolygon', 

113 'geometrycollection', 

114 } 

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

116 

117 FUNCTIONS = { 

118 's_intersects': 2, 

119 's_contains': 2, 

120 's_crosses': 2, 

121 's_disjoint': 2, 

122 's_equals': 2, 

123 's_overlaps': 2, 

124 's_touches': 2, 

125 's_within': 2, 

126 't_after': 2, 

127 't_before': 2, 

128 't_contains': 2, 

129 't_disjoint': 2, 

130 't_during': 2, 

131 't_equals': 2, 

132 't_finishedby': 2, 

133 't_finishes': 2, 

134 't_intersects': 2, 

135 't_meets': 2, 

136 't_metby': 2, 

137 't_overlappedby': 2, 

138 't_overlaps': 2, 

139 't_startedby': 2, 

140 't_starts': 2, 

141 'a_contains': 2, 

142 'a_containedby': 2, 

143 'a_equals': 2, 

144 'a_overlaps': 2, 

145 'bbox': 4, 

146 'date': 1, 

147 'timestamp': 1, 

148 'interval': 2, 

149 'casei': 1, 

150 'accenti': 1, 

151 } 

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

153 

154 ARRAY_FUNCTIONS = { 

155 'a_contains', 

156 'a_containedby', 

157 'a_equals', 

158 'a_overlaps', 

159 } 

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

161 

162 PATTERN_FUNCTIONS = { 

163 'casei', 

164 'accenti', 

165 } 

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

167 

168## 

169 

170 

171class _Token: 

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

173 

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

175 self.type = type 

176 self.value = value 

177 self.index = pos 

178 

179 def __repr__(self): 

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

181 

182 

183_TOKENS = [ 

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

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

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

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

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

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

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

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

192] 

193 

194 

195class _Parser: 

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

197 

198 def __init__(self): 

199 self.tokens = [] 

200 self.index = 0 

201 

202 def parse(self, s: str): 

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

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

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

206 self.index = 0 

207 

208 e = self.parse_boolean_expression() 

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

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

211 return e 

212 

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

214 if pos is None: 

215 pos = self.tok().index 

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

217 

218 def tokenize(self, s): 

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

220 pos = 0 

221 while pos < len(s): 

222 tok = None 

223 for typ, pattern in _TOKENS: 

224 r = re.compile(pattern) 

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

226 if m: 

227 v = m.group(0) 

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

229 pos = m.end() 

230 break 

231 if tok is None: 

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

233 if tok.type != 'WHITESPACE': 

234 yield tok 

235 

236 def node(self, type: str, *args): 

237 return {'type': type, 'args': list(args)} 

238 

239 ## 

240 

241 def tok(self) -> _Token: 

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

243 return self.tokens[self.index] 

244 return self.tokens[-1] 

245 

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

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

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

249 return self.tokens[-1] 

250 

251 def pop(self) -> _Token: 

252 tok = self.tok() 

253 self.index += 1 

254 return tok 

255 

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

257 tok = self.tok() 

258 if tok.type != token_type: 

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

260 return self.pop() 

261 

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

263 tok = self.tok() 

264 return tok.type == token_type 

265 

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

267 tok = self.tok() 

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

269 

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

271 tok = self.tok() 

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

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

274 return self.pop() 

275 

276 ## 

277 

278 def parse_boolean_expression(self): 

279 return self.parse_or_expression() 

280 

281 def parse_or_expression(self): 

282 args = [self.parse_and_expression()] 

283 while self.is_ident('OR'): 

284 self.pop() 

285 args.append(self.parse_and_expression()) 

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

287 

288 def parse_and_expression(self): 

289 args = [self.parse_not_expression()] 

290 while self.is_ident('AND'): 

291 self.pop() 

292 args.append(self.parse_not_expression()) 

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

294 

295 def parse_not_expression(self): 

296 if self.is_ident('NOT'): 

297 self.pop() 

298 e = self.parse_not_expression() 

299 return [Node.NOT, e] 

300 return self.parse_primary_expression() 

301 

302 def parse_primary_expression(self): 

303 if self.is_a('('): 

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

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

306 index = self.index 

307 self.pop() 

308 e = self.parse_boolean_expression() 

309 self.expect(')') 

310 if not self.is_operand_follower(): 

311 return e 

312 self.index = index 

313 return self.parse_predicate() 

314 

315 def is_operand_follower(self): 

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

317 tok = self.tok() 

318 if tok.type in C.OPERATORS: 

319 return True 

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

321 

322 def parse_predicate(self): 

323 tok = self.tok() 

324 if tok.type == 'EOF': 

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

326 

327 e = self.parse_expression() 

328 

329 if self.is_ident('NOT'): 

330 self.pop() 

331 if self.is_ident('LIKE'): 

332 return self.parse_like_predicate(e, True) 

333 if self.is_ident('BETWEEN'): 

334 return self.parse_between_predicate(e, True) 

335 if self.is_ident('IN'): 

336 return self.parse_in_predicate(e, True) 

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

338 

339 if self.is_ident('IS'): 

340 return self.parse_is_null_predicate(e) 

341 if self.is_ident('LIKE'): 

342 return self.parse_like_predicate(e, False) 

343 if self.is_ident('BETWEEN'): 

344 return self.parse_between_predicate(e, False) 

345 if self.is_ident('IN'): 

346 return self.parse_in_predicate(e, False) 

347 

348 return self.parse_comparison_predicate(e) 

349 

350 def parse_comparison_predicate(self, e): 

351 tok = self.tok() 

352 if tok.type in C.COMPARISON_OPERATORS: 

353 self.pop() 

354 b = self.parse_expression() 

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

356 return [op, e, b] 

357 return e 

358 

359 def parse_like_predicate(self, e, is_not): 

360 self.expect_ident('LIKE') 

361 pattern = self.parse_pattern_expression() 

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

363 

364 def parse_pattern_expression(self): 

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

366 return self.parse_postfix_expression() 

367 return self.parse_string_literal() 

368 

369 def parse_between_predicate(self, e, is_not): 

370 self.expect_ident('BETWEEN') 

371 a = self.parse_expression() 

372 self.expect_ident('AND') 

373 b = self.parse_expression() 

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

375 

376 def parse_in_predicate(self, e, is_not): 

377 self.expect_ident('IN') 

378 if self.is_a('('): 

379 self.pop() 

380 a = self.parse_list(')') 

381 elif self.is_a('['): 

382 self.pop() 

383 a = self.parse_list(']') 

384 else: 

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

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

387 

388 def parse_is_null_predicate(self, e): 

389 self.expect_ident('IS') 

390 is_not = False 

391 if self.is_ident('NOT'): 

392 self.pop() 

393 is_not = True 

394 self.expect_ident('NULL') 

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

396 

397 def parse_expression(self): 

398 return self.parse_additive_expression() 

399 

400 def parse_additive_expression(self): 

401 a = self.parse_multiplicative_expression() 

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

403 op = self.pop().value 

404 b = self.parse_multiplicative_expression() 

405 a = [op, a, b] 

406 return a 

407 

408 def parse_multiplicative_expression(self): 

409 a = self.parse_power_expression() 

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

411 op = self.pop().value 

412 b = self.parse_power_expression() 

413 a = [op, a, b] 

414 return a 

415 

416 def parse_power_expression(self): 

417 a = self.parse_unary_expression() 

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

419 op = self.pop().value 

420 b = self.parse_unary_expression() 

421 a = [op, a, b] 

422 return a 

423 

424 def parse_unary_expression(self): 

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

426 op = self.pop().value 

427 e = self.parse_unary_expression() 

428 if op == '-': 

429 return ['-', e] 

430 return e 

431 return self.parse_postfix_expression() 

432 

433 def parse_postfix_expression(self): 

434 pos = self.tok().index 

435 e = self.parse_atom() 

436 if self.is_a('('): 

437 self.pop() 

438 return self.parse_call(e, pos) 

439 return e 

440 

441 def parse_call(self, head, pos): 

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

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

444 

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

446 key = name.lower() 

447 

448 if key in C.ARRAY_FUNCTIONS: 

449 args = self.parse_array_argument_list() 

450 else: 

451 args = self.parse_list(')') 

452 

453 if key not in C.FUNCTIONS: 

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

455 

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

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

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

459 

460 def parse_atom(self): 

461 tok = self.tok() 

462 

463 if tok.type == 'EOF': 

464 raise self.error('unexpected EOF') 

465 

466 if self.is_a('('): 

467 self.pop() 

468 expr = self.parse_boolean_expression() 

469 self.expect(')') 

470 return expr 

471 

472 if self.is_a('['): 

473 self.pop() 

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

475 if self.is_a('NUMBER'): 

476 return self.parse_number_literal() 

477 if self.is_a('STRING'): 

478 return self.parse_string_literal() 

479 if self.is_a('TIMESTAMP'): 

480 return self.parse_timestamp_literal() 

481 if self.is_a('DATE'): 

482 return self.parse_date_literal() 

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

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

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

486 p = self.peek() 

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

488 return self.parse_geometry_literal() 

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

490 return self.parse_name() 

491 

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

493 

494 def parse_name(self): 

495 parts = [] 

496 

497 while True: 

498 tok = self.tok() 

499 if tok.type == 'QUOTED': 

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

501 elif tok.type == 'IDENT': 

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

503 else: 

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

505 if self.is_a('.'): 

506 self.pop() 

507 continue 

508 break 

509 

510 return [Node.NAME, *parts] 

511 

512 def parse_number(self): 

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

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

515 return float(val) 

516 return int(val) 

517 

518 def parse_number_literal(self): 

519 val = self.parse_number() 

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

521 

522 def parse_string_literal(self): 

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

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

525 

526 def parse_timestamp_literal(self): 

527 val = self.pop().value 

528 if val.endswith('Z'): 

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

530 try: 

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

532 except ValueError: 

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

534 

535 def parse_date_literal(self): 

536 val = self.pop().value 

537 try: 

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

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

540 except ValueError: 

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

542 

543 def parse_geometry_literal(self): 

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

545 parts = [] 

546 parens = 0 

547 has_word = False 

548 

549 while True: 

550 if self.is_a('IDENT'): 

551 if has_word: 

552 parts.append(' ') 

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

554 has_word = True 

555 elif self.is_a('NUMBER'): 

556 if has_word: 

557 parts.append(' ') 

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

559 has_word = True 

560 elif self.is_a(','): 

561 self.pop() 

562 parts.append(', ') 

563 has_word = False 

564 elif self.is_a('('): 

565 self.pop() 

566 parts.append('(') 

567 has_word = False 

568 parens += 1 

569 elif self.is_a(')'): 

570 self.pop() 

571 parts.append(')') 

572 has_word = False 

573 parens -= 1 

574 if parens == 0: 

575 break 

576 else: 

577 break 

578 

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

580 

581 def parse_array_argument_list(self): 

582 elements = [] 

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

584 elements.append(self.parse_array_argument()) 

585 while self.is_a(','): 

586 self.pop() 

587 elements.append(self.parse_array_argument()) 

588 self.expect(')') 

589 return elements 

590 

591 def parse_array_argument(self): 

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

593 if self.is_a('('): 

594 self.pop() 

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

596 return self.parse_expression() 

597 

598 def parse_list(self, end): 

599 elements = [] 

600 if not self.is_a(end): 

601 elements.append(self.parse_expression()) 

602 while self.is_a(','): 

603 self.pop() 

604 elements.append(self.parse_expression()) 

605 self.expect(end) 

606 return elements 

607 

608 def unquote(self, s: str): 

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

610 quote = s[0] 

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