我正在尝试使用特征做一些类型级编程,并遇到了一个边缘情况,编译器在试图证明约束的同时无限扩展类型,而我期望它收敛。
这个错误也是不稳定的,因为我不希望有什么不同的小变化突然导致程序成功编译。
我很难理解第一个让编译器发疯的程序有什么特别之处。是不是缺少了某种约束?
原始程序出错
这是原始程序。这已被大大减少,以重现错误。最初的代码实际上是由一个名为typ
的实验类型级编程箱中的宏生成的。
// Just setting up some simple type level lists.
pub struct HCons<H, T> {
pub head: H,
pub tail: T,
}
pub struct HNil;
pub trait HList {}
impl HList for HNil {}
impl<H, T: HList> HList for HCons<H, T> {}
// Trait-encoded type level function that maps over these lists
pub trait MapList<L> {
type Output;
}
impl MapList<HNil> for () {
type Output = HNil;
}
impl<X, T: HList> MapList<HCons<X, T>> for () where (): DoMapList<T> {
type Output = HCons<X, <() as DoMapList<T>>::Output>;
}
// Trait-encoded type level function that calls the other function
pub trait DoMapList<L: HList> where Self::Output: HList {
type Output;
}
impl<L: HList> DoMapList<L> for () where
(): MapList<L>,
<() as MapList<L>>::Output: HList
{
type Output = <() as MapList<L>>::Output;
}
// Helper type
type DoMapListOp<L> = <() as DoMapList<L>>::Output;
pub struct Intermediate<A: HList> where (): DoMapList<A> {
pub foo: DoMapListOp<A>,
}
pub trait Tester<A: HList> where (): DoMapList<A> {
fn foo() -> Intermediate<A>;
}
struct Bar;
impl Tester<HCons<i32, HNil>> for Bar {
fn foo() -> Intermediate<HCons<i32, HNil>> {
return Intermediate { foo: HCons { head: 5, tail: HNil {} } }
}
}
error[E0275]: overflow evaluating the requirement `(): DoMapList<_>`
--> <source>:55:16
|
55 | return Intermediate { foo: HCons { head: 5, tail: HNil {} } }
| ^^^^^^^^^^^^
|
= help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`example`)
note: required because of the requirements on the impl of `MapList<HCons<_, _>>` for `()`
--> <source>:20:19
|
20 | impl<X, T: HList> MapList<HCons<X, T>> for () where (): DoMapList<T> {
| ^^^^^^^^^^^^^^^^^^^^ ^^
note: required because of the requirements on the impl of `DoMapList<HCons<_, _>>` for `()`
--> <source>:30:16
|
30 | impl<L: HList> DoMapList<L> for () where
| ^^^^^^^^^^^^ ^^
= note: 126 redundant requirements hidden
= note: required because of the requirements on the impl of `DoMapList<HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>` for `()`
note: required by a bound in `Intermediate`
--> <source>:43:45
|
43 | pub struct Intermediate<A: HList> where (): DoMapList<A> {
| ^^^^^^^^^^^^ required by this bound in `Intermediate`
error: aborting due to previous error
For more information about this error, try `rustc --explain E0275`.
Compiler returned: 1
Godbolt
Intermediate
newtype被移除,编译
这是一个版本,我删除了Intermediate
newtype。
// Just setting up some simple type level lists.
pub struct HCons<H, T> {
pub head: H,
pub tail: T,
}
pub struct HNil;
pub trait HList {}
impl HList for HNil {}
impl<H, T: HList> HList for HCons<H, T> {}
// Trait-encoded type level function that maps over these lists
pub trait MapList<L> {
type Output;
}
impl MapList<HNil> for () {
type Output = HNil;
}
impl<X, T: HList> MapList<HCons<X, T>> for () where (): DoMapList<T> {
type Output = HCons<X, <() as DoMapList<T>>::Output>;
}
// Trait-encoded type level function that calls the other function
pub trait DoMapList<L: HList> where Self::Output: HList {
type Output;
}
impl<L: HList> DoMapList<L> for () where
(): MapList<L>,
<() as MapList<L>>::Output: HList
{
type Output = <() as MapList<L>>::Output;
}
// Helper type
type DoMapListOp<L> = <() as DoMapList<L>>::Output;
pub trait Tester<A: HList> where (): DoMapList<A> {
fn foo() -> DoMapListOp<A>;
}
struct Bar;
impl Tester<HCons<i32, HNil>> for Bar {
fn foo() -> DoMapListOp<HCons<i32, HNil>> {
return HCons { head: 5, tail: HNil {} }
}
}
Godbolt
删除DoMapList
特性,编译
下一个版本,我删除了中间的DoMapList
特征。
// Just setting up some simple type level lists.
pub struct HCons<H, T> {
pub head: H,
pub tail: T,
}
pub struct HNil;
pub trait HList {}
impl HList for HNil {}
impl<H, T: HList> HList for HCons<H, T> {}
// Trait-encoded type level function that maps over these lists
pub trait MapList<L> {
type Output;
}
impl MapList<HNil> for () {
type Output = HNil;
}
impl<X, T: HList> MapList<HCons<X, T>> for () where (): MapList<T> {
type Output = HCons<X, <() as MapList<T>>::Output>;
}
// Helper type
type DoMapListOp<L> = <() as MapList<L>>::Output;
pub struct Intermediate<A: HList> where (): MapList<A> {
pub foo: DoMapListOp<A>,
}
pub trait Tester<A: HList> where (): MapList<A> {
fn foo() -> Intermediate<A>;
}
struct Bar;
impl Tester<HCons<i32, HNil>> for Bar {
fn foo() -> Intermediate<HCons<i32, HNil>> {
return Intermediate { foo: HCons { head: 5, tail: HNil {} } }
}
}
Godbolt
MapList
trait调用自身,编译
最后我有一个版本,我保持DoMapList
性状,但使MapList
性状直接调用自己。
// Just setting up some simple type level lists.
pub struct HCons<H, T> {
pub head: H,
pub tail: T,
}
pub struct HNil;
pub trait HList {}
impl HList for HNil {}
impl<H, T: HList> HList for HCons<H, T> {}
// Trait-encoded type level function that maps over these lists
pub trait MapList<L> {
type Output;
}
impl MapList<HNil> for () {
type Output = HNil;
}
impl<X, T: HList> MapList<HCons<X, T>> for () where (): MapList<T> {
type Output = HCons<X, <() as MapList<T>>::Output>;
}
// Trait-encoded type level function that calls the other function
pub trait DoMapList<L: HList> where Self::Output: HList {
type Output;
}
impl<L: HList> DoMapList<L> for () where
(): MapList<L>,
<() as MapList<L>>::Output: HList
{
type Output = <() as MapList<L>>::Output;
}
// Helper type
type DoMapListOp<L> = <() as DoMapList<L>>::Output;
pub struct Intermediate<A: HList> where (): DoMapList<A> {
pub foo: DoMapListOp<A>,
}
pub trait Tester<A: HList> where (): DoMapList<A> {
fn foo() -> Intermediate<A>;
}
struct Bar;
impl Tester<HCons<i32, HNil>> for Bar {
fn foo() -> Intermediate<HCons<i32, HNil>> {
return Intermediate { foo: HCons { head: 5, tail: HNil {} } }
}
}
Godbolt
Rust Programming discord上有人告诉我这是trait系统中的一个bug。