Type constraint for generic of another generic

1

I really did my best to find a solution, but regrettably I have to ask for some help. I'd like to implement FromIterator accepting an iterator of tuples or references to tuples. A tuple has two elements. I'd like to have the first element being String, &String, &str.

The code itself.

So the compiler says: unconstrained type parameter. To be honest I feel like the type is constrained.

  • The generic parameter B is constrained by the item of the accepted iterator. So that says that the type of B will be the type of data in the input iterator.
  • The generic parameter S is constrained by the generic parameter B. So that says that the data will be known within the type of data in the input iterator.

Even more a function definition works fine

fn from_iter<T, S, B>(iter: T)
where
    T: IntoIterator<Item = B>,
    S: AsRef<str>,
    B: std::borrow::Borrow<S>,
{}

Could you clarify please, how I can define the constraints for the generic in the trait implementation? Or is my logic completely wrong?

2

S is not constrained because B could in principle have Borrow<S> impls for many different S.

3

"Unconstrained" doesn't mean what you think it does. It means that the type parameter S doesn't influence the signature of the implementation: since the impl is

impl FromIterator<B> for Node

there's nothing in this that would depend on S, only on B. Therefore, two choices of S would result in two, overlapping/ambiguous impls of the same trait (FromIterator<B>) for the same type (Node).

Anyway, your current code doesn't match your description of needing to accept tuples, but this does.

4

I made a mistake in my code. Actually, my B is std::borrow::Borrow<(S, u64)>

S is not constrained because B could in principle have Borrow<S> impls for many different S.

What do you mean by "for many"? Beyond the set which meets AsRef<str>?

5

No, but that's a red herring. The AsRef<str> bound simply doesn't matter here at all. The point is that for two different concrete choices of S, eg. S = String and S = str, there would be two completely identical impls, which violates coherence.

6

Something wrong with my Rust today. How could they be identical?

I feel like I should get 6 different implementations according my code. Yours code works fine, but I need to understand the problem, rather than just pick a ready to use code.

  1. impl FromIterator<(String, u64)> for Node
  2. impl FromIterator<&(String, u64)> for Node
  3. impl FromIterator<(&String, u64)> for Node
  4. impl FromIterator<&(&String, u64)> for Node
  5. impl FromIterator<(&str, u64)> for Node
  6. impl FromIterator<&(&str, u64)> for Node
7

That's not what I'm talking about at all. B doesn't depend on S in any way, but the constraint B: Borrow<S> can be fulfilled for many S. For example, picking B = String, one could pick two completely identical impls with different choices of S.

With the invented syntax Var = Type for denoting the substitution of concrete type Type for type variable Var, two such possible identical impls would be:

impl<S = String, B = String> FromIterator<B = String> for Node
where
    S = String: AsRef<str>,
    String: Borrow<S = String>,

and

impl<S = str, B = String> FromIterator<B = String> for Node
where
    S = str: AsRef<str>,
    String: Borrow<S = str>,

which are exactly the same impl, because both are impl FromIterator<String> for Node. The difference is only in what path Borrow and AsRef "go through", but that doesn't change the impl itself.

1 Like
8

Consider the following user-defined types— There's no way for the compiler to decide between picking S=A and S=B if you pass an iterator of ABs to Node::from_iter, but the choice will change the result.

struct A(String);
struct B(String);
struct AB { a:(A,u64), b:(B,u64) };

impl AsRef<str> for A {
    fn as_ref(&self)->&str { self.0.as_str() }
}

impl AsRef<str> for B {
    fn as_ref(&self)->&str { self.0.as_str() }
}

impl Borrow<(A, u64)> for AB {
    fn borrow(&self)->&(A, u64) { &self.a }
}

impl Borrow<(B, u64)> for AB {
    fn borrow(&self)->&(B, u64) { &self.b }
}
1 Like
9

That makes sense! But why does the generic function, which I posted in the first message, work then?

10

Ah it works, because the argument influenses the function signature. Is that correct?

11

Now I'm understanding the pseudocode. But I don't want to maintain two different implementations. I can use the function to share the functionality of the trait implementations, but it doesn't seem elegant.
Don't you have a more elegant idea?

12

Parameters of generic functions don't have to be constrained because you can specify them at the call[1] site. Example.

Parameters on implementations have to be constrained because there's no way to specify which implementation you want elsewhere (e.g. a call site), you can only specify which type and trait you're talking about. Therefore you have to be able to find the fully qualified implementation from the fully qualified type and a fully qualified trait.

  1. or construction ↩︎

4 Likes
13

An impl has to be selectable based on the types involved — <SomeTy<T...> as SomeTr<U...>>::func() must always determine a unique function — but there is no such rule for function generics. A function can even have completely unused type parameters, because it's always possible for the caller to specify explicitly which ones it means. (For example, std::mem::size_of::<T>() does not use T as input or output.) But there is no way to explicitly specify the type parameters of an impl, because impls are not things you name at the call site; they have to be unambiguous based only on the type and the trait.

1 Like
14

I linked a playground above that compiles and does what you want.

15

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.