Lifetimes for generalizing trait implementation from &T to AsRef

Question

I have some problems generalizing a trait working for &str to other string types (e.g. Rc<str>, Box<str>,String).

First of all my example function should work for:

assert_eq!(count("ababbc", 'a'), 2);                // already working
assert_eq!(count(Rc::from("ababbc"), 'a'), 2);      // todo
assert_eq!(count("ababbc".to_string(), 'a'), 2);    // todo

This is the working code, which makes the first test run:

pub trait Atom: Copy + Eq + Ord + Display + Debug {}
impl Atom for char {}

pub trait Atoms<A, I>
where
  I: Iterator<Item = A>,
  A: Atom,
{
  fn atoms(&self) -> I;
}

impl<'a> Atoms<char, std::str::Chars<'a>> for &'a str {
  fn atoms(&self) -> std::str::Chars<'a> {
    self.chars()
  }
}

pub fn count<I, A, T>(pattern: T, item: A) -> usize
where
  A: Atom,
  I: Iterator<Item = A>,
  T: Atoms<A, I>,
{
  pattern.atoms().filter(|i| *i == item).count()
}

To make the next tests run, I changed the signature of count and Atoms in following way:

pub trait Atoms<'a, A, I>
where
  I: Iterator<Item = A> + 'a,
  A: Atom,
{
  fn atoms<'b>(&'b self) -> I
  where
    'b: 'a;
}

impl<'a, S> Atoms<'a, char, std::str::Chars<'a>> for S
where
  S: AsRef<str> + 'a,
{
  fn atoms<'b>(&'b self) -> std::str::Chars<'b>
  where
    'b: 'a,
  {
    self.as_ref().chars()
  }
}

but now the function count does not compile any more:

pub fn count<'a, I, A, T>(pattern: T, item: A) -> usize
where
  A: Atom,
  I: Iterator<Item = A> + 'a,
  T: Atoms<'a, A, I>,
{
  pattern.atoms().filter(|i| *i == item).count()
}

Playground-Link

The compiler error is: the parameter type 'T' may not live long enough ... consider adding an explicit lifetime bound...: 'T: 'a'. This is not completely understandable for me, so I tried to apply the help T: Atoms<'a, A, I> + 'a. Now the error is: 'pattern' does not live long enough ... 'pattern' dropped here while still borrowed.

Since the latter error also occurs without implementations of Atoms and by just replacing the function body by pattern.atoms();return 1; I suspect that the type signature of Atoms is not suitable for my purpose.

Has anybody a hint what could be wrong with the type signature of Atoms or count?

Answer 1

trait Atoms<'a, A, I> where I: Iterator<Item = A> + 'a ...

By writing this, you're requiring the iterator to outlive the lifetime 'a. Since 'a is part of the trait's generic parameters, it must be a lifetime that extends before you start using (implicitly) <String as Atoms<'a, char, std::str::Chars>>::atoms. This directly contradicts the idea of returning a new iterator object, since that object did not exist before the call to atoms().

Unfortunately, I'm not sure how to rewrite this so that it will work, without generic associated types (a feature not yet stabilized), but I hope that at least this explanation of the problem helps.

Answer 2

I hope I clarify at least some parts of the problem. After doing some internet research on HRTBs and GATs I come to the conclusion that my problem is hardly solvable with stable rust.

The main problem is that one cannot

• have a trait with different lifetime signature than its implementations
• keep lifetimes generic in a trait for later instantiation in the implementation
• limit the upper bound of a results lifetime if it is owned

I tried several approaches to but most evolve to fail:

• at compiling the implementation (because the implementations lifetimes conflict with those of the trait)
• at compiling the caller of the trait because a compiling implementation limits the lifetimes in a way, that no object can satisfy them.

At last I found two solutions:

Implement the trait for references

• the function atoms(self) does now expect Self and not &Self
• Atoms<A,I> is implemented for &'a str and &'a S where S:AsRef<str>

This gives us control of the lifetimes of the self objects ('a) and strips the lifetime completely from the trait.

The disadvantage of this approach is that we have to pass references to our count function even for smart references.

Playground-Link

use std::fmt::Display;
use std::fmt::Debug;

pub trait Atom: Copy + Eq + Ord + Display + Debug {}

impl Atom for char {}

pub trait Atoms<A, I>
where
  I: Iterator<Item = A>,
  A: Atom,
{
  fn atoms(self) -> I;
}

impl<'a> Atoms<char, std::str::Chars<'a>> for &'a str {
  fn atoms(self) -> std::str::Chars<'a> {
    self.chars()
  }
}

impl<'a, S> Atoms<char, std::str::Chars<'a>> for &'a S
where
  S: AsRef<str>,
{
  fn atoms(self) -> std::str::Chars<'a> {
    self.as_ref().chars()
  }
}

pub fn count<I, A, T>(pattern: T, item: A) -> usize
where
  A: Atom,
  I: Iterator<Item = A>,
  T: Atoms<A, I>,
{
  pattern.atoms().filter(|i| *i == item).count()
}

#[cfg(test)]
mod tests {

  use std::rc::Rc;

  use super::*;

  #[test]
  fn test_example() {
    assert_eq!(count("ababbc", 'a'), 2);

    assert_eq!(count(&"ababbc".to_string(), 'a'), 2);
    assert_eq!(count(&Rc::from("ababbc"), 'a'), 2);
  }
}

Switch to Generic Associated Types (unstable)

• reduce the generic type Atoms<A,I> to an type Atoms<A> with an generic associated type I<'a> (which is instantiable at implementations)
• now the function count can refer to the lifetime of I like this fn atoms<'a>(&'a self) -> Self::I<'a>
• and all implementations just have to define how the want to map the lifetime 'a to their own lifetime (for example to Chars<'a>)

In this case we have all lifetime constraints in the trait, the implementation can consider to map this lifetime or ignore it. The trait, the implementation and the call site are concise and do not require references or helper lifetimes.

The disadvantage of this solution is that it is unstable, I do not know whether this means that runtime failures would probably occur or that api could change (or both). You will have to activate #![feature(generic_associated_types)] to let it run.

Playground-Link

use std::{fmt::Display, str::Chars};
use std::{fmt::Debug, rc::Rc};

pub trait Atom: Copy + Eq + Ord + Display + Debug {}

impl Atom for char {}

pub trait Atoms<A>
where
  A: Atom,
{
  type I<'a>: Iterator<Item = A>;

  fn atoms<'a>(&'a self) -> Self::I<'a>;
}

impl Atoms<char> for str
{
  type I<'a> = Chars<'a>;

  fn atoms<'a>(&'a self) -> Chars<'a> {
    self.chars()
  }
}

impl <S> Atoms<char> for S
where
  S: AsRef<str>,
{
  type I<'a> = Chars<'a>;

  fn atoms<'a>(&'a self) -> Chars<'a> {
    self.as_ref().chars()
  }
}

pub fn count<A, S>(pattern: S, item: A) -> usize
where
  A: Atom,
  S: Atoms<A>,
{
  pattern.atoms().filter(|i| *i == item).count()
}

#[cfg(test)]
mod tests {

  use std::rc::Rc;

  use super::*;

  #[test]
  fn test_example() {
    assert_eq!(count("ababbc", 'a'), 2);
    assert_eq!(count("ababbc".to_string(), 'a'), 2);
    assert_eq!(count(Rc::from("ababbc"), 'a'), 2);
  }
}