Unconstrainted type parameter

help
1

I have a library with a somewhat complex library. I have reached an impasse in my implementation. Unfortunately, while I can easily re-create the error in a simpler form, I am not sure what parts of my library are needed to understand what solutions would work.

The library makes heavy use of Reference counted pointers at several points to minimize memory usage. I am trying to make the library generic so that either Rc or Arc can be used. I have had some help on this issue previously.

I am now working on an indexing system which enables me to store data and access it in several different ways, This also uses reference counter pointers. But now I am stuck.

I have set up example here.

The core data structure looks like this:

#[derive(Debug, Eq, Hash, PartialEq)]
pub struct IRI<A:ForIRI>(A);

pub trait ForIRI: AsRef<str> + Borrow<str> + Clone + Debug + Eq + Hash + PartialEq {}
impl<T: ?Sized> ForIRI for T where
    T: AsRef<str> + Borrow<str> + Clone + Debug + Eq + Hash + PartialEq {
}

defining an IRI. The IRI is stored in AnnotatedAxiom whcih looks like this:

pub struct AnnotatedAxiom<A:ForIRI> (
    IRI<A>
);

pub trait ForIndex<A:ForIRI>: AsRef<AnnotatedAxiom<A>> + Borrow<AnnotatedAxiom<A>> + Eq + Hash {}
impl<A:ForIRI, T: ?Sized> ForIndex<A> for T where T:AsRef<AnnotatedAxiom<A>> + Borrow<AnnotatedAxiom<A>>
    + Eq + Hash{}

The actual AnnotatedAxiom is rather more complex; it contains a big enum that actually contains potentially many IRI instances. In total, the AnnotatedAxiom type takes up about 200bytes on the stack.

My index system looks like this:

pub trait Index<I:ForIRI, AA:ForIndex<I>>{
    fn add(&mut self, ax: AA) -> bool;
    fn remove(&mut self, ax:&AnnotatedAxiom<I>) -> bool;
}

and I have successful impls over Vec and HashSet which obviously have different behaviour. My real world use case uses more complex indexing methods. SetIndex looks like this:

#[derive(Debug)]
pub struct SetIndex<AA>(HashSet<AA>);

impl<I:ForIRI, AA:ForIndex<I>> Index<I, AA> for SetIndex<AA> {
    fn add(&mut self, ax: AA) -> bool {
        self.0.insert(ax)
    }

    fn remove(&mut self, ax: &AnnotatedAxiom<I>) -> bool {
        self.0.remove(ax)
    }
}

All is well. And it seems to work. I can create an index of type VecIndex<Rc<AnnotatedAxiom<Rc<str>>>>
or SetIndex<Arc<AnnotatedAxiom<Arc<str>>> or various other variations.

Now, I wanted to add some other methods to SetIndex. Adding new is fine.

// Case 1: Works!
impl<AA> SetIndex<AA> {
    pub fn new() -> SetIndex<AA> {
         SetIndex(HashSet::new())
     }
}

Next, I tried contains

//Case 3: Fails. Unconstrainted type parameter
impl<I, AA> SetIndex<AA> {
    pub fn new() -> SetIndex<AA> {
        SetIndex(HashSet::new())
    }

    pub fn contains(&self, ax: &AnnotatedAxiom<I>) -> bool {
        self.0.contains(ax)
    }
}

which results in this:

error[E0207]: the type parameter `I` is not constrained by the impl trait, self type, or predicates
  --> src/main.rs:94:6
   |
