2 * Copyright (c) 2015, 2016 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.
18 #include "byte-order.h"
20 #include "openvswitch/json.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 "openvswitch/shash.h"
32 VLOG_DEFINE_THIS_MODULE(expr);
34 /* Returns the name of measurement level 'level'. */
36 expr_level_to_string(enum expr_level level)
39 case EXPR_L_NOMINAL: return "nominal";
40 case EXPR_L_BOOLEAN: return "Boolean";
41 case EXPR_L_ORDINAL: return "ordinal";
42 default: OVS_NOT_REACHED();
46 /* Relational operators. */
48 /* Returns a string form of relational operator 'relop'. */
50 expr_relop_to_string(enum expr_relop relop)
53 case EXPR_R_EQ: return "==";
54 case EXPR_R_NE: return "!=";
55 case EXPR_R_LT: return "<";
56 case EXPR_R_LE: return "<=";
57 case EXPR_R_GT: return ">";
58 case EXPR_R_GE: return ">=";
59 default: OVS_NOT_REACHED();
64 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
69 case LEX_T_EQ: r = EXPR_R_EQ; break;
70 case LEX_T_NE: r = EXPR_R_NE; break;
71 case LEX_T_LT: r = EXPR_R_LT; break;
72 case LEX_T_LE: r = EXPR_R_LE; break;
73 case LEX_T_GT: r = EXPR_R_GT; break;
74 case LEX_T_GE: r = EXPR_R_GE; break;
75 default: return false;
84 /* Returns the relational operator that 'relop' becomes if you turn the
85 * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
86 * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
87 * b" is equivalent to "b >= a". */
88 static enum expr_relop
89 expr_relop_turn(enum expr_relop relop)
92 case EXPR_R_EQ: return EXPR_R_EQ;
93 case EXPR_R_NE: return EXPR_R_NE;
94 case EXPR_R_LT: return EXPR_R_GT;
95 case EXPR_R_LE: return EXPR_R_GE;
96 case EXPR_R_GT: return EXPR_R_LT;
97 case EXPR_R_GE: return EXPR_R_LE;
98 default: OVS_NOT_REACHED();
102 /* Returns the relational operator that is the opposite of 'relop'. */
103 static enum expr_relop
104 expr_relop_invert(enum expr_relop relop)
107 case EXPR_R_EQ: return EXPR_R_NE;
108 case EXPR_R_NE: return EXPR_R_EQ;
109 case EXPR_R_LT: return EXPR_R_GE;
110 case EXPR_R_LE: return EXPR_R_GT;
111 case EXPR_R_GT: return EXPR_R_LE;
112 case EXPR_R_GE: return EXPR_R_LT;
113 default: OVS_NOT_REACHED();
117 /* Constructing and manipulating expressions. */
119 /* Creates and returns a logical AND or OR expression (according to 'type',
120 * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
121 * sub-expressions. (To satisfy the invariants for expressions, the caller
122 * must add at least two sub-expressions whose types are different from
125 expr_create_andor(enum expr_type type)
127 struct expr *e = xmalloc(sizeof *e);
129 ovs_list_init(&e->andor);
133 /* Returns a logical AND or OR expression (according to 'type', which must be
134 * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
137 * - If 'a' or 'b' is NULL, just returns the other one (which means that if
138 * that other one is not of the given 'type', then the returned
139 * expression is not either).
141 * - If 'a' or 'b', or both, have type 'type', then they are combined into
142 * a single node that satisfies the invariants for expressions. */
144 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
150 } else if (a->type == type) {
151 if (b->type == type) {
152 ovs_list_splice(&a->andor, b->andor.next, &b->andor);
155 ovs_list_push_back(&a->andor, &b->node);
158 } else if (b->type == type) {
159 ovs_list_push_front(&b->andor, &a->node);
162 struct expr *e = expr_create_andor(type);
163 ovs_list_push_back(&e->andor, &a->node);
164 ovs_list_push_back(&e->andor, &b->node);
170 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
172 if (new->type == andor->type) {
173 if (andor->type == EXPR_T_AND) {
174 /* Conjunction junction, what's your function? */
176 ovs_list_splice(&before->node, new->andor.next, &new->andor);
179 ovs_list_insert(&before->node, &new->node);
183 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
185 expr_create_boolean(bool b)
187 struct expr *e = xmalloc(sizeof *e);
188 e->type = EXPR_T_BOOLEAN;
194 expr_not(struct expr *expr)
198 switch (expr->type) {
200 expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
205 LIST_FOR_EACH (sub, node, &expr->andor) {
208 expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
212 expr->boolean = !expr->boolean;
220 expr_fix_andor(struct expr *expr, bool short_circuit)
222 struct expr *sub, *next;
224 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
225 if (sub->type == EXPR_T_BOOLEAN) {
226 if (sub->boolean == short_circuit) {
228 return expr_create_boolean(short_circuit);
230 ovs_list_remove(&sub->node);
236 if (ovs_list_is_short(&expr->andor)) {
237 if (ovs_list_is_empty(&expr->andor)) {
239 return expr_create_boolean(!short_circuit);
241 sub = expr_from_node(ovs_list_front(&expr->andor));
250 /* Returns 'expr' modified so that top-level oddities are fixed up:
252 * - Eliminates any EXPR_T_BOOLEAN operands at the top level.
254 * - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
256 expr_fix(struct expr *expr)
258 switch (expr->type) {
263 return expr_fix_andor(expr, false);
266 return expr_fix_andor(expr, true);
279 find_bitwise_range(const union mf_subvalue *sv, int width,
280 int *startp, int *n_bitsp)
282 unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
284 unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
286 || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
288 *n_bitsp = end - start;
292 *startp = *n_bitsp = 0;
296 expr_format_cmp(const struct expr *e, struct ds *s)
298 /* The common case is numerical comparisons.
299 * Handle string comparisons as a special case. */
300 if (!e->cmp.symbol->width) {
301 ds_put_format(s, "%s %s ", e->cmp.symbol->name,
302 expr_relop_to_string(e->cmp.relop));
303 json_string_escape(e->cmp.string, s);
308 find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
309 if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
312 positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
313 positive ^= e->cmp.relop == EXPR_R_NE;
317 ds_put_cstr(s, e->cmp.symbol->name);
318 if (e->cmp.symbol->width > 1) {
319 ds_put_format(s, "[%d]", ofs);
324 ds_put_cstr(s, e->cmp.symbol->name);
325 if (n > 0 && n < e->cmp.symbol->width) {
327 ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
329 ds_put_format(s, "[%d]", ofs);
333 ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
336 union mf_subvalue value;
338 memset(&value, 0, sizeof value);
339 bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
340 &value, sizeof value, 0,
342 mf_format_subvalue(&value, s);
344 mf_format_subvalue(&e->cmp.value, s);
346 mf_format_subvalue(&e->cmp.mask, s);
351 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
356 LIST_FOR_EACH (sub, node, &e->andor) {
358 ds_put_format(s, " %s ", op);
361 if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
371 /* Appends a string form of 'e' to 's'. The string form is acceptable for
372 * parsing back into an equivalent expression. */
374 expr_format(const struct expr *e, struct ds *s)
378 expr_format_cmp(e, s);
382 expr_format_andor(e, "&&", s);
386 expr_format_andor(e, "||", s);
390 ds_put_char(s, e->boolean ? '1' : '0');
395 /* Prints a string form of 'e' on stdout, followed by a new-line. */
397 expr_print(const struct expr *e)
402 expr_format(e, &output);
403 puts(ds_cstr(&output));
409 /* Context maintained during expr_parse(). */
410 struct expr_context {
411 struct lexer *lexer; /* Lexer for pulling more tokens. */
412 const struct shash *symtab; /* Symbol table. */
413 const struct shash *macros; /* Table of macros. */
414 char *error; /* Error, if any, otherwise NULL. */
415 bool not; /* True inside odd number of NOT operators. */
418 struct expr *expr_parse__(struct expr_context *);
419 static void expr_not(struct expr *);
420 static bool parse_field(struct expr_context *, struct expr_field *);
423 expr_error_handle_common(struct expr_context *ctx)
426 /* Already have an error, suppress this one since the cascade seems
427 * unlikely to be useful. */
429 } else if (ctx->lexer->token.type == LEX_T_ERROR) {
430 /* The lexer signaled an error. Nothing at the expression level
431 * accepts an error token, so we'll inevitably end up here with some
432 * meaningless parse error. Report the lexical error instead. */
433 ctx->error = xstrdup(ctx->lexer->token.s);
440 static void OVS_PRINTF_FORMAT(2, 3)
441 expr_error(struct expr_context *ctx, const char *message, ...)
443 if (expr_error_handle_common(ctx)) {
448 va_start(args, message);
449 ctx->error = xvasprintf(message, args);
453 static void OVS_PRINTF_FORMAT(2, 3)
454 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
456 if (expr_error_handle_common(ctx)) {
463 ds_put_cstr(&s, "Syntax error ");
464 if (ctx->lexer->token.type == LEX_T_END) {
465 ds_put_cstr(&s, "at end of input ");
466 } else if (ctx->lexer->start) {
467 ds_put_format(&s, "at `%.*s' ",
468 (int) (ctx->lexer->input - ctx->lexer->start),
473 va_start(args, message);
474 ds_put_format_valist(&s, message, args);
477 ctx->error = ds_steal_cstr(&s);
481 make_cmp__(const struct expr_field *f, enum expr_relop r,
482 const union expr_constant *c)
484 struct expr *e = xzalloc(sizeof *e);
485 e->type = EXPR_T_CMP;
486 e->cmp.symbol = f->symbol;
488 if (f->symbol->width) {
489 bitwise_copy(&c->value, sizeof c->value, 0,
490 &e->cmp.value, sizeof e->cmp.value, f->ofs,
493 bitwise_copy(&c->mask, sizeof c->mask, 0,
494 &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
497 bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
501 e->cmp.string = xstrdup(c->string);
506 /* Returns the minimum reasonable width for integer constant 'c'. */
508 expr_constant_width(const union expr_constant *c)
511 return mf_subvalue_width(&c->mask);
516 case LEX_F_HEXADECIMAL:
517 return mf_subvalue_width(&c->value);
534 type_check(struct expr_context *ctx, const struct expr_field *f,
535 struct expr_constant_set *cs)
537 if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
538 expr_error(ctx, "%s field %s is not compatible with %s constant.",
539 f->symbol->width ? "Integer" : "String",
541 cs->type == EXPR_C_INTEGER ? "integer" : "string");
545 if (f->symbol->width) {
546 for (size_t i = 0; i < cs->n_values; i++) {
547 int w = expr_constant_width(&cs->values[i]);
548 if (w > f->symbol->width) {
549 expr_error(ctx, "%d-bit constant is not compatible with "
551 w, f->symbol->width, f->symbol->name);
561 make_cmp(struct expr_context *ctx,
562 const struct expr_field *f, enum expr_relop r,
563 struct expr_constant_set *cs)
565 struct expr *e = NULL;
567 if (!type_check(ctx, f, cs)) {
571 if (r != EXPR_R_EQ && r != EXPR_R_NE) {
572 if (cs->in_curlies) {
573 expr_error(ctx, "Only == and != operators may be used "
577 if (f->symbol->level == EXPR_L_NOMINAL ||
578 f->symbol->level == EXPR_L_BOOLEAN) {
579 expr_error(ctx, "Only == and != operators may be used "
581 expr_level_to_string(f->symbol->level),
585 if (cs->values[0].masked) {
586 expr_error(ctx, "Only == and != operators may be used with "
587 "masked constants. Consider using subfields instead "
588 "(e.g. eth.src[0..15] > 0x1111 in place of "
589 "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
594 if (f->symbol->level == EXPR_L_NOMINAL) {
595 if (f->symbol->expansion) {
596 ovs_assert(f->symbol->width > 0);
597 for (size_t i = 0; i < cs->n_values; i++) {
598 const union mf_subvalue *value = &cs->values[i].value;
599 bool positive = (value->integer & htonll(1)) != 0;
600 positive ^= r == EXPR_R_NE;
601 positive ^= ctx->not;
603 const char *name = f->symbol->name;
604 expr_error(ctx, "Nominal predicate %s may only be tested "
605 "positively, e.g. `%s' or `%s == 1' but not "
606 "`!%s' or `%s == 0'.",
607 name, name, name, name, name);
611 } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
612 expr_error(ctx, "Nominal field %s may only be tested for "
613 "equality (taking enclosing `!' operators into "
614 "account).", f->symbol->name);
619 e = make_cmp__(f, r, &cs->values[0]);
620 for (size_t i = 1; i < cs->n_values; i++) {
621 e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
622 e, make_cmp__(f, r, &cs->values[i]));
625 expr_constant_set_destroy(cs);
630 expr_get_int(struct expr_context *ctx, int *value)
632 bool ok = lexer_get_int(ctx->lexer, value);
634 expr_syntax_error(ctx, "expecting small integer.");
640 parse_field(struct expr_context *ctx, struct expr_field *f)
642 const struct expr_symbol *symbol;
644 if (ctx->lexer->token.type != LEX_T_ID) {
645 expr_syntax_error(ctx, "expecting field name.");
649 symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
651 expr_syntax_error(ctx, "expecting field name.");
654 lexer_get(ctx->lexer);
657 if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
660 if (!symbol->width) {
661 expr_error(ctx, "Cannot select subfield of string field %s.",
666 if (!expr_get_int(ctx, &low)) {
669 if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
670 if (!expr_get_int(ctx, &high)) {
677 if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
678 expr_syntax_error(ctx, "expecting `]'.");
683 expr_error(ctx, "Invalid bit range %d to %d.", low, high);
685 } else if (high >= symbol->width) {
686 expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
687 low, high, symbol->width, symbol->name);
689 } else if (symbol->level == EXPR_L_NOMINAL
690 && (low != 0 || high != symbol->width - 1)) {
691 expr_error(ctx, "Cannot select subfield of nominal field %s.",
697 f->n_bits = high - low + 1;
700 f->n_bits = symbol->width;
707 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
709 if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
710 lexer_get(ctx->lexer);
713 expr_syntax_error(ctx, "expecting relational operator.");
719 assign_constant_set_type(struct expr_context *ctx,
720 struct expr_constant_set *cs,
721 enum expr_constant_type type)
723 if (!cs->n_values || cs->type == type) {
727 expr_syntax_error(ctx, "expecting %s.",
728 cs->type == EXPR_C_INTEGER ? "integer" : "string");
734 parse_macros(struct expr_context *ctx, struct expr_constant_set *cs,
735 size_t *allocated_values)
737 struct expr_constant_set *addr_set
738 = shash_find_data(ctx->macros, ctx->lexer->token.s);
740 expr_syntax_error(ctx, "expecting address set name.");
744 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
748 size_t n_values = cs->n_values + addr_set->n_values;
749 if (n_values >= *allocated_values) {
750 cs->values = xrealloc(cs->values, n_values * sizeof *cs->values);
751 *allocated_values = n_values;
753 for (size_t i = 0; i < addr_set->n_values; i++) {
754 cs->values[cs->n_values++] = addr_set->values[i];
761 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
762 size_t *allocated_values)
764 if (cs->n_values >= *allocated_values) {
765 cs->values = x2nrealloc(cs->values, allocated_values,
769 if (ctx->lexer->token.type == LEX_T_STRING) {
770 if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
773 cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
774 lexer_get(ctx->lexer);
776 } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
777 ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
778 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
782 union expr_constant *c = &cs->values[cs->n_values++];
783 c->value = ctx->lexer->token.value;
784 c->format = ctx->lexer->token.format;
785 c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
787 c->mask = ctx->lexer->token.mask;
789 lexer_get(ctx->lexer);
791 } else if (ctx->lexer->token.type == LEX_T_MACRO) {
792 if (!parse_macros(ctx, cs, allocated_values)) {
795 lexer_get(ctx->lexer);
798 expr_syntax_error(ctx, "expecting constant.");
803 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
804 * which the caller need not have initialized. Returns true on success, in
805 * which case the caller owns 'cs', false on failure, in which case 'cs' is
808 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
810 size_t allocated_values = 0;
813 memset(cs, 0, sizeof *cs);
814 if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
816 cs->in_curlies = true;
818 if (!parse_constant(ctx, cs, &allocated_values)) {
822 lexer_match(ctx->lexer, LEX_T_COMMA);
823 } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
825 ok = parse_constant(ctx, cs, &allocated_values);
828 expr_constant_set_destroy(cs);
834 expr_constant_set_destroy(struct expr_constant_set *cs)
837 if (cs->type == EXPR_C_STRING) {
838 for (size_t i = 0; i < cs->n_values; i++) {
839 free(cs->values[i].string);
846 /* Adds a macro named 'name' to 'macros', replacing any existing macro with the
849 expr_macros_add(struct shash *macros, const char *name,
850 const char *const *values, size_t n_values)
852 /* Replace any existing entry for this name. */
853 expr_macros_remove(macros, name);
855 struct expr_constant_set *cs = xzalloc(sizeof *cs);
856 cs->type = EXPR_C_INTEGER;
857 cs->in_curlies = true;
859 cs->values = xmalloc(n_values * sizeof *cs->values);
860 for (size_t i = 0; i < n_values; i++) {
861 /* Use the lexer to convert each macro into the proper
864 lexer_init(&lex, values[i]);
866 if (lex.token.type != LEX_T_INTEGER
867 && lex.token.type != LEX_T_MASKED_INTEGER) {
868 VLOG_WARN("Invalid address set entry: '%s', token type: %d",
869 values[i], lex.token.type);
871 union expr_constant *c = &cs->values[cs->n_values++];
872 c->value = lex.token.value;
873 c->format = lex.token.format;
874 c->masked = lex.token.type == LEX_T_MASKED_INTEGER;
876 c->mask = lex.token.mask;
882 shash_add(macros, name, cs);
886 expr_macros_remove(struct shash *macros, const char *name)
888 struct expr_constant_set *cs = shash_find_and_delete(macros, name);
890 expr_constant_set_destroy(cs);
895 /* Destroy all contents of 'macros'. */
897 expr_macros_destroy(struct shash *macros)
899 struct shash_node *node, *next;
901 SHASH_FOR_EACH_SAFE (node, next, macros) {
902 struct expr_constant_set *cs = node->data;
904 shash_delete(macros, node);
905 expr_constant_set_destroy(cs);
910 expr_parse_primary(struct expr_context *ctx, bool *atomic)
913 if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
914 struct expr *e = expr_parse__(ctx);
915 if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
917 expr_syntax_error(ctx, "expecting `)'.");
924 if (ctx->lexer->token.type == LEX_T_ID) {
927 struct expr_constant_set c;
929 if (!parse_field(ctx, &f)) {
933 if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
934 if (f.n_bits > 1 && !ctx->not) {
935 expr_error(ctx, "Explicit `!= 0' is required for inequality "
936 "test of multibit field against 0.");
942 union expr_constant *cst = xzalloc(sizeof *cst);
943 cst->format = LEX_F_HEXADECIMAL;
946 c.type = EXPR_C_INTEGER;
949 c.in_curlies = false;
950 return make_cmp(ctx, &f, EXPR_R_NE, &c);
951 } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
952 return make_cmp(ctx, &f, r, &c);
957 struct expr_constant_set c1;
958 if (!parse_constant_set(ctx, &c1)) {
962 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
964 && c1.type == EXPR_C_INTEGER
965 && c1.values[0].format == LEX_F_DECIMAL
966 && !c1.values[0].masked
968 uint64_t x = ntohll(c1.values[0].value.integer);
971 expr_constant_set_destroy(&c1);
972 return expr_create_boolean(x);
978 if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
979 expr_constant_set_destroy(&c1);
983 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
984 return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
988 struct expr_constant_set c2;
989 if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
990 expr_constant_set_destroy(&c1);
993 /* Reject "1 == field == 2", "1 < field > 2", and so on. */
994 if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
995 (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
996 ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
997 (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
998 expr_error(ctx, "Range expressions must have the form "
999 "`x < field < y' or `x > field > y', with each "
1000 "`<' optionally replaced by `<=' or `>' by `>=').");
1001 expr_constant_set_destroy(&c1);
1002 expr_constant_set_destroy(&c2);
1006 struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
1007 struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
1013 return expr_combine(EXPR_T_AND, e1, e2);
1018 static struct expr *
1019 expr_parse_not(struct expr_context *ctx)
1023 if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
1024 ctx->not = !ctx->not;
1025 struct expr *expr = expr_parse_primary(ctx, &atomic);
1026 ctx->not = !ctx->not;
1030 expr_error(ctx, "Missing parentheses around operand of !.");
1038 return expr_parse_primary(ctx, &atomic);
1043 expr_parse__(struct expr_context *ctx)
1045 struct expr *e = expr_parse_not(ctx);
1050 enum lex_type lex_type = ctx->lexer->token.type;
1051 if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
1052 enum expr_type expr_type
1053 = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
1055 lexer_get(ctx->lexer);
1057 struct expr *e2 = expr_parse_not(ctx);
1062 e = expr_combine(expr_type, e, e2);
1063 } while (lexer_match(ctx->lexer, lex_type));
1064 if (ctx->lexer->token.type == LEX_T_LOG_AND
1065 || ctx->lexer->token.type == LEX_T_LOG_OR) {
1068 "&& and || must be parenthesized when used together.");
1075 /* Parses an expression using the symbols in 'symtab' from 'lexer'. If
1076 * successful, returns the new expression and sets '*errorp' to NULL. On
1077 * failure, returns NULL and sets '*errorp' to an explanatory error message.
1078 * The caller must eventually free the returned expression (with
1079 * expr_destroy()) or error (with free()). */
1081 expr_parse(struct lexer *lexer, const struct shash *symtab,
1082 const struct shash *macros, char **errorp)
1084 struct expr_context ctx = { .lexer = lexer,
1087 struct expr *e = expr_parse__(&ctx);
1088 *errorp = ctx.error;
1089 ovs_assert((ctx.error != NULL) != (e != NULL));
1093 /* Like expr_parse(), but the expression is taken from 's'. */
1095 expr_parse_string(const char *s, const struct shash *symtab,
1096 const struct shash *macros, char **errorp)
1101 lexer_init(&lexer, s);
1103 expr = expr_parse(&lexer, symtab, macros, errorp);
1104 if (!*errorp && lexer.token.type != LEX_T_END) {
1105 *errorp = xstrdup("Extra tokens at end of input.");
1109 lexer_destroy(&lexer);
1114 static struct expr_symbol *
1115 add_symbol(struct shash *symtab, const char *name, int width,
1116 const char *prereqs, enum expr_level level,
1117 bool must_crossproduct)
1119 struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1120 symbol->name = xstrdup(name);
1121 symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1122 symbol->width = width;
1123 symbol->level = level;
1124 symbol->must_crossproduct = must_crossproduct;
1125 shash_add_assert(symtab, symbol->name, symbol);
1129 /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1130 * 'name' is referenced, expression annotation (see expr_annotate()) will
1131 * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1132 * conversion to flows will never attempt to use the field as a conjunctive
1133 * match dimension (see "Crossproducting" in the large comment on struct
1134 * expr_symbol in expr.h for an example).
1136 * A given field 'id' must only be used for a single symbol in a symbol table.
1137 * Use subfields to duplicate or subset a field (you can even make a subfield
1138 * include all the bits of the "parent" field if you like). */
1139 struct expr_symbol *
1140 expr_symtab_add_field(struct shash *symtab, const char *name,
1141 enum mf_field_id id, const char *prereqs,
1142 bool must_crossproduct)
1144 const struct mf_field *field = mf_from_id(id);
1145 struct expr_symbol *symbol;
1147 symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1148 (field->maskable == MFM_FULLY
1152 symbol->field = field;
1157 parse_field_from_string(const char *s, const struct shash *symtab,
1158 struct expr_field *field, char **errorp)
1161 lexer_init(&lexer, s);
1164 struct expr_context ctx = { .lexer = &lexer, .symtab = symtab };
1165 bool ok = parse_field(&ctx, field);
1167 *errorp = ctx.error;
1168 } else if (lexer.token.type != LEX_T_END) {
1169 *errorp = xstrdup("Extra tokens at end of input.");
1173 lexer_destroy(&lexer);
1178 /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1179 * 'name' is referenced, expression annotation (see expr_annotate()) will
1180 * ensure that 'prereqs' are also true.
1182 * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1183 * for the low 12 bits of a larger field named "vlan.tci". */
1184 struct expr_symbol *
1185 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1186 const char *prereqs, const char *subfield)
1188 struct expr_symbol *symbol;
1189 struct expr_field f;
1192 if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1193 VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1198 enum expr_level level = f.symbol->level;
1199 if (level != EXPR_L_ORDINAL) {
1200 VLOG_WARN("can't define %s as subfield of %s field %s",
1201 name, expr_level_to_string(level), f.symbol->name);
1204 symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1205 symbol->expansion = xstrdup(subfield);
1209 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1211 struct expr_symbol *
1212 expr_symtab_add_string(struct shash *symtab, const char *name,
1213 enum mf_field_id id, const char *prereqs)
1215 const struct mf_field *field = mf_from_id(id);
1216 struct expr_symbol *symbol;
1218 symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1219 symbol->field = field;
1223 static enum expr_level
1224 expr_get_level(const struct expr *expr)
1226 const struct expr *sub;
1227 enum expr_level level = EXPR_L_ORDINAL;
1229 switch (expr->type) {
1231 return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1237 LIST_FOR_EACH (sub, node, &expr->andor) {
1238 enum expr_level sub_level = expr_get_level(sub);
1239 level = MIN(level, sub_level);
1243 case EXPR_T_BOOLEAN:
1244 return EXPR_L_BOOLEAN;
1251 static enum expr_level
1252 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1254 struct expr *expr = expr_parse_string(s, symtab, NULL, errorp);
1255 enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1260 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1261 * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 6" might be an
1262 * appropriate predicate named "tcp4". */
1263 struct expr_symbol *
1264 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1265 const char *expansion)
1267 struct expr_symbol *symbol;
1268 enum expr_level level;
1271 level = expr_parse_level(expansion, symtab, &error);
1273 VLOG_WARN("%s: error parsing %s expansion (%s)",
1274 expansion, name, error);
1279 symbol = add_symbol(symtab, name, 1, NULL, level, false);
1280 symbol->expansion = xstrdup(expansion);
1284 /* Destroys 'symtab' and all of its symbols. */
1286 expr_symtab_destroy(struct shash *symtab)
1288 struct shash_node *node, *next;
1290 SHASH_FOR_EACH_SAFE (node, next, symtab) {
1291 struct expr_symbol *symbol = node->data;
1293 shash_delete(symtab, node);
1295 free(symbol->prereqs);
1296 free(symbol->expansion);
1303 static struct expr *
1304 expr_clone_cmp(struct expr *expr)
1306 struct expr *new = xmemdup(expr, sizeof *expr);
1307 if (!new->cmp.symbol->width) {
1308 new->cmp.string = xstrdup(new->cmp.string);
1313 static struct expr *
1314 expr_clone_andor(struct expr *expr)
1316 struct expr *new = expr_create_andor(expr->type);
1319 LIST_FOR_EACH (sub, node, &expr->andor) {
1320 struct expr *new_sub = expr_clone(sub);
1321 ovs_list_push_back(&new->andor, &new_sub->node);
1326 /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1327 * expression nor any of its substructure will be shared with 'expr'. */
1329 expr_clone(struct expr *expr)
1331 switch (expr->type) {
1333 return expr_clone_cmp(expr);
1337 return expr_clone_andor(expr);
1339 case EXPR_T_BOOLEAN:
1340 return expr_create_boolean(expr->boolean);
1345 /* Destroys 'expr' and all of the sub-expressions it references. */
1347 expr_destroy(struct expr *expr)
1353 struct expr *sub, *next;
1355 switch (expr->type) {
1357 if (!expr->cmp.symbol->width) {
1358 free(expr->cmp.string);
1364 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1365 ovs_list_remove(&sub->node);
1370 case EXPR_T_BOOLEAN:
1378 /* An element in a linked list of symbols.
1380 * Used to detect when a symbol is being expanded recursively, to allow
1381 * flagging an error. */
1382 struct annotation_nesting {
1383 struct ovs_list node;
1384 const struct expr_symbol *symbol;
1387 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1388 struct ovs_list *nesting, char **errorp);
1390 static struct expr *
1391 parse_and_annotate(const char *s, const struct shash *symtab,
1392 struct ovs_list *nesting, char **errorp)
1397 expr = expr_parse_string(s, symtab, NULL, &error);
1399 expr = expr_annotate__(expr, symtab, nesting, &error);
1404 *errorp = xasprintf("Error parsing expression `%s' encountered as "
1405 "prerequisite or predicate of initial expression: "
1412 static struct expr *
1413 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1414 struct ovs_list *nesting, char **errorp)
1416 const struct expr_symbol *symbol = expr->cmp.symbol;
1417 const struct annotation_nesting *iter;
1418 LIST_FOR_EACH (iter, node, nesting) {
1419 if (iter->symbol == symbol) {
1420 *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1427 struct annotation_nesting an;
1429 ovs_list_push_back(nesting, &an.node);
1431 struct expr *prereqs = NULL;
1432 if (symbol->prereqs) {
1433 prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1439 if (symbol->expansion) {
1440 if (symbol->level == EXPR_L_ORDINAL) {
1441 struct expr_field field;
1443 if (!parse_field_from_string(symbol->expansion, symtab,
1448 expr->cmp.symbol = field.symbol;
1449 mf_subvalue_shift(&expr->cmp.value, field.ofs);
1450 mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1452 struct expr *expansion;
1454 expansion = parse_and_annotate(symbol->expansion, symtab,
1460 bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1461 positive ^= expr->cmp.relop == EXPR_R_NE;
1463 expr_not(expansion);
1471 ovs_list_remove(&an.node);
1472 return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1476 expr_destroy(prereqs);
1477 ovs_list_remove(&an.node);
1482 expr_annotate__(struct expr *expr, const struct shash *symtab,
1483 struct ovs_list *nesting, char **errorp)
1485 switch (expr->type) {
1487 return expr_annotate_cmp(expr, symtab, nesting, errorp);
1491 struct expr *sub, *next;
1493 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1494 ovs_list_remove(&sub->node);
1495 struct expr *new_sub = expr_annotate__(sub, symtab,
1501 expr_insert_andor(expr, next, new_sub);
1507 case EXPR_T_BOOLEAN:
1516 /* "Annotates" 'expr', which does the following:
1518 * - Applies prerequisites, by locating each comparison operator whose
1519 * field has a prerequisite and adding a logical AND against those
1522 * - Expands references to subfield symbols, by replacing them by
1523 * references to their underlying field symbols (suitably shifted).
1525 * - Expands references to predicate symbols, by replacing them by the
1526 * expressions that they expand to.
1528 * In each case, annotation occurs recursively as necessary.
1530 * On failure, returns NULL and sets '*errorp' to an explanatory error
1531 * message, which the caller must free. */
1533 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1535 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1536 return expr_annotate__(expr, symtab, &nesting, errorp);
1539 static struct expr *
1540 expr_simplify_ne(struct expr *expr)
1542 struct expr *new = NULL;
1543 const union mf_subvalue *value = &expr->cmp.value;
1544 const union mf_subvalue *mask = &expr->cmp.mask;
1545 int w = expr->cmp.symbol->width;
1548 for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1551 e = xzalloc(sizeof *e);
1552 e->type = EXPR_T_CMP;
1553 e->cmp.symbol = expr->cmp.symbol;
1554 e->cmp.relop = EXPR_R_EQ;
1555 bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1556 !bitwise_get_bit(value, sizeof *value, i));
1557 bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1559 new = expr_combine(EXPR_T_OR, new, e);
1568 static struct expr *
1569 expr_simplify_relational(struct expr *expr)
1571 const union mf_subvalue *value = &expr->cmp.value;
1572 int start, n_bits, end;
1574 find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1576 ovs_assert(n_bits > 0);
1577 end = start + n_bits;
1580 if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1581 new = xmemdup(expr, sizeof *expr);
1582 new->cmp.relop = EXPR_R_EQ;
1587 bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1588 for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1590 z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1593 e = xmemdup(expr, sizeof *expr);
1594 e->cmp.relop = EXPR_R_EQ;
1595 bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1596 bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1597 bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1598 new = expr_combine(EXPR_T_OR, new, e);
1601 return new ? new : expr_create_boolean(false);
1604 /* Takes ownership of 'expr' and returns an equivalent expression whose
1605 * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1607 expr_simplify(struct expr *expr)
1609 struct expr *sub, *next;
1611 switch (expr->type) {
1613 return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1614 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1615 : expr_simplify_relational(expr));
1619 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1620 ovs_list_remove(&sub->node);
1621 expr_insert_andor(expr, next, expr_simplify(sub));
1623 return expr_fix(expr);
1625 case EXPR_T_BOOLEAN:
1631 static const struct expr_symbol *
1632 expr_is_cmp(const struct expr *expr)
1634 switch (expr->type) {
1636 return expr->cmp.symbol;
1640 const struct expr_symbol *prev = NULL;
1643 LIST_FOR_EACH (sub, node, &expr->andor) {
1644 const struct expr_symbol *symbol = expr_is_cmp(sub);
1645 if (!symbol || (prev && symbol != prev)) {
1653 case EXPR_T_BOOLEAN:
1663 const struct expr_symbol *relop;
1664 enum expr_type type;
1668 compare_expr_sort(const void *a_, const void *b_)
1670 const struct expr_sort *a = a_;
1671 const struct expr_sort *b = b_;
1673 if (a->type != b->type) {
1674 return a->type < b->type ? -1 : 1;
1675 } else if (a->relop) {
1676 int cmp = strcmp(a->relop->name, b->relop->name);
1681 enum expr_type a_type = a->expr->type;
1682 enum expr_type b_type = a->expr->type;
1683 return a_type < b_type ? -1 : a_type > b_type;
1684 } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1685 size_t a_len = ovs_list_size(&a->expr->andor);
1686 size_t b_len = ovs_list_size(&b->expr->andor);
1687 return a_len < b_len ? -1 : a_len > b_len;
1693 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1696 disjunction_matches_string(const struct expr *or, const char *s)
1698 const struct expr *sub;
1700 LIST_FOR_EACH (sub, node, &or->andor) {
1701 if (!strcmp(sub->cmp.string, s)) {
1709 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1710 * string-typed 'symbol'. */
1711 static struct expr *
1712 crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1714 ovs_assert(!ovs_list_is_short(&expr->andor));
1716 struct expr *singleton = NULL;
1718 /* First crush each subexpression into either a single EXPR_T_CMP or an
1719 * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1720 struct expr *sub, *next = NULL;
1721 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1722 ovs_list_remove(&sub->node);
1723 struct expr *new = crush_cmps(sub, symbol);
1724 switch (new->type) {
1727 ovs_list_insert(&next->node, &new->node);
1730 bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1734 return expr_create_boolean(false);
1741 ovs_list_insert(&next->node, &new->node);
1743 case EXPR_T_BOOLEAN:
1744 if (!new->boolean) {
1753 /* If we have a singleton, then the result is either the singleton itself
1754 * (if the ORs allow the singleton) or false. */
1756 LIST_FOR_EACH (sub, node, &expr->andor) {
1757 if (sub->type == EXPR_T_OR
1758 && !disjunction_matches_string(sub, singleton->cmp.string)) {
1760 return expr_create_boolean(false);
1763 ovs_list_remove(&singleton->node);
1768 /* Otherwise the result is the intersection of all of the ORs. */
1769 struct sset result = SSET_INITIALIZER(&result);
1770 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1771 struct sset strings = SSET_INITIALIZER(&strings);
1772 const struct expr *s;
1773 LIST_FOR_EACH (s, node, &sub->andor) {
1774 sset_add(&strings, s->cmp.string);
1776 if (sset_is_empty(&result)) {
1777 sset_swap(&result, &strings);
1779 sset_intersect(&result, &strings);
1781 sset_destroy(&strings);
1783 if (sset_is_empty(&result)) {
1785 sset_destroy(&result);
1786 return expr_create_boolean(false);
1791 expr = expr_create_andor(EXPR_T_OR);
1794 SSET_FOR_EACH (string, &result) {
1795 sub = xmalloc(sizeof *sub);
1796 sub->type = EXPR_T_CMP;
1797 sub->cmp.symbol = symbol;
1798 sub->cmp.string = xstrdup(string);
1799 ovs_list_push_back(&expr->andor, &sub->node);
1801 sset_destroy(&result);
1802 return expr_fix(expr);
1805 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1806 * numeric-typed 'symbol'. */
1807 static struct expr *
1808 crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1810 ovs_assert(!ovs_list_is_short(&expr->andor));
1812 union mf_subvalue value, mask;
1813 memset(&value, 0, sizeof value);
1814 memset(&mask, 0, sizeof mask);
1816 struct expr *sub, *next = NULL;
1817 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1818 ovs_list_remove(&sub->node);
1819 struct expr *new = crush_cmps(sub, symbol);
1820 switch (new->type) {
1822 if (!mf_subvalue_intersect(&value, &mask,
1823 &new->cmp.value, &new->cmp.mask,
1827 return expr_create_boolean(false);
1834 ovs_list_insert(&next->node, &new->node);
1836 case EXPR_T_BOOLEAN:
1837 if (!new->boolean) {
1845 if (ovs_list_is_empty(&expr->andor)) {
1846 if (is_all_zeros(&mask, sizeof mask)) {
1848 return expr_create_boolean(true);
1851 cmp = xmalloc(sizeof *cmp);
1852 cmp->type = EXPR_T_CMP;
1853 cmp->cmp.symbol = symbol;
1854 cmp->cmp.relop = EXPR_R_EQ;
1855 cmp->cmp.value = value;
1856 cmp->cmp.mask = mask;
1860 } else if (ovs_list_is_short(&expr->andor)) {
1861 /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1862 * computed as "a && b", etc. */
1863 struct expr *disjuncts = expr_from_node(ovs_list_pop_front(&expr->andor));
1866 or = xmalloc(sizeof *or);
1867 or->type = EXPR_T_OR;
1868 ovs_list_init(&or->andor);
1870 ovs_assert(disjuncts->type == EXPR_T_OR);
1871 LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1872 ovs_assert(sub->type == EXPR_T_CMP);
1873 ovs_list_remove(&sub->node);
1874 if (mf_subvalue_intersect(&value, &mask,
1875 &sub->cmp.value, &sub->cmp.mask,
1876 &sub->cmp.value, &sub->cmp.mask)) {
1877 ovs_list_push_back(&or->andor, &sub->node);
1884 if (ovs_list_is_empty(&or->andor)) {
1886 return expr_create_boolean(false);
1887 } else if (ovs_list_is_short(&or->andor)) {
1888 struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1895 /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1896 * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1897 struct expr *as = expr_from_node(ovs_list_pop_front(&expr->andor));
1898 struct expr *bs = expr_from_node(ovs_list_pop_front(&expr->andor));
1899 struct expr *new = NULL;
1902 or = xmalloc(sizeof *or);
1903 or->type = EXPR_T_OR;
1904 ovs_list_init(&or->andor);
1907 LIST_FOR_EACH (a, node, &as->andor) {
1908 union mf_subvalue a_value, a_mask;
1910 ovs_assert(a->type == EXPR_T_CMP);
1911 if (!mf_subvalue_intersect(&value, &mask,
1912 &a->cmp.value, &a->cmp.mask,
1913 &a_value, &a_mask)) {
1918 LIST_FOR_EACH (b, node, &bs->andor) {
1919 ovs_assert(b->type == EXPR_T_CMP);
1921 new = xmalloc(sizeof *new);
1922 new->type = EXPR_T_CMP;
1923 new->cmp.symbol = symbol;
1924 new->cmp.relop = EXPR_R_EQ;
1926 if (mf_subvalue_intersect(&a_value, &a_mask,
1927 &b->cmp.value, &b->cmp.mask,
1928 &new->cmp.value, &new->cmp.mask)) {
1929 ovs_list_push_back(&or->andor, &new->node);
1938 if (ovs_list_is_empty(&or->andor)) {
1941 return expr_create_boolean(false);
1942 } else if (ovs_list_is_short(&or->andor)) {
1943 struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1945 if (ovs_list_is_empty(&expr->andor)) {
1947 return crush_cmps(cmp, symbol);
1949 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1951 } else if (!ovs_list_is_empty(&expr->andor)) {
1952 struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1953 ovs_assert(!ovs_list_is_short(&e->andor));
1954 return crush_cmps(e, symbol);
1957 return crush_cmps(or, symbol);
1963 compare_cmps_3way(const struct expr *a, const struct expr *b)
1965 ovs_assert(a->cmp.symbol == b->cmp.symbol);
1966 if (!a->cmp.symbol->width) {
1967 return strcmp(a->cmp.string, b->cmp.string);
1969 int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1971 d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1978 compare_cmps_cb(const void *a_, const void *b_)
1980 const struct expr *const *ap = a_;
1981 const struct expr *const *bp = b_;
1982 const struct expr *a = *ap;
1983 const struct expr *b = *bp;
1984 return compare_cmps_3way(a, b);
1987 /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
1988 static struct expr *
1989 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1991 struct expr *sub, *next = NULL;
1993 /* First, crush all the subexpressions. That might eliminate the
1994 * OR-expression entirely; if so, return the result. Otherwise, 'expr'
1995 * is now a disjunction of cmps over the same symbol. */
1996 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1997 ovs_list_remove(&sub->node);
1998 expr_insert_andor(expr, next, crush_cmps(sub, symbol));
2000 expr = expr_fix(expr);
2001 if (expr->type != EXPR_T_OR) {
2005 /* Sort subexpressions by value and mask, to bring together duplicates. */
2006 size_t n = ovs_list_size(&expr->andor);
2007 struct expr **subs = xmalloc(n * sizeof *subs);
2010 LIST_FOR_EACH (sub, node, &expr->andor) {
2015 qsort(subs, n, sizeof *subs, compare_cmps_cb);
2017 /* Eliminate duplicates. */
2018 ovs_list_init(&expr->andor);
2019 ovs_list_push_back(&expr->andor, &subs[0]->node);
2020 for (i = 1; i < n; i++) {
2021 struct expr *a = expr_from_node(ovs_list_back(&expr->andor));
2022 struct expr *b = subs[i];
2023 if (compare_cmps_3way(a, b)) {
2024 ovs_list_push_back(&expr->andor, &b->node);
2030 return expr_fix(expr);
2033 /* Takes ownership of 'expr', which must be a cmp in the sense determined by
2034 * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
2035 * Returns an equivalent expression owned by the caller that is a single
2036 * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
2037 static struct expr *
2038 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
2040 switch (expr->type) {
2042 return crush_or(expr, symbol);
2045 return (symbol->width
2046 ? crush_and_numeric(expr, symbol)
2047 : crush_and_string(expr, symbol));
2052 case EXPR_T_BOOLEAN:
2060 static struct expr *
2061 expr_sort(struct expr *expr)
2063 size_t n = ovs_list_size(&expr->andor);
2064 struct expr_sort *subs = xmalloc(n * sizeof *subs);
2069 LIST_FOR_EACH (sub, node, &expr->andor) {
2071 subs[i].relop = expr_is_cmp(sub);
2072 subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2077 qsort(subs, n, sizeof *subs, compare_expr_sort);
2079 ovs_list_init(&expr->andor);
2080 for (int i = 0; i < n; ) {
2081 if (subs[i].relop) {
2083 for (j = i + 1; j < n; j++) {
2084 if (subs[i].relop != subs[j].relop) {
2089 struct expr *crushed;
2091 crushed = crush_cmps(subs[i].expr, subs[i].relop);
2093 struct expr *combined = subs[i].expr;
2094 for (int k = i + 1; k < j; k++) {
2095 combined = expr_combine(EXPR_T_AND, combined,
2098 ovs_assert(!ovs_list_is_short(&combined->andor));
2099 crushed = crush_cmps(combined, subs[i].relop);
2101 if (crushed->type == EXPR_T_BOOLEAN) {
2102 if (!crushed->boolean) {
2103 for (int k = j; k < n; k++) {
2104 expr_destroy(subs[k].expr);
2113 expr = expr_combine(EXPR_T_AND, expr, crushed);
2117 expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2125 static struct expr *expr_normalize_or(struct expr *expr);
2127 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2128 * a clause is a cmp or a disjunction of cmps on a single field. */
2129 static struct expr *
2130 expr_normalize_and(struct expr *expr)
2132 ovs_assert(expr->type == EXPR_T_AND);
2134 expr = expr_sort(expr);
2135 if (expr->type != EXPR_T_AND) {
2136 ovs_assert(expr->type == EXPR_T_BOOLEAN);
2141 LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2142 if (&b->node == &expr->andor
2143 || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2144 || a->cmp.symbol != b->cmp.symbol) {
2146 } else if (a->cmp.symbol->width
2147 ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2148 &b->cmp.value, &b->cmp.mask,
2149 &b->cmp.value, &b->cmp.mask)
2150 : !strcmp(a->cmp.string, b->cmp.string)) {
2151 ovs_list_remove(&a->node);
2155 return expr_create_boolean(false);
2158 if (ovs_list_is_short(&expr->andor)) {
2159 struct expr *sub = expr_from_node(ovs_list_front(&expr->andor));
2165 LIST_FOR_EACH (sub, node, &expr->andor) {
2166 if (sub->type == EXPR_T_CMP) {
2170 ovs_assert(sub->type == EXPR_T_OR);
2171 const struct expr_symbol *symbol = expr_is_cmp(sub);
2172 if (!symbol || symbol->must_crossproduct) {
2173 struct expr *or = expr_create_andor(EXPR_T_OR);
2176 LIST_FOR_EACH (k, node, &sub->andor) {
2177 struct expr *and = expr_create_andor(EXPR_T_AND);
2180 LIST_FOR_EACH (m, node, &expr->andor) {
2181 struct expr *term = m == sub ? k : m;
2182 if (term->type == EXPR_T_AND) {
2185 LIST_FOR_EACH (p, node, &term->andor) {
2186 struct expr *new = expr_clone(p);
2187 ovs_list_push_back(&and->andor, &new->node);
2190 struct expr *new = expr_clone(term);
2191 ovs_list_push_back(&and->andor, &new->node);
2194 ovs_list_push_back(&or->andor, &and->node);
2197 return expr_normalize_or(or);
2203 static struct expr *
2204 expr_normalize_or(struct expr *expr)
2206 struct expr *sub, *next;
2208 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2209 if (sub->type == EXPR_T_AND) {
2210 ovs_list_remove(&sub->node);
2212 struct expr *new = expr_normalize_and(sub);
2213 if (new->type == EXPR_T_BOOLEAN) {
2220 expr_insert_andor(expr, next, new);
2223 ovs_assert(sub->type == EXPR_T_CMP);
2226 if (ovs_list_is_empty(&expr->andor)) {
2228 return expr_create_boolean(false);
2230 if (ovs_list_is_short(&expr->andor)) {
2231 struct expr *sub = expr_from_node(ovs_list_pop_front(&expr->andor));
2239 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2240 * an expression in terms of only relationals, AND, and OR. Returns either a
2241 * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2242 * clause is a cmp or a disjunction of cmps on a single field. This form is
2243 * significant because it is a form that can be directly converted to OpenFlow
2244 * flows with the Open vSwitch "conjunctive match" extension.
2246 * 'expr' must already have been simplified, with expr_simplify(). */
2248 expr_normalize(struct expr *expr)
2250 switch (expr->type) {
2255 return expr_normalize_and(expr);
2258 return expr_normalize_or(expr);
2260 case EXPR_T_BOOLEAN:
2266 /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2267 * nonnull then it is copied into the new expr_match, otherwise the new
2268 * expr_match's 'match' member is initialized to a catch-all match for the
2269 * caller to refine in-place.
2271 * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2272 * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2273 * expr_match will not have any conjunctions.
2275 * The caller should use expr_match_add() to add the expr_match to a hash table
2276 * after it is finalized. */
2277 static struct expr_match *
2278 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2281 struct expr_match *match = xmalloc(sizeof *match);
2285 match_init_catchall(&match->match);
2288 match->conjunctions = xmalloc(sizeof *match->conjunctions);
2289 match->conjunctions[0].id = conj_id;
2290 match->conjunctions[0].clause = clause;
2291 match->conjunctions[0].n_clauses = n_clauses;
2293 match->allocated = 1;
2295 match->conjunctions = NULL;
2297 match->allocated = 0;
2302 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2305 * This might actually destroy 'match' because it gets merged together with
2306 * some existing conjunction.*/
2308 expr_match_add(struct hmap *matches, struct expr_match *match)
2310 uint32_t hash = match_hash(&match->match, 0);
2311 struct expr_match *m;
2313 HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2314 if (match_equal(&m->match, &match->match)) {
2315 if (!m->n || !match->n) {
2316 free(m->conjunctions);
2317 m->conjunctions = NULL;
2321 ovs_assert(match->n == 1);
2322 if (m->n >= m->allocated) {
2323 m->conjunctions = x2nrealloc(m->conjunctions,
2325 sizeof *m->conjunctions);
2327 m->conjunctions[m->n++] = match->conjunctions[0];
2329 free(match->conjunctions);
2335 hmap_insert(matches, &match->hmap_node, hash);
2339 constrain_match(const struct expr *expr,
2340 bool (*lookup_port)(const void *aux, const char *port_name,
2341 unsigned int *portp),
2342 const void *aux, struct match *m)
2344 ovs_assert(expr->type == EXPR_T_CMP);
2345 if (expr->cmp.symbol->width) {
2346 mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2347 &expr->cmp.mask, m);
2350 if (!lookup_port(aux, expr->cmp.string, &port)) {
2354 struct mf_subfield sf;
2355 sf.field = expr->cmp.symbol->field;
2357 sf.n_bits = expr->cmp.symbol->field->n_bits;
2359 union mf_subvalue x;
2360 memset(&x, 0, sizeof x);
2361 x.integer = htonll(port);
2363 mf_write_subfield(&sf, &x, m);
2369 add_disjunction(const struct expr *or,
2370 bool (*lookup_port)(const void *aux, const char *port_name,
2371 unsigned int *portp),
2373 struct match *m, uint8_t clause, uint8_t n_clauses,
2374 uint32_t conj_id, struct hmap *matches)
2379 ovs_assert(or->type == EXPR_T_OR);
2380 LIST_FOR_EACH (sub, node, &or->andor) {
2381 struct expr_match *match = expr_match_new(m, clause, n_clauses,
2383 if (constrain_match(sub, lookup_port, aux, &match->match)) {
2384 expr_match_add(matches, match);
2387 free(match->conjunctions);
2392 /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2393 * that shouldn't happen much. */
2398 add_conjunction(const struct expr *and,
2399 bool (*lookup_port)(const void *aux, const char *port_name,
2400 unsigned int *portp),
2401 const void *aux, uint32_t *n_conjsp, struct hmap *matches)
2407 match_init_catchall(&match);
2409 ovs_assert(and->type == EXPR_T_AND);
2410 LIST_FOR_EACH (sub, node, &and->andor) {
2411 switch (sub->type) {
2413 if (!constrain_match(sub, lookup_port, aux, &match)) {
2421 case EXPR_T_BOOLEAN:
2427 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2428 } else if (n_clauses == 1) {
2429 LIST_FOR_EACH (sub, node, &and->andor) {
2430 if (sub->type == EXPR_T_OR) {
2431 add_disjunction(sub, lookup_port, aux, &match, 0, 0, 0,
2438 LIST_FOR_EACH (sub, node, &and->andor) {
2439 if (sub->type == EXPR_T_OR) {
2440 if (!add_disjunction(sub, lookup_port, aux, &match, clause++,
2441 n_clauses, *n_conjsp, matches)) {
2442 /* This clause can't ever match, so we might as well skip
2443 * adding the other clauses--the overall disjunctive flow
2444 * can't ever match. Ideally we would also back out all of
2445 * the clauses we already added, but that seems like a lot
2446 * of trouble for a case that might never occur in
2453 /* Add the flow that matches on conj_id. */
2454 match_set_conj_id(&match, *n_conjsp);
2455 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2460 add_cmp_flow(const struct expr *cmp,
2461 bool (*lookup_port)(const void *aux, const char *port_name,
2462 unsigned int *portp),
2463 const void *aux, struct hmap *matches)
2465 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2466 if (constrain_match(cmp, lookup_port, aux, &m->match)) {
2467 expr_match_add(matches, m);
2473 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2474 * a collection of Open vSwitch flows in 'matches', which this function
2475 * initializes to an hmap of "struct expr_match" structures. Returns the
2476 * number of conjunctive match IDs consumed by 'matches', which uses
2477 * conjunctive match IDs beginning with 0; the caller must offset or remap them
2478 * into the desired range as necessary.
2480 * The matches inserted into 'matches' will be of three distinct kinds:
2482 * - Ordinary flows. The caller should add these OpenFlow flows with
2483 * its desired actions.
2485 * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2486 * structure. The caller should add these OpenFlow flows with the
2487 * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2488 * remapping the ids.
2490 * - conj_id flows, distinguished by matching on the "conj_id" field. The
2491 * caller should remap the conj_id and add the OpenFlow flow with its
2494 * 'lookup_port' must be a function to map from a port name to a port number.
2495 * When successful, 'lookup_port' stores the port number into '*portp' and
2496 * returns true; when there is no port by the given name, it returns false.
2497 * 'aux' is passed to 'lookup_port' as auxiliary data. Any comparisons against
2498 * string fields in 'expr' are translated into integers through this function.
2499 * A comparison against a string that is not in 'ports' acts like a Boolean
2500 * "false"; that is, it will always fail to match. For a simple expression,
2501 * this means that the overall expression always fails to match, but an
2502 * expression with a disjunction on the string field might still match on other
2505 * (This treatment of string fields might be too simplistic in general, but it
2506 * seems reasonable for now when string fields are used only for ports.) */
2508 expr_to_matches(const struct expr *expr,
2509 bool (*lookup_port)(const void *aux, const char *port_name,
2510 unsigned int *portp),
2511 const void *aux, struct hmap *matches)
2513 uint32_t n_conjs = 0;
2516 switch (expr->type) {
2518 add_cmp_flow(expr, lookup_port, aux, matches);
2522 add_conjunction(expr, lookup_port, aux, &n_conjs, matches);
2526 if (expr_is_cmp(expr)) {
2529 LIST_FOR_EACH (sub, node, &expr->andor) {
2530 add_cmp_flow(sub, lookup_port, aux, matches);
2535 LIST_FOR_EACH (sub, node, &expr->andor) {
2536 if (sub->type == EXPR_T_AND) {
2537 add_conjunction(sub, lookup_port, aux, &n_conjs, matches);
2539 add_cmp_flow(sub, lookup_port, aux, matches);
2545 case EXPR_T_BOOLEAN:
2546 if (expr->boolean) {
2547 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2548 expr_match_add(matches, m);
2557 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2558 * 'matches' hmap itself. */
2560 expr_matches_destroy(struct hmap *matches)
2562 struct expr_match *m;
2564 HMAP_FOR_EACH_POP (m, hmap_node, matches) {
2565 free(m->conjunctions);
2568 hmap_destroy(matches);
2571 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2574 expr_matches_print(const struct hmap *matches, FILE *stream)
2576 if (hmap_is_empty(matches)) {
2577 fputs("(no flows)\n", stream);
2581 const struct expr_match *m;
2582 HMAP_FOR_EACH (m, hmap_node, matches) {
2583 char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2588 for (int i = 0; i < m->n; i++) {
2589 const struct cls_conjunction *c = &m->conjunctions[i];
2590 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2591 i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2598 /* Returns true if 'expr' honors the invariants for expressions (see the large
2599 * comment above "struct expr" in expr.h), false otherwise. */
2601 expr_honors_invariants(const struct expr *expr)
2603 const struct expr *sub;
2605 switch (expr->type) {
2607 if (expr->cmp.symbol->width) {
2608 for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2609 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2618 if (ovs_list_is_short(&expr->andor)) {
2621 LIST_FOR_EACH (sub, node, &expr->andor) {
2622 if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2628 case EXPR_T_BOOLEAN:
2637 expr_is_normalized_and(const struct expr *expr)
2639 /* XXX should also check that no symbol is repeated. */
2640 const struct expr *sub;
2642 LIST_FOR_EACH (sub, node, &expr->andor) {
2643 if (!expr_is_cmp(sub)) {
2650 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2653 expr_is_normalized(const struct expr *expr)
2655 switch (expr->type) {
2660 return expr_is_normalized_and(expr);
2663 if (!expr_is_cmp(expr)) {
2664 const struct expr *sub;
2666 LIST_FOR_EACH (sub, node, &expr->andor) {
2667 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2674 case EXPR_T_BOOLEAN:
2682 /* Action parsing helper. */
2684 /* Expands 'f' repeatedly as long as it has an expansion, that is, as long as
2685 * it is a subfield or a predicate. Adds any prerequisites for 'f' to
2688 * If 'rw', verifies that 'f' is a read/write field.
2690 * Returns true if successful, false if an error was encountered (in which case
2691 * 'ctx->error' reports the particular error). */
2693 expand_symbol(struct expr_context *ctx, bool rw,
2694 struct expr_field *f, struct expr **prereqsp)
2696 const struct expr_symbol *orig_symbol = f->symbol;
2698 if (f->symbol->expansion && f->symbol->level != EXPR_L_ORDINAL) {
2699 expr_error(ctx, "Predicate symbol %s used where lvalue required.",
2705 /* Accumulate prerequisites. */
2706 if (f->symbol->prereqs) {
2707 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2710 e = parse_and_annotate(f->symbol->prereqs, ctx->symtab, &nesting,
2713 expr_error(ctx, "%s", error);
2717 *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
2720 /* If there's no expansion, we're done. */
2721 if (!f->symbol->expansion) {
2726 struct expr_field expansion;
2728 if (!parse_field_from_string(f->symbol->expansion, ctx->symtab,
2729 &expansion, &error)) {
2730 expr_error(ctx, "%s", error);
2734 f->symbol = expansion.symbol;
2735 f->ofs += expansion.ofs;
2738 if (rw && !f->symbol->field->writable) {
2739 expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2747 mf_subfield_from_expr_field(const struct expr_field *f, struct mf_subfield *sf)
2749 sf->field = f->symbol->field;
2751 sf->n_bits = f->n_bits ? f->n_bits : f->symbol->field->n_bits;
2755 init_stack_action(const struct expr_field *f, struct ofpact_stack *stack)
2757 mf_subfield_from_expr_field(f, &stack->subfield);
2760 static char * OVS_WARN_UNUSED_RESULT
2761 parse_assignment(struct lexer *lexer, struct expr_field *dst,
2762 const struct shash *symtab, bool exchange,
2763 bool (*lookup_port)(const void *aux, const char *port_name,
2764 unsigned int *portp),
2765 const void *aux, struct ofpbuf *ofpacts,
2766 struct expr **prereqsp)
2768 struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2769 struct expr *prereqs = NULL;
2771 /* Parse destination and do basic checking. */
2772 const struct expr_symbol *orig_dst = dst->symbol;
2773 if (!expand_symbol(&ctx, true, dst, &prereqs)) {
2777 if (exchange || ctx.lexer->token.type == LEX_T_ID) {
2778 struct expr_field src;
2779 if (!parse_field(&ctx, &src)) {
2782 const struct expr_symbol *orig_src = src.symbol;
2783 if (!expand_symbol(&ctx, exchange, &src, &prereqs)) {
2787 if ((dst->symbol->width != 0) != (src.symbol->width != 0)) {
2790 "Can't exchange %s field (%s) with %s field (%s).",
2791 orig_dst->width ? "integer" : "string",
2793 orig_src->width ? "integer" : "string",
2797 "Can't assign %s field (%s) to %s field (%s).",
2798 orig_src->width ? "integer" : "string",
2800 orig_dst->width ? "integer" : "string",
2806 if (dst->n_bits != src.n_bits) {
2809 "Can't exchange %d-bit field with %d-bit field.",
2810 dst->n_bits, src.n_bits);
2813 "Can't assign %d-bit value to %d-bit destination.",
2814 src.n_bits, dst->n_bits);
2817 } else if (!dst->n_bits &&
2818 dst->symbol->field->n_bits != src.symbol->field->n_bits) {
2819 expr_error(&ctx, "String fields %s and %s are incompatible for "
2820 "%s.", orig_dst->name, orig_src->name,
2821 exchange ? "exchange" : "assignment");
2826 init_stack_action(&src, ofpact_put_STACK_PUSH(ofpacts));
2827 init_stack_action(dst, ofpact_put_STACK_PUSH(ofpacts));
2828 init_stack_action(&src, ofpact_put_STACK_POP(ofpacts));
2829 init_stack_action(dst, ofpact_put_STACK_POP(ofpacts));
2831 struct ofpact_reg_move *move = ofpact_put_REG_MOVE(ofpacts);
2832 mf_subfield_from_expr_field(&src, &move->src);
2833 mf_subfield_from_expr_field(dst, &move->dst);
2836 struct expr_constant_set cs;
2837 if (!parse_constant_set(&ctx, &cs)) {
2841 if (!type_check(&ctx, dst, &cs)) {
2842 goto exit_destroy_cs;
2844 if (cs.in_curlies) {
2845 expr_error(&ctx, "Assignments require a single value.");
2846 goto exit_destroy_cs;
2849 union expr_constant *c = cs.values;
2850 struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2851 sf->field = dst->symbol->field;
2852 if (dst->symbol->width) {
2853 mf_subvalue_shift(&c->value, dst->ofs);
2855 memset(&c->mask, 0, sizeof c->mask);
2856 bitwise_one(&c->mask, sizeof c->mask, dst->ofs, dst->n_bits);
2858 mf_subvalue_shift(&c->mask, dst->ofs);
2862 &c->value.u8[sizeof c->value - sf->field->n_bytes],
2863 sf->field->n_bytes);
2865 &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2866 sf->field->n_bytes);
2869 if (!lookup_port(aux, c->string, &port)) {
2872 bitwise_put(port, &sf->value,
2873 sf->field->n_bytes, 0, sf->field->n_bits);
2874 bitwise_one(&sf->mask, sf->field->n_bytes, 0, sf->field->n_bits);
2876 /* If the logical input port is being zeroed, clear the OpenFlow
2877 * ingress port also, to allow a packet to be sent back to its
2879 if (!port && sf->field->id == MFF_LOG_INPORT) {
2880 sf = ofpact_put_SET_FIELD(ofpacts);
2881 sf->field = mf_from_id(MFF_IN_PORT);
2882 bitwise_one(&sf->mask,
2883 sf->field->n_bytes, 0, sf->field->n_bits);
2888 expr_constant_set_destroy(&cs);
2893 expr_destroy(prereqs);
2896 *prereqsp = prereqs;
2900 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2901 * "field = value" or "field = field2" into 'ofpacts'. The caller must have
2902 * already parsed and skipped the left-hand side "field =" and pass in the
2903 * field as 'dst'. Other parameters and return value match those for
2904 * actions_parse(). */
2905 char * OVS_WARN_UNUSED_RESULT
2906 expr_parse_assignment(struct lexer *lexer, struct expr_field *dst,
2907 const struct shash *symtab,
2908 bool (*lookup_port)(const void *aux,
2909 const char *port_name,
2910 unsigned int *portp),
2912 struct ofpbuf *ofpacts, struct expr **prereqsp)
2914 return parse_assignment(lexer, dst, symtab, false, lookup_port, aux,
2918 /* A helper for actions_parse(), to parse an OVN exchange action in the form
2919 * "field1 <-> field2" into 'ofpacts'. The caller must have already parsed and
2920 * skipped the left-hand side "field1 <->" and pass in 'field1'. Other
2921 * parameters and return value match those for actions_parse(). */
2922 char * OVS_WARN_UNUSED_RESULT
2923 expr_parse_exchange(struct lexer *lexer, struct expr_field *field,
2924 const struct shash *symtab,
2925 bool (*lookup_port)(const void *aux,
2926 const char *port_name,
2927 unsigned int *portp),
2929 struct ofpbuf *ofpacts, struct expr **prereqsp)
2931 return parse_assignment(lexer, field, symtab, true, lookup_port, aux,
2935 /* Parses a field or subfield from 'lexer' into 'field', obtaining field names
2936 * from 'symtab'. Returns NULL if successful, otherwise an error message owned
2938 char * OVS_WARN_UNUSED_RESULT
2939 expr_parse_field(struct lexer *lexer, const struct shash *symtab,
2940 struct expr_field *field)
2942 struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2943 if (!parse_field(&ctx, field)) {
2944 memset(field, 0, sizeof *field);
2949 /* Takes 'field', which was presumably parsed by expr_parse_field(), and
2950 * converts it into mf_subfield 'sf' and a set of prerequisites in '*prereqsp'.
2952 * 'n_bits' specifies the number of bits that the field must have, and 0
2953 * indicates a string field; reports an error if 'field' has a different type
2954 * or width. If 'rw' is true, it is an error if 'field' is read-only. Uses
2955 * 'symtab 'for expanding references and 'lexer' for error reporting.
2957 * Returns NULL if successful, otherwise an error message owned by the
2959 char * OVS_WARN_UNUSED_RESULT
2960 expr_expand_field(struct lexer *lexer, const struct shash *symtab,
2961 const struct expr_field *orig_field, int n_bits, bool rw,
2962 struct mf_subfield *sf, struct expr **prereqsp)
2964 struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
2965 struct expr *prereqs = NULL;
2967 struct expr_field field = *orig_field;
2968 if (!expand_symbol(&ctx, rw, &field, &prereqs)) {
2971 ovs_assert(field.n_bits == orig_field->n_bits);
2973 if (n_bits != field.n_bits) {
2974 if (n_bits && field.n_bits) {
2975 expr_error(&ctx, "Cannot use %d-bit field %s[%d..%d] "
2976 "where %d-bit field is required.",
2977 orig_field->n_bits, orig_field->symbol->name,
2979 orig_field->ofs + orig_field->n_bits - 1, n_bits);
2980 } else if (n_bits) {
2981 expr_error(&ctx, "Cannot use string field %s where numeric "
2982 "field is required.",
2983 orig_field->symbol->name);
2985 expr_error(&ctx, "Cannot use numeric field %s where string "
2986 "field is required.",
2987 orig_field->symbol->name);
2993 mf_subfield_from_expr_field(&field, sf);
2994 *prereqsp = prereqs;
2996 memset(sf, 0, sizeof *sf);
2997 expr_destroy(prereqs);
3003 char * OVS_WARN_UNUSED_RESULT
3004 expr_parse_constant_set(struct lexer *lexer, const struct shash *symtab,
3005 struct expr_constant_set *cs)
3007 struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
3008 parse_constant_set(&ctx, cs);