Цепные итераторы к ссылкам разных жизненных сил - PullRequest
Новая
       42

Цепные итераторы к ссылкам разных жизненных сил

0 голосов
/ 17 февраля 2020

Я хочу построить рекурсивную функцию для обхода дерева в Rust. Функция всегда должна получать следующий элемент и итератор по ссылкам на элементы-предки.

Для итератора по элементам-предкам в принципе можно использовать методы chain и once. Рассмотрим следующий простой пример, где дерево - это Ve c (для целей этой демонстрации): 

fn proceed<'a, I>(mut remaining: Vec<String>, ancestors: I)
where
    I: Iterator<Item = &'a String> + Clone,
{
    if let Some(next) = remaining.pop() {
        let next_ancestors = ancestors.chain(std::iter::once(&next));
        proceed(remaining, next_ancestors);
    }
}

Детская площадка

Это не удается компилировать, потому что &next имеет более короткое время жизни, чем 'a: 

error[E0597]: `next` does not live long enough
 --> src/lib.rs:6:62
  |
1 | fn proceed<'a, I>(mut remaining: Vec<String>, ancestors: I)
  |            -- lifetime `'a` defined here
...
6 |         let next_ancestors = ancestors.chain(std::iter::once(&next));
  |                              --------------------------------^^^^^--
  |                              |                               |
  |                              |                               borrowed value does not live long enough
  |                              argument requires that `next` is borrowed for `'a`
7 |         proceed(remaining, next_ancestors);
8 |     }
  |     - `next` dropped here while still borrowed

Я попытался преодолеть это путем добавления явного второго времени жизни 'b: 'a и принудительного использования явной ссылки чем-то вроде let next_ref: &'b String = &next, но это также приводит к (другому) сообщению об ошибке.

Одно из решений, которое я придумала, это вызвать map следующим образом: 

let next_ancestors = ancestors.map(|r| r).chain(std::iter::once(&next));

Как указано @trentcl, это на самом деле не решает проблему , поскольку компилятор застревает в бесконечном l oop при компиляции proceed для всех вложенных Chain s, когда кто-то пытается вызвать функцию.

1 Ответ

1 голос
/ 18 февраля 2020

Части решения уже есть, просто подытожим:

Как вы уже знаете, использование map(|r| r) "разъединяет" требование времени жизни ancestors от времени жизни &next.

Как уже отмечалось в комментариях, исправление бесконечной рекурсии - это вопрос изменения ancestors в объект черты. 

fn proceed<'a>(mut remaining: Vec<String>, ancestors: &mut dyn Iterator<Item = &'a String>) {
    if let Some(next) = remaining.pop() {
        let mut next_ancestors = ancestors.map(|r| r).chain(std::iter::once(&next));
        proceed(remaining, &mut next_ancestors);
    }
}

fn main() {
    let v = vec!["a".to_string(), "b".to_string()];
    proceed(v, &mut std::iter::empty());
}
...