1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/// 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
    }
}