Transform the stack to a tree where also intermediate nodes are lazy.

The leftmost node is the only one being eagerly computed.

2 files changed, 102 insertions, 47 deletions

diff --git a/document/src/main/java/com/yahoo/document/select/rule/LogicNode.java b/document/src/main/java/com/yahoo/document/select/rule/LogicNode.java
index 04e0aabfde7..e22a56f6e9a 100644
--- a/document/src/main/java/com/yahoo/document/select/rule/LogicNode.java
+++ b/document/src/main/java/com/yahoo/document/select/rule/LogicNode.java
@@ -169,8 +169,8 @@ public class LogicNode implements ExpressionNode {
                     combineValues(buf);
                 }
             }
-            
-            buf.push(new LazyValueItem(item, context));
+            ValueItem next = new LazyValueItem(item, context);
+            buf.push(buf.empty() ? new EagerValueItem(next.getOperator(), next.getResult()) : next);
         }
         while (buf.size() > 1) {
             combineValues(buf);
@@ -186,17 +186,7 @@ public class LogicNode implements ExpressionNode {
     private void combineValues(Stack<ValueItem> buf) {
         ValueItem rhs = buf.pop();
         ValueItem lhs = buf.pop();
-
-        switch (rhs.getOperator()) {
-            case AND:
-                buf.push(new EagerValueItem(lhs.getOperator(), lhs.getResult().combineAND(rhs)));
-                break;
-            case OR:
-                buf.push(new EagerValueItem(lhs.getOperator(), lhs.getResult().combineOR(rhs)));
-                break;
-            default:
-                throw new IllegalStateException("Arithmetic operator " + rhs.getOperator() + " not supported.");
-        }
+        buf.push(new LazyCombinedItem(lhs, rhs));
     }
 
     public void accept(Visitor visitor) {
@@ -222,7 +212,7 @@ public class LogicNode implements ExpressionNode {
      * @param operator The operator index to convert.
      * @return The string representation.
      */
-    public String operatorToString(int operator) {
+    private String operatorToString(int operator) {
         switch (operator) {
             case NOP:
                 return null;
@@ -284,6 +274,34 @@ public class LogicNode implements ExpressionNode {
         }
     }
 
+    private final class LazyCombinedItem extends ValueItem {
+        private final ValueItem lhs;
+        private final ValueItem rhs;
+        private ResultList lazyResult = null;
+
+        LazyCombinedItem(ValueItem lhs, ValueItem rhs) {
+            super(lhs.getOperator());
+            this.lhs = lhs;
+            this.rhs = rhs;
+        }
+        @Override
+        public ResultList getResult() {
+            if (lazyResult == null) {
+                switch (rhs.getOperator()) {
+                    case AND:
+                        lazyResult = lhs.getResult().combineAND(rhs);
+                        break;
+                    case OR:
+                        lazyResult = lhs.getResult().combineOR(rhs);
+                        break;
+                    default:
+                        throw new IllegalStateException("Logical operator " + rhs.getOperator() + " not supported.");
+                }
+            }
+            return lazyResult;
+        }
+    }
+
     private final class EagerValueItem extends ValueItem {
         private final ResultList value;
 
diff --git a/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java b/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java
index 5f5de1e8462..25aca22b108 100644
--- a/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java
+++ b/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java
@@ -6,22 +6,26 @@ import com.yahoo.document.select.rule.LiteralNode;
 import com.yahoo.document.select.rule.LogicNode;
 import org.junit.Test;
 
+import java.util.List;
+import java.util.concurrent.atomic.AtomicInteger;
+
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
 public class LogicalNodeTestCase {
     private static class TracedNode implements ExpressionNode {
-
+        private final AtomicInteger evalOrder;
         private final ExpressionNode node;
-        private boolean evaluated = false;
+        private int evaluatedAs = -1;
 
-        TracedNode(ExpressionNode node) {
+        TracedNode(AtomicInteger evalOrder, ExpressionNode node) {
+            this.evalOrder = evalOrder;
             this.node = node;
         }
         @Override
         public Object evaluate(Context doc) {
-            evaluated = true;
+            evaluatedAs = evalOrder.getAndIncrement();
             return node.evaluate(doc);
         }
 
@@ -39,51 +43,84 @@ public class LogicalNodeTestCase {
         public void accept(Visitor visitor) {
             node.accept(visitor);
         }
-        boolean isEvaluated() { return evaluated; }
+        boolean isEvaluated() { return evaluatedAs >= 0; }
+        int getEvalOrder() { return evaluatedAs; }
     }
     private static Result evaluate(ExpressionNode node) {
         return ((ResultList)node.evaluate(new Context(null))).toResult();
     }
+
+    private static TracedNode createTraced(AtomicInteger evalOrder, char node) {
+        return new TracedNode(evalOrder, new LiteralNode(node == 'T'));
+    }
+
+    private static void addOperator(LogicNode logical, char operator, ExpressionNode node) {
+        if (operator == '&') {
+            logical.add("and", node);
+        } else if (operator == '|') {
+            logical.add("or", node);
+        } else {
+            throw new IllegalArgumentException("Bad operator '" + operator + "'");
+        }
+    }
+
+    static private void verifyEvaluationOrder(String expr, boolean expectedResult, List<Integer> expectedEvaluationOrder ) {
+        assertEquals(1, expr.length()%2);
+        assertEquals(expectedEvaluationOrder.size()*2 - 1, expr.length());
+        TracedNode [] traced = new TracedNode[expectedEvaluationOrder.size()];
+        AtomicInteger evalOrder = new AtomicInteger(0);
+        for (int i=0; i < traced.length; i++) {
+            traced[i] = createTraced(evalOrder, expr.charAt(i*2));
+        }
+        LogicNode logical = new LogicNode().add(null, traced[0]);
+        for (int i=1; i < traced.length; i++) {
+            addOperator(logical, expr.charAt(i*2-1), traced[i]);
+        }
+        for (TracedNode node : traced) {
+            assertFalse(node.isEvaluated());
+        }
+        assertEquals(Result.toResult(expectedResult), evaluate(logical));
+        for (int i = 0; i < traced.length; i++) {
+            assertEquals(expectedEvaluationOrder.get(i).intValue(), traced[i].getEvalOrder());
+        }
+    }
     @Test
     public void testFullyExhaustedAND() {
-        TracedNode second = new TracedNode(new LiteralNode(true));
-        assertFalse(second.isEvaluated());
-        ExpressionNode logical = new LogicNode()
-                .add(null, new LiteralNode(true))
-                .add("and", second);
-        assertEquals(Result.TRUE, evaluate(logical));
-        assertTrue(second.isEvaluated());
+        verifyEvaluationOrder("T&T", true, List.of(0,1));
+
     }
     @Test
     public void testShortCircuitAND() {
-        TracedNode second = new TracedNode(new LiteralNode(true));
-        assertFalse(second.isEvaluated());
-        ExpressionNode logical = new LogicNode()
-                .add(null, new LiteralNode(false))
-                .add("and", second);
-        assertEquals(Result.FALSE, evaluate(logical));
-        assertFalse(second.isEvaluated());
+        verifyEvaluationOrder("F&T", false, List.of(0,-1));
     }
 
     @Test
     public void testFullyExhaustedOR() {
-        TracedNode second = new TracedNode(new LiteralNode(true));
-        assertFalse(second.isEvaluated());
-        ExpressionNode logical = new LogicNode()
-                .add(null, new LiteralNode(false))
-                .add("or", second);
-        assertEquals(Result.TRUE, evaluate(logical));
-        assertTrue(second.isEvaluated());
+        verifyEvaluationOrder("F|T", true, List.of(0,1));
     }
 
     @Test
     public void testShortCircuitOR() {
-        TracedNode second = new TracedNode(new LiteralNode(false));
-        assertFalse(second.isEvaluated());
-        ExpressionNode logical = new LogicNode()
-                .add(null, new LiteralNode(true))
-                .add("or", second);
-        assertEquals(Result.TRUE, evaluate(logical));
-        assertFalse(second.isEvaluated());
+        verifyEvaluationOrder("T|F", true, List.of(0,-1));
+    }
+
+    @Test
+    public void testLeft2Right() {
+        verifyEvaluationOrder("T&T&T&T&T", true, List.of(0,1,2,3,4));
+        verifyEvaluationOrder("T&T&F&T&F", false, List.of(0,1,2,-1,-1));
+
+        verifyEvaluationOrder("F|F|F|F|T", true, List.of(0,1,2,3,4));
+        verifyEvaluationOrder("F|F|F|F|F", false, List.of(0,1,2,3,4));
+        verifyEvaluationOrder("F|F|T|F|T", true, List.of(0,1,2,-1,-1));
+    }
+
+    @Test
+    public void testLeft2RightWithPriority() {
+        verifyEvaluationOrder("T&F|T", true, List.of(0,1,2));
+        verifyEvaluationOrder("F&T|T", true, List.of(0,-1,1));
+
+        verifyEvaluationOrder("T|F&T", true, List.of(0,-1,-1));
+        verifyEvaluationOrder("F|F&T", false, List.of(0,1,-1));
+        verifyEvaluationOrder("F|T&T", true, List.of(0,1,2));
     }
 }