Rust中的类型级别映射

Question

我正在尝试在两种类型之间创建一个类型级别的映射,实现为关联列表,以便有效的映射实现特征:

trait Key {
    const KEY: usize;
}

trait TypeLevelMap<K: Key, V> {
    fn convert(K) -> V;
}

零案例很简单:

struct TypeLevelMapNil<T>(PhantomData<T>);

impl<K: Key, V> TypeLevelMap<K, V> for TypeLevelMapNil<V> {
    fn convert(k: K) -> V {
        panic!("Unhandled case: {}", K::KEY);
    }
}

但是,我无法弄清楚这种情况:

struct TypeLevelMapCons<K, V, Tl, TlK, TlV>(PhantomData<(K, V, Tl, TlK, TlV)>);

impl<K, V, Tl, TlK, TlV> TypeLevelMap<K,V> for TypeLevelMapCons<K, V, Tl, TlK, TlV>
where
    K: Key,
    Tl: TypeLevelMap<TlK, TlV>,
    TlK: Key,
{
    fn convert(_k: K) -> V {
        unimplemented!()
    }
}

impl<K, V, Tl, TlK, TlV> TypeLevelMap<TlK, TlV> for TypeLevelMapCons<K, V, Tl, TlK, TlV>
where
    K: Key,
    Tl: TypeLevelMap<TlK, TlV>,
    TlK: Key,
{
    fn convert(k: TlK) -> TlV {
        Tl::convert(k)
    }
}

这当然会给出一个错误," TypeLevelMap<_, _>类型特征的冲突实现TypeLevelMapCons<_, _, _, _, _>".我无法弄清楚如何告诉Rust更喜欢第一个; 专业化没有帮助,并没有!=在哪里界限.

有没有办法消除它们的歧义,或者是否有另一种方法来实现它,或者这是不可能在(当前)Rust中实现的？

Answer 1

如果我理解正确,您试图使用不同的泛型类型参数组合TypeLevelMapCons<K, V, Tl, TlK, TlV>实现TypeLevelMap两次.这是不可能的(从Rust 1.23.0开始),因为有可能K == TlK或那样V == TlV.通过特化,其中一个impls必须严格比"默认"impl更具体,即它必须应用于"默认"impl适用的子集,仅此而已.然而,在这里,K并且TlK是无关的(同样对于V和TlV),因此两者都不比另一个更具体.有一个被称为交集impls的提议功能,据我所知,它应该解决这个问题,因为它允许你编写覆盖交集的impl,以便修复冲突的实现错误.

但是,是采用专门的解决方案!第一步是改为TypeLevelMap不是通用本身; 相反,我们将convert通过从那里的特征移动类型参数来使方法通用.通过这样做,我们可以删除TlK和TlV类型上的参数TypeLevelMapCons,这是没有用的,因为它们只代表一个的可能许多实现的TypeLevelMap,该尾部可能(事实上,我认为当前的设计是因为这个行不通).

实现TypeLevelMap了TypeLevelMapNil很简单:我们简单地忽略类型参数.(注:我已删除的类型参数TypeLevelMapNil,因为它是不必要的.)实现TypeLevelMap了TypeLevelMapCons是有点棘手,因为这是我们需要不同的行为取决于密钥类型.

专业化不允许我们在泛型方法上专门化特定的类型参数集,仅在impls上,所以我们如何实现TypeLevelMapCons？通过引入辅助通用特性!我们可以有一个处理递归情况的特征的默认实现,以及一个处理"找到"情况的专用实现.(注意:这与标准库用于专门化的技术相同<Vec<T> as Extend<T>>::extend<I>.)

#![feature(specialization)]

use std::marker::PhantomData;

trait Key {
    const KEY: usize;
}

trait TypeLevelMap {
    fn convert<K: Key, V>(K) -> V;
}

trait TypeLevelMapConvert<LK, LV> {
    fn convert_impl(LK) -> LV;
}

struct TypeLevelMapNil;

impl TypeLevelMap for TypeLevelMapNil {
    fn convert<K: Key, V>(_k: K) -> V {
        panic!("Unhandled case: {}", K::KEY);
    }
}

struct TypeLevelMapCons<K, V, Tl>(PhantomData<(K, V, Tl)>);

impl<K, V, Tl> TypeLevelMap for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
{
    fn convert<LK: Key, LV>(k: LK) -> LV {
        <Self as TypeLevelMapConvert<LK, LV>>::convert_impl(k)
    }
}

impl<K, V, Tl, LK, LV> TypeLevelMapConvert<LK, LV> for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
    LK: Key,
{
    default fn convert_impl(k: LK) -> LV {
        Tl::convert(k)
    }
}

impl<K, V, Tl> TypeLevelMapConvert<K, V> for TypeLevelMapCons<K, V, Tl>
where
    K: Key,
    Tl: TypeLevelMap,
{
    fn convert_impl(_k: K) -> V {
        unimplemented!()
    }
}

// Sample usage

impl Key for i16 {
    const KEY: usize = 16;
}

impl Key for i32 {
    const KEY: usize = 32;
}

impl Key for i64 {
    const KEY: usize = 64;
}

fn main() {
    TypeLevelMapCons::<i16, i16, TypeLevelMapCons<i32, i32, TypeLevelMapCons<i64, i64, TypeLevelMapNil>>>::convert::<i64, i64>(0);
}

为什么这次专业化工作？首先,让我们看看默认的impl:

impl<K, V, Tl, LK, LV> TypeLevelMapConvert<LK, LV> for TypeLevelMapCons<K, V, Tl>

在这里,LK并且LV是独立的K和V分别.这意味着此impl将为特定TypeLevelMapCons<K, V, Tl>类型生成无限数量的具体特征实现.

现在,我们来看看专门的impl:

impl<K, V, Tl> TypeLevelMapConvert<K, V> for TypeLevelMapCons<K, V, Tl>

这是我们在特征和实施者类型上使用K和使用的V.通过这样做,我们在K和上引入了等式约束V.这意味着此impl将仅为特定TypeLevelMapCons<K, V, Tl>类型生成单个特征实现.这显然是更具体的默认impl!