2 * Copyright (c) 2015 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include "dynamic-string.h"
22 #include "logical-fields.h"
24 #include "ofp-actions.h"
28 #include "openvswitch/vlog.h"
30 VLOG_DEFINE_THIS_MODULE(expr);
32 /* Returns the name of measurement level 'level'. */
34 expr_level_to_string(enum expr_level level)
37 case EXPR_L_NOMINAL: return "nominal";
38 case EXPR_L_BOOLEAN: return "Boolean";
39 case EXPR_L_ORDINAL: return "ordinal";
40 default: OVS_NOT_REACHED();
44 /* Relational operators. */
46 /* Returns a string form of relational operator 'relop'. */
48 expr_relop_to_string(enum expr_relop relop)
51 case EXPR_R_EQ: return "==";
52 case EXPR_R_NE: return "!=";
53 case EXPR_R_LT: return "<";
54 case EXPR_R_LE: return "<=";
55 case EXPR_R_GT: return ">";
56 case EXPR_R_GE: return ">=";
57 default: OVS_NOT_REACHED();
62 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
67 case LEX_T_EQ: r = EXPR_R_EQ; break;
68 case LEX_T_NE: r = EXPR_R_NE; break;
69 case LEX_T_LT: r = EXPR_R_LT; break;
70 case LEX_T_LE: r = EXPR_R_LE; break;
71 case LEX_T_GT: r = EXPR_R_GT; break;
72 case LEX_T_GE: r = EXPR_R_GE; break;
73 default: return false;
82 /* Returns the relational operator that 'relop' becomes if you turn the
83 * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
84 * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
85 * b" is equivalent to "b >= a". */
86 static enum expr_relop
87 expr_relop_turn(enum expr_relop relop)
90 case EXPR_R_EQ: return EXPR_R_EQ;
91 case EXPR_R_NE: return EXPR_R_NE;
92 case EXPR_R_LT: return EXPR_R_GT;
93 case EXPR_R_LE: return EXPR_R_GE;
94 case EXPR_R_GT: return EXPR_R_LT;
95 case EXPR_R_GE: return EXPR_R_LE;
96 default: OVS_NOT_REACHED();
100 /* Returns the relational operator that is the opposite of 'relop'. */
101 static enum expr_relop
102 expr_relop_invert(enum expr_relop relop)
105 case EXPR_R_EQ: return EXPR_R_NE;
106 case EXPR_R_NE: return EXPR_R_EQ;
107 case EXPR_R_LT: return EXPR_R_GE;
108 case EXPR_R_LE: return EXPR_R_GT;
109 case EXPR_R_GT: return EXPR_R_LE;
110 case EXPR_R_GE: return EXPR_R_LT;
111 default: OVS_NOT_REACHED();
115 /* Constructing and manipulating expressions. */
117 /* Creates and returns a logical AND or OR expression (according to 'type',
118 * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
119 * sub-expressions. (To satisfy the invariants for expressions, the caller
120 * must add at least two sub-expressions whose types are different from
123 expr_create_andor(enum expr_type type)
125 struct expr *e = xmalloc(sizeof *e);
127 list_init(&e->andor);
131 /* Returns a logical AND or OR expression (according to 'type', which must be
132 * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
135 * - If 'a' or 'b' is NULL, just returns the other one (which means that if
136 * that other one is not of the given 'type', then the returned
137 * expression is not either).
139 * - If 'a' or 'b', or both, have type 'type', then they are combined into
140 * a single node that satisfies the invariants for expressions. */
142 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
148 } else if (a->type == type) {
149 if (b->type == type) {
150 list_splice(&a->andor, b->andor.next, &b->andor);
153 list_push_back(&a->andor, &b->node);
156 } else if (b->type == type) {
157 list_push_front(&b->andor, &a->node);
160 struct expr *e = expr_create_andor(type);
161 list_push_back(&e->andor, &a->node);
162 list_push_back(&e->andor, &b->node);
168 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
170 if (new->type == andor->type) {
171 if (andor->type == EXPR_T_AND) {
172 /* Conjunction junction, what's your function? */
174 list_splice(&before->node, new->andor.next, &new->andor);
177 list_insert(&before->node, &new->node);
181 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
183 expr_create_boolean(bool b)
185 struct expr *e = xmalloc(sizeof *e);
186 e->type = EXPR_T_BOOLEAN;
192 expr_not(struct expr *expr)
196 switch (expr->type) {
198 expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
203 LIST_FOR_EACH (sub, node, &expr->andor) {
206 expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
210 expr->boolean = !expr->boolean;
218 expr_fix_andor(struct expr *expr, bool short_circuit)
220 struct expr *sub, *next;
222 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
223 if (sub->type == EXPR_T_BOOLEAN) {
224 if (sub->boolean == short_circuit) {
226 return expr_create_boolean(short_circuit);
228 list_remove(&sub->node);
234 if (list_is_short(&expr->andor)) {
235 if (list_is_empty(&expr->andor)) {
237 return expr_create_boolean(!short_circuit);
239 sub = expr_from_node(list_front(&expr->andor));
248 /* Returns 'expr' modified so that top-level oddities are fixed up:
250 * - Eliminates any EXPR_T_BOOLEAN operands at the top level.
252 * - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
254 expr_fix(struct expr *expr)
256 switch (expr->type) {
261 return expr_fix_andor(expr, false);
264 return expr_fix_andor(expr, true);
277 find_bitwise_range(const union mf_subvalue *sv, int width,
278 int *startp, int *n_bitsp)
280 unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
282 unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
284 || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
286 *n_bitsp = end - start;
290 *startp = *n_bitsp = 0;
294 expr_format_cmp(const struct expr *e, struct ds *s)
296 /* The common case is numerical comparisons.
297 * Handle string comparisons as a special case. */
298 if (!e->cmp.symbol->width) {
299 ds_put_format(s, "%s %s ", e->cmp.symbol->name,
300 expr_relop_to_string(e->cmp.relop));
301 json_string_escape(e->cmp.string, s);
306 find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
307 if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
310 positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
311 positive ^= e->cmp.relop == EXPR_R_NE;
315 ds_put_cstr(s, e->cmp.symbol->name);
316 if (e->cmp.symbol->width > 1) {
317 ds_put_format(s, "[%d]", ofs);
322 ds_put_cstr(s, e->cmp.symbol->name);
323 if (n > 0 && n < e->cmp.symbol->width) {
325 ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
327 ds_put_format(s, "[%d]", ofs);
331 ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
334 union mf_subvalue value;
336 memset(&value, 0, sizeof value);
337 bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
338 &value, sizeof value, 0,
340 mf_format_subvalue(&value, s);
342 mf_format_subvalue(&e->cmp.value, s);
344 mf_format_subvalue(&e->cmp.mask, s);
349 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
354 LIST_FOR_EACH (sub, node, &e->andor) {
356 ds_put_format(s, " %s ", op);
359 if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
369 /* Appends a string form of 'e' to 's'. The string form is acceptable for
370 * parsing back into an equivalent expression. */
372 expr_format(const struct expr *e, struct ds *s)
376 expr_format_cmp(e, s);
380 expr_format_andor(e, "&&", s);
384 expr_format_andor(e, "||", s);
388 ds_put_char(s, e->boolean ? '1' : '0');
393 /* Prints a string form of 'e' on stdout, followed by a new-line. */
395 expr_print(const struct expr *e)
400 expr_format(e, &output);
401 puts(ds_cstr(&output));
407 /* Type of a "union expr_constant" or "struct expr_constant_set". */
408 enum expr_constant_type {
413 /* A string or integer constant (one must know which from context). */
414 union expr_constant {
417 * The width of a constant isn't always clear, e.g. if you write "1",
418 * there's no way to tell whether you mean for that to be a 1-bit constant
419 * or a 128-bit constant or somewhere in between. */
421 union mf_subvalue value;
422 union mf_subvalue mask; /* Only initialized if 'masked'. */
425 enum lex_format format; /* From the constant's lex_token. */
428 /* Null-terminated string constant. */
432 /* A collection of "union expr_constant"s of the same type. */
433 struct expr_constant_set {
434 union expr_constant *values; /* Constants. */
435 size_t n_values; /* Number of constants. */
436 enum expr_constant_type type; /* Type of the constants. */
437 bool in_curlies; /* Whether the constants were in {}. */
440 /* A reference to a symbol or a subfield of a symbol.
442 * For string fields, ofs and n_bits are 0. */
444 const struct expr_symbol *symbol; /* The symbol. */
445 int ofs; /* Starting bit offset. */
446 int n_bits; /* Number of bits. */
449 /* Context maintained during expr_parse(). */
450 struct expr_context {
451 struct lexer *lexer; /* Lexer for pulling more tokens. */
452 const struct shash *symtab; /* Symbol table. */
453 char *error; /* Error, if any, otherwise NULL. */
454 bool not; /* True inside odd number of NOT operators. */
457 struct expr *expr_parse__(struct expr_context *);
458 static void expr_not(struct expr *);
459 static void expr_constant_set_destroy(struct expr_constant_set *);
460 static bool parse_field(struct expr_context *, struct expr_field *);
463 expr_error_handle_common(struct expr_context *ctx)
466 /* Already have an error, suppress this one since the cascade seems
467 * unlikely to be useful. */
469 } else if (ctx->lexer->token.type == LEX_T_ERROR) {
470 /* The lexer signaled an error. Nothing at the expression level
471 * accepts an error token, so we'll inevitably end up here with some
472 * meaningless parse error. Report the lexical error instead. */
473 ctx->error = xstrdup(ctx->lexer->token.s);
480 static void OVS_PRINTF_FORMAT(2, 3)
481 expr_error(struct expr_context *ctx, const char *message, ...)
483 if (expr_error_handle_common(ctx)) {
488 va_start(args, message);
489 ctx->error = xvasprintf(message, args);
493 static void OVS_PRINTF_FORMAT(2, 3)
494 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
496 if (expr_error_handle_common(ctx)) {
503 ds_put_cstr(&s, "Syntax error ");
504 if (ctx->lexer->token.type == LEX_T_END) {
505 ds_put_cstr(&s, "at end of input ");
506 } else if (ctx->lexer->start) {
507 ds_put_format(&s, "at `%.*s' ",
508 (int) (ctx->lexer->input - ctx->lexer->start),
513 va_start(args, message);
514 ds_put_format_valist(&s, message, args);
517 ctx->error = ds_steal_cstr(&s);
521 make_cmp__(const struct expr_field *f, enum expr_relop r,
522 const union expr_constant *c)
524 struct expr *e = xzalloc(sizeof *e);
525 e->type = EXPR_T_CMP;
526 e->cmp.symbol = f->symbol;
528 if (f->symbol->width) {
529 bitwise_copy(&c->value, sizeof c->value, 0,
530 &e->cmp.value, sizeof e->cmp.value, f->ofs,
533 bitwise_copy(&c->mask, sizeof c->mask, 0,
534 &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
537 bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
541 e->cmp.string = xstrdup(c->string);
546 /* Returns the minimum reasonable width for integer constant 'c'. */
548 expr_constant_width(const union expr_constant *c)
551 return mf_subvalue_width(&c->mask);
556 case LEX_F_HEXADECIMAL:
557 return mf_subvalue_width(&c->value);
574 type_check(struct expr_context *ctx, const struct expr_field *f,
575 struct expr_constant_set *cs)
577 if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
578 expr_error(ctx, "%s field %s is not compatible with %s constant.",
579 f->symbol->width ? "Integer" : "String",
581 cs->type == EXPR_C_INTEGER ? "integer" : "string");
585 if (f->symbol->width) {
586 for (size_t i = 0; i < cs->n_values; i++) {
587 int w = expr_constant_width(&cs->values[i]);
588 if (w > f->symbol->width) {
589 expr_error(ctx, "%d-bit constant is not compatible with "
591 w, f->symbol->width, f->symbol->name);
601 make_cmp(struct expr_context *ctx,
602 const struct expr_field *f, enum expr_relop r,
603 struct expr_constant_set *cs)
605 struct expr *e = NULL;
607 if (!type_check(ctx, f, cs)) {
611 if (r != EXPR_R_EQ && r != EXPR_R_NE) {
612 if (cs->in_curlies) {
613 expr_error(ctx, "Only == and != operators may be used "
617 if (f->symbol->level == EXPR_L_NOMINAL ||
618 f->symbol->level == EXPR_L_BOOLEAN) {
619 expr_error(ctx, "Only == and != operators may be used "
621 expr_level_to_string(f->symbol->level),
625 if (cs->values[0].masked) {
626 expr_error(ctx, "Only == and != operators may be used with "
627 "masked constants. Consider using subfields instead "
628 "(e.g. eth.src[0..15] > 0x1111 in place of "
629 "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
634 if (f->symbol->level == EXPR_L_NOMINAL) {
635 if (f->symbol->expansion) {
636 ovs_assert(f->symbol->width > 0);
637 for (size_t i = 0; i < cs->n_values; i++) {
638 const union mf_subvalue *value = &cs->values[i].value;
639 bool positive = (value->integer & htonll(1)) != 0;
640 positive ^= r == EXPR_R_NE;
641 positive ^= ctx->not;
643 const char *name = f->symbol->name;
644 expr_error(ctx, "Nominal predicate %s may only be tested "
645 "positively, e.g. `%s' or `%s == 1' but not "
646 "`!%s' or `%s == 0'.",
647 name, name, name, name, name);
651 } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
652 expr_error(ctx, "Nominal field %s may only be tested for "
653 "equality (taking enclosing `!' operators into "
654 "account).", f->symbol->name);
659 e = make_cmp__(f, r, &cs->values[0]);
660 for (size_t i = 1; i < cs->n_values; i++) {
661 e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
662 e, make_cmp__(f, r, &cs->values[i]));
665 expr_constant_set_destroy(cs);
670 expr_get_int(struct expr_context *ctx, int *value)
672 bool ok = lexer_get_int(ctx->lexer, value);
674 expr_syntax_error(ctx, "expecting small integer.");
680 parse_field(struct expr_context *ctx, struct expr_field *f)
682 const struct expr_symbol *symbol;
684 if (ctx->lexer->token.type != LEX_T_ID) {
685 expr_syntax_error(ctx, "expecting field name.");
689 symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
691 expr_syntax_error(ctx, "expecting field name.");
694 lexer_get(ctx->lexer);
697 if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
700 if (!symbol->width) {
701 expr_error(ctx, "Cannot select subfield of string field %s.",
706 if (!expr_get_int(ctx, &low)) {
709 if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
710 if (!expr_get_int(ctx, &high)) {
717 if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
718 expr_syntax_error(ctx, "expecting `]'.");
723 expr_error(ctx, "Invalid bit range %d to %d.", low, high);
725 } else if (high >= symbol->width) {
726 expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
727 low, high, symbol->width, symbol->name);
729 } else if (symbol->level == EXPR_L_NOMINAL
730 && (low != 0 || high != symbol->width - 1)) {
731 expr_error(ctx, "Cannot select subfield of nominal field %s.",
737 f->n_bits = high - low + 1;
740 f->n_bits = symbol->width;
747 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
749 if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
750 lexer_get(ctx->lexer);
753 expr_syntax_error(ctx, "expecting relational operator.");
759 assign_constant_set_type(struct expr_context *ctx,
760 struct expr_constant_set *cs,
761 enum expr_constant_type type)
763 if (!cs->n_values || cs->type == type) {
767 expr_syntax_error(ctx, "expecting %s.",
768 cs->type == EXPR_C_INTEGER ? "integer" : "string");
774 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
775 size_t *allocated_values)
777 if (cs->n_values >= *allocated_values) {
778 cs->values = x2nrealloc(cs->values, allocated_values,
782 if (ctx->lexer->token.type == LEX_T_STRING) {
783 if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
786 cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
787 lexer_get(ctx->lexer);
789 } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
790 ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
791 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
795 union expr_constant *c = &cs->values[cs->n_values++];
796 c->value = ctx->lexer->token.value;
797 c->format = ctx->lexer->token.format;
798 c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
800 c->mask = ctx->lexer->token.mask;
802 lexer_get(ctx->lexer);
805 expr_syntax_error(ctx, "expecting constant.");
810 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
811 * which the caller need not have initialized. Returns true on success, in
812 * which case the caller owns 'cs', false on failure, in which case 'cs' is
815 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
817 size_t allocated_values = 0;
820 memset(cs, 0, sizeof *cs);
821 if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
823 cs->in_curlies = true;
825 if (!parse_constant(ctx, cs, &allocated_values)) {
829 lexer_match(ctx->lexer, LEX_T_COMMA);
830 } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
832 ok = parse_constant(ctx, cs, &allocated_values);
835 expr_constant_set_destroy(cs);
841 expr_constant_set_destroy(struct expr_constant_set *cs)
844 if (cs->type == EXPR_C_STRING) {
845 for (size_t i = 0; i < cs->n_values; i++) {
846 free(cs->values[i].string);
854 expr_parse_primary(struct expr_context *ctx, bool *atomic)
857 if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
858 struct expr *e = expr_parse__(ctx);
859 if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
861 expr_syntax_error(ctx, "expecting `)'.");
868 if (ctx->lexer->token.type == LEX_T_ID) {
871 struct expr_constant_set c;
873 if (!parse_field(ctx, &f)) {
877 if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
878 if (f.n_bits > 1 && !ctx->not) {
879 expr_error(ctx, "Explicit `!= 0' is required for inequality "
880 "test of multibit field against 0.");
886 union expr_constant *cst = xzalloc(sizeof *cst);
887 cst->format = LEX_F_HEXADECIMAL;
890 c.type = EXPR_C_INTEGER;
893 c.in_curlies = false;
894 return make_cmp(ctx, &f, EXPR_R_NE, &c);
895 } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
896 return make_cmp(ctx, &f, r, &c);
901 struct expr_constant_set c1;
902 if (!parse_constant_set(ctx, &c1)) {
906 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
908 && c1.type == EXPR_C_INTEGER
909 && c1.values[0].format == LEX_F_DECIMAL
910 && !c1.values[0].masked
912 uint64_t x = ntohll(c1.values[0].value.integer);
915 expr_constant_set_destroy(&c1);
916 return expr_create_boolean(x);
922 if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
923 expr_constant_set_destroy(&c1);
927 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
928 return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
932 struct expr_constant_set c2;
933 if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
934 expr_constant_set_destroy(&c1);
937 /* Reject "1 == field == 2", "1 < field > 2", and so on. */
938 if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
939 (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
940 ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
941 (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
942 expr_error(ctx, "Range expressions must have the form "
943 "`x < field < y' or `x > field > y', with each "
944 "`<' optionally replaced by `<=' or `>' by `>=').");
945 expr_constant_set_destroy(&c1);
946 expr_constant_set_destroy(&c2);
950 struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
951 struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
957 return expr_combine(EXPR_T_AND, e1, e2);
963 expr_parse_not(struct expr_context *ctx)
967 if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
968 ctx->not = !ctx->not;
969 struct expr *expr = expr_parse_primary(ctx, &atomic);
970 ctx->not = !ctx->not;
974 expr_error(ctx, "Missing parentheses around operand of !.");
982 return expr_parse_primary(ctx, &atomic);
987 expr_parse__(struct expr_context *ctx)
989 struct expr *e = expr_parse_not(ctx);
994 enum lex_type lex_type = ctx->lexer->token.type;
995 if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
996 enum expr_type expr_type
997 = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
999 lexer_get(ctx->lexer);
1001 struct expr *e2 = expr_parse_not(ctx);
1006 e = expr_combine(expr_type, e, e2);
1007 } while (lexer_match(ctx->lexer, lex_type));
1008 if (ctx->lexer->token.type == LEX_T_LOG_AND
1009 || ctx->lexer->token.type == LEX_T_LOG_OR) {
1012 "&& and || must be parenthesized when used together.");
1019 /* Parses an expression using the symbols in 'symtab' from 'lexer'. If
1020 * successful, returns the new expression and sets '*errorp' to NULL. On
1021 * failure, returns NULL and sets '*errorp' to an explanatory error message.
1022 * The caller must eventually free the returned expression (with
1023 * expr_destroy()) or error (with free()). */
1025 expr_parse(struct lexer *lexer, const struct shash *symtab, char **errorp)
1027 struct expr_context ctx;
1030 ctx.symtab = symtab;
1034 struct expr *e = expr_parse__(&ctx);
1035 *errorp = ctx.error;
1036 ovs_assert((ctx.error != NULL) != (e != NULL));
1040 /* Like expr_parse(), but the expression is taken from 's'. */
1042 expr_parse_string(const char *s, const struct shash *symtab, char **errorp)
1047 lexer_init(&lexer, s);
1049 expr = expr_parse(&lexer, symtab, errorp);
1050 if (!*errorp && lexer.token.type != LEX_T_END) {
1051 *errorp = xstrdup("Extra tokens at end of input.");
1055 lexer_destroy(&lexer);
1060 static struct expr_symbol *
1061 add_symbol(struct shash *symtab, const char *name, int width,
1062 const char *prereqs, enum expr_level level,
1063 bool must_crossproduct)
1065 struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1066 symbol->name = xstrdup(name);
1067 symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1068 symbol->width = width;
1069 symbol->level = level;
1070 symbol->must_crossproduct = must_crossproduct;
1071 shash_add_assert(symtab, symbol->name, symbol);
1075 /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1076 * 'name' is referenced, expression annotation (see expr_annotate()) will
1077 * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1078 * conversion to flows will never attempt to use the field as a conjunctive
1079 * match dimension (see "Crossproducting" in the large comment on struct
1080 * expr_symbol in expr.h for an example).
1082 * A given field 'id' must only be used for a single symbol in a symbol table.
1083 * Use subfields to duplicate or subset a field (you can even make a subfield
1084 * include all the bits of the "parent" field if you like). */
1085 struct expr_symbol *
1086 expr_symtab_add_field(struct shash *symtab, const char *name,
1087 enum mf_field_id id, const char *prereqs,
1088 bool must_crossproduct)
1090 const struct mf_field *field = mf_from_id(id);
1091 struct expr_symbol *symbol;
1093 symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1094 (field->maskable == MFM_FULLY
1098 symbol->field = field;
1103 parse_field_from_string(const char *s, const struct shash *symtab,
1104 struct expr_field *field, char **errorp)
1107 lexer_init(&lexer, s);
1110 struct expr_context ctx;
1112 ctx.symtab = symtab;
1116 bool ok = parse_field(&ctx, field);
1118 *errorp = ctx.error;
1119 } else if (lexer.token.type != LEX_T_END) {
1120 *errorp = xstrdup("Extra tokens at end of input.");
1124 lexer_destroy(&lexer);
1129 /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1130 * 'name' is referenced, expression annotation (see expr_annotate()) will
1131 * ensure that 'prereqs' are also true.
1133 * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1134 * for the low 12 bits of a larger field named "vlan.tci". */
1135 struct expr_symbol *
1136 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1137 const char *prereqs, const char *subfield)
1139 struct expr_symbol *symbol;
1140 struct expr_field f;
1143 if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1144 VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1149 enum expr_level level = f.symbol->level;
1150 if (level != EXPR_L_ORDINAL) {
1151 VLOG_WARN("can't define %s as subfield of %s field %s",
1152 name, expr_level_to_string(level), f.symbol->name);
1155 symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1156 symbol->expansion = xstrdup(subfield);
1160 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1162 struct expr_symbol *
1163 expr_symtab_add_string(struct shash *symtab, const char *name,
1164 enum mf_field_id id, const char *prereqs)
1166 const struct mf_field *field = mf_from_id(id);
1167 struct expr_symbol *symbol;
1169 symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1170 symbol->field = field;
1174 static enum expr_level
1175 expr_get_level(const struct expr *expr)
1177 const struct expr *sub;
1178 enum expr_level level = EXPR_L_ORDINAL;
1180 switch (expr->type) {
1182 return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1188 LIST_FOR_EACH (sub, node, &expr->andor) {
1189 enum expr_level sub_level = expr_get_level(sub);
1190 level = MIN(level, sub_level);
1194 case EXPR_T_BOOLEAN:
1195 return EXPR_L_BOOLEAN;
1202 static enum expr_level
1203 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1205 struct expr *expr = expr_parse_string(s, symtab, errorp);
1206 enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1211 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1212 * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 6" might be an
1213 * appropriate predicate named "tcp4". */
1214 struct expr_symbol *
1215 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1216 const char *expansion)
1218 struct expr_symbol *symbol;
1219 enum expr_level level;
1222 level = expr_parse_level(expansion, symtab, &error);
1224 VLOG_WARN("%s: error parsing %s expansion (%s)",
1225 expansion, name, error);
1230 symbol = add_symbol(symtab, name, 1, NULL, level, false);
1231 symbol->expansion = xstrdup(expansion);
1235 /* Destroys 'symtab' and all of its symbols. */
1237 expr_symtab_destroy(struct shash *symtab)
1239 struct shash_node *node, *next;
1241 SHASH_FOR_EACH_SAFE (node, next, symtab) {
1242 struct expr_symbol *symbol = node->data;
1244 shash_delete(symtab, node);
1246 free(symbol->prereqs);
1247 free(symbol->expansion);
1254 static struct expr *
1255 expr_clone_cmp(struct expr *expr)
1257 struct expr *new = xmemdup(expr, sizeof *expr);
1258 if (!new->cmp.symbol->width) {
1259 new->cmp.string = xstrdup(new->cmp.string);
1264 static struct expr *
1265 expr_clone_andor(struct expr *expr)
1267 struct expr *new = expr_create_andor(expr->type);
1270 LIST_FOR_EACH (sub, node, &expr->andor) {
1271 struct expr *new_sub = expr_clone(sub);
1272 list_push_back(&new->andor, &new_sub->node);
1277 /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1278 * expression nor any of its substructure will be shared with 'expr'. */
1280 expr_clone(struct expr *expr)
1282 switch (expr->type) {
1284 return expr_clone_cmp(expr);
1288 return expr_clone_andor(expr);
1290 case EXPR_T_BOOLEAN:
1291 return expr_create_boolean(expr->boolean);
1296 /* Destroys 'expr' and all of the sub-expressions it references. */
1298 expr_destroy(struct expr *expr)
1304 struct expr *sub, *next;
1306 switch (expr->type) {
1308 if (!expr->cmp.symbol->width) {
1309 free(expr->cmp.string);
1315 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1316 list_remove(&sub->node);
1321 case EXPR_T_BOOLEAN:
1329 /* An element in a linked list of symbols.
1331 * Used to detect when a symbol is being expanded recursively, to allow
1332 * flagging an error. */
1333 struct annotation_nesting {
1334 struct ovs_list node;
1335 const struct expr_symbol *symbol;
1338 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1339 struct ovs_list *nesting, char **errorp);
1341 static struct expr *
1342 parse_and_annotate(const char *s, const struct shash *symtab,
1343 struct ovs_list *nesting, char **errorp)
1348 expr = expr_parse_string(s, symtab, &error);
1350 expr = expr_annotate__(expr, symtab, nesting, &error);
1355 *errorp = xasprintf("Error parsing expression `%s' encountered as "
1356 "prerequisite or predicate of initial expression: "
1363 static struct expr *
1364 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1365 struct ovs_list *nesting, char **errorp)
1367 const struct expr_symbol *symbol = expr->cmp.symbol;
1368 const struct annotation_nesting *iter;
1369 LIST_FOR_EACH (iter, node, nesting) {
1370 if (iter->symbol == symbol) {
1371 *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1378 struct annotation_nesting an;
1380 list_push_back(nesting, &an.node);
1382 struct expr *prereqs = NULL;
1383 if (symbol->prereqs) {
1384 prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1390 if (symbol->expansion) {
1391 if (symbol->level == EXPR_L_ORDINAL) {
1392 struct expr_field field;
1394 if (!parse_field_from_string(symbol->expansion, symtab,
1399 expr->cmp.symbol = field.symbol;
1400 mf_subvalue_shift(&expr->cmp.value, field.ofs);
1401 mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1403 struct expr *expansion;
1405 expansion = parse_and_annotate(symbol->expansion, symtab,
1411 bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1412 positive ^= expr->cmp.relop == EXPR_R_NE;
1414 expr_not(expansion);
1422 list_remove(&an.node);
1423 return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1427 expr_destroy(prereqs);
1428 list_remove(&an.node);
1433 expr_annotate__(struct expr *expr, const struct shash *symtab,
1434 struct ovs_list *nesting, char **errorp)
1436 switch (expr->type) {
1438 return expr_annotate_cmp(expr, symtab, nesting, errorp);
1442 struct expr *sub, *next;
1444 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1445 list_remove(&sub->node);
1446 struct expr *new_sub = expr_annotate__(sub, symtab,
1452 expr_insert_andor(expr, next, new_sub);
1458 case EXPR_T_BOOLEAN:
1467 /* "Annotates" 'expr', which does the following:
1469 * - Applies prerequisites, by locating each comparison operator whose
1470 * field has a prerequisite and adding a logical AND against those
1473 * - Expands references to subfield symbols, by replacing them by
1474 * references to their underlying field symbols (suitably shifted).
1476 * - Expands references to predicate symbols, by replacing them by the
1477 * expressions that they expand to.
1479 * In each case, annotation occurs recursively as necessary.
1481 * On failure, returns NULL and sets '*errorp' to an explanatory error
1482 * message, which the caller must free. */
1484 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1486 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1487 return expr_annotate__(expr, symtab, &nesting, errorp);
1490 static struct expr *
1491 expr_simplify_ne(struct expr *expr)
1493 struct expr *new = NULL;
1494 const union mf_subvalue *value = &expr->cmp.value;
1495 const union mf_subvalue *mask = &expr->cmp.mask;
1496 int w = expr->cmp.symbol->width;
1499 for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1502 e = xzalloc(sizeof *e);
1503 e->type = EXPR_T_CMP;
1504 e->cmp.symbol = expr->cmp.symbol;
1505 e->cmp.relop = EXPR_R_EQ;
1506 bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1507 !bitwise_get_bit(value, sizeof *value, i));
1508 bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1510 new = expr_combine(EXPR_T_OR, new, e);
1519 static struct expr *
1520 expr_simplify_relational(struct expr *expr)
1522 const union mf_subvalue *value = &expr->cmp.value;
1523 int start, n_bits, end;
1525 find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1527 ovs_assert(n_bits > 0);
1528 end = start + n_bits;
1531 if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1532 new = xmemdup(expr, sizeof *expr);
1533 new->cmp.relop = EXPR_R_EQ;
1538 bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1539 for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1541 z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1544 e = xmemdup(expr, sizeof *expr);
1545 e->cmp.relop = EXPR_R_EQ;
1546 bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1547 bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1548 bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1549 new = expr_combine(EXPR_T_OR, new, e);
1552 return new ? new : expr_create_boolean(false);
1555 /* Takes ownership of 'expr' and returns an equivalent expression whose
1556 * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1558 expr_simplify(struct expr *expr)
1560 struct expr *sub, *next;
1562 switch (expr->type) {
1564 return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1565 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1566 : expr_simplify_relational(expr));
1570 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1571 list_remove(&sub->node);
1572 expr_insert_andor(expr, next, expr_simplify(sub));
1574 return expr_fix(expr);
1576 case EXPR_T_BOOLEAN:
1582 static const struct expr_symbol *
1583 expr_is_cmp(const struct expr *expr)
1585 switch (expr->type) {
1587 return expr->cmp.symbol;
1591 const struct expr_symbol *prev = NULL;
1594 LIST_FOR_EACH (sub, node, &expr->andor) {
1595 const struct expr_symbol *symbol = expr_is_cmp(sub);
1596 if (!symbol || (prev && symbol != prev)) {
1604 case EXPR_T_BOOLEAN:
1614 const struct expr_symbol *relop;
1615 enum expr_type type;
1619 compare_expr_sort(const void *a_, const void *b_)
1621 const struct expr_sort *a = a_;
1622 const struct expr_sort *b = b_;
1624 if (a->type != b->type) {
1625 return a->type < b->type ? -1 : 1;
1626 } else if (a->relop) {
1627 int cmp = strcmp(a->relop->name, b->relop->name);
1632 enum expr_type a_type = a->expr->type;
1633 enum expr_type b_type = a->expr->type;
1634 return a_type < b_type ? -1 : a_type > b_type;
1635 } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1636 size_t a_len = list_size(&a->expr->andor);
1637 size_t b_len = list_size(&b->expr->andor);
1638 return a_len < b_len ? -1 : a_len > b_len;
1644 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1647 disjunction_matches_string(const struct expr *or, const char *s)
1649 const struct expr *sub;
1651 LIST_FOR_EACH (sub, node, &or->andor) {
1652 if (!strcmp(sub->cmp.string, s)) {
1660 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1661 * string-typed 'symbol'. */
1662 static struct expr *
1663 crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1665 ovs_assert(!list_is_short(&expr->andor));
1667 struct expr *singleton = NULL;
1669 /* First crush each subexpression into either a single EXPR_T_CMP or an
1670 * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1671 struct expr *sub, *next = NULL;
1672 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1673 list_remove(&sub->node);
1674 struct expr *new = crush_cmps(sub, symbol);
1675 switch (new->type) {
1678 list_insert(&next->node, &new->node);
1681 bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1685 return expr_create_boolean(false);
1692 list_insert(&next->node, &new->node);
1694 case EXPR_T_BOOLEAN:
1695 if (!new->boolean) {
1704 /* If we have a singleton, then the result is either the singleton itself
1705 * (if the ORs allow the singleton) or false. */
1707 LIST_FOR_EACH (sub, node, &expr->andor) {
1708 if (sub->type == EXPR_T_OR
1709 && !disjunction_matches_string(sub, singleton->cmp.string)) {
1711 return expr_create_boolean(false);
1714 list_remove(&singleton->node);
1719 /* Otherwise the result is the intersection of all of the ORs. */
1720 struct sset result = SSET_INITIALIZER(&result);
1721 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1722 struct sset strings = SSET_INITIALIZER(&strings);
1723 const struct expr *s;
1724 LIST_FOR_EACH (s, node, &sub->andor) {
1725 sset_add(&strings, s->cmp.string);
1727 if (sset_is_empty(&result)) {
1728 sset_swap(&result, &strings);
1730 sset_intersect(&result, &strings);
1732 sset_destroy(&strings);
1734 if (sset_is_empty(&result)) {
1736 sset_destroy(&result);
1737 return expr_create_boolean(false);
1742 expr = expr_create_andor(EXPR_T_OR);
1745 SSET_FOR_EACH (string, &result) {
1746 sub = xmalloc(sizeof *sub);
1747 sub->type = EXPR_T_CMP;
1748 sub->cmp.symbol = symbol;
1749 sub->cmp.string = xstrdup(string);
1750 list_push_back(&expr->andor, &sub->node);
1752 sset_destroy(&result);
1753 return expr_fix(expr);
1756 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1757 * numeric-typed 'symbol'. */
1758 static struct expr *
1759 crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1761 ovs_assert(!list_is_short(&expr->andor));
1763 union mf_subvalue value, mask;
1764 memset(&value, 0, sizeof value);
1765 memset(&mask, 0, sizeof mask);
1767 struct expr *sub, *next = NULL;
1768 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1769 list_remove(&sub->node);
1770 struct expr *new = crush_cmps(sub, symbol);
1771 switch (new->type) {
1773 if (!mf_subvalue_intersect(&value, &mask,
1774 &new->cmp.value, &new->cmp.mask,
1778 return expr_create_boolean(false);
1785 list_insert(&next->node, &new->node);
1787 case EXPR_T_BOOLEAN:
1788 if (!new->boolean) {
1796 if (list_is_empty(&expr->andor)) {
1797 if (is_all_zeros(&mask, sizeof mask)) {
1799 return expr_create_boolean(true);
1802 cmp = xmalloc(sizeof *cmp);
1803 cmp->type = EXPR_T_CMP;
1804 cmp->cmp.symbol = symbol;
1805 cmp->cmp.relop = EXPR_R_EQ;
1806 cmp->cmp.value = value;
1807 cmp->cmp.mask = mask;
1811 } else if (list_is_short(&expr->andor)) {
1812 /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1813 * computed as "a && b", etc. */
1814 struct expr *disjuncts = expr_from_node(list_pop_front(&expr->andor));
1817 or = xmalloc(sizeof *or);
1818 or->type = EXPR_T_OR;
1819 list_init(&or->andor);
1821 ovs_assert(disjuncts->type == EXPR_T_OR);
1822 LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1823 ovs_assert(sub->type == EXPR_T_CMP);
1824 list_remove(&sub->node);
1825 if (mf_subvalue_intersect(&value, &mask,
1826 &sub->cmp.value, &sub->cmp.mask,
1827 &sub->cmp.value, &sub->cmp.mask)) {
1828 list_push_back(&or->andor, &sub->node);
1835 if (list_is_empty(&or->andor)) {
1837 return expr_create_boolean(false);
1838 } else if (list_is_short(&or->andor)) {
1839 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1846 /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1847 * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1848 struct expr *as = expr_from_node(list_pop_front(&expr->andor));
1849 struct expr *bs = expr_from_node(list_pop_front(&expr->andor));
1850 struct expr *new = NULL;
1853 or = xmalloc(sizeof *or);
1854 or->type = EXPR_T_OR;
1855 list_init(&or->andor);
1858 LIST_FOR_EACH (a, node, &as->andor) {
1859 union mf_subvalue a_value, a_mask;
1861 ovs_assert(a->type == EXPR_T_CMP);
1862 if (!mf_subvalue_intersect(&value, &mask,
1863 &a->cmp.value, &a->cmp.mask,
1864 &a_value, &a_mask)) {
1869 LIST_FOR_EACH (b, node, &bs->andor) {
1870 ovs_assert(b->type == EXPR_T_CMP);
1872 new = xmalloc(sizeof *new);
1873 new->type = EXPR_T_CMP;
1874 new->cmp.symbol = symbol;
1875 new->cmp.relop = EXPR_R_EQ;
1877 if (mf_subvalue_intersect(&a_value, &a_mask,
1878 &b->cmp.value, &b->cmp.mask,
1879 &new->cmp.value, &new->cmp.mask)) {
1880 list_push_back(&or->andor, &new->node);
1889 if (list_is_empty(&or->andor)) {
1892 return expr_create_boolean(false);
1893 } else if (list_is_short(&or->andor)) {
1894 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1896 if (list_is_empty(&expr->andor)) {
1898 return crush_cmps(cmp, symbol);
1900 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1902 } else if (!list_is_empty(&expr->andor)) {
1903 struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1904 ovs_assert(!list_is_short(&e->andor));
1905 return crush_cmps(e, symbol);
1908 return crush_cmps(or, symbol);
1914 compare_cmps_3way(const struct expr *a, const struct expr *b)
1916 ovs_assert(a->cmp.symbol == b->cmp.symbol);
1917 if (!a->cmp.symbol->width) {
1918 return strcmp(a->cmp.string, b->cmp.string);
1920 int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1922 d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1929 compare_cmps_cb(const void *a_, const void *b_)
1931 const struct expr *const *ap = a_;
1932 const struct expr *const *bp = b_;
1933 const struct expr *a = *ap;
1934 const struct expr *b = *bp;
1935 return compare_cmps_3way(a, b);
1938 /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
1939 static struct expr *
1940 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1942 struct expr *sub, *next = NULL;
1944 /* First, crush all the subexpressions. That might eliminate the
1945 * OR-expression entirely; if so, return the result. Otherwise, 'expr'
1946 * is now a disjunction of cmps over the same symbol. */
1947 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1948 list_remove(&sub->node);
1949 expr_insert_andor(expr, next, crush_cmps(sub, symbol));
1951 expr = expr_fix(expr);
1952 if (expr->type != EXPR_T_OR) {
1956 /* Sort subexpressions by value and mask, to bring together duplicates. */
1957 size_t n = list_size(&expr->andor);
1958 struct expr **subs = xmalloc(n * sizeof *subs);
1961 LIST_FOR_EACH (sub, node, &expr->andor) {
1966 qsort(subs, n, sizeof *subs, compare_cmps_cb);
1968 /* Eliminate duplicates. */
1969 list_init(&expr->andor);
1970 list_push_back(&expr->andor, &subs[0]->node);
1971 for (i = 1; i < n; i++) {
1972 struct expr *a = expr_from_node(list_back(&expr->andor));
1973 struct expr *b = subs[i];
1974 if (compare_cmps_3way(a, b)) {
1975 list_push_back(&expr->andor, &b->node);
1981 return expr_fix(expr);
1984 /* Takes ownership of 'expr', which must be a cmp in the sense determined by
1985 * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
1986 * Returns an equivalent expression owned by the caller that is a single
1987 * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
1988 static struct expr *
1989 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
1991 switch (expr->type) {
1993 return crush_or(expr, symbol);
1996 return (symbol->width
1997 ? crush_and_numeric(expr, symbol)
1998 : crush_and_string(expr, symbol));
2003 case EXPR_T_BOOLEAN:
2011 static struct expr *
2012 expr_sort(struct expr *expr)
2014 size_t n = list_size(&expr->andor);
2015 struct expr_sort *subs = xmalloc(n * sizeof *subs);
2020 LIST_FOR_EACH (sub, node, &expr->andor) {
2022 subs[i].relop = expr_is_cmp(sub);
2023 subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2028 qsort(subs, n, sizeof *subs, compare_expr_sort);
2030 list_init(&expr->andor);
2031 for (int i = 0; i < n; ) {
2032 if (subs[i].relop) {
2034 for (j = i + 1; j < n; j++) {
2035 if (subs[i].relop != subs[j].relop) {
2040 struct expr *crushed;
2042 crushed = crush_cmps(subs[i].expr, subs[i].relop);
2044 struct expr *combined = subs[i].expr;
2045 for (int k = i + 1; k < j; k++) {
2046 combined = expr_combine(EXPR_T_AND, combined,
2049 ovs_assert(!list_is_short(&combined->andor));
2050 crushed = crush_cmps(combined, subs[i].relop);
2052 if (crushed->type == EXPR_T_BOOLEAN) {
2053 if (!crushed->boolean) {
2054 for (int k = j; k < n; k++) {
2055 expr_destroy(subs[k].expr);
2064 expr = expr_combine(EXPR_T_AND, expr, crushed);
2068 expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2076 static struct expr *expr_normalize_or(struct expr *expr);
2078 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2079 * a clause is a cmp or a disjunction of cmps on a single field. */
2080 static struct expr *
2081 expr_normalize_and(struct expr *expr)
2083 ovs_assert(expr->type == EXPR_T_AND);
2085 expr = expr_sort(expr);
2086 if (expr->type != EXPR_T_AND) {
2087 ovs_assert(expr->type == EXPR_T_BOOLEAN);
2092 LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2093 if (&b->node == &expr->andor
2094 || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2095 || a->cmp.symbol != b->cmp.symbol) {
2097 } else if (a->cmp.symbol->width
2098 ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2099 &b->cmp.value, &b->cmp.mask,
2100 &b->cmp.value, &b->cmp.mask)
2101 : !strcmp(a->cmp.string, b->cmp.string)) {
2102 list_remove(&a->node);
2106 return expr_create_boolean(false);
2109 if (list_is_short(&expr->andor)) {
2110 struct expr *sub = expr_from_node(list_front(&expr->andor));
2116 LIST_FOR_EACH (sub, node, &expr->andor) {
2117 if (sub->type == EXPR_T_CMP) {
2121 ovs_assert(sub->type == EXPR_T_OR);
2122 const struct expr_symbol *symbol = expr_is_cmp(sub);
2123 if (!symbol || symbol->must_crossproduct) {
2124 struct expr *or = expr_create_andor(EXPR_T_OR);
2127 LIST_FOR_EACH (k, node, &sub->andor) {
2128 struct expr *and = expr_create_andor(EXPR_T_AND);
2131 LIST_FOR_EACH (m, node, &expr->andor) {
2132 struct expr *term = m == sub ? k : m;
2133 if (term->type == EXPR_T_AND) {
2136 LIST_FOR_EACH (p, node, &term->andor) {
2137 struct expr *new = expr_clone(p);
2138 list_push_back(&and->andor, &new->node);
2141 struct expr *new = expr_clone(term);
2142 list_push_back(&and->andor, &new->node);
2145 list_push_back(&or->andor, &and->node);
2148 return expr_normalize_or(or);
2154 static struct expr *
2155 expr_normalize_or(struct expr *expr)
2157 struct expr *sub, *next;
2159 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2160 if (sub->type == EXPR_T_AND) {
2161 list_remove(&sub->node);
2163 struct expr *new = expr_normalize_and(sub);
2164 if (new->type == EXPR_T_BOOLEAN) {
2171 expr_insert_andor(expr, next, new);
2174 ovs_assert(sub->type == EXPR_T_CMP);
2177 if (list_is_empty(&expr->andor)) {
2179 return expr_create_boolean(false);
2181 if (list_is_short(&expr->andor)) {
2182 struct expr *sub = expr_from_node(list_pop_front(&expr->andor));
2190 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2191 * an expression in terms of only relationals, AND, and OR. Returns either a
2192 * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2193 * clause is a cmp or a disjunction of cmps on a single field. This form is
2194 * significant because it is a form that can be directly converted to OpenFlow
2195 * flows with the Open vSwitch "conjunctive match" extension.
2197 * 'expr' must already have been simplified, with expr_simplify(). */
2199 expr_normalize(struct expr *expr)
2201 switch (expr->type) {
2206 return expr_normalize_and(expr);
2209 return expr_normalize_or(expr);
2211 case EXPR_T_BOOLEAN:
2217 /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2218 * nonnull then it is copied into the new expr_match, otherwise the new
2219 * expr_match's 'match' member is initialized to a catch-all match for the
2220 * caller to refine in-place.
2222 * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2223 * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2224 * expr_match will not have any conjunctions.
2226 * The caller should use expr_match_add() to add the expr_match to a hash table
2227 * after it is finalized. */
2228 static struct expr_match *
2229 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2232 struct expr_match *match = xmalloc(sizeof *match);
2236 match_init_catchall(&match->match);
2239 match->conjunctions = xmalloc(sizeof *match->conjunctions);
2240 match->conjunctions[0].id = conj_id;
2241 match->conjunctions[0].clause = clause;
2242 match->conjunctions[0].n_clauses = n_clauses;
2244 match->allocated = 1;
2246 match->conjunctions = NULL;
2248 match->allocated = 0;
2253 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2256 * This might actually destroy 'match' because it gets merged together with
2257 * some existing conjunction.*/
2259 expr_match_add(struct hmap *matches, struct expr_match *match)
2261 uint32_t hash = match_hash(&match->match, 0);
2262 struct expr_match *m;
2264 HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2265 if (match_equal(&m->match, &match->match)) {
2266 if (!m->n || !match->n) {
2267 free(m->conjunctions);
2268 m->conjunctions = NULL;
2272 ovs_assert(match->n == 1);
2273 if (m->n >= m->allocated) {
2274 m->conjunctions = x2nrealloc(m->conjunctions,
2276 sizeof *m->conjunctions);
2278 m->conjunctions[m->n++] = match->conjunctions[0];
2280 free(match->conjunctions);
2286 hmap_insert(matches, &match->hmap_node, hash);
2290 constrain_match(const struct expr *expr, const struct simap *ports,
2293 ovs_assert(expr->type == EXPR_T_CMP);
2294 if (expr->cmp.symbol->width) {
2295 mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2296 &expr->cmp.mask, m);
2298 const struct simap_node *node;
2299 node = ports ? simap_find(ports, expr->cmp.string) : NULL;
2304 struct mf_subfield sf;
2305 sf.field = expr->cmp.symbol->field;
2307 sf.n_bits = expr->cmp.symbol->field->n_bits;
2309 union mf_subvalue x;
2310 memset(&x, 0, sizeof x);
2311 x.integer = htonll(node->data);
2313 mf_write_subfield(&sf, &x, m);
2319 add_disjunction(const struct expr *or, const struct simap *ports,
2320 struct match *m, uint8_t clause, uint8_t n_clauses,
2321 uint32_t conj_id, struct hmap *matches)
2326 ovs_assert(or->type == EXPR_T_OR);
2327 LIST_FOR_EACH (sub, node, &or->andor) {
2328 struct expr_match *match = expr_match_new(m, clause, n_clauses,
2330 if (constrain_match(sub, ports, &match->match)) {
2331 expr_match_add(matches, match);
2334 free(match->conjunctions);
2339 /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2340 * that shouldn't happen much. */
2345 add_conjunction(const struct expr *and, const struct simap *ports,
2346 uint32_t *n_conjsp, struct hmap *matches)
2352 match_init_catchall(&match);
2354 ovs_assert(and->type == EXPR_T_AND);
2355 LIST_FOR_EACH (sub, node, &and->andor) {
2356 switch (sub->type) {
2358 if (!constrain_match(sub, ports, &match)) {
2366 case EXPR_T_BOOLEAN:
2372 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2373 } else if (n_clauses == 1) {
2374 LIST_FOR_EACH (sub, node, &and->andor) {
2375 if (sub->type == EXPR_T_OR) {
2376 add_disjunction(sub, ports, &match, 0, 0, 0, matches);
2382 LIST_FOR_EACH (sub, node, &and->andor) {
2383 if (sub->type == EXPR_T_OR) {
2384 if (!add_disjunction(sub, ports, &match, clause++,
2385 n_clauses, *n_conjsp, matches)) {
2386 /* This clause can't ever match, so we might as well skip
2387 * adding the other clauses--the overall disjunctive flow
2388 * can't ever match. Ideally we would also back out all of
2389 * the clauses we already added, but that seems like a lot
2390 * of trouble for a case that might never occur in
2397 /* Add the flow that matches on conj_id. */
2398 match_set_conj_id(&match, *n_conjsp);
2399 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2404 add_cmp_flow(const struct expr *cmp, const struct simap *ports,
2405 struct hmap *matches)
2407 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2408 if (constrain_match(cmp, ports, &m->match)) {
2409 expr_match_add(matches, m);
2415 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2416 * a collection of Open vSwitch flows in 'matches', which this function
2417 * initializes to an hmap of "struct expr_match" structures. Returns the
2418 * number of conjunctive match IDs consumed by 'matches', which uses
2419 * conjunctive match IDs beginning with 0; the caller must offset or remap them
2420 * into the desired range as necessary.
2422 * The matches inserted into 'matches' will be of three distinct kinds:
2424 * - Ordinary flows. The caller should add these OpenFlow flows with
2425 * its desired actions.
2427 * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2428 * structure. The caller should add these OpenFlow flows with the
2429 * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2430 * remapping the ids.
2432 * - conj_id flows, distinguished by matching on the "conj_id" field. The
2433 * caller should remap the conj_id and add the OpenFlow flow with its
2436 * 'ports' must be a map from strings (presumably names of ports) to integers.
2437 * Any comparisons against string fields in 'expr' are translated into integers
2438 * through this map. A comparison against a string that is not in 'ports' acts
2439 * like a Boolean "false"; that is, it will always fail to match. For a simple
2440 * expression, this means that the overall expression always fails to match,
2441 * but an expression with a disjunction on the string field might still match
2442 * on other port names.
2444 * (This treatment of string fields might be too simplistic in general, but it
2445 * seems reasonable for now when string fields are used only for ports.) */
2447 expr_to_matches(const struct expr *expr, const struct simap *ports,
2448 struct hmap *matches)
2450 uint32_t n_conjs = 0;
2453 switch (expr->type) {
2455 add_cmp_flow(expr, ports, matches);
2459 add_conjunction(expr, ports, &n_conjs, matches);
2463 if (expr_is_cmp(expr)) {
2466 LIST_FOR_EACH (sub, node, &expr->andor) {
2467 add_cmp_flow(sub, ports, matches);
2472 LIST_FOR_EACH (sub, node, &expr->andor) {
2473 if (sub->type == EXPR_T_AND) {
2474 add_conjunction(sub, ports, &n_conjs, matches);
2476 add_cmp_flow(sub, ports, matches);
2482 case EXPR_T_BOOLEAN:
2483 if (expr->boolean) {
2484 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2485 expr_match_add(matches, m);
2494 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2495 * 'matches' hmap itself. */
2497 expr_matches_destroy(struct hmap *matches)
2499 struct expr_match *m, *n;
2501 HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) {
2502 hmap_remove(matches, &m->hmap_node);
2503 free(m->conjunctions);
2506 hmap_destroy(matches);
2509 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2512 expr_matches_print(const struct hmap *matches, FILE *stream)
2514 if (hmap_is_empty(matches)) {
2515 fputs("(no flows)\n", stream);
2519 const struct expr_match *m;
2520 HMAP_FOR_EACH (m, hmap_node, matches) {
2521 char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2526 for (int i = 0; i < m->n; i++) {
2527 const struct cls_conjunction *c = &m->conjunctions[i];
2528 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2529 i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2536 /* Returns true if 'expr' honors the invariants for expressions (see the large
2537 * comment above "struct expr" in expr.h), false otherwise. */
2539 expr_honors_invariants(const struct expr *expr)
2541 const struct expr *sub;
2543 switch (expr->type) {
2545 if (expr->cmp.symbol->width) {
2546 for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2547 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2556 if (list_is_short(&expr->andor)) {
2559 LIST_FOR_EACH (sub, node, &expr->andor) {
2560 if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2566 case EXPR_T_BOOLEAN:
2575 expr_is_normalized_and(const struct expr *expr)
2577 /* XXX should also check that no symbol is repeated. */
2578 const struct expr *sub;
2580 LIST_FOR_EACH (sub, node, &expr->andor) {
2581 if (!expr_is_cmp(sub)) {
2588 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2591 expr_is_normalized(const struct expr *expr)
2593 switch (expr->type) {
2598 return expr_is_normalized_and(expr);
2601 if (!expr_is_cmp(expr)) {
2602 const struct expr *sub;
2604 LIST_FOR_EACH (sub, node, &expr->andor) {
2605 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2612 case EXPR_T_BOOLEAN:
2620 /* Action parsing helper. */
2622 /* Expands 'f' repeatedly as long as it has an expansion, that is, as long as
2623 * it is a subfield or a predicate. Adds any prerequisites for 'f' to
2626 * If 'rw', verifies that 'f' is a read/write field.
2628 * 'exchange' should be true if an exchange action is being parsed. This is
2629 * only used to improve error message phrasing.
2631 * Returns true if successful, false if an error was encountered (in which case
2632 * 'ctx->error' reports the particular error). */
2634 expand_symbol(struct expr_context *ctx, bool rw, bool exchange,
2635 struct expr_field *f, struct expr **prereqsp)
2637 const struct expr_symbol *orig_symbol = f->symbol;
2639 if (f->symbol->expansion && f->symbol->level != EXPR_L_ORDINAL) {
2640 expr_error(ctx, "Predicate symbol %s cannot be used in %s.",
2641 f->symbol->name, exchange ? "exchange" : "assignment");
2646 /* Accumulate prerequisites. */
2647 if (f->symbol->prereqs) {
2648 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2651 e = parse_and_annotate(f->symbol->prereqs, ctx->symtab, &nesting,
2654 expr_error(ctx, "%s", error);
2658 *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
2661 /* If there's no expansion, we're done. */
2662 if (!f->symbol->expansion) {
2667 struct expr_field expansion;
2669 if (!parse_field_from_string(f->symbol->expansion, ctx->symtab,
2670 &expansion, &error)) {
2671 expr_error(ctx, "%s", error);
2675 f->symbol = expansion.symbol;
2676 f->ofs += expansion.ofs;
2679 if (rw && !f->symbol->field->writable) {
2680 expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2688 mf_subfield_from_expr_field(const struct expr_field *f, struct mf_subfield *sf)
2690 sf->field = f->symbol->field;
2692 sf->n_bits = f->n_bits ? f->n_bits : f->symbol->field->n_bits;
2696 init_stack_action(const struct expr_field *f, struct ofpact_stack *stack)
2698 mf_subfield_from_expr_field(f, &stack->subfield);
2701 static struct expr *
2702 parse_assignment(struct expr_context *ctx, const struct simap *ports,
2703 struct ofpbuf *ofpacts)
2705 struct expr *prereqs = NULL;
2707 /* Parse destination and do basic checking. */
2708 struct expr_field dst;
2709 if (!parse_field(ctx, &dst)) {
2712 bool exchange = lexer_match(ctx->lexer, LEX_T_EXCHANGE);
2713 if (!exchange && !lexer_match(ctx->lexer, LEX_T_EQUALS)) {
2714 expr_syntax_error(ctx, "expecting `='.");
2717 const struct expr_symbol *orig_dst = dst.symbol;
2718 if (!expand_symbol(ctx, true, exchange, &dst, &prereqs)) {
2722 if (exchange || ctx->lexer->token.type == LEX_T_ID) {
2723 struct expr_field src;
2724 if (!parse_field(ctx, &src)) {
2727 const struct expr_symbol *orig_src = src.symbol;
2728 if (!expand_symbol(ctx, exchange, exchange, &src, &prereqs)) {
2732 if ((dst.symbol->width != 0) != (src.symbol->width != 0)) {
2735 "Can't exchange %s field (%s) with %s field (%s).",
2736 orig_dst->width ? "integer" : "string",
2738 orig_src->width ? "integer" : "string",
2741 expr_error(ctx, "Can't assign %s field (%s) to %s field (%s).",
2742 orig_src->width ? "integer" : "string",
2744 orig_dst->width ? "integer" : "string",
2750 if (dst.n_bits != src.n_bits) {
2753 "Can't exchange %d-bit field with %d-bit field.",
2754 dst.n_bits, src.n_bits);
2757 "Can't assign %d-bit value to %d-bit destination.",
2758 src.n_bits, dst.n_bits);
2761 } else if (!dst.n_bits
2762 && dst.symbol->field->n_bits != src.symbol->field->n_bits) {
2763 expr_error(ctx, "String fields %s and %s are incompatible for "
2764 "%s.", orig_dst->name, orig_src->name,
2765 exchange ? "exchange" : "assignment");
2770 init_stack_action(&src, ofpact_put_STACK_PUSH(ofpacts));
2771 init_stack_action(&dst, ofpact_put_STACK_PUSH(ofpacts));
2772 init_stack_action(&src, ofpact_put_STACK_POP(ofpacts));
2773 init_stack_action(&dst, ofpact_put_STACK_POP(ofpacts));
2775 struct ofpact_reg_move *move = ofpact_put_REG_MOVE(ofpacts);
2776 mf_subfield_from_expr_field(&src, &move->src);
2777 mf_subfield_from_expr_field(&dst, &move->dst);
2780 struct expr_constant_set cs;
2781 if (!parse_constant_set(ctx, &cs)) {
2785 if (!type_check(ctx, &dst, &cs)) {
2786 goto exit_destroy_cs;
2788 if (cs.in_curlies) {
2789 expr_error(ctx, "Assignments require a single value.");
2790 goto exit_destroy_cs;
2793 union expr_constant *c = cs.values;
2794 struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2795 sf->field = dst.symbol->field;
2796 if (dst.symbol->width) {
2797 mf_subvalue_shift(&c->value, dst.ofs);
2799 memset(&c->mask, 0, sizeof c->mask);
2800 bitwise_one(&c->mask, sizeof c->mask, dst.ofs, dst.n_bits);
2802 mf_subvalue_shift(&c->mask, dst.ofs);
2806 &c->value.u8[sizeof c->value - sf->field->n_bytes],
2807 sf->field->n_bytes);
2809 &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2810 sf->field->n_bytes);
2812 uint32_t port = simap_get(ports, c->string);
2813 bitwise_put(port, &sf->value,
2814 sf->field->n_bytes, 0, sf->field->n_bits);
2815 bitwise_one(&sf->mask, sf->field->n_bytes, 0, sf->field->n_bits);
2817 /* If the logical input port is being zeroed, clear the OpenFlow
2818 * ingress port also, to allow a packet to be sent back to its
2820 if (!port && sf->field->id == MFF_LOG_INPORT) {
2821 sf = ofpact_put_SET_FIELD(ofpacts);
2822 sf->field = mf_from_id(MFF_IN_PORT);
2823 bitwise_one(&sf->mask,
2824 sf->field->n_bytes, 0, sf->field->n_bits);
2829 expr_constant_set_destroy(&cs);
2836 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2837 * "field = value" or "field1 = field2", or a "exchange" action in the form
2838 * "field1 <-> field2", into 'ofpacts'. The parameters and return value match
2839 * those for actions_parse(). */
2841 expr_parse_assignment(struct lexer *lexer, const struct shash *symtab,
2842 const struct simap *ports,
2843 struct ofpbuf *ofpacts, struct expr **prereqsp)
2845 struct expr_context ctx;
2847 ctx.symtab = symtab;
2851 struct expr *prereqs = parse_assignment(&ctx, ports, ofpacts);
2853 expr_destroy(prereqs);
2856 *prereqsp = prereqs;