Bounds on trait type parameters not taken into account

help
1

[ TL;DR: the question requires quite a bit of context, the actual question is way below. ]

I have a type, its details are not important, for example:

struct Attribute { k : String, v : String }

Various structures in the program have a list of Attributes in them, some in simple Vec, some in more complex data structures. I want to be able to list them. Since I want to abstract over different types of structures, that means a trait, and since I want to iterate, that means returning an iterator.

Morally, that would be:

trait With_attributes {
    fn attributes(&self) -> Iterator <Item = &Attribute>;
}

Of course, it is not that simple: Iterator is a trait too, the trait must be abstracted over the actual type of the iterator. Furthermore, iterators are usually borrowed, so a lifetime parameter is necessary:

trait With_attributes <'a, I : Iterator <Item = &'a Attribute>> {
    fn attributes(&'a self) -> I;
}

Now, let us implement a simple structure with attributes:

struct Simple { attr : Vec <Attribute> }

Since the attributes are stored in a Vec, the iterator will be std::slice::Iter:

use std::slice::Iter;
impl <'a> With_attributes <'a, Iter <'a, Attribute>> for Simple { 
    fn attributes(&self) -> Iter <Attribute> {
        return self.attr.iter();
    }
}

I can now use the attributes() function, for example:

fn dump_attributes(s : &Simple) {
    for i in s.attributes() {
        print!("{} -> {}\n", i.k, i.v);
    }
}

The question: This works, but it is monomorphic, not using the trait abstraction. I change it to use the trait abstraction:

fn dump_attributes <I> (s : &With_attributes <I> ) {

And… it does not work:

19:5: 21:6 error: the trait `core::iter::Iterator` is not implemented for the type `I` [E0277]
19     for i in s.attributes() {
20         print!("{} -> {}\n", i.k, i.v);
21     }

19:5: 21:6 note: expansion site
19:5: 21:6 help: run `rustc --explain E0277` to see a detailed explanation
19:5: 21:6 note: `I` is not an iterator; maybe try calling `.iter()` or a similar method

Nuf? The definition of With_attributes requires that I is an iterator, why does the compiler not see it? If I add all the type annotations:

fn dump_attributes <'a, I> (s : &'a With_attributes <'a, I>) 
    where I : Iterator <Item = &'a Attribute> {

… it works. But why is it not implied by using the With_attributes trait?

By the way, if there are simpler ways of doing any of the above, please let me know.

2

Rust wants function signatures to be explicit (modulo lifetime elision) and inferring bounds on I seems like the opposite of that.

3

Thanks, but I am not satisfied by this explanation, I feel it explains both everything and nothing.

When we write Some_trait <T> in a function signature or another type annotation, it imports in the local context the meaning of the trait: “a type that has at least this method, this method and that method”. A future version of the language could provide some kind of anonymous traits; OCaml object system works like that. The type inference, if any, happens after that, taking into account all the constraints, the ones written in place and the ones imported. My question is: why is the bound on the type parameter not imported along with the rest of the trait properties?

Let me put it another way: IIUC, the decision not to have type inference on function signature is meant to avoid algorithmic explosion of the type inference, which is bad for the compiler and even worse for the programmers due to unreadable error messages. Mandatory type annotations at key points in the program avoid that and make the whole thing manageable. My point is that importing the type bound from the trait definition does not harm this in any way.

4

Your With_attributes trait is not an object-safe trait.
In your case this is because of a generic nature of your trait: in order to make it object-safe (means something like "rust can convert trait to a real type with a pointer to virtual methods table") it shouldn't be generic on its attributes() method output type. Just imagine: there are infinite number of possible output types for the method, and you ask Rust to create that many different vtables with pointers to infinite number of specific attributes() methods implementations, so you can dispatch on them in runtime. Now you need infinite amount of RAM. Do you have it?

In this case you have concrete trait implementation with a concrete iterator return type, OK, but you want to abstract of it in runtime, so you loose this types information, all you can know at runtime, is you have some "With_attributes" type, and now you have to find out what is the real methods bound to this type. Rust can't know in advance what other concrete types can be hidden behind this abstractions, hence the problem. Please read the blog post I linked above for details on object safety.

1 Like
5

Oh, yes, I had not noticed that I was using dynamic dispatch in this version. (Is it possible to get a warning?) But I am not sure your explanation applies: I do not see any of the listed cases applying.

The one you are suggesting is the “generic method”, I suspect, but it is about having a type parameter on a method. In my code, the type parameter is on the trait, it gets monomorphised when the dump_attributes function is instantiated. The vtable in the trait object contains a single entry: get_attributes(&self) -> Iter <Attribute>.

But just to make sure, I tried with static dispatch:

fn dump_attributes2 <'a, T, I> (s : &'a T)
    where T : With_attributes <'a, I>,
        I : Iterator <Item = &'a Attribute>
    {
    for i in s.attributes() {
        print!("{} -> {}\n", i.k, i.v);
    }
}

It works like that, but removing the I : Iterator bit breaks it.

6

[quote="Cigaes, post:3, topic:2570"]
Let me put it another way: IIUC, the decision not to have type inference on function signature is meant to avoid algorithmic explosion of the type inference, which is bad for the compiler and even worse for the programmers due to unreadable error messages.
[/quote]This is the best citation I can find at the moment and there seems to be some discussion of a similar question later on.

So, beside any technical reasons Rust actually chooses explicitness in this and some other cases for the sake of the human reader.

7

The FAQ entry pretty much confirms what I was writing. The trait bound is unambiguously attached to the trait definition. Ignoring it at this point helps neither the compiler (it just has to link one bit of the data structure at the right place) nor the human readers. For the later point, it is quite the contrary actually, since it adds useless visual clutter to the function definition.

8

You can have cycles and other non-well-founded dependency graphs with these non-supertrait predicates, but we want a finite set of elaborated predicates.