🔬 Tracking issue for RFC 2089: Extended Implied bounds

[aturon]

This is a tracking issue for the RFC "Implied bounds" (rust-lang/rfcs#2089).

Steps:

• [ ] Implement the RFC (cc @rust-lang/compiler -- can anyone write up mentoring instructions?)
• [ ] Adjust documentation (see instructions on forge)
• [ ] Stabilization PR (see instructions on forge)

Unresolved questions:

• Should we try to limit the range of implied bounds to be crate-local (or module-local, etc)?
• @nikomatsakis pointed here that implied bounds can interact badly with current inference rules.

[skade]

I have a question not covered in the RFC (that not necessarily has to be part of the RFC): what will error reporting on bounds violations look like? Will it point to the original definition of the bound?

[ExpHP]

I'm not part of this, but I'll summarize what appears to be the current state of this feature from what I can find:

---

This tracking issue was posted shortly before the 2017 impl period began, and it looks like it fell under the scope of the WG-compiler-traits workgroup. On the workgroup's dropbox doc I see (under Query model):

We do have to handle cycles at least as well as chalk for implied bounds to work out

I searched the issue tracker for recent issues/PRs about bound cycles or the query model, but nothing stood out.

[L-as]

Is this ready for being implemented? And if so, could I get some mentoring instructions?

[scalexm]

Sorry, it seems like this issue has been remaining silent for a long time! Basically the current state of implied bounds is as follows:

• implied bounds have already been prototyped in chalk, the main work was done in https://github.com/rust-lang-nursery/chalk/pull/82 and another amount of work was done in https://github.com/rust-lang-nursery/chalk/pull/134 where we sketched how implied bounds and generic associated types would interfere
• now the recent effort has been to somehow « connect » rustc and chalk, more info here

We would definitely appreciate contributions for this second point, which may eventually enable really cool features in rustc like implied bounds, generic associated types and more generally better type inference. See you on the Zulip stream!

[scottmcm]

I don't know if this is feasible, but if it is, I think it'd be a nice restriction, so wanted to record it for future consideration:

I think this feature is great for direct uses, but weird for "sideways" uses. To try a concrete example:

// in a world where `struct HashSet<T: Hash+Eq>`...
fn foo<T>(s: &mut HashSet<T>, a: T, b: T) -> bool {
    let r = a == b; // not allowed, because _this_ method doesn't know T: PartialEq
    s.insert(a); // allowed, because the method's `Self` type is HashSet, where we always know Hash+eq
    r
}

I think that would keep the core "look, I'm calling a hashset method, so obviously it's Hash+Eq; I shouldn't need to say so again" but still wouldn't let you directly call things on traits that you never mentioned.

(I do, however, think that in that world, impl<T> HashSet<T> or impl<T> Foo for HashSet<T> should allow use of T:Hash+Eq in the whole impl block, since again it's core to the "self type".)

[alexreg]

Is anyone working on implementing this RFC yet? @scalexm, maybe?

[scalexm]

Chalk already handles implied bounds. I don’t know of any plan for implied bounds in Rust outside of pushing on chalk integration.

[alexreg]

@scalexm Oh right. So once Chalk is fully integrated, they'll just "start working" eh? In that case, I'd love to help with Chalk and speed things along... though I feel I'm a bit overstretched and underqualified as it is.

[scalexm]

Note that they "work" if you enable -Z chalk:

https://github.com/rust-lang/rust/blob/81d6f9cc813e8946b6cb2ee29dffeb0000c63e69/src/test/run-pass/chalkify/type_implied_bound.rs

But since you cannot write any useful code with -Z chalk right now (types with lifetime requirements cannot be proved to be well-formed, which is prohibitive), it is not really useful at the moment lol

[ExpHP]

It has been a long time since I've last heard about chalk. Is this integration still ongoing? Is there a place to check on the status of it?

[nikomatsakis]

Integration is ongoing, most of the discussion takes place in #wg-traits on zulip.

[Andlon]

One rather big pain point in generic numerical code is the fact that it's very hard/impossible to ergonomically express the fact that we want to be able to do arithmetic operations not just on T, but on &T and all combinations thereof. In particular, we'd like to do arithmetic like &T * &T. For example, consider the following code:

trait RefMul: Sized + Mul + for<'a> Mul<&'a Self> 
where
    // We refer to this as the "ref bound" below
    for<'a> &'a Self: Mul<&'a Self, Output=Self>
{}

fn do_mul<T: RefMul + Clone>(a: T, b: T) {
    // Works without the ref bound! T * T
    a.clone() * b.clone();
    // Works without the ref bound! T * &T
    a.clone() * &b;
    // But sadly we can't do anything where we need to use &T
    // on the left hand side like the two below expressions :(
    &a * b.clone();
    &a * &b;
}

The problem here is that the for<'a> &'a Self: ... bound is not implied - and repeating this complex bound everywhere is not accceptable for ergonomic reasons. Therefore in practice we're mostly restricted to T * T, which is quite unfortunate for a number of reasons (in particular, if we don't have T: Copy, we have to write .clone() almost everywhere we want to use arithmetic, totally cluttering up the code and possibly losing out on performance on top due to excessive cloning).

I wanted to bring this up as an example of a very real problem we're facing right now in our code bases. I also wanted to ask for some clarification - will my use case be covered by the current plan for implied bounds?

[vks]

@Andlon You can define traits to avoid having to repeat the for bounds.

[Andlon]

@Andlon You can define traits to avoid having to repeat the for bounds.

Do you have a concrete example? I don't see any way of doing this.

[vks]

@Andlon Here is some code that abstracts over several bigint crates. Note that nowadays equivalent traits are available from num-traits (Num and friends).

It does not completely get rid of the for bounds, but the boilerplate is reduced.

[Andlon]

@vks: thanks for the example, but I'm a little confused. It seems to me that the code you provide has exactly the same problem as my example up above? For example, take this method:

fn normalize<T: Integer>(a: T, n: &T) -> T
    where for<'a> &'a T: IntegerOps<T>
{ ... }

It has exactly the same kind of problematic trait bound that I'd like to avoid, and that I am asking if implied bounds will perhaps allow me to omit.

[vks]

You're right, it's still the same problem you were referring to. I misremembered and thought the situation would be better.

My point is that you can make the repeated for bounds less complex by defining appropriate traits.

[joshtriplett]

We discussed this in today's @rust-lang/lang backlog bonanza. We still care about the unresolved questions, but we would be happy to see this implemented so people can start experimenting with it.

[Dessix]

@Andlon said:

One rather big pain point in generic numerical code is the fact that it's very hard/impossible to ergonomically express the fact that we want to be able to do arithmetic operations not just on T, but on &T and all combinations thereof. In particular, we'd like to do arithmetic like &T * &T.

Would this be akin to some sort of trait HyperReference<T> applied for all reference levels of T? It feels like this may be an alternative direction for handling the ergonomics of the "Eye of Sauron", otherwise-solved by #44762 (AutoDeref and AutoRef in operators), but solving it at the type (rather than language) level. I suspect that - like Auto(De)Ref, this will have ambiguity around the base layer- as Copy/Clone/ByValue is a special case differentiated from the other forms.

However, this would likely complicate the logic around mutable references due to traits not being polymorphic across mutability. We'd need a HyperRef and a HyperMutRef or similar- which strikes me as the wrong direction to take if we're attempting unification. Perhaps trait expressiveness is currently too limited to allow sufficient polymorphism? Intuition points at this resting in the same domain as dyn/Marker polymorphism, wherein being polymorphic over referential class could be a single case of being polymorphic over Send, Sync or Sync, while potentially reducing the special-cases around Sized.

(/Tangent)

---

@joshtriplett I'm struggling to find any unresolved questions directly impacting the solution that would arise from Chalk; do we have any that can be enumerated explicitly?

[nikomatsakis]

I am actively working on this

[nikomatsakis]

As a start, what I am doing is drawing up a new model based on https://github.com/nikomatsakis/mir-formality

[nikomatsakis]

More updates to come :)

