UNIXworkcode

1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3 * 4 * Copyright 2018 Olaf Wintermann. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #include "davqlparser.h" 30 #include <cx/utils.h> 31 #include <cx/linked_list.h> 32 #include <cx/printf.h> 33 #include <string.h> 34 #include <stdio.h> 35 #include <ctype.h> 36 37 #define sfmtarg(s) ((int)(s).length), (s).ptr 38 39 // ------------------------------------------------------------------------ 40 // D E B U G E R 41 // ------------------------------------------------------------------------ 42 43 static const char* _map_querytype(davqltype_t type) { 44 switch(type) { 45 case DAVQL_ERROR: return "ERROR"; 46 case DAVQL_SELECT: return "SELECT"; 47 case DAVQL_SET: return "SET"; 48 default: return "unknown"; 49 } 50 } 51 52 static const char* _map_exprtype(davqlexprtype_t type) { 53 switch(type) { 54 case DAVQL_UNDEFINED_TYPE: return "undefined"; 55 case DAVQL_NUMBER: return "NUMBER"; 56 case DAVQL_STRING: return "STRING"; 57 case DAVQL_TIMESTAMP: return "TIMESTAMP"; 58 case DAVQL_IDENTIFIER: return "IDENTIFIER"; 59 case DAVQL_UNARY: return "UNARY"; 60 case DAVQL_BINARY: return "BINARY"; 61 case DAVQL_LOGICAL: return "LOGICAL"; 62 case DAVQL_FUNCCALL: return "FUNCCALL"; 63 default: return "unknown"; 64 } 65 } 66 67 static const char* _map_specialfield(int info) { 68 switch(info) { 69 case 0: return ""; 70 case 1: return "with wildcard"; 71 case 2: return "(resource data only)"; 72 default: return "with mysterious identifier"; 73 } 74 } 75 76 static const char* _map_operator(davqloperator_t op) { 77 // don't use string array, because enum values may change 78 switch(op) { 79 case DAVQL_NOOP: return "no operator"; 80 case DAVQL_CALL: return "function call"; case DAVQL_ARGLIST: return ","; 81 case DAVQL_ADD: return "+"; case DAVQL_SUB: return "-"; 82 case DAVQL_MUL: return "*"; case DAVQL_DIV: return "/"; 83 case DAVQL_AND: return "&"; case DAVQL_OR: return "|"; 84 case DAVQL_XOR: return "^"; case DAVQL_NEG: return "~"; 85 case DAVQL_NOT: return "NOT"; case DAVQL_LAND: return "AND"; 86 case DAVQL_LOR: return "OR"; case DAVQL_LXOR: return "XOR"; 87 case DAVQL_EQ: return "="; case DAVQL_NEQ: return "!="; 88 case DAVQL_LT: return "<"; case DAVQL_GT: return ">"; 89 case DAVQL_LE: return "<="; case DAVQL_GE: return ">="; 90 case DAVQL_LIKE: return "LIKE"; case DAVQL_UNLIKE: return "UNLIKE"; 91 default: return "unknown"; 92 } 93 } 94 95 static void dav_debug_ql_fnames_print(DavQLStatement *stmt) { 96 if (stmt->fields) { 97 printf("Field names: "); 98 CxIterator i = cxListIterator(stmt->fields); 99 cx_foreach(DavQLField *, f, i) { 100 printf("%.*s, ", (int)f->name.length, f->name.ptr); 101 } 102 printf("\b\b \b\b\n"); 103 } 104 } 105 106 static void dav_debug_ql_stmt_print(DavQLStatement *stmt) { 107 // Basic information 108 size_t fieldcount = stmt->fields ? cxListSize(stmt->fields) : 0; 109 int specialfield = 0; 110 if (fieldcount > 0) { 111 DavQLField* firstfield = (DavQLField*)cxListAt(stmt->fields, 0); 112 if (firstfield->expr->type == DAVQL_IDENTIFIER) { 113 switch (firstfield->expr->srctext.ptr[0]) { 114 case '*': specialfield = 1; break; 115 case '-': specialfield = 2; break; 116 } 117 } 118 } 119 if (specialfield) { 120 fieldcount--; 121 } 122 printf("Statement: %.*s\nType: %s\nField count: %zu %s\n", 123 (int)stmt->srctext.length, stmt->srctext.ptr, 124 _map_querytype(stmt->type), 125 fieldcount, 126 _map_specialfield(specialfield)); 127 128 dav_debug_ql_fnames_print(stmt); 129 printf("Path: %.*s\nHas where clause: %s\n", 130 (int)stmt->path.length, stmt->path.ptr, 131 stmt->where ? "yes" : "no"); 132 133 // WITH attributes 134 if (stmt->depth == DAV_DEPTH_INFINITY) { 135 printf("Depth: infinity\n"); 136 } else if (stmt->depth == DAV_DEPTH_PLACEHOLDER) { 137 printf("Depth: placeholder\n"); 138 } else { 139 printf("Depth: %d\n", stmt->depth); 140 } 141 142 // order by clause 143 printf("Order by: "); 144 if (stmt->orderby) { 145 CxIterator i = cxListIterator(stmt->orderby); 146 cx_foreach(DavQLOrderCriterion*, critdata, i) { 147 printf("%.*s %s%s", (int)critdata->column->srctext.length, critdata->column->srctext.ptr, 148 critdata->descending ? "desc" : "asc", 149 i.index+1 < cxListSize(stmt->orderby) ? ", " : "\n"); 150 } 151 } else { 152 printf("nothing\n"); 153 } 154 155 // error messages 156 if (stmt->errorcode) { 157 printf("\nError code: %d\nError: %s\n", 158 stmt->errorcode, stmt->errormessage); 159 } 160 } 161 162 static int dav_debug_ql_expr_selected(DavQLExpression *expr) { 163 if (!expr) { 164 printf("Currently no expression selected.\n"); 165 return 0; 166 } else { 167 return 1; 168 } 169 } 170 171 static void dav_debug_ql_expr_print(DavQLExpression *expr) { 172 if (dav_debug_ql_expr_selected(expr)) { 173 cxstring empty = CX_STR("(empty)"); 174 printf( 175 "Text: %.*s\nType: %s\nOperator: %s\n", 176 sfmtarg(expr->srctext), 177 _map_exprtype(expr->type), 178 _map_operator(expr->op)); 179 if (expr->left || expr->right) { 180 printf("Left hand: %.*s\nRight hand: %.*s\n", 181 sfmtarg(expr->left?expr->left->srctext:empty), 182 sfmtarg(expr->right?expr->right->srctext:empty)); 183 } 184 } 185 } 186 187 static void dav_debug_ql_field_print(DavQLField *field) { 188 if (field) { 189 printf("Name: %.*s\n", sfmtarg(field->name)); 190 if (field->expr) { 191 dav_debug_ql_expr_print(field->expr); 192 } else { 193 printf("No expression.\n"); 194 } 195 } else { 196 printf("No field selected.\n"); 197 } 198 } 199 200 static void dav_debug_ql_tree_print(DavQLExpression *expr, int depth) { 201 if (expr) { 202 if (expr->left) { 203 printf("%*c%s\n", depth, ' ', _map_operator(expr->op)); 204 dav_debug_ql_tree_print(expr->left, depth+1); 205 dav_debug_ql_tree_print(expr->right, depth+1); 206 } else if (expr->type == DAVQL_UNARY) { 207 printf("%*c%s %.*s\n", depth, ' ', _map_operator(expr->op), 208 sfmtarg(expr->srctext)); 209 } else { 210 printf("%*c%.*s\n", depth, ' ', sfmtarg(expr->srctext)); 211 } 212 } 213 } 214 215 #define DQLD_CMD_Q 0 216 #define DQLD_CMD_PS 1 217 #define DQLD_CMD_PE 2 218 #define DQLD_CMD_PF 3 219 #define DQLD_CMD_PT 4 220 #define DQLD_CMD_F 10 221 #define DQLD_CMD_W 11 222 #define DQLD_CMD_O 12 223 #define DQLD_CMD_L 21 224 #define DQLD_CMD_R 22 225 #define DQLD_CMD_N 23 226 #define DQLD_CMD_P 24 227 #define DQLD_CMD_H 100 228 229 static int dav_debug_ql_command() { 230 printf("> "); 231 232 char buffer[8]; 233 fgets(buffer, 8, stdin); 234 // discard remaining chars 235 if (!strchr(buffer, '\n')) { 236 int chr; 237 while ((chr = fgetc(stdin) != '\n') && chr != EOF); 238 } 239 240 if (!strcmp(buffer, "q\n")) { 241 return DQLD_CMD_Q; 242 } else if (!strcmp(buffer, "ps\n")) { 243 return DQLD_CMD_PS; 244 } else if (!strcmp(buffer, "pe\n")) { 245 return DQLD_CMD_PE; 246 } else if (!strcmp(buffer, "pf\n")) { 247 return DQLD_CMD_PF; 248 } else if (!strcmp(buffer, "pt\n")) { 249 return DQLD_CMD_PT; 250 } else if (!strcmp(buffer, "l\n")) { 251 return DQLD_CMD_L; 252 } else if (!strcmp(buffer, "r\n")) { 253 return DQLD_CMD_R; 254 } else if (!strcmp(buffer, "h\n")) { 255 return DQLD_CMD_H; 256 } else if (!strcmp(buffer, "f\n")) { 257 return DQLD_CMD_F; 258 } else if (!strcmp(buffer, "w\n")) { 259 return DQLD_CMD_W; 260 } else if (!strcmp(buffer, "o\n")) { 261 return DQLD_CMD_O; 262 } else if (!strcmp(buffer, "n\n")) { 263 return DQLD_CMD_N; 264 } else if (!strcmp(buffer, "p\n")) { 265 return DQLD_CMD_P; 266 } else { 267 return -1; 268 } 269 } 270 271 void dav_debug_statement(DavQLStatement *stmt) { 272 if (!stmt) { 273 fprintf(stderr, "Debug DavQLStatement failed: null pointer"); 274 return; 275 } 276 277 printf("Starting DavQL debugger (type ''h'' for help)...\n\n"); 278 dav_debug_ql_stmt_print(stmt); 279 280 if (stmt->errorcode) { 281 return; 282 } 283 284 DavQLExpression *examineexpr = NULL; 285 CxList *examineelem = NULL; 286 int examineclause = 0; 287 288 while(1) { 289 int cmd = dav_debug_ql_command(); 290 switch (cmd) { 291 case DQLD_CMD_Q: return; 292 case DQLD_CMD_PS: dav_debug_ql_stmt_print(stmt); break; 293 case DQLD_CMD_PE: dav_debug_ql_expr_print(examineexpr); break; 294 case DQLD_CMD_PT: dav_debug_ql_tree_print(examineexpr, 1); break; 295 case DQLD_CMD_PF: dav_debug_ql_fnames_print(stmt); break; 296 case DQLD_CMD_F: 297 examineclause = DQLD_CMD_F; 298 examineelem = stmt->fields; 299 if (stmt->fields && cxListSize(stmt->fields) > 0) { 300 DavQLField* field = cxListAt(stmt->fields, 0); 301 examineexpr = field->expr; 302 dav_debug_ql_field_print(field); 303 } else { 304 examineexpr = NULL; 305 } 306 break; 307 case DQLD_CMD_W: 308 examineclause = 0; examineelem = NULL; 309 examineexpr = stmt->where; 310 dav_debug_ql_expr_print(examineexpr); 311 break; 312 case DQLD_CMD_O: 313 examineclause = DQLD_CMD_O; 314 examineelem = stmt->orderby; 315 examineexpr = stmt->orderby && cxListSize(stmt->orderby) > 0 ? 316 ((DavQLOrderCriterion*)cxListAt(stmt->orderby, 0))->column : NULL; 317 dav_debug_ql_expr_print(examineexpr); 318 break; 319 case DQLD_CMD_N: 320 case DQLD_CMD_P: 321 printf("TODO: port code to ucx 3\n"); 322 /* 323 if (examineelem) { 324 CxList *newelem = (cmd == DQLD_CMD_N ? 325 examineelem->next : examineelem->prev); 326 if (newelem) { 327 examineelem = newelem; 328 if (examineclause == DQLD_CMD_O) { 329 examineexpr = ((DavQLOrderCriterion*) 330 examineelem->data)->column; 331 dav_debug_ql_expr_print(examineexpr); 332 } else if (examineclause == DQLD_CMD_F) { 333 DavQLField* field = (DavQLField*)examineelem->data; 334 examineexpr = field->expr; 335 dav_debug_ql_field_print(field); 336 } else { 337 printf("Examining unknown clause type."); 338 } 339 } else { 340 printf("Reached end of list.\n"); 341 } 342 } else { 343 printf("Currently not examining an expression list.\n"); 344 } 345 */ 346 break; 347 case DQLD_CMD_L: 348 if (dav_debug_ql_expr_selected(examineexpr)) { 349 if (examineexpr->left) { 350 examineexpr = examineexpr->left; 351 dav_debug_ql_expr_print(examineexpr); 352 } else { 353 printf("There is no left subtree.\n"); 354 } 355 } 356 break; 357 case DQLD_CMD_R: 358 if (dav_debug_ql_expr_selected(examineexpr)) { 359 if (examineexpr->right) { 360 examineexpr = examineexpr->right; 361 dav_debug_ql_expr_print(examineexpr); 362 } else { 363 printf("There is no right subtree.\n"); 364 } 365 } 366 break; 367 case DQLD_CMD_H: 368 printf( 369 "\nCommands:\n" 370 "ps: print statement information\n" 371 "o: examine order by clause\n" 372 "f: examine field list\n" 373 "pf: print field names\n" 374 "w: examine where clause\n" 375 "n: examine next expression " 376 "(in order by clause or field list)\n" 377 "p: examine previous expression " 378 "(in order by clause or field list)\n" 379 "q: quit\n\n" 380 "\nExpression examination:\n" 381 "pe: print expression information\n" 382 "pt: print full syntax tree of current (sub-)expression\n" 383 "l: enter left subtree\n" 384 "r: enter right subtree\n"); 385 break; 386 default: printf("unknown command\n"); 387 } 388 } 389 } 390 391 // ------------------------------------------------------------------------ 392 // P A R S E R 393 // ------------------------------------------------------------------------ 394 395 #define _error_context "(%.*s[->]%.*s%.*s)" 396 #define _error_invalid "invalid statement" 397 #define _error_out_of_memory "out of memory" 398 #define _error_unexpected_token "unexpected token " _error_context 399 #define _error_invalid_token "invalid token " _error_context 400 #define _error_missing_path "expected path " _error_context 401 #define _error_missing_from "expecting FROM keyword " _error_context 402 #define _error_missing_at "expecting AT keyword " _error_context 403 #define _error_missing_by "expecting BY keyword " _error_context 404 #define _error_missing_as "expecting alias (''as <identifier>'') " _error_context 405 #define _error_missing_identifier "expecting identifier " _error_context 406 #define _error_missing_par "missing closed parenthesis " _error_context 407 #define _error_missing_assign "expecting assignment (''='') " _error_context 408 #define _error_missing_where "SET statements must have a WHERE clause or " \ 409 "explicitly use ANYWHERE " _error_context 410 #define _error_invalid_depth "invalid depth " _error_context 411 #define _error_missing_expr "missing expression " _error_context 412 #define _error_invalid_expr "invalid expression " _error_context 413 #define _error_invalid_unary_op "invalid unary operator " _error_context 414 #define _error_invalid_logical_op "invalid logical operator " _error_context 415 #define _error_invalid_fmtspec "invalid format specifier " _error_context 416 #define _error_invalid_string "string expected " _error_context 417 #define _error_invalid_order_criterion "invalid order criterion " _error_context 418 419 #define token_sstr(token) ((token)->value) 420 421 static void dav_error_in_context(int errorcode, const char *errormsg, 422 DavQLStatement *stmt, DavQLToken *token) { 423 424 // we try to achieve two things: get as many information as possible 425 // and recover the concrete source string (and not the token strings) 426 cxstring emptystring = CX_STR(""); 427 cxstring prev = token->prev ? (token->prev->prev ? 428 token_sstr(token->prev->prev) : token_sstr(token->prev)) 429 : emptystring; 430 cxstring tokenstr = token_sstr(token); 431 cxstring next = token->next ? (token->next->next ? 432 token_sstr(token->next->next) : token_sstr(token->next)) 433 : emptystring; 434 435 int lp = prev.length == 0 ? 0 : tokenstr.ptr-prev.ptr; 436 const char *pn = tokenstr.ptr + tokenstr.length; 437 int ln = next.ptr+next.length - pn; 438 439 stmt->errorcode = errorcode; 440 stmt->errormessage = cx_asprintf(errormsg, 441 lp, prev.ptr, 442 sfmtarg(tokenstr), 443 ln, pn).ptr; 444 } 445 446 #define dqlsec_alloc_failed(ptr, stmt) \ 447 if (!(ptr)) do { \ 448 (stmt)->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; \ 449 return 0; \ 450 } while(0) 451 #define dqlsec_malloc(stmt, ptr, type) \ 452 dqlsec_alloc_failed(ptr = malloc(sizeof(type)), stmt) 453 #define dqlsec_mallocz(stmt, ptr, type) \ 454 dqlsec_alloc_failed(ptr = calloc(1, sizeof(type)), stmt) 455 456 457 // special symbols are single tokens - the % sign MUST NOT be a special symbol 458 static const char *special_token_symbols = ",()+-*/&|^~=!<>"; 459 460 static _Bool iskeyword(DavQLToken *token) { 461 cxstring keywords[] ={CX_STR("select"), CX_STR("set"), CX_STR("from"), CX_STR("at"), CX_STR("as"), 462 CX_STR("where"), CX_STR("anywhere"), CX_STR("like"), CX_STR("unlike"), CX_STR("and"), 463 CX_STR("or"), CX_STR("not"), CX_STR("xor"), CX_STR("with"), CX_STR("infinity"), 464 CX_STR("order"), CX_STR("by"), CX_STR("asc"), CX_STR("desc") 465 }; 466 for (int i = 0 ; i < sizeof(keywords)/sizeof(cxstring) ; i++) { 467 if (!cx_strcasecmp(token->value, keywords[i])) { 468 return 1; 469 } 470 } 471 return 0; 472 } 473 474 static _Bool islongoperator(DavQLToken *token) { 475 cxstring operators[] = {CX_STR("and"), CX_STR("or"), CX_STR("not"), CX_STR("xor"), 476 CX_STR("like"), CX_STR("unlike") 477 }; 478 for (int i = 0 ; i < sizeof(operators)/sizeof(cxstring) ; i++) { 479 if (!cx_strcasecmp(token->value, operators[i])) { 480 return 1; 481 } 482 } 483 return 0; 484 } 485 486 static int dav_stmt_add_field(DavQLStatement *stmt, DavQLField *field) { 487 if(!stmt->fields) { 488 stmt->fields = cxLinkedListCreateSimple(CX_STORE_POINTERS); 489 if(!stmt->fields) { 490 stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; 491 return 1; 492 } 493 } 494 495 if(cxListAdd(stmt->fields, field)) { 496 stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; 497 return 1; 498 } 499 500 return 0; 501 } 502 503 504 static void tokenlist_free(DavQLToken *tokenlist) { 505 DavQLToken *token = tokenlist; 506 while(token) { 507 DavQLToken *next = token->next; 508 free(token); 509 token = next; 510 } 511 } 512 513 static int dav_parse_add_token(DavQLToken **begin, DavQLToken **end, DavQLToken *token) { 514 515 // determine token class (order of if-statements is very important!) 516 char firstchar = token->value.ptr[0]; 517 518 if (isdigit(firstchar)) { 519 token->tokenclass = DAVQL_TOKEN_NUMBER; 520 // check, if all characters are digits 521 for (size_t i = 1 ; i < token->value.length ; i++) { 522 if (!isdigit(token->value.ptr[i])) { 523 token->tokenclass = DAVQL_TOKEN_INVALID; 524 break; 525 } 526 } 527 } else if (firstchar == '%') { 528 token->tokenclass = DAVQL_TOKEN_FMTSPEC; 529 } else if (token->value.length == 1) { 530 switch (firstchar) { 531 case '(': token->tokenclass = DAVQL_TOKEN_OPENP; break; 532 case ')': token->tokenclass = DAVQL_TOKEN_CLOSEP; break; 533 case ',': token->tokenclass = DAVQL_TOKEN_COMMA; break; 534 default: 535 token->tokenclass = strchr(special_token_symbols, firstchar) ? 536 DAVQL_TOKEN_OPERATOR : DAVQL_TOKEN_IDENTIFIER; 537 } 538 } else if (islongoperator(token)) { 539 token->tokenclass = DAVQL_TOKEN_OPERATOR; 540 } else if (firstchar == '\'') { 541 token->tokenclass = DAVQL_TOKEN_STRING; 542 } else if (firstchar == '`') { 543 token->tokenclass = DAVQL_TOKEN_IDENTIFIER; 544 } else if (iskeyword(token)) { 545 token->tokenclass = DAVQL_TOKEN_KEYWORD; 546 } else { 547 token->tokenclass = DAVQL_TOKEN_IDENTIFIER; 548 // TODO: check for illegal characters 549 } 550 551 // remove quotes (extreme cool feature) 552 if (token->tokenclass == DAVQL_TOKEN_STRING || 553 (token->tokenclass == DAVQL_TOKEN_IDENTIFIER && firstchar == '`')) { 554 555 char lastchar = token->value.ptr[token->value.length-1]; 556 if (firstchar == lastchar) { 557 token->value.ptr++; 558 token->value.length -= 2; 559 } else { 560 token->tokenclass = DAVQL_TOKEN_INVALID; 561 } 562 } 563 564 cx_linked_list_add((void**)begin, (void**)end, offsetof(DavQLToken, prev), offsetof(DavQLToken, next), token); 565 return 0; 566 } 567 568 569 570 static DavQLToken* dav_parse_tokenize(cxstring src) { 571 #define alloc_token() do {token = calloc(1, sizeof(DavQLToken));\ 572 if(!token) {tokenlist_free(tokens_begin); return NULL;}} while(0) 573 #define add_token() if(dav_parse_add_token(&tokens_begin, &tokens_end, token)) return NULL; 574 575 DavQLToken *tokens_begin = NULL; 576 DavQLToken *tokens_end = NULL; 577 578 DavQLToken *token = NULL; 579 580 char insequence = '\0'; 581 for (size_t i = 0 ; i < src.length ; i++) { 582 // quoted strings / identifiers are a single token 583 if (src.ptr[i] == '\'' || src.ptr[i] == '`') { 584 if (src.ptr[i] == insequence) { 585 // lookahead for escaped string quotes 586 if (src.ptr[i] == '\'' && i+2 < src.length && 587 src.ptr[i+1] == src.ptr[i] && src.ptr[i+2] == src.ptr[i]) { 588 token->value.length += 3; 589 i += 2; 590 } else { 591 // add quoted token to list 592 token->value.length++; 593 add_token(); 594 token = NULL; 595 insequence = '\0'; 596 } 597 } else if (insequence == '\0') { 598 insequence = src.ptr[i]; 599 // always create new token for quoted strings 600 if (token) { 601 add_token(); 602 } 603 alloc_token(); 604 token->value.ptr = src.ptr + i; 605 token->value.length = 1; 606 } else { 607 // add other kind of quotes to token 608 token->value.length++; 609 } 610 } else if (insequence) { 611 token->value.length++; 612 } else if (isspace(src.ptr[i])) { 613 // add token before spaces to list (if any) 614 if (token) { 615 add_token(); 616 token = NULL; 617 } 618 } else if (strchr(special_token_symbols, src.ptr[i])) { 619 // add token before special symbol to list (if any) 620 if (token) { 621 add_token(); 622 token = NULL; 623 } 624 // add special symbol as single token to list 625 alloc_token(); 626 token->value.ptr = src.ptr + i; 627 token->value.length = 1; 628 add_token(); 629 // set tokenizer ready to read more tokens 630 token = NULL; 631 } else { 632 // if this is a new token, create memory for it 633 if (!token) { 634 alloc_token(); 635 token->value.ptr = src.ptr + i; 636 token->value.length = 0; 637 } 638 // extend token length when reading more bytes 639 token->value.length++; 640 } 641 } 642 643 if (token) { 644 add_token(); 645 } 646 647 alloc_token(); 648 token->tokenclass = DAVQL_TOKEN_END; 649 token->value = CX_STR(""); 650 651 cx_linked_list_add((void**)&tokens_begin, (void**)&tokens_end, offsetof(DavQLToken, prev), offsetof(DavQLToken, next), token); 652 return tokens_begin; 653 #undef alloc_token 654 #undef add_token 655 } 656 657 static void dav_free_expression(DavQLExpression *expr) { 658 if (expr) { 659 if (expr->left) { 660 dav_free_expression(expr->left); 661 } 662 if (expr->right) { 663 dav_free_expression(expr->right); 664 } 665 free(expr); 666 } 667 } 668 669 static void dav_free_field(DavQLField *field) { 670 dav_free_expression(field->expr); 671 free(field); 672 } 673 674 static void dav_free_order_criterion(DavQLOrderCriterion *crit) { 675 if (crit->column) { // do it null-safe though column is expected to be set 676 dav_free_expression(crit->column); 677 } 678 } 679 680 #define token_is(token, expectedclass) (token && \ 681 (token->tokenclass == expectedclass)) 682 683 #define tokenvalue_is(token, expectedvalue) (token && \ 684 !cx_strcasecmp(token->value, cx_str(expectedvalue))) 685 686 typedef int(*exprparser_f)(DavQLStatement*,DavQLToken*,DavQLExpression*); 687 688 static int dav_parse_binary_expr(DavQLStatement* stmt, DavQLToken* token, 689 DavQLExpression* expr, exprparser_f parseL, char* opc, int* opv, 690 exprparser_f parseR) { 691 692 if (!token) { 693 return 0; 694 } 695 696 int total_consumed = 0, consumed; 697 698 // save temporarily on stack (copy to heap later on) 699 DavQLExpression left, right; 700 701 // RULE: LEFT, [Operator, RIGHT] 702 memset(&left, 0, sizeof(DavQLExpression)); 703 consumed = parseL(stmt, token, &left); 704 if (!consumed || stmt->errorcode) { 705 return 0; 706 } 707 total_consumed += consumed; 708 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 709 710 char *op; 711 if (token_is(token, DAVQL_TOKEN_OPERATOR) && 712 (op = strchr(opc, token_sstr(token).ptr[0]))) { 713 expr->op = opv[op-opc]; 714 expr->type = DAVQL_BINARY; 715 total_consumed++; 716 token = token->next; 717 memset(&right, 0, sizeof(DavQLExpression)); 718 consumed = parseR(stmt, token, &right); 719 if (stmt->errorcode) { 720 return 0; 721 } 722 if (!consumed) { 723 dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, 724 _error_missing_expr, stmt, token); 725 return 0; 726 } 727 total_consumed += consumed; 728 } 729 730 if (expr->op == DAVQL_NOOP) { 731 memcpy(expr, &left, sizeof(DavQLExpression)); 732 } else { 733 dqlsec_malloc(stmt, expr->left, DavQLExpression); 734 memcpy(expr->left, &left, sizeof(DavQLExpression)); 735 dqlsec_malloc(stmt, expr->right, DavQLExpression); 736 memcpy(expr->right, &right, sizeof(DavQLExpression)); 737 738 expr->srctext.ptr = expr->left->srctext.ptr; 739 expr->srctext.length = 740 expr->right->srctext.ptr - 741 expr->left->srctext.ptr + expr->right->srctext.length; 742 } 743 744 return total_consumed; 745 } 746 747 static void fmt_args_add(DavQLStatement *stmt, void *data) { 748 if(!stmt->args) { 749 stmt->args = cxLinkedListCreateSimple(CX_STORE_POINTERS); 750 } 751 cxListAdd(stmt->args, data); 752 } 753 754 static void dav_add_fmt_args(DavQLStatement *stmt, cxstring str) { 755 int placeholder = 0; 756 for (size_t i=0;i<str.length;i++) { 757 char c = str.ptr[i]; 758 if (placeholder) { 759 if (c != '%') { 760 fmt_args_add(stmt, (void*)(intptr_t)c); 761 } 762 placeholder = 0; 763 } else if (c == '%') { 764 placeholder = 1; 765 } 766 } 767 } 768 769 static int dav_parse_literal(DavQLStatement* stmt, DavQLToken* token, 770 DavQLExpression* expr) { 771 772 expr->srctext = token_sstr(token); 773 if (token_is(token, DAVQL_TOKEN_NUMBER)) { 774 expr->type = DAVQL_NUMBER; 775 } else if (token_is(token, DAVQL_TOKEN_STRING)) { 776 expr->type = DAVQL_STRING; 777 // check for format specifiers and add args 778 dav_add_fmt_args(stmt, expr->srctext); 779 } else if (token_is(token, DAVQL_TOKEN_TIMESTAMP)) { 780 expr->type = DAVQL_TIMESTAMP; 781 } else if (token_is(token, DAVQL_TOKEN_FMTSPEC) 782 && expr->srctext.length == 2) { 783 switch (expr->srctext.ptr[1]) { 784 case 'd': expr->type = DAVQL_NUMBER; break; 785 case 's': expr->type = DAVQL_STRING; break; 786 case 't': expr->type = DAVQL_TIMESTAMP; break; 787 default: 788 dav_error_in_context(DAVQL_ERROR_INVALID_FMTSPEC, 789 _error_invalid_fmtspec, stmt, token); 790 return 0; 791 } 792 // add fmtspec type to query arg list 793 fmt_args_add(stmt, (void*)(intptr_t)expr->srctext.ptr[1]); 794 } else { 795 return 0; 796 } 797 798 return 1; 799 } 800 801 // forward declaration 802 static int dav_parse_expression(DavQLStatement* stmt, DavQLToken* token, 803 DavQLExpression* expr); 804 805 static int dav_parse_arglist(DavQLStatement* stmt, DavQLToken* token, 806 DavQLExpression* expr) { 807 808 expr->srctext.ptr = token_sstr(token).ptr; 809 expr->srctext.length = 0; 810 expr->left = expr->right = NULL; // in case we fail, we want them to be sane 811 812 int total_consumed = 0; 813 814 // RULE: Expression, {",", Expression}; 815 DavQLExpression *arglist = expr; 816 DavQLExpression arg; 817 const char *lastchar = expr->srctext.ptr; 818 int consumed; 819 do { 820 memset(&arg, 0, sizeof(DavQLExpression)); 821 consumed = dav_parse_expression(stmt, token, &arg); 822 if (consumed) { 823 lastchar = arg.srctext.ptr + arg.srctext.length; 824 total_consumed += consumed; 825 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 826 // look ahead for a comma 827 if (token_is(token, DAVQL_TOKEN_COMMA)) { 828 total_consumed++; 829 token = token->next; 830 /* we have more arguments, so put the current argument to the 831 * left subtree and create a new node to the right 832 */ 833 dqlsec_malloc(stmt, arglist->left, DavQLExpression); 834 memcpy(arglist->left, &arg, sizeof(DavQLExpression)); 835 arglist->srctext.ptr = arg.srctext.ptr; 836 arglist->op = DAVQL_ARGLIST; 837 arglist->type = DAVQL_FUNCCALL; 838 dqlsec_mallocz(stmt, arglist->right, DavQLExpression); 839 arglist = arglist->right; 840 } else { 841 // this was the last argument, so write it to the current node 842 memcpy(arglist, &arg, sizeof(DavQLExpression)); 843 consumed = 0; 844 } 845 } 846 } while (consumed && !stmt->errorcode); 847 848 // recover source text 849 arglist = expr; 850 while (arglist && arglist->type == DAVQL_FUNCCALL) { 851 arglist->srctext.length = lastchar - arglist->srctext.ptr; 852 arglist = arglist->right; 853 } 854 855 return total_consumed; 856 } 857 858 static int dav_parse_funccall(DavQLStatement* stmt, DavQLToken* token, 859 DavQLExpression* expr) { 860 861 // RULE: Identifier, "(", ArgumentList, ")"; 862 if (token_is(token, DAVQL_TOKEN_IDENTIFIER) && 863 token_is(token->next, DAVQL_TOKEN_OPENP)) { 864 865 expr->type = DAVQL_FUNCCALL; 866 expr->op = DAVQL_CALL; 867 868 dqlsec_mallocz(stmt, expr->left, DavQLExpression); 869 expr->left->type = DAVQL_IDENTIFIER; 870 expr->left->srctext = token_sstr(token); 871 expr->right = NULL; 872 873 token = token->next->next; 874 875 DavQLExpression arg; 876 int argtokens = dav_parse_arglist(stmt, token, &arg); 877 if (stmt->errorcode) { 878 // if an error occurred while parsing the arglist, return now 879 return 2; 880 } 881 if (argtokens) { 882 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), argtokens); 883 dqlsec_malloc(stmt, expr->right, DavQLExpression); 884 memcpy(expr->right, &arg, sizeof(DavQLExpression)); 885 } else { 886 // arg list may be empty 887 expr->right = NULL; 888 } 889 890 if (token_is(token, DAVQL_TOKEN_CLOSEP)) { 891 return 3 + argtokens; 892 } else { 893 dav_error_in_context(DAVQL_ERROR_MISSING_PAR, _error_missing_par, 894 stmt, token); 895 return 2; // it MUST be a function call, but it is invalid 896 } 897 } else { 898 return 0; 899 } 900 } 901 902 static int dav_parse_unary_expr(DavQLStatement* stmt, DavQLToken* token, 903 DavQLExpression* expr) { 904 905 DavQLToken *firsttoken = token; // save for srctext recovery 906 907 DavQLExpression* atom = expr; 908 int total_consumed = 0; 909 910 // optional unary operator 911 if (token_is(token, DAVQL_TOKEN_OPERATOR)) { 912 char *op = strchr("+-~", token_sstr(token).ptr[0]); 913 if (op) { 914 expr->type = DAVQL_UNARY; 915 switch (*op) { 916 case '+': expr->op = DAVQL_ADD; break; 917 case '-': expr->op = DAVQL_SUB; break; 918 case '~': expr->op = DAVQL_NEG; break; 919 } 920 dqlsec_mallocz(stmt, expr->left, DavQLExpression); 921 atom = expr->left; 922 total_consumed++; 923 token = token->next; 924 } else { 925 dav_error_in_context(DAVQL_ERROR_INVALID_UNARY_OP, 926 _error_invalid_unary_op, stmt, token); 927 return 0; 928 } 929 } 930 931 // RULE: (ParExpression | AtomicExpression) 932 if (token_is(token, DAVQL_TOKEN_OPENP)) { 933 token = token->next; total_consumed++; 934 // RULE: "(", Expression, ")" 935 int consumed = dav_parse_expression(stmt, token, atom); 936 if (stmt->errorcode) { 937 return 0; 938 } 939 if (!consumed) { 940 dav_error_in_context(DAVQL_ERROR_INVALID_EXPR, 941 _error_invalid_expr, stmt, token); 942 return 0; 943 } 944 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 945 total_consumed += consumed; 946 if (token_is(token, DAVQL_TOKEN_CLOSEP)) { 947 token = token->next; total_consumed++; 948 } else { 949 dav_error_in_context(DAVQL_ERROR_MISSING_PAR, 950 _error_missing_par, stmt, token); 951 return 0; 952 } 953 } else { 954 // RULE: FunctionCall 955 int consumed = dav_parse_funccall(stmt, token, atom); 956 if (consumed) { 957 total_consumed += consumed; 958 } else if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { 959 // RULE: Identifier 960 total_consumed++; 961 atom->type = DAVQL_IDENTIFIER; 962 atom->srctext = token_sstr(token); 963 } else { 964 // RULE: Literal 965 total_consumed += dav_parse_literal(stmt, token, atom); 966 } 967 } 968 969 // recover source text 970 expr->srctext.ptr = token_sstr(firsttoken).ptr; 971 if (total_consumed > 0) { 972 cxstring lasttoken = 973 token_sstr((DavQLToken*)cx_linked_list_at(token, 0, offsetof(DavQLToken, next), total_consumed-1)); 974 expr->srctext.length = 975 lasttoken.ptr - expr->srctext.ptr + lasttoken.length; 976 } else { 977 // the expression should not be used anyway, but we want to be safe 978 expr->srctext.length = 0; 979 } 980 981 982 return total_consumed; 983 } 984 985 static int dav_parse_bitexpr(DavQLStatement* stmt, DavQLToken* token, 986 DavQLExpression* expr) { 987 988 return dav_parse_binary_expr(stmt, token, expr, 989 dav_parse_unary_expr, 990 "&|^", (int[]){DAVQL_AND, DAVQL_OR, DAVQL_XOR}, 991 dav_parse_bitexpr); 992 } 993 994 static int dav_parse_multexpr(DavQLStatement* stmt, DavQLToken* token, 995 DavQLExpression* expr) { 996 997 return dav_parse_binary_expr(stmt, token, expr, 998 dav_parse_bitexpr, 999 "*/", (int[]){DAVQL_MUL, DAVQL_DIV}, 1000 dav_parse_multexpr); 1001 } 1002 1003 static int dav_parse_expression(DavQLStatement* stmt, DavQLToken* token, 1004 DavQLExpression* expr) { 1005 1006 return dav_parse_binary_expr(stmt, token, expr, 1007 dav_parse_multexpr, 1008 "+-", (int[]){DAVQL_ADD, DAVQL_SUB}, 1009 dav_parse_expression); 1010 } 1011 1012 static int dav_parse_named_field(DavQLStatement *stmt, DavQLToken *token, 1013 DavQLField *field) { 1014 int total_consumed = 0, consumed; 1015 1016 // RULE: Expression, " as ", Identifier; 1017 DavQLExpression *expr; 1018 dqlsec_mallocz(stmt, expr, DavQLExpression); 1019 consumed = dav_parse_expression(stmt, token, expr); 1020 if (stmt->errorcode) { 1021 dav_free_expression(expr); 1022 return 0; 1023 } 1024 if (expr->type == DAVQL_UNDEFINED_TYPE) { 1025 dav_free_expression(expr); 1026 dav_error_in_context(DAVQL_ERROR_INVALID_EXPR, 1027 _error_invalid_expr, stmt, token); 1028 return 0; 1029 } 1030 1031 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1032 total_consumed += consumed; 1033 1034 if (token_is(token, DAVQL_TOKEN_KEYWORD) && tokenvalue_is(token, "as")) { 1035 token = token->next; total_consumed++; 1036 } else { 1037 dav_free_expression(expr); 1038 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1039 _error_missing_as, stmt, token); 1040 return 0; 1041 } 1042 1043 if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { 1044 field->name = token_sstr(token); 1045 field->expr = expr; 1046 return total_consumed + 1; 1047 } else { 1048 dav_free_expression(expr); 1049 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1050 _error_missing_identifier, stmt, token); 1051 return 0; 1052 } 1053 } 1054 1055 static int dav_parse_fieldlist(DavQLStatement *stmt, DavQLToken *token) { 1056 1057 // RULE: "-" 1058 if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "-")) { 1059 DavQLField *field; 1060 dqlsec_malloc(stmt, field, DavQLField); 1061 if(dav_stmt_add_field(stmt, field)) { 1062 free(field); 1063 return 0; 1064 } 1065 dqlsec_mallocz(stmt, field->expr, DavQLExpression); 1066 field->expr->type = DAVQL_IDENTIFIER; 1067 field->expr->srctext = field->name = token_sstr(token); 1068 return 1; 1069 } 1070 1071 // RULE: "*", {",", NamedExpression} 1072 if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "*")) { 1073 DavQLField *field; 1074 dqlsec_malloc(stmt, field, DavQLField); 1075 if(dav_stmt_add_field(stmt, field)) { 1076 free(field); 1077 return 0; 1078 } 1079 dqlsec_mallocz(stmt, field->expr, DavQLExpression); 1080 field->expr->type = DAVQL_IDENTIFIER; 1081 field->expr->srctext = field->name = token_sstr(token); 1082 1083 int total_consumed = 0; 1084 int consumed = 1; 1085 1086 do { 1087 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1088 total_consumed += consumed; 1089 1090 if (token_is(token, DAVQL_TOKEN_COMMA)) { 1091 total_consumed++; token = token->next; 1092 DavQLField localfield; 1093 consumed = dav_parse_named_field(stmt, token, &localfield); 1094 if (!stmt->errorcode && consumed) { 1095 DavQLField *add_field; 1096 dqlsec_malloc(stmt, add_field, DavQLField); 1097 memcpy(add_field, &localfield, sizeof(DavQLField)); 1098 if(dav_stmt_add_field(stmt, add_field)) { 1099 free(add_field); 1100 return 0; 1101 } 1102 } 1103 } else { 1104 consumed = 0; 1105 } 1106 } while (consumed > 0); 1107 1108 return total_consumed; 1109 } 1110 1111 // RULE: FieldExpression, {",", FieldExpression} 1112 { 1113 int total_consumed = 0, consumed; 1114 do { 1115 // RULE: NamedField | Identifier 1116 DavQLField localfield; 1117 consumed = dav_parse_named_field(stmt, token, &localfield); 1118 if (consumed) { 1119 DavQLField *field; 1120 dqlsec_malloc(stmt, field, DavQLField); 1121 memcpy(field, &localfield, sizeof(DavQLField)); 1122 if(dav_stmt_add_field(stmt, field)) { 1123 free(field); 1124 return 0; 1125 } 1126 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1127 total_consumed += consumed; 1128 } else if (token_is(token, DAVQL_TOKEN_IDENTIFIER) 1129 // look ahead, if the field is JUST the identifier 1130 && (token_is(token->next, DAVQL_TOKEN_COMMA) || 1131 tokenvalue_is(token->next, "from"))) { 1132 1133 DavQLField *field; 1134 dqlsec_malloc(stmt, field, DavQLField); 1135 dqlsec_mallocz(stmt, field->expr, DavQLExpression); 1136 field->expr->type = DAVQL_IDENTIFIER; 1137 field->expr->srctext = field->name = token_sstr(token); 1138 if(dav_stmt_add_field(stmt, field)) { 1139 free(field); 1140 return 0; 1141 } 1142 1143 consumed = 1; 1144 total_consumed++; 1145 token = token->next; 1146 1147 // we found a valid solution, so erase any errors 1148 stmt->errorcode = 0; 1149 if (stmt->errormessage) { 1150 free(stmt->errormessage); 1151 stmt->errormessage = NULL; 1152 } 1153 } else { 1154 // dav_parse_named_field has already thrown a good error 1155 consumed = 0; 1156 } 1157 1158 // field has been parsed, now try to get a comma 1159 if (consumed) { 1160 consumed = token_is(token, DAVQL_TOKEN_COMMA) ? 1 : 0; 1161 if (consumed) { 1162 token = token->next; 1163 total_consumed++; 1164 } 1165 } 1166 } while (consumed); 1167 1168 return total_consumed; 1169 } 1170 } 1171 1172 // forward declaration 1173 static int dav_parse_logical_expr(DavQLStatement *stmt, DavQLToken *token, 1174 DavQLExpression *expr); 1175 1176 static int dav_parse_bool_prim(DavQLStatement *stmt, DavQLToken *token, 1177 DavQLExpression *expr) { 1178 1179 expr->type = DAVQL_LOGICAL; 1180 expr->srctext = token_sstr(token); 1181 1182 int total_consumed = 0; 1183 1184 DavQLExpression bexpr; 1185 memset(&bexpr, 0, sizeof(DavQLExpression)); 1186 total_consumed = dav_parse_expression(stmt, token, &bexpr); 1187 if (!total_consumed || stmt->errorcode) { 1188 return 0; 1189 } 1190 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), total_consumed); 1191 1192 DavQLToken* optok = token; 1193 // RULE: Expression, (" like " | " unlike "), String 1194 if (token_is(optok, DAVQL_TOKEN_OPERATOR) && (tokenvalue_is(optok, 1195 "like") || tokenvalue_is(optok, "unlike"))) { 1196 1197 total_consumed++; 1198 token = token->next; 1199 if (token_is(token, DAVQL_TOKEN_STRING)) { 1200 expr->op = tokenvalue_is(optok, "like") ? 1201 DAVQL_LIKE : DAVQL_UNLIKE; 1202 dqlsec_malloc(stmt, expr->left, DavQLExpression); 1203 memcpy(expr->left, &bexpr, sizeof(DavQLExpression)); 1204 dqlsec_mallocz(stmt, expr->right, DavQLExpression); 1205 expr->right->type = DAVQL_STRING; 1206 expr->right->srctext = token_sstr(token); 1207 expr->srctext.length = expr->right->srctext.ptr - 1208 expr->srctext.ptr + expr->right->srctext.length; 1209 1210 // fmt args 1211 dav_add_fmt_args(stmt, expr->right->srctext); 1212 1213 return total_consumed + 1; 1214 } else { 1215 dav_error_in_context(DAVQL_ERROR_INVALID_STRING, 1216 _error_invalid_string, stmt, token); 1217 return 0; 1218 } 1219 } 1220 // RULE: Expression, Comparison, Expression 1221 else if (token_is(optok, DAVQL_TOKEN_OPERATOR) && ( 1222 tokenvalue_is(optok, "=") || tokenvalue_is(optok, "!") || 1223 tokenvalue_is(optok, "<") || tokenvalue_is(optok, ">"))) { 1224 1225 total_consumed++; 1226 token = token->next; 1227 1228 if (tokenvalue_is(optok, "=")) { 1229 expr->op = DAVQL_EQ; 1230 } else { 1231 if (tokenvalue_is(token, "=")) { 1232 if (tokenvalue_is(optok, "!")) { 1233 expr->op = DAVQL_NEQ; 1234 } else if (tokenvalue_is(optok, "<")) { 1235 expr->op = DAVQL_LE; 1236 } else if (tokenvalue_is(optok, ">")) { 1237 expr->op = DAVQL_GE; 1238 } 1239 total_consumed++; 1240 token = token->next; 1241 } else { 1242 if (tokenvalue_is(optok, "<")) { 1243 expr->op = DAVQL_LT; 1244 } else if (tokenvalue_is(optok, ">")) { 1245 expr->op = DAVQL_GT; 1246 } 1247 } 1248 } 1249 1250 DavQLExpression rexpr; 1251 memset(&rexpr, 0, sizeof(DavQLExpression)); 1252 int consumed = dav_parse_expression(stmt, token, &rexpr); 1253 if (stmt->errorcode) { 1254 return 0; 1255 } 1256 if (!consumed) { 1257 dav_error_in_context( 1258 DAVQL_ERROR_MISSING_EXPR, _error_missing_expr, 1259 stmt, token); 1260 return 0; 1261 } 1262 1263 total_consumed += consumed; 1264 dqlsec_malloc(stmt, expr->left, DavQLExpression); 1265 memcpy(expr->left, &bexpr, sizeof(DavQLExpression)); 1266 dqlsec_malloc(stmt, expr->right, DavQLExpression); 1267 memcpy(expr->right, &rexpr, sizeof(DavQLExpression)); 1268 1269 expr->srctext.length = expr->right->srctext.ptr - 1270 expr->srctext.ptr + expr->right->srctext.length; 1271 1272 return total_consumed; 1273 } 1274 // RULE: FunctionCall | Identifier; 1275 else if (bexpr.type == DAVQL_FUNCCALL || bexpr.type == DAVQL_IDENTIFIER) { 1276 memcpy(expr, &bexpr, sizeof(DavQLExpression)); 1277 1278 return total_consumed; 1279 } else { 1280 return 0; 1281 } 1282 } 1283 1284 static int dav_parse_bool_expr(DavQLStatement *stmt, DavQLToken *token, 1285 DavQLExpression *expr) { 1286 1287 // RULE: "not ", LogicalExpression 1288 if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "not")) { 1289 expr->type = DAVQL_LOGICAL; 1290 expr->op = DAVQL_NOT; 1291 dqlsec_mallocz(stmt, expr->left, DavQLExpression); 1292 expr->srctext = token_sstr(token); 1293 1294 token = token->next; 1295 int consumed = dav_parse_bool_expr(stmt, token, expr->left); 1296 if (stmt->errorcode) { 1297 return 0; 1298 } 1299 if (consumed) { 1300 cxstring lasttok = token_sstr((DavQLToken*)cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed-1)); 1301 expr->srctext.length = 1302 lasttok.ptr - expr->srctext.ptr + lasttok.length; 1303 return consumed + 1; 1304 } else { 1305 dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, 1306 _error_missing_expr, stmt, token); 1307 return 0; 1308 } 1309 } 1310 // RULE: "(", LogicalExpression, ")" 1311 else if (token_is(token, DAVQL_TOKEN_OPENP)) { 1312 int consumed = dav_parse_logical_expr(stmt, token->next, expr); 1313 if (consumed) { 1314 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1315 1316 if (token_is(token, DAVQL_TOKEN_CLOSEP)) { 1317 token = token->next; 1318 return consumed + 2; 1319 } else { 1320 dav_error_in_context(DAVQL_ERROR_MISSING_PAR, _error_missing_par, 1321 stmt, token); 1322 return 0; 1323 } 1324 } else { 1325 // don't handle errors here, we can also try a boolean primary 1326 stmt->errorcode = 0; 1327 if (stmt->errormessage) { 1328 free(stmt->errormessage); 1329 } 1330 } 1331 } 1332 1333 // RULE: BooleanPrimary 1334 return dav_parse_bool_prim(stmt, token, expr); 1335 } 1336 1337 static int dav_parse_logical_expr(DavQLStatement *stmt, DavQLToken *token, 1338 DavQLExpression *expr) { 1339 1340 DavQLToken *firsttoken = token; 1341 int total_consumed = 0; 1342 1343 // RULE: BooleanLiteral, [LogicalOperator, LogicalExpression]; 1344 DavQLExpression left, right; 1345 memset(&left, 0, sizeof(DavQLExpression)); 1346 int consumed = dav_parse_bool_expr(stmt, token, &left); 1347 if (stmt->errorcode) { 1348 return 0; 1349 } 1350 if (!consumed) { 1351 dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, 1352 _error_missing_expr, stmt, token); 1353 return 0; 1354 } 1355 total_consumed += consumed; 1356 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1357 1358 if (token_is(token, DAVQL_TOKEN_OPERATOR)) { 1359 expr->type = DAVQL_LOGICAL; 1360 1361 davqloperator_t op = DAVQL_NOOP; 1362 if (tokenvalue_is(token, "and")) { 1363 op = DAVQL_LAND; 1364 } else if (tokenvalue_is(token, "or")) { 1365 op = DAVQL_LOR; 1366 } else if (tokenvalue_is(token, "xor")) { 1367 op = DAVQL_LXOR; 1368 } 1369 1370 if (op == DAVQL_NOOP) { 1371 dav_error_in_context(DAVQL_ERROR_INVALID_LOGICAL_OP, 1372 _error_invalid_logical_op, stmt, token); 1373 return 0; 1374 } else { 1375 expr->op = op; 1376 total_consumed++; 1377 token = token->next; 1378 1379 memset(&right, 0, sizeof(DavQLExpression)); 1380 consumed = dav_parse_logical_expr(stmt, token, &right); 1381 if (stmt->errorcode) { 1382 return 0; 1383 } 1384 if (!consumed) { 1385 dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, 1386 _error_missing_expr, stmt, token); 1387 return 0; 1388 } 1389 total_consumed += consumed; 1390 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1391 1392 dqlsec_malloc(stmt, expr->left, DavQLExpression); 1393 memcpy(expr->left, &left, sizeof(DavQLExpression)); 1394 dqlsec_malloc(stmt, expr->right, DavQLExpression); 1395 memcpy(expr->right, &right, sizeof(DavQLExpression)); 1396 } 1397 } else { 1398 memcpy(expr, &left, sizeof(DavQLExpression)); 1399 } 1400 1401 // set type and recover source text 1402 if (total_consumed > 0) { 1403 expr->srctext.ptr = token_sstr(firsttoken).ptr; 1404 cxstring lasttok = token_sstr((DavQLToken*)cx_linked_list_at(firsttoken, 0, offsetof(DavQLToken, next), total_consumed-1)); 1405 expr->srctext.length = lasttok.ptr-expr->srctext.ptr+lasttok.length; 1406 } 1407 1408 return total_consumed; 1409 } 1410 1411 static int dav_parse_where_clause(DavQLStatement *stmt, DavQLToken *token) { 1412 dqlsec_mallocz(stmt, stmt->where, DavQLExpression); 1413 1414 return dav_parse_logical_expr(stmt, token, stmt->where); 1415 } 1416 1417 static int dav_parse_with_clause(DavQLStatement *stmt, DavQLToken *token) { 1418 1419 int total_consumed = 0; 1420 1421 // RULE: "depth", "=", (Number | "infinity") 1422 if (tokenvalue_is(token, "depth")) { 1423 token = token->next; total_consumed++; 1424 if (tokenvalue_is(token, "=")) { 1425 token = token->next; total_consumed++; 1426 if (tokenvalue_is(token, "infinity")) { 1427 stmt->depth = DAV_DEPTH_INFINITY; 1428 token = token->next; total_consumed++; 1429 } else { 1430 DavQLExpression *depthexpr; 1431 dqlsec_mallocz(stmt, depthexpr, DavQLExpression); 1432 1433 int consumed = dav_parse_expression(stmt, token, depthexpr); 1434 1435 if (consumed) { 1436 if (depthexpr->type == DAVQL_NUMBER) { 1437 if (depthexpr->srctext.ptr[0] == '%') { 1438 stmt->depth = DAV_DEPTH_PLACEHOLDER; 1439 } else { 1440 cxstring depthstr = depthexpr->srctext; 1441 char *conv = malloc(depthstr.length+1); 1442 if (!conv) { 1443 dav_free_expression(depthexpr); 1444 stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; 1445 return 0; 1446 } 1447 char *chk; 1448 memcpy(conv, depthstr.ptr, depthstr.length); 1449 conv[depthstr.length] = '\0'; 1450 stmt->depth = strtol(conv, &chk, 10); 1451 if (*chk || stmt->depth < -1) { 1452 dav_error_in_context(DAVQL_ERROR_INVALID_DEPTH, 1453 _error_invalid_depth, stmt, token); 1454 } 1455 free(conv); 1456 } 1457 total_consumed += consumed; 1458 } else { 1459 dav_error_in_context(DAVQL_ERROR_INVALID_DEPTH, 1460 _error_invalid_depth, stmt, token); 1461 } 1462 } 1463 1464 dav_free_expression(depthexpr); 1465 } 1466 } 1467 } 1468 1469 return total_consumed; 1470 } 1471 1472 static int dav_parse_order_crit(DavQLStatement *stmt, DavQLToken *token, 1473 DavQLOrderCriterion *crit) { 1474 1475 // RULE: (Identifier | Number), [" asc"|" desc"]; 1476 DavQLExpression expr; 1477 memset(&expr, 0, sizeof(DavQLExpression)); 1478 int consumed = dav_parse_expression(stmt, token, &expr); 1479 if (stmt->errorcode || !consumed) { 1480 return 0; 1481 } 1482 1483 if (expr.type != DAVQL_IDENTIFIER && expr.type != DAVQL_NUMBER) { 1484 dav_error_in_context(DAVQL_ERROR_INVALID_ORDER_CRITERION, 1485 _error_invalid_order_criterion, stmt, token); 1486 return 0; 1487 } 1488 1489 dqlsec_malloc(stmt, crit->column, DavQLExpression); 1490 memcpy(crit->column, &expr, sizeof(DavQLExpression)); 1491 1492 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1493 if (token_is(token, DAVQL_TOKEN_KEYWORD) && ( 1494 tokenvalue_is(token, "asc") || tokenvalue_is(token, "desc"))) { 1495 1496 crit->descending = tokenvalue_is(token, "desc"); 1497 1498 return consumed+1; 1499 } else { 1500 crit->descending = 0; 1501 return consumed; 1502 } 1503 } 1504 1505 static int dav_parse_orderby_clause(DavQLStatement *stmt, DavQLToken *token) { 1506 1507 int total_consumed = 0, consumed; 1508 1509 DavQLOrderCriterion crit; 1510 1511 if(!stmt->orderby) { 1512 stmt->orderby = cxLinkedListCreateSimple(sizeof(DavQLOrderCriterion)); 1513 if(!stmt->orderby) { 1514 return 0; 1515 } 1516 } 1517 1518 // RULE: OrderByCriterion, {",", OrderByCriterion}; 1519 do { 1520 consumed = dav_parse_order_crit(stmt, token, &crit); 1521 if (stmt->errorcode) { 1522 return 0; 1523 } 1524 if (!consumed) { 1525 dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, _error_missing_expr, 1526 stmt, token); 1527 return 0; 1528 } 1529 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1530 total_consumed += consumed; 1531 1532 if(cxListAdd(stmt->orderby, &crit)) { 1533 stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; 1534 return 0; 1535 } 1536 1537 if (token_is(token, DAVQL_TOKEN_COMMA)) { 1538 total_consumed++; 1539 token = token->next; 1540 } else { 1541 consumed = 0; 1542 } 1543 } while (consumed); 1544 1545 return total_consumed; 1546 } 1547 1548 1549 static int dav_parse_assignments(DavQLStatement *stmt, DavQLToken *token) { 1550 1551 // RULE: Assignment, {",", Assignment} 1552 int total_consumed = 0, consumed; 1553 do { 1554 // RULE: Identifier, "=", Expression 1555 if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { 1556 1557 // Identifier 1558 DavQLField *field; 1559 dqlsec_malloc(stmt, field, DavQLField); 1560 field->name = token_sstr(token); 1561 total_consumed++; 1562 token = token->next; 1563 1564 // "=" 1565 if (!token_is(token, DAVQL_TOKEN_OPERATOR) 1566 || !tokenvalue_is(token, "=")) { 1567 dav_free_field(field); 1568 1569 dav_error_in_context(DAVQL_ERROR_MISSING_ASSIGN, 1570 _error_missing_assign, stmt, token); 1571 return total_consumed; 1572 } 1573 total_consumed++; 1574 token = token->next; 1575 1576 // Expression 1577 dqlsec_mallocz(stmt, field->expr, DavQLExpression); 1578 consumed = dav_parse_expression(stmt, token, field->expr); 1579 if (stmt->errorcode) { 1580 dav_free_field(field); 1581 return total_consumed; 1582 } 1583 token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); 1584 total_consumed += consumed; 1585 1586 // Add assignment to list and check if there's another one 1587 if(dav_stmt_add_field(stmt, field)) { 1588 free(field); 1589 return 0; 1590 } 1591 consumed = token_is(token, DAVQL_TOKEN_COMMA) ? 1 : 0; 1592 if (consumed) { 1593 token = token->next; 1594 total_consumed++; 1595 } 1596 } else { 1597 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1598 _error_missing_identifier, stmt, token); 1599 return total_consumed; 1600 } 1601 } while (consumed); 1602 1603 return total_consumed; 1604 } 1605 1606 static int dav_parse_path(DavQLStatement *stmt, DavQLToken *tokens) { 1607 if (token_is(tokens, DAVQL_TOKEN_STRING)) { 1608 stmt->path = token_sstr(tokens); 1609 tokens = tokens->next; 1610 return 1; 1611 } else if (token_is(tokens, DAVQL_TOKEN_OPERATOR) 1612 && tokenvalue_is(tokens, "/")) { 1613 stmt->path = token_sstr(tokens); 1614 tokens = tokens->next; 1615 int consumed = 1; 1616 while (!token_is(tokens, DAVQL_TOKEN_KEYWORD) && 1617 !token_is(tokens, DAVQL_TOKEN_END)) { 1618 cxstring toksstr = token_sstr(tokens); 1619 stmt->path.length = toksstr.ptr-stmt->path.ptr+toksstr.length; 1620 tokens = tokens->next; 1621 consumed++; 1622 } 1623 return consumed; 1624 } else if (token_is(tokens, DAVQL_TOKEN_FMTSPEC) && 1625 tokenvalue_is(tokens, "%s")) { 1626 stmt->path = token_sstr(tokens); 1627 tokens = tokens->next; 1628 fmt_args_add(stmt, (void*)(intptr_t)'s'); 1629 return 1; 1630 } else { 1631 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1632 _error_missing_path, stmt, tokens); 1633 return 0; 1634 } 1635 } 1636 1637 /** 1638 * Parser of a select statement. 1639 * @param stmt the statement object that shall contain the syntax tree 1640 * @param tokens the token list 1641 */ 1642 static void dav_parse_select_statement(DavQLStatement *stmt, DavQLToken *tokens) { 1643 stmt->type = DAVQL_SELECT; 1644 1645 // Consume field list 1646 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_fieldlist(stmt, tokens)); 1647 if (stmt->errorcode) { 1648 return; 1649 } 1650 1651 // Consume FROM keyword 1652 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1653 && tokenvalue_is(tokens, "from")) { 1654 tokens = tokens->next; 1655 } else { 1656 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1657 _error_missing_from, stmt, tokens); 1658 return; 1659 } 1660 1661 // Consume path 1662 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_path(stmt, tokens)); 1663 if (stmt->errorcode) { 1664 return; 1665 } 1666 //dav_add_fmt_args(stmt, stmt->path); // add possible path args 1667 1668 // Consume with clause (if any) 1669 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1670 && tokenvalue_is(tokens, "with")) { 1671 tokens = tokens->next; 1672 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), 1673 dav_parse_with_clause(stmt, tokens)); 1674 } 1675 if (stmt->errorcode) { 1676 return; 1677 } 1678 1679 // Consume where clause (if any) 1680 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1681 && tokenvalue_is(tokens, "where")) { 1682 tokens = tokens->next; 1683 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), 1684 dav_parse_where_clause(stmt, tokens)); 1685 } else if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1686 && tokenvalue_is(tokens, "anywhere")) { 1687 // useless, but the user may want to explicitly express his intent 1688 tokens = tokens->next; 1689 stmt->where = NULL; 1690 } 1691 if (stmt->errorcode) { 1692 return; 1693 } 1694 1695 // Consume order by clause (if any) 1696 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1697 && tokenvalue_is(tokens, "order")) { 1698 tokens = tokens->next; 1699 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1700 && tokenvalue_is(tokens, "by")) { 1701 tokens = tokens->next; 1702 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), 1703 dav_parse_orderby_clause(stmt, tokens)); 1704 } else { 1705 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1706 _error_missing_by, stmt, tokens); 1707 return; 1708 } 1709 } 1710 if (stmt->errorcode) { 1711 return; 1712 } 1713 1714 1715 if (tokens) { 1716 if (token_is(tokens, DAVQL_TOKEN_INVALID)) { 1717 dav_error_in_context(DAVQL_ERROR_INVALID_TOKEN, 1718 _error_invalid_token, stmt, tokens); 1719 } else if (!token_is(tokens, DAVQL_TOKEN_END)) { 1720 dav_error_in_context(DAVQL_ERROR_UNEXPECTED_TOKEN, 1721 _error_unexpected_token, stmt, tokens); 1722 } 1723 } 1724 } 1725 1726 static void dav_parse_set_statement(DavQLStatement *stmt, DavQLToken *tokens) { 1727 stmt->type = DAVQL_SET; 1728 1729 // Consume assignments 1730 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_assignments(stmt, tokens)); 1731 if (stmt->errorcode) { 1732 return; 1733 } 1734 1735 // Consume AT keyword 1736 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1737 && tokenvalue_is(tokens, "at")) { 1738 tokens = tokens->next; 1739 } else { 1740 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1741 _error_missing_at, stmt, tokens); 1742 return; 1743 } 1744 1745 // Consume path 1746 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_path(stmt, tokens)); 1747 if (stmt->errorcode) { 1748 return; 1749 } 1750 1751 // Consume with clause (if any) 1752 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1753 && tokenvalue_is(tokens, "with")) { 1754 tokens = tokens->next; 1755 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), 1756 dav_parse_with_clause(stmt, tokens)); 1757 } 1758 if (stmt->errorcode) { 1759 return; 1760 } 1761 1762 // Consume mandatory where clause (or anywhere keyword) 1763 if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1764 && tokenvalue_is(tokens, "where")) { 1765 tokens = tokens->next; 1766 tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), 1767 dav_parse_where_clause(stmt, tokens)); 1768 } else if (token_is(tokens, DAVQL_TOKEN_KEYWORD) 1769 && tokenvalue_is(tokens, "anywhere")) { 1770 // no-op, but we want the user to be explicit about this 1771 tokens = tokens->next; 1772 stmt->where = NULL; 1773 } else { 1774 dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, 1775 _error_missing_where, stmt, tokens); 1776 return; 1777 } 1778 } 1779 1780 DavQLStatement* dav_parse_statement(cxstring srctext) { 1781 DavQLStatement *stmt = calloc(1, sizeof(DavQLStatement)); 1782 1783 // if we can't even get enough memory for the statement object or an error 1784 // message, we can simply die without returning anything 1785 if (!stmt) { 1786 return NULL; 1787 } 1788 char *oommsg = strdup(_error_out_of_memory); 1789 if (!oommsg) { 1790 free(stmt); 1791 return NULL; 1792 } 1793 1794 // default values 1795 stmt->type = -1; 1796 stmt->depth = 1; 1797 1798 // save trimmed source text 1799 stmt->srctext = cx_strtrim(srctext); 1800 1801 if (stmt->srctext.length) { 1802 // tokenization 1803 DavQLToken* tokens = dav_parse_tokenize(stmt->srctext); 1804 1805 if (tokens) { 1806 // use first token to determine query type 1807 1808 if (tokenvalue_is(tokens, "select")) { 1809 dav_parse_select_statement(stmt, tokens->next); 1810 } else if (tokenvalue_is(tokens, "set")) { 1811 dav_parse_set_statement(stmt, tokens->next); 1812 } else { 1813 stmt->type = DAVQL_ERROR; 1814 stmt->errorcode = DAVQL_ERROR_INVALID; 1815 stmt->errormessage = strdup(_error_invalid); 1816 } 1817 1818 // free token data 1819 tokenlist_free(tokens); 1820 } else { 1821 stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; 1822 } 1823 } else { 1824 stmt->type = DAVQL_ERROR; 1825 stmt->errorcode = DAVQL_ERROR_INVALID; 1826 stmt->errormessage = strdup(_error_invalid); 1827 } 1828 1829 if (stmt->errorcode == DAVQL_ERROR_OUT_OF_MEMORY) { 1830 stmt->type = DAVQL_ERROR; 1831 stmt->errormessage = oommsg; 1832 } else { 1833 free(oommsg); 1834 } 1835 1836 return stmt; 1837 } 1838 1839 void dav_free_statement(DavQLStatement *stmt) { 1840 if(stmt->fields) { 1841 cxDefineDestructor(stmt->fields, dav_free_field); 1842 cxListDestroy(stmt->fields); 1843 } 1844 1845 if (stmt->where) { 1846 dav_free_expression(stmt->where); 1847 } 1848 if (stmt->errormessage) { 1849 free(stmt->errormessage); 1850 } 1851 1852 if(stmt->orderby) { 1853 cxDefineDestructor(stmt->orderby, dav_free_order_criterion); 1854 cxListDestroy(stmt->orderby); 1855 } 1856 if(stmt->args) { 1857 cxListDestroy(stmt->args); 1858 } 1859 free(stmt); 1860 } 1861