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

1"""CQL2-Text parser. See the package documentation for the parse tree format. 

2 

3Reference: 

4 - https://docs.ogc.org/is/21-065r2/21-065r2.html#cql2-bnf 

5""" 

6 

7import re 

8import datetime 

9 

10 

11def parse(s: str): 

12 """Parse a CQL2-Text expression. 

13 

14 Args: 

15 s: CQL2-Text expression. 

16 

17 Returns: 

18 A parse tree. 

19 

20 Raises: 

21 `ParseError` if the expression is invalid. 

22 """ 

23 

24 parser = _Parser() 

25 return parser.parse(s) 

26 

27 

28class ParseError(Exception): 

29 pass 

30 

31 

32class Node: 

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 LITERALS = { 

59 Node.ARRAY, 

60 Node.BOOL, 

61 Node.DATE, 

62 Node.FLOAT, 

63 Node.INT, 

64 Node.STRING, 

65 Node.TIMESTAMP, 

66 Node.WKT, 

67 } 

68 

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

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

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

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

73 POWER_OPERATORS = {'^'} 

74 

75 OPERATORS = COMPARISON_OPERATORS | ADDITIVE_OPERATORS | MULTIPLICATIVE_OPERATORS | POWER_OPERATORS 

76 

77 KEYWORDS = { 

78 'and', 

79 'or', 

80 'not', 

81 'is', 

82 'like', 

83 'between', 

84 'in', 

85 } 

86 

87 PREDICATE_KEYWORDS = { 

88 'not', 

89 'is', 

90 'like', 

91 'between', 

92 'in', 

93 } 

94 

95 WKT_KEYWORDS = { 

96 'point', 

97 'linestring', 

98 'polygon', 

99 'multipoint', 

100 'multilinestring', 

101 'multipolygon', 

102 'geometrycollection', 

103 } 

104 

105 FUNCTIONS = { 

106 's_intersects': 2, 

107 's_contains': 2, 

108 's_crosses': 2, 

109 's_disjoint': 2, 

110 's_equals': 2, 

111 's_overlaps': 2, 

112 's_touches': 2, 

113 's_within': 2, 

114 't_after': 2, 

115 't_before': 2, 

116 't_contains': 2, 

117 't_disjoint': 2, 

118 't_during': 2, 

119 't_equals': 2, 

120 't_finishedby': 2, 

121 't_finishes': 2, 

122 't_intersects': 2, 

123 't_meets': 2, 

124 't_metby': 2, 

125 't_overlappedby': 2, 

126 't_overlaps': 2, 

127 't_startedby': 2, 

128 't_starts': 2, 

129 'a_contains': 2, 

130 'a_containedby': 2, 

131 'a_equals': 2, 

132 'a_overlaps': 2, 

133 'bbox': 4, 

134 'date': 1, 

135 'timestamp': 1, 

136 'interval': 2, 

137 'casei': 1, 

138 'accenti': 1, 

139 } 

140 

141 ARRAY_FUNCTIONS = { 

142 'a_contains', 

143 'a_containedby', 

144 'a_equals', 

145 'a_overlaps', 

146 } 

147 

148 PATTERN_FUNCTIONS = { 

149 'casei', 

150 'accenti', 

151 } 

152 

153## 

154 

155 

156class _Token: 

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

158 self.type = type 

159 self.value = value 

160 self.index = pos 

161 

162 def __repr__(self): 

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

164 

165 

166_TOKENS = [ 

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

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

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

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

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

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

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

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

175] 

176 

177 

178class _Parser: 

179 def __init__(self): 

180 self.tokens = [] 

181 self.index = 0 

182 

183 def parse(self, s: str): 

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

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

186 self.index = 0 

187 

188 e = self.parse_boolean_expression() 

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

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

191 return e 

192 

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

194 if pos is None: 

195 pos = self.tok().index 

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

197 

198 def tokenize(self, s): 

199 pos = 0 

200 while pos < len(s): 

201 tok = None 

202 for typ, pattern in _TOKENS: 

203 r = re.compile(pattern) 

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

205 if m: 

206 v = m.group(0) 

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

208 pos = m.end() 

209 break 

210 if tok is None: 

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

212 if tok.type != 'WHITESPACE': 

213 yield tok 

214 

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

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

217 

218 ## 

219 

220 def tok(self) -> _Token: 

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

222 return self.tokens[self.index] 

223 return self.tokens[-1] 

224 

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

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

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

228 return self.tokens[-1] 

229 

