Достигнут предел длины типа при создании экземпляра std :: vec :: IntoIter

Question

Я пытаюсь реализовать структуру Tree, но получаю сообщение об ошибке, когда пытаюсь запустить следующий код:

fn main() {
    let tree = Tree::create(1, |_| Vec::new());
    println!("{:?}", tree);
}

#[derive(Debug)]
struct Tree<T> {
    value: T,
    children: Vec<Tree<T>>,
}

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    where
        F: Fn(&T) -> Vec<T>,
    {
        let children = get_children(&value);
        Tree {
            value,
            children: children
                .into_iter()
                .map(|x| Tree::create(x, |y| get_children(y)))
                .collect(),
        }
    }
}

Ошибка:

error: reached the type-length limit while instantiating `<std::vec::IntoIter<i32> as std::iter::Iterator>::map::<Tree<i32...`
  |
  = note: consider adding a `#![type_length_limit="2097152"]` attribute to your crate

Answer 1

Это та же основная проблема, что и Что означает «Переполнение при оценке потребности» и как я могу это исправить? и может быть решена таким же образом.Это означает, что вы избегаете рекурсии на уровне типов, используя объект ссылочной черты:

impl<T> Tree<T> {
    fn create(value: T, mut get_children: impl FnMut(&T) -> Vec<T>) -> Tree<T> {
        fn create_inner<T>(value: T, get_children: &mut FnMut(&T) -> Vec<T>) -> Tree<T> {
            let children = get_children(&value)
                .into_iter()
                .map(|x| create_inner(x, get_children))
                .collect();

            Tree { value, children }
        }

        create_inner(value, &mut get_children)
    }
}

Я также переключился с Fn на FnMut, так как лучше быть более гибким с типами замыканий, когдавозможно.

Answer 2

Вы делаете рекурсивный вызов при создании Tree<T>:

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    //...
    //...
        .map(|x| Tree::create(x, |y| get_children(y))) //endless recursive call

Я запутался, почему это бесконечно повторяется, так как я возвращал пустой вектор в замыкании.

Эта ошибка возникает во время компиляции, и ошибка говорит, что reached the type-length limit while instantiating....Это означает, что вы генерируете чрезвычайно длинный тип.

Как это происходит?

Когда вы вызываете Tree::create(x, |y| get_children(y)), вы создаете аргумент замыкания, который вызывает существующее замыкание.Это нормально, но когда вы вызываете его рекурсивно, компилятор не сможет обнаружить тип F при самом внутреннем вызове.

Помните, get_children имеет тип F, где F: Fn(&T) -> Vec<T>.Когда вы звоните Tree::create в первый раз, F в create<F> будет выглядеть следующим образом:

let tree = Tree::create(1, |_| Vec::new());
//inference of F: Fn(&T) -> Vec<T>

После второго вызова в map(...):

Tree::create(x, |y| get_children(y))
//inference of F: Fn(&T) -> Fn(&T) -> Vec<T>

Тогда это в конечном итоге превратится в следующее:

//inference of F: Fn(&T)-> Fn(&T) -> Fn(&T) -> Vec<T>
//inference of F: Fn(&T)-> ... -> Fn(&T) -> Fn(&T) -> Vec<T>

В конце компилятор достигает предела длины шрифта.

Решение с рекурсией

Как дополнение к Ответ Shepmaster , вы можете использовать функциональные указатели :

impl<T> Tree<T> {
    fn create(value: T, get_children: fn(&T) -> Vec<T>) -> Tree<T> {
        let children = get_children(&value);
        Tree {
            value,
            children: children
                .into_iter()
                .map(|x| Tree::create(x, get_children))
                .collect(),
        }
    }
}

Решение без рекурсии

Вы можете решить проблему, отправив функцию на Vec<Tree<T>> как get_children вместо генерации в create, например:

fn main() {
    let inner_tree = Tree::create(1, |_| Vec::new());
    let tree = Tree::create(1, move |_| vec![inner_tree]);
    println!("{:?}", tree);
}

#[derive(Debug)]
struct Tree<T> {
    value: T,
    children: Vec<Tree<T>>,
}

impl<T> Tree<T> {
    fn create<F>(value: T, get_children: F) -> Tree<T>
    where
        F: FnOnce(&T) -> Vec<Tree<T>>,
    {
        let children = get_children(&value);
        Tree { value, children }
    }
}

Обратите внимание, что я изменил тип параметра функции с Fn на FnOnce.Это необходимо, чтобы переместить владение внутренними деревьями в замыкание.Он будет вызван один раз, чтобы он мог использовать переменную.