From 71d5cd6bd93091b578e864eecb80b14504e5530c Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Mon, 22 Jul 2019 22:23:28 +0200 Subject: Add short circuit evaluation to the selection engine in java for AND and OR. --- .../java/com/yahoo/document/select/ResultList.java | 16 ++++-- .../com/yahoo/document/select/rule/LogicNode.java | 57 ++++++++++++++++------ .../yahoo/document/select/LogicalNodeTestCase.java | 26 +++++++++- 3 files changed, 79 insertions(+), 20 deletions(-) (limited to 'document') 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 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()); + } } -- cgit v1.2.3