Support fuzzy term matching in streaming search

Uses a DFA-based matcher for max edits in {1, 2} and falls back
to the legacy non-DFA matcher for all other values (including 0).

Currently only supports fuzzy matching across the full field
string, i.e. there's no implicit tokenization or whitespace
removal. This matches the semantics we currently have for fuzzy
search over attributes in a non-streaming case

6 files changed, 215 insertions, 33 deletions

diff --git a/streamingvisitors/src/tests/searcher/searcher_test.cpp b/streamingvisitors/src/tests/searcher/searcher_test.cpp
index 24877866c1b..ee2c5e2b5c7 100644
--- a/streamingvisitors/src/tests/searcher/searcher_test.cpp
+++ b/streamingvisitors/src/tests/searcher/searcher_test.cpp
@@ -3,6 +3,7 @@
 #include <vespa/vespalib/testkit/testapp.h>
 
 #include <vespa/document/fieldvalue/fieldvalues.h>
+#include <vespa/searchlib/query/streaming/fuzzy_term.h>
 #include <vespa/searchlib/query/streaming/regexp_term.h>
 #include <vespa/searchlib/query/streaming/queryterm.h>
 #include <vespa/vsm/searcher/boolfieldsearcher.h>
@@ -18,10 +19,14 @@
 #include <vespa/vsm/searcher/utf8suffixstringfieldsearcher.h>
 #include <vespa/vsm/searcher/tokenizereader.h>
 #include <vespa/vsm/vsm/snippetmodifier.h>
+#include <concepts>
+#include <charconv>
+#include <stdexcept>
 
 using namespace document;
 using search::streaming::HitList;
 using search::streaming::QueryNodeResultFactory;
+using search::streaming::FuzzyTerm;
 using search::streaming::RegexpTerm;
 using search::streaming::QueryTerm;
 using search::streaming::Normalizing;
@@ -58,6 +63,46 @@ public:
     }
 };
 
