Make it possible to stream the terms matching an Automaton #297

drusellers · 2018-05-09T03:30:43Z

Closes #273

Ok, so I've started down the path, but I'm for sure lost.

Not sure how I would test with Automaton - still reading up on the fst code there
Not sure how to use the fst StreamBuilder, but it feels close on the code implementation, but I have compiler issues, which could just be about spreading the generic type love around more.

fulmicoton · 2018-05-09T03:35:37Z

src/termdict/termdict.rs

@@ -101,7 +102,7 @@ fn open_fst_index(source: ReadOnlySource) -> fst::Map {
 /// The term dictionary contains all of the terms in
 /// `tantivy index` in a sorted manner.
 ///
-/// The `Fst` crate is used to assoicated terms to their
+/// The `Fst` crate is used to assoicate terms to their


hehe there is still the typo :)

ha! that's what I get. ;p

can you fix the typo:

assoicate => associate

fulmicoton · 2018-05-09T03:36:35Z

src/termdict/termdict.rs

+        use fst::map;
+
+        // given an Automaton and a fst::Map (fst_index)
+        // how can I generate a streambuilder?


I don't understand the question here???

oh gotcha:

pub fn search<'a, A: Automaton>(&'a self, automaton: A) -> TermStreamerBuilder<'a, A> { let sb = self.fst_index.search(automaton); TermStreamerBuilder::<A>::new(self, sb) }

fulmicoton · 2018-05-09T03:40:02Z

Can you push those to the tantivy repo as feature branches in the future? This will make it possible for me to commit stuff.

drusellers · 2018-05-09T12:54:26Z

Can you push those to the tantivy repo as feature branches in the future? This will make it possible for me to commit stuff.

Absolutely. :) Do you have any preferences for branch names in the tantivy repo?

Also, for the life of me I can't get the test to compile. :/

error[E0277]: the trait bound `fst_levenshtein::Levenshtein: fst::Automaton` is not satisfied
   --> src/termdict/mod.rs:459:31
    |
459 |         let range = term_dict.search(automaton).into_stream();
    |                               ^^^^^^ the trait `fst::Automaton` is not implemented for `fst_levenshtein::Levenshtein`

But it appears to be implemented right here.

https://github.com/BurntSushi/fst/blob/master/fst-levenshtein/src/lib.rs#L142

drusellers · 2018-05-11T03:44:40Z

Should I be using fst_levenshtein::Levenshtein to test this code or something else?

fulmicoton · 2018-05-11T03:55:23Z

Alternatively you can use https://github.com/tantivy-search/levenshtein-automata or write your own. You still have a compilation error?

drusellers · 2018-05-11T03:56:24Z

Yeah, same error. Then I saw your impl of Levenshtein and wondered if that is a better "Test"

drusellers · 2018-05-11T04:11:29Z

error[E0277]: the trait bound `levenshtein_automata::DFA: fst::Automaton` is not satisfied
   --> src/termdict/mod.rs:464:31
    |
464 |         let range = term_dict.search(dfa).into_stream();
    |                               ^^^^^^ the trait `fst::Automaton` is not implemented for `levenshtein_automata::DFA`

:(

fulmicoton · 2018-05-11T04:34:02Z

Hmmm.... The only think I can think of, is version of fst conflicting for some reason.
Let me try on my computer.

fulmicoton · 2018-05-11T04:37:08Z

Yeah it compiles on my computer. Maybe try rm -f Cargo.lock?

drusellers · 2018-05-11T04:37:11Z

Ok, did a cargo clean, cargo update - no love. I could try updating fst to 0.3.0

drusellers · 2018-05-11T04:37:42Z

@fulmicoton sweet. one step in the right direction. :)

drusellers · 2018-05-11T04:41:23Z

cargo 1.26.0 (0e7c5a931 2018-04-06) FWIW

drusellers · 2018-05-11T04:43:58Z

cargo build is 👍
cargo test is 👎

just to be clear

fulmicoton · 2018-05-11T04:55:37Z

Ok cargo test fails on my computer as well. Let me check if I can solve that riddle.

