Code

analyzer: Support more flexible iterator expressions.
authorSebastian Harl <sh@tokkee.org>
Mon, 31 Aug 2015 20:50:20 +0000 (22:50 +0200)
committerSebastian Harl <sh@tokkee.org>
Mon, 31 Aug 2015 20:50:20 +0000 (22:50 +0200)
In particular, more complex typed expressions may now include an iterator on a
lower level, like `LOOKUP services MATCHING ANY host.backend =~ 'foo'`. This
is done by adding more information to the analyzer context and pushing it down
to child nodes in the AST if necessary.

As a nice side-effect, the iterator analyzer does not longer have to know
about the specific type of its child node.

src/parser/analyzer.c
t/unit/parser/parser_test.c

index 2cb2816..f12dff2 100644 (file)
 
 #include <assert.h>
 #include <stdarg.h>
+#include <stdbool.h>
+#include <string.h>
 
 #define VALID_OBJ_TYPE(t) ((SDB_HOST <= (t)) && ((t) <= SDB_METRIC))
 
+typedef struct {
+       int type;
+       bool iter;
+} context_t;
+
 #define FILTER_CONTEXT -1
+static const context_t FILTER_CTX = { FILTER_CONTEXT, 0 };
 
 static int
-analyze_node(int context, sdb_ast_node_t *node, sdb_strbuf_t *errbuf);
+analyze_node(context_t ctx, sdb_ast_node_t *node, sdb_strbuf_t *errbuf);
 
 /*
  * error reporting
@@ -82,8 +90,13 @@ iter_error(sdb_strbuf_t *errbuf, sdb_ast_iter_t *iter, const char *reason, ...)
  */
 
 static int
-analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
+analyze_logical(context_t ctx, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
 {
+       if (ctx.iter) {
+               op_error(errbuf, op, "cannot evaluate in iterator context");
+               return -1;
+       }
+
        switch (op->kind) {
        case SDB_AST_OR:
        case SDB_AST_AND:
@@ -93,7 +106,7 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
                                        SDB_AST_OP_TO_STRING(op->kind));
                        return -1;
                }
-               if (analyze_node(context, op->left, errbuf))
+               if (analyze_node(ctx, op->left, errbuf))
                        return -1;
                /* fallthrough */
        case SDB_AST_NOT:
@@ -103,7 +116,7 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
                                        SDB_AST_OP_TO_STRING(op->kind));
                        return -1;
                }
-               if (analyze_node(context, op->right, errbuf))
+               if (analyze_node(ctx, op->right, errbuf))
                        return -1;
                break;
 
