Publish

1 files changed, 169 insertions, 0 deletions

diff --git a/container-search/src/main/java/com/yahoo/prelude/semantics/engine/RuleEngine.java b/container-search/src/main/java/com/yahoo/prelude/semantics/engine/RuleEngine.java
new file mode 100644
index 00000000000..ee874b76ed6
--- /dev/null
+++ b/container-search/src/main/java/com/yahoo/prelude/semantics/engine/RuleEngine.java
@@ -0,0 +1,169 @@
+// Copyright 2016 Yahoo Inc. 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 <a href="mailto:bratseth@yahoo-inc.com">Jon S Bratseth</a>
+ */
+public class RuleEngine {
+
+    private 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,traceLevel);
+        evaluation.setStemming(rules.getStemming());
+        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);
+
+        if (query.getTraceLevel()>=1)
+            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 does 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 if (!doProduction)
+                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;
+    }
+
+}