Reference Cycles and Memory Leaks

Oxide's ownership system prevents most memory leaks, but it's still possible to create memory leaks by creating reference cycles—when values refer to each other in a circle, preventing the reference counts from ever reaching zero.

Creating a Reference Cycle

Let's see how a reference cycle can occur with Rc<T> and RefCell<T>:

import std.rc.Rc
import std.cell.RefCell

public struct Node {
    public value: Int,
    public next: RefCell<Rc<Node>?>,
}

fn main() {
    // Create a node
    let a = Rc { Node {
        value: 5,
        next: RefCell { null }
    } }

    // Create another node
    let b = Rc { Node {
        value: 10,
        next: RefCell { null }
    } }

    // This creates a cycle: a -> b -> a
    a.next.borrowMut() = Rc.clone(&b)
    b.next.borrowMut() = Rc.clone(&a)

    // When a and b go out of scope, the memory is NOT freed
    // because each holds a reference to the other
}

Why Reference Cycles Cause Memory Leaks

Let's trace the reference counts:

After creating a: a ref count = 1
After creating b: b ref count = 1
After a.next = b: b ref count = 2
After b.next = a: a ref count = 2
a goes out of scope: a ref count = 1 (not zero!)
b goes out of scope: b ref count = 1 (not zero!)

Because the reference counts never reach zero, the memory is never freed—even though both a and b are unreachable from the rest of the program. This is a memory leak.

The Solution: Weak References

The solution is to use weak references instead of strong references. Weak<T> is like Rc<T>, but it doesn't prevent the value from being dropped:

Strong reference (Rc<T>): Keeps a value alive; prevents it from being dropped
Weak reference (Weak<T>): Does not keep a value alive; allows it to be dropped

When all strong references are gone, the value is dropped, even if there are weak references remaining. Weak references that point to dropped values become null.

import std.rc.Rc
import std.rc.Weak
import std.cell.RefCell

public struct Node {
    public value: Int,
    public next: RefCell<Rc<Node>?>,
    public previous: RefCell<Weak<Node>?>,  // Use Weak for back-references
}

fn main() {
    let a = Rc { Node {
        value: 5,
        next: RefCell { null },
        previous: RefCell { null },
    } }

    let b = Rc { Node {
        value: 10,
        next: RefCell { null },
        previous: RefCell { null },
    } }

    // a -> b (strong reference)
    a.next.borrowMut() = Rc.clone(&b)

    // b -> a (weak reference - doesn't create a cycle!)
    b.previous.borrowMut() = Weak.clone(&a)

    // Now when we drop a and b, the memory is properly freed
}

When to Use Weak References

Use weak references when you have a hierarchical relationship where:

A parent owns its children (strong references)
Children reference their parent (weak references)

Common examples:

1. Tree Structure

public struct TreeNode<T> {
    public value: T,
    public children: RefCell<Vec<Rc<TreeNode<T>>>>,  // Strong: owns children
    public parent: RefCell<Weak<TreeNode<T>>?>,      // Weak: doesn't own parent
}

extension TreeNode {
    public fn newRoot(value: T): Rc<TreeNode<T>> {
        Rc { TreeNode {
            value: value,
            children: RefCell { vec![] },
            parent: RefCell { null },
        } }
    }

    public fn addChild(parent: Rc<TreeNode<T>>, child: T) {
        let newChild = Rc { TreeNode {
            value: child,
            children: RefCell { vec![] },
            parent: RefCell { Weak.clone(&parent) },
        } }

        parent.children.borrowMut().push(newChild)
    }
}

2. Graph with Shared Edges

public struct Person {
    public name: String,
    public friends: RefCell<Vec<Weak<Person>>>,  // Weak references to prevent cycles
}

fn main() {
    let alice = Rc { Person {
        name: "Alice",
        friends: RefCell { vec![] },
    } }

    let bob = Rc { Person {
        name: "Bob",
        friends: RefCell { vec![] },
    } }

    // Both can have weak references to each other
    alice.friends.borrowMut().push(Weak.clone(&bob))
    bob.friends.borrowMut().push(Weak.clone(&alice))

    // Memory is properly freed when alice and bob go out of scope
}

Using Weak References

To use a weak reference, you must upgrade it to a strong reference first:

let weakRef: Weak<MyType> = ...

// Upgrade to a strong reference
if let Some(strongRef) = weakRef.upgrade() {
    // Use strongRef
    println!("Value: \(strongRef.value)")
}

The upgrade() method returns Rc<T>? because the value might have been dropped.

Complete Example: Doubly-Linked List

Here's a complete example of a doubly-linked list that uses weak references to prevent memory leaks:

import std.rc.Rc
import std.rc.Weak
import std.cell.RefCell

public struct ListNode<T> {
    public data: T,
    public next: RefCell<Rc<ListNode<T>>?>,
    public previous: RefCell<Weak<ListNode<T>>?>,
}

public struct DoublyLinkedList<T> {
    public head: RefCell<Rc<ListNode<T>>?>,
    public tail: RefCell<Weak<ListNode<T>>?>,
}

extension DoublyLinkedList {
    public static fn new(): DoublyLinkedList<T> {
        DoublyLinkedList {
            head: RefCell { null },
            tail: RefCell { null },
        }
    }

    public mutating fn push(value: T) {
        let newNode = Rc { ListNode {
            data: value,
            next: RefCell { null },
            previous: RefCell { null },
        } }

        if let Some(tailNode) = self.tail.borrow().upgrade() {
            tailNode.next.borrowMut() = Rc { newNode }
            newNode.previous.borrowMut() = Weak.clone(&self.tail.borrow())
        } else {
            self.head.borrowMut() = Rc { newNode }
        }

        self.tail.borrowMut() = Weak.clone(&newNode)
    }
}

fn main() {
    var list: DoublyLinkedList<Int> = DoublyLinkedList.new()
    list.push(1)
    list.push(2)
    list.push(3)

    // List is properly cleaned up when it goes out of scope
}

Detecting Reference Cycles in Your Code

Ask yourself these questions:

Do I have circular references? If A points to B and B points to A, you have a potential cycle
Are they all strong references? If yes, you have a memory leak
Is there an owner relationship? Parent owns children → parent uses Rc<T>, children use Weak<T>

If you answer "yes" to questions 1 and 2, you probably need weak references.

Reference Cycles and Rc.strongCount()

You can use Rc.strongCount() to check the reference count and detect cycles:

let a = Rc { Node { value: 5 } }
println!("Count: \(Rc.strongCount(&a))")  // 1

let b = Rc.clone(&a)
println!("Count: \(Rc.strongCount(&a))")  // 2

// If the count doesn't decrease when a value goes out of scope,
// it might be part of a reference cycle

Performance Impact of Weak References

Weak references have minimal overhead:

Slightly larger struct (stores both strong and weak counts)
Slight cost to upgrade() operation
Minimal cost compared to fixing a memory leak

Summary

Reference cycles can prevent values from being dropped, causing memory leaks even in Oxide:

A reference cycle occurs when values refer to each other circularly
Both strong references in Rc<T> prevent dropping
Use Weak<T> for back-references in hierarchical structures
Parent owns children (strong Rc<T>); children reference parent (weak Rc<T>)
Always upgrade() a weak reference before using it
Detecting cycles: ask if there's an ownership hierarchy; if so, use weak references for back-references

This completes our exploration of smart pointers! You now understand:

Box<T> for single ownership on the heap
Rc<T> for multiple ownership
RefCell<T> for interior mutability
How to prevent memory leaks with weak references

These tools give you the flexibility to write complex data structures while maintaining Oxide's memory safety guarantees.

The Oxide Programming Language