A trait inheriting Ord


#1

I want to sort a vector of objects with a given trait. So I tried adding ‘Ord’ to the trait. However this produces error E0038, that the trait cannot be made into an object because the use of Self as a type parameter.

The relevant portion of code:

trait RegEx<T:Ord>: Ord
{
	fn to_string(&self, t_to_string:&Fn(&T)->String )->String;
}
struct Disjunction<T:Ord>
{
	values: Vec<Rc<RegEx<T>>>,
}
impl<T:Ord> RegEx<T> for Disjunction<T>
{
	...
}

Here I want to sort the elements of the disjunction and remove repeated ones in order to have a good normal form. Each regular expression is composed of more of them, as a tree, ending with literals of type T.


#2

Don’t make the trait a supertrait of Ord instead;
You add it to the trait object starting with;

impl<T: Ord> Ord for RegEx<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        unimplemented!()
    }
}

#3

Doing that I make some progress, but then I get unknown size errors.

trait RegEx<T:Ord>
{
	fn to_string(&self, t_to_string:&Fn(&T)->String )->String;
	fn cmp(&self, other: &RegEx<T>) -> Ordering where Self:Sized;
}

impl<T:Ord> Ord for RegEx<T>
{
	fn cmp(&self,other:&Self) -> Ordering
	{
		println!("cmp unimplemented");
		unimplemented!()
	}
}

impl<T:Ord> PartialOrd for RegEx<T>
{
	fn partial_cmp(&self,other:&Self) -> Option<Ordering>
	{
		Some(RegEx::cmp(self,other))
	}
}

impl<T:Ord> PartialEq for RegEx<T>
{
	fn eq(&self, other:&Self) -> bool
	{
		println!("eq unimplemented");
		unimplemented!()
	}
}

impl<T:Ord> Eq for RegEx<T> {}

struct EmptyString
{
}

impl<T:Ord> RegEx<T> for EmptyString
{
	fn to_string(&self, t_to_string:&Fn(&T)->String )->String
	{
		String::from("()")
	}
	fn cmp(&self,other:&RegEx<T>) -> Ordering
	{
		Ordering::Less
	}
}

This together with the fact that I should compare types (so that EmptyString elements are before Disjunction ones and similiar for others) makes me think that this approach is flawed.

Perhaps it would be better to simply state

enum<T:Ord> RegEx<T>
{
	EmptyString,
	Single(T),
	Disjunction(Vec<Rc<RegEx<T>>>),
	...
}

But that would force me to rewrite a considerable amount of code.

Am I thinking correctly or the original approach can be made to work?


#4

I have rewritten it as enum and now it compiles correctly and the code feels better. Even if there is solution to the the problem; using enums seems much better for my use case than my original idea.


#5

Yeah, trait objects and things like Ord don’t go well together. I see you’ve switched to enums but if you were interested in sorting a vector, you can use sort_by (and friends) to sort via just the public trait object interface and leave the underlying impls alone.