libidav/davqlparser.c

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