Why does using an associated type break variance

help
#1

This code is distilled from a variation on the implementation of BTreeMap. I've defined a NodeTypeTrait trait that in turn defines an associated type E. This example largely compiles (and all the other code and tests left out here compile too), but fails at a variance unit test as shown. Yet it all compiles fine when you switch to the commented out definition of type InternalNode<T>, which in my mind simply spells out the same type. What is so special about this particular use of the associated type that it breaks variance? I have other references to the associated type (left out of this example) that work fine.

#![allow(dead_code)]
use std::ptr::NonNull;

struct LeafData<T> {
    data: T,
    parent: NonNull<InternalNode<T>>,
}

pub struct Node<T, E> {
    leaf: LeafData<T>,
    edge: E,
}

pub trait NodeTypeTrait<T> {
    type E;
}

impl<T> NodeTypeTrait<T> for marker::Internal {
    type E = BoxedNode<T>;
}

type InternalNode<T> = Node<T, <marker::Internal as NodeTypeTrait<T>>::E>;
//type InternalNode<T> = Node<T, BoxedNode<T>>;

pub struct BoxedNode<T> {
    ptr: Box<LeafData<T>>,
}

pub mod marker {
    pub enum Internal {}
}

pub struct BTreeMap<T> {
    root: BoxedNode<T>,
}

fn main() {
    fn map_key<'new>(v: BTreeMap<&'static str>) -> BTreeMap<&'new str> {
        v
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/main.rs:39:9
   |
39 |         v
   |         ^ lifetime mismatch
   |
   = note: expected struct `BTreeMap<&'new str>`
              found struct `BTreeMap<&'static str>`
note: the lifetime `'new` as defined on the function body at 38:16...
  --> src/main.rs:38:16
   |
38 |     fn map_key<'new>(v: BTreeMap<&'static str>) -> BTreeMap<&'new str> {
   |                ^^^^
   = note: ...does not necessarily outlive the static lifetime
1 Like
#2

There's some discussion of this problem here: https://github.com/rust-lang/rust/issues/21726

1 Like
#3

Phew, I got it working. That discussion contains the crucial hint. Applying that here, there's a twist: LeafData<T> kind of recurses back to InternalNode<T>, so the definition of InternalNode<T> needs to repeat the type anyway.

But that duplication isn't too bad and it makes the definition of Node with a Type argument, which is what I wanted anyways.

2 Likes