230 def pop(self) -> _Token: 

231 tok = self.tok() 

232 self.index += 1 

233 return tok 

234 

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

236 tok = self.tok() 

237 if tok.type != token_type: 

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

239 return self.pop() 

240 

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

242 tok = self.tok() 

243 return tok.type == token_type 

244 

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

246 tok = self.tok() 

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

248 

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

250 tok = self.tok() 

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

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

253 return self.pop() 

254 

255 ## 

256 

257 def parse_boolean_expression(self): 

258 return self.parse_or_expression() 

259 

260 def parse_or_expression(self): 

261 args = [self.parse_and_expression()] 

262 while self.is_ident('OR'): 

263 self.pop() 

264 args.append(self.parse_and_expression()) 

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

266 

267 def parse_and_expression(self): 

268 args = [self.parse_not_expression()] 

269 while self.is_ident('AND'): 

270 self.pop() 

271 args.append(self.parse_not_expression()) 

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

273 

274 def parse_not_expression(self): 

275 if self.is_ident('NOT'): 

276 self.pop() 

277 e = self.parse_not_expression() 

278 return [Node.NOT, e] 

279 return self.parse_primary_expression() 

280 

281 def parse_primary_expression(self): 

282 if self.is_a('('): 

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

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

285 index = self.index 

286 self.pop() 

287 e = self.parse_boolean_expression() 

288 self.expect(')') 

289 if not self.is_operand_follower(): 

290 return e 

291 self.index = index 

292 return self.parse_predicate() 

293 

294 def is_operand_follower(self): 

295 tok = self.tok() 

296 if tok.type in C.OPERATORS: 

297 return True 

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

299 

300 def parse_predicate(self): 

301 tok = self.tok() 

302 if tok.type == 'EOF': 

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

304 

305 e = self.parse_expression() 

306 

307 if self.is_ident('NOT'): 

308 self.pop() 

309 if self.is_ident('LIKE'): 

310 return self.parse_like_predicate(e, True) 

311 if self.is_ident('BETWEEN'): 

312 return self.parse_between_predicate(e, True) 

313 if self.is_ident('IN'): 

314 return self.parse_in_predicate(e, True) 

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

316 

317 if self.is_ident('IS'): 

318 return self.parse_is_null_predicate(e) 

319 if self.is_ident('LIKE'): 

320 return self.parse_like_predicate(e, False) 

321 if self.is_ident('BETWEEN'): 

322 return self.parse_between_predicate(e, False) 

323 if self.is_ident('IN'): 

324 return self.parse_in_predicate(e, False) 

325 

326 return self.parse_comparison_predicate(e) 

327 

328 def parse_comparison_predicate(self, e): 

329 tok = self.tok() 

330 if tok.type in C.COMPARISON_OPERATORS: 

331 self.pop() 

332 b = self.parse_expression() 

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

334 return [op, e, b] 

335 return e 

336 

337 def parse_like_predicate(self, e, is_not): 

338 self.expect_ident('LIKE') 

339 pattern = self.parse_pattern_expression() 

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

341 

342 def parse_pattern_expression(self): 

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

344 return self.parse_postfix_expression() 

345 return self.parse_string_literal() 

346 

347 def parse_between_predicate(self, e, is_not): 

348 self.expect_ident('BETWEEN') 

349 a = self.parse_expression() 

350 self.expect_ident('AND') 

351 b = self.parse_expression() 

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

353 

354 def parse_in_predicate(self, e, is_not): 

355 self.expect_ident('IN') 

356 if self.is_a('('): 

357 self.pop() 

358 a = self.parse_list(')') 

359 elif self.is_a('['): 

360 self.pop() 

361 a = self.parse_list(']') 

362 else: 

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

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

365 

366 def parse_is_null_predicate(self, e): 

367 self.expect_ident('IS') 

368 is_not = False 

369 if self.is_ident('NOT'): 

370 self.pop() 

371 is_not = True 

372 self.expect_ident('NULL') 

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

374 

375 def parse_expression(self): 

376 return self.parse_additive_expression() 

377 

378 def parse_additive_expression(self): 

379 a = self.parse_multiplicative_expression() 

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

381 op = self.pop().value 

382 b = self.parse_multiplicative_expression() 

383 a = [op, a, b] 

384 return a 

385 

386 def parse_multiplicative_expression(self): 

387 a = self.parse_power_expression() 

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

389 op = self.pop().value 

390 b = self.parse_power_expression() 

391 a = [op, a, b] 

