tantivy_fst/

stream.rs

/// 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:
///
/// ```ignore
/// 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:
///
/// ```ignore
/// 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.
pub trait Streamer<'a> {
    /// The type of the item emitted by this stream.
    type Item: 'a;

    /// 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.
    fn next(&'a mut self) -> Option<Self::Item>;
}

/// IntoStreamer describes types that can be converted to streams.
///
/// This is analogous to the `IntoIterator` trait for `Iterator` in
/// `std::iter`.
pub trait IntoStreamer<'a> {
    /// The type of the item emitted by the stream.
    type Item: 'a;
    /// The type of the stream to be constructed.
    type Into: Streamer<'a, Item = Self::Item>;

    /// Construct a stream from `Self`.
    fn into_stream(self) -> Self::Into;
}

impl<'a, S: Streamer<'a>> IntoStreamer<'a> for S {
    type Item = S::Item;
    type Into = S;

    fn into_stream(self) -> S {
        self
    }
}