«переполнение при добавлении правил проверки кавычек» при реализации fingertree

Question

Я пытаюсь определить структуру пальцевого дерева и реализовать его основные операции как упражнение в Rust. Я придумал следующее: это в основном то, что описано в этом paper.

use self::FingerTree::{Empty, Single, Deep}; 
use self::Digit::{One, Two, Three, Four}; 

enum Digit<A> { 
    One(A), 
    Two(A, A), 
    Three(A, A, A), 
    Four(A, A, A, A), 
} 

enum Node<V, A> { 
    Node2(V, A, A), 
    Node3(V, A, A, A), 
} 

enum FingerTree<V, A> { 
    Empty, 
    Single(A), 
    Deep { 
     size: V, 
     prefix: Digit<A>, 
     tree: Box<FingerTree<V, Node<V, A>>>, 
     suffix: Digit<A>, 
    }, 
} 

fn main() { 
    let e: FingerTree<i32, String> = Empty; 
} 

Компиляция дает мне ошибку, что я не понимаю:

error[E0320]: overflow while adding drop-check rules for FingerTree<i32, std::string::String> 
    --> fingertree.rs:28:9 
    | 
28 |  let e: FingerTree<i32, String> = Empty; 
    |  ^
    | 
note: overflowed on enum Node variant Node2 field 0 type: i32 
    --> fingertree.rs:28:9 
    | 
28 |  let e: FingerTree<i32, String> = Empty; 
    |  ^

error[E0320]: overflow while adding drop-check rules for FingerTree<i32, std::string::String> 
    --> fingertree.rs:28:38 
    | 
28 |  let e: FingerTree<i32, String> = Empty; 
    |          ^^^^^ 
    | 
note: overflowed on enum Node variant Node2 field 0 type: i32 
    --> fingertree.rs:28:38 
    | 
28 |  let e: FingerTree<i32, String> = Empty; 
    |          ^^^^^ 

Почему это не работает? Как мне заставить работать?

Answer 1

Вы создали бесконечный тип.

Создание экземпляра FingerTree<V, A> экземпляров FingerTree<V, Node<V, A>>, который создает экземпляр FingerTree<V, Node<V, Node<V, A>>>, который создает экземпляры, ... и нет конца.

Компилятор не может сказать, что тип фактически не будет использоваться во время выполнения, поэтому готовится к худшему. И худшее бесконечно.

Просто заменив тип tree на Box<FingerTree<V, A>>, эта проблема решается, хотя это может быть неправильной ситуации.