具有许多可变引用的 Rust 回溯树结构

Question

我正在尝试构建一个能够保存进化模拟内容的数据结构。我发现了一堆令人讨厌的解决方案来连续种植树，然后启用回溯。它可以工作，但是我不确定我是否在代码的回溯部分产生了内存泄漏。

我附加了大部分不是构造函数等的代码，特别是我不确定 Descendant::get_sequence() 因为我必须在那里使用不安全的代码。

问题：Descendant::get_sequence()是否有内存泄漏？

use derivative::Derivative;
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Derivative)]
#[derivative(Debug)]
pub enum Haplotype {
    Wildtype(Wildtype),
    Descendant(Descendant),
}

#[derive(Derivative)]
#[derivative(Debug)]
pub struct Wildtype {
    #[derivative(Debug = "ignore")]
    reference: Option<Rc<RefCell<Haplotype>>>,
    sequence: Vec<u8>,
    descendants: Vec<Rc<RefCell<Haplotype>>>,
}

#[derive(Derivative)]
#[derivative(Debug)]
pub struct Descendant {
    #[derivative(Debug = "ignore")]
    reference: Option<Rc<RefCell<Haplotype>>>,
    #[derivative(Debug = "ignore")]
    ancestor: Rc<RefCell<Haplotype>>,
    #[derivative(Debug = "ignore")]
    wildtype: Rc<RefCell<Haplotype>>,
    descendants: Vec<Rc<RefCell<Haplotype>>>,
    position: usize,
    change: u8,
}

impl Haplotype {
    pub fn get_reference(&self) -> &Rc<RefCell<Haplotype>> {
        let option = match self {
            Haplotype::Wildtype(wt) => &wt.reference,
            Haplotype::Descendant(ht) => &ht.reference,
        };
        match option {
            Some(reference) => &reference,
            None => {
                eprintln!("Haplotype incorrectly initialized.");
                std::process::exit(-1);
            }
        }
    }

    pub fn get_base(&self, position: usize) -> u8 {
        match self {
            Haplotype::Wildtype(wt) => wt.get_base(position),
            Haplotype::Descendant(ht) => ht.get_base(position),
        }
    }

    pub fn get_sequence(&self) -> Vec<u8> {
        match self {
            Haplotype::Wildtype(wt) => wt.get_sequence(),
            Haplotype::Descendant(ht) => ht.get_sequence(),
        }
    }

    pub fn get_length(&self) -> usize {
        match self {
            Haplotype::Wildtype(wt) => wt.get_length(),
            Haplotype::Descendant(ht) => ht.get_length(),
        }
    }
}

impl Wildtype {
    pub fn get_reference(&self) -> &Rc<RefCell<Haplotype>> {
        match &self.reference {
            Some(reference) => &reference,
            None => {
                eprintln!("Haplotype incorrectly initialized.");
                std::process::exit(-1);
            }
        }
    }

    pub fn get_base(&self, position: usize) -> u8 {
        self.sequence[position]
    }

    pub fn get_sequence(&self) -> Vec<u8> {
        self.sequence.to_vec()
    }

    pub fn get_length(&self) -> usize {
        self.sequence.len()
    }
}

impl Descendant {
    pub fn get_reference(&self) -> &Rc<RefCell<Haplotype>> {
        match &self.reference {
            Some(reference) => &reference,
            None => {
                eprintln!("Haplotype incorrectly initialized.");
                std::process::exit(-1);
            }
        }
    }

    pub fn get_base(&self, position: usize) -> u8 {
        if self.position == position {
            return self.change;
        }
        self.ancestor.as_ref().borrow().get_base(position)
    }

    pub fn get_sequence(&self) -> Vec<u8> {
        let mut sequence = vec![0; self.get_length()];
        let mut current = Rc::into_raw(Rc::clone(self.get_reference()));
        unsafe {
            while let Haplotype::Descendant(ht) = &*(*current).borrow() {
                if sequence[ht.position] == 0 {
                    sequence[ht.position] = ht.change
                }
                Rc::from_raw(current);
                current = Rc::into_raw(Rc::clone(&ht.ancestor));
            }
            if let Haplotype::Wildtype(wt) = &*(*current).borrow() {
                for (position, symbol) in wt.sequence.iter().enumerate() {
                    if sequence[position] == 0 {
                        sequence[position] = *symbol;
                    }
                }
            }
            Rc::from_raw(current);
            return sequence;
        }
    }

    pub fn get_length(&self) -> usize {
        self.wildtype.borrow().get_length()
    }
}

Answer 1

您可以重组代码以消除 unsafe:

的需要

pub fn get_sequence(&self) -> Vec<u8> {
    let mut sequence = vec![0; self.get_length()];
    let mut current = Rc::clone(self.get_reference());
    while let Haplotype::Descendant(ht) = &*Rc::clone(&current).borrow() {
        if sequence[ht.position] == 0 {
            sequence[ht.position] = ht.change;
        }
        current = Rc::clone(&ht.ancestor);
    }
    if let Haplotype::Wildtype(wt) = &*(*current).borrow() {
        for (position, symbol) in wt.sequence.iter().enumerate() {
            if sequence[position] == 0 {
                sequence[position] = *symbol;
            }
        }
    }
    return sequence;
}

请注意，我们必须在 while let 循环中从 current 的克隆中借用 ht 以满足借用检查器 .

Playground

具有许多可变引用的 Rust 回溯树结构

Rust backtrace tree structure with many mutable references

tree

unsafe

rust