Wire fuzzy prefix matching support through the query stack

Adds `prefix:[true|false]` annotation support to the `fuzzy`
query operator in the YQL and JSON query languages. Fuzzy
prefix matching semantics are wired through to the matcher
implementations for both indexed and streaming search.

Example usage:

  {maxEditDistance:1,prefix:true}fuzzy("foo")

Will match `foo`, `foobar`, `foxtrot`, `zookeeper` and so on.

It can be combined with the existing prefix locking feature:

  {maxEditDistance:1,prefixLength:2,prefix:true}fuzzy("foo")

Which will match `foo`, `foobar`, `foxtrot` etc, but _not_
`zookeeper` since the locked prefix (`fo`) does not match.

Due to the complexities involved with extending the legacy binary
query stack representation, signalling prefix matching for the
fuzzy term is done by pragmatically adding a new, generic "prefix
matching" term-level flag. This is currently ignored for
everything except fuzzy query items.

Modernizing the query stack format to make it more extensible
(i.e. move encoding to Protobuf) is on the backlog...!

5 files changed, 77 insertions, 33 deletions

diff --git a/container-search/src/main/java/com/yahoo/prelude/query/FuzzyItem.java b/container-search/src/main/java/com/yahoo/prelude/query/FuzzyItem.java
index 3cf86a70985..b900dee20ba 100644
--- a/container-search/src/main/java/com/yahoo/prelude/query/FuzzyItem.java
+++ b/container-search/src/main/java/com/yahoo/prelude/query/FuzzyItem.java
@@ -16,15 +16,21 @@ public class FuzzyItem extends TermItem {
 
     private int maxEditDistance;
     private int prefixLength;
+    private boolean prefixMatch;
 
     public static int DEFAULT_MAX_EDIT_DISTANCE = 2;
     public static int DEFAULT_PREFIX_LENGTH = 0;
 
-    public FuzzyItem(String indexName, boolean isFromQuery, String term, int maxEditDistance, int prefixLength) {
+    public FuzzyItem(String indexName, boolean isFromQuery, String term, int maxEditDistance, int prefixLength, boolean prefixMatch) {
         super(indexName, isFromQuery, null);
         setValue(term);
         setMaxEditDistance(maxEditDistance);
         setPrefixLength(prefixLength);
+        setPrefixMatch(prefixMatch);
+    }
+
+    public FuzzyItem(String indexName, boolean isFromQuery, String term, int maxEditDistance, int prefixLength) {
+        this(indexName, isFromQuery, term, maxEditDistance, prefixLength, false);
     }
 
     public void setMaxEditDistance(int maxEditDistance) {
@@ -43,6 +49,19 @@ public class FuzzyItem extends TermItem {
         return this.maxEditDistance;
     }
 
+    public boolean isPrefixMatch() {
+        return this.prefixMatch;
+    }
+
+    public void setPrefixMatch(boolean prefixMatch) {
+        this.prefixMatch = prefixMatch;
+    }
+
+    @Override
+    protected boolean hasPrefixMatchSemantics() {
+        return this.prefixMatch;
+    }
+
     @Override
     public void setValue(String value) {
         this.term = value;
@@ -89,43 +108,39 @@ public class FuzzyItem extends TermItem {
     }
 
     @Override
-    public boolean equals(Object obj) {
-        if (this == obj) {
-            return true;
-        }
-        if (!super.equals(obj)) {
-            return false;
-        }
-        if (getClass() != obj.getClass()) {
-            return false;
-        }
-        FuzzyItem other = (FuzzyItem) obj;
-        if (!this.term.equals(other.term)) return false;
-        if (this.maxEditDistance != other.maxEditDistance) return false;
-        if (this.prefixLength != other.prefixLength) return false;
-        return true;
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        if (!super.equals(o)) return false;
+        FuzzyItem fuzzyItem = (FuzzyItem) o;
+        return maxEditDistance == fuzzyItem.maxEditDistance &&
+                prefixLength == fuzzyItem.prefixLength &&
+                prefixMatch == fuzzyItem.prefixMatch &&
+                Objects.equals(term, fuzzyItem.term);
     }
 
     @Override
     public int hashCode() {
-        return Objects.hash(super.hashCode(), term, maxEditDistance, prefixLength);
+        return Objects.hash(super.hashCode(), term, maxEditDistance, prefixLength, prefixMatch);
     }
 
     @Override
     protected void appendHeadingString(StringBuilder buffer) {
         buffer.append(getName());
-        buffer.append("(");
+        buffer.append('(');
         buffer.append(this.term);
-        buffer.append(",");
+        buffer.append(',');
         buffer.append(this.maxEditDistance);
-        buffer.append(",");
+        buffer.append(',');
         buffer.append(this.prefixLength);
-        buffer.append(")");
-        buffer.append(" ");
+        buffer.append(',');
+        buffer.append(this.prefixMatch);
+        buffer.append(") ");
     }
 
     @Override
     protected void encodeThis(ByteBuffer buffer) {
+        // Prefix matching is communicated via term header flags
         super.encodeThis(buffer);
         putString(getIndexedString(), buffer);
         IntegerCompressor.putCompressedPositiveNumber(this.maxEditDistance, buffer);
diff --git a/container-search/src/main/java/com/yahoo/prelude/query/Item.java b/container-search/src/main/java/com/yahoo/prelude/query/Item.java
index f43b55424e6..099c546e3f0 100644
--- a/container-search/src/main/java/com/yahoo/prelude/query/Item.java
+++ b/container-search/src/main/java/com/yahoo/prelude/query/Item.java
@@ -161,6 +161,16 @@ public abstract class Item implements Cloneable {
     }
 
     /**
+     * Indicates that a query item that does not normally match with prefix semantics
+     * should do so for this particular query item instance.
+     *
+     * False by default; should be overridden by subclasses that want to signal this behavior.
+     */
+    protected boolean hasPrefixMatchSemantics() {
+        return false;
+    }
+
+    /**
      * Returns the item creator value.
      *
      * @deprecated use isFilter(boolean)
@@ -286,6 +296,7 @@ public abstract class Item implements Cloneable {
         byte FLAGS_SPECIALTOKEN = 0x02;
         byte FLAGS_NOPOSITIONDATA = 0x04;
         byte FLAGS_ISFILTER = 0x08;
+        byte FLAGS_PREFIX_MATCH = 0x10;
 
         byte ret = 0;
         if (!isRanked()) {
@@ -300,6 +311,9 @@ public abstract class Item implements Cloneable {
         if (isFilter()) {
             ret |= FLAGS_ISFILTER;
         }
+        if (hasPrefixMatchSemantics()) {
+            ret |= FLAGS_PREFIX_MATCH;
+        }
         return ret;
     }
 
diff --git a/container-search/src/main/java/com/yahoo/search/query/SelectParser.java b/container-search/src/main/java/com/yahoo/search/query/SelectParser.java
index c897afe144c..c90612425fa 100644
--- a/container-search/src/main/java/com/yahoo/search/query/SelectParser.java
+++ b/container-search/src/main/java/com/yahoo/search/query/SelectParser.java
@@ -1150,8 +1150,9 @@ public class SelectParser implements Parser {
 
         Integer maxEditDistance = getIntegerAnnotation(MAX_EDIT_DISTANCE, annotations, FuzzyItem.DEFAULT_MAX_EDIT_DISTANCE);
         Integer prefixLength = getIntegerAnnotation(PREFIX_LENGTH, annotations, FuzzyItem.DEFAULT_PREFIX_LENGTH);
+        boolean prefixMatch = getBoolAnnotation(PREFIX, annotations, Boolean.FALSE);
 
-        FuzzyItem fuzzy = new FuzzyItem(field, true, wordData, maxEditDistance, prefixLength);
+        FuzzyItem fuzzy = new FuzzyItem(field, true, wordData, maxEditDistance, prefixLength, prefixMatch);
 
         return leafStyleSettings(getAnnotations(value), fuzzy);
     }
diff --git a/container-search/src/main/java/com/yahoo/search/yql/VespaSerializer.java b/container-search/src/main/java/com/yahoo/search/yql/VespaSerializer.java
index 634163bf0c2..a354006aa9b 100644
--- a/container-search/src/main/java/com/yahoo/search/yql/VespaSerializer.java
+++ b/container-search/src/main/java/com/yahoo/search/yql/VespaSerializer.java
@@ -551,24 +551,31 @@ public class VespaSerializer {
         static String fuzzyAnnotations(FuzzyItem fuzzyItem) {
             boolean isMaxEditDistanceSet = fuzzyItem.getMaxEditDistance() != FuzzyItem.DEFAULT_MAX_EDIT_DISTANCE;
             boolean isPrefixLengthSet = fuzzyItem.getPrefixLength() != FuzzyItem.DEFAULT_PREFIX_LENGTH;
-            boolean anyAnnotationSet = isMaxEditDistanceSet || isPrefixLengthSet;
+            boolean isPrefixMatch = fuzzyItem.isPrefixMatch();
+            boolean anyAnnotationSet = isMaxEditDistanceSet || isPrefixLengthSet || isPrefixMatch;
 
-            StringBuilder builder = new StringBuilder();
-            if (anyAnnotationSet) {
-                builder.append("{");
+            if (!anyAnnotationSet) {
+                return "";
             }
+
+            StringBuilder builder = new StringBuilder();
+            builder.append("{");
             if (isMaxEditDistanceSet) {
                 builder.append(MAX_EDIT_DISTANCE + ":").append(fuzzyItem.getMaxEditDistance());
-            }
-            if (isMaxEditDistanceSet && isPrefixLengthSet) {
-                builder.append(",");
+                if (isPrefixLengthSet || isPrefixMatch) {
+                    builder.append(",");
+                }
             }
             if (isPrefixLengthSet) {
                 builder.append(PREFIX_LENGTH + ":").append(fuzzyItem.getPrefixLength());
+                if (isPrefixMatch) {
+                    builder.append(",");
+                }
             }
-            if (anyAnnotationSet) {
-                builder.append("}");
+            if (isPrefixMatch) {
+                builder.append(PREFIX).append(':').append(fuzzyItem.isPrefixMatch());
             }
+            builder.append("}");
             return builder.toString();
         }
     }
diff --git a/container-search/src/main/java/com/yahoo/search/yql/YqlParser.java b/container-search/src/main/java/com/yahoo/search/yql/YqlParser.java
index e66cac5766c..fb4ec5ba872 100644
--- a/container-search/src/main/java/com/yahoo/search/yql/YqlParser.java
+++ b/container-search/src/main/java/com/yahoo/search/yql/YqlParser.java
@@ -1385,7 +1385,14 @@ public class YqlParser implements Parser {
                 FuzzyItem.DEFAULT_PREFIX_LENGTH,
                 PREFIX_LENGTH_DESCRIPTION);
 
-        FuzzyItem fuzzy = new FuzzyItem(field, true, wordData, maxEditDistance, prefixLength);
+        boolean prefixMatch = getAnnotation(
+                ast,
+                PREFIX,
+                Boolean.class,
+                Boolean.FALSE,
+                "setting for whether to use prefix match of input data");
+
+        FuzzyItem fuzzy = new FuzzyItem(field, true, wordData, maxEditDistance, prefixLength, prefixMatch);
         return leafStyleSettings(ast, fuzzy);
     }