392 return a 

393 

394 def parse_power_expression(self): 

395 a = self.parse_unary_expression() 

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

397 op = self.pop().value 

398 b = self.parse_unary_expression() 

399 a = [op, a, b] 

400 return a 

401 

402 def parse_unary_expression(self): 

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

404 op = self.pop().value 

405 e = self.parse_unary_expression() 

406 if op == '-': 

407 return ['-', e] 

408 return e 

409 return self.parse_postfix_expression() 

410 

411 def parse_postfix_expression(self): 

412 pos = self.tok().index 

413 e = self.parse_atom() 

414 if self.is_a('('): 

415 self.pop() 

416 return self.parse_call(e, pos) 

417 return e 

418 

419 def parse_call(self, head, pos): 

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

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

422 

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

424 key = name.lower() 

425 

426 if key in C.ARRAY_FUNCTIONS: 

427 args = self.parse_array_argument_list() 

428 else: 

429 args = self.parse_list(')') 

430 

431 if key not in C.FUNCTIONS: 

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

433 

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

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

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

437 

438 def parse_atom(self): 

439 tok = self.tok() 

440 

441 if tok.type == 'EOF': 

442 raise self.error('unexpected EOF') 

443 

444 if self.is_a('('): 

445 self.pop() 

446 expr = self.parse_boolean_expression() 

447 self.expect(')') 

448 return expr 

449 

450 if self.is_a('['): 

451 self.pop() 

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

453 if self.is_a('NUMBER'): 

454 return self.parse_number_literal() 

455 if self.is_a('STRING'): 

456 return self.parse_string_literal() 

457 if self.is_a('TIMESTAMP'): 

458 return self.parse_timestamp_literal() 

459 if self.is_a('DATE'): 

460 return self.parse_date_literal() 

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

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

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

464 p = self.peek() 

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

466 return self.parse_geometry_literal() 

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

468 return self.parse_name() 

469 

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

471 

472 def parse_name(self): 

473 parts = [] 

474 

475 while True: 

476 tok = self.tok() 

477 if tok.type == 'QUOTED': 

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

479 elif tok.type == 'IDENT': 

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

481 else: 

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

483 if self.is_a('.'): 

484 self.pop() 

485 continue 

486 break 

487 

488 return [Node.NAME, *parts] 

489 

490 def parse_number(self): 

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

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

493 return float(val) 

494 return int(val) 

495 

496 def parse_number_literal(self): 

497 val = self.parse_number() 

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

499 

500 def parse_string_literal(self): 

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

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

503 

504 def parse_timestamp_literal(self): 

505 val = self.pop().value 

506 if val.endswith('Z'): 

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

508 try: 

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

510 except ValueError: 

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

512 

513 def parse_date_literal(self): 

514 val = self.pop().value 

515 try: 

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

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

518 except ValueError: 

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

520 

521 def parse_geometry_literal(self): 

522 parts = [] 

523 parens = 0 

524 has_word = False 

525 

526 while True: 

527 if self.is_a('IDENT'): 

528 if has_word: 

529 parts.append(' ') 

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

531 has_word = True 

532 elif self.is_a('NUMBER'): 

533 if has_word: 

534 parts.append(' ') 

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

536 has_word = True 

537 elif self.is_a(','): 

538 self.pop() 

539 parts.append(', ') 

540 has_word = False 

541 elif self.is_a('('): 

542 self.pop() 

543 parts.append('(') 

544 has_word = False 

545 parens += 1 

546 elif self.is_a(')'): 

547 self.pop() 

548 parts.append(')') 

549 has_word = False 

550 parens -= 1 

551 if parens == 0: 

552 break 

553 else: 

554 break 

555 

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

557 

558 def parse_array_argument_list(self): 

559 elements = [] 

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

561 elements.append(self.parse_array_argument()) 

562 while self.is_a(','): 

563 self.pop() 

564 elements.append(self.parse_array_argument()) 

565 self.expect(')') 

566 return elements 

567 

568 def parse_array_argument(self): 

569 if self.is_a('('): 

570 self.pop() 

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

572 return self.parse_expression() 

573 

574 def parse_list(self, end): 

575 elements = [] 

576 if not self.is_a(end): 

577 elements.append(self.parse_expression()) 

578 while self.is_a(','): 

579 self.pop() 

580 elements.append(self.parse_expression()) 

581 self.expect(end) 

582 return elements 

583 

584 def unquote(self, s: str): 

585 quote = s[0] 

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