"the type parameter is not constrained" but it is needed

[RalfJung]

I would expect the following code to compile:

#![allow(unused)]

trait AllocExtra<MemoryExtra> {
    fn create(x: &MemoryExtra) -> Self;
}

struct Alloc<Extra> {
    extra: Extra,
    other: u32,
}

impl<MemoryExtra, Extra: AllocExtra<MemoryExtra>> Alloc<Extra> {
    fn new(x: &MemoryExtra) -> Self {
        Alloc {
            extra: AllocExtra::create(x),
            other: 42,
        }
    }
}

but it does not.

I will now try to hack around this by moving the where-clause to every function, but I will have to repeat it at lot.

[hanna-kruppe]

Could MemoryExtra be an associated type of AllocExtra?

[RalfJung]

No. Both are associated types of some rather big outer trait:

/// Methods of this trait signifies a point where CTFE evaluation would fail
/// and some use case dependent behaviour can instead be applied.
pub trait Machine<'a, 'mir, 'tcx>: Sized {
    /// Additional memory kinds a machine wishes to distinguish from the builtin ones
    type MemoryKinds: ::std::fmt::Debug + MayLeak + Eq + 'static;

    /// Tag tracked alongside every pointer.  This is used to implement "Stacked Borrows"
    /// <https://www.ralfj.de/blog/2018/08/07/stacked-borrows.html>.
    /// The `default()` is used for pointers to consts, statics, vtables and functions.
    type PointerTag: ::std::fmt::Debug + Default + Copy + Eq + Hash + 'static;

    /// Extra data stored in every call frame.
    type FrameExtra;

    /// Extra data stored in memory.  A reference to this is available when `AllocExtra`
    /// gets initialized, so you can e.g. have an `Rc` here if there is global state you
    /// need access to in the `AllocExtra` hooks.
    type MemoryExtra: Default;

    /// Extra data stored in every allocation.
    type AllocExtra: AllocationExtra<Self::PointerTag, Self::MemoryExtra>;

    /// Memory's allocation map
    type MemoryMap:
        AllocMap<
            AllocId,
            (MemoryKind<Self::MemoryKinds>, Allocation<Self::PointerTag, Self::AllocExtra>)
        > +
        Default +
        Clone;

[RalfJung]

Btw, here's how horrible it looks to work around this issue.

[hanna-kruppe]

No. Both are associated types of some rather big outer trait:

I don't understand why that means my suggestion can't work. I'd expect something like

type AllocExtra: AllocationExtra<PointerTag=Self::PointerTag, MemoryExtra=Self::MemoryExtra>;

[RalfJung]

Oh, I see. That might work.

But why? I cannot see anything wrong with my original code. Actually, the fact that it works if I add the where clause in every single function shows that even type inference is fine with this. The check is just a bit overzealous.

[ExpHP]

You didn't just add where bounds; you also added generic type arguments to each individual method. As far as I can tell, this comes down to the difference between

impl Struct {
    fn function<T>(arg: &T) {}
}

—which is a function whose monomorphized instances have the path <Struct>::function::<T>—versus this:

impl<T> Struct {
    fn function(arg: &T) {}
}

...which rust does not currently allow.

---

Associated types are the workaround for this, by allowing a type parameter to be constrained. Type inference does do some obscene things and solve for type parameters uniquely determined by the impls of a trait (frunk relies heavily on this), but there's nothing to stop a downstream crate from adding an impl that breaks the uniqueness, unlike with associated types.

[valarauca]

Issue

Self is always considered not constrained despite the fact that Self is a keyword & always constrained by implementer.

Types which are the result of secondary constraints are unconditionally considered unconstrained.

---

Here is a trivial example of where this is useful, namely polymorphic indexing.

If we have a type

pub struct Graph<E,N> {
    edges: Vec<E>,
    nodes: Vec<N>,
}

With specialized indexing types you can preform some

#[derive(Copy,Clone,Default,PartialEq,Eq,Hash)]
pub struct NodeIndex {
    data: usize,
}
#[derive(Copy,Clone,Default,PartialEq,Eq,Hash)]
pub struct EdgeIndex {
    data: usize,
}
impl<E,N> Index<NodeIndex> for Graph<E,N> {
    type Output = N;
    fn index<'b>(&'b self, indexer: NodeIndex) -> &'b N {
        self.nodes.index(indexer.data)
    }
}
impl<E,N> Index<EdgeIndex> for Graph<E,N> {
    type Output = E;
    fn index<'b>(&'b self, indexer: EdgeIndex) -> &'b E {
        self.nodes.index(indexer.data)
    }
}

