Цепные итераторы для ссылок на разные жизненные циклы

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

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

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, этот на самом деле не решает проблему., поскольку компилятор застревает в бесконечном цикле при компиляции proceed для всех вложенных Chain, когда кто-то действительно пытается вызвать функцию.


iterator rust lifetime chain
person mrspl    schedule 17.02.2020    source источник
comment
Вы попадаете в лабиринт маленьких извилистых ошибок компилятора, и все они разные. Если я исправлю первую ошибку, все будет в порядке сначала, но если вы попытаетесь вызвать proceed в любом месте, компилятор попытается вычислить бесконечный тип (потому что для компиляции proceed<I> вы должны сначала скомпилировать proceed<Chain<I, Once<String>>>, а чтобы скомпилировать это, вы должны сначала скомпилировать proceed<Chain<Chain<I, Once<String>>, Once<String>>> и т.д. Теперь вы можете решить эту проблему с помощью динамической отправки ...   -  person trentcl    schedule 17.02.2020
comment
... но это просто толкает вас дальше в лабиринт: ancestors нельзя разрешить заимствовать из remaining, так как вы обходите Vec деструктивно, поэтому вы не можете применить ту же стратегию для итерации по дереву по ссылке. Я не уверен, как лучше всего ответить на этот вопрос, потому что исправление текущей ошибки компилятора явно не решает проблему. Я настоятельно рекомендую вам сделать шаг назад и переоценить, как вы сюда попали; скорее всего найдется более простое решение. (Прочтите Изучите Rust с слишком большим количеством связанных списков, если у вас нет т уже.)   -  person trentcl    schedule 17.02.2020

Ответы (1)


arrow_upward
1
arrow_downward

Кусочки решения уже есть, просто подведем итог:

Как вы уже знаете, использование 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());
}
person attdona    schedule 17.02.2020