Trait tantivy_fst::Streamer

pub trait Streamer<'a> {
    type Item: 'a;
    fn next(&'a mut self) -> Option<Self::Item>;
}

Streamer describes a "streaming iterator."

It provides a mechanism for writing code that is generic over streams produced by this crate.

Note that this is strictly less useful than Iterator because the item associated type is bound to a specific lifetime. However, this does permit us to write some generic code over streams that produce values tied to the lifetime of the stream.

Some form of stream abstraction is inherently required for this crate because elements in a finite state transducer are produced by iterating over the structure. The alternative would be to create a new allocation for each element iterated over, which would be prohibitively expensive.

Usage & motivation

Streams are hard to use because they don't fit into Rust's current type system very well. They are so hard to use that this author loathes having a publically defined trait for it. Nevertheless, they do just barely provide a means for composing multiple stream abstractions with different concrete types. For example, one might want to take the union of a range query stream with a stream that has been filtered by a regex. These streams have different concrete types. A Streamer trait allows us to write code that is generic over these concrete types. (All of the set operations are implemented this way.)

A problem with streams is that the trait is itself parameterized by a lifetime. In practice, this makes them very unergonomic because specifying a Streamer bound generally requires a higher-ranked trait bound. This is necessary because the lifetime can't actually be named in the enclosing function; instead, the lifetime is local to iteration itself. Therefore, one must assert that the bound is valid for any particular lifetime. This is the essence of higher-rank trait bounds.

Because of this, you might expect to see lots of bounds that look like this:

fn takes_stream<T, S>(s: S)
    where S: for<'a> Streamer<'a, Item=T>
{
}

There are three different problems with this declaration:

1. S is not bound by any particular lifetime itself, and most streams probably contain a reference to an underlying finite state transducer.
2. It is often convenient to separate the notion of "stream" with "stream constructor." This represents a similar split found in the standard library for Iterator and IntoIterator, respectively.
3. The Item=T is invalid because Streamer's associated type is parameterized by a lifetime and there is no way to parameterize an arbitrary type constructor. (In this context, T is the type constructor, because it will invariably require a lifetime to become a concrete type.)

With that said, we must revise our possibly-workable bounds to a giant scary monster:

fn takes_stream<'f, I, S>(s: I)
    where I: for<'a> IntoStreamer<'a, Into=S, Item=(&'a [u8], Output)>,
          S: 'f + for<'a> Streamer<'a, Item=(&'a [u8], Output)>
{
}

We addressed the above points correspondingly:

1. S is now bound by 'f, which corresponds to the lifetime (possibly 'static) of the underlying stream.
2. The I type parameter has been added to refer to a type that knows how to build a stream. Notice that neither of the bounds for I or S share a lifetime parameter. This is because the higher rank trait bound specifies it works for any particular lifetime.
3. T has been replaced with specific concrete types. Note that these concrete types are duplicated. With iterators, we could use Item=S::Item in the bound for I, but one cannot access an associated type through a higher-ranked trait bound. Therefore, we must duplicate the item type.

As you can see, streams offer little flexibility, little ergonomics and a lot of hard to read trait bounds. The situation is lamentable, but nevertheless, without them, we would not be able to compose streams by leveraging the type system.

A redeemable quality is that these same exact trait bounds (modulo some tweaks in the Item associated type) appear in many places in this crate without much variation. Therefore, once you grok it, it's mostly easy to pattern match it with "oh I need a stream." My hope is that clear documentation and examples make these complex bounds easier to burden.

Stretching this abstraction further with Rust's current type system is not advised.

Associated Types

type Item: 'a

The type of the item emitted by this stream.

Loading content...

Required methods

fn next(&'a mut self) -> Option<Self::Item>

Emits the next element in this stream, or None to indicate the stream has been exhausted.

It is not specified what a stream does after None is emitted. In most cases, None should be emitted on every subsequent call.

Loading content...

Implementors

impl<'a, 'f> Streamer<'a> for tantivy_fst::raw::Difference<'f>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'f> Streamer<'a> for tantivy_fst::raw::Intersection<'f>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'f> Streamer<'a> for tantivy_fst::raw::SymmetricDifference<'f>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'f> Streamer<'a> for tantivy_fst::raw::Union<'f>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for tantivy_fst::map::Difference<'m>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for tantivy_fst::map::Intersection<'m>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for Keys<'m>

type Item = &'a [u8]

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for tantivy_fst::map::SymmetricDifference<'m>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for tantivy_fst::map::Union<'m>

type Item = (&'a [u8], &'a [IndexedValue])

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm> Streamer<'a> for Values<'m>

type Item = u64

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm, A: 'a + Automaton> Streamer<'a> for tantivy_fst::map::StreamWithState<'m, A> where
    A::State: Clone, 

type Item = (&'a [u8], u64, A::State)

fn next(&'a mut self) -> Option<Self::Item>

impl<'a, 'm, A: Automaton> Streamer<'a> for tantivy_fst::map::Stream<'m, A>

type Item = (&'a [u8], u64)

fn next(&'a mut self) -> Option<Self::Item>

impl<'f, 'a, A: 'a + Automaton> Streamer<'a> for tantivy_fst::raw::StreamWithState<'f, A> where
    A::State: Clone, 

type Item = (&'a [u8], Output, A::State)

fn next(&'a mut self) -> Option<Self::Item>

impl<'f, 'a, A: Automaton> Streamer<'a> for tantivy_fst::raw::Stream<'f, A>

type Item = (&'a [u8], Output)

fn next(&'a mut self) -> Option<Self::Item>

Loading content...