[ExpHP]

I'd like to copy a possible concern I raised on URLO. The concern is not with implied bounds directly, but with the practice of putting bounds on the type (which this feature will undoubtedly encourage).

---

It is already commonly recognized that placing bounds on a struct rather than on impls prevents simple functions from being able to have weaker constraints; a common example being HashSet::new. Personally, I don't see this as a big deal; in a theoretical world where HashSet::new required Eq + Hash (with all else unchanged), I would simply put the HashSet in an Option if I needed to support types like f64.

However. What I don't see people talking about is the fact that bounds on the type are enforced even if the object is never constructed. Most notably this affects enums, and it means that the workaround of "putting it in an Option" wouldn't actually work when the bounds are on the type! This can have strong implications on downstream code:

// in crate `upstream`
pub struct Set<K: Hash + Eq>(HashSet<K>);

// in crate `downstream`
enum MaybeSet<K> {
    Single(K),
    Set(upstream::Set<K>),   // Error: K requires Hash + Eq
}

MaybeSet::<f64>::Single ought to be a perfectly meaningful variant to work with, but in this case, the upstream author's decision to place bounds on Set has prevented the downstream code author from defining this enum! If I were the downstream code author I would be right maddened, because the alternatives are not pretty.

---

Personally, I'm still excited to see progress on this feature, and don't believe that the above problem is necessarily a dealbreaker (especially as there are still types like std::borrow::Cow which have no choice but to place the bounds on the type). I expect that some concrete examples of the above upstream-downstream conflicts will begin to crop up once people have the opportunity to play with the feature and start trying to take advantage of it, but only time and experience will tell whether it is ultimately a good or bad idea for authors to be writing bounds on the type when it is avoidable.

