"Unconstrained type parameter" when the parameter is constrained by a "where" clause

help
1

Hello! I am struggling with a design issues regarding traits and generics and I have been unable to find my answer in similar threads, I am sorry if a similar problem has been solved already and I kindly ask you to link me the relative thread.

Let's suppose I have this trait, which defines whether a struct may store an error of a generic type:

trait StoreError<E> {
    fn set_error(&mut self, error: E);    
    fn get_error(&self) -> Option<E>;
}

I define another trait that other struct which are able to extract and handle the error may implement:

trait ErrorHandler<H> {
    fn handle_from(&self, handler: H);
}

I implement this last trait for a struct which prints the result of get_error():

struct ErrorPrinter {
    preamble: String
}

impl<H, E> ErrorHandler<H> for ErrorPrinter
where
    H: StoreError<E>,
    E: std::fmt::Debug
{
    fn handle_from(&self, handler: H) {
        println!("{}: {:?}", self.preamble, handler.get_error());
    }
}

However, this code produces the following compilation error:

error[E0207]: the type parameter `E` is not constrained by the impl trait, self type, or predicates
  --> src/lib.rs:14:9
   |
14 | impl<H, E> ErrorHandler<H> for ErrorPrinter
   |         ^ unconstrained type parameter

This error does not show up if I force ErrorPrinter to store the type E, even if it is unused.

I am convinced that this design may result ambiguous, but I still cannot imagine a case where it would. I would like ErrorPrinter to work with any type H which is able to store an error of type E, as soon as E is "Debug-gable". Is there anyway to obtain such a behaviour? Thanks in advance.

Full code: Rust Playground

2

"unconstrained" doesn't mean "does not appear in a where clause".

Here "unconstrained" means that it doesn't do anything, it isn't used by either the trait or the implementing type.

That's a problem, because for two distinct choices of E, this would generate the following impls when desugared:

impl<H> ErrorHandler<H> for ErrorPrinter
where
    H: StoreError<E1>,
{
    fn handle_from(&self, handler: H) {
        println!("{}: {:?}", self.preamble, handler.get_error());
    }
}

impl<H> ErrorHandler<H> for ErrorPrinter
where
    H: StoreError<E2>,
{
    fn handle_from(&self, handler: H) {
        println!("{}: {:?}", self.preamble, handler.get_error());
    }
}

As you can see, these both are exactly the same impl! That's because there's nothing preventing the type H from implementing both StoreError<E1> and StoreError<E2>, so for such a type H, the impls would overlap.

2 Likes
3

You can add the parameter to the type without actually storing it.

You can add the parameter to the trait. Implementors choose which E they can handle.

You can add the parameter to the method. Your trait bounds have to move to the method and implementors have to support everything within those bounds, which could be unacceptably inflexible.

3 Likes
4

Thank you, the ambiguity it's clear to me, but why doesn't the language give the possibility to disambiguate the method call?

@quinedot Does using PhantomData lead to overhead at runtime? I have taken a look at this but it seems something more related to FFI and interaction with unsafe code, so I thought it was dirty to use it to force compilation in my instance.

5

Because there's nothing to disambiguate. The problem is not ambiguity, but the fact that there are two impls that can be exactly the same.

6

No, it's not present at run time. It's used to steer various semantics about your type like auto-traits and variance. Or in this case, coherence.

1 Like
7

But they are not “exactly the same”. One is H as StoreError<E1> and the other is similar-yet-different H as StoreError<E2>. One may even imagine that something like this would produce such distinct types:

fn turn_H_into_store_errror_E1(handler: H)
  -> impl StoreError<E1>
{
  return handler
}
fn turn_H_into_store_errror_E2(handler: H)
  -> impl StoreError<E2>
{
  return handler
}

Note that you already couldn't use H returned from turn_H_into_store_errror_E1 as StoreError<E2> and H returned from turn_H_into_store_errror_E2 as StoreError<E1> which means such quasitypes are already a thing in Rust.

Whether it's good idea to expand their use further is unclear, though.

8

Again, it's possible for a particular type H to implement both StoreError<E1> and StoreError<E2>. I'm not sure what you are getting at with the as syntax, but a type implementing two different traits doesn't change the fact it's still the same type.

Thus, the compiler is not allowed to assume that the two Hs in the two impls are always different, and it must forbid the simultaneous implementations. Since generics must work with all (eligible) types, including 3rd-party code, the compiler must conservatively forbid any two impls that can potentially collide, regardless of whether the current set of types in your own crate does.

9

That's not true for abstract return types. If you return some type in that way then internally it's still the same type, but from the language POV it's “H restricted to StoreError<E1>”. One can imagine elevation of these quasitypes to the level of real types.

Whether that's a good idea or not is debatable.

