libidav/davqlparser.c

/*
 * 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 <cx/utils.h>
#include <cx/linked_list.h>
#include <cx/printf.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>

#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 ? cxListSize(stmt->fields) : 0;
    int specialfield = 0;
    if (fieldcount > 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 < cxListSize(stmt->orderby) ? ", " : "\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 && cxListSize(stmt->fields) > 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 && cxListSize(stmt->orderby) > 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 <identifier>') " _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;i<str.length;i++) {
        char c = str.ptr[i];
        if (placeholder) {
            if (c != '%') {
                fmt_args_add(stmt, (void*)(intptr_t)c);
            }
            placeholder = 0;
        } else if (c == '%') {
            placeholder = 1;
        }
    }
}

static int dav_parse_literal(DavQLStatement* stmt, DavQLToken* token,
        DavQLExpression* expr) {
    
    expr->srctext = 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 *add_field;
                    dqlsec_malloc(stmt, add_field, DavQLField);
                    memcpy(add_field, &localfield, sizeof(DavQLField));
                    if(dav_stmt_add_field(stmt, add_field)) {
                        free(add_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) {
        cxDefineDestructor(stmt->fields, dav_free_field);
        cxListDestroy(stmt->fields);
    }
    
    if (stmt->where) {
        dav_free_expression(stmt->where);
    }
    if (stmt->errormessage) {
        free(stmt->errormessage);
    }
    
    if(stmt->orderby) {
        cxDefineDestructor(stmt->orderby, dav_free_order_criterion);
        cxListDestroy(stmt->orderby);
    }
    if(stmt->args) {
        cxListDestroy(stmt->args);
    }
    free(stmt);
}