A circular reference

For front-end students learn JS garbage collection mechanism, must have heard of the concept of circular reference, two data refer to each other, like a ring, because each pointer reference counting in the ring could not be reduced to 0, so the corresponding value will not be released to discard, this creates a memory leak, we learn in front of the Rc < T > type, The same problem exists.

Make circular reference

Here we use the previous example again to try to make two linked lists that reference each other:

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

#[derive(Debug)]
enum List {
  Cons(i32, RefCell<Rc<List>>),
  Nil
}

impl List {
  The tail method is used to conveniently access the second item of a Cons member
  fn tail(&self) - >Option<&RefCell<Rc<List>>> {
    match self {
      List::Cons(_, item) => Some(item),
      List::Nil => None}}}// Create an instance of Rc
      
        in variable A to hold List values with initial values of 5 and Nil
      
let a = Rc::new(List::Cons(5,
  RefCell::new(
    Rc::new(List::Nil)
  )
));

println!("Number of references after initialization of A = {}", Rc::strong_count(&a));
// The number of references after a is initialized = 1

println!("The second term of A is = {:? }", a.tail());
// the second term of a is = Some(RefCell {value: Nil})
Copy the code

Create an instance of Rc<List> in variable b to hold Rc<List> with initial value 10 and pointing to List A:

let b = Rc::new(List::Cons(10,
  RefCell::new(
    Rc::clone(&a)
  )
));

println!("Number of references a creates after B = {}", Rc::strong_count(&a));
// The number of references a makes after B is created = 2

println!("Number of references after b initialization = {}", Rc::strong_count(&b));
// the number of references after b initialization = 1

println!("The second term of b is = {:? }", b.tail());
// the second item of b is = Some(RefCell {value: Cons(5, RefCell {value: Nil)})
Copy the code

Finally, the second term of A points to B, creating a circular reference:

if let Some(second) = a.tail() {
  *second.borrow_mut() = Rc::clone(&b);
}

println!("Number of references to B after changing A = {}", Rc::strong_count(&b));
// After changing a, the number of references to b = 2

println!("The number of references to A after changing a = {}", Rc::strong_count(&a));
// The number of references to a after changing a = 2

println!("a next item = {:? }", a);
// The stack overflows because a and B refer to each other
Copy the code

You can see that after modifying a to point to B, the Rc<List> instances in both a and B have a reference count of 2. At the end of main, Rust tries to discard B first, which reduces the reference count of Rc<List> instances in A and B by one. However, because A still refers to Rc<List> in B, the reference count of Rc<List> is 1 instead of 0, and since its memory reference count is 1, the memory of Rc<List> on the heap is not discarded and will remain there forever.

Avoid reference loops: change Rc<T> to Weak<T>

We can use the Weak reference type Weak<T> to prevent circular references:

/ / into the Weak
use std::rc::{ Rc, Weak };
use std::cell::RefCell;

// Create a tree data structure: nodes with child nodes
#[derive(Debug)]
struct Node {
  value: i32,
  parent: RefCell<Weak<Node>>, // References to the parent node are weak references
  children: RefCell<Vec<Rc<Node>>> // References to child nodes are strong references
}

// Create a leaf node
let leaf = Rc::new(Node {
  value: 3,
  children: RefCell::new(vec![]),
  parent: RefCell::new(Weak::new())
});

// Create a branch node
let branch = Rc::new(Node {
  value: 5.// Use leaf as a child of branch
  children: RefCell::new(vec![Rc::clone(&leaf)]),
  parent: RefCell::new(Weak::new())
});
Copy the code

Connect branches and leaf nodes using weak references:

// Similar to the Rc::clone method,
// Use the Rc::downgrade method to point the parent of a Leaf node to the branch with a weak reference
*(leaf.parent.borrow_mut()) = Rc::downgrade(&branch);

// Use the upgrade method to check whether the parent exists, return the Option type,
// It prints successfully, indicating that the use of weak references does not cause circular references
println!("Parent node of leaf = {:? }", leaf.parent.borrow().upgrade());
// Leaf parent = Some(Node {
// value: 5,
// parent: RefCell { value: (Weak) },
// children: RefCell {
// value: [
// Node {
// value: 3,
// parent: RefCell { val (Weak) },
// children: RefCell { value: [] }
/ /}
/ /]
/ /}
// })
Copy the code

If we use Rc::downgrade, we will get Weak<T>. If we call Rc::downgrade, we will add weak_count () 1 to register how many Weak references it will have. If the instance is changed to 0, strong_count will be changed. Does not care about the number of weak references Weak_count.

Observe the change of strong_count and Weak_count

Strong_count () and Rc:: Weak_count () methods are used to observe the difference between strong and weak references, and note how they behave in scope destruction:

#[derive(Debug)]
struct Node {
  value: i32,
  parent: RefCell<Weak<Node>>,
  children: RefCell<Vec<Rc<Node>>>,
}

let leaf = Rc::new(Node {
  value: 3,
  parent: RefCell::new(Weak::new()),
  children: RefCell::new(vec![])});println!("Child strong reference = {}, weak reference = {}", Rc::strong_count(&leaf), Rc::weak_count(&leaf));
// Strong reference = 1, weak reference = 0

// New scope
{
  let branch = Rc::new(Node {
    value: 5,
    parent: RefCell::new(Weak::new()),
    // leaf goes to the branch child node
    children: RefCell::new(vec![Rc::clone(&leaf)]),
  });

  // the leaf parent weakly references the branch node
  *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

  println!(Branch strong reference = {}, weak reference = {}, Rc::strong_count(&branch), Rc::weak_count(&branch));
  // branch strong reference = 1, weak reference = 1

  println!(Leaf strong reference = {}, weak reference = {}", Rc::strong_count(&leaf), Rc::weak_count(&leaf));
  // leaf strong reference = 2, weak reference = 0
}

println!("Parent of leaf = {:? }", leaf.parent.borrow().upgrade());
// The parent node of leaf = None, and branch is strongly referenced from 1 when the above scope is destroyed
// Becomes 0, notice that weak references are not concerned, even if weak references are 1, branch will still be destroyed

println!(Leaf strong reference = {}, weak reference = {}", Rc::strong_count(&leaf), Rc::weak_count(&leaf));
// Leaf strong reference = 1, weak reference = 0, branch is no longer strong reference to leaf due to the destruction of the scope above.
Copy the code

The Weak<T> type can be used when the data types have cyclic references to each other, so that the referenced data points to each other without cyclic references and memory leaks.