Short circuit boolean expressions

Short circuit boolean expressions by converting them
to (nested) if expressions. This also fixes a bug in
Java expression evaluation where evaluation of arithmetic
operations with the same precedence would be from right
to left rather than left to right.

4 files changed, 166 insertions, 3 deletions

diff --git a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java
new file mode 100644
index 00000000000..336156a11bd
--- /dev/null
+++ b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformer.java
@@ -0,0 +1,105 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.schema.expressiontransforms;
+
+import com.yahoo.searchlib.rankingexpression.evaluation.BooleanValue;
+import com.yahoo.searchlib.rankingexpression.rule.ArithmeticNode;
+import com.yahoo.searchlib.rankingexpression.rule.ArithmeticOperator;
+import com.yahoo.searchlib.rankingexpression.rule.CompositeNode;
+import com.yahoo.searchlib.rankingexpression.rule.ConstantNode;
+import com.yahoo.searchlib.rankingexpression.rule.ExpressionNode;
+import com.yahoo.searchlib.rankingexpression.rule.IfNode;
+import com.yahoo.searchlib.rankingexpression.transform.ExpressionTransformer;
+import com.yahoo.searchlib.rankingexpression.transform.TransformContext;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * Transforms
+ *        a && b into if(a, b, false)
+ * and
+ *        a || b into if(a, true, b)
+ * to avoid computing b if a is false and true respectively.
+ *
+ * This may increase performance since boolean expressions are not short-circuited.
+ *
+ * @author bratseth
+ */
+public class BooleanExpressionTransformer extends ExpressionTransformer<TransformContext> {
+
+    @Override
+    public ExpressionNode transform(ExpressionNode node, TransformContext context) {
+        if (node instanceof CompositeNode composite)
+            node = transformChildren(composite, context);
+
+        if (node instanceof ArithmeticNode arithmetic)
+            node = transformBooleanArithmetics(arithmetic);
+
+        return node;
+    }
+
+    private ExpressionNode transformBooleanArithmetics(ArithmeticNode node) {
+        Iterator<ExpressionNode> child = node.children().iterator();
+
+        // Transform in precedence order:
+        Deque<ChildNode> stack = new ArrayDeque<>();
+        stack.push(new ChildNode(ArithmeticOperator.OR, child.next()));
+        for (Iterator<ArithmeticOperator> it = node.operators().iterator(); it.hasNext() && child.hasNext();) {
+            ArithmeticOperator op = it.next();
+            if ( ! stack.isEmpty()) {
+                while (stack.size() > 1 && ! op.hasPrecedenceOver(stack.peek().op)) {
+                    popStack(stack);
+                }
+            }
+            stack.push(new ChildNode(op, child.next()));
+        }
+        while (stack.size() > 1)
+            popStack(stack);
+        return stack.getFirst().child;
+    }
+
+    private void popStack(Deque<ChildNode> stack) {
+        ChildNode rhs = stack.pop();
+        ChildNode lhs = stack.peek();
+
+        ExpressionNode combination;
+        if (rhs.op == ArithmeticOperator.AND)
+            combination = andByIfNode(lhs.child, rhs.child);
+        else if (rhs.op == ArithmeticOperator.OR)
+            combination = orByIfNode(lhs.child, rhs.child);
+        else
+            combination = new ArithmeticNode(List.of(lhs.child, rhs.child), List.of(rhs.op));
+        lhs.child = combination;
+    }
+
+
+    private IfNode andByIfNode(ExpressionNode a, ExpressionNode b) {
+        return new IfNode(a, b, new ConstantNode(new BooleanValue(false)));
+    }
+
+    private IfNode orByIfNode(ExpressionNode a, ExpressionNode b) {
+        return new IfNode(a, new ConstantNode(new BooleanValue(true)), b);
+    }
+
+    /** A child with the operator to be applied to it when combining it with the previous child. */
+    private static class ChildNode {
+
+        final ArithmeticOperator op;
+        ExpressionNode child;
+
+        public ChildNode(ArithmeticOperator op, ExpressionNode child) {
+            this.op = op;
+            this.child = child;
+        }
+
+        @Override
+        public String toString() {
+            return child.toString();
+        }
+
+    }
+
+}
diff --git a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java
index 86aedd4332a..132597ee75e 100644
--- a/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java
+++ b/config-model/src/main/java/com/yahoo/schema/expressiontransforms/ExpressionTransforms.java
@@ -35,7 +35,8 @@ public class ExpressionTransforms {
                                  new FunctionInliner(),
                                  new FunctionShadower(),
                                  new TensorMaxMinTransformer(),
-                                 new Simplifier());
+                                 new Simplifier(),
+                                 new BooleanExpressionTransformer());
     }
 
     public RankingExpression transform(RankingExpression expression, RankProfileTransformContext context) {
diff --git a/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java b/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java
index 789c4ac5577..5eecee516ec 100644
--- a/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java
+++ b/config-model/src/test/java/com/yahoo/schema/RankingExpressionInliningTestCase.java
@@ -163,7 +163,7 @@ public class RankingExpressionInliningTestCase extends AbstractSchemaTestCase {
                         "    \n" +
                         "    rank-profile test {\n" +
                         "        first-phase {\n" +
-                        "            expression: A + C + D\n" +
+                        "            expression: A + C - D\n" +
                         "        }\n" +
                         "        function inline D() {\n" +
                         "            expression: B + 1\n" +
@@ -184,7 +184,7 @@ public class RankingExpressionInliningTestCase extends AbstractSchemaTestCase {
         Schema s = builder.getSchema();
 
         RankProfile test = rankProfileRegistry.get(s, "test").compile(new QueryProfileRegistry(), new ImportedMlModels());
-        assertEquals("attribute(a) + C + (attribute(b) + 1)", test.getFirstPhaseRanking().getRoot().toString());
+        assertEquals("attribute(a) + C - (attribute(b) + 1)", test.getFirstPhaseRanking().getRoot().toString());
         assertEquals("attribute(a) + attribute(b)", getRankingExpression("C", test, s));
         assertEquals("attribute(b) + 1", getRankingExpression("D", test, s));
     }
diff --git a/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java b/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java
new file mode 100644
index 00000000000..71d0657c701
--- /dev/null
+++ b/config-model/src/test/java/com/yahoo/schema/expressiontransforms/BooleanExpressionTransformerTestCase.java
@@ -0,0 +1,57 @@
+// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.schema.expressiontransforms;
+
+import com.yahoo.searchlib.rankingexpression.RankingExpression;
+import com.yahoo.searchlib.rankingexpression.evaluation.MapContext;
+import com.yahoo.searchlib.rankingexpression.evaluation.MapTypeContext;
+import com.yahoo.searchlib.rankingexpression.transform.TransformContext;
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Map;
+
+/**
+ * @author bratseth
+ */
+public class BooleanExpressionTransformerTestCase {
+
+    @Test
+    public void testTransformer() throws Exception {
+        assertTransformed("if (a, b, false)", "a && b");
+        assertTransformed("if (a, true, b)", "a || b");
+        assertTransformed("if (a, true, b + c)", "a || b + c");
+        assertTransformed("if (c + a, true, b)", "c + a || b");
+        assertTransformed("if (c + a, true, b + c)", "c + a || b + c");
+        assertTransformed("if (a + b, true, if (c - d * e, f, false))", "a + b || c - d * e && f");
+        assertTransformed("if (a, true, if (b, c, false))", "a || b && c");
+        assertTransformed("if (a + b, true, if (if (c, d, false), e * f - g, false))", "a + b || c && d && e * f - g");
+        assertTransformed("if(1 - 1, true, 1 - 1)", "1 - 1 || 1 - 1");
+    }
+
+    @Test
+    public void testIt() throws Exception {
+        assertTransformed("if(1 - 1, true, 1 - 1)", "1 - 1 || 1 - 1");
+    }
+
+    private void assertTransformed(String expected, String input) throws Exception {
+        var transformedExpression = new BooleanExpressionTransformer()
+                                            .transform(new RankingExpression(input),
+                                                       new TransformContext(Map.of(), new MapTypeContext()));
+
+        assertEquals(new RankingExpression(expected), transformedExpression, "Transformed as expected");
+
+        MapContext context = contextWithSingleLetterVariables();
+        var inputExpression = new RankingExpression(input);
+        assertEquals(inputExpression.evaluate(new MapContext()).asBoolean(),
+                     transformedExpression.evaluate(new MapContext()).asBoolean(),
+                     "Transform and original input are equivalent");
+    }
+
+    private MapContext contextWithSingleLetterVariables() {
+        var context = new MapContext();
+        for (int i = 0; i < 26; i++)
+            context.put(Character.toString(i + 97), Math.floorMod(i, 2));
+        return context;
+    }
+
+}