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_LITERAL: return "LITERAL";
    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_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_stmt_print(DavQLStatement *stmt) {
    // Basic information
    size_t fieldcount = ucx_list_size(stmt->fields);
    int specialfield = 0;
    UCX_FOREACH(elm, stmt->fields) {
        DavQLExpression* expr = (DavQLExpression*)elm->data;
        if (expr->type == DAVQL_IDENTIFIER && expr->srctext.length == 1) {
            if (expr->srctext.ptr[0] == '*') {
                specialfield = 1;
            } else if (expr->srctext.ptr[0] == '-') {
                specialfield = 2;
            }
        }
    }
    if (specialfield) {
        fieldcount--;
    }
    printf("Statement: %.*s\nType: %s\nField count: %zu %s\nPath: %.*s\n"
        "Has where clause: %s\n",
        sfmtarg(stmt->srctext),
        _map_querytype(stmt->type),
        fieldcount,
        _map_specialfield(specialfield),
        sfmtarg(stmt->path),
        stmt->where ? "yes" : "no");
    if (stmt->type == DAVQL_SET) {
        printf("Value list size matches: %s",
            ucx_list_size(stmt->fields) == ucx_list_size(stmt->setvalues)
            ? "yes" : "no");
    }
    
    // WITH attributes
    if (stmt->depth < 0) {
        printf("Depth: infinity\n");
    } else {
        printf("Depth: %d\n", stmt->depth);
    }
    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"
            "Left hand: %.*s\nRight hand: %.*s\n",
            sfmtarg(expr->srctext),
            _map_exprtype(expr->type),
            _map_operator(expr->op),
            sfmtarg(expr->left?expr->left->srctext:empty),
            sfmtarg(expr->right?expr->right->srctext:empty));
    }
}

#define DQLD_CMD_Q     0
#define DQLD_CMD_PS    1
#define DQLD_CMD_PE    2
#define DQLD_CMD_P    10
#define DQLD_CMD_L    21
#define DQLD_CMD_R    22
#define DQLD_CMD_H   100

static int dav_debug_ql_command() {
    printf("> ");
    
    char buffer[16];
    fgets(buffer, 16, stdin);
    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, "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 {
        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;
    
    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_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"
                "q:   quit\n\n"
                "\nExpression examination:\n"
                "pe:  print expression information\n"
                "l:   enter left subtree\n"
                "r:   enter right subtree\n");
            break;
        default: printf("unknown command\n");
        }
    }
}

// ------------------------------------------------------------------------
//                         P A R S E R
// ------------------------------------------------------------------------

#define _unexpected_end_msg "unexpected end of statement"
#define _invalid_msg "invalid statement"
#define _unexpected_token "unexpected token (%.*s [->]%.*s %.*s)"
#define _expected_token "expected token '%s' before '%.*s'"
#define _expected_by "expected 'by' after 'order' (order [->]%.*s)"
#define _missing_quote "missing closing quote symbol (%.*s)"
#define _parser_state "parser reached invalid state"
#define _unknown_attribute "unknown attribute '%.*s'"
#define _duplicated_attribute "duplicated attribute '%.*s'"
#define _invalid_depth "invalid depth"
#define _identifier_expected "identifier expected, but found: %.*s"

static const char *special_token_symbols = ",()+-*/&|^~=!<>";

static UcxList* dav_parse_tokenize(sstr_t src) {
    UcxList *tokens = NULL;
    
    sstr_t *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->length++;
                tokens = ucx_list_append(tokens, token);
                token = NULL;
                insequence = '\0';
            } else if (insequence == '\0') {
                insequence = src.ptr[i];
                // always create new token for quoted strings
                if (token) {
                    tokens = ucx_list_append(tokens, token);
                }
                token = malloc(sizeof(sstr_t));
                token->ptr = src.ptr + i;
                token->length = 1;
            } else {
                // add other kind of quotes to token
                token->length++;
            }
        } else if (insequence) {
            token->length++;
        } else if (isspace(src.ptr[i])) {
            // add token before spaces to list (if any)
            if (token) {
                tokens = ucx_list_append(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 = ucx_list_append(tokens, token);
                token = NULL;
            }
            // add special symbol as single token to list
            token = malloc(sizeof(sstr_t));
            token->ptr = src.ptr + i;
            token->length = 1;
            tokens = ucx_list_append(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(sstr_t));
                token->ptr = src.ptr + i;
                token->length = 0;
            }
            // extend token length when reading more bytes
            token->length++;
        }
    }
    
    if (token) {
        tokens = ucx_list_append(tokens, token);
    }
    
    return tokens;
}

