tip/libidav/davqlparser.h

/*
 * 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.
 */

#ifndef DAVQLPARSER_H
#define	DAVQLPARSER_H

#ifdef	__cplusplus
extern "C" {
#endif

#include <stdint.h>
#include <cx/string.h>
#include <cx/list.h>

/**
 * Enumeration of possible statement types.
 */
typedef enum {DAVQL_ERROR, DAVQL_SELECT, DAVQL_SET} davqltype_t;

/**
 * Enumeration of possible token classes.
 */
typedef enum {
    DAVQL_TOKEN_INVALID, DAVQL_TOKEN_KEYWORD,
    DAVQL_TOKEN_IDENTIFIER, DAVQL_TOKEN_FMTSPEC,
    DAVQL_TOKEN_STRING, DAVQL_TOKEN_NUMBER, DAVQL_TOKEN_TIMESTAMP,
    DAVQL_TOKEN_COMMA, DAVQL_TOKEN_OPENP, DAVQL_TOKEN_CLOSEP,
    DAVQL_TOKEN_OPERATOR, DAVQL_TOKEN_END
} davqltokenclass_t;

/**
 * Enumeration of possible expression types.
 */
typedef enum {
    DAVQL_UNDEFINED_TYPE,
    DAVQL_NUMBER, DAVQL_STRING, DAVQL_TIMESTAMP, DAVQL_IDENTIFIER,
    DAVQL_UNARY, DAVQL_BINARY, DAVQL_LOGICAL, DAVQL_FUNCCALL
} davqlexprtype_t;

/**
 * Enumeration of possible expression operators.
 */
typedef enum {
    DAVQL_NOOP, DAVQL_CALL, DAVQL_ARGLIST, // internal representations
    DAVQL_ADD, DAVQL_SUB, DAVQL_MUL, DAVQL_DIV,
    DAVQL_AND, DAVQL_OR, DAVQL_XOR, DAVQL_NEG,  // airthmetic
    DAVQL_NOT, DAVQL_LAND, DAVQL_LOR, DAVQL_LXOR, // logical
    DAVQL_EQ, DAVQL_NEQ, DAVQL_LT, DAVQL_GT, DAVQL_LE, DAVQL_GE,
    DAVQL_LIKE, DAVQL_UNLIKE // comparisons
} davqloperator_t;

typedef struct DavQLToken DavQLToken;    
struct DavQLToken {
    davqltokenclass_t tokenclass;
    cxstring value;
    DavQLToken *prev;
    DavQLToken *next;
};

/**
 * An expression within a DAVQL query.
 */
typedef struct _davqlexpr DavQLExpression;

/**
 * The structure for type DavQLExpression.
 */
struct _davqlexpr {
    /**
     * The original expression text.
     * Contains the literal value, if type is LITERAL.
     */
    cxstring srctext;
    /**
     * The expression type.
     */
    davqlexprtype_t type;
    /**
     * Operator.
     */
    davqloperator_t op;
    /**
     * Left or single operand.
     * <code>NULL</code> for literals or identifiers.
     */
    DavQLExpression *left;
    /**
     * Right operand.
     * <code>NULL</code> for literals, identifiers or unary expressions.
     */
    DavQLExpression *right;
};

/**
 * A tuple representing an order criterion.
 */
typedef struct {
    /**
     * The column.
     */
    DavQLExpression *column;
    /**
     * True, if the result shall be sorted descending, false otherwise.
     * Default is false (ascending).
     */
    _Bool descending;
} DavQLOrderCriterion;

/**
 * A tuple representing a field.
 */
typedef struct {
    /**
     * The field name.
     * <ul>
     * <li>SELECT: the identifier or an alias name</li>
     * <li>SET: the identifier</li>
     * </ul>
     */
    cxstring name;
    /**
     * The field expression.
     * <ul>
     * <li>SELECT: the queried property (identifier) or an expression</li>
     * <li>SET: the expression for the value to be set</li>
     * </ul>
     */
    DavQLExpression *expr;
} DavQLField;

/**
 * Query statement object.
 * Contains the binary information about the parsed query.
 * 
 * The grammar for a DavQLStatement is:
 * 
 * <pre>
 * Keyword = "select" | "set" | "from" | "at" | "as"
 *         | "where" | "anywhere" | "like" | "unlike"
 *         | "and" | "or" | "not" | "xor" | "with" | "infinity"
 *         | "order" | "by" | "asc" | "desc";
 * 
 * Expression        = AddExpression;
 * AddExpression     = MultExpression, [AddOperator, AddExpression];
 * MultExpression    = BitwiseExpression, [MultOperator, MultExpression];
 * BitwiseExpression = UnaryExpression, [BitwiseOperator, BitwiseExpression];
 * UnaryExpression   = [UnaryOperator], (ParExpression | AtomicExpression);
 * AtomicExpression  = FunctionCall | Identifier | Literal;
 * ParExpression     = "(", Expression, ")";
 * 
 * BitwiseOperator = "&" | "|" | "^";
 * MultOperator    = "*" | "/";
 * AddOperator     = "+" | "-";
 * UnaryOperator   = "+" | "-" | "~";
 * 
 * FunctionCall    = Identifier, "(", [ArgumentList], ")";
 * ArgumentList    = Expression, {",", Expression};
 * Identifier      = IdentifierChar - ?Digit?, {IdentifierChar}
 *                 | "`", ?Character? - "`", {?Character? - "`"}, "`";
 * IdentifierChar  = ?Character? - (" "|",");
 * Literal         = Number | String | Timestamp;
 * Number          = ?Digit?, {?Digit?} | "%d";
 * String          = "'", {?Character? - "'" | "'''"} , "'" | "%s";
 * Timestamp       = "%t"; // TODO: maybe introduce a real literal 
 * 
 * LogicalExpression = BooleanExpression, [LogicalOperator, LogicalExpression];
 * BooleanExpression = "not ", BooleanExpression
 *                   | "(", LogicalExpression, ")"
 *                   | BooleanPrimary;
 * BooleanPrimary    = Expression, (" like " | " unlike "), String
 *                   | Expression, Comparison, Expression
 *                   | FunctionCall | Identifier;
 * 
 * LogicalOperator = " and " | " or " | " xor ";
 * Comparison      = | "=" | "<" | ">" | "<=" | ">=" | "!=";
 * 
 * FieldExpressions = "-"
 *                  | "*", {",", NamedField}
 *                  | FieldExpression, {",", FieldExpression};
 * FieldExpression  = NamedField | Identifier;
 * NamedField       = Expression, " as ", Identifier;
 * 
 * Assignments   = Assignment, {",", Assignment};
 * Assignment    = Identifier, "=", Expression;
 * 
 * Path     = String
 *          | "/", [PathNode, {"/", PathNode}], ["/"];
 * PathNode = {{?Character? - "/"} - Keyword};
 * 
 * WithClause = "depth", "=", (Number | "infinity");
 * 
 * OrderByClause    = OrderByCriterion, {",", OrderByCriterion};
 * OrderByCriterion = (Identifier | Number), [" asc"|" desc"];
 * 
 * </pre>
 * 
 * Note: mandatory spaces are part of the grammar. But you may also insert an
 * arbitrary amount of optional spaces between two symbols if they are not part
 * of an literal, identifier or the path.
 * 
 * <b>SELECT:</b>
 * <pre>
 * SelectStatement = "select ", FieldExpressions,
 * " from ", Path,
 * [" with ", WithClause],
 * [(" where ", LogicalExpression) | " anywhere"],
 * [" order by ", OrderByClause];
  * </pre>
 * 
 * <b>SET:</b>
 * <pre>
 * SetStatement = "set ",Assignments,
 * " at ", Path,
 * [" with ", WithClause],
 * (" where ", LogicalExpression) | " anywhere";
 * </pre>
 * 
 */
typedef struct {
    /**
     * The original query text.
     */
    cxstring srctext;
    /**
     * The statement type.
     */
    davqltype_t type;
    /**
     * Error code, if any error occurred. Zero otherwise.
     */
    int errorcode;
    /**
     * Error message, if any error occurred.
     */
    char* errormessage;
    /**
     * The list of DavQLFields.
     */
    CxList* fields;
    /**
     * A string that denotes the queried path.
     */
    cxstring path;
    /**
     * Logical expression for selection.
     * <code>NULL</code>, if there is no where clause.
     */
    DavQLExpression* where;
    /**
     * The list of DavQLOrderCriterions.
     * This is <code>NULL</code> for SET queries and may be <code>NULL</code>
     * if the result doesn't need to be sorted.
     */
    CxList* orderby;
    /**
     * The recursion depth for the statement.
     * Defaults to 1.
     * Magic numbers are DAV_DEPTH_INFINITY for infinity and
     * DAV_DEPTH_PLACEHOLDER for a placeholder.
     */
    int depth;
    /**
     * A list of all required arguments
     */
    CxList* args;
} DavQLStatement;

/** Infinity recursion depth for a DavQLStatement. */
#define DAV_DEPTH_INFINITY -1

/** Depth needs to be specified at runtime. */
#define DAV_DEPTH_PLACEHOLDER -2

/** Unexpected token. */
#define DAVQL_ERROR_UNEXPECTED_TOKEN 1

/** A token has been found, for which no token class is applicable. */
#define DAVQL_ERROR_INVALID_TOKEN 2

/** A token that has been expected was not found. */
#define DAVQL_ERROR_MISSING_TOKEN 11

/** An expression has been expected, but was not found. */
#define DAVQL_ERROR_MISSING_EXPR 12

/** A closed parenthesis ')' is missing. */
#define DAVQL_ERROR_MISSING_PAR 13

/** An assignment operator '=' is missing. */
#define DAVQL_ERROR_MISSING_ASSIGN 14

/** The type of the expression could not be determined. */
#define DAVQL_ERROR_INVALID_EXPR 21

/** An operator has been found for an unary expression, but it is invalid. */
#define DAVQL_ERROR_INVALID_UNARY_OP 22

/** An operator has been found for a logical expression, but it is invalid. */
#define DAVQL_ERROR_INVALID_LOGICAL_OP 23

/** Invalid format specifier. */
#define DAVQL_ERROR_INVALID_FMTSPEC 24

/** A string has been expected. */
#define DAVQL_ERROR_INVALID_STRING 25

/** The order criterion is invalid (must be an identifier or field index). */
#define DAVQL_ERROR_INVALID_ORDER_CRITERION 26

/** The depth is invalid. */
#define DAVQL_ERROR_INVALID_DEPTH 101

/** Nothing about the statement seems legit. */
#define DAVQL_ERROR_INVALID -1

/** A call to malloc or calloc failed. */
#define DAVQL_ERROR_OUT_OF_MEMORY -2

/**
 * Starts an interactive debugger for a DavQLStatement.
 * 
 * @param stmt the statement to debug
 */
void dav_debug_statement(DavQLStatement *stmt);

/**
 * Parses a statement.
 * @param stmt the sstr_t containing the statement
 * @return a DavQLStatement object
 */
DavQLStatement* dav_parse_statement(cxstring stmt);

/**
 * Implicitly converts a cstr to a sstr_t and calls dav_parse_statement.
 */
#define dav_parse_cstr_statement(stmt) dav_parse_statement(cx_str(stmt))

/**
 * Frees a DavQLStatement.
 * @param stmt the statement object to free
 */
void dav_free_statement(DavQLStatement *stmt);

#ifdef	__cplusplus
}
#endif

#endif	/* DAVQLPARSER_H */