94 | impl<I, AA> SetIndex<AA> {
   |      ^ unconstrained type parameter

For more information about this error, try `rustc --explain E0207`.
error: could not compile `playground` due to previous error

I've tried several variations on the theme here, but for the life of me I cannot see how to work around this problem. What is the right way to express the types here?

2

The simplest solution is to attach the I parameter to contains(), then constrain it with a where bound:

impl<AA> SetIndex<AA> {
    pub fn new() -> SetIndex<AA> {
        SetIndex(HashSet::new())
    }

    pub fn contains<I: ForIRI>(&self, ax: &AnnotatedAxiom<I>) -> bool
    where
        AA: ForIndex<I>,
    {
        self.0.contains(ax)
    }
}

But I don't understand why you need the ForIndex trait in the first place, instead of just using AnnotatedAxiom. Assuming ForIndex is necessary, I'd prefer to write Index with an associated type, which yields a somewhat more involved solution:

pub trait Index<A: ForIRI> {
    type Item: ForIndex<A>;
    fn add(&mut self, ax: Self::Item) -> bool;
    fn remove(&mut self, ax: &AnnotatedAxiom<A>) -> bool;
}

#[derive(Debug)]
pub struct SetIndex<I: ForIRI, AA: ForIndex<I>>(HashSet<AA>, PhantomData<I>);

impl<I: ForIRI, AA: ForIndex<I>> Index<I> for SetIndex<I, AA> {
    type Item = AA;

    fn add(&mut self, ax: Self::Item) -> bool {
        self.0.insert(ax)
    }

    fn remove(&mut self, ax: &AnnotatedAxiom<I>) -> bool {
        self.0.remove(ax)
    }
}

impl<I: ForIRI, AA: ForIndex<I>> SetIndex<I, AA> {
    pub fn new() -> SetIndex<I, AA> {
        SetIndex(HashSet::new(), PhantomData)
    }

    pub fn contains(&self, ax: &AnnotatedAxiom<I>) -> bool {
        self.0.contains(ax)
    }
}
3

In the example that I have given, AnnotatedAxiom is a thin wrapper around IRI. In actuality it's rather bigger than that being a large enum, coming in at around 200 bytes. If I wanted to build two indexes to the set set of AnnotatedAxiom, I need to be able to clone them cheaply. So, I use an Rc (or Arc) to keep a shared reference and index these instead of AnnotatedAxiom directly.

I have a similar layer of caching for the IRI because I expect these also to be shared between many otherwise different AnnotatedAxiom. It's feels complex, and it's hard to test how much value all of this complexity brings without implementing it all first.

The associated type solution also looks nice, although I still don't really understand associated types. But the use of PhantomData feels strange and reading the documentation seems like a workaround that is designed for a different purpose (i.e. interfacing with C and such like). But I will try this also.

Thank you!

4

It has a variety of uses; here's a recent thread about a few. "I don't store a X but I know how to produce one" seems like a common theme, or more generally: "I don't store a X but I know how to do something with one".

1 Like
5

As an exercise, I tried implementing these types in nightly Rust using generic associated types, and they actually work pretty well here:

The only real downside is that a few more turbofishes are necessary to resolve to the correct RefKind.

6

That's pretty interesting. I guessed that GATs would make things easier, but I am kind of waiting for support to come into the lang (I mean, not just the feature, but stuff like RcKind and RefKind that you have added here.

The only other downside of the way that you have it is my version allows me to express types like
VecIndex<AnnotatedAxiom<Rc<str>> as opposed to VecIndex<Rc<AnnotatedAxiom<Rc<str>>>. Although I wasn't planning this, it has the advantage that when only using a single index, I don't have the runtime cost of an Rc that I no longer need. Easy to fix by adding two generic types which my system requires.

7

Note that to support VecIndex<AnnotatedAxiom<...>>, you'd need to add an impl<A: ForIRI> AsRef<AnnotatedAxiom<A>> for AnnotatedAxiom<A>, since AsRef isn't reflexive by default. Admittedly, my GAT solution wouldn't work, since it requires that R::Ref<T>: Sized even when T: !Sized. I'd probably need to add a separate SizedRefKind trait with a ValueKind that implements it. Although one can get close with a BoxKind:

#[derive(Debug, Eq, Hash, PartialEq)]
pub struct BoxKind;

impl private::Sealed for BoxKind {}

impl RefKind for BoxKind {
    type Ref<T: ?Sized> = Box<T>
    where
        T: Debug + Eq + Hash;
}

And as you mentioned, the inner and outer RefKinds can easily be split apart:

pub trait Index<RA: RefKind, RI: RefKind> {
    fn add(&mut self, ax: RA::Ref<AnnotatedAxiom<RI>>) -> bool;
    fn remove(&mut self, ax: &AnnotatedAxiom<RI>) -> bool;
}

#[derive(Debug)]
pub struct VecIndex<RA: RefKind, RI: RefKind>(Vec<RA::Ref<AnnotatedAxiom<RI>>>);

#[derive(Debug)]
pub struct SetIndex<RA: RefKind, RI: RefKind>(HashSet<RA::Ref<AnnotatedAxiom<RI>>>);

// Adjust impls as necessary
8

Interesting point about the AsRef impl for AnnotatedAxiom. I hadn't done this and yet it was working which confused me for a bit. The actual answer is, I think, that I have dropped AsRef from ForIRI and ForIndex and just require Borrow which has a blanket implementation for any T.

I shall revisit this design when GATs are live. Although it would might a large number of changes to my code base to re-implement, it might be worth it.

9

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.