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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.prelude.semantics.engine;
import com.yahoo.search.Query;
import com.yahoo.prelude.query.QueryCanonicalizer;
import com.yahoo.prelude.semantics.RuleBase;
import com.yahoo.prelude.semantics.RuleBaseException;
import com.yahoo.prelude.semantics.rule.ProductionRule;
import java.util.ListIterator;
/**
* Evaluates the rules of a rule base. This method is thread safe on analyze calls, but
* not on modification calls.
*
* @author bratseth
*/
public class RuleEngine {
private final RuleBase rules;
public RuleEngine(RuleBase rules) {
this.rules=rules;
}
/**
* Evaluates a rule base over a query
*
* @param query the query to evaluate
* @param traceLevel the level of tracing to do
* @return the error caused by analyzing the query, or null if there was no error
* If there is an error, this query is destroyed (unusable)
*/
public String evaluate(Query query, int traceLevel) {
// TODO: This is O(query size*rule base size). We'll eventually need to create indices
// on rules to look up rule candidates per term to make it O(query size) instead
// Probably create indices on the first term like Prolog implementations use to
boolean matchedAnything = false;
Evaluation evaluation = new Evaluation(query, rules, traceLevel);
if (traceLevel >= 2)
evaluation.trace(2,"Evaluating query '" + evaluation.getQuery().getModel().getQueryTree().getRoot() + "':");
for (ListIterator<ProductionRule> i = rules.ruleIterator(); i.hasNext(); ) {
evaluation.reset();
ProductionRule rule = i.next();
boolean matched = matchRuleAtAllStartPoints(evaluation,rule);
matchedAnything |= matched;
}
if ( ! matchedAnything) return null;
String error = QueryCanonicalizer.canonicalize(query);
query.trace("SemanticSearcher: Rewrote query",true,1);
return error;
}
/** Match a rule at any starting point in the query */
private boolean matchRuleAtAllStartPoints(Evaluation evaluation, ProductionRule rule) {
boolean matchedAtLeastOnce = false;
int iterationCount = 0;
// Test if it is a removal rule, if so iterate backwards so that precalculated
// replacement positions do not become invalid as the query shrink
boolean removalRule = false;
if ( (rule instanceof com.yahoo.prelude.semantics.rule.ReplacingProductionRule) &&
(rule.getProduction().toString().length() == 0) ) { // empty replacement
removalRule = true;
evaluation.setToLast();
}
int loopLimit = Math.max(15, evaluation.getQuerySize() * 3);
while (evaluation.currentItem() != null) {
boolean matched = matchRule(evaluation,rule);
if (matched) {
if (removalRule)
evaluation.resetToLast();
else
evaluation.reset();
matchedAtLeastOnce = true;
if (rule.isLoop()) break;
}
else {
if (removalRule)
evaluation.previous();
else
evaluation.next();
}
if (matched && iterationCount++ > loopLimit) {
throw new RuleBaseException("Rule '" + rule + "' has matched '" +
evaluation.getQuery().getModel().getQueryTree().getRoot() +
"' " + loopLimit + " times, aborting");
}
}
return matchedAtLeastOnce;
}
/**
* Matches a rule at the current starting point of the evaluation, and carries
* out the production if there is a match
*
* @return whether this rule matched
*/
// TODO: Code cleanup
private boolean matchRule(Evaluation evaluation, ProductionRule rule) {
RuleEvaluation ruleEvaluation=evaluation.freshRuleEvaluation();
ruleEvaluation.indentTrace();
if (ruleEvaluation.getTraceLevel() >= 3) {
ruleEvaluation.trace(3,"Evaluating rule '" + rule +
"' on '" + ruleEvaluation.getEvaluation().getQuery().getModel().getQueryTree().getRoot() +
"' at '" + ruleEvaluation.currentItem() + "':");
}
ruleEvaluation.indentTrace();
boolean matches = rule.matches(ruleEvaluation);
boolean matchedBefore = false;
int currentMatchDigest = ruleEvaluation.calculateMatchDigest(rule);
if (evaluation.hasMatchDigest(currentMatchDigest))
matchedBefore = true;
boolean queryGotShorter = false;
if (evaluation.getPreviousQuerySize() > evaluation.getQuerySize())
queryGotShorter = true;
boolean doProduction =! matchedBefore || queryGotShorter;
ruleEvaluation.unindentTrace();
if (ruleEvaluation.getTraceLevel() >= 2) {
if (matches && doProduction)
ruleEvaluation.trace(2,"Matched rule '" + rule + "' at " + ruleEvaluation.previousItem());
else if ( ! matches)
ruleEvaluation.trace(2,"Did not match rule '" + rule + "' at " + ruleEvaluation.currentItem());
else
ruleEvaluation.trace(2,"Ignoring repeated match of '" + rule + "'");
}
ruleEvaluation.unindentTrace();
if (!matches || !doProduction) return false;
// Do production barrier
evaluation.addMatchDigest(currentMatchDigest);
String preQuery = null;
if (evaluation.getTraceLevel()>=1) {
preQuery = evaluation.getQuery().getModel().getQueryTree().getRoot().toString();
}
rule.produce(ruleEvaluation);
if (evaluation.getTraceLevel() >= 1) {
evaluation.trace(1,"Transforming '" + preQuery + "' to '" +
evaluation.getQuery().getModel().getQueryTree().getRoot().toString()
+ "' since '" + rule + "' matched");
}
return true;
}
}
|