This allows for some extremely clean visitor pattern-esque reading of the graph references.

The multi-type complexity is completely irrelevant to the interface, it is extremely sublime all the work the generics do for you.

impl<E,N> Graph<E,N> {
    pub fn read<T,I,F>(&self, indexer: I, lambda: F) -> Option<T>
    where
        Self: Index<I>,
        F: FnOnce(&<Self as Index<I>>::Output) -> Option<T>,
    {
        lambda(&self[indexer])
    }

Super happy with this. Awesome separation of concerns. The Graph<E,N> doesn't care about its internal data, everything is awesome.

The Problem

Arises if you want polymorphism on the indexers (which can be useful if you want to represent abstract state, attached to an Edge/Node). One example is in Ukkonem's algorithm where you need to associate an index in a symbol array, with a graph entry.

This can be easily implied as:

pub struct SpecialIndexOperation<T> {
    data: T
    node_to_maybe_update: NodeIndex,
}
impl<T> AsRef<NodeIndex> for SpecialIndexOperation>T> {
    fn as_ref<'a>(&'a self) -> &'a NodeIndex {
        self.node_to_maybe_update
    }
}

The issue arises when you want to bind to this

impl<'b, I: Clone, Self: Index<I>, T: AsRef<I> + 'b, E, N> Index<&'b T> for Graph<E,N> {
    type Output = <Self as Index<I>::Output;
    fn index<'a>(&'a self, indexer: &'b T) -> <Self as Index<I>>::Output {
        self.index(indexer.as_ref().clone())
    }
}

The problem here is

1. Self is an unconstrained type parameter? What? How? Self always appear, and is always constrained?
2. I is treated as unconstrained despite being extremely influential in all other parameters.

playground link to compiler error

Highlight Problem 1:

This is possible playground link

impl<E,N> Graph<E,N> {

    fn read_ref<R,T,I,F>(&self, index: &R, lambda: F) - Option<T>
    where
        Self: Index<I>,
        I: Clone,
        R: AsRef<I>,
        F: FnOnce(&<Self as Index<I>>::Output) -> Option<T>,
    {
        lambda(& self[index.as_ref().clone()])
    }
}

Both Self and I are considered constrained, but when the same patter appears in impl< they aren't.

Highlight Problem 2

Here we seeing using a similar pattern where I is only referenced in the constrains over other types still results in an error

impl<'b, I: Clone, R: AsRef<I>+'b, G: Index<NodeIndex>+Index<EdgeIndex>+Index<I>> Index<&'b R> for G {
    type Output = <Self as Index<I>>::Output;
    fn index<'a>(&'a self, indexer: &'b R) -> Self::Output {
        self.index(indexer.as_ref().clone())
    }
}

This error returns that I is unconstrained when it interacts with R, G, and Self::Output. It is fairly well constrained and critical to the definition.

Highlight of Problem 3

One can legally write:

playground link

pub fn weird<C,I,T,R,F>(collection: &C, indexer: &R, lambda: F) -> Option<T>
where
    C: Index<I>,
    I: Clone,
    R: AsRef<I>,
    F: FnOnce(&<C as Index<I>>::Output) -> Option<T>,
{
    lambda(&collection[indexer.as_ref().clone()])
}

Which is just as abstract as the trait bounds, but works totally fine.

[steveklabnik]

Triage: not aware of any movement on this issue.

[rw]

A descriptive error message would be helpful. I spent too long trying to figure this out just now :-]

[ghost]

Is there any reason why type parameters can't, in principle, be considered "constrained" when They are used in the constraints of other type parameters? Does this "just" need to be implemented, or is it fundamentally inctractable?

[ExpHP]

It's intractable. A clause like where SomeType: Index<I> cannot be considered to constrain I, because even if SomeType only implements Index for a single index type, a downstream crate can always add another impl:

struct MyIndex;
impl Index<MyIndex> for that_crate::SomeType {
    ...
}

causing I to become ambiguous.