diff -r 2483f517c562 -r b5bb7b3cd597 libidav/davqlparser.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/libidav/davqlparser.c Mon Jan 22 17:27:47 2024 +0100 @@ -0,0 +1,1860 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2018 Olaf Wintermann. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "davqlparser.h" +#include +#include +#include +#include +#include +#include + +#define sfmtarg(s) ((int)(s).length), (s).ptr + +// ------------------------------------------------------------------------ +// D E B U G E R +// ------------------------------------------------------------------------ + +static const char* _map_querytype(davqltype_t type) { + switch(type) { + case DAVQL_ERROR: return "ERROR"; + case DAVQL_SELECT: return "SELECT"; + case DAVQL_SET: return "SET"; + default: return "unknown"; + } +} + +static const char* _map_exprtype(davqlexprtype_t type) { + switch(type) { + case DAVQL_UNDEFINED_TYPE: return "undefined"; + case DAVQL_NUMBER: return "NUMBER"; + case DAVQL_STRING: return "STRING"; + case DAVQL_TIMESTAMP: return "TIMESTAMP"; + case DAVQL_IDENTIFIER: return "IDENTIFIER"; + case DAVQL_UNARY: return "UNARY"; + case DAVQL_BINARY: return "BINARY"; + case DAVQL_LOGICAL: return "LOGICAL"; + case DAVQL_FUNCCALL: return "FUNCCALL"; + default: return "unknown"; + } +} + +static const char* _map_specialfield(int info) { + switch(info) { + case 0: return ""; + case 1: return "with wildcard"; + case 2: return "(resource data only)"; + default: return "with mysterious identifier"; + } +} + +static const char* _map_operator(davqloperator_t op) { + // don't use string array, because enum values may change + switch(op) { + case DAVQL_NOOP: return "no operator"; + case DAVQL_CALL: return "function call"; case DAVQL_ARGLIST: return ","; + case DAVQL_ADD: return "+"; case DAVQL_SUB: return "-"; + case DAVQL_MUL: return "*"; case DAVQL_DIV: return "/"; + case DAVQL_AND: return "&"; case DAVQL_OR: return "|"; + case DAVQL_XOR: return "^"; case DAVQL_NEG: return "~"; + case DAVQL_NOT: return "NOT"; case DAVQL_LAND: return "AND"; + case DAVQL_LOR: return "OR"; case DAVQL_LXOR: return "XOR"; + case DAVQL_EQ: return "="; case DAVQL_NEQ: return "!="; + case DAVQL_LT: return "<"; case DAVQL_GT: return ">"; + case DAVQL_LE: return "<="; case DAVQL_GE: return ">="; + case DAVQL_LIKE: return "LIKE"; case DAVQL_UNLIKE: return "UNLIKE"; + default: return "unknown"; + } +} + +static void dav_debug_ql_fnames_print(DavQLStatement *stmt) { + if (stmt->fields) { + printf("Field names: "); + CxIterator i = cxListIterator(stmt->fields); + cx_foreach(DavQLField *, f, i) { + printf("%.*s, ", (int)f->name.length, f->name.ptr); + } + printf("\b\b \b\b\n"); + } +} + +static void dav_debug_ql_stmt_print(DavQLStatement *stmt) { + // Basic information + size_t fieldcount = stmt->fields ? stmt->fields->size : 0; + int specialfield = 0; + if (stmt->fields && stmt->fields->size > 0) { + DavQLField* firstfield = (DavQLField*)cxListAt(stmt->fields, 0); + if (firstfield->expr->type == DAVQL_IDENTIFIER) { + switch (firstfield->expr->srctext.ptr[0]) { + case '*': specialfield = 1; break; + case '-': specialfield = 2; break; + } + } + } + if (specialfield) { + fieldcount--; + } + printf("Statement: %.*s\nType: %s\nField count: %zu %s\n", + (int)stmt->srctext.length, stmt->srctext.ptr, + _map_querytype(stmt->type), + fieldcount, + _map_specialfield(specialfield)); + + dav_debug_ql_fnames_print(stmt); + printf("Path: %.*s\nHas where clause: %s\n", + (int)stmt->path.length, stmt->path.ptr, + stmt->where ? "yes" : "no"); + + // WITH attributes + if (stmt->depth == DAV_DEPTH_INFINITY) { + printf("Depth: infinity\n"); + } else if (stmt->depth == DAV_DEPTH_PLACEHOLDER) { + printf("Depth: placeholder\n"); + } else { + printf("Depth: %d\n", stmt->depth); + } + + // order by clause + printf("Order by: "); + if (stmt->orderby) { + CxIterator i = cxListIterator(stmt->orderby); + cx_foreach(DavQLOrderCriterion*, critdata, i) { + printf("%.*s %s%s", (int)critdata->column->srctext.length, critdata->column->srctext.ptr, + critdata->descending ? "desc" : "asc", + i.index+1 < stmt->orderby->size ? ", " : "\n"); + } + } else { + printf("nothing\n"); + } + + // error messages + if (stmt->errorcode) { + printf("\nError code: %d\nError: %s\n", + stmt->errorcode, stmt->errormessage); + } +} + +static int dav_debug_ql_expr_selected(DavQLExpression *expr) { + if (!expr) { + printf("Currently no expression selected.\n"); + return 0; + } else { + return 1; + } +} + +static void dav_debug_ql_expr_print(DavQLExpression *expr) { + if (dav_debug_ql_expr_selected(expr)) { + cxstring empty = CX_STR("(empty)"); + printf( + "Text: %.*s\nType: %s\nOperator: %s\n", + sfmtarg(expr->srctext), + _map_exprtype(expr->type), + _map_operator(expr->op)); + if (expr->left || expr->right) { + printf("Left hand: %.*s\nRight hand: %.*s\n", + sfmtarg(expr->left?expr->left->srctext:empty), + sfmtarg(expr->right?expr->right->srctext:empty)); + } + } +} + +static void dav_debug_ql_field_print(DavQLField *field) { + if (field) { + printf("Name: %.*s\n", sfmtarg(field->name)); + if (field->expr) { + dav_debug_ql_expr_print(field->expr); + } else { + printf("No expression.\n"); + } + } else { + printf("No field selected.\n"); + } +} + +static void dav_debug_ql_tree_print(DavQLExpression *expr, int depth) { + if (expr) { + if (expr->left) { + printf("%*c%s\n", depth, ' ', _map_operator(expr->op)); + dav_debug_ql_tree_print(expr->left, depth+1); + dav_debug_ql_tree_print(expr->right, depth+1); + } else if (expr->type == DAVQL_UNARY) { + printf("%*c%s %.*s\n", depth, ' ', _map_operator(expr->op), + sfmtarg(expr->srctext)); + } else { + printf("%*c%.*s\n", depth, ' ', sfmtarg(expr->srctext)); + } + } +} + +#define DQLD_CMD_Q 0 +#define DQLD_CMD_PS 1 +#define DQLD_CMD_PE 2 +#define DQLD_CMD_PF 3 +#define DQLD_CMD_PT 4 +#define DQLD_CMD_F 10 +#define DQLD_CMD_W 11 +#define DQLD_CMD_O 12 +#define DQLD_CMD_L 21 +#define DQLD_CMD_R 22 +#define DQLD_CMD_N 23 +#define DQLD_CMD_P 24 +#define DQLD_CMD_H 100 + +static int dav_debug_ql_command() { + printf("> "); + + char buffer[8]; + fgets(buffer, 8, stdin); + // discard remaining chars + if (!strchr(buffer, '\n')) { + int chr; + while ((chr = fgetc(stdin) != '\n') && chr != EOF); + } + + if (!strcmp(buffer, "q\n")) { + return DQLD_CMD_Q; + } else if (!strcmp(buffer, "ps\n")) { + return DQLD_CMD_PS; + } else if (!strcmp(buffer, "pe\n")) { + return DQLD_CMD_PE; + } else if (!strcmp(buffer, "pf\n")) { + return DQLD_CMD_PF; + } else if (!strcmp(buffer, "pt\n")) { + return DQLD_CMD_PT; + } else if (!strcmp(buffer, "l\n")) { + return DQLD_CMD_L; + } else if (!strcmp(buffer, "r\n")) { + return DQLD_CMD_R; + } else if (!strcmp(buffer, "h\n")) { + return DQLD_CMD_H; + } else if (!strcmp(buffer, "f\n")) { + return DQLD_CMD_F; + } else if (!strcmp(buffer, "w\n")) { + return DQLD_CMD_W; + } else if (!strcmp(buffer, "o\n")) { + return DQLD_CMD_O; + } else if (!strcmp(buffer, "n\n")) { + return DQLD_CMD_N; + } else if (!strcmp(buffer, "p\n")) { + return DQLD_CMD_P; + } else { + return -1; + } +} + +void dav_debug_statement(DavQLStatement *stmt) { + if (!stmt) { + fprintf(stderr, "Debug DavQLStatement failed: null pointer"); + return; + } + + printf("Starting DavQL debugger (type 'h' for help)...\n\n"); + dav_debug_ql_stmt_print(stmt); + + if (stmt->errorcode) { + return; + } + + DavQLExpression *examineexpr = NULL; + CxList *examineelem = NULL; + int examineclause = 0; + + while(1) { + int cmd = dav_debug_ql_command(); + switch (cmd) { + case DQLD_CMD_Q: return; + case DQLD_CMD_PS: dav_debug_ql_stmt_print(stmt); break; + case DQLD_CMD_PE: dav_debug_ql_expr_print(examineexpr); break; + case DQLD_CMD_PT: dav_debug_ql_tree_print(examineexpr, 1); break; + case DQLD_CMD_PF: dav_debug_ql_fnames_print(stmt); break; + case DQLD_CMD_F: + examineclause = DQLD_CMD_F; + examineelem = stmt->fields; + if (stmt->fields && stmt->fields->size > 0) { + DavQLField* field = cxListAt(stmt->fields, 0); + examineexpr = field->expr; + dav_debug_ql_field_print(field); + } else { + examineexpr = NULL; + } + break; + case DQLD_CMD_W: + examineclause = 0; examineelem = NULL; + examineexpr = stmt->where; + dav_debug_ql_expr_print(examineexpr); + break; + case DQLD_CMD_O: + examineclause = DQLD_CMD_O; + examineelem = stmt->orderby; + examineexpr = stmt->orderby && stmt->orderby->size > 0 ? + ((DavQLOrderCriterion*)cxListAt(stmt->orderby, 0))->column : NULL; + dav_debug_ql_expr_print(examineexpr); + break; + case DQLD_CMD_N: + case DQLD_CMD_P: + printf("TODO: port code to ucx 3\n"); + /* + if (examineelem) { + CxList *newelem = (cmd == DQLD_CMD_N ? + examineelem->next : examineelem->prev); + if (newelem) { + examineelem = newelem; + if (examineclause == DQLD_CMD_O) { + examineexpr = ((DavQLOrderCriterion*) + examineelem->data)->column; + dav_debug_ql_expr_print(examineexpr); + } else if (examineclause == DQLD_CMD_F) { + DavQLField* field = (DavQLField*)examineelem->data; + examineexpr = field->expr; + dav_debug_ql_field_print(field); + } else { + printf("Examining unknown clause type."); + } + } else { + printf("Reached end of list.\n"); + } + } else { + printf("Currently not examining an expression list.\n"); + } + */ + break; + case DQLD_CMD_L: + if (dav_debug_ql_expr_selected(examineexpr)) { + if (examineexpr->left) { + examineexpr = examineexpr->left; + dav_debug_ql_expr_print(examineexpr); + } else { + printf("There is no left subtree.\n"); + } + } + break; + case DQLD_CMD_R: + if (dav_debug_ql_expr_selected(examineexpr)) { + if (examineexpr->right) { + examineexpr = examineexpr->right; + dav_debug_ql_expr_print(examineexpr); + } else { + printf("There is no right subtree.\n"); + } + } + break; + case DQLD_CMD_H: + printf( + "\nCommands:\n" + "ps: print statement information\n" + "o: examine order by clause\n" + "f: examine field list\n" + "pf: print field names\n" + "w: examine where clause\n" + "n: examine next expression " + "(in order by clause or field list)\n" + "p: examine previous expression " + "(in order by clause or field list)\n" + "q: quit\n\n" + "\nExpression examination:\n" + "pe: print expression information\n" + "pt: print full syntax tree of current (sub-)expression\n" + "l: enter left subtree\n" + "r: enter right subtree\n"); + break; + default: printf("unknown command\n"); + } + } +} + +// ------------------------------------------------------------------------ +// P A R S E R +// ------------------------------------------------------------------------ + +#define _error_context "(%.*s[->]%.*s%.*s)" +#define _error_invalid "invalid statement" +#define _error_out_of_memory "out of memory" +#define _error_unexpected_token "unexpected token " _error_context +#define _error_invalid_token "invalid token " _error_context +#define _error_missing_path "expected path " _error_context +#define _error_missing_from "expecting FROM keyword " _error_context +#define _error_missing_at "expecting AT keyword " _error_context +#define _error_missing_by "expecting BY keyword " _error_context +#define _error_missing_as "expecting alias ('as ') " _error_context +#define _error_missing_identifier "expecting identifier " _error_context +#define _error_missing_par "missing closed parenthesis " _error_context +#define _error_missing_assign "expecting assignment ('=') " _error_context +#define _error_missing_where "SET statements must have a WHERE clause or " \ + "explicitly use ANYWHERE " _error_context +#define _error_invalid_depth "invalid depth " _error_context +#define _error_missing_expr "missing expression " _error_context +#define _error_invalid_expr "invalid expression " _error_context +#define _error_invalid_unary_op "invalid unary operator " _error_context +#define _error_invalid_logical_op "invalid logical operator " _error_context +#define _error_invalid_fmtspec "invalid format specifier " _error_context +#define _error_invalid_string "string expected " _error_context +#define _error_invalid_order_criterion "invalid order criterion " _error_context + +#define token_sstr(token) ((token)->value) + +static void dav_error_in_context(int errorcode, const char *errormsg, + DavQLStatement *stmt, DavQLToken *token) { + + // we try to achieve two things: get as many information as possible + // and recover the concrete source string (and not the token strings) + cxstring emptystring = CX_STR(""); + cxstring prev = token->prev ? (token->prev->prev ? + token_sstr(token->prev->prev) : token_sstr(token->prev)) + : emptystring; + cxstring tokenstr = token_sstr(token); + cxstring next = token->next ? (token->next->next ? + token_sstr(token->next->next) : token_sstr(token->next)) + : emptystring; + + int lp = prev.length == 0 ? 0 : tokenstr.ptr-prev.ptr; + const char *pn = tokenstr.ptr + tokenstr.length; + int ln = next.ptr+next.length - pn; + + stmt->errorcode = errorcode; + stmt->errormessage = cx_asprintf(errormsg, + lp, prev.ptr, + sfmtarg(tokenstr), + ln, pn).ptr; +} + +#define dqlsec_alloc_failed(ptr, stmt) \ + if (!(ptr)) do { \ + (stmt)->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; \ + return 0; \ + } while(0) +#define dqlsec_malloc(stmt, ptr, type) \ + dqlsec_alloc_failed(ptr = malloc(sizeof(type)), stmt) +#define dqlsec_mallocz(stmt, ptr, type) \ + dqlsec_alloc_failed(ptr = calloc(1, sizeof(type)), stmt) + + +// special symbols are single tokens - the % sign MUST NOT be a special symbol +static const char *special_token_symbols = ",()+-*/&|^~=!<>"; + +static _Bool iskeyword(DavQLToken *token) { + cxstring keywords[] ={CX_STR("select"), CX_STR("set"), CX_STR("from"), CX_STR("at"), CX_STR("as"), + CX_STR("where"), CX_STR("anywhere"), CX_STR("like"), CX_STR("unlike"), CX_STR("and"), + CX_STR("or"), CX_STR("not"), CX_STR("xor"), CX_STR("with"), CX_STR("infinity"), + CX_STR("order"), CX_STR("by"), CX_STR("asc"), CX_STR("desc") + }; + for (int i = 0 ; i < sizeof(keywords)/sizeof(cxstring) ; i++) { + if (!cx_strcasecmp(token->value, keywords[i])) { + return 1; + } + } + return 0; +} + +static _Bool islongoperator(DavQLToken *token) { + cxstring operators[] = {CX_STR("and"), CX_STR("or"), CX_STR("not"), CX_STR("xor"), + CX_STR("like"), CX_STR("unlike") + }; + for (int i = 0 ; i < sizeof(operators)/sizeof(cxstring) ; i++) { + if (!cx_strcasecmp(token->value, operators[i])) { + return 1; + } + } + return 0; +} + +static int dav_stmt_add_field(DavQLStatement *stmt, DavQLField *field) { + if(!stmt->fields) { + stmt->fields = cxLinkedListCreateSimple(CX_STORE_POINTERS); + if(!stmt->fields) { + stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; + return 1; + } + } + + if(cxListAdd(stmt->fields, field)) { + stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; + return 1; + } + + return 0; +} + + +static void tokenlist_free(DavQLToken *tokenlist) { + DavQLToken *token = tokenlist; + while(token) { + DavQLToken *next = token->next; + free(token); + token = next; + } +} + +static int dav_parse_add_token(DavQLToken **begin, DavQLToken **end, DavQLToken *token) { + + // determine token class (order of if-statements is very important!) + char firstchar = token->value.ptr[0]; + + if (isdigit(firstchar)) { + token->tokenclass = DAVQL_TOKEN_NUMBER; + // check, if all characters are digits + for (size_t i = 1 ; i < token->value.length ; i++) { + if (!isdigit(token->value.ptr[i])) { + token->tokenclass = DAVQL_TOKEN_INVALID; + break; + } + } + } else if (firstchar == '%') { + token->tokenclass = DAVQL_TOKEN_FMTSPEC; + } else if (token->value.length == 1) { + switch (firstchar) { + case '(': token->tokenclass = DAVQL_TOKEN_OPENP; break; + case ')': token->tokenclass = DAVQL_TOKEN_CLOSEP; break; + case ',': token->tokenclass = DAVQL_TOKEN_COMMA; break; + default: + token->tokenclass = strchr(special_token_symbols, firstchar) ? + DAVQL_TOKEN_OPERATOR : DAVQL_TOKEN_IDENTIFIER; + } + } else if (islongoperator(token)) { + token->tokenclass = DAVQL_TOKEN_OPERATOR; + } else if (firstchar == '\'') { + token->tokenclass = DAVQL_TOKEN_STRING; + } else if (firstchar == '`') { + token->tokenclass = DAVQL_TOKEN_IDENTIFIER; + } else if (iskeyword(token)) { + token->tokenclass = DAVQL_TOKEN_KEYWORD; + } else { + token->tokenclass = DAVQL_TOKEN_IDENTIFIER; + // TODO: check for illegal characters + } + + // remove quotes (extreme cool feature) + if (token->tokenclass == DAVQL_TOKEN_STRING || + (token->tokenclass == DAVQL_TOKEN_IDENTIFIER && firstchar == '`')) { + + char lastchar = token->value.ptr[token->value.length-1]; + if (firstchar == lastchar) { + token->value.ptr++; + token->value.length -= 2; + } else { + token->tokenclass = DAVQL_TOKEN_INVALID; + } + } + + cx_linked_list_add((void**)begin, (void**)end, offsetof(DavQLToken, prev), offsetof(DavQLToken, next), token); + return 0; +} + + + +static DavQLToken* dav_parse_tokenize(cxstring src) { +#define alloc_token() do {token = calloc(1, sizeof(DavQLToken));\ + if(!token) {tokenlist_free(tokens_begin); return NULL;}} while(0) +#define add_token() if(dav_parse_add_token(&tokens_begin, &tokens_end, token)) return NULL; + + DavQLToken *tokens_begin = NULL; + DavQLToken *tokens_end = NULL; + + DavQLToken *token = NULL; + + char insequence = '\0'; + for (size_t i = 0 ; i < src.length ; i++) { + // quoted strings / identifiers are a single token + if (src.ptr[i] == '\'' || src.ptr[i] == '`') { + if (src.ptr[i] == insequence) { + // lookahead for escaped string quotes + if (src.ptr[i] == '\'' && i+2 < src.length && + src.ptr[i+1] == src.ptr[i] && src.ptr[i+2] == src.ptr[i]) { + token->value.length += 3; + i += 2; + } else { + // add quoted token to list + token->value.length++; + add_token(); + token = NULL; + insequence = '\0'; + } + } else if (insequence == '\0') { + insequence = src.ptr[i]; + // always create new token for quoted strings + if (token) { + add_token(); + } + alloc_token(); + token->value.ptr = src.ptr + i; + token->value.length = 1; + } else { + // add other kind of quotes to token + token->value.length++; + } + } else if (insequence) { + token->value.length++; + } else if (isspace(src.ptr[i])) { + // add token before spaces to list (if any) + if (token) { + add_token(); + token = NULL; + } + } else if (strchr(special_token_symbols, src.ptr[i])) { + // add token before special symbol to list (if any) + if (token) { + add_token(); + token = NULL; + } + // add special symbol as single token to list + alloc_token(); + token->value.ptr = src.ptr + i; + token->value.length = 1; + add_token(); + // set tokenizer ready to read more tokens + token = NULL; + } else { + // if this is a new token, create memory for it + if (!token) { + alloc_token(); + token->value.ptr = src.ptr + i; + token->value.length = 0; + } + // extend token length when reading more bytes + token->value.length++; + } + } + + if (token) { + add_token(); + } + + alloc_token(); + token->tokenclass = DAVQL_TOKEN_END; + token->value = CX_STR(""); + + cx_linked_list_add((void**)&tokens_begin, (void**)&tokens_end, offsetof(DavQLToken, prev), offsetof(DavQLToken, next), token); + return tokens_begin; +#undef alloc_token +#undef add_token +} + +static void dav_free_expression(DavQLExpression *expr) { + if (expr) { + if (expr->left) { + dav_free_expression(expr->left); + } + if (expr->right) { + dav_free_expression(expr->right); + } + free(expr); + } +} + +static void dav_free_field(DavQLField *field) { + dav_free_expression(field->expr); + free(field); +} + +static void dav_free_order_criterion(DavQLOrderCriterion *crit) { + if (crit->column) { // do it null-safe though column is expected to be set + dav_free_expression(crit->column); + } +} + +#define token_is(token, expectedclass) (token && \ + (token->tokenclass == expectedclass)) + +#define tokenvalue_is(token, expectedvalue) (token && \ + !cx_strcasecmp(token->value, cx_str(expectedvalue))) + +typedef int(*exprparser_f)(DavQLStatement*,DavQLToken*,DavQLExpression*); + +static int dav_parse_binary_expr(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr, exprparser_f parseL, char* opc, int* opv, + exprparser_f parseR) { + + if (!token) { + return 0; + } + + int total_consumed = 0, consumed; + + // save temporarily on stack (copy to heap later on) + DavQLExpression left, right; + + // RULE: LEFT, [Operator, RIGHT] + memset(&left, 0, sizeof(DavQLExpression)); + consumed = parseL(stmt, token, &left); + if (!consumed || stmt->errorcode) { + return 0; + } + total_consumed += consumed; + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + + char *op; + if (token_is(token, DAVQL_TOKEN_OPERATOR) && + (op = strchr(opc, token_sstr(token).ptr[0]))) { + expr->op = opv[op-opc]; + expr->type = DAVQL_BINARY; + total_consumed++; + token = token->next; + memset(&right, 0, sizeof(DavQLExpression)); + consumed = parseR(stmt, token, &right); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, + _error_missing_expr, stmt, token); + return 0; + } + total_consumed += consumed; + } + + if (expr->op == DAVQL_NOOP) { + memcpy(expr, &left, sizeof(DavQLExpression)); + } else { + dqlsec_malloc(stmt, expr->left, DavQLExpression); + memcpy(expr->left, &left, sizeof(DavQLExpression)); + dqlsec_malloc(stmt, expr->right, DavQLExpression); + memcpy(expr->right, &right, sizeof(DavQLExpression)); + + expr->srctext.ptr = expr->left->srctext.ptr; + expr->srctext.length = + expr->right->srctext.ptr - + expr->left->srctext.ptr + expr->right->srctext.length; + } + + return total_consumed; +} + +static void fmt_args_add(DavQLStatement *stmt, void *data) { + if(!stmt->args) { + stmt->args = cxLinkedListCreateSimple(CX_STORE_POINTERS); + } + cxListAdd(stmt->args, data); +} + +static void dav_add_fmt_args(DavQLStatement *stmt, cxstring str) { + int placeholder = 0; + for (size_t i=0;isrctext = token_sstr(token); + if (token_is(token, DAVQL_TOKEN_NUMBER)) { + expr->type = DAVQL_NUMBER; + } else if (token_is(token, DAVQL_TOKEN_STRING)) { + expr->type = DAVQL_STRING; + // check for format specifiers and add args + dav_add_fmt_args(stmt, expr->srctext); + } else if (token_is(token, DAVQL_TOKEN_TIMESTAMP)) { + expr->type = DAVQL_TIMESTAMP; + } else if (token_is(token, DAVQL_TOKEN_FMTSPEC) + && expr->srctext.length == 2) { + switch (expr->srctext.ptr[1]) { + case 'd': expr->type = DAVQL_NUMBER; break; + case 's': expr->type = DAVQL_STRING; break; + case 't': expr->type = DAVQL_TIMESTAMP; break; + default: + dav_error_in_context(DAVQL_ERROR_INVALID_FMTSPEC, + _error_invalid_fmtspec, stmt, token); + return 0; + } + // add fmtspec type to query arg list + fmt_args_add(stmt, (void*)(intptr_t)expr->srctext.ptr[1]); + } else { + return 0; + } + + return 1; +} + +// forward declaration +static int dav_parse_expression(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr); + +static int dav_parse_arglist(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + expr->srctext.ptr = token_sstr(token).ptr; + expr->srctext.length = 0; + expr->left = expr->right = NULL; // in case we fail, we want them to be sane + + int total_consumed = 0; + + // RULE: Expression, {",", Expression}; + DavQLExpression *arglist = expr; + DavQLExpression arg; + const char *lastchar = expr->srctext.ptr; + int consumed; + do { + memset(&arg, 0, sizeof(DavQLExpression)); + consumed = dav_parse_expression(stmt, token, &arg); + if (consumed) { + lastchar = arg.srctext.ptr + arg.srctext.length; + total_consumed += consumed; + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + // look ahead for a comma + if (token_is(token, DAVQL_TOKEN_COMMA)) { + total_consumed++; + token = token->next; + /* we have more arguments, so put the current argument to the + * left subtree and create a new node to the right + */ + dqlsec_malloc(stmt, arglist->left, DavQLExpression); + memcpy(arglist->left, &arg, sizeof(DavQLExpression)); + arglist->srctext.ptr = arg.srctext.ptr; + arglist->op = DAVQL_ARGLIST; + arglist->type = DAVQL_FUNCCALL; + dqlsec_mallocz(stmt, arglist->right, DavQLExpression); + arglist = arglist->right; + } else { + // this was the last argument, so write it to the current node + memcpy(arglist, &arg, sizeof(DavQLExpression)); + consumed = 0; + } + } + } while (consumed && !stmt->errorcode); + + // recover source text + arglist = expr; + while (arglist && arglist->type == DAVQL_FUNCCALL) { + arglist->srctext.length = lastchar - arglist->srctext.ptr; + arglist = arglist->right; + } + + return total_consumed; +} + +static int dav_parse_funccall(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + // RULE: Identifier, "(", ArgumentList, ")"; + if (token_is(token, DAVQL_TOKEN_IDENTIFIER) && + token_is(token->next, DAVQL_TOKEN_OPENP)) { + + expr->type = DAVQL_FUNCCALL; + expr->op = DAVQL_CALL; + + dqlsec_mallocz(stmt, expr->left, DavQLExpression); + expr->left->type = DAVQL_IDENTIFIER; + expr->left->srctext = token_sstr(token); + expr->right = NULL; + + token = token->next->next; + + DavQLExpression arg; + int argtokens = dav_parse_arglist(stmt, token, &arg); + if (stmt->errorcode) { + // if an error occurred while parsing the arglist, return now + return 2; + } + if (argtokens) { + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), argtokens); + dqlsec_malloc(stmt, expr->right, DavQLExpression); + memcpy(expr->right, &arg, sizeof(DavQLExpression)); + } else { + // arg list may be empty + expr->right = NULL; + } + + if (token_is(token, DAVQL_TOKEN_CLOSEP)) { + return 3 + argtokens; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_PAR, _error_missing_par, + stmt, token); + return 2; // it MUST be a function call, but it is invalid + } + } else { + return 0; + } +} + +static int dav_parse_unary_expr(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + DavQLToken *firsttoken = token; // save for srctext recovery + + DavQLExpression* atom = expr; + int total_consumed = 0; + + // optional unary operator + if (token_is(token, DAVQL_TOKEN_OPERATOR)) { + char *op = strchr("+-~", token_sstr(token).ptr[0]); + if (op) { + expr->type = DAVQL_UNARY; + switch (*op) { + case '+': expr->op = DAVQL_ADD; break; + case '-': expr->op = DAVQL_SUB; break; + case '~': expr->op = DAVQL_NEG; break; + } + dqlsec_mallocz(stmt, expr->left, DavQLExpression); + atom = expr->left; + total_consumed++; + token = token->next; + } else { + dav_error_in_context(DAVQL_ERROR_INVALID_UNARY_OP, + _error_invalid_unary_op, stmt, token); + return 0; + } + } + + // RULE: (ParExpression | AtomicExpression) + if (token_is(token, DAVQL_TOKEN_OPENP)) { + token = token->next; total_consumed++; + // RULE: "(", Expression, ")" + int consumed = dav_parse_expression(stmt, token, atom); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context(DAVQL_ERROR_INVALID_EXPR, + _error_invalid_expr, stmt, token); + return 0; + } + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + if (token_is(token, DAVQL_TOKEN_CLOSEP)) { + token = token->next; total_consumed++; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_PAR, + _error_missing_par, stmt, token); + return 0; + } + } else { + // RULE: FunctionCall + int consumed = dav_parse_funccall(stmt, token, atom); + if (consumed) { + total_consumed += consumed; + } else if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { + // RULE: Identifier + total_consumed++; + atom->type = DAVQL_IDENTIFIER; + atom->srctext = token_sstr(token); + } else { + // RULE: Literal + total_consumed += dav_parse_literal(stmt, token, atom); + } + } + + // recover source text + expr->srctext.ptr = token_sstr(firsttoken).ptr; + if (total_consumed > 0) { + cxstring lasttoken = + token_sstr((DavQLToken*)cx_linked_list_at(token, 0, offsetof(DavQLToken, next), total_consumed-1)); + expr->srctext.length = + lasttoken.ptr - expr->srctext.ptr + lasttoken.length; + } else { + // the expression should not be used anyway, but we want to be safe + expr->srctext.length = 0; + } + + + return total_consumed; +} + +static int dav_parse_bitexpr(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + return dav_parse_binary_expr(stmt, token, expr, + dav_parse_unary_expr, + "&|^", (int[]){DAVQL_AND, DAVQL_OR, DAVQL_XOR}, + dav_parse_bitexpr); +} + +static int dav_parse_multexpr(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + return dav_parse_binary_expr(stmt, token, expr, + dav_parse_bitexpr, + "*/", (int[]){DAVQL_MUL, DAVQL_DIV}, + dav_parse_multexpr); +} + +static int dav_parse_expression(DavQLStatement* stmt, DavQLToken* token, + DavQLExpression* expr) { + + return dav_parse_binary_expr(stmt, token, expr, + dav_parse_multexpr, + "+-", (int[]){DAVQL_ADD, DAVQL_SUB}, + dav_parse_expression); +} + +static int dav_parse_named_field(DavQLStatement *stmt, DavQLToken *token, + DavQLField *field) { + int total_consumed = 0, consumed; + + // RULE: Expression, " as ", Identifier; + DavQLExpression *expr; + dqlsec_mallocz(stmt, expr, DavQLExpression); + consumed = dav_parse_expression(stmt, token, expr); + if (stmt->errorcode) { + dav_free_expression(expr); + return 0; + } + if (expr->type == DAVQL_UNDEFINED_TYPE) { + dav_free_expression(expr); + dav_error_in_context(DAVQL_ERROR_INVALID_EXPR, + _error_invalid_expr, stmt, token); + return 0; + } + + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + + if (token_is(token, DAVQL_TOKEN_KEYWORD) && tokenvalue_is(token, "as")) { + token = token->next; total_consumed++; + } else { + dav_free_expression(expr); + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_as, stmt, token); + return 0; + } + + if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { + field->name = token_sstr(token); + field->expr = expr; + return total_consumed + 1; + } else { + dav_free_expression(expr); + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_identifier, stmt, token); + return 0; + } +} + +static int dav_parse_fieldlist(DavQLStatement *stmt, DavQLToken *token) { + + // RULE: "-" + if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "-")) { + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + dqlsec_mallocz(stmt, field->expr, DavQLExpression); + field->expr->type = DAVQL_IDENTIFIER; + field->expr->srctext = field->name = token_sstr(token); + return 1; + } + + // RULE: "*", {",", NamedExpression} + if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "*")) { + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + dqlsec_mallocz(stmt, field->expr, DavQLExpression); + field->expr->type = DAVQL_IDENTIFIER; + field->expr->srctext = field->name = token_sstr(token); + + int total_consumed = 0; + int consumed = 1; + + do { + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + + if (token_is(token, DAVQL_TOKEN_COMMA)) { + total_consumed++; token = token->next; + DavQLField localfield; + consumed = dav_parse_named_field(stmt, token, &localfield); + if (!stmt->errorcode && consumed) { + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + memcpy(field, &localfield, sizeof(DavQLField)); + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + } + } else { + consumed = 0; + } + } while (consumed > 0); + + return total_consumed; + } + + // RULE: FieldExpression, {",", FieldExpression} + { + int total_consumed = 0, consumed; + do { + // RULE: NamedField | Identifier + DavQLField localfield; + consumed = dav_parse_named_field(stmt, token, &localfield); + if (consumed) { + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + memcpy(field, &localfield, sizeof(DavQLField)); + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + } else if (token_is(token, DAVQL_TOKEN_IDENTIFIER) + // look ahead, if the field is JUST the identifier + && (token_is(token->next, DAVQL_TOKEN_COMMA) || + tokenvalue_is(token->next, "from"))) { + + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + dqlsec_mallocz(stmt, field->expr, DavQLExpression); + field->expr->type = DAVQL_IDENTIFIER; + field->expr->srctext = field->name = token_sstr(token); + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + + consumed = 1; + total_consumed++; + token = token->next; + + // we found a valid solution, so erase any errors + stmt->errorcode = 0; + if (stmt->errormessage) { + free(stmt->errormessage); + stmt->errormessage = NULL; + } + } else { + // dav_parse_named_field has already thrown a good error + consumed = 0; + } + + // field has been parsed, now try to get a comma + if (consumed) { + consumed = token_is(token, DAVQL_TOKEN_COMMA) ? 1 : 0; + if (consumed) { + token = token->next; + total_consumed++; + } + } + } while (consumed); + + return total_consumed; + } +} + +// forward declaration +static int dav_parse_logical_expr(DavQLStatement *stmt, DavQLToken *token, + DavQLExpression *expr); + +static int dav_parse_bool_prim(DavQLStatement *stmt, DavQLToken *token, + DavQLExpression *expr) { + + expr->type = DAVQL_LOGICAL; + expr->srctext = token_sstr(token); + + int total_consumed = 0; + + DavQLExpression bexpr; + memset(&bexpr, 0, sizeof(DavQLExpression)); + total_consumed = dav_parse_expression(stmt, token, &bexpr); + if (!total_consumed || stmt->errorcode) { + return 0; + } + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), total_consumed); + + DavQLToken* optok = token; + // RULE: Expression, (" like " | " unlike "), String + if (token_is(optok, DAVQL_TOKEN_OPERATOR) && (tokenvalue_is(optok, + "like") || tokenvalue_is(optok, "unlike"))) { + + total_consumed++; + token = token->next; + if (token_is(token, DAVQL_TOKEN_STRING)) { + expr->op = tokenvalue_is(optok, "like") ? + DAVQL_LIKE : DAVQL_UNLIKE; + dqlsec_malloc(stmt, expr->left, DavQLExpression); + memcpy(expr->left, &bexpr, sizeof(DavQLExpression)); + dqlsec_mallocz(stmt, expr->right, DavQLExpression); + expr->right->type = DAVQL_STRING; + expr->right->srctext = token_sstr(token); + expr->srctext.length = expr->right->srctext.ptr - + expr->srctext.ptr + expr->right->srctext.length; + + // fmt args + dav_add_fmt_args(stmt, expr->right->srctext); + + return total_consumed + 1; + } else { + dav_error_in_context(DAVQL_ERROR_INVALID_STRING, + _error_invalid_string, stmt, token); + return 0; + } + } + // RULE: Expression, Comparison, Expression + else if (token_is(optok, DAVQL_TOKEN_OPERATOR) && ( + tokenvalue_is(optok, "=") || tokenvalue_is(optok, "!") || + tokenvalue_is(optok, "<") || tokenvalue_is(optok, ">"))) { + + total_consumed++; + token = token->next; + + if (tokenvalue_is(optok, "=")) { + expr->op = DAVQL_EQ; + } else { + if (tokenvalue_is(token, "=")) { + if (tokenvalue_is(optok, "!")) { + expr->op = DAVQL_NEQ; + } else if (tokenvalue_is(optok, "<")) { + expr->op = DAVQL_LE; + } else if (tokenvalue_is(optok, ">")) { + expr->op = DAVQL_GE; + } + total_consumed++; + token = token->next; + } else { + if (tokenvalue_is(optok, "<")) { + expr->op = DAVQL_LT; + } else if (tokenvalue_is(optok, ">")) { + expr->op = DAVQL_GT; + } + } + } + + DavQLExpression rexpr; + memset(&rexpr, 0, sizeof(DavQLExpression)); + int consumed = dav_parse_expression(stmt, token, &rexpr); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context( + DAVQL_ERROR_MISSING_EXPR, _error_missing_expr, + stmt, token); + return 0; + } + + total_consumed += consumed; + dqlsec_malloc(stmt, expr->left, DavQLExpression); + memcpy(expr->left, &bexpr, sizeof(DavQLExpression)); + dqlsec_malloc(stmt, expr->right, DavQLExpression); + memcpy(expr->right, &rexpr, sizeof(DavQLExpression)); + + expr->srctext.length = expr->right->srctext.ptr - + expr->srctext.ptr + expr->right->srctext.length; + + return total_consumed; + } + // RULE: FunctionCall | Identifier; + else if (bexpr.type == DAVQL_FUNCCALL || bexpr.type == DAVQL_IDENTIFIER) { + memcpy(expr, &bexpr, sizeof(DavQLExpression)); + + return total_consumed; + } else { + return 0; + } +} + +static int dav_parse_bool_expr(DavQLStatement *stmt, DavQLToken *token, + DavQLExpression *expr) { + + // RULE: "not ", LogicalExpression + if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "not")) { + expr->type = DAVQL_LOGICAL; + expr->op = DAVQL_NOT; + dqlsec_mallocz(stmt, expr->left, DavQLExpression); + expr->srctext = token_sstr(token); + + token = token->next; + int consumed = dav_parse_bool_expr(stmt, token, expr->left); + if (stmt->errorcode) { + return 0; + } + if (consumed) { + cxstring lasttok = token_sstr((DavQLToken*)cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed-1)); + expr->srctext.length = + lasttok.ptr - expr->srctext.ptr + lasttok.length; + return consumed + 1; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, + _error_missing_expr, stmt, token); + return 0; + } + } + // RULE: "(", LogicalExpression, ")" + else if (token_is(token, DAVQL_TOKEN_OPENP)) { + int consumed = dav_parse_logical_expr(stmt, token->next, expr); + if (consumed) { + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + + if (token_is(token, DAVQL_TOKEN_CLOSEP)) { + token = token->next; + return consumed + 2; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_PAR, _error_missing_par, + stmt, token); + return 0; + } + } else { + // don't handle errors here, we can also try a boolean primary + stmt->errorcode = 0; + if (stmt->errormessage) { + free(stmt->errormessage); + } + } + } + + // RULE: BooleanPrimary + return dav_parse_bool_prim(stmt, token, expr); +} + +static int dav_parse_logical_expr(DavQLStatement *stmt, DavQLToken *token, + DavQLExpression *expr) { + + DavQLToken *firsttoken = token; + int total_consumed = 0; + + // RULE: BooleanLiteral, [LogicalOperator, LogicalExpression]; + DavQLExpression left, right; + memset(&left, 0, sizeof(DavQLExpression)); + int consumed = dav_parse_bool_expr(stmt, token, &left); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, + _error_missing_expr, stmt, token); + return 0; + } + total_consumed += consumed; + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + + if (token_is(token, DAVQL_TOKEN_OPERATOR)) { + expr->type = DAVQL_LOGICAL; + + davqloperator_t op = DAVQL_NOOP; + if (tokenvalue_is(token, "and")) { + op = DAVQL_LAND; + } else if (tokenvalue_is(token, "or")) { + op = DAVQL_LOR; + } else if (tokenvalue_is(token, "xor")) { + op = DAVQL_LXOR; + } + + if (op == DAVQL_NOOP) { + dav_error_in_context(DAVQL_ERROR_INVALID_LOGICAL_OP, + _error_invalid_logical_op, stmt, token); + return 0; + } else { + expr->op = op; + total_consumed++; + token = token->next; + + memset(&right, 0, sizeof(DavQLExpression)); + consumed = dav_parse_logical_expr(stmt, token, &right); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, + _error_missing_expr, stmt, token); + return 0; + } + total_consumed += consumed; + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + + dqlsec_malloc(stmt, expr->left, DavQLExpression); + memcpy(expr->left, &left, sizeof(DavQLExpression)); + dqlsec_malloc(stmt, expr->right, DavQLExpression); + memcpy(expr->right, &right, sizeof(DavQLExpression)); + } + } else { + memcpy(expr, &left, sizeof(DavQLExpression)); + } + + // set type and recover source text + if (total_consumed > 0) { + expr->srctext.ptr = token_sstr(firsttoken).ptr; + cxstring lasttok = token_sstr((DavQLToken*)cx_linked_list_at(firsttoken, 0, offsetof(DavQLToken, next), total_consumed-1)); + expr->srctext.length = lasttok.ptr-expr->srctext.ptr+lasttok.length; + } + + return total_consumed; +} + +static int dav_parse_where_clause(DavQLStatement *stmt, DavQLToken *token) { + dqlsec_mallocz(stmt, stmt->where, DavQLExpression); + + return dav_parse_logical_expr(stmt, token, stmt->where); +} + +static int dav_parse_with_clause(DavQLStatement *stmt, DavQLToken *token) { + + int total_consumed = 0; + + // RULE: "depth", "=", (Number | "infinity") + if (tokenvalue_is(token, "depth")) { + token = token->next; total_consumed++; + if (tokenvalue_is(token, "=")) { + token = token->next; total_consumed++; + if (tokenvalue_is(token, "infinity")) { + stmt->depth = DAV_DEPTH_INFINITY; + token = token->next; total_consumed++; + } else { + DavQLExpression *depthexpr; + dqlsec_mallocz(stmt, depthexpr, DavQLExpression); + + int consumed = dav_parse_expression(stmt, token, depthexpr); + + if (consumed) { + if (depthexpr->type == DAVQL_NUMBER) { + if (depthexpr->srctext.ptr[0] == '%') { + stmt->depth = DAV_DEPTH_PLACEHOLDER; + } else { + cxstring depthstr = depthexpr->srctext; + char *conv = malloc(depthstr.length+1); + if (!conv) { + dav_free_expression(depthexpr); + stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; + return 0; + } + char *chk; + memcpy(conv, depthstr.ptr, depthstr.length); + conv[depthstr.length] = '\0'; + stmt->depth = strtol(conv, &chk, 10); + if (*chk || stmt->depth < -1) { + dav_error_in_context(DAVQL_ERROR_INVALID_DEPTH, + _error_invalid_depth, stmt, token); + } + free(conv); + } + total_consumed += consumed; + } else { + dav_error_in_context(DAVQL_ERROR_INVALID_DEPTH, + _error_invalid_depth, stmt, token); + } + } + + dav_free_expression(depthexpr); + } + } + } + + return total_consumed; +} + +static int dav_parse_order_crit(DavQLStatement *stmt, DavQLToken *token, + DavQLOrderCriterion *crit) { + + // RULE: (Identifier | Number), [" asc"|" desc"]; + DavQLExpression expr; + memset(&expr, 0, sizeof(DavQLExpression)); + int consumed = dav_parse_expression(stmt, token, &expr); + if (stmt->errorcode || !consumed) { + return 0; + } + + if (expr.type != DAVQL_IDENTIFIER && expr.type != DAVQL_NUMBER) { + dav_error_in_context(DAVQL_ERROR_INVALID_ORDER_CRITERION, + _error_invalid_order_criterion, stmt, token); + return 0; + } + + dqlsec_malloc(stmt, crit->column, DavQLExpression); + memcpy(crit->column, &expr, sizeof(DavQLExpression)); + + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + if (token_is(token, DAVQL_TOKEN_KEYWORD) && ( + tokenvalue_is(token, "asc") || tokenvalue_is(token, "desc"))) { + + crit->descending = tokenvalue_is(token, "desc"); + + return consumed+1; + } else { + crit->descending = 0; + return consumed; + } +} + +static int dav_parse_orderby_clause(DavQLStatement *stmt, DavQLToken *token) { + + int total_consumed = 0, consumed; + + DavQLOrderCriterion crit; + + if(!stmt->orderby) { + stmt->orderby = cxLinkedListCreateSimple(sizeof(DavQLOrderCriterion)); + if(!stmt->orderby) { + return 0; + } + } + + // RULE: OrderByCriterion, {",", OrderByCriterion}; + do { + consumed = dav_parse_order_crit(stmt, token, &crit); + if (stmt->errorcode) { + return 0; + } + if (!consumed) { + dav_error_in_context(DAVQL_ERROR_MISSING_EXPR, _error_missing_expr, + stmt, token); + return 0; + } + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + + if(cxListAdd(stmt->orderby, &crit)) { + stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; + return 0; + } + + if (token_is(token, DAVQL_TOKEN_COMMA)) { + total_consumed++; + token = token->next; + } else { + consumed = 0; + } + } while (consumed); + + return total_consumed; +} + + +static int dav_parse_assignments(DavQLStatement *stmt, DavQLToken *token) { + + // RULE: Assignment, {",", Assignment} + int total_consumed = 0, consumed; + do { + // RULE: Identifier, "=", Expression + if (token_is(token, DAVQL_TOKEN_IDENTIFIER)) { + + // Identifier + DavQLField *field; + dqlsec_malloc(stmt, field, DavQLField); + field->name = token_sstr(token); + total_consumed++; + token = token->next; + + // "=" + if (!token_is(token, DAVQL_TOKEN_OPERATOR) + || !tokenvalue_is(token, "=")) { + dav_free_field(field); + + dav_error_in_context(DAVQL_ERROR_MISSING_ASSIGN, + _error_missing_assign, stmt, token); + return total_consumed; + } + total_consumed++; + token = token->next; + + // Expression + dqlsec_mallocz(stmt, field->expr, DavQLExpression); + consumed = dav_parse_expression(stmt, token, field->expr); + if (stmt->errorcode) { + dav_free_field(field); + return total_consumed; + } + token = cx_linked_list_at(token, 0, offsetof(DavQLToken, next), consumed); + total_consumed += consumed; + + // Add assignment to list and check if there's another one + if(dav_stmt_add_field(stmt, field)) { + free(field); + return 0; + } + consumed = token_is(token, DAVQL_TOKEN_COMMA) ? 1 : 0; + if (consumed) { + token = token->next; + total_consumed++; + } + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_identifier, stmt, token); + return total_consumed; + } + } while (consumed); + + return total_consumed; +} + +static int dav_parse_path(DavQLStatement *stmt, DavQLToken *tokens) { + if (token_is(tokens, DAVQL_TOKEN_STRING)) { + stmt->path = token_sstr(tokens); + tokens = tokens->next; + return 1; + } else if (token_is(tokens, DAVQL_TOKEN_OPERATOR) + && tokenvalue_is(tokens, "/")) { + stmt->path = token_sstr(tokens); + tokens = tokens->next; + int consumed = 1; + while (!token_is(tokens, DAVQL_TOKEN_KEYWORD) && + !token_is(tokens, DAVQL_TOKEN_END)) { + cxstring toksstr = token_sstr(tokens); + stmt->path.length = toksstr.ptr-stmt->path.ptr+toksstr.length; + tokens = tokens->next; + consumed++; + } + return consumed; + } else if (token_is(tokens, DAVQL_TOKEN_FMTSPEC) && + tokenvalue_is(tokens, "%s")) { + stmt->path = token_sstr(tokens); + tokens = tokens->next; + fmt_args_add(stmt, (void*)(intptr_t)'s'); + return 1; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_path, stmt, tokens); + return 0; + } +} + +/** + * Parser of a select statement. + * @param stmt the statement object that shall contain the syntax tree + * @param tokens the token list + */ +static void dav_parse_select_statement(DavQLStatement *stmt, DavQLToken *tokens) { + stmt->type = DAVQL_SELECT; + + // Consume field list + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_fieldlist(stmt, tokens)); + if (stmt->errorcode) { + return; + } + + // Consume FROM keyword + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "from")) { + tokens = tokens->next; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_from, stmt, tokens); + return; + } + + // Consume path + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_path(stmt, tokens)); + if (stmt->errorcode) { + return; + } + //dav_add_fmt_args(stmt, stmt->path); // add possible path args + + // Consume with clause (if any) + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "with")) { + tokens = tokens->next; + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), + dav_parse_with_clause(stmt, tokens)); + } + if (stmt->errorcode) { + return; + } + + // Consume where clause (if any) + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "where")) { + tokens = tokens->next; + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), + dav_parse_where_clause(stmt, tokens)); + } else if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "anywhere")) { + // useless, but the user may want to explicitly express his intent + tokens = tokens->next; + stmt->where = NULL; + } + if (stmt->errorcode) { + return; + } + + // Consume order by clause (if any) + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "order")) { + tokens = tokens->next; + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "by")) { + tokens = tokens->next; + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), + dav_parse_orderby_clause(stmt, tokens)); + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_by, stmt, tokens); + return; + } + } + if (stmt->errorcode) { + return; + } + + + if (tokens) { + if (token_is(tokens, DAVQL_TOKEN_INVALID)) { + dav_error_in_context(DAVQL_ERROR_INVALID_TOKEN, + _error_invalid_token, stmt, tokens); + } else if (!token_is(tokens, DAVQL_TOKEN_END)) { + dav_error_in_context(DAVQL_ERROR_UNEXPECTED_TOKEN, + _error_unexpected_token, stmt, tokens); + } + } +} + +static void dav_parse_set_statement(DavQLStatement *stmt, DavQLToken *tokens) { + stmt->type = DAVQL_SET; + + // Consume assignments + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_assignments(stmt, tokens)); + if (stmt->errorcode) { + return; + } + + // Consume AT keyword + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "at")) { + tokens = tokens->next; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_at, stmt, tokens); + return; + } + + // Consume path + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), dav_parse_path(stmt, tokens)); + if (stmt->errorcode) { + return; + } + + // Consume with clause (if any) + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "with")) { + tokens = tokens->next; + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), + dav_parse_with_clause(stmt, tokens)); + } + if (stmt->errorcode) { + return; + } + + // Consume mandatory where clause (or anywhere keyword) + if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "where")) { + tokens = tokens->next; + tokens = cx_linked_list_at(tokens, 0, offsetof(DavQLToken, next), + dav_parse_where_clause(stmt, tokens)); + } else if (token_is(tokens, DAVQL_TOKEN_KEYWORD) + && tokenvalue_is(tokens, "anywhere")) { + // no-op, but we want the user to be explicit about this + tokens = tokens->next; + stmt->where = NULL; + } else { + dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN, + _error_missing_where, stmt, tokens); + return; + } +} + +DavQLStatement* dav_parse_statement(cxstring srctext) { + DavQLStatement *stmt = calloc(1, sizeof(DavQLStatement)); + + // if we can't even get enough memory for the statement object or an error + // message, we can simply die without returning anything + if (!stmt) { + return NULL; + } + char *oommsg = strdup(_error_out_of_memory); + if (!oommsg) { + free(stmt); + return NULL; + } + + // default values + stmt->type = -1; + stmt->depth = 1; + + // save trimmed source text + stmt->srctext = cx_strtrim(srctext); + + if (stmt->srctext.length) { + // tokenization + DavQLToken* tokens = dav_parse_tokenize(stmt->srctext); + + if (tokens) { + // use first token to determine query type + + if (tokenvalue_is(tokens, "select")) { + dav_parse_select_statement(stmt, tokens->next); + } else if (tokenvalue_is(tokens, "set")) { + dav_parse_set_statement(stmt, tokens->next); + } else { + stmt->type = DAVQL_ERROR; + stmt->errorcode = DAVQL_ERROR_INVALID; + stmt->errormessage = strdup(_error_invalid); + } + + // free token data + tokenlist_free(tokens); + } else { + stmt->errorcode = DAVQL_ERROR_OUT_OF_MEMORY; + } + } else { + stmt->type = DAVQL_ERROR; + stmt->errorcode = DAVQL_ERROR_INVALID; + stmt->errormessage = strdup(_error_invalid); + } + + if (stmt->errorcode == DAVQL_ERROR_OUT_OF_MEMORY) { + stmt->type = DAVQL_ERROR; + stmt->errormessage = oommsg; + } else { + free(oommsg); + } + + return stmt; +} + +void dav_free_statement(DavQLStatement *stmt) { + if(stmt->fields) { + stmt->fields->simple_destructor = (cx_destructor_func)dav_free_field; + cxListDestroy(stmt->fields); + } + + if (stmt->where) { + dav_free_expression(stmt->where); + } + if (stmt->errormessage) { + free(stmt->errormessage); + } + + if(stmt->orderby) { + stmt->orderby->simple_destructor = (cx_destructor_func)dav_free_order_criterion; + cxListDestroy(stmt->orderby); + } + if(stmt->args) { + cxListDestroy(stmt->args); + } + free(stmt); +}