Плохой дизайн для программы Rust со временем жизни и множественными ссылками

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

Однако у меня есть две проблемы. Первое связано со временем жизни структуры Boxed внутри вектора algorithms.

error: lifetime may not live long enough
  --> main.rs:67:29
   |
51 |   impl<'a> Solver<'a> {
   |        -- lifetime `'a` defined here
...
63 |       pub fn solve(&mut self) {
   |                    - let's call the lifetime of this reference `'1`
...
67 |               let algorithm = Box::new(MyAlgorithm {
   |  _____________________________^
68 | |                 graph: &mut self.graph,
69 | |             });
   | |______________^ assignment requires that `'1` must outlive `'a`

Я изо всех сил старался указать компилятору, что время жизни структуры Algorithm должно оставаться в пределах времени жизни структуры Solver, но это не сработало.

По завершении своей работы Algorithm потребуется обновить узлы и ребра графа, поэтому ему требуется изменяемая ссылка на объект графа. Однако это, конечно, неверно из-за второго изменяемого заимствования.

cannot borrow `self.graph` as mutable more than once at a time
second mutable borrow occurs here

Ниже приведен код.

struct Node {
    // Define the Node struct...
}

impl Node {
    // Implement methods for Node...
}

struct Graph {
    nodes: Vec<Node>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            nodes: Vec::new(),
            // Initialize other fields...
        }
    }
}

trait BaseAlgorithm<'a> {
    // Define the trait methods...
}

// Create a MyAlgorithm struct that takes a mutable reference to the graph
struct MyAlgorithm<'a> {
    graph: &'a mut Graph,
}

impl<'a> BaseAlgorithm<'a> for MyAlgorithm<'a> {
    // Implement the trait methods for MyAlgorithm...
}

struct Solver<'a> {
    algorithms: Vec<Box<dyn BaseAlgorithm<'a> + 'a>>,
    graph: Graph,
}

impl<'a> Solver<'a> {
    fn new() -> Self {
        Solver {
            algorithms: Vec::new(),
            graph: Graph::new(),
        }
    }

    fn add_algorithm(&mut self, algorithm: Box<dyn BaseAlgorithm<'a> + 'a>) {
        self.algorithms.push(algorithm);
    }

    pub fn solve(&mut self) {
        // Loop over the nodes vector within Graph
        for node in &mut self.graph.nodes {
            // add an algorithm with a mutable reference to Graph
            let algorithm = Box::new(MyAlgorithm {
                graph: &mut self.graph,
            });
            self.add_algorithm(algorithm);
        }
    }
}

fn main() {
    let mut solver = Solver::new();

    solver.solve();
}

Если дизайн можно исправить, я был бы очень признателен за любую помощь в этом. Однако, если дизайн невозможно исправить, существует ли идиоматический шаблон Rust для достижения требований этой логики?

Вместо хранения &mut Graph в MyAlgorithm вы также можете передать &mut Graph методу, требующему его в trait BaseAlgorithm.

vallentin 06.05.2024 00:48

Спасибо за быстрый ответ! Я экспериментирую с этой идеей, и она работает для упрощенного примера, приведенного выше, и это здорово. Это потребует немалого рефакторинга реального кода, поэтому я пока не знаю, работает ли он, но я попробую и сообщу вам, как это выглядит.

RedPen 06.05.2024 01:00
Почему Python в конце концов умрет
Почему Python в конце концов умрет
Последние 20 лет были действительно хорошими для Python. Он прошел путь от "просто языка сценариев" до основного языка, используемого для написания...
0
2
71
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Если алгоритмы действительно требуют постоянно изменяемого доступа к графу, то &mut не сможет этого добиться. Вам нужно будет обеспечить изменчивость другим способом, используя внутреннюю изменчивость. Если программа однопоточная, вы можете использовать RefCell, а если многопоточная, Mutex или RwLock. Таким образом, вы можете сохранить свой график как RefCell<Graph>. Это позволяет заимствовать график с возможностью изменения, даже если у вас есть только неизменяемая ссылка на RefCell. Тогда может сработать простое заимствование ячейки ref в каждый из алгоритмов, например Algorithm{ graph: &self.graph }, но если нет, вы можете заставить ее работать, введя подсчет ссылок. Это позволяет вам не беспокоиться о времени жизни, поскольку все ссылки на данные подсчитываются, и они будут удалены, когда ссылок не останется. Типы указателей с подсчетом ссылок: Rc для однопоточного и Arc для многопоточного. Таким образом, вы можете сохранить свой график как Rc<RefCell<Graph>> или Arc<RwLock<Graph>> в зависимости от многопоточности. Теперь, используя Rc или Arc, вы можете вызвать clone(), чтобы получить второй Rc или Arc, указывающий на те же данные, что и первый. Если эти данные являются внутренними изменяемыми, например RefCell, Mutex или RwLock, то вы можете заимствовать их содержимое с возможностью изменения.

Спасибо за Ваш ответ. Просмотрев кодовую базу и проведя ее рефакторинг, как было предложено, я действительно могу просто передать ссылку на граф в функции, а не сохранять ссылки. Это упростило код! Также +1 за объяснение RefCell и связанных с ним вопросов — это помогло! Спасибо.

RedPen 06.05.2024 14:47

Другие вопросы по теме