ovsdb/condition.c

   1 /* Copyright (c) 2009, 2010, 2011 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "condition.h"
  19
  20 #include <limits.h>
  21
  22 #include "column.h"
  23 #include "json.h"
  24 #include "ovsdb-error.h"
  25 #include "row.h"
  26 #include "table.h"
  27
  28 struct ovsdb_error *
  29 ovsdb_function_from_string(const char *name, enum ovsdb_function *function)
  30 {
  31 #define OVSDB_FUNCTION(ENUM, NAME)              \
  32     if (!strcmp(name, NAME)) {                  \
  33         *function = ENUM;                       \
  34         return NULL;                            \
  35     }
  36     OVSDB_FUNCTIONS;
  37 #undef OVSDB_FUNCTION
  38
  39     return ovsdb_syntax_error(NULL, "unknown function",
  40                               "No function named %s.", name);
  41 }
  42
  43 const char *
  44 ovsdb_function_to_string(enum ovsdb_function function)
  45 {
  46     switch (function) {
  47 #define OVSDB_FUNCTION(ENUM, NAME) case ENUM: return NAME;
  48         OVSDB_FUNCTIONS;
  49 #undef OVSDB_FUNCTION
  50     }
  51
  52     return NULL;
  53 }
  54
  55 static struct ovsdb_error *
  56 ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
  57                        const struct json *json,
  58                        struct ovsdb_symbol_table *symtab,
  59                        struct ovsdb_clause *clause)
  60 {
  61     const struct json_array *array;
  62     struct ovsdb_error *error;
  63     const char *function_name;
  64     const char *column_name;
  65     struct ovsdb_type type;
  66
  67     if (json->type == JSON_TRUE || json->type == JSON_FALSE) {
  68         clause->function =
  69             json->type == JSON_TRUE ? OVSDB_F_TRUE : OVSDB_F_FALSE;
  70
  71         /* Column and arg fields are not being used with boolean functions.
  72          * Use dummy values */
  73         clause->column = ovsdb_table_schema_get_column(ts, "_uuid");
  74         clause->index = clause->column->index;
  75         ovsdb_datum_init_default(&clause->arg, &clause->column->type);
  76         return NULL;
  77     }
  78
  79     if (json->type != JSON_ARRAY
  80         || json->u.array.n != 3
  81         || json->u.array.elems[0]->type != JSON_STRING
  82         || json->u.array.elems[1]->type != JSON_STRING) {
  83         return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
  84     }
  85     array = json_array(json);
  86
  87     column_name = json_string(array->elems[0]);
  88     clause->column = ovsdb_table_schema_get_column(ts, column_name);
  89     if (!clause->column) {
  90         return ovsdb_syntax_error(json, "unknown column",
  91                                   "No column %s in table %s.",
  92                                   column_name, ts->name);
  93     }
  94     clause->index = clause->column->index;
  95     type = clause->column->type;
  96
  97     function_name = json_string(array->elems[1]);
  98     error = ovsdb_function_from_string(function_name, &clause->function);
  99     if (error) {
 100         return error;
 101     }
 102
 103     /* Type-check and relax restrictions on 'type' if appropriate.  */
 104     switch (clause->function) {
 105     case OVSDB_F_LT:
 106     case OVSDB_F_LE:
 107     case OVSDB_F_GT:
 108     case OVSDB_F_GE:
 109         /* Allow these operators for types with n_min == 0, n_max == 1.
 110          * (They will always be "false" if the value is missing.) */
 111         if (!(ovsdb_type_is_scalar(&type)
 112             || ovsdb_type_is_optional_scalar(&type))
 113             || (type.key.type != OVSDB_TYPE_INTEGER
 114                 && type.key.type != OVSDB_TYPE_REAL)) {
 115             char *s = ovsdb_type_to_english(&type);
 116             error = ovsdb_syntax_error(
 117                 json, NULL, "Type mismatch: \"%s\" operator may not be "
 118                 "applied to column %s of type %s.",
 119                 ovsdb_function_to_string(clause->function),
 120                 clause->column->name, s);
 121             free(s);
 122             return error;
 123         }
 124         break;
 125     case OVSDB_F_EQ:
 126     case OVSDB_F_NE:
 127         break;
 128
 129     case OVSDB_F_EXCLUDES:
 130         if (!ovsdb_type_is_scalar(&type)) {
 131             type.n_min = 0;
 132             type.n_max = UINT_MAX;
 133         }
 134         break;
 135
 136     case OVSDB_F_INCLUDES:
 137         if (!ovsdb_type_is_scalar(&type)) {
 138             type.n_min = 0;
 139         }
 140         break;
 141     case OVSDB_F_TRUE:
 142     case OVSDB_F_FALSE:
 143         OVS_NOT_REACHED();
 144     }
 145     return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
 146 }
 147
 148 static void
 149 ovsdb_clause_free(struct ovsdb_clause *clause)
 150 {
 151     ovsdb_datum_destroy(&clause->arg, &clause->column->type);
 152 }
 153
 154 static int
 155 compare_clauses_3way(const void *a_, const void *b_)
 156 {
 157     const struct ovsdb_clause *a = a_;
 158     const struct ovsdb_clause *b = b_;
 159
 160     if (a->function != b->function) {
 161         /* Bring functions to the front based on the fraction of table rows
 162          * that they are (heuristically) expected to leave in the query
 163          * results.  Note that "enum ovsdb_function" is intentionally ordered
 164          * to make this trivial. */
 165         return a->function < b->function ? -1 : 1;
 166     } else if (a->column->index != b->column->index) {
 167         if (a->column->index < OVSDB_N_STD_COLUMNS
 168             || b->column->index < OVSDB_N_STD_COLUMNS) {
 169             /* Bring the standard columns and in particular the UUID column
 170              * (since OVSDB_COL_UUID has value 0) to the front.  We have an
 171              * index on the UUID column, so that makes our queries cheaper. */
 172             return a->column->index < b->column->index ? -1 : 1;
 173         } else {
 174             /* Order clauses predictably to make testing easier. */
 175             return strcmp(a->column->name, b->column->name);
 176         }
 177     } else {
 178         return 0;
 179     }
 180 }
 181
 182 static int
 183 compare_clauses_3way_with_data(const void *a_, const void *b_)
 184 {
 185     const struct ovsdb_clause *a = a_;
 186     const struct ovsdb_clause *b = b_;
 187     int res;
 188
 189     res = compare_clauses_3way(a, b);
 190     return res ? res : ovsdb_datum_compare_3way(&a->arg,
 191                                                 &b->arg,
 192                                                 &a->column->type);
 193  }
 194
 195 struct ovsdb_error *
 196 ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
 197                           const struct json *json,
 198                           struct ovsdb_symbol_table *symtab,
 199                           struct ovsdb_condition *cnd)
 200 {
 201     const struct json_array *array = json_array(json);
 202     size_t i;
 203
 204     cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
 205     cnd->n_clauses = 0;
 206     for (i = 0; i < array->n; i++) {
 207         struct ovsdb_error *error;
 208         error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
 209                                        &cnd->clauses[i]);
 210         if (error) {
 211             ovsdb_condition_destroy(cnd);
 212             cnd->clauses = NULL;
 213             cnd->n_clauses = 0;
 214             return error;
 215         }
 216         cnd->n_clauses++;
 217     }
 218
 219     /* A real database would have a query optimizer here. */
 220     qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
 221           compare_clauses_3way_with_data);
 222
 223     return NULL;
 224 }
 225
 226 static struct json *
 227 ovsdb_clause_to_json(const struct ovsdb_clause *clause)
 228 {
 229     if (clause->function != OVSDB_F_TRUE &&
 230         clause->function != OVSDB_F_FALSE) {
 231         return json_array_create_3(
 232                 json_string_create(clause->column->name),
 233                 json_string_create(ovsdb_function_to_string(clause->function)),
 234                 ovsdb_datum_to_json(&clause->arg, &clause->column->type));
 235     }
 236
 237     return json_boolean_create(clause->function == OVSDB_F_TRUE);
 238 }
 239
 240 struct json *
 241 ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
 242 {
 243     struct json **clauses;
 244     size_t i;
 245
 246     clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
 247     for (i = 0; i < cnd->n_clauses; i++) {
 248         clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
 249     }
 250     return json_array_create(clauses, cnd->n_clauses);
 251 }
 252
 253 static bool
 254 ovsdb_clause_evaluate(const struct ovsdb_datum *fields,
 255                       const struct ovsdb_clause *c,
 256                       unsigned int index_map[])
 257 {
 258     const struct ovsdb_datum *field = &fields[index_map ?
 259                                               index_map[c->column->index] :
 260                                               c->column->index];
 261     const struct ovsdb_datum *arg = &c->arg;
 262     const struct ovsdb_type *type = &c->column->type;
 263
 264     if (c->function == OVSDB_F_TRUE ||
 265         c->function == OVSDB_F_FALSE) {
 266         return c->function == OVSDB_F_TRUE;
 267     }
 268     if (ovsdb_type_is_optional_scalar(type) && field->n == 0) {
 269         switch (c->function) {
 270             case OVSDB_F_LT:
 271             case OVSDB_F_LE:
 272             case OVSDB_F_EQ:
 273             case OVSDB_F_GE:
 274             case OVSDB_F_GT:
 275             case OVSDB_F_INCLUDES:
 276                 return false;
 277             case OVSDB_F_NE:
 278             case OVSDB_F_EXCLUDES:
 279                 return true;
 280             case OVSDB_F_TRUE:
 281             case OVSDB_F_FALSE:
 282                 OVS_NOT_REACHED();
 283         }
 284     } else if (ovsdb_type_is_scalar(type)
 285                || ovsdb_type_is_optional_scalar(type)) {
 286         int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
 287                                           type->key.type);
 288         switch (c->function) {
 289         case OVSDB_F_LT:
 290             return cmp < 0;
 291         case OVSDB_F_LE:
 292             return cmp <= 0;
 293         case OVSDB_F_EQ:
 294         case OVSDB_F_INCLUDES:
 295             return cmp == 0;
 296         case OVSDB_F_NE:
 297         case OVSDB_F_EXCLUDES:
 298             return cmp != 0;
 299         case OVSDB_F_GE:
 300             return cmp >= 0;
 301         case OVSDB_F_GT:
 302             return cmp > 0;
 303         case OVSDB_F_TRUE:
 304         case OVSDB_F_FALSE:
 305             OVS_NOT_REACHED();
 306         }
 307     } else {
 308         switch (c->function) {
 309         case OVSDB_F_EQ:
 310             return ovsdb_datum_equals(field, arg, type);
 311         case OVSDB_F_NE:
 312             return !ovsdb_datum_equals(field, arg, type);
 313         case OVSDB_F_INCLUDES:
 314             return ovsdb_datum_includes_all(arg, field, type);
 315         case OVSDB_F_EXCLUDES:
 316             return ovsdb_datum_excludes_all(arg, field, type);
 317         case OVSDB_F_LT:
 318         case OVSDB_F_LE:
 319         case OVSDB_F_GE:
 320         case OVSDB_F_GT:
 321         case OVSDB_F_TRUE:
 322         case OVSDB_F_FALSE:
 323             OVS_NOT_REACHED();
 324         }
 325     }
 326
 327     OVS_NOT_REACHED();
 328 }
 329
 330 static void
 331 ovsdb_clause_clone(struct ovsdb_clause *new, struct ovsdb_clause *old)
 332 {
 333     new->function = old->function;
 334     new->column = old->column;
 335     ovsdb_datum_clone(&new->arg,
 336                       &old->arg,
 337                       &old->column->type);
 338 }
 339
 340 bool
 341 ovsdb_condition_match_every_clause(const struct ovsdb_row *row,
 342                                    const struct ovsdb_condition *cnd)
 343 {
 344     size_t i;
 345
 346     for (i = 0; i < cnd->n_clauses; i++) {
 347         if (!ovsdb_clause_evaluate(row->fields, &cnd->clauses[i], NULL)) {
 348             return false;
 349         }
 350     }
 351
 352     return true;
 353 }
 354
 355 /* Returns true if condition evaluation of one of the clauses is
 356  * true. index_map[] is an optional array that if exists indicates a mapping
 357  * between indexing row_datum to the indexes in ovsdb_column */
 358 bool
 359 ovsdb_condition_match_any_clause(const struct ovsdb_datum *row_datum,
 360                                  const struct ovsdb_condition *cnd,
 361                                  unsigned int index_map[])
 362 {
 363     size_t i;
 364
 365     for (i = 0; i < cnd->n_clauses; i++) {
 366         if (ovsdb_clause_evaluate(row_datum, &cnd->clauses[i], index_map)) {
 367             return true;
 368         }
 369     }
 370
 371     return false;
 372 }
 373
 374 void
 375 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
 376 {
 377     size_t i;
 378
 379     for (i = 0; i < cnd->n_clauses; i++) {
 380         ovsdb_clause_free(&cnd->clauses[i]);
 381     }
 382     free(cnd->clauses);
 383     cnd->n_clauses = 0;
 384 }
 385
 386 void
 387 ovsdb_condition_init(struct ovsdb_condition *cnd)
 388 {
 389     cnd->clauses = NULL;
 390     cnd->n_clauses = 0;
 391 }
 392
 393 bool
 394 ovsdb_condition_empty(const struct ovsdb_condition *cnd)
 395 {
 396     return cnd->n_clauses == 0;
 397 }
 398
 399 int
 400 ovsdb_condition_cmp_3way(const struct ovsdb_condition *a,
 401                          const struct ovsdb_condition *b)
 402 {
 403     size_t i;
 404     int res;
 405
 406     if (a->n_clauses != b->n_clauses) {
 407         return a->n_clauses < b->n_clauses ? -1 : 1;
 408     }
 409
 410     /* We assume clauses are sorted */
 411     for (i = 0; i < a->n_clauses; i++) {
 412         res = (compare_clauses_3way_with_data(&a->clauses[i], &b->clauses[i]));
 413         if (res != 0) {
 414             return res;
 415         }
 416     }
 417
 418     return 0;
 419 }
 420
 421 void
 422 ovsdb_condition_clone(struct ovsdb_condition *to,
 423                       const struct ovsdb_condition *from)
 424 {
 425     size_t i;
 426
 427     to->clauses = xzalloc(from->n_clauses * sizeof *to->clauses);
 428
 429     for (i = 0; i < from->n_clauses; i++) {
 430         ovsdb_clause_clone(&to->clauses[i], &from->clauses[i]);
 431     }
 432     to->n_clauses = from->n_clauses;
 433 }
 434
 435 /* Return true if ovsdb_condition_match_any_clause() will return true on
 436  * any row */
 437 bool
 438 ovsdb_condition_is_true(const struct ovsdb_condition *cond)
 439 {
 440     return (!cond->n_clauses ||
 441        (cond->n_clauses >= 1 && (cond->clauses[0].function == OVSDB_F_TRUE)) ||
 442        (cond->n_clauses >= 2 && (cond->clauses[1].function == OVSDB_F_TRUE)));
 443 }
 444
 445 bool
 446 ovsdb_condition_is_false(const struct ovsdb_condition *cond)
 447 {
 448     return ((cond->n_clauses == 1) &&
 449             (cond->clauses[0].function == OVSDB_F_FALSE));
 450  }
 451
 452 const struct ovsdb_column **
 453 ovsdb_condition_get_columns(const struct ovsdb_condition *cond,
 454                             size_t *n_columns)
 455 {
 456     const struct ovsdb_column **columns;
 457     size_t i;
 458
 459     columns = xmalloc(cond->n_clauses * sizeof *columns);
 460     for (i = 0; i < cond->n_clauses; i++) {
 461         columns[i] = cond->clauses[i].column;
 462     }
 463     *n_columns = i;
 464
 465     return columns;
 466 }