[fintelia]

It does seem weird that bounds on a struct can produce a type even more restrictive than !:

struct N<K: Hash>(PhantomData<K>);
type ActuallyNever = N<f32>;

fn main() {
    let foo: Option<!> = None; // Ok
    let foo: Option<ActuallyNever> = None; // ERROR!
}

[kpreid]

To address unnecessary bounds: what if there was a Clippy suspicious lint against bounds that aren't used in the body of the type (e.g. a field whose type is an associated type)?

[nikomatsakis]

Being able to add bounds in more places (e.g., enum variants) would be nice here. Orthogonal, but plausible.

[scottmcm]

especially as there are still types like std::borrow::Cow which have no choice but to place the bounds on the type

This makes me wonder about a potentially-much-simpler version of this: could we say that a function doesn't need to "prove" the bounds needed for types it mentions in its signature?

So, for example, I could write this:

fn is_borrowed<T>(x: Cow<T>) -> bool {
    if let Cow::Borrowed(_) = x { true }
    else { false }
}

And that would be fine, because I'm not doing anything that needs the bound.

What would need the bound? Any constructor (struct literals, variant functions, etc), and any call to a function (like Cow::to_mut) that itself requires the bound (perhaps via a trait impl requiring the bound).

Do you think that would be sound? It feels like it ought to be -- though I'm nowhere near sophisticated enough to prove it -- as the cases that don't meet the bounds would be rather like the trivial_bounds cases of where String: Copy that we already deal with.

[dhardy]

For those looking for an alternative that works today using macros, try impl-tools:

impl_scope! {
    struct Foo<T: Debug> { .. }

    // expands to impl<T: Debug> Self { .. }
    impl Self { .. }

    // where bounds supported too:
    impl Self where T: PartialEq { .. }
}

Obviously this has the same drawback as mentioned above: stronger bounds on the type than are required just to construct the type. I haven't found this an issue in my own usage, but appreciate that it could be in some cases.

[daniil-berg]

@Andlon Have you or has someone else here been able to find some kind of workaround/hack for this problem you described, while this issue is still open?

One rather big pain point in generic numerical code is the fact that it's very hard/impossible to ergonomically express the fact that we want to be able to do arithmetic operations not just on T, but on &T and all combinations thereof. [...]

I came across this problem and was pulling my hair out, until I found out that this is a "shortcoming" of the Rust compiler. I agree that it is absolutely not feasible to repeat those redundant trait bounds over and over everywhere the trait itself is used.

Even the following MRE (playground) is enough to stump the compiler:

use std::ops::Add;

trait RefAddable: Sized
where
    for<'a> &'a Self: Add<Output = Self>,
{}

fn do_stuff<T: RefAddable>(x: &T) {}

Causes the following error:

fn do_stuff<T: RefAddable>(x: &T) {}
               ^^^^^^^^^^ no implementation for `&'a T + &'a T`

Telling me I need to add the bound again:

fn do_stuff<T: RefAddable>(x: &T) where for<'a> &'a T: Add {}
                                  ++++++++++++++++++++++++

Can this be worked around with a proc macro somehow? Or is there some hacky magic with marker traits possible here?

PS

I just found out about trait aliases. So at least in nightly it seems you could work around this with a trait alias:

#![feature(trait_alias)]

use std::ops::Add;

trait RefAddable = where for<'a> &'a Self: Sized + Add<Output = Self>;

fn do_stuff<T: RefAddable>(x: &T, y: &T) -> T {
    x + y
}

(playground with test)

Seems good enough at first glance. But I am still curious, if someone found another workaround.

[djc]

Does anyone have a sense of what is blocking this at this point? Surely would be nice to have...

[rsalmei]

Rust 1.79 has just stabilized implied bounds ability on Supertraits! (Full ability I mean, including Associated Type bounds) Hopefully, we are a bit closer to full implied bounds now.