Add short circuit evaluation to the selection engine in java for AND and OR.

4 files changed, 79 insertions, 21 deletions

diff --git a/document/src/main/java/com/yahoo/document/select/ResultList.java b/document/src/main/java/com/yahoo/document/select/ResultList.java
index 8d73c475981..432e86a6c78 100644
--- a/document/src/main/java/com/yahoo/document/select/ResultList.java
+++ b/document/src/main/java/com/yahoo/document/select/ResultList.java
@@ -116,13 +116,19 @@ public class ResultList {
         return true;
     }
 
-    public ResultList combineAND(ResultList other)
+    public interface GetResultList {
+        ResultList getResult();
+    }
+
+    public ResultList combineAND(GetResultList other)
     {
+        if (Result.FALSE == toResult()) return ResultList.toResultList(false);
+
         ResultList result = new ResultList();
 
         // TODO: optimize
         for (ResultPair pair : results) {
-            for (ResultPair otherPair : other.results) {
+            for (ResultPair otherPair : other.getResult().results) {
                 FieldPathIteratorHandler.VariableMap varMap = (FieldPathIteratorHandler.VariableMap)pair.variables.clone();
 
                 if (combineVariables(varMap, otherPair.variables)) {
@@ -144,13 +150,15 @@ public class ResultList {
         return Result.INVALID;
     }
 
-    public ResultList combineOR(ResultList other)
+    public ResultList combineOR(GetResultList other)
     {
+        if (Result.TRUE == toResult()) return ResultList.toResultList(true);
+
         ResultList result = new ResultList();
 
         // TODO: optimize
         for (ResultPair pair : results) {
-            for (ResultPair otherPair : other.results) {
+            for (ResultPair otherPair : other.getResult().results) {
                 FieldPathIteratorHandler.VariableMap varMap = (FieldPathIteratorHandler.VariableMap)pair.variables.clone();
 
                 if (combineVariables(varMap, otherPair.variables)) {
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 308f84ff789..04e0aabfde7 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
@@ -160,23 +160,22 @@ public class LogicNode implements ExpressionNode {
         buf.push(lhs);
     }
 
-    // Inherit doc from ExpressionNode.
     @Override
     public Object evaluate(Context context) {
         Stack<ValueItem> buf = new Stack<>();
         for (NodeItem item : items) {
-            if ( ! buf.isEmpty()) {
-                while (buf.peek().operator > item.operator) {
+            if ( buf.size() > 1) {
+                while ((buf.peek().getOperator() >= item.operator)) {
                     combineValues(buf);
                 }
             }
             
-            buf.push(new ValueItem(item.operator, ResultList.toResultList(item.node.evaluate(context))));
+            buf.push(new LazyValueItem(item, context));
         }
         while (buf.size() > 1) {
             combineValues(buf);
         }
-        return buf.pop().value;
+        return buf.pop().getResult();
     }
 
     /**
@@ -188,15 +187,15 @@ public class LogicNode implements ExpressionNode {
         ValueItem rhs = buf.pop();
         ValueItem lhs = buf.pop();
 
-        switch (rhs.operator) {
+        switch (rhs.getOperator()) {
             case AND:
-                buf.push(new ValueItem(lhs.operator, lhs.value.combineAND(rhs.value)));
+                buf.push(new EagerValueItem(lhs.getOperator(), lhs.getResult().combineAND(rhs)));
                 break;
             case OR:
-                buf.push(new ValueItem(lhs.operator, lhs.value.combineOR(rhs.value)));
+                buf.push(new EagerValueItem(lhs.getOperator(), lhs.getResult().combineOR(rhs)));
                 break;
             default:
-                throw new IllegalStateException("Arithmetic operator " + rhs.operator + " not supported.");
+                throw new IllegalStateException("Arithmetic operator " + rhs.getOperator() + " not supported.");
         }
     }
 
@@ -258,14 +257,44 @@ public class LogicNode implements ExpressionNode {
     /**
      * Private class to store results in a stack.
      */
-    private final class ValueItem {
-        private int operator;
-        private ResultList value;
-
-        ValueItem(int operator, ResultList value) {
+    private abstract class ValueItem implements ResultList.GetResultList {
+        private final int operator;
+        ValueItem(int operator) {
             this.operator = operator;
+        }
+        int getOperator() { return operator; }
+    }
+
+    private final class LazyValueItem extends ValueItem {
+        private final NodeItem item;
+        private final Context context;
+        private ResultList lazyResult = null;
+
+        LazyValueItem(NodeItem item, Context context) {
+            super(item.operator);
+            this.item = item;
+            this.context = context;
+        }
+        @Override
+        public ResultList getResult() {
+            if (lazyResult == null) {
+                lazyResult = ResultList.toResultList(item.node.evaluate(context));
+            }
+            return lazyResult;
+        }
+    }
+
+    private final class EagerValueItem extends ValueItem {
+        private final ResultList value;
+
+        EagerValueItem(int operator, ResultList value) {
+            super(operator);
             this.value = value;
         }
+        @Override
+        public ResultList getResult() {
+            return 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 fbf307667d8..5f5de1e8462 100644
--- a/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java
+++ b/document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java
@@ -45,7 +45,7 @@ public class LogicalNodeTestCase {
         return ((ResultList)node.evaluate(new Context(null))).toResult();
     }
     @Test
-    public void testFullyExhaustedAnd() {
+    public void testFullyExhaustedAND() {
         TracedNode second = new TracedNode(new LiteralNode(true));
         assertFalse(second.isEvaluated());
         ExpressionNode logical = new LogicNode()
@@ -55,7 +55,7 @@ public class LogicalNodeTestCase {
         assertTrue(second.isEvaluated());
     }
     @Test
-    public void testShortCircuitAnd() {
+    public void testShortCircuitAND() {
         TracedNode second = new TracedNode(new LiteralNode(true));
         assertFalse(second.isEvaluated());
         ExpressionNode logical = new LogicNode()
@@ -64,4 +64,26 @@ public class LogicalNodeTestCase {
         assertEquals(Result.FALSE, evaluate(logical));
         assertFalse(second.isEvaluated());
     }
+
+    @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());
+    }
+
+    @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());
+    }
 }
diff --git a/documentapi/src/test/java/com/yahoo/documentapi/messagebus/protocol/test/PolicyTestCase.java b/documentapi/src/test/java/com/yahoo/documentapi/messagebus/protocol/test/PolicyTestCase.java
index cd045c0363d..cb32ce75e03 100755
--- a/documentapi/src/test/java/com/yahoo/documentapi/messagebus/protocol/test/PolicyTestCase.java
+++ b/documentapi/src/test/java/com/yahoo/documentapi/messagebus/protocol/test/PolicyTestCase.java
@@ -613,7 +613,6 @@ public class PolicyTestCase {
     }
 
     @Test
-    @Ignore
     public void testDocumentSelectorDualCluster() {
         PolicyTestFrame frame = new PolicyTestFrame(manager);
         frame.setHop(new HopSpec("test", "[DocumentRouteSelector:raw:" +