fulmicoton · 2018-05-11T05:17:36Z

It works if you change tantivy's fst version to 0.3.

If you want to use tantivy's levenshtein_automata crate, be careful.
The implementation of fst::Automaton is guarded by a feature called fst_automaton.

So

levenshtein_automata = {version="0.1", features=["fst_automaton"]}

is the right way to add the dependency in tantivy's Cargo.toml

coveralls · 2018-05-11T13:45:24Z

Coverage increased (+0.02%) to 91.386% when pulling f9091a4 on drusellers:fuzzy into 82d8741 on tantivy-search:master.

drusellers · 2018-05-11T16:05:52Z

Cargo.toml

@@ -28,6 +29,7 @@ serde_derive = "1.0"
 serde_json = "1.0"
 num_cpus = "1.2"
 itertools = "0.5.9"
+levenshtein_automata = {version="0.1", features=["fst_automaton"]}


I should probably make this optional?

No that's ok.

drusellers · 2018-05-11T16:06:19Z

Cargo.toml

@@ -17,7 +17,8 @@ byteorder = "1.0"
 lazy_static = "0.2.1"
 tinysegmenter = "0.1.0"
 regex = "0.2"
-fst = {version="0.2", default-features=false}
+fst = {version="0.3", default-features=false}
+fst-levenshtein = "0.2"


Should this be optional - maybe behind a fuzzy feature gate until the whole feature is done?

we can remove fst-levenshtein and keep only levenshtein-automata. The latter does the same thing, but faster, better and stronger.

drusellers · 2018-05-11T16:07:12Z

src/directory/mmap_directory.rs

+        MmapReadOnly::open(&file)
+            .map(Some)
+            .map_err(|e| From::from(IOError::with_path(full_path.to_owned(), e)))
+    }


I don't understand why this change was required when I updated fst -> 0.3 (could be new rust stable too) - but would want someone else's eyes on it.

You mean the unsafe ? There is a comment about it in the fst crate.
It was modified in a non-backward compatible way in 0.3. As a general rule any change from 0.x to 0.y may change backward compatibility.
For version > 1.x, backward compatilibility is respected as long as the major version does not change.

Cool, since it was an unsafe change I just wanted someone else to look at it. :)

(To be really "philosophically" correct here, we should probably make the caller unsafe... I think this is borderline enough to not care.)

drusellers · 2018-05-11T16:07:19Z

src/directory/read_only_source.rs

@@ -42,7 +42,7 @@ impl ReadOnlySource {
    pub fn as_slice(&self) -> &[u8] {
        match *self {
            #[cfg(feature = "mmap")]
-            ReadOnlySource::Mmap(ref mmap_read_only) => unsafe { mmap_read_only.as_slice() },
+            ReadOnlySource::Mmap(ref mmap_read_only) => mmap_read_only.as_slice(),


I don't understand why this change was required when I updated fst -> 0.3 (could be new rust stable too) - but would want someone else's eyes on it.

fulmicoton · 2018-05-11T17:44:24Z

src/termdict/streamer.rs

 /// a range of terms that should be streamed.
-pub struct TermStreamerBuilder<'a> {
+pub struct TermStreamerBuilder<'a, A>


make A=AlwaysMatch a default

fulmicoton · 2018-05-11T17:44:36Z

src/termdict/streamer.rs

@@ -58,15 +65,21 @@ impl<'a> TermStreamerBuilder<'a> {

 /// `TermStreamer` acts as a cursor over a range of terms of a segment.
 /// Terms are guaranteed to be sorted.
-pub struct TermStreamer<'a> {
+pub struct TermStreamer<'a, A>


make A=AlwaysMatch a default

fulmicoton · 2018-05-11T17:44:57Z

src/termdict/merger.rs

 use schema::Term;
 use std::cmp::Ordering;
 use std::collections::BinaryHeap;
 use termdict::TermOrdinal;
 use termdict::TermStreamer;

 pub struct HeapItem<'a> {
-    pub streamer: TermStreamer<'a>,
+    pub streamer: TermStreamer<'a, AlwaysMatch>,
