[ovs-dev] [PATCH] Factor prerequisites out of AND/OR trees with unique symbol

[Ben Pfaff]

On Thu, Apr 26, 2018 at 09:54:06PM +0200, Jakub Sitnicki wrote:
> Appending prerequisites to sub-expressions of OR that are all over one
> symbol prevents the expression-to-matches converter from applying
> conjunctive matching. This happens during the annotation phase.
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
>             ((p2 && s2 == c3) || (p2 && s2 == c4))
> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
>             (p1 && p2 && s1 == c1 && s2 == c4) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c3) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c4)
> 
> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> 
> Since sub-expressions of OR trees that are over one symbol all have the
> same prerequisites, we can factor them out leaving the OR tree in tact,
> and enabling the converter to apply conjunctive matching to
> AND(OR(clause)) trees.
> 
> Going back to our example this change gives us:
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> 
> We also factor out the prerequisites out of pure AND or mixed AND/OR
> trees to keep the common code path, but in this case we don't gain
> anything.
> 
> Signed-off-by: Jakub Sitnicki <jkbs at redhat.com>

This is nice.  Thank you.

I suggest folding in the following to better document and to better
match usual OVS style:

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 9dd8d6f17abe..bac8e1efd53f 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -32,13 +32,10 @@
 
 VLOG_DEFINE_THIS_MODULE(expr);
 
-static const struct expr_symbol *
-expr_get_unique_symbol(const struct expr *expr);
-
-struct expr *
-expr_annotate__(struct expr *expr, const struct shash *symtab,
-                bool append_prereqs, struct ovs_list *nesting, char **errorp);
-
+static const struct expr_symbol *expr_get_unique_symbol(const struct expr *);
+struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
+                             bool append_prereqs, struct ovs_list *nesting,
+                             char **errorp);
 static struct expr *parse_and_annotate(const char *s,
                                        const struct shash *symtab,
                                        struct ovs_list *nesting,
@@ -1771,6 +1768,15 @@ error:
     return NULL;
 }
 
+/* Same interface and purpose as expr_annotate(), with a couple of additional
+ * parameters for internal bookkeeping.
+ *
+ * Uses 'nesting' to ensure that a given symbol is not recursively expanded.
+ *
+ * Ordinarily, annotation adds prerequisites to the expression, and that's what
+ * this function does if 'append_prereqs' is true.  If 'append_prereqs' is
+ * false, this function ignores prerequisites (in which case the caller must
+ * have arranged to deal with them). */
 struct expr *
 expr_annotate__(struct expr *expr, const struct shash *symtab,
                 bool append_prereqs, struct ovs_list *nesting, char **errorp)

I also wonder about the following, because it seems like currently the
append_prereqs parameter is only being honored for a single level of
AND/OR, not when expr_annotate__() recurses:

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 9dd8d6f17abe..a33b4eb46933 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -1782,12 +1788,25 @@ expr_annotate__(struct expr *expr, const struct shash *symtab,
 
     case EXPR_T_AND:
     case EXPR_T_OR: {
-        const struct expr_symbol *unique_symbol = expr_get_unique_symbol(expr);
+        /* Detect whether every term in 'expr' mentions the same symbol.  If
+         * so, then suppress prerequisites for that symbol for those terms and
+         * instead apply them once at our higher level.
+         *
+         * If 'append_prereqs' is true, though, we're not supposed to handle
+         * prereqs at all (because our caller is already doing it). */
+        const struct expr_symbol *unique_symbol = NULL;
+        if (!append_prereqs) {
+            unique_symbol = expr_get_unique_symbol(expr);
+            if (unique_symbol) {
+                append_prereqs = false;
+            }
+        }
+
         struct expr *sub, *next;
 
         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
             ovs_list_remove(&sub->node);
-            struct expr *new_sub = expr_annotate__(sub, symtab, !unique_symbol,
+            struct expr *new_sub = expr_annotate__(sub, symtab, append_prereqs,
                                                    nesting, errorp);
             if (!new_sub) {
                 expr_destroy(expr);

However this patch, while it seems reasonable, causes some test failures
due to the difference that it produces and I'm not sure whether the new
results are actually superior to the old ones.