Alternative would be to provide a way to restrict type. E.g. RPIT already does it, only it creates completely anonymous type which is related to H (indeed, in reality it's H and compiler knows it) but compiler chooses to ignore it (sometimes, not 100% of time which leads to funny error messages in some cases).

Whether turning such quasitypes into real types is good idea or not is debatable, but nothing prevents one from extending Rust in that way (except that it's a lot of work for very limited benefit).

10

No, that doesn't apply here, exactly because we are in a generic context, not RPIT. The two aren't really comparable use cases/features anyway, so without a concrete design ("it should work" is not a concrete design!), it's hard to tell why/how you think it should work or why RPIT is relevant at all in this discussion.

RPIT is existentially-qualified. Generic type variables are, however, universally-quantified, therefore the compiler must only allow code that it can prove correct for all possible substitutions of a given type variable. In the above examples, there can be some choices of H that make the code incorrect, breaking the universal quantification, which must in turn cause a compiler error.

Your vague assertion of H being "restricted" doesn't really help. A trait is not a type, and two type variables that are bounded by two different traits simply don't always have to stand in for different concrete types, because a type can and does implement multiple traits.

There are of course cases when the compiler can prove such inequality based on unicity of trait bounds. Eg. a type variable that is bounded by a non-generic trait with a given associated type is necessarily non-overlapping with a type variable bounded by the same trait with a different associated type. So changing the trait's type parameter to an associated type works, but that's only due to the 1-to-1 nature of associated types, ie. the fact that a given type can't implement the same (non-generic) trait twice with two different associated types.

1 Like
11

They are relevant because they are living and breathing examples of H as Foo.

Suppose we have something like this:

struct H;

trait Foo {
    fn trait_fn(self);
}

impl Foo for H {
    fn trait_fn(self) {
        println!("This is Foo::trait_fn");
        Bar::trait_fn(self)
    }
}

trait Bar {
    fn trait_fn(self);
}

impl Bar for H {
    fn trait_fn(self) {
        println!("This is Bar::trait_fn");
    }
}

Here attempt to use h.trait_fn should lead to ambiguity, because there are two trait_fn functions. And that's exactly what happens if you would try to use it like this:

fn main() {
   let h: H = H;
   h.trait_fn()
}

Ambiguity. Not allowed. But what if we have H as Foo, thanks to RPIT?

fn h_as_foo(h: H) -> impl Foo {
    h
}

fn main() {
   let h: H = H;
   let h_as_foo = h_as_foo(h);
   h_as_foo.trait_fn()
}

No problem. No ambiguity and everything works. Which, essentially, means that Rust already have H as Foo hidden type.

Note that said H as Foo type decays nicely inside of Foo::trait_fn. That function can call Bar::trait_fn even if main couldn't.

Is this universal rule of the universe? Rust already have case where type which implements one trait works, type which implements another trait also works, but if you implement two… you are SOL.

Why can't situation which topicstarter is talking about be another such case? Obviously it can be done.

The question of whether that's good idea or not is separate.

How does my full example with h_as_foo.trait_fn and Bar::trait_fn(self) works, then?

You theory is really nice, only it describes some other language, not Rust.

There are no requirements for that to be 1-to-1. That's just limitation of current resolver. Whether complete overhaul of it, which is needed to support topic-starter's use-case is worthwhile effort is different question.

12

You are utterly and completely wrong. As I have already explained several times to you in this thread, the problem is not ambiguity, and your example involving trait_fn is completely irrelevant. In that example, there are two different traits, and the ambiguity is trivial, because it stems from a simple syntactic/namespacing reason, nothing more.

Resolving this problem is easy, because it only requires local reasoning, specifically asking which traits are already implemented. And there's already a coherentc non-overlapping set of trait impls, and the only thing the user needs to do is type out the fully-qualified path of the method. (Which they would need to do anyway if it wasn't for method call syntax, which is a trivial piece of syntactic sugar.)

In contrast, in OP's code, there isn't any sort of "ambiguity". Instead, there is a potential set of types that lead to duplicated implementations of the exact same trait. That is not a simple syntactic or name resolution problem. It's a fundamental logical problem that is a consequence of universal quantification, and no amount of "disambiguation" can solve this, since which trait/type combination causes the problem is already unambiguous.

The root of the problem is instead that it requires global reasoning, as the genericity of the trait causes all of their specializations to be implementable for 3rd-party types too. Thus, the overlap is impossible to prevent, since the compiler can't possibly foresee all external future impls.

No, but it is 100% positively how the language is defined.

I'm honestly not sure what you are getting at here. A single concrete trait impl for a given type can only ever have one specific definition for each associated type. It is not possible to simultaneously implement Trait<Assoc = T> and Trait<Assoc = U>, because the associated type is not a generic parameter – it's an output, not an input, so it doesn't determine which trait we are implementing. The relationship is asymmetric: the trait determines the associated type but the converse is not true, which in turn means that two such impls would again implement the exact same trait, not two different traits.

Allowing it would be logically inconsistent. What you seem to want here is already possible with a generic trait, of which associated types are dependent upon (eg. identical to) the generic type parameter(s), without causing any sort of conflict.

1 Like
13

The way I see it is that you're basically asking the compiler to desugar this code:

trait StoreError<E> {
    fn get_error(&self) -> String;
}

trait ErrorHandler<H> {
    fn handle_from(&self, handler: H);
}

struct ErrorPrinter {
    preamble: String
}

impl<H, E> ErrorHandler<H> for ErrorPrinter
where
    H: StoreError<E>,
    E: std::fmt::Debug
{
    fn handle_from(&self, handler: H) {
        println!("{}: {:?}", self.preamble, handler.get_error());
    }
}

into this code:

trait StoreError<E> {
    fn get_error(&self) -> String;
}

trait ErrorHandler<H> {
    fn handle_from(&self, handler: H);
}

struct ErrorPrinter {
    preamble: String
}

trait DisambiguatedStoreErrorTrait {
    type E; // The generic parameter becomes an associated type
    fn get_error(&self) -> String;
}

struct DisambiguatedStoreErrorType<T, E>(T, core::marker::PhantomData<E>);

impl<T: StoreError<E>, E> DisambiguatedStoreErrorTrait for DisambiguatedStoreErrorType<T, E> {
    type E = E;
    fn get_error(&self) -> String {
        self.0.get_error()
    }
}

impl<H> ErrorHandler<H> for ErrorPrinter
where
    H: DisambiguatedStoreErrorTrait,
    H::E: std::fmt::Debug
{
    fn handle_from(&self, handler: H) {
        println!("{}: {:?}", self.preamble, handler.get_error());
    }
}

Here DisambiguatedStoreErrorType<T, E> is your T as StoreError<E>. Could the compiler do this automatically? Probably. Is this wanted? My guess is no, it doesn't feel necessary, easy to explain and hides other possible solutions (you could attach the E type to the ErrorHandler trait, or to the ErrorPrinter type, or make it an associated type to start with, or maybe this is a sign that your design is flawed etc etc).

14

Finally you are saying something sensible. Indeed, if our trait solver have inputs and outputs then this problem have no solution. But there are no reason to have inputs and outputs. In fact I would say that the fact that traits do have inputs and outputs is the artificial limitation.

It haven't existed in half-century old Prolog, why does it exist in Rust? To make use of traits problematic? Well, it have certainly achieved that.

I don't think it's worth trying to change that (Chalk tried, but, ultimately, failed, because refusal too have inputs and outputs have too many implications and while this approach may prove to be more usable backward compatibility is practically impossible to retain), but there are no fundamental laws of the universe which make it undesirable, just the historical baggage, and, more importantly, orphan rules.

I'm not asking the compiler to do anything. I'm just saying that there are nothing fundamentally wrong with treating these two implementations as different and making it possible to disambiguate between them.

The decision to make traits generic parameters inputs and associated types outputs while forbidding any other restrictions entirely is arbitrary and, actually, harmful. That's why Rust have already few bolt-ons which allow certain tricks which wouldn't work otherwise and would undoubtedly get more in the future.

I, too, don't think it's good idea to add such extension. But it's perfectly possible to add it and in hypothetical Chalk-based Rust where generic arguments are not inputs and associated types are not outputs everything would just happen to work automatically.

The big disadvantage of “Chalk-based Rust” is problem of orphan rules: if you go from inputs to outputs then it's easy to design runes which would guarantee that different crates wouldn't provide conflicting implementations, if you do full-blown Prolog resolutions, then such rules become much harder to create, maybe impossible…

15

...and I guess this point alone would make the whole proposal a non-starter. We don't want the process of simply adding another dependency to break seemingly unrelated code.

16

I'm not sure what you mean here. In Prolog the parameters of clauses are the inputs while the output is just whether the clause holds or not. It doesn't need to disambiguate overlapping rules because if one happens to hold then the clause also holds.

If you translate this to Rust, you're saying that you only care whether a trait is implemented for a given type, and if there are overlapping implementations then the trait is obvious implemented! However this discards not only associated types, but associated constants and methods too. That's like almost the whole point of using traits.

Note that there is a nightly feature, called marker_trait_attr, which does allow overlapping implementations (not ones with unconstrained parameters though, but that seems more like an oversight) of traits annotated with #[marker]. Most notably however these traits' body must be empty, so that the only observable "output" is whether the trait is implemented or not (just like in Prolog!). Rust Playground

But isn't that what the code I shown does? It makes the two implementations different and allow you to disambiguate between them. So effectively one way to implement in the compiler what you want is to desugar the first snippet to the second one.

Can you explain those few bolt-ons, why they are bad, and why allowing overlapping implementations would "fix" them?

17

No. In Prolog bound variables are “inputs” and unbound variables are “outputs”. You can write rule x = y + z and then bind y and z and then get x or bind x and y and get z.

This is precisely what you want with generics.

Of course it needs to disambiguate! Prolog's goals is to report solutions, after all, not just to say if some statements holds or not.

But Prolog is happy to return many solutions if they exist… Rust would ask you to disambiguate them, somehow.

Sure, but that's just the solution for the problem of one such trait. When one wants to call many traits and you have many possibilities at each step you need full prolog-style resolver to find the solution see if satisfaction of requirements at each stage would lead to one, unique, solution or not.

I have already shown one. Abstract return types restrict the type and make it “think” it's limited. Except when it's not limited. And then it's limited again. Look on the example.

This is done via creation of hidden types and then converting them back and forth (bonus points for when you would create many such different types) and while it's possible to extend it to cover the case which topicstarted talks about (like you have shown) it doesn't feel like a good idea, because in reality what's desired there is not a way to hide/unhide certain properties of your type, but for the compiler to look on the few traits and then find out how to satisfy them all.

E.g. it may look on which get_error is provided for handler and pick one of them that would suit the other parts of the program. Similarly how into may decide what to produce depending on assignment target.

It's not even horribly hard to implement such system, but the question of whether it would be easier or harder to use it in comparison to what Rust have now is not entirely clear.

18

You can make a typeless trait containing typed supertraits if you just want to compose possible type outputs [playground].

19

I can see how you could consider those outputs, but I would not say that the unbounded variables are the outputs, rather that the list of the valid subsitutions for them is the output.

I don't see how you would want this with generics though.

Reporting all the solutions doesn't mean disambiguating between them. It just reports all of them, not select one of them. Though I agree it's not just reporting whether it applies or not.

I don't see something in Rust could lead to one unique solution if it ever splits in two branches. Do you have some example?

Abstract return types are used for 2 main purposes:

  • refer to types that you can't name (e.g. closures) that is existential types, while generics are always universally quantified
  • hide a type, exposing only a trait it implements. Usually this is done to hide a private type, not "forcing" a specific trait on it

I don't see how these two needs could be satisfied by allowing overlapping implementations and Type is Trait.

The problem with this approach in general is that in order to get an unique answer you might need to do negative reasoning (e.g. this trait is not implemented for this type, so this branch is not possible). This often has stability implications because these conditions are not always entirely in your control. For example another crate may make that condition true by implementing some trait and suddently your crate doesn't compile anymore. My guess is that in order to avoid this you would have to always conservatively require impls to be disambiguated.

20

Look on what we are discussing from the beginning. Suppose this whole machinery is used in some larger generic function where types H and E are specified explicitly. Something like this:

fn process_data<E>(h: impl StoreError<E>) {
   …
}

In that function there are no ambiguity about which E have to be used with ErrorPrinter.

Even if “outside” there are many conflicting implementations for that trait “inside” of process_data they are “invisible”. That's how traits in Rust already work, isn't it?

If, instead of implementing this with hidden extra type and hidden implementation of trait for that type, compiler would do the same resolution as with [hyphotetical] process_data above effect would be similar isn't it?

Your guess is an good as mine. C++ doesn't require anything of the sort and yet there are, literally, billions of lines of code written in it.

And while trouble with templates mixups and stability do happen, from time time we know they don't happen often.

On the other hand the lack of TMP is cited as one of the main reasons to stick with C++ or try Zig. Some even say that Rust is entirely useless because of that. I'm not among them, rather I'm saying that other advantages of Rust outweigh it's clunky and unwieldy traits story, but said story with all it's limitations is just quite tiring in practice.

But then, I'm not typical, I work in a team where we follow style guide and best practices religiously and where I have just committed bugfix for P1 bug this week without ever running test once (the issue was with other teams tests that violated the spec and when we saw the logs it was easy enough to adjust code to allow that violation).

IOW: that amazing achievement that we discussed here… we have it in C++, too. Only instead of compiler the complaints about violation of ownership rules and other such things are done by other team members. Using the compiler for these is really tempting, but dealing with limitations of Rust's trait system… it's a big turn-off.

But for now Rust-without-Traits-crazyness doesn't exist thus I would assume that maybe in some other teams this wouldn't work. But I just want to note that while I regularly see issues with ownership in C++ (usually caught on review but in rare cases they survive till production) and silent conversion between different types sometimes bites us, too but I have never seen trouble with templates in C++ which made something working improperly.

Compile time failures? Sure, often. Something in runtime? Wouldn't say that it never happened, but the fact that I couldn't recall even a single example from the top of my head speak volumes.

Can you even show one such accident in any open-source project? There must be plenty of such cases if the cure offered is this whole extra-complicated construct of traits and orphan rules and bazillion limitations.