diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2019-07-23 11:53:32 +0200 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2019-07-23 11:53:32 +0200 |
commit | 8c29221827f0a95ad3a1502c0ea39ce249ffad51 (patch) | |
tree | 315da03fec98f9b40c145acc53248df76f31e146 /document | |
parent | 71d5cd6bd93091b578e864eecb80b14504e5530c (diff) |
Transform the stack to a tree where also intermediate nodes are lazy.
The leftmost node is the only one being eagerly computed.
Diffstat (limited to 'document')
-rw-r--r-- | document/src/main/java/com/yahoo/document/select/rule/LogicNode.java | 46 | ||||
-rw-r--r-- | document/src/test/java/com/yahoo/document/select/LogicalNodeTestCase.java | 103 |
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)); } } |