#define token_sstr(listelem) ((sstr_t*)(listelem)->data)
static DavQLExpression* dav_parse_expression(
        DavQLStatement* stmt, UcxList* starttoken, size_t n) {
    if (n == 0) {
        return NULL;
    }
    
    DavQLExpression *expr = calloc(1, sizeof(DavQLExpression));
    
    // set pointer for source text
    expr->srctext.ptr = token_sstr(starttoken)->ptr;
    
    // special case - only one token
    if (n == 1) {
        expr->srctext.length = token_sstr(starttoken)->length;
        char firstchar = expr->srctext.ptr[0];
        char lastchar = expr->srctext.ptr[expr->srctext.length-1];
        if (firstchar == '\'' || isdigit(firstchar)) {
            expr->type = DAVQL_LITERAL;
        } else {
            expr->type = DAVQL_IDENTIFIER;
        }
        // remove quotes (if any)
        if (firstchar == '\'' || firstchar == '`') {
            if (lastchar != firstchar) {
                stmt->errorcode = DAVQL_ERROR_MISSING_QUOTE;
                stmt->errormessage =
                    ucx_sprintf(_missing_quote, sfmtarg(expr->srctext)).ptr;
            }
            expr->srctext.ptr++;
            if (expr->srctext.length > 2) {
                expr->srctext.length -= 2;
            } else {
                expr->srctext.length = 0;
            }
        }
    } else {
        UcxList* token = starttoken;
        
        // check, if first token is (
        // if so, verify that last token is ) and throw both away
        if (!sstrcmp(*token_sstr(token), S("("))) {
            if (!sstrcmp(*token_sstr(ucx_list_get(token, n-1)), S(")"))) {
                token = token->next;
                n -= 2;
            } else {
                // TODO: throw syntax error
            }
        }

        // process tokens        
        for (size_t i = 0 ; i < n ; i++) {
            
            // TODO: make it so

            // go to next token (if this is not the last token)
            if (i < n-1) {
                token = token->next;
            }
        }

        // compute length of source text (including delimiters)
        expr->srctext.length = token_sstr(token)->ptr +
            token_sstr(token)->length - expr->srctext.ptr;
    }
    
    return expr;
}

static void dav_free_expression(DavQLExpression *expr) {
    if (expr->left) {
        dav_free_expression(expr->left);
    }
    if (expr->right) {
        dav_free_expression(expr->right);
    }
    free(expr);
}

static void dav_parse_unexpected_token(DavQLStatement *stmt, UcxList *token) {
    sstr_t emptystring = ST("");
    stmt->errorcode = DAVQL_ERROR_UNEXPECTED_TOKEN;
    sstr_t errormsg = ucx_sprintf(_unexpected_token,
        sfmtarg(token->prev?*token_sstr(token->prev):emptystring),
        sfmtarg(*token_sstr(token)),
        sfmtarg(token->next?*token_sstr(token->next):emptystring));
    stmt->errormessage = errormsg.ptr;
}

