libidav/davqlparser.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2015 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 <ucx/utils.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_GET: return "GET";
    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: ");
        UCX_FOREACH(field, stmt->fields) {
            DavQLField *f = field->data;
            printf("%.*s, ", sfmtarg(f->name));
        }
        printf("\b\b  \b\b\n");
    }
}

static void dav_debug_ql_stmt_print(DavQLStatement *stmt) {
    // Basic information
    size_t fieldcount = ucx_list_size(stmt->fields);
    int specialfield = 0;
    if (stmt->fields) {
        DavQLField* firstfield = (DavQLField*)stmt->fields->data;
        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",
        sfmtarg(stmt->srctext),
        _map_querytype(stmt->type),
        fieldcount,
        _map_specialfield(specialfield));
    
    dav_debug_ql_fnames_print(stmt);
    printf("Path: %.*s\nHas where clause: %s\n",
        sfmtarg(stmt->path),
        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) {
        UCX_FOREACH(crit, stmt->orderby) {
            DavQLOrderCriterion *critdata = crit->data;
            printf("%.*s %s%s", sfmtarg(critdata->column->srctext),
                critdata->descending ? "desc" : "asc",
                crit->next ? ", " : "\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)) {
        sstr_t empty = ST("(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_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;
    UcxList *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:
            if (examineclause != DQLD_CMD_F) {
                examineclause = DQLD_CMD_F;
                examineelem = stmt->fields;
                examineexpr = stmt->fields ?
                    ((DavQLField*)stmt->fields->data)->expr : NULL;
                dav_debug_ql_expr_print(examineexpr);
            }
            break;
        case DQLD_CMD_W:
            examineclause = 0; examineelem = NULL;
            examineexpr = stmt->where;
            dav_debug_ql_expr_print(examineexpr);
            break;
        case DQLD_CMD_O:
            if (examineclause != DQLD_CMD_O) {
                examineclause = DQLD_CMD_O;
                examineelem = stmt->orderby;
                examineexpr = stmt->orderby ?
                    ((DavQLOrderCriterion*)stmt->orderby->data)->column : NULL;
                dav_debug_ql_expr_print(examineexpr);
            }
            break;
        case DQLD_CMD_N:
        case DQLD_CMD_P:
            if (examineelem) {
                UcxList *newelem = (cmd == DQLD_CMD_N ?
                    examineelem->next : examineelem->prev);
                if (newelem) {
                    examineelem = newelem;
                    if (examineclause == DQLD_CMD_O) {
                        examineexpr = ((DavQLOrderCriterion*)
                            examineelem->data)->column;
                    } else if (examineclause == DQLD_CMD_F) {
                        examineexpr = ((DavQLField*)examineelem->data)->expr;
                    } else {
                        printf("Examining unknown clause type.");
                    }
                    dav_debug_ql_expr_print(examineexpr);
                } 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_unhandled "unhandled error " _error_context
#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_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_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_fmtspec "invalid format specifier " _error_context

#define token_sstr(token) (((DavQLToken*)(token)->data)->value)

static void dav_error_in_context(int errorcode, const char *errormsg,
        DavQLStatement *stmt, UcxList *token) {
    
    // we try to achieve two things: get as many information as possible
    // and recover the concrete source string (and not the token strings)
    sstr_t emptystring = ST("");
    sstr_t prev = token->prev ? (token->prev->prev ?
        token_sstr(token->prev->prev) : token_sstr(token->prev))
        : emptystring;
    sstr_t tokenstr = token_sstr(token);
    sstr_t 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;
    char *pn = tokenstr.ptr + tokenstr.length;
    int ln = next.ptr+next.length - pn;
    
    stmt->errorcode = errorcode;
    stmt->errormessage = ucx_sprintf(errormsg,
        lp, prev.ptr,
        sfmtarg(tokenstr),
        ln, pn).ptr;
}

// special symbols are single tokens - the % sign MUST NOT be a special symbol
static const char *special_token_symbols = ",()+-*/&|^~=!<>";

static _Bool iskeyword(DavQLToken *token) {
    sstr_t keywords[] = {ST("get"), ST("set"), ST("from"), ST("at"), ST("as"),
        ST("where"), ST("with"), ST("order"), ST("by"), ST("asc"), ST("desc")
    };
    for (int i = 0 ; i < sizeof(keywords)/sizeof(sstr_t) ; i++) {
        if (!sstrcasecmp(token->value, keywords[i])) {
            return 1;
        }
    }
    return 0;
}

static UcxList* dav_parse_add_token(UcxList *tokenlist, 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;
    } 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;
        case '=': token->tokenclass = DAVQL_TOKEN_EQ; break;
        case '<': token->tokenclass = DAVQL_TOKEN_LT; break;
        case '>': token->tokenclass = DAVQL_TOKEN_GT; break;
        case '!': token->tokenclass = DAVQL_TOKEN_EXCLAIM; break;
        default:
            token->tokenclass = strchr(special_token_symbols, firstchar) ?
                DAVQL_TOKEN_OPERATOR : DAVQL_TOKEN_IDENTIFIER;
        }
    } 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;
    }
    
    // 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;
        }
    }
    
    
    return ucx_list_append(tokenlist, token);
}

