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"
27 #include "openvswitch/vlog.h"
29 VLOG_DEFINE_THIS_MODULE(expr);
31 /* Returns the name of measurement level 'level'. */
33 expr_level_to_string(enum expr_level level)
36 case EXPR_L_NOMINAL: return "nominal";
37 case EXPR_L_BOOLEAN: return "Boolean";
38 case EXPR_L_ORDINAL: return "ordinal";
39 default: OVS_NOT_REACHED();
43 /* Relational operators. */
45 /* Returns a string form of relational operator 'relop'. */
47 expr_relop_to_string(enum expr_relop relop)
50 case EXPR_R_EQ: return "==";
51 case EXPR_R_NE: return "!=";
52 case EXPR_R_LT: return "<";
53 case EXPR_R_LE: return "<=";
54 case EXPR_R_GT: return ">";
55 case EXPR_R_GE: return ">=";
56 default: OVS_NOT_REACHED();
61 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
66 case LEX_T_EQ: r = EXPR_R_EQ; break;
67 case LEX_T_NE: r = EXPR_R_NE; break;
68 case LEX_T_LT: r = EXPR_R_LT; break;
69 case LEX_T_LE: r = EXPR_R_LE; break;
70 case LEX_T_GT: r = EXPR_R_GT; break;
71 case LEX_T_GE: r = EXPR_R_GE; break;
72 default: return false;
81 /* Returns the relational operator that 'relop' becomes if you turn the
82 * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
83 * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
84 * b" is equivalent to "b >= a". */
85 static enum expr_relop
86 expr_relop_turn(enum expr_relop relop)
89 case EXPR_R_EQ: return EXPR_R_EQ;
90 case EXPR_R_NE: return EXPR_R_NE;
91 case EXPR_R_LT: return EXPR_R_GT;
92 case EXPR_R_LE: return EXPR_R_GE;
93 case EXPR_R_GT: return EXPR_R_LT;
94 case EXPR_R_GE: return EXPR_R_LE;
95 default: OVS_NOT_REACHED();
99 /* Returns the relational operator that is the opposite of 'relop'. */
100 static enum expr_relop
101 expr_relop_invert(enum expr_relop relop)
104 case EXPR_R_EQ: return EXPR_R_NE;
105 case EXPR_R_NE: return EXPR_R_EQ;
106 case EXPR_R_LT: return EXPR_R_GE;
107 case EXPR_R_LE: return EXPR_R_GT;
108 case EXPR_R_GT: return EXPR_R_LE;
109 case EXPR_R_GE: return EXPR_R_LT;
110 default: OVS_NOT_REACHED();
114 /* Constructing and manipulating expressions. */
116 /* Creates and returns a logical AND or OR expression (according to 'type',
117 * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
118 * sub-expressions. (To satisfy the invariants for expressions, the caller
119 * must add at least two sub-expressions whose types are different from
122 expr_create_andor(enum expr_type type)
124 struct expr *e = xmalloc(sizeof *e);
126 list_init(&e->andor);
130 /* Returns a logical AND or OR expression (according to 'type', which must be
131 * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
134 * - If 'a' or 'b' is NULL, just returns the other one (which means that if
135 * that other one is not of the given 'type', then the returned
136 * expression is not either).
138 * - If 'a' or 'b', or both, have type 'type', then they are combined into
139 * a single node that satisfies the invariants for expressions. */
141 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
147 } else if (a->type == type) {
148 if (b->type == type) {
149 list_splice(&a->andor, b->andor.next, &b->andor);
152 list_push_back(&a->andor, &b->node);
155 } else if (b->type == type) {
156 list_push_front(&b->andor, &a->node);
159 struct expr *e = expr_create_andor(type);
160 list_push_back(&e->andor, &a->node);
161 list_push_back(&e->andor, &b->node);
167 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
169 if (new->type == andor->type) {
170 if (andor->type == EXPR_T_AND) {
171 /* Conjunction junction, what's your function? */
173 list_splice(&before->node, new->andor.next, &new->andor);
176 list_insert(&before->node, &new->node);
180 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
182 expr_create_boolean(bool b)
184 struct expr *e = xmalloc(sizeof *e);
185 e->type = EXPR_T_BOOLEAN;
191 expr_not(struct expr *expr)
195 switch (expr->type) {
197 expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
202 LIST_FOR_EACH (sub, node, &expr->andor) {
205 expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
209 expr->boolean = !expr->boolean;
217 expr_fix_andor(struct expr *expr, bool short_circuit)
219 struct expr *sub, *next;
221 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
222 if (sub->type == EXPR_T_BOOLEAN) {
223 if (sub->boolean == short_circuit) {
225 return expr_create_boolean(short_circuit);
227 list_remove(&sub->node);
233 if (list_is_short(&expr->andor)) {
234 if (list_is_empty(&expr->andor)) {
236 return expr_create_boolean(!short_circuit);
238 sub = expr_from_node(list_front(&expr->andor));
247 /* Returns 'expr' modified so that top-level oddities are fixed up:
249 * - Eliminates any EXPR_T_BOOLEAN operands at the top level.
251 * - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
253 expr_fix(struct expr *expr)
255 switch (expr->type) {
260 return expr_fix_andor(expr, false);
263 return expr_fix_andor(expr, true);
276 find_bitwise_range(const union mf_subvalue *sv, int width,
277 int *startp, int *n_bitsp)
279 unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
281 unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
283 || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
285 *n_bitsp = end - start;
289 *startp = *n_bitsp = 0;
293 expr_format_cmp(const struct expr *e, struct ds *s)
295 /* The common case is numerical comparisons.
296 * Handle string comparisons as a special case. */
297 if (!e->cmp.symbol->width) {
298 ds_put_format(s, "%s %s ", e->cmp.symbol->name,
299 expr_relop_to_string(e->cmp.relop));
300 json_string_escape(e->cmp.string, s);
305 find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
306 if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
309 positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
310 positive ^= e->cmp.relop == EXPR_R_NE;
314 ds_put_cstr(s, e->cmp.symbol->name);
315 if (e->cmp.symbol->width > 1) {
316 ds_put_format(s, "[%d]", ofs);
321 ds_put_cstr(s, e->cmp.symbol->name);
322 if (n > 0 && n < e->cmp.symbol->width) {
324 ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
326 ds_put_format(s, "[%d]", ofs);
330 ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
333 union mf_subvalue value;
335 memset(&value, 0, sizeof value);
336 bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
337 &value, sizeof value, 0,
339 mf_format_subvalue(&value, s);
341 mf_format_subvalue(&e->cmp.value, s);
343 mf_format_subvalue(&e->cmp.mask, s);
348 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
353 LIST_FOR_EACH (sub, node, &e->andor) {
355 ds_put_format(s, " %s ", op);
358 if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
368 /* Appends a string form of 'e' to 's'. The string form is acceptable for
369 * parsing back into an equivalent expression. */
371 expr_format(const struct expr *e, struct ds *s)
375 expr_format_cmp(e, s);
379 expr_format_andor(e, "&&", s);
383 expr_format_andor(e, "||", s);
387 ds_put_char(s, e->boolean ? '1' : '0');
392 /* Prints a string form of 'e' on stdout, followed by a new-line. */
394 expr_print(const struct expr *e)
399 expr_format(e, &output);
400 puts(ds_cstr(&output));
406 /* Type of a "union expr_constant" or "struct expr_constant_set". */
407 enum expr_constant_type {
412 /* A string or integer constant (one must know which from context). */
413 union expr_constant {
416 * The width of a constant isn't always clear, e.g. if you write "1",
417 * there's no way to tell whether you mean for that to be a 1-bit constant
418 * or a 128-bit constant or somewhere in between. */
420 union mf_subvalue value;
421 union mf_subvalue mask; /* Only initialized if 'masked'. */
424 enum lex_format format; /* From the constant's lex_token. */
427 /* Null-terminated string constant. */
431 /* A collection of "union expr_constant"s of the same type. */
432 struct expr_constant_set {
433 union expr_constant *values; /* Constants. */
434 size_t n_values; /* Number of constants. */
435 enum expr_constant_type type; /* Type of the constants. */
436 bool in_curlies; /* Whether the constants were in {}. */
439 /* A reference to a symbol or a subfield of a symbol.
441 * For string fields, ofs and n_bits are 0. */
443 const struct expr_symbol *symbol; /* The symbol. */
444 int ofs; /* Starting bit offset. */
445 int n_bits; /* Number of bits. */
448 /* Context maintained during expr_parse(). */
449 struct expr_context {
450 struct lexer *lexer; /* Lexer for pulling more tokens. */
451 const struct shash *symtab; /* Symbol table. */
452 char *error; /* Error, if any, otherwise NULL. */
453 bool not; /* True inside odd number of NOT operators. */
456 struct expr *expr_parse__(struct expr_context *);
457 static void expr_not(struct expr *);
458 static void expr_constant_set_destroy(struct expr_constant_set *);
459 static bool parse_field(struct expr_context *, struct expr_field *);
462 expr_error_handle_common(struct expr_context *ctx)
465 /* Already have an error, suppress this one since the cascade seems
466 * unlikely to be useful. */
468 } else if (ctx->lexer->token.type == LEX_T_ERROR) {
469 /* The lexer signaled an error. Nothing at the expression level
470 * accepts an error token, so we'll inevitably end up here with some
471 * meaningless parse error. Report the lexical error instead. */
472 ctx->error = xstrdup(ctx->lexer->token.s);
479 static void OVS_PRINTF_FORMAT(2, 3)
480 expr_error(struct expr_context *ctx, const char *message, ...)
482 if (expr_error_handle_common(ctx)) {
487 va_start(args, message);
488 ctx->error = xvasprintf(message, args);
492 static void OVS_PRINTF_FORMAT(2, 3)
493 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
495 if (expr_error_handle_common(ctx)) {
502 ds_put_cstr(&s, "Syntax error ");
503 if (ctx->lexer->token.type == LEX_T_END) {
504 ds_put_cstr(&s, "at end of input ");
505 } else if (ctx->lexer->start) {
506 ds_put_format(&s, "at `%.*s' ",
507 (int) (ctx->lexer->input - ctx->lexer->start),
512 va_start(args, message);
513 ds_put_format_valist(&s, message, args);
516 ctx->error = ds_steal_cstr(&s);
520 make_cmp__(const struct expr_field *f, enum expr_relop r,
521 const union expr_constant *c)
523 struct expr *e = xzalloc(sizeof *e);
524 e->type = EXPR_T_CMP;
525 e->cmp.symbol = f->symbol;
527 if (f->symbol->width) {
528 bitwise_copy(&c->value, sizeof c->value, 0,
529 &e->cmp.value, sizeof e->cmp.value, f->ofs,
532 bitwise_copy(&c->mask, sizeof c->mask, 0,
533 &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
536 bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
540 e->cmp.string = xstrdup(c->string);
545 /* Returns the minimum reasonable width for integer constant 'c'. */
547 expr_constant_width(const union expr_constant *c)
550 return mf_subvalue_width(&c->mask);
555 case LEX_F_HEXADECIMAL:
556 return mf_subvalue_width(&c->value);
573 type_check(struct expr_context *ctx, const struct expr_field *f,
574 struct expr_constant_set *cs)
576 if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
577 expr_error(ctx, "%s field %s is not compatible with %s constant.",
578 f->symbol->width ? "Integer" : "String",
580 cs->type == EXPR_C_INTEGER ? "integer" : "string");
584 if (f->symbol->width) {
585 for (size_t i = 0; i < cs->n_values; i++) {
586 int w = expr_constant_width(&cs->values[i]);
587 if (w > f->symbol->width) {
588 expr_error(ctx, "%d-bit constant is not compatible with "
590 w, f->symbol->width, f->symbol->name);
600 make_cmp(struct expr_context *ctx,
601 const struct expr_field *f, enum expr_relop r,
602 struct expr_constant_set *cs)
604 struct expr *e = NULL;
606 if (!type_check(ctx, f, cs)) {
610 if (r != EXPR_R_EQ && r != EXPR_R_NE) {
611 if (cs->in_curlies) {
612 expr_error(ctx, "Only == and != operators may be used "
616 if (f->symbol->level == EXPR_L_NOMINAL ||
617 f->symbol->level == EXPR_L_BOOLEAN) {
618 expr_error(ctx, "Only == and != operators may be used "
620 expr_level_to_string(f->symbol->level),
624 if (cs->values[0].masked) {
625 expr_error(ctx, "Only == and != operators may be used with "
626 "masked constants. Consider using subfields instead "
627 "(e.g. eth.src[0..15] > 0x1111 in place of "
628 "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
633 if (f->symbol->level == EXPR_L_NOMINAL) {
634 if (f->symbol->expansion) {
635 ovs_assert(f->symbol->width > 0);
636 for (size_t i = 0; i < cs->n_values; i++) {
637 const union mf_subvalue *value = &cs->values[i].value;
638 bool positive = (value->integer & htonll(1)) != 0;
639 positive ^= r == EXPR_R_NE;
640 positive ^= ctx->not;
642 const char *name = f->symbol->name;
643 expr_error(ctx, "Nominal predicate %s may only be tested "
644 "positively, e.g. `%s' or `%s == 1' but not "
645 "`!%s' or `%s == 0'.",
646 name, name, name, name, name);
650 } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
651 expr_error(ctx, "Nominal field %s may only be tested for "
652 "equality (taking enclosing `!' operators into "
653 "account).", f->symbol->name);
658 e = make_cmp__(f, r, &cs->values[0]);
659 for (size_t i = 1; i < cs->n_values; i++) {
660 e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
661 e, make_cmp__(f, r, &cs->values[i]));
664 expr_constant_set_destroy(cs);
669 expr_get_int(struct expr_context *ctx, int *value)
671 bool ok = lexer_get_int(ctx->lexer, value);
673 expr_syntax_error(ctx, "expecting small integer.");
679 parse_field(struct expr_context *ctx, struct expr_field *f)
681 const struct expr_symbol *symbol;
683 if (ctx->lexer->token.type != LEX_T_ID) {
684 expr_syntax_error(ctx, "expecting field name.");
688 symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
690 expr_syntax_error(ctx, "expecting field name.");
693 lexer_get(ctx->lexer);
696 if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
699 if (!symbol->width) {
700 expr_error(ctx, "Cannot select subfield of string field %s.",
705 if (!expr_get_int(ctx, &low)) {
708 if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
709 if (!expr_get_int(ctx, &high)) {
716 if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
717 expr_syntax_error(ctx, "expecting `]'.");
722 expr_error(ctx, "Invalid bit range %d to %d.", low, high);
724 } else if (high >= symbol->width) {
725 expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
726 low, high, symbol->width, symbol->name);
728 } else if (symbol->level == EXPR_L_NOMINAL
729 && (low != 0 || high != symbol->width - 1)) {
730 expr_error(ctx, "Cannot select subfield of nominal field %s.",
736 f->n_bits = high - low + 1;
739 f->n_bits = symbol->width;
746 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
748 if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
749 lexer_get(ctx->lexer);
752 expr_syntax_error(ctx, "expecting relational operator.");
758 assign_constant_set_type(struct expr_context *ctx,
759 struct expr_constant_set *cs,
760 enum expr_constant_type type)
762 if (!cs->n_values || cs->type == type) {
766 expr_syntax_error(ctx, "expecting %s.",
767 cs->type == EXPR_C_INTEGER ? "integer" : "string");
773 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
774 size_t *allocated_values)
776 if (cs->n_values >= *allocated_values) {
777 cs->values = x2nrealloc(cs->values, allocated_values,
781 if (ctx->lexer->token.type == LEX_T_STRING) {
782 if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
785 cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
786 lexer_get(ctx->lexer);
788 } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
789 ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
790 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
794 union expr_constant *c = &cs->values[cs->n_values++];
795 c->value = ctx->lexer->token.value;
796 c->format = ctx->lexer->token.format;
797 c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
799 c->mask = ctx->lexer->token.mask;
801 lexer_get(ctx->lexer);
804 expr_syntax_error(ctx, "expecting constant.");
809 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
810 * which the caller need not have initialized. Returns true on success, in
811 * which case the caller owns 'cs', false on failure, in which case 'cs' is
814 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
816 size_t allocated_values = 0;
819 memset(cs, 0, sizeof *cs);
820 if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
822 cs->in_curlies = true;
824 if (!parse_constant(ctx, cs, &allocated_values)) {
828 lexer_match(ctx->lexer, LEX_T_COMMA);
829 } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
831 ok = parse_constant(ctx, cs, &allocated_values);
834 expr_constant_set_destroy(cs);
840 expr_constant_set_destroy(struct expr_constant_set *cs)
843 if (cs->type == EXPR_C_STRING) {
844 for (size_t i = 0; i < cs->n_values; i++) {
845 free(cs->values[i].string);
853 expr_parse_primary(struct expr_context *ctx, bool *atomic)
856 if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
857 struct expr *e = expr_parse__(ctx);
858 if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
860 expr_syntax_error(ctx, "expecting `)'.");
867 if (ctx->lexer->token.type == LEX_T_ID) {
870 struct expr_constant_set c;
872 if (!parse_field(ctx, &f)) {
876 if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
877 if (f.n_bits > 1 && !ctx->not) {
878 expr_error(ctx, "Explicit `!= 0' is required for inequality "
879 "test of multibit field against 0.");
885 union expr_constant *cst = xzalloc(sizeof *cst);
886 cst->format = LEX_F_HEXADECIMAL;
889 c.type = EXPR_C_INTEGER;
892 c.in_curlies = false;
893 return make_cmp(ctx, &f, EXPR_R_NE, &c);
894 } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
895 return make_cmp(ctx, &f, r, &c);
900 struct expr_constant_set c1;
901 if (!parse_constant_set(ctx, &c1)) {
905 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
907 && c1.type == EXPR_C_INTEGER
908 && c1.values[0].format == LEX_F_DECIMAL
909 && !c1.values[0].masked
911 uint64_t x = ntohll(c1.values[0].value.integer);
914 expr_constant_set_destroy(&c1);
915 return expr_create_boolean(x);
921 if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
922 expr_constant_set_destroy(&c1);
926 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
927 return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
931 struct expr_constant_set c2;
932 if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
933 expr_constant_set_destroy(&c1);
936 /* Reject "1 == field == 2", "1 < field > 2", and so on. */
937 if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
938 (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
939 ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
940 (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
941 expr_error(ctx, "Range expressions must have the form "
942 "`x < field < y' or `x > field > y', with each "
943 "`<' optionally replaced by `<=' or `>' by `>=').");
944 expr_constant_set_destroy(&c1);
945 expr_constant_set_destroy(&c2);
949 struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
950 struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
956 return expr_combine(EXPR_T_AND, e1, e2);
962 expr_parse_not(struct expr_context *ctx)
966 if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
967 ctx->not = !ctx->not;
968 struct expr *expr = expr_parse_primary(ctx, &atomic);
969 ctx->not = !ctx->not;
973 expr_error(ctx, "Missing parentheses around operand of !.");
981 return expr_parse_primary(ctx, &atomic);
986 expr_parse__(struct expr_context *ctx)
988 struct expr *e = expr_parse_not(ctx);
993 enum lex_type lex_type = ctx->lexer->token.type;
994 if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
995 enum expr_type expr_type
996 = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
998 lexer_get(ctx->lexer);
1000 struct expr *e2 = expr_parse_not(ctx);
1005 e = expr_combine(expr_type, e, e2);
1006 } while (lexer_match(ctx->lexer, lex_type));
1007 if (ctx->lexer->token.type == LEX_T_LOG_AND
1008 || ctx->lexer->token.type == LEX_T_LOG_OR) {
1011 "&& and || must be parenthesized when used together.");
1018 /* Parses an expression using the symbols in 'symtab' from 'lexer'. If
1019 * successful, returns the new expression and sets '*errorp' to NULL. On
1020 * failure, returns NULL and sets '*errorp' to an explanatory error message.
1021 * The caller must eventually free the returned expression (with
1022 * expr_destroy()) or error (with free()). */
1024 expr_parse(struct lexer *lexer, const struct shash *symtab, char **errorp)
1026 struct expr_context ctx;
1029 ctx.symtab = symtab;
1033 struct expr *e = expr_parse__(&ctx);
1034 *errorp = ctx.error;
1035 ovs_assert((ctx.error != NULL) != (e != NULL));
1039 /* Like expr_parse(), but the expression is taken from 's'. */
1041 expr_parse_string(const char *s, const struct shash *symtab, char **errorp)
1046 lexer_init(&lexer, s);
1048 expr = expr_parse(&lexer, symtab, errorp);
1049 if (!*errorp && lexer.token.type != LEX_T_END) {
1050 *errorp = xstrdup("Extra tokens at end of input.");
1054 lexer_destroy(&lexer);
1059 static struct expr_symbol *
1060 add_symbol(struct shash *symtab, const char *name, int width,
1061 const char *prereqs, enum expr_level level,
1062 bool must_crossproduct)
1064 struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1065 symbol->name = xstrdup(name);
1066 symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1067 symbol->width = width;
1068 symbol->level = level;
1069 symbol->must_crossproduct = must_crossproduct;
1070 shash_add_assert(symtab, symbol->name, symbol);
1074 /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1075 * 'name' is referenced, expression annotation (see expr_annotate()) will
1076 * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1077 * conversion to flows will never attempt to use the field as a conjunctive
1078 * match dimension (see "Crossproducting" in the large comment on struct
1079 * expr_symbol in expr.h for an example).
1081 * A given field 'id' must only be used for a single symbol in a symbol table.
1082 * Use subfields to duplicate or subset a field (you can even make a subfield
1083 * include all the bits of the "parent" field if you like). */
1084 struct expr_symbol *
1085 expr_symtab_add_field(struct shash *symtab, const char *name,
1086 enum mf_field_id id, const char *prereqs,
1087 bool must_crossproduct)
1089 const struct mf_field *field = mf_from_id(id);
1090 struct expr_symbol *symbol;
1092 symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1093 (field->maskable == MFM_FULLY
1097 symbol->field = field;
1102 parse_field_from_string(const char *s, const struct shash *symtab,
1103 struct expr_field *field, char **errorp)
1106 lexer_init(&lexer, s);
1109 struct expr_context ctx;
1111 ctx.symtab = symtab;
1115 bool ok = parse_field(&ctx, field);
1117 *errorp = ctx.error;
1118 } else if (lexer.token.type != LEX_T_END) {
1119 *errorp = xstrdup("Extra tokens at end of input.");
1123 lexer_destroy(&lexer);
1128 /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1129 * 'name' is referenced, expression annotation (see expr_annotate()) will
1130 * ensure that 'prereqs' are also true.
1132 * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1133 * for the low 12 bits of a larger field named "vlan.tci". */
1134 struct expr_symbol *
1135 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1136 const char *prereqs, const char *subfield)
1138 struct expr_symbol *symbol;
1139 struct expr_field f;
1142 if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1143 VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1148 enum expr_level level = f.symbol->level;
1149 if (level != EXPR_L_ORDINAL) {
1150 VLOG_WARN("can't define %s as subfield of %s field %s",
1151 name, expr_level_to_string(level), f.symbol->name);
1154 symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1155 symbol->expansion = xstrdup(subfield);
1159 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1161 struct expr_symbol *
1162 expr_symtab_add_string(struct shash *symtab, const char *name,
1163 enum mf_field_id id, const char *prereqs)
1165 const struct mf_field *field = mf_from_id(id);
1166 struct expr_symbol *symbol;
1168 symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1169 symbol->field = field;
1173 static enum expr_level
1174 expr_get_level(const struct expr *expr)
1176 const struct expr *sub;
1177 enum expr_level level = EXPR_L_ORDINAL;
1179 switch (expr->type) {
1181 return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1187 LIST_FOR_EACH (sub, node, &expr->andor) {
1188 enum expr_level sub_level = expr_get_level(sub);
1189 level = MIN(level, sub_level);
1193 case EXPR_T_BOOLEAN:
1194 return EXPR_L_BOOLEAN;
1201 static enum expr_level
1202 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1204 struct expr *expr = expr_parse_string(s, symtab, errorp);
1205 enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1210 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1211 * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 6" might be an
1212 * appropriate predicate named "tcp4". */
1213 struct expr_symbol *
1214 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1215 const char *expansion)
1217 struct expr_symbol *symbol;
1218 enum expr_level level;
1221 level = expr_parse_level(expansion, symtab, &error);
1223 VLOG_WARN("%s: error parsing %s expansion (%s)",
1224 expansion, name, error);
1229 symbol = add_symbol(symtab, name, 1, NULL, level, false);
1230 symbol->expansion = xstrdup(expansion);
1234 /* Destroys 'symtab' and all of its symbols. */
1236 expr_symtab_destroy(struct shash *symtab)
1238 struct shash_node *node, *next;
1240 SHASH_FOR_EACH_SAFE (node, next, symtab) {
1241 struct expr_symbol *symbol = node->data;
1243 shash_delete(symtab, node);
1245 free(symbol->prereqs);
1246 free(symbol->expansion);
1253 static struct expr *
1254 expr_clone_cmp(struct expr *expr)
1256 struct expr *new = xmemdup(expr, sizeof *expr);
1257 if (!new->cmp.symbol->width) {
1258 new->cmp.string = xstrdup(new->cmp.string);
1263 static struct expr *
1264 expr_clone_andor(struct expr *expr)
1266 struct expr *new = expr_create_andor(expr->type);
1269 LIST_FOR_EACH (sub, node, &expr->andor) {
1270 struct expr *new_sub = expr_clone(sub);
1271 list_push_back(&new->andor, &new_sub->node);
1276 /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1277 * expression nor any of its substructure will be shared with 'expr'. */
1279 expr_clone(struct expr *expr)
1281 switch (expr->type) {
1283 return expr_clone_cmp(expr);
1287 return expr_clone_andor(expr);
1289 case EXPR_T_BOOLEAN:
1290 return expr_create_boolean(expr->boolean);
1295 /* Destroys 'expr' and all of the sub-expressions it references. */
1297 expr_destroy(struct expr *expr)
1303 struct expr *sub, *next;
1305 switch (expr->type) {
1307 if (!expr->cmp.symbol->width) {
1308 free(expr->cmp.string);
1314 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1315 list_remove(&sub->node);
1320 case EXPR_T_BOOLEAN:
1328 /* An element in a linked list of symbols.
1330 * Used to detect when a symbol is being expanded recursively, to allow
1331 * flagging an error. */
1332 struct annotation_nesting {
1333 struct ovs_list node;
1334 const struct expr_symbol *symbol;
1337 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1338 struct ovs_list *nesting, char **errorp);
1340 static struct expr *
1341 parse_and_annotate(const char *s, const struct shash *symtab,
1342 struct ovs_list *nesting, char **errorp)
1347 expr = expr_parse_string(s, symtab, &error);
1349 expr = expr_annotate__(expr, symtab, nesting, &error);
1354 *errorp = xasprintf("Error parsing expression `%s' encountered as "
1355 "prerequisite or predicate of initial expression: "
1362 static struct expr *
1363 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1364 struct ovs_list *nesting, char **errorp)
1366 const struct expr_symbol *symbol = expr->cmp.symbol;
1367 const struct annotation_nesting *iter;
1368 LIST_FOR_EACH (iter, node, nesting) {
1369 if (iter->symbol == symbol) {
1370 *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1377 struct annotation_nesting an;
1379 list_push_back(nesting, &an.node);
1381 struct expr *prereqs = NULL;
1382 if (symbol->prereqs) {
1383 prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1389 if (symbol->expansion) {
1390 if (symbol->level == EXPR_L_ORDINAL) {
1391 struct expr_field field;
1393 if (!parse_field_from_string(symbol->expansion, symtab,
1398 expr->cmp.symbol = field.symbol;
1399 mf_subvalue_shift(&expr->cmp.value, field.ofs);
1400 mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1402 struct expr *expansion;
1404 expansion = parse_and_annotate(symbol->expansion, symtab,
1410 bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1411 positive ^= expr->cmp.relop == EXPR_R_NE;
1413 expr_not(expansion);
1421 list_remove(&an.node);
1422 return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1426 expr_destroy(prereqs);
1427 list_remove(&an.node);
1432 expr_annotate__(struct expr *expr, const struct shash *symtab,
1433 struct ovs_list *nesting, char **errorp)
1435 switch (expr->type) {
1437 return expr_annotate_cmp(expr, symtab, nesting, errorp);
1441 struct expr *sub, *next;
1443 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1444 list_remove(&sub->node);
1445 struct expr *new_sub = expr_annotate__(sub, symtab,
1451 expr_insert_andor(expr, next, new_sub);
1457 case EXPR_T_BOOLEAN:
1466 /* "Annotates" 'expr', which does the following:
1468 * - Applies prerequisites, by locating each comparison operator whose
1469 * field has a prerequisite and adding a logical AND against those
1472 * - Expands references to subfield symbols, by replacing them by
1473 * references to their underlying field symbols (suitably shifted).
1475 * - Expands references to predicate symbols, by replacing them by the
1476 * expressions that they expand to.
1478 * In each case, annotation occurs recursively as necessary.
1480 * On failure, returns NULL and sets '*errorp' to an explanatory error
1481 * message, which the caller must free. */
1483 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1485 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1486 return expr_annotate__(expr, symtab, &nesting, errorp);
1489 static struct expr *
1490 expr_simplify_ne(struct expr *expr)
1492 struct expr *new = NULL;
1493 const union mf_subvalue *value = &expr->cmp.value;
1494 const union mf_subvalue *mask = &expr->cmp.mask;
1495 int w = expr->cmp.symbol->width;
1498 for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1501 e = xzalloc(sizeof *e);
1502 e->type = EXPR_T_CMP;
1503 e->cmp.symbol = expr->cmp.symbol;
1504 e->cmp.relop = EXPR_R_EQ;
1505 bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1506 !bitwise_get_bit(value, sizeof *value, i));
1507 bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1509 new = expr_combine(EXPR_T_OR, new, e);
1518 static struct expr *
1519 expr_simplify_relational(struct expr *expr)
1521 const union mf_subvalue *value = &expr->cmp.value;
1522 int start, n_bits, end;
1524 find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1526 ovs_assert(n_bits > 0);
1527 end = start + n_bits;
1530 if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1531 new = xmemdup(expr, sizeof *expr);
1532 new->cmp.relop = EXPR_R_EQ;
1537 bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1538 for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1540 z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1543 e = xmemdup(expr, sizeof *expr);
1544 e->cmp.relop = EXPR_R_EQ;
1545 bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1546 bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1547 bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1548 new = expr_combine(EXPR_T_OR, new, e);
1551 return new ? new : expr_create_boolean(false);
1554 /* Takes ownership of 'expr' and returns an equivalent expression whose
1555 * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1557 expr_simplify(struct expr *expr)
1559 struct expr *sub, *next;
1561 switch (expr->type) {
1563 return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1564 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1565 : expr_simplify_relational(expr));
1569 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1570 list_remove(&sub->node);
1571 expr_insert_andor(expr, next, expr_simplify(sub));
1573 return expr_fix(expr);
1575 case EXPR_T_BOOLEAN:
1581 static const struct expr_symbol *
1582 expr_is_cmp(const struct expr *expr)
1584 switch (expr->type) {
1586 return expr->cmp.symbol;
1590 const struct expr_symbol *prev = NULL;
1593 LIST_FOR_EACH (sub, node, &expr->andor) {
1594 const struct expr_symbol *symbol = expr_is_cmp(sub);
1595 if (!symbol || (prev && symbol != prev)) {
1603 case EXPR_T_BOOLEAN:
1613 const struct expr_symbol *relop;
1614 enum expr_type type;
1618 compare_expr_sort(const void *a_, const void *b_)
1620 const struct expr_sort *a = a_;
1621 const struct expr_sort *b = b_;
1623 if (a->type != b->type) {
1624 return a->type < b->type ? -1 : 1;
1625 } else if (a->relop) {
1626 int cmp = strcmp(a->relop->name, b->relop->name);
1631 enum expr_type a_type = a->expr->type;
1632 enum expr_type b_type = a->expr->type;
1633 return a_type < b_type ? -1 : a_type > b_type;
1634 } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1635 size_t a_len = list_size(&a->expr->andor);
1636 size_t b_len = list_size(&b->expr->andor);
1637 return a_len < b_len ? -1 : a_len > b_len;
1643 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1646 disjunction_matches_string(const struct expr *or, const char *s)
1648 const struct expr *sub;
1650 LIST_FOR_EACH (sub, node, &or->andor) {
1651 if (!strcmp(sub->cmp.string, s)) {
1659 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1660 * string-typed 'symbol'. */
1661 static struct expr *
1662 crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1664 ovs_assert(!list_is_short(&expr->andor));
1666 struct expr *singleton = NULL;
1668 /* First crush each subexpression into either a single EXPR_T_CMP or an
1669 * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1670 struct expr *sub, *next = NULL;
1671 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1672 list_remove(&sub->node);
1673 struct expr *new = crush_cmps(sub, symbol);
1674 switch (new->type) {
1677 list_insert(&next->node, &new->node);
1680 bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1684 return expr_create_boolean(false);
1691 list_insert(&next->node, &new->node);
1693 case EXPR_T_BOOLEAN:
1694 if (!new->boolean) {
1703 /* If we have a singleton, then the result is either the singleton itself
1704 * (if the ORs allow the singleton) or false. */
1706 LIST_FOR_EACH (sub, node, &expr->andor) {
1707 if (sub->type == EXPR_T_OR
1708 && !disjunction_matches_string(sub, singleton->cmp.string)) {
1710 return expr_create_boolean(false);
1713 list_remove(&singleton->node);
1718 /* Otherwise the result is the intersection of all of the ORs. */
1719 struct sset result = SSET_INITIALIZER(&result);
1720 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1721 struct sset strings = SSET_INITIALIZER(&strings);
1722 const struct expr *s;
1723 LIST_FOR_EACH (s, node, &sub->andor) {
1724 sset_add(&strings, s->cmp.string);
1726 if (sset_is_empty(&result)) {
1727 sset_swap(&result, &strings);
1729 sset_intersect(&result, &strings);
1731 sset_destroy(&strings);
1733 if (sset_is_empty(&result)) {
1735 sset_destroy(&result);
1736 return expr_create_boolean(false);
1741 expr = expr_create_andor(EXPR_T_OR);
1744 SSET_FOR_EACH (string, &result) {
1745 sub = xmalloc(sizeof *sub);
1746 sub->type = EXPR_T_CMP;
1747 sub->cmp.symbol = symbol;
1748 sub->cmp.string = xstrdup(string);
1749 list_push_back(&expr->andor, &sub->node);
1751 return expr_fix(expr);
1754 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1755 * numeric-typed 'symbol'. */
1756 static struct expr *
1757 crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1759 ovs_assert(!list_is_short(&expr->andor));
1761 union mf_subvalue value, mask;
1762 memset(&value, 0, sizeof value);
1763 memset(&mask, 0, sizeof mask);
1765 struct expr *sub, *next = NULL;
1766 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1767 list_remove(&sub->node);
1768 struct expr *new = crush_cmps(sub, symbol);
1769 switch (new->type) {
1771 if (!mf_subvalue_intersect(&value, &mask,
1772 &new->cmp.value, &new->cmp.mask,
1776 return expr_create_boolean(false);
1783 list_insert(&next->node, &new->node);
1785 case EXPR_T_BOOLEAN:
1786 if (!new->boolean) {
1794 if (list_is_empty(&expr->andor)) {
1795 if (is_all_zeros(&mask, sizeof mask)) {
1797 return expr_create_boolean(true);
1800 cmp = xmalloc(sizeof *cmp);
1801 cmp->type = EXPR_T_CMP;
1802 cmp->cmp.symbol = symbol;
1803 cmp->cmp.relop = EXPR_R_EQ;
1804 cmp->cmp.value = value;
1805 cmp->cmp.mask = mask;
1809 } else if (list_is_short(&expr->andor)) {
1810 /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1811 * computed as "a && b", etc. */
1812 struct expr *disjuncts = expr_from_node(list_pop_front(&expr->andor));
1815 or = xmalloc(sizeof *or);
1816 or->type = EXPR_T_OR;
1817 list_init(&or->andor);
1819 ovs_assert(disjuncts->type == EXPR_T_OR);
1820 LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1821 ovs_assert(sub->type == EXPR_T_CMP);
1822 list_remove(&sub->node);
1823 if (mf_subvalue_intersect(&value, &mask,
1824 &sub->cmp.value, &sub->cmp.mask,
1825 &sub->cmp.value, &sub->cmp.mask)) {
1826 list_push_back(&or->andor, &sub->node);
1833 if (list_is_empty(&or->andor)) {
1835 return expr_create_boolean(false);
1836 } else if (list_is_short(&or->andor)) {
1837 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1844 /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1845 * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1846 struct expr *as = expr_from_node(list_pop_front(&expr->andor));
1847 struct expr *bs = expr_from_node(list_pop_front(&expr->andor));
1848 struct expr *new = NULL;
1851 or = xmalloc(sizeof *or);
1852 or->type = EXPR_T_OR;
1853 list_init(&or->andor);
1856 LIST_FOR_EACH (a, node, &as->andor) {
1857 union mf_subvalue a_value, a_mask;
1859 ovs_assert(a->type == EXPR_T_CMP);
1860 if (!mf_subvalue_intersect(&value, &mask,
1861 &a->cmp.value, &a->cmp.mask,
1862 &a_value, &a_mask)) {
1867 LIST_FOR_EACH (b, node, &bs->andor) {
1868 ovs_assert(b->type == EXPR_T_CMP);
1870 new = xmalloc(sizeof *new);
1871 new->type = EXPR_T_CMP;
1872 new->cmp.symbol = symbol;
1873 new->cmp.relop = EXPR_R_EQ;
1875 if (mf_subvalue_intersect(&a_value, &a_mask,
1876 &b->cmp.value, &b->cmp.mask,
1877 &new->cmp.value, &new->cmp.mask)) {
1878 list_push_back(&or->andor, &new->node);
1887 if (list_is_empty(&or->andor)) {
1890 return expr_create_boolean(false);
1891 } else if (list_is_short(&or->andor)) {
1892 struct expr *cmp = expr_from_node(list_pop_front(&or->andor));
1894 if (list_is_empty(&expr->andor)) {
1896 return crush_cmps(cmp, symbol);
1898 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1900 } else if (!list_is_empty(&expr->andor)) {
1901 struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1902 ovs_assert(!list_is_short(&e->andor));
1903 return crush_cmps(e, symbol);
1906 return crush_cmps(or, symbol);
1912 compare_cmps_3way(const struct expr *a, const struct expr *b)
1914 ovs_assert(a->cmp.symbol == b->cmp.symbol);
1915 if (!a->cmp.symbol->width) {
1916 return strcmp(a->cmp.string, b->cmp.string);
1918 int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1920 d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1927 compare_cmps_cb(const void *a_, const void *b_)
1929 const struct expr *const *ap = a_;
1930 const struct expr *const *bp = b_;
1931 const struct expr *a = *ap;
1932 const struct expr *b = *bp;
1933 return compare_cmps_3way(a, b);
1936 /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
1937 static struct expr *
1938 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1940 struct expr *sub, *next = NULL;
1942 /* First, crush all the subexpressions. That might eliminate the
1943 * OR-expression entirely; if so, return the result. Otherwise, 'expr'
1944 * is now a disjunction of cmps over the same symbol. */
1945 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1946 list_remove(&sub->node);
1947 expr_insert_andor(expr, next, crush_cmps(sub, symbol));
1949 expr = expr_fix(expr);
1950 if (expr->type != EXPR_T_OR) {
1954 /* Sort subexpressions by value and mask, to bring together duplicates. */
1955 size_t n = list_size(&expr->andor);
1956 struct expr **subs = xmalloc(n * sizeof *subs);
1959 LIST_FOR_EACH (sub, node, &expr->andor) {
1964 qsort(subs, n, sizeof *subs, compare_cmps_cb);
1966 /* Eliminate duplicates. */
1967 list_init(&expr->andor);
1968 list_push_back(&expr->andor, &subs[0]->node);
1969 for (i = 1; i < n; i++) {
1970 struct expr *a = expr_from_node(list_back(&expr->andor));
1971 struct expr *b = subs[i];
1972 if (compare_cmps_3way(a, b)) {
1973 list_push_back(&expr->andor, &b->node);
1979 return expr_fix(expr);
1982 /* Takes ownership of 'expr', which must be a cmp in the sense determined by
1983 * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
1984 * Returns an equivalent expression owned by the caller that is a single
1985 * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
1986 static struct expr *
1987 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
1989 switch (expr->type) {
1991 return crush_or(expr, symbol);
1994 return (symbol->width
1995 ? crush_and_numeric(expr, symbol)
1996 : crush_and_string(expr, symbol));
2001 case EXPR_T_BOOLEAN:
2009 static struct expr *
2010 expr_sort(struct expr *expr)
2012 size_t n = list_size(&expr->andor);
2013 struct expr_sort *subs = xmalloc(n * sizeof *subs);
2018 LIST_FOR_EACH (sub, node, &expr->andor) {
2020 subs[i].relop = expr_is_cmp(sub);
2021 subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2026 qsort(subs, n, sizeof *subs, compare_expr_sort);
2028 list_init(&expr->andor);
2029 for (int i = 0; i < n; ) {
2030 if (subs[i].relop) {
2032 for (j = i + 1; j < n; j++) {
2033 if (subs[i].relop != subs[j].relop) {
2038 struct expr *crushed;
2040 crushed = crush_cmps(subs[i].expr, subs[i].relop);
2042 struct expr *combined = subs[i].expr;
2043 for (int k = i + 1; k < j; k++) {
2044 combined = expr_combine(EXPR_T_AND, combined,
2047 ovs_assert(!list_is_short(&combined->andor));
2048 crushed = crush_cmps(combined, subs[i].relop);
2050 if (crushed->type == EXPR_T_BOOLEAN) {
2051 if (!crushed->boolean) {
2052 for (int k = j; k < n; k++) {
2053 expr_destroy(subs[k].expr);
2062 expr = expr_combine(EXPR_T_AND, expr, crushed);
2066 expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2074 static struct expr *expr_normalize_or(struct expr *expr);
2076 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2077 * a clause is a cmp or a disjunction of cmps on a single field. */
2078 static struct expr *
2079 expr_normalize_and(struct expr *expr)
2081 ovs_assert(expr->type == EXPR_T_AND);
2083 expr = expr_sort(expr);
2084 if (expr->type != EXPR_T_AND) {
2085 ovs_assert(expr->type == EXPR_T_BOOLEAN);
2090 LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2091 if (&b->node == &expr->andor
2092 || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2093 || a->cmp.symbol != b->cmp.symbol) {
2095 } else if (a->cmp.symbol->width
2096 ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2097 &b->cmp.value, &b->cmp.mask,
2098 &b->cmp.value, &b->cmp.mask)
2099 : !strcmp(a->cmp.string, b->cmp.string)) {
2100 list_remove(&a->node);
2104 return expr_create_boolean(false);
2107 if (list_is_short(&expr->andor)) {
2108 struct expr *sub = expr_from_node(list_front(&expr->andor));
2114 LIST_FOR_EACH (sub, node, &expr->andor) {
2115 if (sub->type == EXPR_T_CMP) {
2119 ovs_assert(sub->type == EXPR_T_OR);
2120 const struct expr_symbol *symbol = expr_is_cmp(sub);
2121 if (!symbol || symbol->must_crossproduct) {
2122 struct expr *or = expr_create_andor(EXPR_T_OR);
2125 LIST_FOR_EACH (k, node, &sub->andor) {
2126 struct expr *and = expr_create_andor(EXPR_T_AND);
2129 LIST_FOR_EACH (m, node, &expr->andor) {
2130 struct expr *term = m == sub ? k : m;
2131 if (term->type == EXPR_T_AND) {
2134 LIST_FOR_EACH (p, node, &term->andor) {
2135 struct expr *new = expr_clone(p);
2136 list_push_back(&and->andor, &new->node);
2139 struct expr *new = expr_clone(term);
2140 list_push_back(&and->andor, &new->node);
2143 list_push_back(&or->andor, &and->node);
2146 return expr_normalize_or(or);
2152 static struct expr *
2153 expr_normalize_or(struct expr *expr)
2155 struct expr *sub, *next;
2157 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2158 if (sub->type == EXPR_T_AND) {
2159 list_remove(&sub->node);
2161 struct expr *new = expr_normalize_and(sub);
2162 if (new->type == EXPR_T_BOOLEAN) {
2169 expr_insert_andor(expr, next, new);
2172 ovs_assert(sub->type == EXPR_T_CMP);
2175 if (list_is_empty(&expr->andor)) {
2177 return expr_create_boolean(false);
2179 if (list_is_short(&expr->andor)) {
2180 struct expr *sub = expr_from_node(list_pop_front(&expr->andor));
2188 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2189 * an expression in terms of only relationals, AND, and OR. Returns either a
2190 * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2191 * clause is a cmp or a disjunction of cmps on a single field. This form is
2192 * significant because it is a form that can be directly converted to OpenFlow
2193 * flows with the Open vSwitch "conjunctive match" extension.
2195 * 'expr' must already have been simplified, with expr_simplify(). */
2197 expr_normalize(struct expr *expr)
2199 switch (expr->type) {
2204 return expr_normalize_and(expr);
2207 return expr_normalize_or(expr);
2209 case EXPR_T_BOOLEAN:
2215 /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2216 * nonnull then it is copied into the new expr_match, otherwise the new
2217 * expr_match's 'match' member is initialized to a catch-all match for the
2218 * caller to refine in-place.
2220 * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2221 * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2222 * expr_match will not have any conjunctions.
2224 * The caller should use expr_match_add() to add the expr_match to a hash table
2225 * after it is finalized. */
2226 static struct expr_match *
2227 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2230 struct expr_match *match = xmalloc(sizeof *match);
2234 match_init_catchall(&match->match);
2237 match->conjunctions = xmalloc(sizeof *match->conjunctions);
2238 match->conjunctions[0].id = conj_id;
2239 match->conjunctions[0].clause = clause;
2240 match->conjunctions[0].n_clauses = n_clauses;
2242 match->allocated = 1;
2244 match->conjunctions = NULL;
2246 match->allocated = 0;
2251 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2254 * This might actually destroy 'match' because it gets merged together with
2255 * some existing conjunction.*/
2257 expr_match_add(struct hmap *matches, struct expr_match *match)
2259 uint32_t hash = match_hash(&match->match, 0);
2260 struct expr_match *m;
2262 HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2263 if (match_equal(&m->match, &match->match)) {
2264 if (!m->n || !match->n) {
2265 free(m->conjunctions);
2266 m->conjunctions = NULL;
2270 ovs_assert(match->n == 1);
2271 if (m->n >= m->allocated) {
2272 m->conjunctions = x2nrealloc(m->conjunctions,
2274 sizeof *m->conjunctions);
2276 m->conjunctions[m->n++] = match->conjunctions[0];
2278 free(match->conjunctions);
2284 hmap_insert(matches, &match->hmap_node, hash);
2288 constrain_match(const struct expr *expr, const struct simap *ports,
2291 ovs_assert(expr->type == EXPR_T_CMP);
2292 if (expr->cmp.symbol->width) {
2293 mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2294 &expr->cmp.mask, m);
2296 const struct simap_node *node;
2297 node = ports ? simap_find(ports, expr->cmp.string) : NULL;
2302 struct mf_subfield sf;
2303 sf.field = expr->cmp.symbol->field;
2305 sf.n_bits = expr->cmp.symbol->field->n_bits;
2307 union mf_subvalue x;
2308 memset(&x, 0, sizeof x);
2309 x.integer = htonll(node->data);
2311 mf_write_subfield(&sf, &x, m);
2317 add_disjunction(const struct expr *or, const struct simap *ports,
2318 struct match *m, uint8_t clause, uint8_t n_clauses,
2319 uint32_t conj_id, struct hmap *matches)
2324 ovs_assert(or->type == EXPR_T_OR);
2325 LIST_FOR_EACH (sub, node, &or->andor) {
2326 struct expr_match *match = expr_match_new(m, clause, n_clauses,
2328 if (constrain_match(sub, ports, &match->match)) {
2329 expr_match_add(matches, match);
2332 free(match->conjunctions);
2337 /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2338 * that shouldn't happen much. */
2343 add_conjunction(const struct expr *and, const struct simap *ports,
2344 uint32_t *n_conjsp, struct hmap *matches)
2350 match_init_catchall(&match);
2352 ovs_assert(and->type == EXPR_T_AND);
2353 LIST_FOR_EACH (sub, node, &and->andor) {
2354 switch (sub->type) {
2356 if (!constrain_match(sub, ports, &match)) {
2364 case EXPR_T_BOOLEAN:
2370 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2371 } else if (n_clauses == 1) {
2372 LIST_FOR_EACH (sub, node, &and->andor) {
2373 if (sub->type == EXPR_T_OR) {
2374 add_disjunction(sub, ports, &match, 0, 0, 0, matches);
2380 LIST_FOR_EACH (sub, node, &and->andor) {
2381 if (sub->type == EXPR_T_OR) {
2382 if (!add_disjunction(sub, ports, &match, clause++,
2383 n_clauses, *n_conjsp, matches)) {
2384 /* This clause can't ever match, so we might as well skip
2385 * adding the other clauses--the overall disjunctive flow
2386 * can't ever match. Ideally we would also back out all of
2387 * the clauses we already added, but that seems like a lot
2388 * of trouble for a case that might never occur in
2395 /* Add the flow that matches on conj_id. */
2396 match_set_conj_id(&match, *n_conjsp);
2397 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2402 add_cmp_flow(const struct expr *cmp, const struct simap *ports,
2403 struct hmap *matches)
2405 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2406 if (constrain_match(cmp, ports, &m->match)) {
2407 expr_match_add(matches, m);
2413 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2414 * a collection of Open vSwitch flows in 'matches', which this function
2415 * initializes to an hmap of "struct expr_match" structures. Returns the
2416 * number of conjunctive match IDs consumed by 'matches', which uses
2417 * conjunctive match IDs beginning with 0; the caller must offset or remap them
2418 * into the desired range as necessary.
2420 * The matches inserted into 'matches' will be of three distinct kinds:
2422 * - Ordinary flows. The caller should add these OpenFlow flows with
2423 * its desired actions.
2425 * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2426 * structure. The caller should add these OpenFlow flows with the
2427 * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2428 * remapping the ids.
2430 * - conj_id flows, distinguished by matching on the "conj_id" field. The
2431 * caller should remap the conj_id and add the OpenFlow flow with its
2434 * 'ports' must be a map from strings (presumably names of ports) to integers.
2435 * Any comparisons against string fields in 'expr' are translated into integers
2436 * through this map. A comparison against a string that is not in 'ports' acts
2437 * like a Boolean "false"; that is, it will always fail to match. For a simple
2438 * expression, this means that the overall expression always fails to match,
2439 * but an expression with a disjunction on the string field might still match
2440 * on other port names.
2442 * (This treatment of string fields might be too simplistic in general, but it
2443 * seems reasonable for now when string fields are used only for ports.) */
2445 expr_to_matches(const struct expr *expr, const struct simap *ports,
2446 struct hmap *matches)
2448 uint32_t n_conjs = 0;
2451 switch (expr->type) {
2453 add_cmp_flow(expr, ports, matches);
2457 add_conjunction(expr, ports, &n_conjs, matches);
2461 if (expr_is_cmp(expr)) {
2464 LIST_FOR_EACH (sub, node, &expr->andor) {
2465 add_cmp_flow(sub, ports, matches);
2470 LIST_FOR_EACH (sub, node, &expr->andor) {
2471 if (sub->type == EXPR_T_AND) {
2472 add_conjunction(sub, ports, &n_conjs, matches);
2474 add_cmp_flow(sub, ports, matches);
2480 case EXPR_T_BOOLEAN:
2481 if (expr->boolean) {
2482 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2483 expr_match_add(matches, m);
2492 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2493 * 'matches' hmap itself. */
2495 expr_matches_destroy(struct hmap *matches)
2497 struct expr_match *m, *n;
2499 HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) {
2500 hmap_remove(matches, &m->hmap_node);
2501 free(m->conjunctions);
2504 hmap_destroy(matches);
2507 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2510 expr_matches_print(const struct hmap *matches, FILE *stream)
2512 if (hmap_is_empty(matches)) {
2513 fputs("(no flows)\n", stream);
2517 const struct expr_match *m;
2518 HMAP_FOR_EACH (m, hmap_node, matches) {
2519 char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2524 for (int i = 0; i < m->n; i++) {
2525 const struct cls_conjunction *c = &m->conjunctions[i];
2526 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2527 i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2534 /* Returns true if 'expr' honors the invariants for expressions (see the large
2535 * comment above "struct expr" in expr.h), false otherwise. */
2537 expr_honors_invariants(const struct expr *expr)
2539 const struct expr *sub;
2541 switch (expr->type) {
2543 if (expr->cmp.symbol->width) {
2544 for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2545 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2554 if (list_is_short(&expr->andor)) {
2557 LIST_FOR_EACH (sub, node, &expr->andor) {
2558 if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2564 case EXPR_T_BOOLEAN:
2573 expr_is_normalized_and(const struct expr *expr)
2575 /* XXX should also check that no symbol is repeated. */
2576 const struct expr *sub;
2578 LIST_FOR_EACH (sub, node, &expr->andor) {
2579 if (!expr_is_cmp(sub)) {
2586 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2589 expr_is_normalized(const struct expr *expr)
2591 switch (expr->type) {
2596 return expr_is_normalized_and(expr);
2599 if (!expr_is_cmp(expr)) {
2600 const struct expr *sub;
2602 LIST_FOR_EACH (sub, node, &expr->andor) {
2603 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2610 case EXPR_T_BOOLEAN:
2618 /* Action parsing helper. */
2620 /* Expands 'f' repeatedly as long as it has an expansion, that is, as long as
2621 * it is a subfield or a predicate. Adds any prerequisites for 'f' to
2624 * If 'rw', verifies that 'f' is a read/write field.
2626 * 'exchange' should be true if an exchange action is being parsed. This is
2627 * only used to improve error message phrasing.
2629 * Returns true if successful, false if an error was encountered (in which case
2630 * 'ctx->error' reports the particular error). */
2632 expand_symbol(struct expr_context *ctx, bool rw, bool exchange,
2633 struct expr_field *f, struct expr **prereqsp)
2635 const struct expr_symbol *orig_symbol = f->symbol;
2637 if (f->symbol->expansion && f->symbol->level != EXPR_L_ORDINAL) {
2638 expr_error(ctx, "Predicate symbol %s cannot be used in %s.",
2639 f->symbol->name, exchange ? "exchange" : "assignment");
2644 /* Accumulate prerequisites. */
2645 if (f->symbol->prereqs) {
2646 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2649 e = parse_and_annotate(f->symbol->prereqs, ctx->symtab, &nesting,
2652 expr_error(ctx, "%s", error);
2656 *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
2659 /* If there's no expansion, we're done. */
2660 if (!f->symbol->expansion) {
2665 struct expr_field expansion;
2667 if (!parse_field_from_string(f->symbol->expansion, ctx->symtab,
2668 &expansion, &error)) {
2669 expr_error(ctx, "%s", error);
2673 f->symbol = expansion.symbol;
2674 f->ofs += expansion.ofs;
2677 if (rw && !f->symbol->field->writable) {
2678 expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2686 mf_subfield_from_expr_field(const struct expr_field *f, struct mf_subfield *sf)
2688 sf->field = f->symbol->field;
2690 sf->n_bits = f->n_bits ? f->n_bits : f->symbol->field->n_bits;
2694 init_stack_action(const struct expr_field *f, struct ofpact_stack *stack)
2696 mf_subfield_from_expr_field(f, &stack->subfield);
2699 static struct expr *
2700 parse_assignment(struct expr_context *ctx, const struct simap *ports,
2701 struct ofpbuf *ofpacts)
2703 struct expr *prereqs = NULL;
2705 /* Parse destination and do basic checking. */
2706 struct expr_field dst;
2707 if (!parse_field(ctx, &dst)) {
2710 bool exchange = lexer_match(ctx->lexer, LEX_T_EXCHANGE);
2711 if (!exchange && !lexer_match(ctx->lexer, LEX_T_EQUALS)) {
2712 expr_syntax_error(ctx, "expecting `='.");
2715 const struct expr_symbol *orig_dst = dst.symbol;
2716 if (!expand_symbol(ctx, true, exchange, &dst, &prereqs)) {
2720 if (exchange || ctx->lexer->token.type == LEX_T_ID) {
2721 struct expr_field src;
2722 if (!parse_field(ctx, &src)) {
2725 const struct expr_symbol *orig_src = src.symbol;
2726 if (!expand_symbol(ctx, exchange, exchange, &src, &prereqs)) {
2730 if ((dst.symbol->width != 0) != (src.symbol->width != 0)) {
2733 "Can't exchange %s field (%s) with %s field (%s).",
2734 orig_dst->width ? "integer" : "string",
2736 orig_src->width ? "integer" : "string",
2739 expr_error(ctx, "Can't assign %s field (%s) to %s field (%s).",
2740 orig_src->width ? "integer" : "string",
2742 orig_dst->width ? "integer" : "string",
2748 if (dst.n_bits != src.n_bits) {
2751 "Can't exchange %d-bit field with %d-bit field.",
2752 dst.n_bits, src.n_bits);
2755 "Can't assign %d-bit value to %d-bit destination.",
2756 src.n_bits, dst.n_bits);
2759 } else if (!dst.n_bits
2760 && dst.symbol->field->n_bits != src.symbol->field->n_bits) {
2761 expr_error(ctx, "String fields %s and %s are incompatible for "
2762 "%s.", orig_dst->name, orig_src->name,
2763 exchange ? "exchange" : "assignment");
2768 init_stack_action(&src, ofpact_put_STACK_PUSH(ofpacts));
2769 init_stack_action(&dst, ofpact_put_STACK_PUSH(ofpacts));
2770 init_stack_action(&src, ofpact_put_STACK_POP(ofpacts));
2771 init_stack_action(&dst, ofpact_put_STACK_POP(ofpacts));
2773 struct ofpact_reg_move *move = ofpact_put_REG_MOVE(ofpacts);
2774 mf_subfield_from_expr_field(&src, &move->src);
2775 mf_subfield_from_expr_field(&dst, &move->dst);
2778 struct expr_constant_set cs;
2779 if (!parse_constant_set(ctx, &cs)) {
2783 if (!type_check(ctx, &dst, &cs)) {
2784 goto exit_destroy_cs;
2786 if (cs.in_curlies) {
2787 expr_error(ctx, "Assignments require a single value.");
2788 goto exit_destroy_cs;
2791 union expr_constant *c = cs.values;
2792 struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2793 sf->field = dst.symbol->field;
2794 if (dst.symbol->width) {
2795 mf_subvalue_shift(&c->value, dst.ofs);
2797 memset(&c->mask, 0, sizeof c->mask);
2798 bitwise_one(&c->mask, sizeof c->mask, dst.ofs, dst.n_bits);
2800 mf_subvalue_shift(&c->mask, dst.ofs);
2804 &c->value.u8[sizeof c->value - sf->field->n_bytes],
2805 sf->field->n_bytes);
2807 &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2808 sf->field->n_bytes);
2810 uint32_t port = simap_get(ports, c->string);
2811 bitwise_put(port, &sf->value,
2812 sf->field->n_bytes, 0, sf->field->n_bits);
2813 bitwise_put(UINT64_MAX, &sf->mask,
2814 sf->field->n_bytes, 0, sf->field->n_bits);
2818 expr_constant_set_destroy(&cs);
2825 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2826 * "field = value" or "field1 = field2", or a "exchange" action in the form
2827 * "field1 <-> field2", into 'ofpacts'. The parameters and return value match
2828 * those for actions_parse(). */
2830 expr_parse_assignment(struct lexer *lexer, const struct shash *symtab,
2831 const struct simap *ports,
2832 struct ofpbuf *ofpacts, struct expr **prereqsp)
2834 struct expr_context ctx;
2836 ctx.symtab = symtab;
2840 struct expr *prereqs = parse_assignment(&ctx, ports, ofpacts);
2842 expr_destroy(prereqs);
2845 *prereqsp = prereqs;