static int dav_parse_with_clause(DavQLStatement *stmt, UcxList *token) {
    sstr_t tokendata = *token_sstr(token);
    /*
     * 0: key
     * 1: =
     * 2: value
     * TODO: commas
     */
    static int parsestate = 0;

    /*
     * 1: depth
     */
    static int key = 0;
    static int keymask = 0;

    switch (parsestate) {
    case 0:
        if (!sstrcasecmp(tokendata, S("depth"))) {
            key = 1;
            parsestate = 1;
        } else {
            stmt->errorcode = DAVQL_ERROR_UNKNOWN_ATTRIBUTE;
            stmt->errormessage = ucx_sprintf(_unknown_attribute,
                sfmtarg(tokendata)).ptr;
            break;
        }
        if (keymask & key) {
            stmt->errorcode = DAVQL_ERROR_DUPLICATED_ATTRIBUTE;
            stmt->errormessage = ucx_sprintf(_duplicated_attribute,
                sfmtarg(tokendata)).ptr;
        } else {
            keymask |= key;
        }
        return 0;
    case 1:
        if (sstrcmp(tokendata, S("="))) {
            stmt->errorcode = DAVQL_ERROR_UNEXPECTED_TOKEN;
            stmt->errormessage = ucx_sprintf(_expected_token,
                "=", sfmtarg(tokendata)).ptr;
        } else {
            parsestate = 2;
        }
        return 0;
    case 2:
        switch (key) {
        case 1: /* depth */
            if (!sstrcasecmp(tokendata, S("infinity"))) {
                stmt->depth = DAV_DEPTH_INFINITY;
            } else {
                char *conv = malloc(tokendata.length+1);
                char *chk;
                memcpy(conv, tokendata.ptr, tokendata.length);
                conv[tokendata.length] = '\0';
                stmt->depth = strtol(conv, &chk, 10);
                if (*chk || stmt->depth < -1) {
                    stmt->errorcode = DAVQL_ERROR_INVALID_DEPTH;
                    stmt->errormessage = strdup(_invalid_depth);
                }
                free(conv);
            }
            break;
        }
        parsestate = 0;
        return 1;
    default:
        return -1;
    }
}