@@ -114,9 +127,9 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
        case SDB_AST_GE:
        case SDB_AST_GT:
        {
-               if (analyze_node(context, op->left, errbuf))
+               if (analyze_node(ctx, op->left, errbuf))
                        return -1;
-               if (analyze_node(context, op->right, errbuf))
+               if (analyze_node(ctx, op->right, errbuf))
                        return -1;
 
                if ((op->left->data_type > 0) && (op->right->data_type > 0)) {
@@ -138,9 +151,9 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
 
        case SDB_AST_REGEX:
        case SDB_AST_NREGEX:
-               if (analyze_node(context, op->left, errbuf))
+               if (analyze_node(ctx, op->left, errbuf))
                        return -1;
-               if (analyze_node(context, op->right, errbuf))
+               if (analyze_node(ctx, op->right, errbuf))
                        return -1;
 
                /* all types are supported for the left operand
@@ -156,14 +169,14 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
        case SDB_AST_ISNULL:
        case SDB_AST_ISTRUE:
        case SDB_AST_ISFALSE:
-               if (analyze_node(context, op->right, errbuf))
+               if (analyze_node(ctx, op->right, errbuf))
                        return -1;
                break;
 
        case SDB_AST_IN:
-               if (analyze_node(context, op->left, errbuf))
+               if (analyze_node(ctx, op->left, errbuf))
                        return -1;
-               if (analyze_node(context, op->right, errbuf))
+               if (analyze_node(ctx, op->right, errbuf))
                        return -1;
 
                if ((op->right->data_type > 0) && (! (op->right->data_type & SDB_TYPE_ARRAY))) {
@@ -187,11 +200,16 @@ analyze_logical(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
 } /* analyze_logical */
 
 static int
-analyze_arith(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
+analyze_arith(context_t ctx, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
 {
-       if (analyze_node(context, op->left, errbuf))
+       if (ctx.iter) {
+               op_error(errbuf, op, "cannot evaluate in iterator context");
                return -1;
-       if (analyze_node(context, op->right, errbuf))
+       }
+
+       if (analyze_node(ctx, op->left, errbuf))
+               return -1;
+       if (analyze_node(ctx, op->right, errbuf))
                return -1;
        SDB_AST_NODE(op)->data_type = sdb_data_expr_type(SDB_AST_OP_TO_DATA_OP(op->kind),
                        op->left->data_type, op->right->data_type);
@@ -207,86 +225,36 @@ analyze_arith(int context, sdb_ast_op_t *op, sdb_strbuf_t *errbuf)
 } /* analyze_arith */
 
 static int
-analyze_iter(int context, sdb_ast_iter_t *iter, sdb_strbuf_t *errbuf)
+analyze_iter(context_t ctx, sdb_ast_iter_t *iter, sdb_strbuf_t *errbuf)
 {
        sdb_ast_const_t c = SDB_AST_CONST_INIT;
-       int iter_context = context;
+       context_t iter_ctx = ctx;
        int status;
 
-       if (iter->iter->type == SDB_AST_TYPE_TYPED)
-               iter_context = SDB_AST_TYPED(iter->iter)->type;
-
-       if (analyze_node(iter_context, iter->iter, errbuf))
+       if (ctx.iter) {
+               iter_error(errbuf, iter, "nested iterators are not supported");
                return -1;
-       /* TODO: support other setups as well */
-       assert((iter->expr->type == SDB_AST_TYPE_OPERATOR)
-                       && (! SDB_AST_OP(iter->expr)->left));
-       /* determine the data-type for better error messages */
-       analyze_node(iter_context, SDB_AST_OP(iter->expr)->right, NULL);
-
-       if (iter->iter->type == SDB_AST_TYPE_TYPED) {
-               int iter_type = SDB_AST_TYPED(iter->iter)->type;
-
-               c.value.type = iter->iter->data_type;
-
-               if (iter_type == SDB_ATTRIBUTE) {
-                       /* attributes are always iterable */
-               }
-               else if ((context != SDB_HOST) && (context != SDB_SERVICE)
-                               && (context != SDB_METRIC)) {
-                       iter_error(errbuf, iter, "%s not iterable in %s context",
-                                       SDB_STORE_TYPE_TO_NAME(iter_type),
-                                       SDB_STORE_TYPE_TO_NAME(context));
-                       return -1;
-               }
-
-               if ((context == iter_type)
-                               || ((iter_type != SDB_SERVICE)
-                                       && (iter_type != SDB_METRIC)
-                                       && (iter_type != SDB_ATTRIBUTE))
-                               || ((context == SDB_SERVICE)
-                                       && (iter_type == SDB_METRIC))
-                               || ((context == SDB_METRIC)
-                                       && (iter_type == SDB_SERVICE))) {
-                       iter_error(errbuf, iter, "%s not iterable in %s context",
-                                       SDB_STORE_TYPE_TO_NAME(iter_type),
-                                       SDB_STORE_TYPE_TO_NAME(context));
-                       return -1;
-               }
        }
-       else if (iter->iter->type == SDB_AST_TYPE_VALUE) {
-               int iter_type = SDB_AST_VALUE(iter->iter)->type;
 
-               c.value.type = iter->iter->data_type & 0xff;
+       iter_ctx.iter = 1;
+       if (analyze_node(iter_ctx, iter->iter, errbuf))
+               return -1;
 
-               if (iter_type != SDB_FIELD_BACKEND) {
-                       iter_error(errbuf, iter, "%s not iterable in %s context",
-                                       (iter_type == SDB_ATTRIBUTE)
-                                               ? "attribute"
-                                               : SDB_FIELD_TO_NAME(iter_type),
-                                       SDB_STORE_TYPE_TO_NAME(context));
+       if (iter->iter->data_type > 0) {
+               if (! (iter->iter->data_type & SDB_TYPE_ARRAY)) {
+                       iter_error(errbuf, iter, "cannot iterate values of type %s",
+                                       SDB_TYPE_TO_STRING(iter->iter->data_type));
                        return -1;
                }
-       }
-       else if (iter->iter->type == SDB_AST_TYPE_CONST) {
                c.value.type = iter->iter->data_type & 0xff;
-
-               if (! (SDB_AST_CONST(iter->iter)->value.type & SDB_TYPE_ARRAY)) {
-                       iter_error(errbuf, iter, "%s not iterable",
-                                       SDB_TYPE_TO_STRING(SDB_AST_CONST(iter->iter)->value.type));
-                       return -1;
-               }
-       }
-       else {
-               /* TODO: if we know the data-type of iter->iter and it's an array,
-                * we should support an iterator for it as well */
-               iter_error(errbuf, iter, "%s expression not iterable",
-                               SDB_AST_TYPE_TO_STRING(iter->iter));
-               return -1;
        }
 
+       /* TODO: support other setups as well */
+       assert((iter->expr->type == SDB_AST_TYPE_OPERATOR)
+                       && (! SDB_AST_OP(iter->expr)->left));
+
        SDB_AST_OP(iter->expr)->left = SDB_AST_NODE(&c);
-       status = analyze_node(context, iter->expr, errbuf);
+       status = analyze_node(ctx, iter->expr, errbuf);
        SDB_AST_OP(iter->expr)->left = NULL;
        if (status)
                return -1;
@@ -294,7 +262,7 @@ analyze_iter(int context, sdb_ast_iter_t *iter, sdb_strbuf_t *errbuf)
 } /* analyze_iter */
 
 static int
-analyze_const(int __attribute__((unused)) context, sdb_ast_const_t *c,
+analyze_const(context_t __attribute__((unused)) ctx, sdb_ast_const_t *c,
                sdb_strbuf_t __attribute__((unused)) *errbuf)
 {
        SDB_AST_NODE(c)->data_type = c->value.type;
@@ -302,7 +270,7 @@ analyze_const(int __attribute__((unused)) context, sdb_ast_const_t *c,
 } /* analyze_const */
 
 static int
-analyze_value(int context, sdb_ast_value_t *v, sdb_strbuf_t *errbuf)
+analyze_value(context_t ctx, sdb_ast_value_t *v, sdb_strbuf_t *errbuf)
 {
        if (v->type != SDB_ATTRIBUTE)
                SDB_AST_NODE(v)->data_type = SDB_FIELD_TYPE(v->type);
@@ -318,22 +286,39 @@ analyze_value(int context, sdb_ast_value_t *v, sdb_strbuf_t *errbuf)
                return -1;
        }
 
-       if ((context != SDB_ATTRIBUTE) && (v->type == SDB_FIELD_VALUE)) {
+       /* this would be caught by the type check in analyze_iter but we're able
+        * to provide a more specific error message here */
+       if (ctx.iter && (v->type != SDB_FIELD_BACKEND)) {
+               /* only backend values are iterable */
+               char value_str[64 + (v->name ? strlen(v->name) : 0)];
+               if (v->type == SDB_ATTRIBUTE)
+                       snprintf(value_str, sizeof(value_str), "attribute[%s]", v->name);
+               else
+                       snprintf(value_str, sizeof(value_str), "'%s'", SDB_FIELD_TO_NAME(v->type));
+               sdb_strbuf_sprintf(errbuf, "Cannot iterate %s (scalar value)", value_str);
+               return -1;
+       }
+
+       if ((ctx.type != SDB_ATTRIBUTE) && (v->type == SDB_FIELD_VALUE)) {
                sdb_strbuf_sprintf(errbuf, "Invalid expression %s.value",
-                               SDB_FIELD_TO_NAME(context));
+                               SDB_FIELD_TO_NAME(ctx.type));
                return -1;
        }
-       if ((context != SDB_METRIC) && (v->type == SDB_FIELD_TIMESERIES)) {
+       if ((ctx.type != SDB_METRIC) && (v->type == SDB_FIELD_TIMESERIES)) {
                sdb_strbuf_sprintf(errbuf, "Invalid expression %s.timeseries",
-                               SDB_FIELD_TO_NAME(context));
+                               SDB_FIELD_TO_NAME(ctx.type));
                return -1;
        }
        return 0;
 } /* analyze_value */
 
 static int
-analyze_typed(int context, sdb_ast_typed_t *t, sdb_strbuf_t *errbuf)
+analyze_typed(context_t ctx, sdb_ast_typed_t *t, sdb_strbuf_t *errbuf)
 {
+       context_t child_ctx = ctx;
+       bool needs_iter = 0;
+       bool valid = 1;
+
        if ((t->expr->type != SDB_AST_TYPE_VALUE)
                        && (t->expr->type != SDB_AST_TYPE_TYPED)) {
                sdb_strbuf_sprintf(errbuf, "Invalid expression %s.%s",
@@ -341,33 +326,75 @@ analyze_typed(int context, sdb_ast_typed_t *t, sdb_strbuf_t *errbuf)
                                SDB_AST_TYPE_TO_STRING(t->expr));
                return -1;
        }
-       if (analyze_node(t->type, t->expr, errbuf))
-               return -1;
-       SDB_AST_NODE(t)->data_type = t->expr->data_type;
-
        if ((t->type != SDB_ATTRIBUTE) && (! VALID_OBJ_TYPE(t->type))) {
                sdb_strbuf_sprintf(errbuf, "Invalid expression %#x.%s",
                                t->type, SDB_AST_TYPE_TO_STRING(t->expr));
                return -1;
        }
 
-       /* self-references are allowed and services and metrics may reference
-        * their parent host; everything may reference attributes */
-       if ((context != t->type) && (context > 0)
-                       && (((context != SDB_SERVICE) && (context != SDB_METRIC))
-                               || (t->type != SDB_HOST))
-                       && (t->type != SDB_ATTRIBUTE)) {
+       if (ctx.type > 0) {
+               if ((ctx.type == t->type)
+                               || ((t->type == SDB_HOST) && (ctx.type != SDB_ATTRIBUTE))) {
+                       /* self-references and references to the parent host are always fine */
+               }
+               else if (t->type == SDB_ATTRIBUTE) {
+                       /* references to attributes are always fine */
+                       needs_iter = 1;
+               }
+               else if ((ctx.type == SDB_HOST)
+                               && ((t->type == SDB_SERVICE) || (t->type == SDB_METRIC))) {
+                       /* only hosts may reference services and metrics */
+                       needs_iter = 1;
+               }
+               else {
+                       valid = 0;
+               }
+       }
+       else if (ctx.type == FILTER_CONTEXT) {
+               if (t->type == SDB_ATTRIBUTE) {
+                       /* all objects have attributes */
+                       needs_iter = 1;
+               }
+               else if ((t->type == SDB_SERVICE) || (t->type == SDB_METRIC)) {
+                       /* these will be iterators for *some* operations;
+                        * better forbid this altogether */
+                       valid = 0;
+               }
+       }
+
+       if (needs_iter) {
+               if (! ctx.iter)
+                       valid = 0;
+               else
+                       child_ctx.iter = 0;
+       } /* else: push ctx.iter down to the child node */
+
+       if (! valid) {
                sdb_strbuf_sprintf(errbuf, "Invalid expression %s.%s in %s context",
                                SDB_STORE_TYPE_TO_NAME(t->type),
                                SDB_AST_TYPE_TO_STRING(t->expr),
-                               context == -1 ? "generic" : SDB_STORE_TYPE_TO_NAME(context));
+                               SDB_STORE_TYPE_TO_NAME(ctx.type));
+               return -1;
+       }
+
+       child_ctx.type = t->type;
+       if (analyze_node(child_ctx, t->expr, errbuf))
                return -1;
+       SDB_AST_NODE(t)->data_type = t->expr->data_type;
+
+       if (needs_iter && (SDB_AST_NODE(t)->data_type > 0)) {
+               if (SDB_AST_NODE(t)->data_type & SDB_TYPE_ARRAY) {
+                       sdb_strbuf_sprintf(errbuf, "Cannot access array inside iterator");
+                       return -1;
+               }
+               /* Tell the caller that we're accessing an iterator. */
+               SDB_AST_NODE(t)->data_type |= SDB_TYPE_ARRAY;
        }
        return 0;
 } /* analyze_typed */
 
 static int
-analyze_node(int context, sdb_ast_node_t *node, sdb_strbuf_t *errbuf)
+analyze_node(context_t ctx, sdb_ast_node_t *node, sdb_strbuf_t *errbuf)
 {
        if (! node) {
                sdb_strbuf_sprintf(errbuf, "Empty AST node");
@@ -379,18 +406,18 @@ analyze_node(int context, sdb_ast_node_t *node, sdb_strbuf_t *errbuf)
 
        if ((node->type == SDB_AST_TYPE_OPERATOR)
                        && (SDB_AST_IS_LOGICAL(node)))
-               return analyze_logical(context, SDB_AST_OP(node), errbuf);
+               return analyze_logical(ctx, SDB_AST_OP(node), errbuf);
        else if ((node->type == SDB_AST_TYPE_OPERATOR)
                        && (SDB_AST_IS_ARITHMETIC(node)))
-               return analyze_arith(context, SDB_AST_OP(node), errbuf);
+               return analyze_arith(ctx, SDB_AST_OP(node), errbuf);
        else if (node->type == SDB_AST_TYPE_ITERATOR)
-               return analyze_iter(context, SDB_AST_ITER(node), errbuf);
+               return analyze_iter(ctx, SDB_AST_ITER(node), errbuf);
        else if (node->type == SDB_AST_TYPE_CONST)
-               return analyze_const(context, SDB_AST_CONST(node), errbuf);
+               return analyze_const(ctx, SDB_AST_CONST(node), errbuf);
        else if (node->type == SDB_AST_TYPE_VALUE)
-               return analyze_value(context, SDB_AST_VALUE(node), errbuf);
+               return analyze_value(ctx, SDB_AST_VALUE(node), errbuf);
        else if (node->type == SDB_AST_TYPE_TYPED)
-               return analyze_typed(context, SDB_AST_TYPED(node), errbuf);
+               return analyze_typed(ctx, SDB_AST_TYPED(node), errbuf);
 
        sdb_strbuf_sprintf(errbuf, "Invalid expression node "
                        "of type %#x", node->type);
@@ -428,7 +455,7 @@ analyze_fetch(sdb_ast_fetch_t *fetch, sdb_strbuf_t *errbuf)
        }
 
        if (fetch->filter)
-               return analyze_node(FILTER_CONTEXT, fetch->filter, errbuf);
+               return analyze_node(FILTER_CTX, fetch->filter, errbuf);
        return 0;
 } /* analyze_fetch */
 
@@ -441,7 +468,7 @@ analyze_list(sdb_ast_list_t *list, sdb_strbuf_t *errbuf)
                return -1;
        }
        if (list->filter)
-               return analyze_node(FILTER_CONTEXT, list->filter, errbuf);
+               return analyze_node(FILTER_CTX, list->filter, errbuf);
        return 0;
 } /* analyze_list */
 
@@ -453,11 +480,13 @@ analyze_lookup(sdb_ast_lookup_t *lookup, sdb_strbuf_t *errbuf)
                                "in LOOKUP command", lookup->obj_type);
                return -1;
        }
-       if (lookup->matcher)
-               if (analyze_node(lookup->obj_type, lookup->matcher, errbuf))
+       if (lookup->matcher) {
+               context_t ctx = { lookup->obj_type, 0 };
+               if (analyze_node(ctx, lookup->matcher, errbuf))
                        return -1;
+       }
        if (lookup->filter)
-               return analyze_node(FILTER_CONTEXT, lookup->filter, errbuf);
+               return analyze_node(FILTER_CTX, lookup->filter, errbuf);
        return 0;
 } /* analyze_lookup */
 
@@ -606,6 +635,7 @@ int
 sdb_parser_analyze_conditional(int context,
                sdb_ast_node_t *node, sdb_strbuf_t *errbuf)
 {
+       context_t ctx = { context, 0 };
        if (! VALID_OBJ_TYPE(context)) {
                sdb_strbuf_sprintf(errbuf, "Invalid object type %#x", context);
                return -1;
@@ -619,13 +649,14 @@ sdb_parser_analyze_conditional(int context,
                                SDB_AST_TYPE_TO_STRING(node));
                return -1;
        }
-       return analyze_node(context, node, errbuf);
+       return analyze_node(ctx, node, errbuf);
 } /* sdb_parser_analyze_conditional */
 
 int
 sdb_parser_analyze_arith(int context,
                sdb_ast_node_t *node, sdb_strbuf_t *errbuf)
 {
+       context_t ctx = { context, 0 };
        if (! VALID_OBJ_TYPE(context)) {
                sdb_strbuf_sprintf(errbuf, "Invalid object type %#x", context);
                return -1;
@@ -639,7 +670,7 @@ sdb_parser_analyze_arith(int context,
                                SDB_AST_TYPE_TO_STRING(node));
                return -1;
        }
-       return analyze_node(context, node, errbuf);
+       return analyze_node(ctx, node, errbuf);
 } /* sdb_parser_analyze_arith */
 
 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
index 62a7e90..89ee2e6 100644 (file)
@@ -157,6 +157,8 @@ struct {
          "host.name = 'p'",         -1,   1, SDB_AST_TYPE_LOOKUP, SDB_SERVICE },
        { "LOOKUP services MATCHING "
          "service.name = 'p'",      -1,   1, SDB_AST_TYPE_LOOKUP, SDB_SERVICE },
+       { "LOOKUP services MATCHING ANY "
+         "host.backend =~ 'b'",     -1,   1, SDB_AST_TYPE_LOOKUP, SDB_SERVICE },
        { "LOOKUP metrics",          -1,   1, SDB_AST_TYPE_LOOKUP, SDB_METRIC },
        { "LOOKUP metrics MATCHING ANY "
          "attribute.name =~ 'a'",   -1,   1, SDB_AST_TYPE_LOOKUP, SDB_METRIC },
@@ -164,6 +166,8 @@ struct {
          "host.name = 'p'",         -1,   1, SDB_AST_TYPE_LOOKUP, SDB_METRIC },
        { "LOOKUP metrics MATCHING "
          "metric.name = 'p'",       -1,   1, SDB_AST_TYPE_LOOKUP, SDB_METRIC },
+       { "LOOKUP metrics MATCHING ANY "
+         "host.service.name = 'p'", -1,   1, SDB_AST_TYPE_LOOKUP, SDB_METRIC },
 
        /* TIMESERIES commands */
        { "TIMESERIES 'host'.'metric' "
@@ -579,6 +583,12 @@ struct {
        { "LOOKUP hosts MATCHING "
          "ANY backend || 'a' = 'b'",
                                -1,  -1, 0, 0 },
+       { "LOOKUP hosts MATCHING ANY "
+         "host.name = 'h'",    -1, -1, 0, 0 },
+       { "LOOKUP services MATCHING ANY "
+         "host.name = 'h'",    -1, -1, 0, 0 },
+       { "LOOKUP metrics MATCHING ANY "
+         "host.name = 'h'",    -1, -1, 0, 0 },
 
        /* invalid LIST commands */
        { "LIST",                -1, -1, 0, 0 },