static UcxList* dav_parse_tokenize(sstr_t src) {
    UcxList *tokens = 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) {
                // add quoted token to list
                token->value.length++;
                tokens = dav_parse_add_token(tokens, token);
                token = NULL;
                insequence = '\0';
            } else if (insequence == '\0') {
                insequence = src.ptr[i];
                // always create new token for quoted strings
                if (token) {
                    tokens = dav_parse_add_token(tokens, token);
                }
                token = malloc(sizeof(DavQLToken));
                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) {
                tokens = dav_parse_add_token(tokens, token);
                token = NULL;
            }
        } else if (strchr(special_token_symbols, src.ptr[i])) {
            // add token before special symbol to list (if any)
            if (token) {
                tokens = dav_parse_add_token(tokens, token);
                token = NULL;
            }
            // add special symbol as single token to list
            token = malloc(sizeof(DavQLToken));
            token->value.ptr = src.ptr + i;
            token->value.length = 1;
            tokens = dav_parse_add_token(tokens, token);
            // set tokenizer ready to read more tokens
            token = NULL;
        } else {
            // if this is a new token, create memory for it
            if (!token) {
                token = malloc(sizeof(DavQLToken));
                token->value.ptr = src.ptr + i;
                token->value.length = 0;
            }
            // extend token length when reading more bytes
            token->value.length++;
        }
    }
    
    if (token) {
        tokens = dav_parse_add_token(tokens, token);
    }
    
    return tokens;
}

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);
    }
    free(crit);
}

#define token_is(token, expectedclass) (token && \
    (((DavQLToken*)(token)->data)->tokenclass == expectedclass))

#define tokenvalue_is(token, expectedvalue) (token && \
    !sstrcasecmp(((DavQLToken*)(token)->data)->value, S(expectedvalue)))

typedef int(*exprparser_f)(DavQLStatement*,UcxList*,DavQLExpression*);

