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"
23 #include "ofp-actions.h"
26 #include "openvswitch/vlog.h"
28 VLOG_DEFINE_THIS_MODULE(expr);
30 /* Returns the name of measurement level 'level'. */
32 expr_level_to_string(enum expr_level level)
35 case EXPR_L_NOMINAL: return "nominal";
36 case EXPR_L_BOOLEAN: return "Boolean";
37 case EXPR_L_ORDINAL: return "ordinal";
38 default: OVS_NOT_REACHED();
42 /* Relational operators. */
44 /* Returns a string form of relational operator 'relop'. */
46 expr_relop_to_string(enum expr_relop relop)
49 case EXPR_R_EQ: return "==";
50 case EXPR_R_NE: return "!=";
51 case EXPR_R_LT: return "<";
52 case EXPR_R_LE: return "<=";
53 case EXPR_R_GT: return ">";
54 case EXPR_R_GE: return ">=";
55 default: OVS_NOT_REACHED();
60 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
65 case LEX_T_EQ: r = EXPR_R_EQ; break;
66 case LEX_T_NE: r = EXPR_R_NE; break;
67 case LEX_T_LT: r = EXPR_R_LT; break;
68 case LEX_T_LE: r = EXPR_R_LE; break;
69 case LEX_T_GT: r = EXPR_R_GT; break;
70 case LEX_T_GE: r = EXPR_R_GE; break;
71 default: return false;
80 /* Returns the relational operator that 'relop' becomes if you turn the
81 * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
82 * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
83 * b" is equivalent to "b >= a". */
84 static enum expr_relop
85 expr_relop_turn(enum expr_relop relop)
88 case EXPR_R_EQ: return EXPR_R_EQ;
89 case EXPR_R_NE: return EXPR_R_NE;
90 case EXPR_R_LT: return EXPR_R_GT;
91 case EXPR_R_LE: return EXPR_R_GE;
92 case EXPR_R_GT: return EXPR_R_LT;
93 case EXPR_R_GE: return EXPR_R_LE;
94 default: OVS_NOT_REACHED();
98 /* Returns the relational operator that is the opposite of 'relop'. */
99 static enum expr_relop
100 expr_relop_invert(enum expr_relop relop)
103 case EXPR_R_EQ: return EXPR_R_NE;
104 case EXPR_R_NE: return EXPR_R_EQ;
105 case EXPR_R_LT: return EXPR_R_GE;
106 case EXPR_R_LE: return EXPR_R_GT;
107 case EXPR_R_GT: return EXPR_R_LE;
108 case EXPR_R_GE: return EXPR_R_LT;
109 default: OVS_NOT_REACHED();
113 /* Constructing and manipulating expressions. */
115 /* Creates and returns a logical AND or OR expression (according to 'type',
116 * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
117 * sub-expressions. (To satisfy the invariants for expressions, the caller
118 * must add at least two sub-expressions whose types are different from
121 expr_create_andor(enum expr_type type)
123 struct expr *e = xmalloc(sizeof *e);
125 list_init(&e->andor);
129 /* Returns a logical AND or OR expression (according to 'type', which must be
130 * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
133 * - If 'a' or 'b' is NULL, just returns the other one (which means that if
134 * that other one is not of the given 'type', then the returned
135 * expression is not either).
137 * - If 'a' or 'b', or both, have type 'type', then they are combined into
138 * a single node that satisfies the invariants for expressions. */
140 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
146 } else if (a->type == type) {
147 if (b->type == type) {
148 list_splice(&a->andor, b->andor.next, &b->andor);
151 list_push_back(&a->andor, &b->node);
154 } else if (b->type == type) {
155 list_push_front(&b->andor, &a->node);
158 struct expr *e = expr_create_andor(type);
159 list_push_back(&e->andor, &a->node);
160 list_push_back(&e->andor, &b->node);
166 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
168 if (new->type == andor->type) {
169 if (andor->type == EXPR_T_AND) {
170 /* Conjunction junction, what's your function? */
172 list_splice(&before->node, new->andor.next, &new->andor);
175 list_insert(&before->node, &new->node);
179 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
181 expr_create_boolean(bool b)
183 struct expr *e = xmalloc(sizeof *e);
184 e->type = EXPR_T_BOOLEAN;
190 expr_not(struct expr *expr)
194 switch (expr->type) {
196 expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
201 LIST_FOR_EACH (sub, node, &expr->andor) {
204 expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
208 expr->boolean = !expr->boolean;
216 expr_fix_andor(struct expr *expr, bool short_circuit)
218 struct expr *sub, *next;
220 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
221 if (sub->type == EXPR_T_BOOLEAN) {
222 if (sub->boolean == short_circuit) {
224 return expr_create_boolean(short_circuit);
226 list_remove(&sub->node);
232 if (list_is_short(&expr->andor)) {
233 if (list_is_empty(&expr->andor)) {
235 return expr_create_boolean(!short_circuit);
237 sub = expr_from_node(list_front(&expr->andor));
247 expr_fix(struct expr *expr)
249 switch (expr->type) {
254 return expr_fix_andor(expr, false);
257 return expr_fix_andor(expr, true);
270 find_bitwise_range(const union mf_subvalue *sv, int width,
271 int *startp, int *n_bitsp)
273 unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
275 unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
277 || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
279 *n_bitsp = end - start;
283 *startp = *n_bitsp = 0;
287 expr_format_cmp(const struct expr *e, struct ds *s)
289 /* The common case is numerical comparisons.
290 * Handle string comparisons as a special case. */
291 if (!e->cmp.symbol->width) {
292 ds_put_format(s, "%s %s ", e->cmp.symbol->name,
293 expr_relop_to_string(e->cmp.relop));
294 json_string_escape(e->cmp.string, s);
299 find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
300 if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
303 positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
304 positive ^= e->cmp.relop == EXPR_R_NE;
308 ds_put_cstr(s, e->cmp.symbol->name);
309 if (e->cmp.symbol->width > 1) {
310 ds_put_format(s, "[%d]", ofs);
315 ds_put_cstr(s, e->cmp.symbol->name);
316 if (n > 0 && n < e->cmp.symbol->width) {
318 ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
320 ds_put_format(s, "[%d]", ofs);
324 ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
327 union mf_subvalue value;
329 memset(&value, 0, sizeof value);
330 bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
331 &value, sizeof value, 0,
333 mf_format_subvalue(&value, s);
335 mf_format_subvalue(&e->cmp.value, s);
337 mf_format_subvalue(&e->cmp.mask, s);
342 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
347 LIST_FOR_EACH (sub, node, &e->andor) {
349 ds_put_format(s, " %s ", op);
352 if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
362 /* Appends a string form of 'e' to 's'. The string form is acceptable for
363 * parsing back into an equivalent expression. */
365 expr_format(const struct expr *e, struct ds *s)
369 expr_format_cmp(e, s);
373 expr_format_andor(e, "&&", s);
377 expr_format_andor(e, "||", s);
381 ds_put_char(s, e->boolean ? '1' : '0');
386 /* Prints a string form of 'e' on stdout, followed by a new-line. */
388 expr_print(const struct expr *e)
393 expr_format(e, &output);
394 puts(ds_cstr(&output));
400 /* Type of a "union expr_constant" or "struct expr_constant_set". */
401 enum expr_constant_type {
406 /* A string or integer constant (one must know which from context). */
407 union expr_constant {
410 * The width of a constant isn't always clear, e.g. if you write "1",
411 * there's no way to tell whether you mean for that to be a 1-bit constant
412 * or a 128-bit constant or somewhere in between. */
414 union mf_subvalue value;
415 union mf_subvalue mask; /* Only initialized if 'masked'. */
418 enum lex_format format; /* From the constant's lex_token. */
421 /* Null-terminated string constant. */
425 /* A collection of "union expr_constant"s of the same type. */
426 struct expr_constant_set {
427 union expr_constant *values; /* Constants. */
428 size_t n_values; /* Number of constants. */
429 enum expr_constant_type type; /* Type of the constants. */
430 bool in_curlies; /* Whether the constants were in {}. */
433 /* A reference to a symbol or a subfield of a symbol.
435 * For string fields, ofs and n_bits are 0. */
437 const struct expr_symbol *symbol; /* The symbol. */
438 int ofs; /* Starting bit offset. */
439 int n_bits; /* Number of bits. */
442 /* Context maintained during expr_parse(). */
443 struct expr_context {
444 struct lexer *lexer; /* Lexer for pulling more tokens. */
445 const struct shash *symtab; /* Symbol table. */
446 char *error; /* Error, if any, otherwise NULL. */
447 bool not; /* True inside odd number of NOT operators. */
450 struct expr *expr_parse__(struct expr_context *);
451 static void expr_not(struct expr *);
452 static void expr_constant_set_destroy(struct expr_constant_set *);
453 static bool parse_field(struct expr_context *, struct expr_field *);
456 expr_error_handle_common(struct expr_context *ctx)
459 /* Already have an error, suppress this one since the cascade seems
460 * unlikely to be useful. */
462 } else if (ctx->lexer->token.type == LEX_T_ERROR) {
463 /* The lexer signaled an error. Nothing at the expression level
464 * accepts an error token, so we'll inevitably end up here with some
465 * meaningless parse error. Report the lexical error instead. */
466 ctx->error = xstrdup(ctx->lexer->token.s);
473 static void OVS_PRINTF_FORMAT(2, 3)
474 expr_error(struct expr_context *ctx, const char *message, ...)
476 if (expr_error_handle_common(ctx)) {
481 va_start(args, message);
482 ctx->error = xvasprintf(message, args);
486 static void OVS_PRINTF_FORMAT(2, 3)
487 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
489 if (expr_error_handle_common(ctx)) {
496 ds_put_cstr(&s, "Syntax error ");
497 if (ctx->lexer->token.type == LEX_T_END) {
498 ds_put_cstr(&s, "at end of input ");
499 } else if (ctx->lexer->start) {
500 ds_put_format(&s, "at `%.*s' ",
501 (int) (ctx->lexer->input - ctx->lexer->start),
506 va_start(args, message);
507 ds_put_format_valist(&s, message, args);
510 ctx->error = ds_steal_cstr(&s);
514 make_cmp__(const struct expr_field *f, enum expr_relop r,
515 const union expr_constant *c)
517 struct expr *e = xzalloc(sizeof *e);
518 e->type = EXPR_T_CMP;
519 e->cmp.symbol = f->symbol;
521 if (f->symbol->width) {
522 bitwise_copy(&c->value, sizeof c->value, 0,
523 &e->cmp.value, sizeof e->cmp.value, f->ofs,
526 bitwise_copy(&c->mask, sizeof c->mask, 0,
527 &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
530 bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
534 e->cmp.string = xstrdup(c->string);
539 /* Returns the minimum reasonable width for integer constant 'c'. */
541 expr_constant_width(const union expr_constant *c)
544 return mf_subvalue_width(&c->mask);
549 case LEX_F_HEXADECIMAL:
550 return mf_subvalue_width(&c->value);
567 type_check(struct expr_context *ctx, const struct expr_field *f,
568 struct expr_constant_set *cs)
570 if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
571 expr_error(ctx, "%s field %s is not compatible with %s constant.",
572 f->symbol->width ? "Integer" : "String",
574 cs->type == EXPR_C_INTEGER ? "integer" : "string");
578 if (f->symbol->width) {
579 for (size_t i = 0; i < cs->n_values; i++) {
580 int w = expr_constant_width(&cs->values[i]);
581 if (w > f->symbol->width) {
582 expr_error(ctx, "%d-bit constant is not compatible with "
584 w, f->symbol->width, f->symbol->name);
594 make_cmp(struct expr_context *ctx,
595 const struct expr_field *f, enum expr_relop r,
596 struct expr_constant_set *cs)
598 struct expr *e = NULL;
600 if (!type_check(ctx, f, cs)) {
604 if (r != EXPR_R_EQ && r != EXPR_R_NE) {
605 if (cs->in_curlies) {
606 expr_error(ctx, "Only == and != operators may be used "
610 if (f->symbol->level == EXPR_L_NOMINAL ||
611 f->symbol->level == EXPR_L_BOOLEAN) {
612 expr_error(ctx, "Only == and != operators may be used "
614 expr_level_to_string(f->symbol->level),
618 if (cs->values[0].masked) {
619 expr_error(ctx, "Only == and != operators may be used with "
620 "masked constants. Consider using subfields instead "
621 "(e.g. eth.src[0..15] > 0x1111 in place of "
622 "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
627 if (f->symbol->level == EXPR_L_NOMINAL) {
628 if (f->symbol->expansion) {
629 for (size_t i = 0; i < cs->n_values; i++) {
630 const union mf_subvalue *value = &cs->values[i].value;
631 bool positive = (value->integer & htonll(1)) != 0;
632 positive ^= r == EXPR_R_NE;
633 positive ^= ctx->not;
635 const char *name = f->symbol->name;
636 expr_error(ctx, "Nominal predicate %s may only be tested "
637 "positively, e.g. `%s' or `%s == 1' but not "
638 "`!%s' or `%s == 0'.",
639 name, name, name, name, name);
643 } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
644 expr_error(ctx, "Nominal field %s may only be tested for "
645 "equality (taking enclosing `!' operators into "
646 "account).", f->symbol->name);
651 e = make_cmp__(f, r, &cs->values[0]);
652 for (size_t i = 1; i < cs->n_values; i++) {
653 e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
654 e, make_cmp__(f, r, &cs->values[i]));
657 expr_constant_set_destroy(cs);
662 expr_get_int(struct expr_context *ctx, int *value)
664 if (ctx->lexer->token.type == LEX_T_INTEGER
665 && ctx->lexer->token.format == LEX_F_DECIMAL
666 && ntohll(ctx->lexer->token.value.integer) <= INT_MAX) {
667 *value = ntohll(ctx->lexer->token.value.integer);
668 lexer_get(ctx->lexer);
671 expr_syntax_error(ctx, "expecting small integer.");
677 parse_field(struct expr_context *ctx, struct expr_field *f)
679 const struct expr_symbol *symbol;
681 if (ctx->lexer->token.type != LEX_T_ID) {
682 expr_syntax_error(ctx, "expecting field name.");
686 symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
688 expr_syntax_error(ctx, "expecting field name.");
691 lexer_get(ctx->lexer);
694 if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
697 if (!symbol->width) {
698 expr_error(ctx, "Cannot select subfield of string field %s.",
703 if (!expr_get_int(ctx, &low)) {
706 if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
707 if (!expr_get_int(ctx, &high)) {
714 if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
715 expr_syntax_error(ctx, "expecting `]'.");
720 expr_error(ctx, "Invalid bit range %d to %d.", low, high);
722 } else if (high >= symbol->width) {
723 expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
724 low, high, symbol->width, symbol->name);
726 } else if (symbol->level == EXPR_L_NOMINAL
727 && (low != 0 || high != symbol->width - 1)) {
728 expr_error(ctx, "Cannot select subfield of nominal field %s.",
734 f->n_bits = high - low + 1;
737 f->n_bits = symbol->width;
744 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
746 if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
747 lexer_get(ctx->lexer);
750 expr_syntax_error(ctx, "expecting relational operator.");
756 assign_constant_set_type(struct expr_context *ctx,
757 struct expr_constant_set *cs,
758 enum expr_constant_type type)
760 if (!cs->n_values || cs->type == type) {
764 expr_syntax_error(ctx, "expecting %s.",
765 cs->type == EXPR_C_INTEGER ? "integer" : "string");
771 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
772 size_t *allocated_values)
774 if (cs->n_values >= *allocated_values) {
775 cs->values = x2nrealloc(cs->values, allocated_values,
779 if (ctx->lexer->token.type == LEX_T_STRING) {
780 if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
783 cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
784 lexer_get(ctx->lexer);
786 } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
787 ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
788 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
792 union expr_constant *c = &cs->values[cs->n_values++];
793 c->value = ctx->lexer->token.value;
794 c->format = ctx->lexer->token.format;
795 c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
797 c->mask = ctx->lexer->token.mask;
799 lexer_get(ctx->lexer);
802 expr_syntax_error(ctx, "expecting constant.");
807 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
808 * which the caller need not have initialized. Returns true on success, in
809 * which case the caller owns 'cs', false on failure, in which case 'cs' is
812 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
814 size_t allocated_values = 0;
817 memset(cs, 0, sizeof *cs);
818 if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
820 cs->in_curlies = true;
822 if (!parse_constant(ctx, cs, &allocated_values)) {
826 lexer_match(ctx->lexer, LEX_T_COMMA);
827 } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
829 ok = parse_constant(ctx, cs, &allocated_values);
832 expr_constant_set_destroy(cs);
838 expr_constant_set_destroy(struct expr_constant_set *cs)
841 if (cs->type == EXPR_C_STRING) {
842 for (size_t i = 0; i < cs->n_values; i++) {
843 free(cs->values[i].string);
851 expr_parse_primary(struct expr_context *ctx, bool *atomic)
854 if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
855 struct expr *e = expr_parse__(ctx);
856 if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
858 expr_syntax_error(ctx, "expecting `)'.");
865 if (ctx->lexer->token.type == LEX_T_ID) {
868 struct expr_constant_set c;
870 if (!parse_field(ctx, &f)) {
874 if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
875 if (f.n_bits > 1 && !ctx->not) {
876 expr_error(ctx, "Explicit `!= 0' is required for inequality "
877 "test of multibit field against 0.");
883 union expr_constant *cst = xzalloc(sizeof *cst);
884 cst->format = LEX_F_HEXADECIMAL;
887 c.type = EXPR_C_INTEGER;
890 c.in_curlies = false;
891 return make_cmp(ctx, &f, EXPR_R_NE, &c);
892 } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
893 return make_cmp(ctx, &f, r, &c);
898 struct expr_constant_set c1;
899 if (!parse_constant_set(ctx, &c1)) {
903 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
905 && c1.type == EXPR_C_INTEGER
906 && c1.values[0].format == LEX_F_DECIMAL
907 && !c1.values[0].masked
909 uint64_t x = ntohll(c1.values[0].value.integer);
912 expr_constant_set_destroy(&c1);
913 return expr_create_boolean(x);
919 if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
920 expr_constant_set_destroy(&c1);
924 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
925 return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
929 struct expr_constant_set c2;
930 if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
931 expr_constant_set_destroy(&c1);
934 /* Reject "1 == field == 2", "1 < field > 2", and so on. */
935 if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
936 (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
937 ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
938 (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
939 expr_error(ctx, "Range expressions must have the form "
940 "`x < field < y' or `x > field > y', with each "
941 "`<' optionally replaced by `<=' or `>' by `>=').");
942 expr_constant_set_destroy(&c1);
943 expr_constant_set_destroy(&c2);
947 struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
948 struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
954 return expr_combine(EXPR_T_AND, e1, e2);
960 expr_parse_not(struct expr_context *ctx)
964 if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
965 ctx->not = !ctx->not;
966 struct expr *expr = expr_parse_primary(ctx, &atomic);
967 ctx->not = !ctx->not;
971 expr_error(ctx, "Missing parentheses around operand of !.");
979 return expr_parse_primary(ctx, &atomic);
984 expr_parse__(struct expr_context *ctx)
986 struct expr *e = expr_parse_not(ctx);
991 enum lex_type lex_type = ctx->lexer->token.type;
992 if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
993 enum expr_type expr_type
994 = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
996 lexer_get(ctx->lexer);
998 struct expr *e2 = expr_parse_not(ctx);
1003 e = expr_combine(expr_type, e, e2);
1004 } while (lexer_match(ctx->lexer, lex_type));
1005 if (ctx->lexer->token.type == LEX_T_LOG_AND
1006 || ctx->lexer->token.type == LEX_T_LOG_OR) {
1009 "&& and || must be parenthesized when used together.");
1016 /* Parses an expression using the symbols in 'symtab' from 'lexer'. If
1017 * successful, returns the new expression and sets '*errorp' to NULL. On
1018 * failure, returns NULL and sets '*errorp' to an explanatory error message.
1019 * The caller must eventually free the returned expression (with
1020 * expr_destroy()) or error (with free()). */
1022 expr_parse(struct lexer *lexer, const struct shash *symtab, char **errorp)
1024 struct expr_context ctx;
1027 ctx.symtab = symtab;
1031 struct expr *e = expr_parse__(&ctx);
1032 *errorp = ctx.error;
1033 ovs_assert((ctx.error != NULL) != (e != NULL));
1037 /* Like expr_parse(), but the expression is taken from 's'. */
1039 expr_parse_string(const char *s, const struct shash *symtab, char **errorp)
1044 lexer_init(&lexer, s);
1046 expr = expr_parse(&lexer, symtab, errorp);
1047 if (!*errorp && lexer.token.type != LEX_T_END) {
1048 *errorp = xstrdup("Extra tokens at end of input.");
1052 lexer_destroy(&lexer);
1057 static struct expr_symbol *
1058 add_symbol(struct shash *symtab, const char *name, int width,
1059 const char *prereqs, enum expr_level level,
1060 bool must_crossproduct)
1062 struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1063 symbol->name = xstrdup(name);
1064 symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1065 symbol->width = width;
1066 symbol->level = level;
1067 symbol->must_crossproduct = must_crossproduct;
1068 shash_add_assert(symtab, symbol->name, symbol);
1072 /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1073 * 'name' is referenced, expression annotation (see expr_annotate()) will
1074 * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1075 * conversion to flows will never attempt to use the field as a conjunctive
1076 * match dimension (see "Crossproducting" in the large comment on struct
1077 * expr_symbol in expr.h for an example).
1079 * A given field 'id' must only be used for a single symbol in a symbol table.
1080 * Use subfields to duplicate or subset a field (you can even make a subfield
1081 * include all the bits of the "parent" field if you like). */
1082 struct expr_symbol *
1083 expr_symtab_add_field(struct shash *symtab, const char *name,
1084 enum mf_field_id id, const char *prereqs,
1085 bool must_crossproduct)
1087 const struct mf_field *field = mf_from_id(id);
1088 struct expr_symbol *symbol;
1090 symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1091 (field->maskable == MFM_FULLY
1095 symbol->field = field;
1100 parse_field_from_string(const char *s, const struct shash *symtab,
1101 struct expr_field *field, char **errorp)
1104 lexer_init(&lexer, s);
1107 struct expr_context ctx;
1109 ctx.symtab = symtab;
1113 bool ok = parse_field(&ctx, field);
1115 *errorp = ctx.error;
1116 } else if (lexer.token.type != LEX_T_END) {
1117 *errorp = xstrdup("Extra tokens at end of input.");
1121 lexer_destroy(&lexer);
1126 /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1127 * 'name' is referenced, expression annotation (see expr_annotate()) will
1128 * ensure that 'prereqs' are also true.
1130 * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1131 * for the low 12 bits of a larger field named "vlan.tci". */
1132 struct expr_symbol *
1133 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1134 const char *prereqs, const char *subfield)
1136 struct expr_symbol *symbol;
1137 struct expr_field f;
1140 if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1141 VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1146 enum expr_level level = f.symbol->level;
1147 if (level != EXPR_L_ORDINAL) {
1148 VLOG_WARN("can't define %s as subfield of %s field %s",
1149 name, expr_level_to_string(level), f.symbol->name);
1152 symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1153 symbol->expansion = xstrdup(subfield);
1157 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1159 struct expr_symbol *
1160 expr_symtab_add_string(struct shash *symtab, const char *name,
1161 enum mf_field_id id, const char *prereqs)
1163 const struct mf_field *field = mf_from_id(id);
1164 struct expr_symbol *symbol;
1166 symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1167 symbol->field = field;
1171 static enum expr_level
1172 expr_get_level(const struct expr *expr)
1174 const struct expr *sub;
1175 enum expr_level level = EXPR_L_ORDINAL;
1177 switch (expr->type) {
1179 return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1185 LIST_FOR_EACH (sub, node, &expr->andor) {
1186 enum expr_level sub_level = expr_get_level(sub);
1187 level = MIN(level, sub_level);
1191 case EXPR_T_BOOLEAN:
1192 return EXPR_L_BOOLEAN;
1199 static enum expr_level
1200 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1202 struct expr *expr = expr_parse_string(s, symtab, errorp);
1203 enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1208 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1209 * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 1" might be an
1210 * appropriate predicate named "tcp4". */
1211 struct expr_symbol *
1212 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1213 const char *expansion)
1215 struct expr_symbol *symbol;
1216 enum expr_level level;
1219 level = expr_parse_level(expansion, symtab, &error);
1221 VLOG_WARN("%s: error parsing %s expansion (%s)",
1222 expansion, name, error);
1227 symbol = add_symbol(symtab, name, 1, NULL, level, false);
1228 symbol->expansion = xstrdup(expansion);
1232 /* Destroys 'symtab' and all of its symbols. */
1234 expr_symtab_destroy(struct shash *symtab)
1236 struct shash_node *node, *next;
1238 SHASH_FOR_EACH_SAFE (node, next, symtab) {
1239 struct expr_symbol *symbol = node->data;
1241 shash_delete(symtab, node);
1243 free(symbol->prereqs);
1244 free(symbol->expansion);
1251 static struct expr *
1252 expr_clone_cmp(struct expr *expr)
1254 struct expr *new = xmemdup(expr, sizeof *expr);
1255 if (!new->cmp.symbol->width) {
1256 new->cmp.string = xstrdup(new->cmp.string);
1261 static struct expr *
1262 expr_clone_andor(struct expr *expr)
1264 struct expr *new = expr_create_andor(expr->type);
1267 LIST_FOR_EACH (sub, node, &expr->andor) {
1268 struct expr *new_sub = expr_clone(sub);
1269 list_push_back(&new->andor, &new_sub->node);
1274 /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1275 * expression nor any of its substructure will be shared with 'expr'. */
1277 expr_clone(struct expr *expr)
1279 switch (expr->type) {
1281 return expr_clone_cmp(expr);
1285 return expr_clone_andor(expr);
1287 case EXPR_T_BOOLEAN:
1288 return expr_create_boolean(expr->boolean);
1293 /* Destroys 'expr' and all of the sub-expressions it references. */
1295 expr_destroy(struct expr *expr)
1301 struct expr *sub, *next;
1303 switch (expr->type) {
1305 if (!expr->cmp.symbol->width) {
1306 free(expr->cmp.string);
1312 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1313 list_remove(&sub->node);
1318 case EXPR_T_BOOLEAN:
1326 /* An element in a linked list of symbols.
1328 * Used to detect when a symbol is being expanded recursively, to allow
1329 * flagging an error. */
1330 struct annotation_nesting {
1331 struct ovs_list node;
1332 const struct expr_symbol *symbol;
1335 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1336 struct ovs_list *nesting, char **errorp);
1338 static struct expr *
1339 parse_and_annotate(const char *s, const struct shash *symtab,
1340 struct ovs_list *nesting, char **errorp)
1345 expr = expr_parse_string(s, symtab, &error);
1347 expr = expr_annotate__(expr, symtab, nesting, &error);
1352 *errorp = xasprintf("Error parsing expression `%s' encountered as "
1353 "prerequisite or predicate of initial expression: "
1360 static struct expr *
1361 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1362 struct ovs_list *nesting, char **errorp)
1364 const struct expr_symbol *symbol = expr->cmp.symbol;
1365 const struct annotation_nesting *iter;
1366 LIST_FOR_EACH (iter, node, nesting) {
1367 if (iter->symbol == symbol) {
1368 *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1375 struct annotation_nesting an;
1377 list_push_back(nesting, &an.node);
1379 struct expr *prereqs = NULL;
1380 if (symbol->prereqs) {
1381 prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1387 if (symbol->expansion) {
1388 if (symbol->level == EXPR_L_ORDINAL) {
1389 struct expr_field field;
1391 if (!parse_field_from_string(symbol->expansion, symtab,
1396 expr->cmp.symbol = field.symbol;
1397 mf_subvalue_shift(&expr->cmp.value, field.ofs);
1398 mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1400 struct expr *expansion;
1402 expansion = parse_and_annotate(symbol->expansion, symtab,
1408 bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1409 positive ^= expr->cmp.relop == EXPR_R_NE;
1411 expr_not(expansion);
1419 list_remove(&an.node);
1420 return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1424 expr_destroy(prereqs);
1425 list_remove(&an.node);
1430 expr_annotate__(struct expr *expr, const struct shash *symtab,
1431 struct ovs_list *nesting, char **errorp)
1433 switch (expr->type) {
1435 return expr_annotate_cmp(expr, symtab, nesting, errorp);
1439 struct expr *sub, *next;
1441 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1442 list_remove(&sub->node);
1443 struct expr *new_sub = expr_annotate__(sub, symtab,
1449 expr_insert_andor(expr, next, new_sub);
1455 case EXPR_T_BOOLEAN:
1464 /* "Annotates" 'expr', which does the following:
1466 * - Applies prerequisites, by locating each comparison operator whose
1467 * field has a prerequisite and adding a logical AND against those
1470 * - Expands references to subfield symbols, by replacing them by
1471 * references to their underlying field symbols (suitably shifted).
1473 * - Expands references to predicate symbols, by replacing them by the
1474 * expressions that they expand to.
1476 * In each case, annotation occurs recursively as necessary. */
1478 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1480 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1481 return expr_annotate__(expr, symtab, &nesting, errorp);
1484 static struct expr *
1485 expr_simplify_ne(struct expr *expr)
1487 struct expr *new = NULL;
1488 const union mf_subvalue *value = &expr->cmp.value;
1489 const union mf_subvalue *mask = &expr->cmp.mask;
1490 int w = expr->cmp.symbol->width;
1493 for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1496 e = xzalloc(sizeof *e);
1497 e->type = EXPR_T_CMP;
1498 e->cmp.symbol = expr->cmp.symbol;
1499 e->cmp.relop = EXPR_R_EQ;
1500 bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1501 !bitwise_get_bit(value, sizeof *value, i));
1502 bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1504 new = expr_combine(EXPR_T_OR, new, e);
1513 static struct expr *
1514 expr_simplify_relational(struct expr *expr)
1516 const union mf_subvalue *value = &expr->cmp.value;
1517 int start, n_bits, end;
1519 find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1521 ovs_assert(n_bits > 0);
1522 end = start + n_bits;
1525 if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1526 new = xmemdup(expr, sizeof *expr);
1527 new->cmp.relop = EXPR_R_EQ;
1532 bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1533 for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1535 z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1538 e = xmemdup(expr, sizeof *expr);
1539 e->cmp.relop = EXPR_R_EQ;
1540 bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1541 bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1542 bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1543 new = expr_combine(EXPR_T_OR, new, e);
1546 return new ? new : expr_create_boolean(false);
1549 /* Takes ownership of 'expr' and returns an equivalent expression whose
1550 * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1552 expr_simplify(struct expr *expr)
1554 struct expr *sub, *next;
1556 switch (expr->type) {
1558 return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1559 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1560 : expr_simplify_relational(expr));
1564 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1565 list_remove(&sub->node);
1566 expr_insert_andor(expr, next, expr_simplify(sub));
1568 return expr_fix(expr);
1570 case EXPR_T_BOOLEAN:
1576 static const struct expr_symbol *
1577 expr_is_cmp(const struct expr *expr)
1579 switch (expr->type) {
1581 return expr->cmp.symbol;
1585 const struct expr_symbol *prev = NULL;
1588 LIST_FOR_EACH (sub, node, &expr->andor) {
1589 const struct expr_symbol *symbol = expr_is_cmp(sub);
1590 if (!symbol || (prev && symbol != prev)) {
1598 case EXPR_T_BOOLEAN:
1608 const struct expr_symbol *relop;
1609 enum expr_type type;
1613 compare_expr_sort(const void *a_, const void *b_)
1615 const struct expr_sort *a = a_;
1616 const struct expr_sort *b = b_;
1618 if (a->type != b->type) {
1619 return a->type < b->type ? -1 : 1;
1620 } else if (a->relop) {
1621 int cmp = strcmp(a->relop->name, b->relop->name);
1626 enum expr_type a_type = a->expr->type;
1627 enum expr_type b_type = a->expr->type;
1628 return a_type < b_type ? -1 : a_type > b_type;
1629 } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1630 size_t a_len = list_size(&a->expr->andor);
1631 size_t b_len = list_size(&b->expr->andor);
1632 return a_len < b_len ? -1 : a_len > b_len;
1638 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1640 static struct expr *
1641 crush_and(struct expr *expr, const struct expr_symbol *symbol)
1643 ovs_assert(!list_is_short(&expr->andor));
1645 union mf_subvalue value, mask;
1646 memset(&value, 0, sizeof value);
1647 memset(&mask, 0, sizeof mask);
1649 struct expr *sub, *next = NULL;
1650 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1651 list_remove(&sub->node);
1652 struct expr *new = crush_cmps(sub, symbol);
1653 switch (new->type) {
1655 if (!mf_subvalue_intersect(&value, &mask,
1656 &new->cmp.value, &new->cmp.mask,
1660 return expr_create_boolean(false);
1667 list_insert(&next->node, &new->node);
1669 case EXPR_T_BOOLEAN:
1670 if (!new->boolean) {
1678 if (list_is_empty(&expr->andor)) {
1679 if (is_all_zeros(&mask, sizeof mask)) {
1681 return expr_create_boolean(true);
1684 cmp = xmalloc(sizeof *cmp);
1685 cmp->type = EXPR_T_CMP;
1686 cmp->cmp.symbol = symbol;
1687 cmp->cmp.relop = EXPR_R_EQ;
1688 cmp->cmp.value = value;
1689 cmp->cmp.mask = mask;
1693 } else if (list_is_short(&expr->andor)) {
1694 /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1695 * computed as "a && b", etc. */
1696 struct expr *disjuncts = expr_from_node(list_pop_front(&expr->andor));
1699 or = xmalloc(sizeof *or);
1700 or->type = EXPR_T_OR;
1701 list_init(&or->andor);
1703 ovs_assert(disjuncts->type == EXPR_T_OR);
1704 LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1705 ovs_assert(sub->type == EXPR_T_CMP);
1706 list_remove(&sub->node);
1707 if (mf_subvalue_intersect(&value, &mask,
1708 &sub->cmp.value, &sub->cmp.mask,
1709 &sub->cmp.value, &sub->cmp.mask)) {
1710 list_push_back(&or->andor, &sub->node);
1717 if (list_is_empty(&or->andor)) {
1719 return expr_create_boolean(false);
1720 } else if (list_is_short(&or->andor)) {
1721 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1728 /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1729 * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1730 struct expr *as = expr_from_node(list_pop_front(&expr->andor));
1731 struct expr *bs = expr_from_node(list_pop_front(&expr->andor));
1732 struct expr *new = NULL;
1735 or = xmalloc(sizeof *or);
1736 or->type = EXPR_T_OR;
1737 list_init(&or->andor);
1740 LIST_FOR_EACH (a, node, &as->andor) {
1741 union mf_subvalue a_value, a_mask;
1743 ovs_assert(a->type == EXPR_T_CMP);
1744 if (!mf_subvalue_intersect(&value, &mask,
1745 &a->cmp.value, &a->cmp.mask,
1746 &a_value, &a_mask)) {
1751 LIST_FOR_EACH (b, node, &bs->andor) {
1752 ovs_assert(b->type == EXPR_T_CMP);
1754 new = xmalloc(sizeof *new);
1755 new->type = EXPR_T_CMP;
1756 new->cmp.symbol = symbol;
1757 new->cmp.relop = EXPR_R_EQ;
1759 if (mf_subvalue_intersect(&a_value, &a_mask,
1760 &b->cmp.value, &b->cmp.mask,
1761 &new->cmp.value, &new->cmp.mask)) {
1762 list_push_back(&or->andor, &new->node);
1771 if (list_is_empty(&or->andor)) {
1774 return expr_create_boolean(false);
1775 } else if (list_is_short(&or->andor)) {
1776 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1778 if (list_is_empty(&expr->andor)) {
1780 return crush_cmps(cmp, symbol);
1782 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1784 } else if (!list_is_empty(&expr->andor)) {
1785 struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1786 ovs_assert(!list_is_short(&e->andor));
1787 return crush_cmps(e, symbol);
1790 return crush_cmps(or, symbol);
1796 compare_expr(const void *a_, const void *b_)
1798 const struct expr *const *ap = a_;
1799 const struct expr *const *bp = b_;
1800 const struct expr *a = *ap;
1801 const struct expr *b = *bp;
1802 int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1804 d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1809 static struct expr *
1810 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1812 struct expr *sub, *next = NULL;
1814 /* First, crush all the subexpressions. That might eliminate the
1815 * OR-expression entirely; if so, return the result. */
1816 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1817 list_remove(&sub->node);
1818 expr_insert_andor(expr, next, crush_cmps(sub, symbol));
1820 expr = expr_fix(expr);
1821 if (expr->type != EXPR_T_OR) {
1825 /* Eliminate duplicates by sorting the subexpressions. */
1826 size_t n = list_size(&expr->andor);
1827 struct expr **subs = xmalloc(n * sizeof *subs);
1830 LIST_FOR_EACH (sub, node, &expr->andor) {
1835 qsort(subs, n, sizeof *subs, compare_expr);
1837 list_init(&expr->andor);
1838 list_push_back(&expr->andor, &subs[0]->node);
1839 for (i = 1; i < n; i++) {
1840 struct expr *a = expr_from_node(list_back(&expr->andor));
1841 struct expr *b = subs[i];
1842 if (memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value)
1843 || memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask)) {
1844 list_push_back(&expr->andor, &b->node);
1850 return expr_fix(expr);
1853 /* Converts 'expr', which must be a cmp in the sense determined by
1854 * expr_is_cmp(). Returns a cmp, a disjunction of cmps, or a boolean. */
1855 static struct expr *
1856 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
1858 switch (expr->type) {
1860 return crush_or(expr, symbol);
1863 return crush_and(expr, symbol);
1868 case EXPR_T_BOOLEAN:
1876 static struct expr *
1877 expr_sort(struct expr *expr)
1879 size_t n = list_size(&expr->andor);
1880 struct expr_sort *subs = xmalloc(n * sizeof *subs);
1885 LIST_FOR_EACH (sub, node, &expr->andor) {
1887 subs[i].relop = expr_is_cmp(sub);
1888 subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
1893 qsort(subs, n, sizeof *subs, compare_expr_sort);
1895 list_init(&expr->andor);
1896 for (int i = 0; i < n; ) {
1897 if (subs[i].relop) {
1899 for (j = i + 1; j < n; j++) {
1900 if (subs[i].relop != subs[j].relop) {
1905 struct expr *crushed;
1907 crushed = crush_cmps(subs[i].expr, subs[i].relop);
1909 struct expr *combined = subs[i].expr;
1910 for (int k = i + 1; k < j; k++) {
1911 combined = expr_combine(EXPR_T_AND, combined,
1914 ovs_assert(!list_is_short(&combined->andor));
1915 crushed = crush_cmps(combined, subs[i].relop);
1917 if (crushed->type == EXPR_T_BOOLEAN) {
1918 if (!crushed->boolean) {
1919 for (int k = j; k < n; k++) {
1920 expr_destroy(subs[k].expr);
1929 expr = expr_combine(EXPR_T_AND, expr, crushed);
1933 expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
1941 static struct expr *expr_normalize_or(struct expr *expr);
1943 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
1944 * a clause is a cmp or a disjunction of cmps on a single field. */
1945 static struct expr *
1946 expr_normalize_and(struct expr *expr)
1948 ovs_assert(expr->type == EXPR_T_AND);
1950 expr = expr_sort(expr);
1951 if (expr->type != EXPR_T_AND) {
1952 ovs_assert(expr->type == EXPR_T_BOOLEAN);
1957 LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
1958 if (&b->node == &expr->andor
1959 || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP) {
1960 } else if (a->cmp.symbol != b->cmp.symbol) {
1962 } else if (mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
1963 &b->cmp.value, &b->cmp.mask,
1964 &b->cmp.value, &b->cmp.mask)) {
1965 list_remove(&a->node);
1969 return expr_create_boolean(false);
1972 if (list_is_short(&expr->andor)) {
1973 struct expr *sub = expr_from_node(list_front(&expr->andor));
1979 LIST_FOR_EACH (sub, node, &expr->andor) {
1980 if (sub->type == EXPR_T_CMP) {
1984 ovs_assert(sub->type == EXPR_T_OR);
1985 const struct expr_symbol *symbol = expr_is_cmp(sub);
1986 if (!symbol || symbol->must_crossproduct) {
1987 struct expr *or = expr_create_andor(EXPR_T_OR);
1990 LIST_FOR_EACH (k, node, &sub->andor) {
1991 struct expr *and = expr_create_andor(EXPR_T_AND);
1994 LIST_FOR_EACH (m, node, &expr->andor) {
1995 struct expr *term = m == sub ? k : m;
1996 if (term->type == EXPR_T_AND) {
1999 LIST_FOR_EACH (p, node, &term->andor) {
2000 struct expr *new = expr_clone(p);
2001 list_push_back(&and->andor, &new->node);
2004 struct expr *new = expr_clone(term);
2005 list_push_back(&and->andor, &new->node);
2008 list_push_back(&or->andor, &and->node);
2011 return expr_normalize_or(or);
2017 static struct expr *
2018 expr_normalize_or(struct expr *expr)
2020 struct expr *sub, *next;
2022 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2023 if (sub->type == EXPR_T_AND) {
2024 list_remove(&sub->node);
2026 struct expr *new = expr_normalize_and(sub);
2027 if (new->type == EXPR_T_BOOLEAN) {
2034 expr_insert_andor(expr, next, new);
2037 ovs_assert(sub->type == EXPR_T_CMP);
2040 if (list_is_empty(&expr->andor)) {
2042 return expr_create_boolean(false);
2044 if (list_is_short(&expr->andor)) {
2045 struct expr *sub = expr_from_node(list_pop_front(&expr->andor));
2053 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2054 * an expression in terms of only relationals, AND, and OR. Returns either a
2055 * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2056 * clause is a cmp or a disjunction of cmps on a single field. This form is
2057 * significant because it is a form that can be directly converted to OpenFlow
2058 * flows with the Open vSwitch "conjunctive match" extension.
2060 * 'expr' must already have been simplified, with expr_simplify(). */
2062 expr_normalize(struct expr *expr)
2064 switch (expr->type) {
2069 return expr_normalize_and(expr);
2072 return expr_normalize_or(expr);
2074 case EXPR_T_BOOLEAN:
2080 /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2081 * nonnull then it is copied into the new expr_match, otherwise the new
2082 * expr_match's 'match' member is initialized to a catch-all match for the
2083 * caller to refine in-place.
2085 * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2086 * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2087 * expr_match will not have any conjunctions.
2089 * The caller should use expr_match_add() to add the expr_match to a hash table
2090 * after it is finalized. */
2091 static struct expr_match *
2092 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2095 struct expr_match *match = xmalloc(sizeof *match);
2099 match_init_catchall(&match->match);
2102 match->conjunctions = xmalloc(sizeof *match->conjunctions);
2103 match->conjunctions[0].id = conj_id;
2104 match->conjunctions[0].clause = clause;
2105 match->conjunctions[0].n_clauses = n_clauses;
2107 match->allocated = 1;
2109 match->conjunctions = NULL;
2111 match->allocated = 0;
2116 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2119 * This might actually destroy 'match' because it gets merged together with
2120 * some existing conjunction.*/
2122 expr_match_add(struct hmap *matches, struct expr_match *match)
2124 uint32_t hash = match_hash(&match->match, 0);
2125 struct expr_match *m;
2127 HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2128 if (match_equal(&m->match, &match->match)) {
2129 if (!m->n || !match->n) {
2130 free(m->conjunctions);
2131 m->conjunctions = NULL;
2135 ovs_assert(match->n == 1);
2136 if (m->n >= m->allocated) {
2137 m->conjunctions = x2nrealloc(m->conjunctions,
2139 sizeof *m->conjunctions);
2141 m->conjunctions[m->n++] = match->conjunctions[0];
2143 free(match->conjunctions);
2149 hmap_insert(matches, &match->hmap_node, hash);
2153 constrain_match(const struct expr *expr, const struct simap *ports,
2156 ovs_assert(expr->type == EXPR_T_CMP);
2157 if (expr->cmp.symbol->width) {
2158 mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2159 &expr->cmp.mask, m);
2161 const struct simap_node *node;
2162 node = ports ? simap_find(ports, expr->cmp.string) : NULL;
2167 struct mf_subfield sf;
2168 sf.field = expr->cmp.symbol->field;
2170 sf.n_bits = expr->cmp.symbol->field->n_bits;
2172 union mf_subvalue x;
2173 memset(&x, 0, sizeof x);
2174 x.integer = htonll(node->data);
2176 mf_write_subfield(&sf, &x, m);
2182 add_disjunction(const struct expr *or, const struct simap *ports,
2183 struct match *m, uint8_t clause, uint8_t n_clauses,
2184 uint32_t conj_id, struct hmap *matches)
2189 ovs_assert(or->type == EXPR_T_OR);
2190 LIST_FOR_EACH (sub, node, &or->andor) {
2191 struct expr_match *match = expr_match_new(m, clause, n_clauses,
2193 if (constrain_match(sub, ports, &match->match)) {
2194 expr_match_add(matches, match);
2197 free(match->conjunctions);
2202 /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2203 * that shouldn't happen much. */
2208 add_conjunction(const struct expr *and, const struct simap *ports,
2209 uint32_t *n_conjsp, struct hmap *matches)
2215 match_init_catchall(&match);
2217 ovs_assert(and->type == EXPR_T_AND);
2218 LIST_FOR_EACH (sub, node, &and->andor) {
2219 switch (sub->type) {
2221 if (!constrain_match(sub, ports, &match)) {
2229 case EXPR_T_BOOLEAN:
2235 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2236 } else if (n_clauses == 1) {
2237 LIST_FOR_EACH (sub, node, &and->andor) {
2238 if (sub->type == EXPR_T_OR) {
2239 add_disjunction(sub, ports, &match, 0, 0, 0, matches);
2245 LIST_FOR_EACH (sub, node, &and->andor) {
2246 if (sub->type == EXPR_T_OR) {
2247 if (!add_disjunction(sub, ports, &match, clause++,
2248 n_clauses, *n_conjsp, matches)) {
2249 /* This clause can't ever match, so we might as well skip
2250 * adding the other clauses--the overall disjunctive flow
2251 * can't ever match. Ideally we would also back out all of
2252 * the clauses we already added, but that seems like a lot
2253 * of trouble for a case that might never occur in
2260 /* Add the flow that matches on conj_id. */
2261 match_set_conj_id(&match, *n_conjsp);
2262 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2267 add_cmp_flow(const struct expr *cmp, const struct simap *ports,
2268 struct hmap *matches)
2270 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2271 if (constrain_match(cmp, ports, &m->match)) {
2272 expr_match_add(matches, m);
2278 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2279 * a collection of Open vSwitch flows in 'matches', which this function
2280 * initializes to an hmap of "struct expr_match" structures. Returns the
2281 * number of conjunctive match IDs consumed by 'matches', which uses
2282 * conjunctive match IDs beginning with 0; the caller must offset or remap them
2283 * into the desired range as necessary.
2285 * The matches inserted into 'matches' will be of three distinct kinds:
2287 * - Ordinary flows. The caller should add these OpenFlow flows with
2288 * its desired actions.
2290 * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2291 * structure. The caller should add these OpenFlow flows with the
2292 * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2293 * remapping the ids.
2295 * - conj_id flows, distinguished by matching on the "conj_id" field. The
2296 * caller should remap the conj_id and add the OpenFlow flow with its
2299 * 'ports' must be a map from strings (presumably names of ports) to integers.
2300 * Any comparisons against string fields in 'expr' are translated into integers
2301 * through this map. A comparison against a string that is not in 'ports' acts
2302 * like a Boolean "false"; that is, it will always fail to match. For a simple
2303 * expression, this means that the overall expression always fails to match,
2304 * but an expression with a disjunction on the string field might still match
2305 * on other port names.
2307 * (This treatment of string fields might be too simplistic in general, but it
2308 * seems reasonable for now when string fields are used only for ports.) */
2310 expr_to_matches(const struct expr *expr, const struct simap *ports,
2311 struct hmap *matches)
2313 uint32_t n_conjs = 0;
2316 switch (expr->type) {
2318 add_cmp_flow(expr, ports, matches);
2322 add_conjunction(expr, ports, &n_conjs, matches);
2326 if (expr_is_cmp(expr)) {
2329 LIST_FOR_EACH (sub, node, &expr->andor) {
2330 add_cmp_flow(sub, ports, matches);
2335 LIST_FOR_EACH (sub, node, &expr->andor) {
2336 if (sub->type == EXPR_T_AND) {
2337 add_conjunction(sub, ports, &n_conjs, matches);
2339 add_cmp_flow(sub, ports, matches);
2345 case EXPR_T_BOOLEAN:
2346 if (expr->boolean) {
2347 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2348 expr_match_add(matches, m);
2357 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2358 * 'matches' hmap itself. */
2360 expr_matches_destroy(struct hmap *matches)
2362 struct expr_match *m, *n;
2364 HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) {
2365 hmap_remove(matches, &m->hmap_node);
2366 free(m->conjunctions);
2369 hmap_destroy(matches);
2372 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2375 expr_matches_print(const struct hmap *matches, FILE *stream)
2377 if (hmap_is_empty(matches)) {
2378 fputs("(no flows)\n", stream);
2382 const struct expr_match *m;
2383 HMAP_FOR_EACH (m, hmap_node, matches) {
2384 char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2389 for (int i = 0; i < m->n; i++) {
2390 const struct cls_conjunction *c = &m->conjunctions[i];
2391 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2392 i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2399 /* Returns true if 'expr' honors the invariants for expressions (see the large
2400 * comment above "struct expr" in expr.h), false otherwise. */
2402 expr_honors_invariants(const struct expr *expr)
2404 const struct expr *sub;
2406 switch (expr->type) {
2408 if (expr->cmp.symbol->width) {
2409 for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2410 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2419 if (list_is_short(&expr->andor)) {
2422 LIST_FOR_EACH (sub, node, &expr->andor) {
2423 if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2429 case EXPR_T_BOOLEAN:
2438 expr_is_normalized_and(const struct expr *expr)
2440 /* XXX should also check that no symbol is repeated. */
2441 const struct expr *sub;
2443 LIST_FOR_EACH (sub, node, &expr->andor) {
2444 if (!expr_is_cmp(sub)) {
2451 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2454 expr_is_normalized(const struct expr *expr)
2456 switch (expr->type) {
2461 return expr_is_normalized_and(expr);
2464 if (!expr_is_cmp(expr)) {
2465 const struct expr *sub;
2467 LIST_FOR_EACH (sub, node, &expr->andor) {
2468 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2475 case EXPR_T_BOOLEAN:
2483 /* Action parsing helper. */
2485 static struct expr *
2486 parse_assignment(struct expr_context *ctx, const struct simap *ports,
2487 struct ofpbuf *ofpacts)
2489 struct expr *prereqs = NULL;
2491 struct expr_field f;
2492 if (!parse_field(ctx, &f)) {
2495 if (!lexer_match(ctx->lexer, LEX_T_EQUALS)) {
2496 expr_syntax_error(ctx, "expecting `='.");
2500 if (f.symbol->expansion && f.symbol->level != EXPR_L_ORDINAL) {
2501 expr_error(ctx, "Can't assign to predicate symbol %s.",
2506 struct expr_constant_set cs;
2507 if (!parse_constant_set(ctx, &cs)) {
2511 if (!type_check(ctx, &f, &cs)) {
2512 goto exit_destroy_cs;
2514 if (cs.in_curlies) {
2515 expr_error(ctx, "Assignments require a single value.");
2516 goto exit_destroy_cs;
2519 const struct expr_symbol *orig_symbol = f.symbol;
2520 union expr_constant *c = cs.values;
2522 /* Accumulate prerequisites. */
2523 if (f.symbol->prereqs) {
2524 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2527 e = parse_and_annotate(f.symbol->prereqs, ctx->symtab, &nesting,
2530 expr_error(ctx, "%s", error);
2532 goto exit_destroy_cs;
2534 prereqs = expr_combine(EXPR_T_AND, prereqs, e);
2537 /* If there's no expansion, we're done. */
2538 if (!f.symbol->expansion) {
2543 struct expr_field expansion;
2545 if (!parse_field_from_string(f.symbol->expansion, ctx->symtab,
2546 &expansion, &error)) {
2547 expr_error(ctx, "%s", error);
2549 goto exit_destroy_cs;
2551 f.symbol = expansion.symbol;
2552 f.ofs += expansion.ofs;
2555 if (!f.symbol->field->writable) {
2556 expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2557 goto exit_destroy_cs;
2560 struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2561 sf->field = f.symbol->field;
2562 if (f.symbol->width) {
2563 mf_subvalue_shift(&c->value, f.ofs);
2565 memset(&c->mask, 0, sizeof c->mask);
2566 bitwise_one(&c->mask, sizeof c->mask, f.ofs, f.n_bits);
2568 mf_subvalue_shift(&c->mask, f.ofs);
2571 memcpy(&sf->value, &c->value.u8[sizeof c->value - sf->field->n_bytes],
2572 sf->field->n_bytes);
2573 memcpy(&sf->mask, &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2574 sf->field->n_bytes);
2576 uint32_t port = simap_get(ports, c->string);
2577 bitwise_put(port, &sf->value,
2578 sf->field->n_bytes, 0, sf->field->n_bits);
2579 bitwise_put(UINT64_MAX, &sf->mask,
2580 sf->field->n_bytes, 0, sf->field->n_bits);
2584 expr_constant_set_destroy(&cs);
2589 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2590 * "field = value" into 'ofpacts'. The parameters and return value match those
2591 * for actions_parse(). */
2593 expr_parse_assignment(struct lexer *lexer, const struct shash *symtab,
2594 const struct simap *ports,
2595 struct ofpbuf *ofpacts, struct expr **prereqsp)
2597 struct expr_context ctx;
2599 ctx.symtab = symtab;
2603 struct expr *prereqs = parse_assignment(&ctx, ports, ofpacts);
2605 expr_destroy(prereqs);
2608 *prereqsp = prereqs;