Lexer Implementation in Rust - `PhantomData` Awkwardness I've been working on a Tokeniser/Lexer in Rust. I would like to have the tokeniser take input from different sources, such as files or in-memory strings. To abstract over this concern i've created a trait Source. This has left me with a wonky situation where I appear to need a PhantomData member in the token iterator. I've created a cut-down example here:

/// Source of Characters
///
/// In this example all that a source can do is be sliced to retrieve
/// a subsection of the overall character buffer.
trait Source&lt;'a&gt; {
    /// Character at Offset
    ///
    /// Gets the character at the given offset in the buffer and
    /// returns it. If no character is available at that offset `None`
    /// is returned.
    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt;;

    /// Slice the Source Buffer
    fn slice(&amp;self, start: usize, end: usize) -&gt; &amp;'a str;
}

/// Source of Characters from a `str` Slice
struct StringSource&lt;'a&gt; {
    pub buff: &amp;'a str
}

/// Implementation of the Source trait.
impl&lt;'a&gt; Source&lt;'a&gt; for StringSource&lt;'a&gt; {
    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt; {
        self.buff[offset..].chars().nth(0).map(|ch| { (ch, offset + ch.len_utf8()) })
    }

    fn slice(&amp;self, start: usize, end: usize) -&gt; &amp;'a str {
        &amp;self.buff[start..end]
    }
}

/// Token Iterator Implementation
///
/// This token iterator takes a given source and steps through it returning string slices for each token
struct TokenIter&lt;'a, S&gt;
    where S: Source&lt;'a&gt;,
          S: 'a
{
    source: S,
    idx: usize,
    phantom: ::std::marker::PhantomData&lt;&amp;'a ()&gt;,
}

impl&lt;'a, S&gt; TokenIter&lt;'a, S&gt;
    where S: Source&lt;'a&gt;
{
    /// Create a Token Iterator from a Source
    fn new(source: S) -&gt; Self {
        TokenIter {
            source: source,
            idx: 0,
            phantom: ::std::marker::PhantomData,
        }
    }
}

/// Token Iterators implement `Iterator`
impl&lt;'a, S&gt; Iterator for TokenIter&lt;'a, S&gt;
    where S: Source&lt;'a&gt;
{
    type Item = &amp;'a str;

    fn next(&amp;mut self) -&gt; Option&lt;Self::Item&gt; {
        let ts = self.idx;
        self.source.at(ts).map(|(_ch, next)| {
            self.idx = next;
            // Imagine a regex state machine is run here to produce a token
            // rather than just returning single-character tokens.
            self.source.slice(ts, next)
        })
    }
}

fn main() {
    let source = StringSource{ buff: "hello world" };
    let iter = TokenIter::new(source);
    println!("{:?}", iter.collect::&lt;Vec&lt;_&gt;&gt;());
}


Run it here:
https://is.gd/OCL91u

Is there a nicer way to express the source buffer lifetime 'a so that I don't need a PhantomData member or this bit of funky lifetime constraints:

where S: Source&lt;'a&gt;,
      S: 'a
such as files or in-memory strings


I'm going to give the advice that people dread: I don't think your abstraction is going to work here. When I first read "in-memory strings", I expected a String, not a &amp;str. Since you mentioned a file, I think it's still a valid comparison. I don't believe you can implement this trait for such a type:

struct OwnedStringSource {
    pub buff: String,
}

impl&lt;'a&gt; Source&lt;'a&gt; for OwnedStringSource {
    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt; { None }

    fn slice(&amp;self, start: usize, end: usize) -&gt; &amp;'a str {
        // Hmm.... what to put here?
    }
}


That is, there's no way to say a reasonable lifetime for 'a. I also think that it's the same root problem as Can I write an Iterator that yields a reference into itself?.

Aside from that, your original error was probably something like:

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
   --&gt; src/main.rs:117:6
    |
117 | impl&lt;'a, S&gt; Iterator for TokenIter&lt;S&gt;
    |      ^^ unconstrained lifetime parameter


The best advice I've gotten about that specific error was helpful... after thinking about it for a while. Paraphrased and elided for this situation:


  what [the error is] trying to tell you is that it cannot get [the generic type] back from either
  the implemented trait [...] or the type implemented on [...]. [The where clause]
  is not enough to extract [the generic] from [the type] because one [...] type can have multiple
  [...] impls with various arguments


Instead, I might suggest that you use an associated type instead of the generic parameter:

trait Source {
    type Slice;

    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt;;
    fn slice(&amp;self, start: usize, end: usize) -&gt; Self::Slice;
}


This separates the lifetimes from the trait. Specific implementations can still participate in it:

impl&lt;'a&gt; Source for StringSource&lt;'a&gt; {
    type Slice = &amp;'a str;
    // ...
}


And you can just bubble up the inner type out of the iterator:

impl&lt;'a, S&gt; Iterator for TokenIter&lt;S&gt;
    where S: Source,
{
    type Item = S::Slice;
    // ...
}


You potentially might need to add extra bounds on that generic there (S::Slice: AsRef&lt;str&gt;) depending on what you need to be able to do with the slice in the iterator implementation.



trait Source {
    type Slice;

    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt;;
    fn slice(&amp;self, start: usize, end: usize) -&gt; Self::Slice;
}

struct StringSource&lt;'a&gt; {
    pub buff: &amp;'a str
}

impl&lt;'a&gt; Source for StringSource&lt;'a&gt; {
    type Slice = &amp;'a str;

    fn at(&amp;self, offset: usize) -&gt; Option&lt;(char, usize)&gt; {
        self.buff[offset..].chars().nth(0).map(|ch| { (ch, offset + ch.len_utf8()) })
    }

    fn slice(&amp;self, start: usize, end: usize) -&gt; &amp;'a str {
        &amp;self.buff[start..end]
    }
}

struct TokenIter&lt;S&gt; {
    source: S,
    idx: usize,
}

impl&lt;S&gt; TokenIter&lt;S&gt; {
    fn new(source: S) -&gt; Self {
        TokenIter {
            source: source,
            idx: 0,
        }
    }
}

impl&lt;S&gt; Iterator for TokenIter&lt;S&gt;
    where S: Source,
{
    type Item = S::Slice;

    fn next(&amp;mut self) -&gt; Option&lt;Self::Item&gt; {
        let ts = self.idx;
        self.source.at(ts).map(|(_ch, next)| {
            self.idx = next;
            self.source.slice(ts, next)
        })
    }
}

fn main() {
    let source = StringSource{ buff: "hello world" };
    let iter = TokenIter::new(source);
    println!("{:?}", iter.collect::&lt;Vec&lt;_&gt;&gt;());
}