Trait with associate type working over iterators


#1

I am trying to implement a trait with an associate type. This trait tries to implement a function that manipulates iterators over that type. However it fails to compile with the error "std::iter::Iterator<Item=<Self as StateMachine>::Item> does not have a constant size known at compile-time". I have tried different ways to no avail.

Here is the code (with some commented alternatives) of the trait:

trait StateMachine
{
	type Item:Sized;
	//type Iterator:Iterator+Sized = Iterator<Item=Self::Item>;
	fn trans(&self, state:usize, elem:Self::Item) -> (usize,Action);

	fn replace_all(&self, source:Iterator<Item=Self::Item>, replacement:Iterator<Item=Self::Item>) -> ReplacerIt<Self::Item,Iterator<Item=Self::Item>>
	//fn replace_all<I>(&self, source:I, replacement:I) -> ReplacerIt<Self::Item,I> where I:Iterator<Item=Self::Item>
	//fn replace_all(&self, source:Self::Iterator, replacement:Self::Iterator) -> ReplacerIt<Self::Item,Self::Iterator>
	{
		//ReplacerIt::<Self::Item,Iterator<Item=Self::Item>>
		ReplacerIt::<Self::Item,Self::Iterator>
		{
			machine:self,
			source,
			replacement,
			state:State::start(),
			flushing: false,
			insert: None,
		}
	}
}

Is it possible to implement this trait or should I look for a completely different way to implement the functionality?


#2

Your problem is that Iterator<Item=Self::Item> is a trait, not type of a known size.

What you need is something akin to this:

fn replace<I: Iterator<Item=Self::Item>>(&self, source: I, replacement: I) -> ReplacerIt<Self::Item, I>

I is a generic type of a known compile time size, which implements Iterator.


#3

I see. But then there appears an error at the declaration of the ReplacerIt struct, which has reference to a thing that implements the trait.

This is the code of the struct:

struct ReplacerIt<'a,T:'a+Sized, I> where I:'a+Iterator<Item=T>+Sized
{
	machine: &'a StateMachine<Item=T>,
	source: I,
	replacement: I,
	state: State<T>,
	flushing: bool,
	insert: Option<I>,
}

The error states that “method replace_all has generic type parameters” and hence “the trait StateMachine cannot be made into an object”.


#4

Unless you have a specific reason to want a trait object here, you should add another generic type parameter to ReplacerIt:

struct ReplacerIt<'a, S: StateMachine<Item=T> + 'a, T: 'a + Sized, I> where I:'a+Iterator<Item=T>+Sized {
   machine: &'a S,
   ...
}

#5

Thank you both! It still required a little tweaking, but it works now.

The working code reads now this way:

trait StateMachine
{
	type Item:Sized;
	fn trans(&self, state:usize, elem:Self::Item) -> (usize,Action);

	fn replace_all<I:Iterator<Item=Self::Item>>(&self, source:I, replacement:I) -> ReplacerIt<Self::Item,Self,I> where Self:Sized
	{
		ReplacerIt::<Self::Item,Self,I>
		{
			machine:self,
			source,
			replacement,
			state:State::start(),
			flushing: false,
			insert: None,
		}
	}
}
struct ReplacerIt<'a,T:'a+Sized, S: StateMachine<Item=T>+'a, I> where I:'a+Iterator<Item=T>+Sized
{
	machine: &'a S,
	source: I,
	replacement: I,
	state: State<T>,
	flushing: bool,
	insert: Option<I>,
}

#6

A few tangential suggestions:

  1. Sized is a default bound for generic types in most positions. Most notably, it’s not the default for the trait itself (but you’re holding it behind a reference in the ReplacerIt anyway).
  2. You don’t need to specify the generic types of ReplacerIt when you return it in replace_all.
  3. Be a bit more liberal with whitespace when declaring generic types and their bounds :slight_smile:

#7

Right. I filled the traits with Sized aiming to remove those unknown size errors. Now I see that the only necessary ‘Sized’ is the ‘where Self:Sized’ on replace_all, which I am not even sure what it means. I guess that replace_all can only be called from a StateMachine of specific size.

Now that it compiles I can more calmly do aesthetic improvements like you suggest.


#8

You don’t need it there either - you just need to modify ReplacerIt generic type bounds to ReplacerIt<..., S: StateMachine + ?Sized + 'a, ...>.


#9

Ok, that works too. Does using ‘?Sized’ provide an actual advantage? I have not yet fully understood the details of the Sized trait.


#10

It depends. One can argue that accepting ?Sized makes your types more flexible (ie they can work with more types). Whether the flexibility is actually useful depends on the intended use cases.

In this case, you may actually want to keep Self: Sized requirement on replace_all if you intend to make StateMachine trait objects. There are certain rules (restrictions) on a trait to make it eligible for trait object formation (aka object safety), and one of them is no generic methods :slight_smile:. Putting a where Self: Sized bound on that method “removes” the method from the trait object interface (ie it’s not callable on a trait object) and makes the trait object safe (assuming other requirements are met). You can take a look at http://huonw.github.io/blog/2015/01/object-safety/ to explore object safety in more depth.


#11

Thanks. That makes things more clear for me.


#12

No problem. I forgot to mention that the canonical example of slapping where Self: Sized bounds on trait methods to allow the rest of the trait to be an object is exemplified by std’s Iterator trait.