1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
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 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();
}
}
}
|