static void dav_parse_get_statement(DavQLStatement *stmt, UcxList *tokens) {
    stmt->type = DAVQL_GET;
    
#define _step_fieldlist_    10 // field list
#define _step_FROM_         20 // FROM clause
#define _step_expect_WWO_  530 // expecting WITH, WHERE or ORDER BY clause
#define _step_comma_WITH_  531 // expecting comma for WITH clause
#define _step_WITH_         30 // WITH clause
#define _step_expect_WO    540 // expecting WHERE or ORDER BY clause
#define _step_WHERE_        40 // WHERE clause
#define _step_expect_O     550 // expecting ORDER BY clause
#define _step_expect_BY    551 // expecting the BY token for the ORDER BY clause
#define _step_ORDER_BY_     50 // ORDER BY clause
#define _step_end_         500 // expect end

    int step = _step_fieldlist_;
    
    // Variables for token sublists for expressions
    UcxList *exprstart = NULL;
    size_t exprlen = 0;
    
    // Process tokens
    UCX_FOREACH(token, tokens) {
        if (stmt->errorcode) {
            ultrabreak: break;
        }
        
        sstr_t tokendata = *token_sstr(token);
        
        switch (step) {
        // too much input data
        case _step_end_:
            dav_parse_unexpected_token(stmt, token);
            goto ultrabreak;
        // optional clauses
        case _step_expect_WWO_:
            if (!sstrcasecmp(tokendata, S("with"))) {
                step = _step_WITH_;
                continue;
            }
            /* no break and no else*/
        case _step_expect_WO:
            if (!sstrcasecmp(tokendata, S("where"))) {
                step = _step_WHERE_;
                continue;
            }
            /* no break and no else*/
        case _step_expect_O:
            if (!sstrcasecmp(tokendata, S("order"))) {
                step = _step_expect_BY;
                continue;
            } else { // last possible clause checked and not present
                dav_parse_unexpected_token(stmt, token);
                goto ultrabreak;
            }
            break;
        case _step_expect_BY:
            if (!sstrcasecmp(tokendata, S("by"))) {
                step = _step_ORDER_BY_;
            } else {
                stmt->errorcode = DAVQL_ERROR_UNEXPECTED_TOKEN;
                stmt->errormessage = ucx_sprintf(_expected_by,
                    sfmtarg(tokendata)).ptr;
                goto ultrabreak;
            }
            break;
        case _step_comma_WITH_:
            // a with clause may be continued with a comma
            // or another clause may follow
            if (!sstrcmp(tokendata, S(","))) {
                step = _step_WITH_;
            } if (!sstrcasecmp(tokendata, S("where"))) {
                step = _step_WHERE_;
            } else if (!sstrcasecmp(tokendata, S("order"))) {
                step = _step_expect_BY;
            } else {
                dav_parse_unexpected_token(stmt, token);
                goto ultrabreak;
            }
            break;
        // field list
        case _step_fieldlist_: {
            _Bool fromkeyword = !sstrcasecmp(tokendata, S("from"));
            if (fromkeyword || !sstrcmp(tokendata, S(","))) {
                if (exprstart) {
                    stmt->fields = ucx_list_append(stmt->fields,
                        dav_parse_expression(stmt, exprstart, exprlen));
                    exprstart = NULL;
                    exprlen = 0;
                } else {
                    dav_parse_unexpected_token(stmt, token);
                    goto ultrabreak;
                }
                
                if (fromkeyword) {
                    step = _step_FROM_;
                }
            } else {
                // collect tokens for field expression
                if (exprstart) {
                    exprlen++;
                } else {
                    exprstart = token;
                    exprlen = 1;
                }
            }
            break;
        }
        // from clause
        case _step_FROM_: {
            DavQLExpression *expr = dav_parse_expression(stmt, token, 1);
            stmt->path = expr->srctext;
            int exprtype = expr->type;
            dav_free_expression(expr);
            if (exprtype != DAVQL_IDENTIFIER) {
                stmt->errorcode = DAVQL_ERROR_IDENTIFIER_EXPECTED;
                stmt->errormessage = ucx_sprintf(_identifier_expected,
                    sfmtarg(tokendata)).ptr;
            }
            step = _step_expect_WWO_;
            break;
        }
        // with clause
        case _step_WITH_: {
            int withclause_result = dav_parse_with_clause(stmt, token);
            if (withclause_result < 0) {
                stmt->errorcode = DAVQL_ERROR_INVALID;
                stmt->errormessage = strdup(_parser_state);
            } else if (withclause_result > 0) {
                step = _step_comma_WITH_;
            }
            break;
        }
        // where clause
        case _step_WHERE_:
            // TODO: implement
            step = _step_end_;
            break;
        // order by clause
        case _step_ORDER_BY_:
            // TODO: implement
            step = _step_end_;
            break;
        default:
            stmt->errorcode = DAVQL_ERROR_INVALID;
            stmt->errormessage = strdup(_parser_state);
        }
    }
    
    if (!stmt->errorcode && step < _step_end_) {
        stmt->errorcode = DAVQL_ERROR_UNEXPECTED_END;
        stmt->errormessage = strdup(_unexpected_end_msg);
    }
}

static void dav_parse_set_statement(DavQLStatement *stmt, UcxList *tokens) {
    stmt->type = DAVQL_SET;
    
    UCX_FOREACH(token, tokens) {
        sstr_t tokendata = *token_sstr(token);
        
    }
}

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
        sstr_t token = *token_sstr(tokens);
        free(tokens->data);
        tokens = ucx_list_remove(tokens, tokens);
        
        if (!sstrcasecmp(token, S("get"))) {
            dav_parse_get_statement(stmt, tokens);
        } else if (!sstrcasecmp(token, S("set"))) {
            dav_parse_set_statement(stmt, tokens);
        } else {
            stmt->type = DAVQL_ERROR;
            stmt->errorcode = DAVQL_ERROR_INVALID;
            stmt->errormessage = strdup(_invalid_msg);
        }
        
        // 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(_invalid_msg);
    }
    
    return stmt;
}

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