ovn/lib/expr.c

   1 /*
   2  * Copyright (c) 2015, 2016 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "byte-order.h"
  19 #include "expr.h"
  20 #include "json.h"
  21 #include "lex.h"
  22 #include "logical-fields.h"
  23 #include "openvswitch/dynamic-string.h"
  24 #include "openvswitch/match.h"
  25 #include "openvswitch/ofp-actions.h"
  26 #include "openvswitch/vlog.h"
  27 #include "shash.h"
  28 #include "simap.h"
  29 #include "sset.h"
  30
  31 VLOG_DEFINE_THIS_MODULE(expr);
  32 \f
  33 /* Returns the name of measurement level 'level'. */
  34 const char *
  35 expr_level_to_string(enum expr_level level)
  36 {
  37     switch (level) {
  38     case EXPR_L_NOMINAL: return "nominal";
  39     case EXPR_L_BOOLEAN: return "Boolean";
  40     case EXPR_L_ORDINAL: return "ordinal";
  41     default: OVS_NOT_REACHED();
  42     }
  43 }
  44 \f
  45 /* Relational operators. */
  46
  47 /* Returns a string form of relational operator 'relop'. */
  48 const char *
  49 expr_relop_to_string(enum expr_relop relop)
  50 {
  51     switch (relop) {
  52     case EXPR_R_EQ: return "==";
  53     case EXPR_R_NE: return "!=";
  54     case EXPR_R_LT: return "<";
  55     case EXPR_R_LE: return "<=";
  56     case EXPR_R_GT: return ">";
  57     case EXPR_R_GE: return ">=";
  58     default: OVS_NOT_REACHED();
  59     }
  60 }
  61
  62 bool
  63 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
  64 {
  65     enum expr_relop r;
  66
  67     switch ((int) type) {
  68     case LEX_T_EQ: r = EXPR_R_EQ; break;
  69     case LEX_T_NE: r = EXPR_R_NE; break;
  70     case LEX_T_LT: r = EXPR_R_LT; break;
  71     case LEX_T_LE: r = EXPR_R_LE; break;
  72     case LEX_T_GT: r = EXPR_R_GT; break;
  73     case LEX_T_GE: r = EXPR_R_GE; break;
  74     default: return false;
  75     }
  76
  77     if (relop) {
  78         *relop = r;
  79     }
  80     return true;
  81 }
  82
  83 /* Returns the relational operator that 'relop' becomes if you turn the
  84  * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
  85  * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
  86  * b" is equivalent to "b >= a". */
  87 static enum expr_relop
  88 expr_relop_turn(enum expr_relop relop)
  89 {
  90     switch (relop) {
  91     case EXPR_R_EQ: return EXPR_R_EQ;
  92     case EXPR_R_NE: return EXPR_R_NE;
  93     case EXPR_R_LT: return EXPR_R_GT;
  94     case EXPR_R_LE: return EXPR_R_GE;
  95     case EXPR_R_GT: return EXPR_R_LT;
  96     case EXPR_R_GE: return EXPR_R_LE;
  97     default: OVS_NOT_REACHED();
  98     }
  99 }
 100
 101 /* Returns the relational operator that is the opposite of 'relop'. */
 102 static enum expr_relop
 103 expr_relop_invert(enum expr_relop relop)
 104 {
 105     switch (relop) {
 106     case EXPR_R_EQ: return EXPR_R_NE;
 107     case EXPR_R_NE: return EXPR_R_EQ;
 108     case EXPR_R_LT: return EXPR_R_GE;
 109     case EXPR_R_LE: return EXPR_R_GT;
 110     case EXPR_R_GT: return EXPR_R_LE;
 111     case EXPR_R_GE: return EXPR_R_LT;
 112     default: OVS_NOT_REACHED();
 113     }
 114 }
 115 \f
 116 /* Constructing and manipulating expressions. */
 117
 118 /* Creates and returns a logical AND or OR expression (according to 'type',
 119  * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
 120  * sub-expressions.  (To satisfy the invariants for expressions, the caller
 121  * must add at least two sub-expressions whose types are different from
 122  * 'type'.) */
 123 struct expr *
 124 expr_create_andor(enum expr_type type)
 125 {
 126     struct expr *e = xmalloc(sizeof *e);
 127     e->type = type;
 128     ovs_list_init(&e->andor);
 129     return e;
 130 }
 131
 132 /* Returns a logical AND or OR expression (according to 'type', which must be
 133  * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
 134  * flexibility:
 135  *
 136  *     - If 'a' or 'b' is NULL, just returns the other one (which means that if
 137  *       that other one is not of the given 'type', then the returned
 138  *       expression is not either).
 139  *
 140  *     - If 'a' or 'b', or both, have type 'type', then they are combined into
 141  *       a single node that satisfies the invariants for expressions. */
 142 struct expr *
 143 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
 144 {
 145     if (!a) {
 146         return b;
 147     } else if (!b) {
 148         return a;
 149     } else if (a->type == type) {
 150         if (b->type == type) {
 151             ovs_list_splice(&a->andor, b->andor.next, &b->andor);
 152             free(b);
 153         } else {
 154             ovs_list_push_back(&a->andor, &b->node);
 155         }
 156         return a;
 157     } else if (b->type == type) {
 158         ovs_list_push_front(&b->andor, &a->node);
 159         return b;
 160     } else {
 161         struct expr *e = expr_create_andor(type);
 162         ovs_list_push_back(&e->andor, &a->node);
 163         ovs_list_push_back(&e->andor, &b->node);
 164         return e;
 165     }
 166 }
 167
 168 static void
 169 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
 170 {
 171     if (new->type == andor->type) {
 172         if (andor->type == EXPR_T_AND) {
 173             /* Conjunction junction, what's your function? */
 174         }
 175         ovs_list_splice(&before->node, new->andor.next, &new->andor);
 176         free(new);
 177     } else {
 178         ovs_list_insert(&before->node, &new->node);
 179     }
 180 }
 181
 182 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
 183 struct expr *
 184 expr_create_boolean(bool b)
 185 {
 186     struct expr *e = xmalloc(sizeof *e);
 187     e->type = EXPR_T_BOOLEAN;
 188     e->boolean = b;
 189     return e;
 190 }
 191
 192 static void
 193 expr_not(struct expr *expr)
 194 {
 195     struct expr *sub;
 196
 197     switch (expr->type) {
 198     case EXPR_T_CMP:
 199         expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
 200         break;
 201
 202     case EXPR_T_AND:
 203     case EXPR_T_OR:
 204         LIST_FOR_EACH (sub, node, &expr->andor) {
 205             expr_not(sub);
 206         }
 207         expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
 208         break;
 209
 210     case EXPR_T_BOOLEAN:
 211         expr->boolean = !expr->boolean;
 212         break;
 213     default:
 214         OVS_NOT_REACHED();
 215     }
 216 }
 217
 218 static struct expr *
 219 expr_fix_andor(struct expr *expr, bool short_circuit)
 220 {
 221     struct expr *sub, *next;
 222
 223     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
 224         if (sub->type == EXPR_T_BOOLEAN) {
 225             if (sub->boolean == short_circuit) {
 226                 expr_destroy(expr);
 227                 return expr_create_boolean(short_circuit);
 228             } else {
 229                 ovs_list_remove(&sub->node);
 230                 expr_destroy(sub);
 231             }
 232         }
 233     }
 234
 235     if (ovs_list_is_short(&expr->andor)) {
 236         if (ovs_list_is_empty(&expr->andor)) {
 237             free(expr);
 238             return expr_create_boolean(!short_circuit);
 239         } else {
 240             sub = expr_from_node(ovs_list_front(&expr->andor));
 241             free(expr);
 242             return sub;
 243         }
 244     } else {
 245         return expr;
 246     }
 247 }
 248
 249 /* Returns 'expr' modified so that top-level oddities are fixed up:
 250  *
 251  *     - Eliminates any EXPR_T_BOOLEAN operands at the top level.
 252  *
 253  *     - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
 254 static struct expr *
 255 expr_fix(struct expr *expr)
 256 {
 257     switch (expr->type) {
 258     case EXPR_T_CMP:
 259         return expr;
 260
 261     case EXPR_T_AND:
 262         return expr_fix_andor(expr, false);
 263
 264     case EXPR_T_OR:
 265         return expr_fix_andor(expr, true);
 266
 267     case EXPR_T_BOOLEAN:
 268         return expr;
 269
 270     default:
 271         OVS_NOT_REACHED();
 272     }
 273 }
 274 \f
 275 /* Formatting. */
 276
 277 static void
 278 find_bitwise_range(const union mf_subvalue *sv, int width,
 279                    int *startp, int *n_bitsp)
 280 {
 281     unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
 282     if (start < width) {
 283         unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
 284         if (end >= width
 285             || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
 286             *startp = start;
 287             *n_bitsp = end - start;
 288             return;
 289         }
 290     }
 291     *startp = *n_bitsp = 0;
 292 }
 293
 294 static void
 295 expr_format_cmp(const struct expr *e, struct ds *s)
 296 {
 297     /* The common case is numerical comparisons.
 298      * Handle string comparisons as a special case. */
 299     if (!e->cmp.symbol->width) {
 300         ds_put_format(s, "%s %s ", e->cmp.symbol->name,
 301                       expr_relop_to_string(e->cmp.relop));
 302         json_string_escape(e->cmp.string, s);
 303         return;
 304     }
 305
 306     int ofs, n;
 307     find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
 308     if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
 309         bool positive;
 310
 311         positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
 312         positive ^= e->cmp.relop == EXPR_R_NE;
 313         if (!positive) {
 314             ds_put_char(s, '!');
 315         }
 316         ds_put_cstr(s, e->cmp.symbol->name);
 317         if (e->cmp.symbol->width > 1) {
 318             ds_put_format(s, "[%d]", ofs);
 319         }
 320         return;
 321     }
 322
 323     ds_put_cstr(s, e->cmp.symbol->name);
 324     if (n > 0 && n < e->cmp.symbol->width) {
 325         if (n > 1) {
 326             ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
 327         } else {
 328             ds_put_format(s, "[%d]", ofs);
 329         }
 330     }
 331
 332     ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
 333
 334     if (n) {
 335         union mf_subvalue value;
 336
 337         memset(&value, 0, sizeof value);
 338         bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
 339                      &value, sizeof value, 0,
 340                      n);
 341         mf_format_subvalue(&value, s);
 342     } else {
 343         mf_format_subvalue(&e->cmp.value, s);
 344         ds_put_char(s, '/');
 345         mf_format_subvalue(&e->cmp.mask, s);
 346     }
 347 }
 348
 349 static void
 350 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
 351 {
 352     struct expr *sub;
 353     int i = 0;
 354
 355     LIST_FOR_EACH (sub, node, &e->andor) {
 356         if (i++) {
 357             ds_put_format(s, " %s ", op);
 358         }
 359
 360         if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
 361             ds_put_char(s, '(');
 362             expr_format(sub, s);
 363             ds_put_char(s, ')');
 364         } else {
 365             expr_format(sub, s);
 366         }
 367     }
 368 }
 369
 370 /* Appends a string form of 'e' to 's'.  The string form is acceptable for
 371  * parsing back into an equivalent expression. */
 372 void
 373 expr_format(const struct expr *e, struct ds *s)
 374 {
 375     switch (e->type) {
 376     case EXPR_T_CMP:
 377         expr_format_cmp(e, s);
 378         break;
 379
 380     case EXPR_T_AND:
 381         expr_format_andor(e, "&&", s);
 382         break;
 383
 384     case EXPR_T_OR:
 385         expr_format_andor(e, "||", s);
 386         break;
 387
 388     case EXPR_T_BOOLEAN:
 389         ds_put_char(s, e->boolean ? '1' : '0');
 390         break;
 391     }
 392 }
 393
 394 /* Prints a string form of 'e' on stdout, followed by a new-line. */
 395 void
 396 expr_print(const struct expr *e)
 397 {
 398     struct ds output;
 399
 400     ds_init(&output);
 401     expr_format(e, &output);
 402     puts(ds_cstr(&output));
 403     ds_destroy(&output);
 404 }
 405 \f
 406 /* Parsing. */
 407
 408 /* Context maintained during expr_parse(). */
 409 struct expr_context {
 410     struct lexer *lexer;        /* Lexer for pulling more tokens. */
 411     const struct shash *symtab; /* Symbol table. */
 412     const struct shash *macros; /* Table of macros. */
 413     char *error;                /* Error, if any, otherwise NULL. */
 414     bool not;                   /* True inside odd number of NOT operators. */
 415 };
 416
 417 struct expr *expr_parse__(struct expr_context *);
 418 static void expr_not(struct expr *);
 419 static bool parse_field(struct expr_context *, struct expr_field *);
 420
 421 static bool
 422 expr_error_handle_common(struct expr_context *ctx)
 423 {
 424     if (ctx->error) {
 425         /* Already have an error, suppress this one since the cascade seems
 426          * unlikely to be useful. */
 427         return true;
 428     } else if (ctx->lexer->token.type == LEX_T_ERROR) {
 429         /* The lexer signaled an error.  Nothing at the expression level
 430          * accepts an error token, so we'll inevitably end up here with some
 431          * meaningless parse error.  Report the lexical error instead. */
 432         ctx->error = xstrdup(ctx->lexer->token.s);
 433         return true;
 434     } else {
 435         return false;
 436     }
 437 }
 438
 439 static void OVS_PRINTF_FORMAT(2, 3)
 440 expr_error(struct expr_context *ctx, const char *message, ...)
 441 {
 442     if (expr_error_handle_common(ctx)) {
 443         return;
 444     }
 445
 446     va_list args;
 447     va_start(args, message);
 448     ctx->error = xvasprintf(message, args);
 449     va_end(args);
 450 }
 451
 452 static void OVS_PRINTF_FORMAT(2, 3)
 453 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
 454 {
 455     if (expr_error_handle_common(ctx)) {
 456         return;
 457     }
 458
 459     struct ds s;
 460
 461     ds_init(&s);
 462     ds_put_cstr(&s, "Syntax error ");
 463     if (ctx->lexer->token.type == LEX_T_END) {
 464         ds_put_cstr(&s, "at end of input ");
 465     } else if (ctx->lexer->start) {
 466         ds_put_format(&s, "at `%.*s' ",
 467                       (int) (ctx->lexer->input - ctx->lexer->start),
 468                       ctx->lexer->start);
 469     }
 470
 471     va_list args;
 472     va_start(args, message);
 473     ds_put_format_valist(&s, message, args);
 474     va_end(args);
 475
 476     ctx->error = ds_steal_cstr(&s);
 477 }
 478
 479 static struct expr *
 480 make_cmp__(const struct expr_field *f, enum expr_relop r,
 481              const union expr_constant *c)
 482 {
 483     struct expr *e = xzalloc(sizeof *e);
 484     e->type = EXPR_T_CMP;
 485     e->cmp.symbol = f->symbol;
 486     e->cmp.relop = r;
 487     if (f->symbol->width) {
 488         bitwise_copy(&c->value, sizeof c->value, 0,
 489                      &e->cmp.value, sizeof e->cmp.value, f->ofs,
 490                      f->n_bits);
 491         if (c->masked) {
 492             bitwise_copy(&c->mask, sizeof c->mask, 0,
 493                          &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
 494                          f->n_bits);
 495         } else {
 496             bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
 497                         f->n_bits);
 498         }
 499     } else {
 500         e->cmp.string = xstrdup(c->string);
 501     }
 502     return e;
 503 }
 504
 505 /* Returns the minimum reasonable width for integer constant 'c'. */
 506 static int
 507 expr_constant_width(const union expr_constant *c)
 508 {
 509     if (c->masked) {
 510         return mf_subvalue_width(&c->mask);
 511     }
 512
 513     switch (c->format) {
 514     case LEX_F_DECIMAL:
 515     case LEX_F_HEXADECIMAL:
 516         return mf_subvalue_width(&c->value);
 517
 518     case LEX_F_IPV4:
 519         return 32;
 520
 521     case LEX_F_IPV6:
 522         return 128;
 523
 524     case LEX_F_ETHERNET:
 525         return 48;
 526
 527     default:
 528         OVS_NOT_REACHED();
 529     }
 530 }
 531
 532 static bool
 533 type_check(struct expr_context *ctx, const struct expr_field *f,
 534            struct expr_constant_set *cs)
 535 {
 536     if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
 537         expr_error(ctx, "%s field %s is not compatible with %s constant.",
 538                    f->symbol->width ? "Integer" : "String",
 539                    f->symbol->name,
 540                    cs->type == EXPR_C_INTEGER ? "integer" : "string");
 541         return false;
 542     }
 543
 544     if (f->symbol->width) {
 545         for (size_t i = 0; i < cs->n_values; i++) {
 546             int w = expr_constant_width(&cs->values[i]);
 547             if (w > f->symbol->width) {
 548                 expr_error(ctx, "%d-bit constant is not compatible with "
 549                            "%d-bit field %s.",
 550                            w, f->symbol->width, f->symbol->name);
 551                 return false;
 552             }
 553         }
 554     }
 555
 556     return true;
 557 }
 558
 559 static struct expr *
 560 make_cmp(struct expr_context *ctx,
 561          const struct expr_field *f, enum expr_relop r,
 562          struct expr_constant_set *cs)
 563 {
 564     struct expr *e = NULL;
 565
 566     if (!type_check(ctx, f, cs)) {
 567         goto exit;
 568     }
 569
 570     if (r != EXPR_R_EQ && r != EXPR_R_NE) {
 571         if (cs->in_curlies) {
 572             expr_error(ctx, "Only == and != operators may be used "
 573                        "with value sets.");
 574             goto exit;
 575         }
 576         if (f->symbol->level == EXPR_L_NOMINAL ||
 577             f->symbol->level == EXPR_L_BOOLEAN) {
 578             expr_error(ctx, "Only == and != operators may be used "
 579                        "with %s field %s.",
 580                        expr_level_to_string(f->symbol->level),
 581                        f->symbol->name);
 582             goto exit;
 583         }
 584         if (cs->values[0].masked) {
 585             expr_error(ctx, "Only == and != operators may be used with "
 586                        "masked constants.  Consider using subfields instead "
 587                        "(e.g. eth.src[0..15] > 0x1111 in place of "
 588                        "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
 589             goto exit;
 590         }
 591     }
 592
 593     if (f->symbol->level == EXPR_L_NOMINAL) {
 594         if (f->symbol->expansion) {
 595             ovs_assert(f->symbol->width > 0);
 596             for (size_t i = 0; i < cs->n_values; i++) {
 597                 const union mf_subvalue *value = &cs->values[i].value;
 598                 bool positive = (value->integer & htonll(1)) != 0;
 599                 positive ^= r == EXPR_R_NE;
 600                 positive ^= ctx->not;
 601                 if (!positive) {
 602                     const char *name = f->symbol->name;
 603                     expr_error(ctx, "Nominal predicate %s may only be tested "
 604                                "positively, e.g. `%s' or `%s == 1' but not "
 605                                "`!%s' or `%s == 0'.",
 606                                name, name, name, name, name);
 607                     goto exit;
 608                 }
 609             }
 610         } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
 611             expr_error(ctx, "Nominal field %s may only be tested for "
 612                        "equality (taking enclosing `!' operators into "
 613                        "account).", f->symbol->name);
 614             goto exit;
 615         }
 616     }
 617
 618     e = make_cmp__(f, r, &cs->values[0]);
 619     for (size_t i = 1; i < cs->n_values; i++) {
 620         e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
 621                          e, make_cmp__(f, r, &cs->values[i]));
 622     }
 623 exit:
 624     expr_constant_set_destroy(cs);
 625     return e;
 626 }
 627
 628 static bool
 629 expr_get_int(struct expr_context *ctx, int *value)
 630 {
 631     bool ok = lexer_get_int(ctx->lexer, value);
 632     if (!ok) {
 633         expr_syntax_error(ctx, "expecting small integer.");
 634     }
 635     return ok;
 636 }
 637
 638 static bool
 639 parse_field(struct expr_context *ctx, struct expr_field *f)
 640 {
 641     const struct expr_symbol *symbol;
 642
 643     if (ctx->lexer->token.type != LEX_T_ID) {
 644         expr_syntax_error(ctx, "expecting field name.");
 645         return false;
 646     }
 647
 648     symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
 649     if (!symbol) {
 650         expr_syntax_error(ctx, "expecting field name.");
 651         return false;
 652     }
 653     lexer_get(ctx->lexer);
 654
 655     f->symbol = symbol;
 656     if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
 657         int low, high;
 658
 659         if (!symbol->width) {
 660             expr_error(ctx, "Cannot select subfield of string field %s.",
 661                        symbol->name);
 662             return false;
 663         }
 664
 665         if (!expr_get_int(ctx, &low)) {
 666             return false;
 667         }
 668         if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
 669             if (!expr_get_int(ctx, &high)) {
 670                 return false;
 671             }
 672         } else {
 673             high = low;
 674         }
 675
 676         if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
 677             expr_syntax_error(ctx, "expecting `]'.");
 678             return false;
 679         }
 680
 681         if (low > high) {
 682             expr_error(ctx, "Invalid bit range %d to %d.", low, high);
 683             return false;
 684         } else if (high >= symbol->width) {
 685             expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
 686                        low, high, symbol->width, symbol->name);
 687             return false;
 688         } else if (symbol->level == EXPR_L_NOMINAL
 689                    && (low != 0 || high != symbol->width - 1)) {
 690             expr_error(ctx, "Cannot select subfield of nominal field %s.",
 691                        symbol->name);
 692             return false;
 693         }
 694
 695         f->ofs = low;
 696         f->n_bits = high - low + 1;
 697     } else {
 698         f->ofs = 0;
 699         f->n_bits = symbol->width;
 700     }
 701
 702     return true;
 703 }
 704
 705 static bool
 706 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
 707 {
 708     if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
 709         lexer_get(ctx->lexer);
 710         return true;
 711     } else {
 712         expr_syntax_error(ctx, "expecting relational operator.");
 713         return false;
 714     }
 715 }
 716
 717 static bool
 718 assign_constant_set_type(struct expr_context *ctx,
 719                          struct expr_constant_set *cs,
 720                          enum expr_constant_type type)
 721 {
 722     if (!cs->n_values || cs->type == type) {
 723         cs->type = type;
 724         return true;
 725     } else {
 726         expr_syntax_error(ctx, "expecting %s.",
 727                           cs->type == EXPR_C_INTEGER ? "integer" : "string");
 728         return false;
 729     }
 730 }
 731
 732 static bool
 733 parse_macros(struct expr_context *ctx, struct expr_constant_set *cs,
 734              size_t *allocated_values)
 735 {
 736     struct expr_constant_set *addr_set
 737         = shash_find_data(ctx->macros, ctx->lexer->token.s);
 738     if (!addr_set) {
 739         expr_syntax_error(ctx, "expecting address set name.");
 740         return false;
 741     }
 742
 743     if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
 744         return false;
 745     }
 746
 747     size_t n_values = cs->n_values + addr_set->n_values;
 748     if (n_values >= *allocated_values) {
 749         cs->values = xrealloc(cs->values, n_values * sizeof *cs->values);
 750         *allocated_values = n_values;
 751     }
 752     for (size_t i = 0; i < addr_set->n_values; i++) {
 753         cs->values[cs->n_values++] = addr_set->values[i];
 754     }
 755
 756     return true;
 757 }
 758
 759 static bool
 760 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
 761                size_t *allocated_values)
 762 {
 763     if (cs->n_values >= *allocated_values) {
 764         cs->values = x2nrealloc(cs->values, allocated_values,
 765                                 sizeof *cs->values);
 766     }
 767
 768     if (ctx->lexer->token.type == LEX_T_STRING) {
 769         if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
 770             return false;
 771         }
 772         cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
 773         lexer_get(ctx->lexer);
 774         return true;
 775     } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
 776                ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
 777         if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
 778             return false;
 779         }
 780
 781         union expr_constant *c = &cs->values[cs->n_values++];
 782         c->value = ctx->lexer->token.value;
 783         c->format = ctx->lexer->token.format;
 784         c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
 785         if (c->masked) {
 786             c->mask = ctx->lexer->token.mask;
 787         }
 788         lexer_get(ctx->lexer);
 789         return true;
 790     } else if (ctx->lexer->token.type == LEX_T_MACRO) {
 791         if (!parse_macros(ctx, cs, allocated_values)) {
 792             return false;
 793         }
 794         lexer_get(ctx->lexer);
 795         return true;
 796     } else {
 797         expr_syntax_error(ctx, "expecting constant.");
 798         return false;
 799     }
 800 }
 801
 802 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
 803  * which the caller need not have initialized.  Returns true on success, in
 804  * which case the caller owns 'cs', false on failure, in which case 'cs' is
 805  * indeterminate. */
 806 static bool
 807 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
 808 {
 809     size_t allocated_values = 0;
 810     bool ok;
 811
 812     memset(cs, 0, sizeof *cs);
 813     if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
 814         ok = true;
 815         cs->in_curlies = true;
 816         do {
 817             if (!parse_constant(ctx, cs, &allocated_values)) {
 818                 ok = false;
 819                 break;
 820             }
 821             lexer_match(ctx->lexer, LEX_T_COMMA);
 822         } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
 823     } else {
 824         ok = parse_constant(ctx, cs, &allocated_values);
 825     }
 826     if (!ok) {
 827         expr_constant_set_destroy(cs);
 828     }
 829     return ok;
 830 }
 831
 832 void
 833 expr_constant_set_destroy(struct expr_constant_set *cs)
 834 {
 835     if (cs) {
 836         if (cs->type == EXPR_C_STRING) {
 837             for (size_t i = 0; i < cs->n_values; i++) {
 838                 free(cs->values[i].string);
 839             }
 840         }
 841         free(cs->values);
 842     }
 843 }
 844
 845 /* Adds a macro named 'name' to 'macros', replacing any existing macro with the
 846  * given name. */
 847 void
 848 expr_macros_add(struct shash *macros, const char *name,
 849                 const char *const *values, size_t n_values)
 850 {
 851     /* Replace any existing entry for this name. */
 852     expr_macros_remove(macros, name);
 853
 854     struct expr_constant_set *cs = xzalloc(sizeof *cs);
 855     cs->type = EXPR_C_INTEGER;
 856     cs->in_curlies = true;
 857     cs->n_values = 0;
 858     cs->values = xmalloc(n_values * sizeof *cs->values);
 859     for (size_t i = 0; i < n_values; i++) {
 860         /* Use the lexer to convert each macro into the proper
 861          * integer format. */
 862         struct lexer lex;
 863         lexer_init(&lex, values[i]);
 864         lexer_get(&lex);
 865         if (lex.token.type != LEX_T_INTEGER
 866             && lex.token.type != LEX_T_MASKED_INTEGER) {
 867             VLOG_WARN("Invalid address set entry: '%s', token type: %d",
 868                       values[i], lex.token.type);
 869         } else {
 870             union expr_constant *c = &cs->values[cs->n_values++];
 871             c->value = lex.token.value;
 872             c->format = lex.token.format;
 873             c->masked = lex.token.type == LEX_T_MASKED_INTEGER;
 874             if (c->masked) {
 875                 c->mask = lex.token.mask;
 876             }
 877         }
 878         lexer_destroy(&lex);
 879     }
 880
 881     shash_add(macros, name, cs);
 882 }
 883
 884 void
 885 expr_macros_remove(struct shash *macros, const char *name)
 886 {
 887     struct expr_constant_set *cs = shash_find_and_delete(macros, name);
 888     if (cs) {
 889         expr_constant_set_destroy(cs);
 890         free(cs);
 891     }
 892 }
 893
 894 /* Destroy all contents of 'macros'. */
 895 void
 896 expr_macros_destroy(struct shash *macros)
 897 {
 898     struct shash_node *node, *next;
 899
 900     SHASH_FOR_EACH_SAFE (node, next, macros) {
 901         struct expr_constant_set *cs = node->data;
 902
 903         shash_delete(macros, node);
 904         expr_constant_set_destroy(cs);
 905     }
 906 }
 907
 908 static struct expr *
 909 expr_parse_primary(struct expr_context *ctx, bool *atomic)
 910 {
 911     *atomic = false;
 912     if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
 913         struct expr *e = expr_parse__(ctx);
 914         if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
 915             expr_destroy(e);
 916             expr_syntax_error(ctx, "expecting `)'.");
 917             return NULL;
 918         }
 919         *atomic = true;
 920         return e;
 921     }
 922
 923     if (ctx->lexer->token.type == LEX_T_ID) {
 924         struct expr_field f;
 925         enum expr_relop r;
 926         struct expr_constant_set c;
 927
 928         if (!parse_field(ctx, &f)) {
 929             return NULL;
 930         }
 931
 932         if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
 933             if (f.n_bits > 1 && !ctx->not) {
 934                 expr_error(ctx, "Explicit `!= 0' is required for inequality "
 935                            "test of multibit field against 0.");
 936                 return NULL;
 937             }
 938
 939             *atomic = true;
 940
 941             union expr_constant *cst = xzalloc(sizeof *cst);
 942             cst->format = LEX_F_HEXADECIMAL;
 943             cst->masked = false;
 944
 945             c.type = EXPR_C_INTEGER;
 946             c.values = cst;
 947             c.n_values = 1;
 948             c.in_curlies = false;
 949             return make_cmp(ctx, &f, EXPR_R_NE, &c);
 950         } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
 951             return make_cmp(ctx, &f, r, &c);
 952         } else {
 953             return NULL;
 954         }
 955     } else {
 956         struct expr_constant_set c1;
 957         if (!parse_constant_set(ctx, &c1)) {
 958             return NULL;
 959         }
 960
 961         if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
 962             && c1.n_values == 1
 963             && c1.type == EXPR_C_INTEGER
 964             && c1.values[0].format == LEX_F_DECIMAL
 965             && !c1.values[0].masked
 966             && !c1.in_curlies) {
 967             uint64_t x = ntohll(c1.values[0].value.integer);
 968             if (x <= 1) {
 969                 *atomic = true;
 970                 expr_constant_set_destroy(&c1);
 971                 return expr_create_boolean(x);
 972             }
 973         }
 974
 975         enum expr_relop r1;
 976         struct expr_field f;
 977         if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
 978             expr_constant_set_destroy(&c1);
 979             return NULL;
 980         }
 981
 982         if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
 983             return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
 984         }
 985
 986         enum expr_relop r2;
 987         struct expr_constant_set c2;
 988         if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
 989             expr_constant_set_destroy(&c1);
 990             return NULL;
 991         } else {
 992             /* Reject "1 == field == 2", "1 < field > 2", and so on. */
 993             if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
 994                    (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
 995                   ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
 996                    (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
 997                 expr_error(ctx, "Range expressions must have the form "
 998                            "`x < field < y' or `x > field > y', with each "
 999                            "`<' optionally replaced by `<=' or `>' by `>=').");
1000                 expr_constant_set_destroy(&c1);
1001                 expr_constant_set_destroy(&c2);
1002                 return NULL;
1003             }
1004
1005             struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
1006             struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
1007             if (ctx->error) {
1008                 expr_destroy(e1);
1009                 expr_destroy(e2);
1010                 return NULL;
1011             }
1012             return expr_combine(EXPR_T_AND, e1, e2);
1013         }
1014     }
1015 }
1016
1017 static struct expr *
1018 expr_parse_not(struct expr_context *ctx)
1019 {
1020     bool atomic;
1021
1022     if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
1023         ctx->not = !ctx->not;
1024         struct expr *expr = expr_parse_primary(ctx, &atomic);
1025         ctx->not = !ctx->not;
1026
1027         if (expr) {
1028             if (!atomic) {
1029                 expr_error(ctx, "Missing parentheses around operand of !.");
1030                 expr_destroy(expr);
1031                 return NULL;
1032             }
1033             expr_not(expr);
1034         }
1035         return expr;
1036     } else {
1037         return expr_parse_primary(ctx, &atomic);
1038     }
1039 }
1040
1041 struct expr *
1042 expr_parse__(struct expr_context *ctx)
1043 {
1044     struct expr *e = expr_parse_not(ctx);
1045     if (!e) {
1046         return NULL;
1047     }
1048
1049     enum lex_type lex_type = ctx->lexer->token.type;
1050     if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
1051         enum expr_type expr_type
1052             = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
1053
1054         lexer_get(ctx->lexer);
1055         do {
1056             struct expr *e2 = expr_parse_not(ctx);
1057             if (!e2) {
1058                 expr_destroy(e);
1059                 return NULL;
1060             }
1061             e = expr_combine(expr_type, e, e2);
1062         } while (lexer_match(ctx->lexer, lex_type));
1063         if (ctx->lexer->token.type == LEX_T_LOG_AND
1064             || ctx->lexer->token.type == LEX_T_LOG_OR) {
1065             expr_destroy(e);
1066             expr_error(ctx,
1067                        "&& and || must be parenthesized when used together.");
1068             return NULL;
1069         }
1070     }
1071     return e;
1072 }
1073
1074 /* Parses an expression using the symbols in 'symtab' from 'lexer'.  If
1075  * successful, returns the new expression and sets '*errorp' to NULL.  On
1076  * failure, returns NULL and sets '*errorp' to an explanatory error message.
1077  * The caller must eventually free the returned expression (with
1078  * expr_destroy()) or error (with free()). */
1079 struct expr *
1080 expr_parse(struct lexer *lexer, const struct shash *symtab,
1081            const struct shash *macros, char **errorp)
1082 {
1083     struct expr_context ctx = { .lexer = lexer,
1084                                 .symtab = symtab,
1085                                 .macros = macros };
1086     struct expr *e = expr_parse__(&ctx);
1087     *errorp = ctx.error;
1088     ovs_assert((ctx.error != NULL) != (e != NULL));
1089     return e;
1090 }
1091
1092 /* Like expr_parse(), but the expression is taken from 's'. */
1093 struct expr *
1094 expr_parse_string(const char *s, const struct shash *symtab,
1095                   const struct shash *macros, char **errorp)
1096 {
1097     struct lexer lexer;
1098     struct expr *expr;
1099
1100     lexer_init(&lexer, s);
1101     lexer_get(&lexer);
1102     expr = expr_parse(&lexer, symtab, macros, errorp);
1103     if (!*errorp && lexer.token.type != LEX_T_END) {
1104         *errorp = xstrdup("Extra tokens at end of input.");
1105         expr_destroy(expr);
1106         expr = NULL;
1107     }
1108     lexer_destroy(&lexer);
1109
1110     return expr;
1111 }
1112 \f
1113 static struct expr_symbol *
1114 add_symbol(struct shash *symtab, const char *name, int width,
1115            const char *prereqs, enum expr_level level,
1116            bool must_crossproduct)
1117 {
1118     struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1119     symbol->name = xstrdup(name);
1120     symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1121     symbol->width = width;
1122     symbol->level = level;
1123     symbol->must_crossproduct = must_crossproduct;
1124     shash_add_assert(symtab, symbol->name, symbol);
1125     return symbol;
1126 }
1127
1128 /* Adds field 'id' to symbol table 'symtab' under the given 'name'.  Whenever
1129  * 'name' is referenced, expression annotation (see expr_annotate()) will
1130  * ensure that 'prereqs' are also true.  If 'must_crossproduct' is true, then
1131  * conversion to flows will never attempt to use the field as a conjunctive
1132  * match dimension (see "Crossproducting" in the large comment on struct
1133  * expr_symbol in expr.h for an example).
1134  *
1135  * A given field 'id' must only be used for a single symbol in a symbol table.
1136  * Use subfields to duplicate or subset a field (you can even make a subfield
1137  * include all the bits of the "parent" field if you like). */
1138 struct expr_symbol *
1139 expr_symtab_add_field(struct shash *symtab, const char *name,
1140                       enum mf_field_id id, const char *prereqs,
1141                       bool must_crossproduct)
1142 {
1143     const struct mf_field *field = mf_from_id(id);
1144     struct expr_symbol *symbol;
1145
1146     symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1147                         (field->maskable == MFM_FULLY
1148                          ? EXPR_L_ORDINAL
1149                          : EXPR_L_NOMINAL),
1150                         must_crossproduct);
1151     symbol->field = field;
1152     return symbol;
1153 }
1154
1155 static bool
1156 parse_field_from_string(const char *s, const struct shash *symtab,
1157                         struct expr_field *field, char **errorp)
1158 {
1159     struct lexer lexer;
1160     lexer_init(&lexer, s);
1161     lexer_get(&lexer);
1162
1163     struct expr_context ctx = { .lexer = &lexer, .symtab = symtab };
1164     bool ok = parse_field(&ctx, field);
1165     if (!ok) {
1166         *errorp = ctx.error;
1167     } else if (lexer.token.type != LEX_T_END) {
1168         *errorp = xstrdup("Extra tokens at end of input.");
1169         ok = false;
1170     }
1171
1172     lexer_destroy(&lexer);
1173
1174     return ok;
1175 }
1176
1177 /* Adds 'name' as a subfield of a larger field in 'symtab'.  Whenever
1178  * 'name' is referenced, expression annotation (see expr_annotate()) will
1179  * ensure that 'prereqs' are also true.
1180  *
1181  * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1182  * for the low 12 bits of a larger field named "vlan.tci". */
1183 struct expr_symbol *
1184 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1185                          const char *prereqs, const char *subfield)
1186 {
1187     struct expr_symbol *symbol;
1188     struct expr_field f;
1189     char *error;
1190
1191     if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1192         VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1193         free(error);
1194         return NULL;
1195     }
1196
1197     enum expr_level level = f.symbol->level;
1198     if (level != EXPR_L_ORDINAL) {
1199         VLOG_WARN("can't define %s as subfield of %s field %s",
1200                   name, expr_level_to_string(level), f.symbol->name);
1201     }
1202
1203     symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1204     symbol->expansion = xstrdup(subfield);
1205     return symbol;
1206 }
1207
1208 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1209  * 'prereqs'. */
1210 struct expr_symbol *
1211 expr_symtab_add_string(struct shash *symtab, const char *name,
1212                        enum mf_field_id id, const char *prereqs)
1213 {
1214     const struct mf_field *field = mf_from_id(id);
1215     struct expr_symbol *symbol;
1216
1217     symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1218     symbol->field = field;
1219     return symbol;
1220 }
1221
1222 static enum expr_level
1223 expr_get_level(const struct expr *expr)
1224 {
1225     const struct expr *sub;
1226     enum expr_level level = EXPR_L_ORDINAL;
1227
1228     switch (expr->type) {
1229     case EXPR_T_CMP:
1230         return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1231                 ? EXPR_L_NOMINAL
1232                 : EXPR_L_BOOLEAN);
1233
1234     case EXPR_T_AND:
1235     case EXPR_T_OR:
1236         LIST_FOR_EACH (sub, node, &expr->andor) {
1237             enum expr_level sub_level = expr_get_level(sub);
1238             level = MIN(level, sub_level);
1239         }
1240         return level;
1241
1242     case EXPR_T_BOOLEAN:
1243         return EXPR_L_BOOLEAN;
1244
1245     default:
1246         OVS_NOT_REACHED();
1247     }
1248 }
1249
1250 static enum expr_level
1251 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1252 {
1253     struct expr *expr = expr_parse_string(s, symtab, NULL, errorp);
1254     enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1255     expr_destroy(expr);
1256     return level;
1257 }
1258
1259 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1260  * named 'name' to 'symtab'.  For example, "ip4 && ip4.proto == 6" might be an
1261  * appropriate predicate named "tcp4". */
1262 struct expr_symbol *
1263 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1264                           const char *expansion)
1265 {
1266     struct expr_symbol *symbol;
1267     enum expr_level level;
1268     char *error;
1269
1270     level = expr_parse_level(expansion, symtab, &error);
1271     if (error) {
1272         VLOG_WARN("%s: error parsing %s expansion (%s)",
1273                   expansion, name, error);
1274         free(error);
1275         return NULL;
1276     }
1277
1278     symbol = add_symbol(symtab, name, 1, NULL, level, false);
1279     symbol->expansion = xstrdup(expansion);
1280     return symbol;
1281 }
1282
1283 /* Destroys 'symtab' and all of its symbols. */
1284 void
1285 expr_symtab_destroy(struct shash *symtab)
1286 {
1287     struct shash_node *node, *next;
1288
1289     SHASH_FOR_EACH_SAFE (node, next, symtab) {
1290         struct expr_symbol *symbol = node->data;
1291
1292         shash_delete(symtab, node);
1293         free(symbol->name);
1294         free(symbol->prereqs);
1295         free(symbol->expansion);
1296         free(symbol);
1297     }
1298 }
1299 \f
1300 /* Cloning. */
1301
1302 static struct expr *
1303 expr_clone_cmp(struct expr *expr)
1304 {
1305     struct expr *new = xmemdup(expr, sizeof *expr);
1306     if (!new->cmp.symbol->width) {
1307         new->cmp.string = xstrdup(new->cmp.string);
1308     }
1309     return new;
1310 }
1311
1312 static struct expr *
1313 expr_clone_andor(struct expr *expr)
1314 {
1315     struct expr *new = expr_create_andor(expr->type);
1316     struct expr *sub;
1317
1318     LIST_FOR_EACH (sub, node, &expr->andor) {
1319         struct expr *new_sub = expr_clone(sub);
1320         ovs_list_push_back(&new->andor, &new_sub->node);
1321     }
1322     return new;
1323 }
1324
1325 /* Returns a clone of 'expr'.  This is a "deep copy": neither the returned
1326  * expression nor any of its substructure will be shared with 'expr'. */
1327 struct expr *
1328 expr_clone(struct expr *expr)
1329 {
1330     switch (expr->type) {
1331     case EXPR_T_CMP:
1332         return expr_clone_cmp(expr);
1333
1334     case EXPR_T_AND:
1335     case EXPR_T_OR:
1336         return expr_clone_andor(expr);
1337
1338     case EXPR_T_BOOLEAN:
1339         return expr_create_boolean(expr->boolean);
1340     }
1341     OVS_NOT_REACHED();
1342 }
1343 \f
1344 /* Destroys 'expr' and all of the sub-expressions it references. */
1345 void
1346 expr_destroy(struct expr *expr)
1347 {
1348     if (!expr) {
1349         return;
1350     }
1351
1352     struct expr *sub, *next;
1353
1354     switch (expr->type) {
1355     case EXPR_T_CMP:
1356         if (!expr->cmp.symbol->width) {
1357             free(expr->cmp.string);
1358         }
1359         break;
1360
1361     case EXPR_T_AND:
1362     case EXPR_T_OR:
1363         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1364             ovs_list_remove(&sub->node);
1365             expr_destroy(sub);
1366         }
1367         break;
1368
1369     case EXPR_T_BOOLEAN:
1370         break;
1371     }
1372     free(expr);
1373 }
1374 \f
1375 /* Annotation. */
1376
1377 /* An element in a linked list of symbols.
1378  *
1379  * Used to detect when a symbol is being expanded recursively, to allow
1380  * flagging an error. */
1381 struct annotation_nesting {
1382     struct ovs_list node;
1383     const struct expr_symbol *symbol;
1384 };
1385
1386 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1387                              struct ovs_list *nesting, char **errorp);
1388
1389 static struct expr *
1390 parse_and_annotate(const char *s, const struct shash *symtab,
1391                    struct ovs_list *nesting, char **errorp)
1392 {
1393     char *error;
1394     struct expr *expr;
1395
1396     expr = expr_parse_string(s, symtab, NULL, &error);
1397     if (expr) {
1398         expr = expr_annotate__(expr, symtab, nesting, &error);
1399     }
1400     if (expr) {
1401         *errorp = NULL;
1402     } else {
1403         *errorp = xasprintf("Error parsing expression `%s' encountered as "
1404                             "prerequisite or predicate of initial expression: "
1405                             "%s", s, error);
1406         free(error);
1407     }
1408     return expr;
1409 }
1410
1411 static struct expr *
1412 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1413                   struct ovs_list *nesting, char **errorp)
1414 {
1415     const struct expr_symbol *symbol = expr->cmp.symbol;
1416     const struct annotation_nesting *iter;
1417     LIST_FOR_EACH (iter, node, nesting) {
1418         if (iter->symbol == symbol) {
1419             *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1420                                 symbol->name);
1421             expr_destroy(expr);
1422             return NULL;
1423         }
1424     }
1425
1426     struct annotation_nesting an;
1427     an.symbol = symbol;
1428     ovs_list_push_back(nesting, &an.node);
1429
1430     struct expr *prereqs = NULL;
1431     if (symbol->prereqs) {
1432         prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1433         if (!prereqs) {
1434             goto error;
1435         }
1436     }
1437
1438     if (symbol->expansion) {
1439         if (symbol->level == EXPR_L_ORDINAL) {
1440             struct expr_field field;
1441
1442             if (!parse_field_from_string(symbol->expansion, symtab,
1443                                          &field, errorp)) {
1444                 goto error;
1445             }
1446
1447             expr->cmp.symbol = field.symbol;
1448             mf_subvalue_shift(&expr->cmp.value, field.ofs);
1449             mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1450         } else {
1451             struct expr *expansion;
1452
1453             expansion = parse_and_annotate(symbol->expansion, symtab,
1454                                            nesting, errorp);
1455             if (!expansion) {
1456                 goto error;
1457             }
1458
1459             bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1460             positive ^= expr->cmp.relop == EXPR_R_NE;
1461             if (!positive) {
1462                 expr_not(expansion);
1463             }
1464
1465             expr_destroy(expr);
1466             expr = expansion;
1467         }
1468     }
1469
1470     ovs_list_remove(&an.node);
1471     return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1472
1473 error:
1474     expr_destroy(expr);
1475     expr_destroy(prereqs);
1476     ovs_list_remove(&an.node);
1477     return NULL;
1478 }
1479
1480 struct expr *
1481 expr_annotate__(struct expr *expr, const struct shash *symtab,
1482                 struct ovs_list *nesting, char **errorp)
1483 {
1484     switch (expr->type) {
1485     case EXPR_T_CMP:
1486         return expr_annotate_cmp(expr, symtab, nesting, errorp);
1487
1488     case EXPR_T_AND:
1489     case EXPR_T_OR: {
1490         struct expr *sub, *next;
1491
1492         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1493             ovs_list_remove(&sub->node);
1494             struct expr *new_sub = expr_annotate__(sub, symtab,
1495                                                    nesting, errorp);
1496             if (!new_sub) {
1497                 expr_destroy(expr);
1498                 return NULL;
1499             }
1500             expr_insert_andor(expr, next, new_sub);
1501         }
1502         *errorp = NULL;
1503         return expr;
1504     }
1505
1506     case EXPR_T_BOOLEAN:
1507         *errorp = NULL;
1508         return expr;
1509
1510     default:
1511         OVS_NOT_REACHED();
1512     }
1513 }
1514
1515 /* "Annotates" 'expr', which does the following:
1516  *
1517  *     - Applies prerequisites, by locating each comparison operator whose
1518  *       field has a prerequisite and adding a logical AND against those
1519  *       prerequisites.
1520  *
1521  *     - Expands references to subfield symbols, by replacing them by
1522  *       references to their underlying field symbols (suitably shifted).
1523  *
1524  *     - Expands references to predicate symbols, by replacing them by the
1525  *       expressions that they expand to.
1526  *
1527  * In each case, annotation occurs recursively as necessary.
1528  *
1529  * On failure, returns NULL and sets '*errorp' to an explanatory error
1530  * message, which the caller must free. */
1531 struct expr *
1532 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1533 {
1534     struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1535     return expr_annotate__(expr, symtab, &nesting, errorp);
1536 }
1537 \f
1538 static struct expr *
1539 expr_simplify_ne(struct expr *expr)
1540 {
1541     struct expr *new = NULL;
1542     const union mf_subvalue *value = &expr->cmp.value;
1543     const union mf_subvalue *mask = &expr->cmp.mask;
1544     int w = expr->cmp.symbol->width;
1545     int i;
1546
1547     for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1548         struct expr *e;
1549
1550         e = xzalloc(sizeof *e);
1551         e->type = EXPR_T_CMP;
1552         e->cmp.symbol = expr->cmp.symbol;
1553         e->cmp.relop = EXPR_R_EQ;
1554         bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1555                         !bitwise_get_bit(value, sizeof *value, i));
1556         bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1557
1558         new = expr_combine(EXPR_T_OR, new, e);
1559     }
1560     ovs_assert(new);
1561
1562     expr_destroy(expr);
1563
1564     return new;
1565 }
1566
1567 static struct expr *
1568 expr_simplify_relational(struct expr *expr)
1569 {
1570     const union mf_subvalue *value = &expr->cmp.value;
1571     int start, n_bits, end;
1572
1573     find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1574                        &start, &n_bits);
1575     ovs_assert(n_bits > 0);
1576     end = start + n_bits;
1577
1578     struct expr *new;
1579     if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1580         new = xmemdup(expr, sizeof *expr);
1581         new->cmp.relop = EXPR_R_EQ;
1582     } else {
1583         new = NULL;
1584     }
1585
1586     bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1587     for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1588          z < end;
1589          z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1590         struct expr *e;
1591
1592         e = xmemdup(expr, sizeof *expr);
1593         e->cmp.relop = EXPR_R_EQ;
1594         bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1595         bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1596         bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1597         new = expr_combine(EXPR_T_OR, new, e);
1598     }
1599     expr_destroy(expr);
1600     return new ? new : expr_create_boolean(false);
1601 }
1602
1603 /* Takes ownership of 'expr' and returns an equivalent expression whose
1604  * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1605 struct expr *
1606 expr_simplify(struct expr *expr)
1607 {
1608     struct expr *sub, *next;
1609
1610     switch (expr->type) {
1611     case EXPR_T_CMP:
1612         return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1613                 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1614                 : expr_simplify_relational(expr));
1615
1616     case EXPR_T_AND:
1617     case EXPR_T_OR:
1618         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1619             ovs_list_remove(&sub->node);
1620             expr_insert_andor(expr, next, expr_simplify(sub));
1621         }
1622         return expr_fix(expr);
1623
1624     case EXPR_T_BOOLEAN:
1625         return expr;
1626     }
1627     OVS_NOT_REACHED();
1628 }
1629 \f
1630 static const struct expr_symbol *
1631 expr_is_cmp(const struct expr *expr)
1632 {
1633     switch (expr->type) {
1634     case EXPR_T_CMP:
1635         return expr->cmp.symbol;
1636
1637     case EXPR_T_AND:
1638     case EXPR_T_OR: {
1639         const struct expr_symbol *prev = NULL;
1640         struct expr *sub;
1641
1642         LIST_FOR_EACH (sub, node, &expr->andor) {
1643             const struct expr_symbol *symbol = expr_is_cmp(sub);
1644             if (!symbol || (prev && symbol != prev)) {
1645                 return NULL;
1646             }
1647             prev = symbol;
1648         }
1649         return prev;
1650     }
1651
1652     case EXPR_T_BOOLEAN:
1653         return NULL;
1654
1655     default:
1656         OVS_NOT_REACHED();
1657     }
1658 }
1659
1660 struct expr_sort {
1661     struct expr *expr;
1662     const struct expr_symbol *relop;
1663     enum expr_type type;
1664 };
1665
1666 static int
1667 compare_expr_sort(const void *a_, const void *b_)
1668 {
1669     const struct expr_sort *a = a_;
1670     const struct expr_sort *b = b_;
1671
1672     if (a->type != b->type) {
1673         return a->type < b->type ? -1 : 1;
1674     } else if (a->relop) {
1675         int cmp = strcmp(a->relop->name, b->relop->name);
1676         if (cmp) {
1677             return cmp;
1678         }
1679
1680         enum expr_type a_type = a->expr->type;
1681         enum expr_type b_type = a->expr->type;
1682         return a_type < b_type ? -1 : a_type > b_type;
1683     } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1684         size_t a_len = ovs_list_size(&a->expr->andor);
1685         size_t b_len = ovs_list_size(&b->expr->andor);
1686         return a_len < b_len ? -1 : a_len > b_len;
1687     } else {
1688         return 0;
1689     }
1690 }
1691
1692 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1693
1694 static bool
1695 disjunction_matches_string(const struct expr *or, const char *s)
1696 {
1697     const struct expr *sub;
1698
1699     LIST_FOR_EACH (sub, node, &or->andor) {
1700         if (!strcmp(sub->cmp.string, s)) {
1701             return true;
1702         }
1703     }
1704
1705     return false;
1706 }
1707
1708 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1709  * string-typed 'symbol'. */
1710 static struct expr *
1711 crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1712 {
1713     ovs_assert(!ovs_list_is_short(&expr->andor));
1714
1715     struct expr *singleton = NULL;
1716
1717     /* First crush each subexpression into either a single EXPR_T_CMP or an
1718      * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1719     struct expr *sub, *next = NULL;
1720     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1721         ovs_list_remove(&sub->node);
1722         struct expr *new = crush_cmps(sub, symbol);
1723         switch (new->type) {
1724         case EXPR_T_CMP:
1725             if (!singleton) {
1726                 ovs_list_insert(&next->node, &new->node);
1727                 singleton = new;
1728             } else {
1729                 bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1730                 expr_destroy(new);
1731                 if (!match) {
1732                     expr_destroy(expr);
1733                     return expr_create_boolean(false);
1734                 }
1735             }
1736             break;
1737         case EXPR_T_AND:
1738             OVS_NOT_REACHED();
1739         case EXPR_T_OR:
1740             ovs_list_insert(&next->node, &new->node);
1741             break;
1742         case EXPR_T_BOOLEAN:
1743             if (!new->boolean) {
1744                 expr_destroy(expr);
1745                 return new;
1746             }
1747             free(new);
1748             break;
1749         }
1750     }
1751
1752     /* If we have a singleton, then the result is either the singleton itself
1753      * (if the ORs allow the singleton) or false. */
1754     if (singleton) {
1755         LIST_FOR_EACH (sub, node, &expr->andor) {
1756             if (sub->type == EXPR_T_OR
1757                 && !disjunction_matches_string(sub, singleton->cmp.string)) {
1758                 expr_destroy(expr);
1759                 return expr_create_boolean(false);
1760             }
1761         }
1762         ovs_list_remove(&singleton->node);
1763         expr_destroy(expr);
1764         return singleton;
1765     }
1766
1767     /* Otherwise the result is the intersection of all of the ORs. */
1768     struct sset result = SSET_INITIALIZER(&result);
1769     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1770         struct sset strings = SSET_INITIALIZER(&strings);
1771         const struct expr *s;
1772         LIST_FOR_EACH (s, node, &sub->andor) {
1773             sset_add(&strings, s->cmp.string);
1774         }
1775         if (sset_is_empty(&result)) {
1776             sset_swap(&result, &strings);
1777         } else {
1778             sset_intersect(&result, &strings);
1779         }
1780         sset_destroy(&strings);
1781
1782         if (sset_is_empty(&result)) {
1783             expr_destroy(expr);
1784             sset_destroy(&result);
1785             return expr_create_boolean(false);
1786         }
1787     }
1788
1789     expr_destroy(expr);
1790     expr = expr_create_andor(EXPR_T_OR);
1791
1792     const char *string;
1793     SSET_FOR_EACH (string, &result) {
1794         sub = xmalloc(sizeof *sub);
1795         sub->type = EXPR_T_CMP;
1796         sub->cmp.symbol = symbol;
1797         sub->cmp.string = xstrdup(string);
1798         ovs_list_push_back(&expr->andor, &sub->node);
1799     }
1800     sset_destroy(&result);
1801     return expr_fix(expr);
1802 }
1803
1804 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1805  * numeric-typed 'symbol'. */
1806 static struct expr *
1807 crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1808 {
1809     ovs_assert(!ovs_list_is_short(&expr->andor));
1810
1811     union mf_subvalue value, mask;
1812     memset(&value, 0, sizeof value);
1813     memset(&mask, 0, sizeof mask);
1814
1815     struct expr *sub, *next = NULL;
1816     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1817         ovs_list_remove(&sub->node);
1818         struct expr *new = crush_cmps(sub, symbol);
1819         switch (new->type) {
1820         case EXPR_T_CMP:
1821             if (!mf_subvalue_intersect(&value, &mask,
1822                                        &new->cmp.value, &new->cmp.mask,
1823                                        &value, &mask)) {
1824                 expr_destroy(new);
1825                 expr_destroy(expr);
1826                 return expr_create_boolean(false);
1827             }
1828             expr_destroy(new);
1829             break;
1830         case EXPR_T_AND:
1831             OVS_NOT_REACHED();
1832         case EXPR_T_OR:
1833             ovs_list_insert(&next->node, &new->node);
1834             break;
1835         case EXPR_T_BOOLEAN:
1836             if (!new->boolean) {
1837                 expr_destroy(expr);
1838                 return new;
1839             }
1840             expr_destroy(new);
1841             break;
1842         }
1843     }
1844     if (ovs_list_is_empty(&expr->andor)) {
1845         if (is_all_zeros(&mask, sizeof mask)) {
1846             expr_destroy(expr);
1847             return expr_create_boolean(true);
1848         } else {
1849             struct expr *cmp;
1850             cmp = xmalloc(sizeof *cmp);
1851             cmp->type = EXPR_T_CMP;
1852             cmp->cmp.symbol = symbol;
1853             cmp->cmp.relop = EXPR_R_EQ;
1854             cmp->cmp.value = value;
1855             cmp->cmp.mask = mask;
1856             expr_destroy(expr);
1857             return cmp;
1858         }
1859     } else if (ovs_list_is_short(&expr->andor)) {
1860         /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1861          * computed as "a && b", etc. */
1862         struct expr *disjuncts = expr_from_node(ovs_list_pop_front(&expr->andor));
1863         struct expr *or;
1864
1865         or = xmalloc(sizeof *or);
1866         or->type = EXPR_T_OR;
1867         ovs_list_init(&or->andor);
1868
1869         ovs_assert(disjuncts->type == EXPR_T_OR);
1870         LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1871             ovs_assert(sub->type == EXPR_T_CMP);
1872             ovs_list_remove(&sub->node);
1873             if (mf_subvalue_intersect(&value, &mask,
1874                                       &sub->cmp.value, &sub->cmp.mask,
1875                                       &sub->cmp.value, &sub->cmp.mask)) {
1876                 ovs_list_push_back(&or->andor, &sub->node);
1877             } else {
1878                 expr_destroy(sub);
1879             }
1880         }
1881         free(disjuncts);
1882         free(expr);
1883         if (ovs_list_is_empty(&or->andor)) {
1884             free(or);
1885             return expr_create_boolean(false);
1886         } else if (ovs_list_is_short(&or->andor)) {
1887             struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1888             free(or);
1889             return cmp;
1890         } else {
1891             return or;
1892         }
1893     } else {
1894         /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1895          *           "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1896         struct expr *as = expr_from_node(ovs_list_pop_front(&expr->andor));
1897         struct expr *bs = expr_from_node(ovs_list_pop_front(&expr->andor));
1898         struct expr *new = NULL;
1899         struct expr *or;
1900
1901         or = xmalloc(sizeof *or);
1902         or->type = EXPR_T_OR;
1903         ovs_list_init(&or->andor);
1904
1905         struct expr *a;
1906         LIST_FOR_EACH (a, node, &as->andor) {
1907             union mf_subvalue a_value, a_mask;
1908
1909             ovs_assert(a->type == EXPR_T_CMP);
1910             if (!mf_subvalue_intersect(&value, &mask,
1911                                        &a->cmp.value, &a->cmp.mask,
1912                                        &a_value, &a_mask)) {
1913                 continue;
1914             }
1915
1916             struct expr *b;
1917             LIST_FOR_EACH (b, node, &bs->andor) {
1918                 ovs_assert(b->type == EXPR_T_CMP);
1919                 if (!new) {
1920                     new = xmalloc(sizeof *new);
1921                     new->type = EXPR_T_CMP;
1922                     new->cmp.symbol = symbol;
1923                     new->cmp.relop = EXPR_R_EQ;
1924                 }
1925                 if (mf_subvalue_intersect(&a_value, &a_mask,
1926                                           &b->cmp.value, &b->cmp.mask,
1927                                           &new->cmp.value, &new->cmp.mask)) {
1928                     ovs_list_push_back(&or->andor, &new->node);
1929                     new = NULL;
1930                 }
1931             }
1932         }
1933         expr_destroy(as);
1934         expr_destroy(bs);
1935         free(new);
1936
1937         if (ovs_list_is_empty(&or->andor)) {
1938             expr_destroy(expr);
1939             free(or);
1940             return expr_create_boolean(false);
1941         } else if (ovs_list_is_short(&or->andor)) {
1942             struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1943             free(or);
1944             if (ovs_list_is_empty(&expr->andor)) {
1945                 expr_destroy(expr);
1946                 return crush_cmps(cmp, symbol);
1947             } else {
1948                 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1949             }
1950         } else if (!ovs_list_is_empty(&expr->andor)) {
1951             struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1952             ovs_assert(!ovs_list_is_short(&e->andor));
1953             return crush_cmps(e, symbol);
1954         } else {
1955             expr_destroy(expr);
1956             return crush_cmps(or, symbol);
1957         }
1958     }
1959 }
1960
1961 static int
1962 compare_cmps_3way(const struct expr *a, const struct expr *b)
1963 {
1964     ovs_assert(a->cmp.symbol == b->cmp.symbol);
1965     if (!a->cmp.symbol->width) {
1966         return strcmp(a->cmp.string, b->cmp.string);
1967     } else {
1968         int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1969         if (!d) {
1970             d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1971         }
1972         return d;
1973     }
1974 }
1975
1976 static int
1977 compare_cmps_cb(const void *a_, const void *b_)
1978 {
1979     const struct expr *const *ap = a_;
1980     const struct expr *const *bp = b_;
1981     const struct expr *a = *ap;
1982     const struct expr *b = *bp;
1983     return compare_cmps_3way(a, b);
1984 }
1985
1986 /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
1987 static struct expr *
1988 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1989 {
1990     struct expr *sub, *next = NULL;
1991
1992     /* First, crush all the subexpressions.  That might eliminate the
1993      * OR-expression entirely; if so, return the result.  Otherwise, 'expr'
1994      * is now a disjunction of cmps over the same symbol. */
1995     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1996         ovs_list_remove(&sub->node);
1997         expr_insert_andor(expr, next, crush_cmps(sub, symbol));
1998     }
1999     expr = expr_fix(expr);
2000     if (expr->type != EXPR_T_OR) {
2001         return expr;
2002     }
2003
2004     /* Sort subexpressions by value and mask, to bring together duplicates. */
2005     size_t n = ovs_list_size(&expr->andor);
2006     struct expr **subs = xmalloc(n * sizeof *subs);
2007
2008     size_t i = 0;
2009     LIST_FOR_EACH (sub, node, &expr->andor) {
2010         subs[i++] = sub;
2011     }
2012     ovs_assert(i == n);
2013
2014     qsort(subs, n, sizeof *subs, compare_cmps_cb);
2015
2016     /* Eliminate duplicates. */
2017     ovs_list_init(&expr->andor);
2018     ovs_list_push_back(&expr->andor, &subs[0]->node);
2019     for (i = 1; i < n; i++) {
2020         struct expr *a = expr_from_node(ovs_list_back(&expr->andor));
2021         struct expr *b = subs[i];
2022         if (compare_cmps_3way(a, b)) {
2023             ovs_list_push_back(&expr->andor, &b->node);
2024         } else {
2025             expr_destroy(b);
2026         }
2027     }
2028     free(subs);
2029     return expr_fix(expr);
2030 }
2031
2032 /* Takes ownership of 'expr', which must be a cmp in the sense determined by
2033  * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
2034  * Returns an equivalent expression owned by the caller that is a single
2035  * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
2036 static struct expr *
2037 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
2038 {
2039     switch (expr->type) {
2040     case EXPR_T_OR:
2041         return crush_or(expr, symbol);
2042
2043     case EXPR_T_AND:
2044         return (symbol->width
2045                 ? crush_and_numeric(expr, symbol)
2046                 : crush_and_string(expr, symbol));
2047
2048     case EXPR_T_CMP:
2049         return expr;
2050
2051     case EXPR_T_BOOLEAN:
2052         return expr;
2053
2054     default:
2055         OVS_NOT_REACHED();
2056     }
2057 }
2058
2059 static struct expr *
2060 expr_sort(struct expr *expr)
2061 {
2062     size_t n = ovs_list_size(&expr->andor);
2063     struct expr_sort *subs = xmalloc(n * sizeof *subs);
2064     struct expr *sub;
2065     size_t i;
2066
2067     i = 0;
2068     LIST_FOR_EACH (sub, node, &expr->andor) {
2069         subs[i].expr = sub;
2070         subs[i].relop = expr_is_cmp(sub);
2071         subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2072         i++;
2073     }
2074     ovs_assert(i == n);
2075
2076     qsort(subs, n, sizeof *subs, compare_expr_sort);
2077
2078     ovs_list_init(&expr->andor);
2079     for (int i = 0; i < n; ) {
2080         if (subs[i].relop) {
2081             int j;
2082             for (j = i + 1; j < n; j++) {
2083                 if (subs[i].relop != subs[j].relop) {
2084                     break;
2085                 }
2086             }
2087
2088             struct expr *crushed;
2089             if (j == i + 1) {
2090                 crushed = crush_cmps(subs[i].expr, subs[i].relop);
2091             } else {
2092                 struct expr *combined = subs[i].expr;
2093                 for (int k = i + 1; k < j; k++) {
2094                     combined = expr_combine(EXPR_T_AND, combined,
2095                                             subs[k].expr);
2096                 }
2097                 ovs_assert(!ovs_list_is_short(&combined->andor));
2098                 crushed = crush_cmps(combined, subs[i].relop);
2099             }
2100             if (crushed->type == EXPR_T_BOOLEAN) {
2101                 if (!crushed->boolean) {
2102                     for (int k = j; k < n; k++) {
2103                         expr_destroy(subs[k].expr);
2104                     }
2105                     expr_destroy(expr);
2106                     expr = crushed;
2107                     break;
2108                 } else {
2109                     free(crushed);
2110                 }
2111             } else {
2112                 expr = expr_combine(EXPR_T_AND, expr, crushed);
2113             }
2114             i = j;
2115         } else {
2116             expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2117         }
2118     }
2119     free(subs);
2120
2121     return expr;
2122 }
2123
2124 static struct expr *expr_normalize_or(struct expr *expr);
2125
2126 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2127  * a clause is a cmp or a disjunction of cmps on a single field. */
2128 static struct expr *
2129 expr_normalize_and(struct expr *expr)
2130 {
2131     ovs_assert(expr->type == EXPR_T_AND);
2132
2133     expr = expr_sort(expr);
2134     if (expr->type != EXPR_T_AND) {
2135         ovs_assert(expr->type == EXPR_T_BOOLEAN);
2136         return expr;
2137     }
2138
2139     struct expr *a, *b;
2140     LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2141         if (&b->node == &expr->andor
2142             || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2143             || a->cmp.symbol != b->cmp.symbol) {
2144             continue;
2145         } else if (a->cmp.symbol->width
2146                    ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2147                                            &b->cmp.value, &b->cmp.mask,
2148                                            &b->cmp.value, &b->cmp.mask)
2149                    : !strcmp(a->cmp.string, b->cmp.string)) {
2150             ovs_list_remove(&a->node);
2151             expr_destroy(a);
2152         } else {
2153             expr_destroy(expr);
2154             return expr_create_boolean(false);
2155         }
2156     }
2157     if (ovs_list_is_short(&expr->andor)) {
2158         struct expr *sub = expr_from_node(ovs_list_front(&expr->andor));
2159         free(expr);
2160         return sub;
2161     }
2162
2163     struct expr *sub;
2164     LIST_FOR_EACH (sub, node, &expr->andor) {
2165         if (sub->type == EXPR_T_CMP) {
2166             continue;
2167         }
2168
2169         ovs_assert(sub->type == EXPR_T_OR);
2170         const struct expr_symbol *symbol = expr_is_cmp(sub);
2171         if (!symbol || symbol->must_crossproduct) {
2172             struct expr *or = expr_create_andor(EXPR_T_OR);
2173             struct expr *k;
2174
2175             LIST_FOR_EACH (k, node, &sub->andor) {
2176                 struct expr *and = expr_create_andor(EXPR_T_AND);
2177                 struct expr *m;
2178
2179                 LIST_FOR_EACH (m, node, &expr->andor) {
2180                     struct expr *term = m == sub ? k : m;
2181                     if (term->type == EXPR_T_AND) {
2182                         struct expr *p;
2183
2184                         LIST_FOR_EACH (p, node, &term->andor) {
2185                             struct expr *new = expr_clone(p);
2186                             ovs_list_push_back(&and->andor, &new->node);
2187                         }
2188                     } else {
2189                         struct expr *new = expr_clone(term);
2190                         ovs_list_push_back(&and->andor, &new->node);
2191                     }
2192                 }
2193                 ovs_list_push_back(&or->andor, &and->node);
2194             }
2195             expr_destroy(expr);
2196             return expr_normalize_or(or);
2197         }
2198     }
2199     return expr;
2200 }
2201
2202 static struct expr *
2203 expr_normalize_or(struct expr *expr)
2204 {
2205     struct expr *sub, *next;
2206
2207     LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2208         if (sub->type == EXPR_T_AND) {
2209             ovs_list_remove(&sub->node);
2210
2211             struct expr *new = expr_normalize_and(sub);
2212             if (new->type == EXPR_T_BOOLEAN) {
2213                 if (new->boolean) {
2214                     expr_destroy(expr);
2215                     return new;
2216                 }
2217                 free(new);
2218             } else {
2219                 expr_insert_andor(expr, next, new);
2220             }
2221         } else {
2222             ovs_assert(sub->type == EXPR_T_CMP);
2223         }
2224     }
2225     if (ovs_list_is_empty(&expr->andor)) {
2226         free(expr);
2227         return expr_create_boolean(false);
2228     }
2229     if (ovs_list_is_short(&expr->andor)) {
2230         struct expr *sub = expr_from_node(ovs_list_pop_front(&expr->andor));
2231         free(expr);
2232         return sub;
2233     }
2234
2235     return expr;
2236 }
2237
2238 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2239  * an expression in terms of only relationals, AND, and OR.  Returns either a
2240  * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2241  * clause is a cmp or a disjunction of cmps on a single field.  This form is
2242  * significant because it is a form that can be directly converted to OpenFlow
2243  * flows with the Open vSwitch "conjunctive match" extension.
2244  *
2245  * 'expr' must already have been simplified, with expr_simplify(). */
2246 struct expr *
2247 expr_normalize(struct expr *expr)
2248 {
2249     switch (expr->type) {
2250     case EXPR_T_CMP:
2251         return expr;
2252
2253     case EXPR_T_AND:
2254         return expr_normalize_and(expr);
2255
2256     case EXPR_T_OR:
2257         return expr_normalize_or(expr);
2258
2259     case EXPR_T_BOOLEAN:
2260         return expr;
2261     }
2262     OVS_NOT_REACHED();
2263 }
2264 \f
2265 /* Creates, initializes, and returns a new 'struct expr_match'.  If 'm' is
2266  * nonnull then it is copied into the new expr_match, otherwise the new
2267  * expr_match's 'match' member is initialized to a catch-all match for the
2268  * caller to refine in-place.
2269  *
2270  * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2271  * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2272  * expr_match will not have any conjunctions.
2273  *
2274  * The caller should use expr_match_add() to add the expr_match to a hash table
2275  * after it is finalized. */
2276 static struct expr_match *
2277 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2278                uint32_t conj_id)
2279 {
2280     struct expr_match *match = xmalloc(sizeof *match);
2281     if (m) {
2282         match->match = *m;
2283     } else {
2284         match_init_catchall(&match->match);
2285     }
2286     if (conj_id) {
2287         match->conjunctions = xmalloc(sizeof *match->conjunctions);
2288         match->conjunctions[0].id = conj_id;
2289         match->conjunctions[0].clause = clause;
2290         match->conjunctions[0].n_clauses = n_clauses;
2291         match->n = 1;
2292         match->allocated = 1;
2293     } else {
2294         match->conjunctions = NULL;
2295         match->n = 0;
2296         match->allocated = 0;
2297     }
2298     return match;
2299 }
2300
2301 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2302  * 'match'.
2303  *
2304  * This might actually destroy 'match' because it gets merged together with
2305  * some existing conjunction.*/
2306 static void
2307 expr_match_add(struct hmap *matches, struct expr_match *match)
2308 {
2309     uint32_t hash = match_hash(&match->match, 0);
2310     struct expr_match *m;
2311
2312     HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2313         if (match_equal(&m->match, &match->match)) {
2314             if (!m->n || !match->n) {
2315                 free(m->conjunctions);
2316                 m->conjunctions = NULL;
2317                 m->n = 0;
2318                 m->allocated = 0;
2319             } else {
2320                 ovs_assert(match->n == 1);
2321                 if (m->n >= m->allocated) {
2322                     m->conjunctions = x2nrealloc(m->conjunctions,
2323                                                  &m->allocated,
2324                                                  sizeof *m->conjunctions);
2325                 }
2326                 m->conjunctions[m->n++] = match->conjunctions[0];
2327             }
2328             free(match->conjunctions);
2329             free(match);
2330             return;
2331         }
2332     }
2333
2334     hmap_insert(matches, &match->hmap_node, hash);
2335 }
2336
2337 static bool
2338 constrain_match(const struct expr *expr,
2339                 bool (*lookup_port)(const void *aux, const char *port_name,
2340                                     unsigned int *portp),
2341                 const void *aux, struct match *m)
2342 {
2343     ovs_assert(expr->type == EXPR_T_CMP);
2344     if (expr->cmp.symbol->width) {
2345         mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2346                          &expr->cmp.mask, m);
2347     } else {
2348         unsigned int port;
2349         if (!lookup_port(aux, expr->cmp.string, &port)) {
2350             return false;
2351         }
2352
2353         struct mf_subfield sf;
2354         sf.field = expr->cmp.symbol->field;
2355         sf.ofs = 0;
2356         sf.n_bits = expr->cmp.symbol->field->n_bits;
2357
2358         union mf_subvalue x;
2359         memset(&x, 0, sizeof x);
2360         x.integer = htonll(port);
2361
2362         mf_write_subfield(&sf, &x, m);
2363     }
2364     return true;
2365 }
2366
2367 static bool
2368 add_disjunction(const struct expr *or,
2369                 bool (*lookup_port)(const void *aux, const char *port_name,
2370                                     unsigned int *portp),
2371                 const void *aux,
2372                 struct match *m, uint8_t clause, uint8_t n_clauses,
2373                 uint32_t conj_id, struct hmap *matches)
2374 {
2375     struct expr *sub;
2376     int n = 0;
2377
2378     ovs_assert(or->type == EXPR_T_OR);
2379     LIST_FOR_EACH (sub, node, &or->andor) {
2380         struct expr_match *match = expr_match_new(m, clause, n_clauses,
2381                                                   conj_id);
2382         if (constrain_match(sub, lookup_port, aux, &match->match)) {
2383             expr_match_add(matches, match);
2384             n++;
2385         } else {
2386             free(match->conjunctions);
2387             free(match);
2388         }
2389     }
2390
2391     /* If n == 1, then this didn't really need to be a disjunction.  Oh well,
2392      * that shouldn't happen much. */
2393     return n > 0;
2394 }
2395
2396 static void
2397 add_conjunction(const struct expr *and,
2398                 bool (*lookup_port)(const void *aux, const char *port_name,
2399                                     unsigned int *portp),
2400                 const void *aux, uint32_t *n_conjsp, struct hmap *matches)
2401 {
2402     struct match match;
2403     int n_clauses = 0;
2404     struct expr *sub;
2405
2406     match_init_catchall(&match);
2407
2408     ovs_assert(and->type == EXPR_T_AND);
2409     LIST_FOR_EACH (sub, node, &and->andor) {
2410         switch (sub->type) {
2411         case EXPR_T_CMP:
2412             if (!constrain_match(sub, lookup_port, aux, &match)) {
2413                 return;
2414             }
2415             break;
2416         case EXPR_T_OR:
2417             n_clauses++;
2418             break;
2419         case EXPR_T_AND:
2420         case EXPR_T_BOOLEAN:
2421             OVS_NOT_REACHED();
2422         }
2423     }
2424
2425     if (!n_clauses) {
2426         expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2427     } else if (n_clauses == 1) {
2428         LIST_FOR_EACH (sub, node, &and->andor) {
2429             if (sub->type == EXPR_T_OR) {
2430                 add_disjunction(sub, lookup_port, aux, &match, 0, 0, 0,
2431                                 matches);
2432             }
2433         }
2434     } else {
2435         int clause = 0;
2436         (*n_conjsp)++;
2437         LIST_FOR_EACH (sub, node, &and->andor) {
2438             if (sub->type == EXPR_T_OR) {
2439                 if (!add_disjunction(sub, lookup_port, aux, &match, clause++,
2440                                      n_clauses, *n_conjsp, matches)) {
2441                     /* This clause can't ever match, so we might as well skip
2442                      * adding the other clauses--the overall disjunctive flow
2443                      * can't ever match.  Ideally we would also back out all of
2444                      * the clauses we already added, but that seems like a lot
2445                      * of trouble for a case that might never occur in
2446                      * practice. */
2447                     return;
2448                 }
2449             }
2450         }
2451
2452         /* Add the flow that matches on conj_id. */
2453         match_set_conj_id(&match, *n_conjsp);
2454         expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2455     }
2456 }
2457
2458 static void
2459 add_cmp_flow(const struct expr *cmp,
2460              bool (*lookup_port)(const void *aux, const char *port_name,
2461                                  unsigned int *portp),
2462              const void *aux, struct hmap *matches)
2463 {
2464     struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2465     if (constrain_match(cmp, lookup_port, aux, &m->match)) {
2466         expr_match_add(matches, m);
2467     } else {
2468         free(m);
2469     }
2470 }
2471
2472 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2473  * a collection of Open vSwitch flows in 'matches', which this function
2474  * initializes to an hmap of "struct expr_match" structures.  Returns the
2475  * number of conjunctive match IDs consumed by 'matches', which uses
2476  * conjunctive match IDs beginning with 0; the caller must offset or remap them
2477  * into the desired range as necessary.
2478  *
2479  * The matches inserted into 'matches' will be of three distinct kinds:
2480  *
2481  *     - Ordinary flows.  The caller should add these OpenFlow flows with
2482  *       its desired actions.
2483  *
2484  *     - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2485  *       structure.  The caller should add these OpenFlow flows with the
2486  *       conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2487  *       remapping the ids.
2488  *
2489  *     - conj_id flows, distinguished by matching on the "conj_id" field.  The
2490  *       caller should remap the conj_id and add the OpenFlow flow with its
2491  *       desired actions.
2492  *
2493  * 'lookup_port' must be a function to map from a port name to a port number.
2494  * When successful, 'lookup_port' stores the port number into '*portp' and
2495  * returns true; when there is no port by the given name, it returns false.
2496  * 'aux' is passed to 'lookup_port' as auxiliary data.  Any comparisons against
2497  * string fields in 'expr' are translated into integers through this function.
2498  * A comparison against a string that is not in 'ports' acts like a Boolean
2499  * "false"; that is, it will always fail to match.  For a simple expression,
2500  * this means that the overall expression always fails to match, but an
2501  * expression with a disjunction on the string field might still match on other
2502  * port names.
2503  *
2504  * (This treatment of string fields might be too simplistic in general, but it
2505  * seems reasonable for now when string fields are used only for ports.) */
2506 uint32_t
2507 expr_to_matches(const struct expr *expr,
2508                 bool (*lookup_port)(const void *aux, const char *port_name,
2509                                     unsigned int *portp),
2510                 const void *aux, struct hmap *matches)
2511 {
2512     uint32_t n_conjs = 0;
2513
2514     hmap_init(matches);
2515     switch (expr->type) {
2516     case EXPR_T_CMP:
2517         add_cmp_flow(expr, lookup_port, aux, matches);
2518         break;
2519
2520     case EXPR_T_AND:
2521         add_conjunction(expr, lookup_port, aux, &n_conjs, matches);
2522         break;
2523
2524     case EXPR_T_OR:
2525         if (expr_is_cmp(expr)) {
2526             struct expr *sub;
2527
2528             LIST_FOR_EACH (sub, node, &expr->andor) {
2529                 add_cmp_flow(sub, lookup_port, aux, matches);
2530             }
2531         } else {
2532             struct expr *sub;
2533
2534             LIST_FOR_EACH (sub, node, &expr->andor) {
2535                 if (sub->type == EXPR_T_AND) {
2536                     add_conjunction(sub, lookup_port, aux, &n_conjs, matches);
2537                 } else {
2538                     add_cmp_flow(sub, lookup_port, aux, matches);
2539                 }
2540             }
2541         }
2542         break;
2543
2544     case EXPR_T_BOOLEAN:
2545         if (expr->boolean) {
2546             struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2547             expr_match_add(matches, m);
2548         } else {
2549             /* No match. */
2550         }
2551         break;
2552     }
2553     return n_conjs;
2554 }
2555
2556 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2557  * 'matches' hmap itself. */
2558 void
2559 expr_matches_destroy(struct hmap *matches)
2560 {
2561     struct expr_match *m;
2562
2563     HMAP_FOR_EACH_POP (m, hmap_node, matches) {
2564         free(m->conjunctions);
2565         free(m);
2566     }
2567     hmap_destroy(matches);
2568 }
2569
2570 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2571  * 'stream'. */
2572 void
2573 expr_matches_print(const struct hmap *matches, FILE *stream)
2574 {
2575     if (hmap_is_empty(matches)) {
2576         fputs("(no flows)\n", stream);
2577         return;
2578     }
2579
2580     const struct expr_match *m;
2581     HMAP_FOR_EACH (m, hmap_node, matches) {
2582         char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2583         fputs(s, stream);
2584         free(s);
2585
2586         if (m->n) {
2587             for (int i = 0; i < m->n; i++) {
2588                 const struct cls_conjunction *c = &m->conjunctions[i];
2589                 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2590                         i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2591             }
2592         }
2593         putc('\n', stream);
2594     }
2595 }
2596 \f
2597 /* Returns true if 'expr' honors the invariants for expressions (see the large
2598  * comment above "struct expr" in expr.h), false otherwise. */
2599 bool
2600 expr_honors_invariants(const struct expr *expr)
2601 {
2602     const struct expr *sub;
2603
2604     switch (expr->type) {
2605     case EXPR_T_CMP:
2606         if (expr->cmp.symbol->width) {
2607             for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2608                 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2609                     return false;
2610                 }
2611             }
2612         }
2613         return true;
2614
2615     case EXPR_T_AND:
2616     case EXPR_T_OR:
2617         if (ovs_list_is_short(&expr->andor)) {
2618             return false;
2619         }
2620         LIST_FOR_EACH (sub, node, &expr->andor) {
2621             if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2622                 return false;
2623             }
2624         }
2625         return true;
2626
2627     case EXPR_T_BOOLEAN:
2628         return true;
2629
2630     default:
2631         OVS_NOT_REACHED();
2632     }
2633 }
2634
2635 static bool
2636 expr_is_normalized_and(const struct expr *expr)
2637 {
2638     /* XXX should also check that no symbol is repeated. */
2639     const struct expr *sub;
2640
2641     LIST_FOR_EACH (sub, node, &expr->andor) {
2642         if (!expr_is_cmp(sub)) {
2643             return false;
2644         }
2645     }
2646     return true;
2647 }
2648
2649 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2650  * otherwise. */
2651 bool
2652 expr_is_normalized(const struct expr *expr)
2653 {
2654     switch (expr->type) {
2655     case EXPR_T_CMP:
2656         return true;
2657
2658     case EXPR_T_AND:
2659         return expr_is_normalized_and(expr);
2660
2661     case EXPR_T_OR:
2662         if (!expr_is_cmp(expr)) {
2663             const struct expr *sub;
2664
2665             LIST_FOR_EACH (sub, node, &expr->andor) {
2666                 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2667                     return false;
2668                 }
2669             }
2670         }
2671         return true;
2672
2673     case EXPR_T_BOOLEAN:
2674         return true;
2675
2676     default:
2677         OVS_NOT_REACHED();
2678     }
2679 }
2680 \f
2681 /* Action parsing helper. */
2682
2683 /* Expands 'f' repeatedly as long as it has an expansion, that is, as long as
2684  * it is a subfield or a predicate.  Adds any prerequisites for 'f' to
2685  * '*prereqs'.
2686  *
2687  * If 'rw', verifies that 'f' is a read/write field.
2688  *
2689  * Returns true if successful, false if an error was encountered (in which case
2690  * 'ctx->error' reports the particular error). */
2691 static bool
2692 expand_symbol(struct expr_context *ctx, bool rw,
2693               struct expr_field *f, struct expr **prereqsp)
2694 {
2695     const struct expr_symbol *orig_symbol = f->symbol;
2696
2697     if (f->symbol->expansion && f->symbol->level != EXPR_L_ORDINAL) {
2698         expr_error(ctx, "Predicate symbol %s used where lvalue required.",
2699                    f->symbol->name);
2700         return false;
2701     }
2702
2703     for (;;) {
2704         /* Accumulate prerequisites. */
2705         if (f->symbol->prereqs) {
2706             struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2707             char *error;
2708             struct expr *e;
2709             e = parse_and_annotate(f->symbol->prereqs, ctx->symtab, &nesting,
2710                                    &error);
2711             if (error) {
2712                 expr_error(ctx, "%s", error);
2713                 free(error);
2714                 return false;
2715             }
2716             *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
2717         }
2718
2719         /* If there's no expansion, we're done. */
2720         if (!f->symbol->expansion) {
2721             break;
2722         }
2723
2724         /* Expand. */
2725         struct expr_field expansion;
2726         char *error;
2727         if (!parse_field_from_string(f->symbol->expansion, ctx->symtab,
2728                                      &expansion, &error)) {
2729             expr_error(ctx, "%s", error);
2730             free(error);
2731             return false;
2732         }
2733         f->symbol = expansion.symbol;
2734         f->ofs += expansion.ofs;
2735     }
2736
2737     if (rw && !f->symbol->field->writable) {
2738         expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2739         return false;
2740     }
2741
2742     return true;
2743 }
2744
2745 static void
2746 mf_subfield_from_expr_field(const struct expr_field *f, struct mf_subfield *sf)
2747 {
2748     sf->field = f->symbol->field;
2749     sf->ofs = f->ofs;
2750     sf->n_bits = f->n_bits ? f->n_bits : f->symbol->field->n_bits;
2751 }
2752
2753 static void
2754 init_stack_action(const struct expr_field *f, struct ofpact_stack *stack)
2755 {
2756     mf_subfield_from_expr_field(f, &stack->subfield);
2757 }
2758
2759 static char * OVS_WARN_UNUSED_RESULT
2760 parse_assignment(struct lexer *lexer, struct expr_field *dst,
2761                  const struct shash *symtab, bool exchange,
2762                  bool (*lookup_port)(const void *aux, const char *port_name,
2763                                      unsigned int *portp),
2764                  const void *aux, struct ofpbuf *ofpacts,
2765                  struct expr **prereqsp)
2766 {
2767     struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2768     struct expr *prereqs = NULL;
2769
2770     /* Parse destination and do basic checking. */
2771     const struct expr_symbol *orig_dst = dst->symbol;
2772     if (!expand_symbol(&ctx, true, dst, &prereqs)) {
2773         goto exit;
2774     }
2775
2776     if (exchange || ctx.lexer->token.type == LEX_T_ID) {
2777         struct expr_field src;
2778         if (!parse_field(&ctx, &src)) {
2779             goto exit;
2780         }
2781         const struct expr_symbol *orig_src = src.symbol;
2782         if (!expand_symbol(&ctx, exchange, &src, &prereqs)) {
2783             goto exit;
2784         }
2785
2786         if ((dst->symbol->width != 0) != (src.symbol->width != 0)) {
2787             if (exchange) {
2788                 expr_error(&ctx,
2789                            "Can't exchange %s field (%s) with %s field (%s).",
2790                            orig_dst->width ? "integer" : "string",
2791                            orig_dst->name,
2792                            orig_src->width ? "integer" : "string",
2793                            orig_src->name);
2794             } else {
2795                 expr_error(&ctx,
2796                            "Can't assign %s field (%s) to %s field (%s).",
2797                            orig_src->width ? "integer" : "string",
2798                            orig_src->name,
2799                            orig_dst->width ? "integer" : "string",
2800                            orig_dst->name);
2801             }
2802             goto exit;
2803         }
2804
2805         if (dst->n_bits != src.n_bits) {
2806             if (exchange) {
2807                 expr_error(&ctx,
2808                            "Can't exchange %d-bit field with %d-bit field.",
2809                            dst->n_bits, src.n_bits);
2810             } else {
2811                 expr_error(&ctx,
2812                            "Can't assign %d-bit value to %d-bit destination.",
2813                            src.n_bits, dst->n_bits);
2814             }
2815             goto exit;
2816         } else if (!dst->n_bits &&
2817                    dst->symbol->field->n_bits != src.symbol->field->n_bits) {
2818             expr_error(&ctx, "String fields %s and %s are incompatible for "
2819                        "%s.", orig_dst->name, orig_src->name,
2820                        exchange ? "exchange" : "assignment");
2821             goto exit;
2822         }
2823
2824         if (exchange) {
2825             init_stack_action(&src, ofpact_put_STACK_PUSH(ofpacts));
2826             init_stack_action(dst, ofpact_put_STACK_PUSH(ofpacts));
2827             init_stack_action(&src, ofpact_put_STACK_POP(ofpacts));
2828             init_stack_action(dst, ofpact_put_STACK_POP(ofpacts));
2829         } else {
2830             struct ofpact_reg_move *move = ofpact_put_REG_MOVE(ofpacts);
2831             mf_subfield_from_expr_field(&src, &move->src);
2832             mf_subfield_from_expr_field(dst, &move->dst);
2833         }
2834     } else {
2835         struct expr_constant_set cs;
2836         if (!parse_constant_set(&ctx, &cs)) {
2837             goto exit;
2838         }
2839
2840         if (!type_check(&ctx, dst, &cs)) {
2841             goto exit_destroy_cs;
2842         }
2843         if (cs.in_curlies) {
2844             expr_error(&ctx, "Assignments require a single value.");
2845             goto exit_destroy_cs;
2846         }
2847
2848         union expr_constant *c = cs.values;
2849         struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2850         sf->field = dst->symbol->field;
2851         if (dst->symbol->width) {
2852             mf_subvalue_shift(&c->value, dst->ofs);
2853             if (!c->masked) {
2854                 memset(&c->mask, 0, sizeof c->mask);
2855                 bitwise_one(&c->mask, sizeof c->mask, dst->ofs, dst->n_bits);
2856             } else {
2857                 mf_subvalue_shift(&c->mask, dst->ofs);
2858             }
2859
2860             memcpy(&sf->value,
2861                    &c->value.u8[sizeof c->value - sf->field->n_bytes],
2862                    sf->field->n_bytes);
2863             memcpy(&sf->mask,
2864                    &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2865                    sf->field->n_bytes);
2866         } else {
2867             uint32_t port;
2868             if (!lookup_port(aux, c->string, &port)) {
2869                 port = 0;
2870             }
2871             bitwise_put(port, &sf->value,
2872                         sf->field->n_bytes, 0, sf->field->n_bits);
2873             bitwise_one(&sf->mask, sf->field->n_bytes, 0, sf->field->n_bits);
2874
2875             /* If the logical input port is being zeroed, clear the OpenFlow
2876              * ingress port also, to allow a packet to be sent back to its
2877              * origin. */
2878             if (!port && sf->field->id == MFF_LOG_INPORT) {
2879                 sf = ofpact_put_SET_FIELD(ofpacts);
2880                 sf->field = mf_from_id(MFF_IN_PORT);
2881                 bitwise_one(&sf->mask,
2882                             sf->field->n_bytes, 0, sf->field->n_bits);
2883             }
2884         }
2885
2886     exit_destroy_cs:
2887         expr_constant_set_destroy(&cs);
2888     }
2889
2890 exit:
2891     if (ctx.error) {
2892         expr_destroy(prereqs);
2893         prereqs = NULL;
2894     }
2895     *prereqsp = prereqs;
2896     return ctx.error;
2897 }
2898
2899 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2900  * "field = value" or "field = field2" into 'ofpacts'.  The caller must have
2901  * already parsed and skipped the left-hand side "field =" and pass in the
2902  * field as 'dst'.  Other parameters and return value match those for
2903  * actions_parse(). */
2904 char * OVS_WARN_UNUSED_RESULT
2905 expr_parse_assignment(struct lexer *lexer, struct expr_field *dst,
2906                       const struct shash *symtab,
2907                       bool (*lookup_port)(const void *aux,
2908                                           const char *port_name,
2909                                           unsigned int *portp),
2910                       const void *aux,
2911                       struct ofpbuf *ofpacts, struct expr **prereqsp)
2912 {
2913     return parse_assignment(lexer, dst, symtab, false, lookup_port, aux,
2914                             ofpacts, prereqsp);
2915 }
2916
2917 /* A helper for actions_parse(), to parse an OVN exchange action in the form
2918  * "field1 <-> field2" into 'ofpacts'.  The caller must have already parsed and
2919  * skipped the left-hand side "field1 <->" and pass in 'field1'.  Other
2920  * parameters and return value match those for actions_parse(). */
2921 char * OVS_WARN_UNUSED_RESULT
2922 expr_parse_exchange(struct lexer *lexer, struct expr_field *field,
2923                     const struct shash *symtab,
2924                     bool (*lookup_port)(const void *aux,
2925                                         const char *port_name,
2926                                         unsigned int *portp),
2927                     const void *aux,
2928                     struct ofpbuf *ofpacts, struct expr **prereqsp)
2929 {
2930     return parse_assignment(lexer, field, symtab, true, lookup_port, aux,
2931                             ofpacts, prereqsp);
2932 }
2933
2934 /* Parses a field or subfield from 'lexer' into 'field', obtaining field names
2935  * from 'symtab'.  Returns NULL if successful, otherwise an error message owned
2936  * by the caller. */
2937 char * OVS_WARN_UNUSED_RESULT
2938 expr_parse_field(struct lexer *lexer, const struct shash *symtab,
2939                  struct expr_field *field)
2940 {
2941     struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2942     if (!parse_field(&ctx, field)) {
2943         memset(field, 0, sizeof *field);
2944     }
2945     return ctx.error;
2946 }
2947
2948 /* Takes 'field', which was presumably parsed by expr_parse_field(), and
2949  * converts it into mf_subfield 'sf' and a set of prerequisites in '*prereqsp'.
2950  *
2951  * 'n_bits' specifies the number of bits that the field must have, and 0
2952  * indicates a string field; reports an error if 'field' has a different type
2953  * or width.  If 'rw' is true, it is an error if 'field' is read-only.  Uses
2954  * 'symtab 'for expanding references and 'lexer' for error reporting.
2955  *
2956  * Returns NULL if successful, otherwise an error message owned by the
2957  * caller. */
2958 char * OVS_WARN_UNUSED_RESULT
2959 expr_expand_field(struct lexer *lexer, const struct shash *symtab,
2960                   const struct expr_field *orig_field, int n_bits, bool rw,
2961                   struct mf_subfield *sf, struct expr **prereqsp)
2962 {
2963     struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2964     struct expr *prereqs = NULL;
2965
2966     struct expr_field field = *orig_field;
2967     if (!expand_symbol(&ctx, rw, &field, &prereqs)) {
2968         goto exit;
2969     }
2970     ovs_assert(field.n_bits == orig_field->n_bits);
2971
2972     if (n_bits != field.n_bits) {
2973         if (n_bits && field.n_bits) {
2974             expr_error(&ctx, "Cannot use %d-bit field %s[%d..%d] "
2975                        "where %d-bit field is required.",
2976                        orig_field->n_bits, orig_field->symbol->name,
2977                        orig_field->ofs,
2978                        orig_field->ofs + orig_field->n_bits - 1, n_bits);
2979         } else if (n_bits) {
2980             expr_error(&ctx, "Cannot use string field %s where numeric "
2981                        "field is required.",
2982                        orig_field->symbol->name);
2983         } else {
2984             expr_error(&ctx, "Cannot use numeric field %s where string "
2985                        "field is required.",
2986                        orig_field->symbol->name);
2987         }
2988     }
2989
2990 exit:
2991     if (!ctx.error) {
2992         mf_subfield_from_expr_field(&field, sf);
2993         *prereqsp = prereqs;
2994     } else {
2995         memset(sf, 0, sizeof *sf);
2996         expr_destroy(prereqs);
2997         *prereqsp = NULL;
2998     }
2999     return ctx.error;
3000 }
3001
3002 char * OVS_WARN_UNUSED_RESULT
3003 expr_parse_constant_set(struct lexer *lexer, const struct shash *symtab,
3004                         struct expr_constant_set *cs)
3005 {
3006     struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
3007     parse_constant_set(&ctx, cs);
3008     return ctx.error;
3009 }