From 75134cf3ae88e778b31ee099697bfa85b5e88c1b Mon Sep 17 00:00:00 2001
From: Vsevolod Stakhov <vsevolod@highsecure.ru>
Date: Thu, 26 Mar 2015 16:34:36 +0000
Subject: [PATCH] Implement AST nodes branch sorting.

---
 src/libutil/expression.c | 72 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 72 insertions(+)

diff --git a/src/libutil/expression.c b/src/libutil/expression.c
index a72c3d6d1..48888e669 100644
--- a/src/libutil/expression.c
+++ b/src/libutil/expression.c
@@ -26,6 +26,7 @@
 #include "expression.h"
 #include "printf.h"
 #include "regexp.h"
+#include "utlist.h"
 
 #define RSPAMD_EXPR_FLAG_NEGATE (1 << 0)
 #define RSPAMD_EXPR_FLAG_PROCESSED (1 << 1)
@@ -62,6 +63,7 @@ struct rspamd_expression_elt {
 	} p;
 	gint flags;
 	gint value;
+	gint priority;
 };
 
 struct rspamd_expression {
@@ -367,6 +369,68 @@ rspamd_ast_add_node (GArray *operands, struct rspamd_expression_elt *op)
 	rspamd_expr_stack_elt_push (operands, res);
 }
 
+static gboolean
+rspamd_ast_priority_traverse (GNode *node, gpointer d)
+{
+	struct rspamd_expression_elt *elt = node->data, *cur_elt;
+	struct rspamd_expression *expr = d;
+	gint cnt = 0;
+	GNode *cur;
+
+	if (node->children) {
+		cur = node->children;
+		while (cur) {
+			cur_elt = cur->data;
+			cnt += cur_elt->priority;
+			cur = cur->next;
+		}
+	}
+	else {
+		/* It is atom or limit */
+		g_assert (elt->type != ELT_OP);
+
+		if (elt->type == ELT_LIMIT) {
+			/* Always push limit first */
+			elt->priority = G_MAXINT;
+		}
+		else {
+			elt->priority = 0;
+
+			if (expr->subr->priority != NULL) {
+				elt->priority = expr->subr->priority (elt->p.atom);
+			}
+		}
+	}
+
+	elt->priority = cnt;
+
+	return FALSE;
+}
+
+static gint
+rspamd_ast_priority_cmp (GNode *a, GNode *b)
+{
+	struct rspamd_expression_elt *ea = a->data, *eb = b->data;
+
+	return ea->priority - eb->priority;
+}
+
+static gboolean
+rspamd_ast_resort_traverse (GNode *node, gpointer unused)
+{
+	GNode *cur;
+
+	cur = node->children;
+
+	if (cur) {
+		DL_SORT (cur, rspamd_ast_priority_cmp);
+	}
+
+	node->children = cur;
+
+	return FALSE;
+}
+
 gboolean
 rspamd_parse_expression (const gchar *line, gsize len,
 		const struct rspamd_atom_subr *subr, gpointer subr_data,
@@ -615,6 +679,14 @@ rspamd_parse_expression (const gchar *line, gsize len,
 	e->ast = rspamd_expr_stack_elt_pop (operand_stack);
 	g_array_free (operand_stack, TRUE);
 
+	/* Set priorities for branches */
+	g_node_traverse (e->ast, G_POST_ORDER, G_TRAVERSE_ALL, -1,
+			rspamd_ast_priority_traverse, e);
+
+	/* Now set less expensive branches to be evaluated first */
+	g_node_traverse (e->ast, G_POST_ORDER, G_TRAVERSE_NON_LEAVES, -1,
+			rspamd_ast_resort_traverse, NULL);
+
 	if (target) {
 		*target = e;
 		rspamd_mempool_add_destructor (pool,
-- 
2.39.5