static int dav_parse_binary_expr(DavQLStatement* stmt, UcxList* 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 = ucx_list_get(token, 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 {
        expr->left = malloc(sizeof(DavQLExpression));
        memcpy(expr->left, &left, sizeof(DavQLExpression));
        expr->right = malloc(sizeof(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 int dav_parse_literal(DavQLStatement* stmt, UcxList* 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;
    } 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;
        }
    } else {
        return 0;
    }
    
    return 1;
}

// forward declaration
static int dav_parse_expression(DavQLStatement* stmt, UcxList* token,
        DavQLExpression* expr);

static int dav_parse_arglist(DavQLStatement* stmt, UcxList* 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;
    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 = ucx_list_get(token, 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
                 */
                arglist->left = malloc(sizeof(DavQLExpression));
                memcpy(arglist->left, &arg, sizeof(DavQLExpression));
                arglist->srctext.ptr = arg.srctext.ptr;
                arglist->op = DAVQL_ARGLIST;
                arglist->type = DAVQL_FUNCCALL;
                arglist->right = calloc(1, sizeof(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, UcxList* 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;
        
        expr->left = calloc(1, sizeof(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 = ucx_list_get(token, argtokens);
            expr->right = malloc(sizeof(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, UcxList* token,
        DavQLExpression* expr) {
    
    UcxList *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;
            }
            expr->left = calloc(1, sizeof(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 = ucx_list_get(token, 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) {
        sstr_t lasttoken =
            token_sstr(ucx_list_get(firsttoken, 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, UcxList* 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, UcxList* 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, UcxList* 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, UcxList *token,
        DavQLField *field) {
    int total_consumed = 0, consumed;
    
    // RULE:    Expression, " as ", Identifier;
    DavQLExpression *expr = calloc(1, sizeof(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 = ucx_list_get(token, 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, UcxList *token) {
    
    // RULE:    "-"
    if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "-")) {
        DavQLField *field = malloc(sizeof(DavQLField));
        field->expr = calloc(1, sizeof(DavQLExpression));
        field->expr->type = DAVQL_IDENTIFIER;
        field->expr->srctext = field->name = token_sstr(token);
        stmt->fields = ucx_list_append(stmt->fields, field);
        return 1;
    }
    
    // RULE:    "*", {",", NamedExpression}
    if (token_is(token, DAVQL_TOKEN_OPERATOR) && tokenvalue_is(token, "*")) {
        DavQLField *field = malloc(sizeof(DavQLField));
        field->expr = calloc(1, sizeof(DavQLExpression));
        field->expr->type = DAVQL_IDENTIFIER;
        field->expr->srctext = field->name = token_sstr(token);
        stmt->fields = ucx_list_append(stmt->fields, field);
        
        int total_consumed = 0;
        int consumed = 1;
        
        do {
            token = ucx_list_get(token, 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 = malloc(sizeof(DavQLField));
                    memcpy(field, &localfield, sizeof(DavQLField));
                    stmt->fields = ucx_list_append(stmt->fields, field);
                }                
            } 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 = malloc(sizeof(DavQLField));
                memcpy(field, &localfield, sizeof(DavQLField));
                stmt->fields = ucx_list_append(stmt->fields, field);
                token = ucx_list_get(token, 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 = malloc(sizeof(DavQLField));
                field->expr = calloc(1, sizeof(DavQLExpression));
                field->expr->type = DAVQL_IDENTIFIER;
                field->expr->srctext = field->name = token_sstr(token);
                stmt->fields = ucx_list_append(stmt->fields, field);

                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;
    }
}

static int dav_parse_where_clause(DavQLStatement *stmt, UcxList *token) {
    return 0;
}

static int dav_parse_with_clause(DavQLStatement *stmt, UcxList *token) {

    int total_consumed = 0;
    
    // RULE:    "depth", "=", (Number | "infinity")
    if (tokenvalue_is(token, "depth")) {
        token = token->next; total_consumed++;
        if (token_is(token, DAVQL_TOKEN_EQ)) {
            token = token->next; total_consumed++;
            if (tokenvalue_is(token, "infinity")) {
                stmt->depth = DAV_DEPTH_INFINITY;
                token = token->next; total_consumed++;
            } else {
                DavQLExpression *depthexpr = calloc(1, sizeof(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 {
                            sstr_t depthstr = depthexpr->srctext;
                            char *conv = malloc(depthstr.length+1);
                            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_orderby_clause(DavQLStatement *stmt, UcxList *token) {
    return 0;
}

/**
 * Semantic analysis of a get statement.
 * @param stmt the statement to analyze.
 */
static void dav_analyze_get_statement(DavQLStatement *stmt) {
    // TODO: make it so
}


/**
 * Parser of a get statement.
 * @param stmt the statement object that shall contain the syntax tree
 * @param tokens the token list
 */
static void dav_parse_get_statement(DavQLStatement *stmt, UcxList *tokens) {
    stmt->type = DAVQL_GET;

    // Consume field list
    tokens = ucx_list_get(tokens, 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
    if (token_is(tokens, DAVQL_TOKEN_STRING)) {
        stmt->path = token_sstr(tokens);
        tokens = tokens->next;
    } else if (token_is(tokens, DAVQL_TOKEN_OPERATOR)
            && tokenvalue_is(tokens, "/")) {
        stmt->path.ptr = token_sstr(tokens).ptr;
        tokens = tokens->next;
        while (!token_is(tokens, DAVQL_TOKEN_KEYWORD)) {
            sstr_t toksstr = token_sstr(tokens);
            stmt->path.length = toksstr.ptr-stmt->path.ptr+toksstr.length;
            tokens = tokens->next;
        }
    } else if (token_is(tokens, DAVQL_TOKEN_FMTSPEC) &&
            tokenvalue_is(tokens, "%s")) {
        stmt->path = token_sstr(tokens);
        tokens = tokens->next;
    } else {
        dav_error_in_context(DAVQL_ERROR_MISSING_TOKEN,
            _error_missing_path, stmt, tokens);
        return;
    }
    
    // Consume with clause (if any)
    if (token_is(tokens, DAVQL_TOKEN_KEYWORD)
            && tokenvalue_is(tokens, "with")) {
        tokens = tokens->next;
        tokens = ucx_list_get(tokens,
            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 = ucx_list_get(tokens,
            dav_parse_where_clause(stmt, tokens));
    }
    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 = ucx_list_get(tokens,
                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 {
            dav_error_in_context(DAVQL_ERROR_UNEXPECTED_TOKEN,
                _error_unexpected_token, stmt, tokens);
        }
    } else {
        dav_analyze_get_statement(stmt);
    }
}

static void dav_parse_set_statement(DavQLStatement *stmt, UcxList *tokens) {
    stmt->type = DAVQL_SET;
    
    // TODO: make it so
}

DavQLStatement* dav_parse_statement(sstr_t srctext) {
    DavQLStatement *stmt = calloc(1, sizeof(DavQLStatement));
    
    // default values
    stmt->type = -1;
    stmt->depth = 1;
    
    // save trimmed source text
    stmt->srctext = sstrtrim(srctext);
    
    // tokenization
    UcxList* tokens = dav_parse_tokenize(stmt->srctext);
    
    if (tokens) {
        // use first token to determine query type
        
        if (tokenvalue_is(tokens, "get")) {
            dav_parse_get_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
        UCX_FOREACH(token, tokens) {
            free(token->data);
        }
        ucx_list_free(tokens);
    } else {
        stmt->type = DAVQL_ERROR;
        stmt->errorcode = DAVQL_ERROR_INVALID;
        stmt->errormessage = strdup(_error_invalid);
    }
    
    return stmt;
}

void dav_free_statement(DavQLStatement *stmt) {
    UCX_FOREACH(expr, stmt->fields) {
        dav_free_field(expr->data);
    }
    ucx_list_free(stmt->fields);
    
    if (stmt->where) {
        dav_free_expression(stmt->where);
    }
    if (stmt->errormessage) {
        free(stmt->errormessage);
    }
    UCX_FOREACH(crit, stmt->orderby) {
        dav_free_order_criterion(crit->data);
    }
    ucx_list_free(stmt->orderby);
    free(stmt);
}