Cyclic references (again)

code review
1

Disclaimer: I know, cyclic references should be (and usually can be) avoided, and there a better data structures to represent graphs than linking nodes by references.

However, for educational purposes I want to model (cyclic) graphs in a way that is as close as possible to approaches in other language without memory safety checks, such a C (but without unsafe).

The usual approaches I'm aware use Rc and Weak and shift memory safety into runtime.
However, I find it more appealing to use direct references behind OnceCell, especially since "my" graphs a quite static (in sense of not dynamic, not in the Rust sense):

use std::cell::OnceCell;
use std::fmt;

struct Node<'a> {
   id:    String,
   edges: Vec<OnceCell<&'a Node<'a>>>,
}

impl<'a> Node<'a>{
   fn new(id: &str, degree: usize) -> Node<'a> {
      Node{
         id: id.to_owned(), 
         edges: vec![OnceCell::new();degree]
      }
    }

   fn add_edge(&'a self, ndx: usize, to: &'a Node<'a>) -> Result<(),&'a Node>{
      if ndx < self.edges.len() {
         self.edges[ndx].set(to)?;
         Ok(())
      } else {
         Err(to)
      }
   }

   #[allow(dead_code)] // Use for futher graph analysis
   fn get_edge(&'a self,ndx: usize) -> Option<&'a Node> {
     self.edges[ndx].get().copied()
   }
}

impl<'a> fmt::Display for Node<'a> {
   fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
      let mut sep = "(";
      write!(f,"{} -> ", self.id)?;
      for onode in &self.edges {
         if let Some(node) = onode.get().copied() {
            write!(f,"{}{}", sep, node.id)?;
            sep = ", ";
         }
      }
      write!(f,")")
   }
}

fn main() {
   let n1 = Node::new("A",1);
   let n2 = Node::new("B",2);
   let n3 = Node::new("C",2);
   n1.add_edge(0, &n3).expect("Can't add edge.");
   n1.add_edge(0, &n3).expect("Can't add edge.");
   n2.add_edge(0, &n1).expect("Can't add edge.");
   n2.add_edge(1, &n3).expect("Can't add edge.");
   n3.add_edge(0, &n1).expect("Can't add edge.");
   n3.add_edge(1, &n3).expect("Can't add edge.");
   println!("{n1}, {n2}, {n3}");
}

Is there something wrong with that approach?
Especially: Does it introduce a memory leak or UB (both IMHO: no), or is it unrusty for some reason?
(I'm aware that trying to add an invalid self-loop leads to stack overflow in expect(), but I've removed the check for the moment to keep the code cleaner.)

2

The main problem with it is that the whole graph is essentially stack-pinned, and therefore can't be moved (in particular, can't be returned to the caller).

Nope - you can't leak memory if you don't allocate memory, and the only structural allocation here is Vec, which is deallocated once Nodes are dropped.

You have no unsafe in your code, so any UB caused by it would be a bug somewhere else.

6 Likes
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.