src/include/parser/ast.h

   1 /*
   2  * SysDB - src/include/parser/ast.h
   3  * Copyright (C) 2013-2015 Sebastian 'tokkee' Harl <sh@tokkee.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  16  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  17  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  18  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  19  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  20  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 /*
  29  * The SysDB query language AST describes the parse-tree of an SysQL query.
  30  */
  31
  32 #ifndef SDB_PARSER_AST_H
  33 #define SDB_PARSER_AST_H 1
  34
  35 #include "core/data.h"
  36 #include "core/time.h"
  37 #include "core/object.h"
  38
  39 #include <assert.h>
  40
  41 #ifdef __cplusplus
  42 extern "C" {
  43 #endif
  44
  45 /*
  46  * sdb_ast_node_type_t describes the type of an AST node.
  47  */
  48 typedef enum {
  49         /* command nodes */
  50         SDB_AST_TYPE_FETCH      = 1,
  51         SDB_AST_TYPE_LIST       = 2,
  52         SDB_AST_TYPE_LOOKUP     = 3,
  53         SDB_AST_TYPE_STORE      = 4,
  54         SDB_AST_TYPE_TIMESERIES = 5,
  55
  56         /* generic expressions */
  57         SDB_AST_TYPE_OPERATOR   = 100,
  58         SDB_AST_TYPE_ITERATOR   = 101,
  59
  60         /* values */
  61         SDB_AST_TYPE_CONST      = 200,
  62         SDB_AST_TYPE_VALUE      = 201,
  63
  64         SDB_AST_TYPE_TYPED      = 210,
  65 } sdb_ast_node_type_t;
  66
  67 /*
  68  * sdb_ast_operator_t describes the type of an operator.
  69  */
  70 typedef enum {
  71         /* logical and comparison operators */
  72 #define SDB_AST_IS_LOGICAL(n) \
  73         ((((n)->type == SDB_AST_TYPE_OPERATOR) \
  74                         && ((SDB_AST_AND <= SDB_AST_OP(n)->kind) \
  75                                 && (SDB_AST_OP(n)->kind <= SDB_AST_IN))) \
  76                 || (((n)->type == SDB_AST_TYPE_ITERATOR) \
  77                         && ((SDB_AST_ALL <= SDB_AST_ITER(n)->kind) \
  78                                 && (SDB_AST_ITER(n)->kind <= SDB_AST_ANY))))
  79         SDB_AST_AND     = 1000,
  80         SDB_AST_OR      = 1001,
  81         SDB_AST_NOT     = 1002,
  82
  83         SDB_AST_LT      = 1010,
  84         SDB_AST_LE      = 1011,
  85         SDB_AST_EQ      = 1012,
  86         SDB_AST_NE      = 1013,
  87         SDB_AST_GE      = 1014,
  88         SDB_AST_GT      = 1015,
  89         SDB_AST_REGEX   = 1016,
  90         SDB_AST_NREGEX  = 1017,
  91         SDB_AST_ISNULL  = 1018,
  92         SDB_AST_ISTRUE  = 1019,
  93         SDB_AST_ISFALSE = 1020,
  94         SDB_AST_IN      = 1021,
  95
  96         /* arithmetic expressions */
  97 #define SDB_AST_IS_ARITHMETIC(n) \
  98         (((n)->type == SDB_AST_TYPE_CONST) \
  99                 || ((n)->type == SDB_AST_TYPE_VALUE) \
 100                 || ((n)->type == SDB_AST_TYPE_TYPED) \
 101                 || (((n)->type == SDB_AST_TYPE_OPERATOR) \
 102                         && ((SDB_AST_ADD <= SDB_AST_OP(n)->kind) \
 103                                 && (SDB_AST_OP(n)->kind <= SDB_AST_CONCAT))))
 104         SDB_AST_ADD     = 2000,
 105         SDB_AST_SUB     = 2001,
 106         SDB_AST_MUL     = 2002,
 107         SDB_AST_DIV     = 2003,
 108         SDB_AST_MOD     = 2004,
 109         SDB_AST_CONCAT  = 2005,
 110
 111         /* iterators */
 112 #define SDB_AST_IS_ITERATOR(n) \
 113         (((n)->type == SDB_AST_TYPE_ITERATOR) \
 114                 && ((SDB_AST_ALL <= SDB_AST_ITER(n)->kind) \
 115                         && (SDB_AST_ITER(n)->kind <= SDB_AST_ANY)))
 116         SDB_AST_ALL     = 3000,
 117         SDB_AST_ANY     = 3001,
 118 } sdb_ast_operator_t;
 119
 120 #define SDB_AST_OP_TO_STRING(op) \
 121         (((op) == SDB_AST_AND) ? "AND" \
 122                 : ((op) == SDB_AST_OR) ? "OR" \
 123                 : ((op) == SDB_AST_NOT) ? "NOT" \
 124                 : ((op) == SDB_AST_LT) ? "LT" \
 125                 : ((op) == SDB_AST_LE) ? "LE" \
 126                 : ((op) == SDB_AST_EQ) ? "EQ" \
 127                 : ((op) == SDB_AST_NE) ? "NE" \
 128                 : ((op) == SDB_AST_GE) ? "GE" \
 129                 : ((op) == SDB_AST_GT) ? "GT" \
 130                 : ((op) == SDB_AST_REGEX) ? "REGEX" \
 131                 : ((op) == SDB_AST_NREGEX) ? "NREGEX" \
 132                 : ((op) == SDB_AST_ISNULL) ? "IS NULL" \
 133                 : ((op) == SDB_AST_ISTRUE) ? "IS TRUE" \
 134                 : ((op) == SDB_AST_ISFALSE) ? "IS FALSE" \
 135                 : ((op) == SDB_AST_IN) ? "IN" \
 136                 : ((op) == SDB_AST_ADD) ? "ADD" \
 137                 : ((op) == SDB_AST_SUB) ? "SUB" \
 138                 : ((op) == SDB_AST_MUL) ? "MUL" \
 139                 : ((op) == SDB_AST_DIV) ? "DIV" \
 140                 : ((op) == SDB_AST_MOD) ? "MOD" \
 141                 : ((op) == SDB_AST_CONCAT) ? "CONCAT" \
 142                 : ((op) == SDB_AST_ALL) ? "ALL" \
 143                 : ((op) == SDB_AST_ANY) ? "ANY" \
 144                 : "UNKNOWN")
 145
 146 #define SDB_AST_OP_TO_DATA_OP(op) \
 147         (((op) == SDB_AST_ADD) ? SDB_DATA_ADD \
 148                 : ((op) == SDB_AST_SUB) ? SDB_DATA_SUB \
 149                 : ((op) == SDB_AST_MUL) ? SDB_DATA_MUL \
 150                 : ((op) == SDB_AST_DIV) ? SDB_DATA_DIV \
 151                 : ((op) == SDB_AST_MOD) ? SDB_DATA_MOD \
 152                 : ((op) == SDB_AST_CONCAT) ? SDB_DATA_CONCAT \
 153                 : -1)
 154
 155 #define SDB_AST_TYPE_TO_STRING(n) \
 156         (((n)->type == SDB_AST_TYPE_FETCH) ? "FETCH" \
 157                 : ((n)->type == SDB_AST_TYPE_LIST) ? "LIST" \
 158                 : ((n)->type == SDB_AST_TYPE_LOOKUP) ? "LOOKUP" \
 159                 : ((n)->type == SDB_AST_TYPE_STORE) ? "STORE" \
 160                 : ((n)->type == SDB_AST_TYPE_TIMESERIES) ? "TIMESERIES" \
 161                 : ((n)->type == SDB_AST_TYPE_OPERATOR) \
 162                         ? SDB_AST_OP_TO_STRING(SDB_AST_OP(n)->kind) \
 163                 : ((n)->type == SDB_AST_TYPE_ITERATOR) ? "ITERATOR" \
 164                 : ((n)->type == SDB_AST_TYPE_CONST) ? "CONSTANT" \
 165                 : ((n)->type == SDB_AST_TYPE_VALUE) ? "VALUE" \
 166                 : ((n)->type == SDB_AST_TYPE_TYPED) ? "TYPED VALUE" \
 167                 : "UNKNOWN")
 168
 169 /*
 170  * sdb_ast_node_t is the interface for AST nodes. The first field of any
 171  * actual implementation of the interface is of type sdb_ast_node_t to
 172  * fascilitate casting between the interface and implementation types.
 173  *
 174  * It inherits from sdb_object_t and instances may safely be cast to a generic
 175  * object as well.
 176  */
 177 typedef struct {
 178         sdb_object_t super;
 179
 180         /* type describes the type of the actual node */
 181         int type;
 182
 183         /* data-type describes the type of the result value */
 184         int data_type;
 185 } sdb_ast_node_t;
 186 #define SDB_AST_NODE(obj) ((sdb_ast_node_t *)(obj))
 187
 188 /*
 189  * sdb_ast_op_t represents a simple operation.
 190  */
 191 typedef struct {
 192         sdb_ast_node_t super;
 193         int kind;
 194         /* left operand is NULL for unary expressions */
 195         sdb_ast_node_t *left;
 196         sdb_ast_node_t *right;
 197 } sdb_ast_op_t;
 198 #define SDB_AST_OP(obj) ((sdb_ast_op_t *)(obj))
 199 #define SDB_AST_OP_INIT \
 200         { { SDB_OBJECT_INIT, SDB_AST_TYPE_OPERATOR, -1 }, -1, NULL, NULL }
 201
 202 /*
 203  * sdb_ast_iter_t represents an iterator.
 204  */
 205 typedef struct {
 206         sdb_ast_node_t super;
 207         int kind;
 208         sdb_ast_node_t *iter;
 209         /* exactly one operand of the expression has to be unset and will be
 210          * filled in by the iterator value */
 211         sdb_ast_node_t *expr;
 212 } sdb_ast_iter_t;
 213 #define SDB_AST_ITER(obj) ((sdb_ast_iter_t *)(obj))
 214 #define SDB_AST_ITER_INIT \
 215         { { SDB_OBJECT_INIT, SDB_AST_TYPE_ITERATOR, -1 }, -1, NULL, NULL }
 216
 217 /*
 218  * sdb_ast_typed_t represents a typed value.
 219  */
 220 typedef struct {
 221         sdb_ast_node_t super;
 222         int type;
 223         sdb_ast_node_t *expr;
 224 } sdb_ast_typed_t;
 225 #define SDB_AST_TYPED(obj) ((sdb_ast_typed_t *)(obj))
 226 #define SDB_AST_TYPED_INIT \
 227         { { SDB_OBJECT_INIT, SDB_AST_TYPE_TYPED, -1 }, -1, NULL }
 228
 229 /*
 230  * sdb_ast_const_t represents a constant value.
 231  */
 232 typedef struct {
 233         sdb_ast_node_t super;
 234         sdb_data_t value;
 235 } sdb_ast_const_t;
 236 #define SDB_AST_CONST(obj) ((sdb_ast_const_t *)(obj))
 237 #define SDB_AST_CONST_INIT \
 238         { { SDB_OBJECT_INIT, SDB_AST_TYPE_CONST, -1 }, SDB_DATA_INIT }
 239
 240 /*
 241  * sdb_ast_value_t represents an object-specific value:
 242  * attributes, or field values.
 243  */
 244 typedef struct {
 245         sdb_ast_node_t super;
 246         int type; /* attribute or field */
 247         char *name; /* object name; optional */
 248 } sdb_ast_value_t;
 249 #define SDB_AST_VALUE(obj) ((sdb_ast_value_t *)(obj))
 250 #define SDB_AST_VALUE_INIT \
 251         { { SDB_OBJECT_INIT, SDB_AST_TYPE_VALUE, -1 }, -1, NULL }
 252
 253 /*
 254  * sdb_ast_fetch_t represents a FETCH command.
 255  */
 256 typedef struct {
 257         sdb_ast_node_t super;
 258         int obj_type;
 259         char *hostname; /* optional */
 260         int parent_type; /* optional */
 261         char *parent; /* optional */
 262         char *name;
 263         /* whether to include the full object, that is,
 264          * including all attributes and all children */
 265         bool full;
 266         sdb_ast_node_t *filter; /* optional */
 267 } sdb_ast_fetch_t;
 268 #define SDB_AST_FETCH(obj) ((sdb_ast_fetch_t *)(obj))
 269 #define SDB_AST_FETCH_INIT \
 270         { { SDB_OBJECT_INIT, SDB_AST_TYPE_FETCH, -1 }, -1, NULL, -1, NULL, NULL, 0, NULL }
 271
 272 /*
 273  * sdb_ast_list_t represents a LIST command.
 274  */
 275 typedef struct {
 276         sdb_ast_node_t super;
 277         int obj_type;
 278         sdb_ast_node_t *filter; /* optional */
 279 } sdb_ast_list_t;
 280 #define SDB_AST_LIST(obj) ((sdb_ast_list_t *)(obj))
 281 #define SDB_AST_LIST_INIT \
 282         { { SDB_OBJECT_INIT, SDB_AST_TYPE_LIST, -1 }, -1, NULL }
 283
 284 /*
 285  * sdb_ast_lookup_t represents a LOOKUP command.
 286  */
 287 typedef struct {
 288         sdb_ast_node_t super;
 289         int obj_type;
 290         sdb_ast_node_t *matcher; /* optional */
 291         sdb_ast_node_t *filter; /* optional */
 292 } sdb_ast_lookup_t;
 293 #define SDB_AST_LOOKUP(obj) ((sdb_ast_lookup_t *)(obj))
 294 #define SDB_AST_LOOKUP_INIT \
 295         { { SDB_OBJECT_INIT, SDB_AST_TYPE_LOOKUP, -1 }, -1, NULL, NULL }
 296
 297 /*
 298  * sdb_ast_store_t represents a STORE command.
 299  */
 300 typedef struct {
 301         sdb_ast_node_t super;
 302         int obj_type;
 303         char *hostname;  /* optional */
 304         int parent_type; /* optional */
 305         char *parent;    /* optional */
 306         char *name;
 307         sdb_time_t last_update;
 308
 309         /* metric specific */
 310         char *store_type;
 311         char *store_id;
 312         sdb_time_t store_last_update;
 313
 314         /* attribute specific */
 315         sdb_data_t value;
 316 } sdb_ast_store_t;
 317 #define SDB_AST_STORE(obj) ((sdb_ast_store_t *)(obj))
 318 #define SDB_AST_STORE_INIT \
 319         { { SDB_OBJECT_INIT, SDB_AST_TYPE_STORE, -1 }, \
 320                 -1, NULL, -1, NULL, NULL, 0, NULL, NULL, 0, SDB_DATA_INIT }
 321
 322 /*
 323  * sdb_ast_timeseries_t represents a TIMESERIES command.
 324  */
 325 typedef struct {
 326         sdb_ast_node_t super;
 327         char *hostname;
 328         char *metric;
 329         char **data_names;
 330         size_t data_names_len;
 331         sdb_time_t start;
 332         sdb_time_t end;
 333 } sdb_ast_timeseries_t;
 334 #define SDB_AST_TIMESERIES(obj) ((sdb_ast_timeseries_t *)(obj))
 335 #define SDB_AST_TIMESERIES_INIT \
 336         { { SDB_OBJECT_INIT, SDB_AST_TYPE_TIMESERIES, -1 }, NULL, NULL, NULL, 0, 0, 0 }
 337
 338 /*
 339  * AST constructors:
 340  * Newly created nodes take ownership of any dynamically allocated objects
 341  * (node objects, dynamically allocated constant values, strings). The memory
 342  * will be freed when destroying the node using sdb_object_deref.
 343  *
 344  * The constructors do not verify any arguments. The analyzer has to be used
 345  * for that purpose.
 346  */
 347
 348 /*
 349  * sdb_ast_op_create:
 350  * Creates an AST node representing a simple (ary or unary) operation. The
 351  * newly created node takes ownership of the left and right nodes.
 352  */
 353 sdb_ast_node_t *
 354 sdb_ast_op_create(int kind, sdb_ast_node_t *left, sdb_ast_node_t *right);
 355
 356 /*
 357  * sdb_ast_iter_create:
 358  * Creates an AST node representing an iterator. The newly created node takes
 359  * ownership of the iter and expr nodes.
 360  */
 361 sdb_ast_node_t *
 362 sdb_ast_iter_create(int kind, sdb_ast_node_t *iter, sdb_ast_node_t *expr);
 363
 364 /*
 365  * sdb_ast_typed_create:
 366  * Creates an AST node representing a typed expression. Thew newly created
 367  * node takes ownership of the expr node.
 368  */
 369 sdb_ast_node_t *
 370 sdb_ast_typed_create(int type, sdb_ast_node_t *expr);
 371
 372 /*
 373  * sdb_ast_const_create:
 374  * Creates an AST node representing a constant value. The newly created node
 375  * takes ownership of the value object.
 376  */
 377 sdb_ast_node_t *
 378 sdb_ast_const_create(sdb_data_t value);
 379
 380 /*
 381  * sdb_ast_value_create:
 382  * Creates an AST node representing an object-specific value (sibling nodes,
 383  * attributes, or field values). The newly created node takes ownership of the
 384  * string value.
 385  */
 386 sdb_ast_node_t *
 387 sdb_ast_value_create(int type, char *name);
 388
 389 /*
 390  * sdb_ast_fetch_create:
 391  * Creates an AST node representing a FETCH command. The newly created node
 392  * takes ownership of the strings and the filter node.
 393  */
 394 sdb_ast_node_t *
 395 sdb_ast_fetch_create(int obj_type, char *hostname,
 396                 int parent_type, char *parent, char *name,
 397                 bool full, sdb_ast_node_t *filter);
 398
 399 /*
 400  * sdb_ast_list_create:
 401  * Creates an AST node representing a LIST command. The newly created node
 402  * takes ownership of the filter node.
 403  */
 404 sdb_ast_node_t *
 405 sdb_ast_list_create(int obj_type, sdb_ast_node_t *filter);
 406
 407 /*
 408  * sdb_ast_lookup_create:
 409  * Creates an AST node representing a LOOKUP command. The newly created node
 410  * takes ownership of the matcher and filter nodes.
 411  */
 412 sdb_ast_node_t *
 413 sdb_ast_lookup_create(int obj_type, sdb_ast_node_t *matcher,
 414                 sdb_ast_node_t *filter);
 415
 416 /*
 417  * sdb_ast_store_create:
 418  * Creates an AST node representing a STORE command. Thew newly created node
 419  * takes ownership of all strings and the value object.
 420  */
 421 sdb_ast_node_t *
 422 sdb_ast_store_create(int obj_type, char *hostname,
 423                 int parent_type, char *parent, char *name, sdb_time_t last_update,
 424                 char *store_type, char *store_id, sdb_time_t store_last_update,
 425                 sdb_data_t value);
 426
 427 /*
 428  * sdb_ast_timeseries_create:
 429  * Creates an AST node representing a TIMESERIES command. The newly created
 430  * node takes ownership of the strings and string vectors.
 431  */
 432 sdb_ast_node_t *
 433 sdb_ast_timeseries_create(char *hostname, char *metric,
 434                 char **data_names, size_t data_names_len,
 435                 sdb_time_t start, sdb_time_t end);
 436
 437 #ifdef __cplusplus
 438 } /* extern "C" */
 439 #endif
 440
 441 #endif /* ! SDB_PARSER_AST_H */
 442
 443 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 444