Переполнение при оценке требования при возврате рекурсивного итератора с использованием impl trait - PullRequest
Новая
       26

Переполнение при оценке требования при возврате рекурсивного итератора с использованием impl trait

0 голосов
/ 31 декабря 2018

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

#[derive(Debug, Eq, PartialEq)]
struct Node {
    metadata: Vec<i64>,
    children: Vec<Box<Node>>,
}

impl Node {
    fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
        self.children
            .iter()
            .map(|child| child.depth_first_metadata_iter())
            .flatten()
            .chain(self.metadata.iter())
    }
}

fn main() {
    let tree = Node {
        metadata: vec![1, 2, 3],
        children: vec![
            Box::new(Node {
                metadata: vec![4, 5],
                children: vec![],
            }),
            Box::new(Node {
                metadata: vec![6, 7],
                children: vec![],
            }),
        ],
    };
    println!(
        "{:?}",
        tree.depth_first_metadata_iter().collect::<Vec<&i64>>()
    );
}

Однако при компиляции я получаю следующееошибка: 

error[E0275]: overflow evaluating the requirement `impl std::iter::Iterator`
  |
  = help: consider adding a `#![recursion_limit="128"]` attribute to your crate

(Вы можете проверить это самостоятельно на детской площадке .)

Имеет смысл, что это будет ошибкой, так как я делаю рекурсивныйвызовы внутри depth_first_metadata_iter, которые возвращают вложенные итераторы, но было бы очень хорошо, если бы что-то вроде этого кода могло работать без необходимости реализации собственного итератора.

Все другие решения ошибки E0275, которые я видел (например, это , это , это ), похоже, связаны со стратегическим размещениемгде-то аннотация типа - возможно ли что-то подобное здесь, или я пытаюсь сделать что-то «невозможное»?

1 Ответ

0 голосов
/ 31 декабря 2018

, если что-то вроде этого кода может работать

Зависит от того, насколько "как" вы имеете в виду.Это похоже, работает и не требует специального итератора;таким образом отвечая всем вашим требованиям: 

fn depth_first_metadata_iter(&self) -> Box<Iterator<Item = &i64> + '_> {
    Box::new({
        self.children
            .iter()
            .flat_map(|child| child.depth_first_metadata_iter())
            .chain(self.metadata.iter())
    })
}

По сути, это та же проблема, что показана в

Поставьте себя на место компилятора некоторое время.Ваш оригинальный код говорит: «Я собираюсь вернуть конкретный тип итератора, но я не собираюсь говорить точный тип».Компилятор все еще должен иметь возможность определить этот тип, поэтому давайте будем компилятором: 

let a = self.children.iter();
// std::slice::Iter<'_, Box<Node>>

let cls = |child| child.depth_first_metadata_iter();
// Fn(&Box<Node>) -> ?X?

let b = a.flat_map(cls);
// FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>

let d = self.metadata.iter();
// std::slice::Iter<'_, i64>

b.chain(d);
// Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>>

Этот конечный результат является возвращаемым значением, поэтому у нас есть уравнение: 

Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>> === ?X?

AFAIK, невозможно выполнить алгебру уровня типа, чтобы решить для ?X?, таким образом, вы получите ошибку.

Изменение типа возвращаемого значения в объекте с признаками в штучной упаковке замыкает всю необходимую логику и вызываетконкретный тип бетона.

стратегическое размещение где-то аннотации типа

Я не верю, что это так.Если это так, это будет означать, что алгебра разрешима, но компилятор не достаточно умен, чтобы ее решить.Хотя это, несомненно, верно в других ситуациях, я не думаю, что это здесь.

Я не думаю, что это замечательное решение, так как в нем будет многокрошечные выделения.Я бы предположил (но не проверял), что пользовательский итератор, использующий структуру данных стека, будет более эффективным.

Срединной точкой было бы построение всего набора узлов: 

impl Node {
    fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
        self.x().into_iter()
    }

    fn x(&self) -> Vec<&i64> {
        fn x_inner<'a>(node: &'a Node, v: &mut Vec<&'a i64>) {
            for c in &node.children {
                x_inner(c, v)
            }
            v.extend(&node.metadata);
        }

        let mut v = Vec::new();
        x_inner(self, &mut v);
        v
    }
}
...