+namespace {
+
+template <std::integral T>
+std::string_view maybe_consume_into(std::string_view str, T& val_out) {
+    auto [ptr, ec] = std::from_chars(str.data(), str.data() + str.size(), val_out);
+    if (ec != std::errc()) {
+        return str;
+    }
+    return str.substr(ptr - str.data());
+}
+
+// Parse optional max edits and prefix lock length from term string.
+// Syntax:
+//   "term"      -> {2, 0, "term"} (default max edits & prefix length)
+//   "{1}term"   -> {1, 0, "term"}
+//   "{1,3}term" -> {1, 3, "term"}
+//
+// Note: this is not a "proper" parser (it accepts empty numeric values); only for testing!
+std::tuple<uint8_t, uint32_t, std::string_view> parse_fuzzy_params(std::string_view term) {
+    if (term.empty() || term[0] != '{') {
+        return {2, 0, term};
+    }
+    uint8_t  max_edits = 2;
+    uint32_t prefix_length = 0;
+    term = maybe_consume_into(term.substr(1), max_edits);
+    if (term.empty() || (term[0] != ',' && term[0] != '}')) {
+        throw std::invalid_argument("malformed fuzzy params at (or after) max_edits");
+    }
+    if (term[0] == '}') {
+        return {max_edits, prefix_length, term.substr(1)};
+    }
+    term = maybe_consume_into(term.substr(1), prefix_length);
+    if (term.empty() || term[0] != '}') {
+        throw std::invalid_argument("malformed fuzzy params at (or after) prefix_length");
+    }
+    return {max_edits, prefix_length, term.substr(1)};
+}
+
+}
+
 class Query
 {
 private:
@@ -66,10 +111,14 @@ private:
             ParsedQueryTerm pqt = parseQueryTerm(term);
             ParsedTerm pt = parseTerm(pqt.second);
             std::string effective_index = pqt.first.empty() ? "index" : pqt.first;
-            if (pt.second != TermType::REGEXP) {
-                qtv.push_back(std::make_unique<QueryTerm>(eqnr.create(), pt.first, effective_index, pt.second, normalizing));
+            if (pt.second == TermType::REGEXP) {
+                qtv.push_back(std::make_unique<RegexpTerm>(eqnr.create(), pt.first, effective_index, TermType::REGEXP, normalizing));
+            } else if (pt.second == TermType::FUZZYTERM) {
+                auto [max_edits, prefix_length, actual_term] = parse_fuzzy_params(pt.first);
+                qtv.push_back(std::make_unique<FuzzyTerm>(eqnr.create(), vespalib::stringref(actual_term.data(), actual_term.size()),
+                                                          effective_index, TermType::FUZZYTERM, normalizing, max_edits, prefix_length));
             } else {
-                qtv.push_back(std::make_unique<RegexpTerm>(eqnr.create(), pt.first, effective_index, pt.second, normalizing));
+                qtv.push_back(std::make_unique<QueryTerm>(eqnr.create(), pt.first, effective_index, pt.second, normalizing));
             }
         }
         for (const auto & i : qtv) {
@@ -100,6 +149,8 @@ public:
             return std::make_pair(term.substr(1, term.size() - 1), TermType::SUFFIXTERM);
         } else if (term[0] == '#') { // magic regex enabler
             return std::make_pair(term.substr(1), TermType::REGEXP);
+        } else if (term[0] == '%') { // equally magic fuzzy enabler
+            return std::make_pair(term.substr(1), TermType::FUZZYTERM);
         } else if (term[term.size() - 1] == '*') {
             return std::make_pair(term.substr(0, term.size() - 1), TermType::PREFIXTERM);
         } else {
@@ -477,31 +528,54 @@ testStrChrFieldSearcher(StrChrFieldSearcher & fs)
     return true;
 }
 
-    TEST("verify correct term parsing") {
-        ASSERT_TRUE(Query::parseQueryTerm("index:term").first == "index");
-        ASSERT_TRUE(Query::parseQueryTerm("index:term").second == "term");
-        ASSERT_TRUE(Query::parseQueryTerm("term").first.empty());
-        ASSERT_TRUE(Query::parseQueryTerm("term").second == "term");
-        ASSERT_TRUE(Query::parseTerm("*substr*").first == "substr");
-        ASSERT_TRUE(Query::parseTerm("*substr*").second == TermType::SUBSTRINGTERM);
-        ASSERT_TRUE(Query::parseTerm("*suffix").first == "suffix");
-        ASSERT_TRUE(Query::parseTerm("*suffix").second == TermType::SUFFIXTERM);
-        ASSERT_TRUE(Query::parseTerm("prefix*").first == "prefix");
-        ASSERT_TRUE(Query::parseTerm("prefix*").second == TermType::PREFIXTERM);
-        ASSERT_TRUE(Query::parseTerm("#regex").first == "regex");
-        ASSERT_TRUE(Query::parseTerm("#regex").second == TermType::REGEXP);
-        ASSERT_TRUE(Query::parseTerm("term").first == "term");
-        ASSERT_TRUE(Query::parseTerm("term").second == TermType::WORD);
-    }
-
-    TEST("suffix matching") {
-        EXPECT_EQUAL(assertMatchTermSuffix("a",      "vespa"), true);
-        EXPECT_EQUAL(assertMatchTermSuffix("spa",    "vespa"), true);
-        EXPECT_EQUAL(assertMatchTermSuffix("vespa",  "vespa"), true);
-        EXPECT_EQUAL(assertMatchTermSuffix("vvespa", "vespa"), false);
-        EXPECT_EQUAL(assertMatchTermSuffix("fspa",   "vespa"), false);
-        EXPECT_EQUAL(assertMatchTermSuffix("v",      "vespa"), false);
-    }
+TEST("parsing of test-only fuzzy term params can extract numeric values") {
+    uint8_t max_edits = 0;
+    uint32_t prefix_length = 1234;
+    std::string_view out;
+
+    std::tie(max_edits, prefix_length, out) = parse_fuzzy_params("myterm");
+    EXPECT_EQUAL(max_edits, 2u);
+    EXPECT_EQUAL(prefix_length, 0u);
+    EXPECT_EQUAL(out, "myterm");
+
+    std::tie(max_edits, prefix_length, out) = parse_fuzzy_params("{3}myterm");
+    EXPECT_EQUAL(max_edits, 3u);
+    EXPECT_EQUAL(prefix_length, 0u);
+    EXPECT_EQUAL(out, "myterm");
+
+    std::tie(max_edits, prefix_length, out) = parse_fuzzy_params("{2,70}myterm");
+    EXPECT_EQUAL(max_edits, 2u);
+    EXPECT_EQUAL(prefix_length, 70u);
+    EXPECT_EQUAL(out, "myterm");
+}
+
+TEST("verify correct term parsing") {
+    ASSERT_TRUE(Query::parseQueryTerm("index:term").first == "index");
+    ASSERT_TRUE(Query::parseQueryTerm("index:term").second == "term");
+    ASSERT_TRUE(Query::parseQueryTerm("term").first.empty());
+    ASSERT_TRUE(Query::parseQueryTerm("term").second == "term");
+    ASSERT_TRUE(Query::parseTerm("*substr*").first == "substr");
+    ASSERT_TRUE(Query::parseTerm("*substr*").second == TermType::SUBSTRINGTERM);
+    ASSERT_TRUE(Query::parseTerm("*suffix").first == "suffix");
+    ASSERT_TRUE(Query::parseTerm("*suffix").second == TermType::SUFFIXTERM);
+    ASSERT_TRUE(Query::parseTerm("prefix*").first == "prefix");
+    ASSERT_TRUE(Query::parseTerm("prefix*").second == TermType::PREFIXTERM);
+    ASSERT_TRUE(Query::parseTerm("#regex").first == "regex");
+    ASSERT_TRUE(Query::parseTerm("#regex").second == TermType::REGEXP);
+    ASSERT_TRUE(Query::parseTerm("%fuzzy").first == "fuzzy");
+    ASSERT_TRUE(Query::parseTerm("%fuzzy").second == TermType::FUZZYTERM);
+    ASSERT_TRUE(Query::parseTerm("term").first == "term");
+    ASSERT_TRUE(Query::parseTerm("term").second == TermType::WORD);
+}
+
+TEST("suffix matching") {
+    EXPECT_EQUAL(assertMatchTermSuffix("a",      "vespa"), true);
+    EXPECT_EQUAL(assertMatchTermSuffix("spa",    "vespa"), true);
+    EXPECT_EQUAL(assertMatchTermSuffix("vespa",  "vespa"), true);
+    EXPECT_EQUAL(assertMatchTermSuffix("vvespa", "vespa"), false);
+    EXPECT_EQUAL(assertMatchTermSuffix("fspa",   "vespa"), false);
+    EXPECT_EQUAL(assertMatchTermSuffix("v",      "vespa"), false);
+}
 
 TEST("Test basic strchrfield searchers") {
     {
@@ -654,6 +728,96 @@ TEST("utf8 flexible searcher handles regexes with explicit anchoring") {
     TEST_DO(assertString(fs, "#^foo$", "oo",   Hits()));
 }
 
+TEST("utf8 flexible searcher handles fuzzy search in uncased mode") {
+    UTF8FlexibleStringFieldSearcher fs(0);
+    // Term syntax (only applies to these tests):
+    //   %{k}term   => fuzzy match "term" with max edits k
+    //   %{k,p}term => fuzzy match "term" with max edits k, prefix lock length p
+
+    // DFA is used for k in {1, 2}
+    TEST_DO(assertString(fs, "%{1}abc",  "abc",    Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}ABC",  "abc",    Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}abc",  "ABC",    Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}Abc",  "abd",    Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}abc",  "ABCD",   Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}abc",  "abcde",  Hits()));
+    TEST_DO(assertString(fs, "%{2}abc",  "abcde",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{2}abc",  "xabcde", Hits()));
+    // Fallback to non-DFA matcher when k not in {1, 2}
+    TEST_DO(assertString(fs, "%{3}abc",  "abc",   Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3}abc",  "XYZ",   Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3}abc",  "XYZ!",  Hits()));
+}
+
+TEST("utf8 flexible searcher handles fuzzy search in cased mode") {
+    UTF8FlexibleStringFieldSearcher fs(0);
+    fs.normalize_mode(Normalizing::NONE);
+    TEST_DO(assertString(fs, "%{1}abc", "abc",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}abc", "Abc",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1}ABC", "abc",  Hits()));
+    TEST_DO(assertString(fs, "%{2}Abc", "abc",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{2}abc", "AbC",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3}abc", "ABC",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3}abc", "ABCD", Hits()));
+}
+
+TEST("utf8 flexible searcher handles fuzzy search with prefix locking") {
+    UTF8FlexibleStringFieldSearcher fs(0);
+    // DFA
+    TEST_DO(assertString(fs, "%{1,4}zoid",     "zoi",        Hits()));
+    TEST_DO(assertString(fs, "%{1,4}zoid",     "zoid",       Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,4}zoid",     "ZOID",       Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "zoid",       Hits()));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "ZoidBerg",   Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "ZoidBergg",  Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "zoidborg",   Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "zoidblergh", Hits()));
+    TEST_DO(assertString(fs, "%{2,4}zoidberg", "zoidblergh", Hits().add(0)));
+    // Fallback
+    TEST_DO(assertString(fs, "%{3,4}zoidberg", "zoidblergh", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3,4}zoidberg", "zoidbooorg", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{3,4}zoidberg", "zoidzooorg", Hits()));
+
+    fs.normalize_mode(Normalizing::NONE);
+    // DFA
+    TEST_DO(assertString(fs, "%{1,4}zoid",     "ZOID",       Hits()));
+    TEST_DO(assertString(fs, "%{1,4}ZOID",     "zoid",       Hits()));
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "zoidBerg",   Hits().add(0))); // 1 edit
+    TEST_DO(assertString(fs, "%{1,4}zoidberg", "zoidBblerg", Hits()));        // 2 edits, 1 max
+    TEST_DO(assertString(fs, "%{2,4}zoidberg", "zoidBblerg", Hits().add(0))); // 2 edits, 2 max
+    // Fallback
+    TEST_DO(assertString(fs, "%{3,4}zoidberg", "zoidBERG",   Hits()));        // 4 edits, 3 max
+    TEST_DO(assertString(fs, "%{4,4}zoidberg", "zoidBERG",   Hits().add(0))); // 4 edits, 4 max
+}
+
+TEST("utf8 flexible searcher fuzzy match with max_edits=0 implies exact match") {
+    UTF8FlexibleStringFieldSearcher fs(0);
+    TEST_DO(assertString(fs, "%{0}zoid",   "zoi",  Hits()));
+    TEST_DO(assertString(fs, "%{0,4}zoid", "zoi",  Hits()));
+    TEST_DO(assertString(fs, "%{0}zoid",   "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{0}zoid",   "ZOID", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{0,4}zoid", "ZOID", Hits().add(0)));
+    fs.normalize_mode(Normalizing::NONE);
+    TEST_DO(assertString(fs, "%{0}zoid",   "ZOID", Hits()));
+    TEST_DO(assertString(fs, "%{0,4}zoid", "ZOID", Hits()));
+    TEST_DO(assertString(fs, "%{0}zoid",   "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{0,4}zoid", "zoid", Hits().add(0)));
+}
+
+TEST("utf8 flexible searcher caps oversized fuzzy prefix length to term length") {
+    UTF8FlexibleStringFieldSearcher fs(0);
+    // DFA
+    TEST_DO(assertString(fs, "%{1,5}zoid",    "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,9001}zoid", "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{1,9001}zoid", "boid", Hits()));
+    // Fallback
+    TEST_DO(assertString(fs, "%{0,5}zoid",    "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{5,5}zoid",    "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{0,9001}zoid", "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{5,9001}zoid", "zoid", Hits().add(0)));
+    TEST_DO(assertString(fs, "%{5,9001}zoid", "boid", Hits()));
+}
+
 TEST("bool search") {
     BoolFieldSearcher fs(0);
     TEST_DO(assertBool(fs,     "true",  true, true));
diff --git a/streamingvisitors/src/vespa/vsm/searcher/fieldsearcher.h b/streamingvisitors/src/vespa/vsm/searcher/fieldsearcher.h
index c5bca6f3899..bb3aa6fdd10 100644
--- a/streamingvisitors/src/vespa/vsm/searcher/fieldsearcher.h
+++ b/streamingvisitors/src/vespa/vsm/searcher/fieldsearcher.h
@@ -46,7 +46,7 @@ public:
     explicit FieldSearcher(FieldIdT fId) noexcept : FieldSearcher(fId, false) {}
     FieldSearcher(FieldIdT fId, bool defaultPrefix) noexcept;
     ~FieldSearcher() override;
-    virtual std::unique_ptr<FieldSearcher> duplicate() const = 0;
+    [[nodiscard]] virtual std::unique_ptr<FieldSearcher> duplicate() const = 0;
     bool search(const StorageDocument & doc);
     virtual void prepare(search::streaming::QueryTermList& qtl, const SharedSearcherBuf& buf,
                          const vsm::FieldPathMapT& field_paths, search::fef::IQueryEnvironment& query_env);
diff --git a/streamingvisitors/src/vespa/vsm/searcher/strchrfieldsearcher.cpp b/streamingvisitors/src/vespa/vsm/searcher/strchrfieldsearcher.cpp
index c0a0249125f..98e88e45b3a 100644
--- a/streamingvisitors/src/vespa/vsm/searcher/strchrfieldsearcher.cpp
+++ b/streamingvisitors/src/vespa/vsm/searcher/strchrfieldsearcher.cpp
@@ -34,7 +34,7 @@ bool StrChrFieldSearcher::matchDoc(const FieldRef & fieldRef)
     }
   } else {
     for (auto qt : _qtl) {
-      if (fieldRef.size() >= qt->termLen() || qt->isRegex()) {
+      if (fieldRef.size() >= qt->termLen() || qt->isRegex() || qt->isFuzzy()) {
         _words += matchTerm(fieldRef, *qt);
       } else {
         _words += countWords(fieldRef);
@@ -49,8 +49,8 @@ size_t StrChrFieldSearcher::shortestTerm() const
   size_t mintsz(_qtl.front()->termLen());
   for (auto it=_qtl.begin()+1, mt=_qtl.end(); it != mt; it++) {
     const QueryTerm & qt = **it;
-    if (qt.isRegex()) {
-        return 0; // Must avoid "too short query term" optimization when using regex
+    if (qt.isRegex() || qt.isFuzzy()) {
+        return 0; // Must avoid "too short query term" optimization when using regex or fuzzy
     }
     mintsz = std::min(mintsz, qt.termLen());
   }
diff --git a/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.cpp b/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.cpp
index c6deb6eacd1..d648d2e252e 100644
--- a/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.cpp
+++ b/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.cpp
@@ -1,5 +1,6 @@
 // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 #include "utf8flexiblestringfieldsearcher.h"
+#include <vespa/searchlib/query/streaming/fuzzy_term.h>
 #include <vespa/searchlib/query/streaming/regexp_term.h>
 #include <cassert>
 
@@ -40,6 +41,19 @@ UTF8FlexibleStringFieldSearcher::match_regexp(const FieldRef & f, search::stream
 }
 
 size_t
+UTF8FlexibleStringFieldSearcher::match_fuzzy(const FieldRef & f, search::streaming::QueryTerm & qt)
+{
+    auto* fuzzy_term = qt.as_fuzzy_term();
+    assert(fuzzy_term != nullptr);
+    // TODO delegate to matchTermExact if max edits == 0?
+    //  - needs to avoid folding to have consistent normalization semantics
+    if (fuzzy_term->is_match({f.data(), f.size()})) {
+        addHit(qt, 0);
+    }
+    return countWords(f);
+}
+
+size_t
 UTF8FlexibleStringFieldSearcher::matchTerm(const FieldRef & f, QueryTerm & qt)
 {
     if (qt.isPrefix()) {
@@ -57,6 +71,9 @@ UTF8FlexibleStringFieldSearcher::matchTerm(const FieldRef & f, QueryTerm & qt)
     } else if (qt.isRegex()) {
         LOG(debug, "Use regexp match for term '%s:%s'", qt.index().c_str(), qt.getTerm());
         return match_regexp(f, qt);
+    } else if (qt.isFuzzy()) {
+        LOG(debug, "Use fuzzy match for term '%s:%s'", qt.index().c_str(), qt.getTerm());
+        return match_fuzzy(f, qt);
     } else {
         if (substring()) {
             LOG(debug, "Use substring match for term '%s:%s'", qt.index().c_str(), qt.getTerm());
diff --git a/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.h b/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.h
index cd1715ad158..a5f6ad46246 100644
--- a/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.h
+++ b/streamingvisitors/src/vespa/vsm/searcher/utf8flexiblestringfieldsearcher.h
@@ -25,6 +25,7 @@ private:
     size_t matchTerms(const FieldRef & f, size_t shortestTerm) override;
 
     size_t match_regexp(const FieldRef & f, search::streaming::QueryTerm & qt);
+    size_t match_fuzzy(const FieldRef & f, search::streaming::QueryTerm & qt);
 
 public:
     std::unique_ptr<FieldSearcher> duplicate() const override;
diff --git a/streamingvisitors/src/vespa/vsm/vsm/fieldsearchspec.cpp b/streamingvisitors/src/vespa/vsm/vsm/fieldsearchspec.cpp
index 9c8bb2f185a..63d2007cecf 100644
--- a/streamingvisitors/src/vespa/vsm/vsm/fieldsearchspec.cpp
+++ b/streamingvisitors/src/vespa/vsm/vsm/fieldsearchspec.cpp
@@ -133,7 +133,7 @@ FieldSearchSpec::reconfig(const QueryTerm & term)
             (term.isSuffix() && _arg1 != "suffix") ||
             (term.isExactstring() && _arg1 != "exact") ||
             (term.isPrefix() && _arg1 == "suffix") ||
-            term.isRegex())
+            (term.isRegex() || term.isFuzzy()))
         {
             _searcher = std::make_unique<UTF8FlexibleStringFieldSearcher>(id());
             propagate_settings_to_searcher();