Rc<T>: contagem de referências

Esta aula aborda o tipo Rc<T> (Reference Counted) do Rust, que permite o compartilhamento de ownership de um valor imutável através de contagem de referências. Veremos como criar, clonar e usar Rc<T>, suas limitações (apenas acesso imutável, sem garantia de ausência de ciclos) e casos de uso típicos, como em grafos ou árvores.

Em Rust, o sistema de ownership garante segurança de memória em tempo de compilação, mas em algumas situações precisamos que um valor tenha múltiplos donos. Por exemplo, em uma estrutura de grafo onde um nó pode ser referenciado por vários outros, ou em uma árvore onde um nó filho pode ter múltiplos pais. O tipo Rc<T> (Reference Counted) fornece uma solução: ele permite que um valor tenha vários donos, mantendo uma contagem de referências. Quando a contagem chega a zero, o valor é liberado.

Rc<T> só funciona em programas single-threaded. Para concorrência, usamos Arc<T> (Atomic Reference Counted). O Rc<T> é uma forma de compartilhar ownership de forma imutável: você só pode obter referências imutáveis ao valor interno (a menos que combine com RefCell<T> para mutabilidade interior).

Compartilhamento de ownership

Normalmente, cada valor em Rust tem exatamente um dono. Mas com Rc<T>, podemos criar múltiplos ponteiros para o mesmo valor, todos considerados donos. O Rc usa uma contagem de referências para rastrear quantos ponteiros existem. Quando um Rc é clonado, a contagem aumenta; quando um Rc sai de escopo, a contagem diminui. Quando a contagem chega a zero, o valor é dropado.

Exemplo básico:

use std::rc::Rc;

let a = Rc::new(42);
let b = Rc::clone(&a); // b também aponta para o mesmo valor
println!("{}", a); // 42
println!("{}", b); // 42
// Ambos são donos do valor 42

Internamente, Rc armazena o valor em uma alocação no heap, junto com dois contadores: um para referências fortes (que mantêm o valor vivo) e outro para referências fracas (que não impedem a liberação). A contagem de referências fortes é acessível via Rc::strong_count(&rc).

`Rc::clone`

A principal maneira de aumentar a contagem de referências é chamando Rc::clone. Diferente de uma clonagem profunda (clone de um String, por exemplo), Rc::clone apenas incrementa o contador e copia o ponteiro. É uma operação barata.

Exemplo com contagem:

use std::rc::Rc;

let a = Rc::new(10);
println!("Contagem inicial: {}", Rc::strong_count(&a)); // 1

let b = Rc::clone(&a);
println!("Contagem após clone: {}", Rc::strong_count(&a)); // 2

{
    let c = Rc::clone(&a);
    println!("Contagem dentro do escopo: {}", Rc::strong_count(&a)); // 3
}

println!("Contagem após drop de c: {}", Rc::strong_count(&a)); // 2

drop(b);
println!("Contagem após drop de b: {}", Rc::strong_count(&a)); // 1

Note que Rc::clone pode ser chamado tanto como método quanto como função associada. A implementação do trait Clone para Rc chama Rc::clone internamente.

`Limitações`

Apesar de útil, Rc<T> tem limitações importantes:

Apenas acesso imutável: O valor dentro de Rc é imutável. Para mutabilidade, é necessário combiná-lo com RefCell<T> (mutabilidade interior) ou usar Cell<T> para tipos que implementam Copy.
Não é thread-safe: Rc não implementa Send nem Sync, portanto não pode ser usado em múltiplas threads. Para isso, use Arc<T>.
Possibilidade de ciclos: Se dois Rcs apontam um para o outro, a contagem de referências nunca chegará a zero, causando vazamento de memória. Para evitar isso, use Weak<T> (referências fracas) para quebrar ciclos.
Overhead de performance: A contagem de referências é feita em tempo de execução, com custo de incremento/decremento a cada clone/drop. Além disso, Rc usa alocação dinâmica.

Exemplo de ciclo:

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

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

let leaf = Rc::new(Node { value: 3, children: RefCell::new(vec![]) });
let branch = Rc::new(Node { value: 5, children: RefCell::new(vec![Rc::clone(&leaf)]) });
// Agora leaf.children pode conter branch, criando um ciclo
// leaf.children.borrow_mut().push(Rc::clone(&branch)); // Isso causaria vazamento se não usarmos Weak

`Casos de uso`

Rc é amplamente utilizado em estruturas de dados onde um nó pode ser referenciado por múltiplos pais ou por vários lugares, como:

Grafos: Representação de grafos direcionados ou não, onde cada nó pode ter múltiplos vizinhos.
Árvores com referências compartilhadas: Por exemplo, uma árvore de sintaxe abstrata (AST) onde subárvores podem ser compartilhadas.
Padrão Flyweight: Compartilhar objetos imutáveis para economizar memória.
Cache: Manter referências a valores calculados que podem ser reutilizados.
Implementação de estruturas de dados persistentes: Onde versões antigas e novas compartilham partes imutáveis.

Exemplo de uso em um grafo simples:

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

#[derive(Debug)]
struct Grafo {
    nos: Vec<Rc<No>>,
}

#[derive(Debug)]
struct No {
    valor: i32,
    vizinhos: RefCell<Vec<Rc<No>>>,
}

impl No {
    fn new(valor: i32) -> Rc<Self> {
        Rc::new(No { valor, vizinhos: RefCell::new(vec![]) })
    }

    fn adicionar_vizinho(&self, vizinho: &Rc<No>) {
        self.vizinhos.borrow_mut().push(Rc::clone(vizinho));
    }
}

fn main() {
    let no1 = No::new(1);
    let no2 = No::new(2);
    let no3 = No::new(3);

    no1.adicionar_vizinho(&no2);
    no1.adicionar_vizinho(&no3);
    no2.adicionar_vizinho(&no3);

    println!("{:?}", no1);
}

`Referências`

`Exercícios`

Crie um programa que demonstre o uso de Rc para compartilhar um valor inteiro entre duas variáveis. Imprima a contagem de referências antes e depois de clonar.

✓ Resposta:use std::rc::Rc;

fn main() {
    let a = Rc::new(100);
    println!("Contagem inicial: {}", Rc::strong_count(&a));
    let b = Rc::clone(&a);
    println!("Contagem após clone: {}", Rc::strong_count(&a));
    println!("a = {}, b = {}", a, b);
}

Escreva uma função que receba um Rc<String> e retorne o comprimento da string. Chame a função duas vezes com o mesmo Rc e verifique a contagem de referências.

✓ Resposta:use std::rc::Rc;

fn comprimento(s: &Rc<String>) -> usize {
    s.len()
}

fn main() {
    let s = Rc::new(String::from("Hello"));
    println!("Contagem: {}", Rc::strong_count(&s));
    let len1 = comprimento(&s);
    println!("Contagem após primeira chamada: {}", Rc::strong_count(&s));
    let len2 = comprimento(&s);
    println!("Contagem após segunda chamada: {}", Rc::strong_count(&s));
    println!("Comprimentos: {} e {}", len1, len2);
}

Implemente uma estrutura de lista encadeada simples usando Rc e RefCell para permitir que um nó seja compartilhado entre múltiplas listas (por exemplo, uma lista que termina em um nó comum).

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

#[derive(Debug)]
struct No {
    valor: i32,
    proximo: Option<Rc<RefCell<No>>>,
}

fn main() {
    let no_comum = Rc::new(RefCell::new(No { valor: 42, proximo: None }));
    
    let lista1 = Rc::new(RefCell::new(No { valor: 1, proximo: Some(Rc::clone(&no_comum)) }));
    let lista2 = Rc::new(RefCell::new(No { valor: 2, proximo: Some(Rc::clone(&no_comum)) }));
    
    println!("lista1: {:?}", lista1);
    println!("lista2: {:?}", lista2);
}

Explique por que o código abaixo causaria um vazamento de memória e como corrigi-lo usando Weak.

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

struct No {
    valor: i32,
    proximo: Option<Rc<RefCell<No>>>,
}

fn main() {
    let a = Rc::new(RefCell::new(No { valor: 1, proximo: None }));
    let b = Rc::new(RefCell::new(No { valor: 2, proximo: Some(Rc::clone(&a)) }));
    // Ciclo: a aponta para b?
    a.borrow_mut().proximo = Some(Rc::clone(&b));
}

✓ Resposta:O código cria um ciclo: a aponta para b e b aponta para a. Ambos têm contagem de referências 1, mas como se referenciam mutuamente, a contagem nunca chega a zero. Para corrigir, um dos ponteiros deve ser Weak, que não incrementa a contagem forte. Exemplo:
use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct No {
    valor: i32,
    proximo: Option<Rc<RefCell<No>>>,
    // Em vez de Rc, use Weak para o pai
    pai: RefCell<Weak<RefCell<No>>>,
}

fn main() {
    let a = Rc::new(RefCell::new(No { valor: 1, proximo: None, pai: RefCell::new(Weak::new()) }));
    let b = Rc::new(RefCell::new(No { valor: 2, proximo: Some(Rc::clone(&a)), pai: RefCell::new(Rc::downgrade(&a)) }));
    // a.pai pode ser configurado como Weak para b
    a.borrow_mut().pai = RefCell::new(Rc::downgrade(&b));
}

Usando Rc e RefCell, implemente um contador de referências manual que imprime uma mensagem quando um Rc é clonado ou dropado. Dica: crie um wrapper sobre Rc.

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

struct RcLog {
    inner: Rc<RefCell<T>>,
}

impl<T> RcLog<T> {
    fn new(value: T) -> Self {
        println!("Criando RcLog");
        RcLog { inner: Rc::new(RefCell::new(value)) }
    }

    fn clone(&self) -> Self {
        println!("Clonando RcLog");
        RcLog { inner: Rc::clone(&self.inner) }
    }
}

impl<T> Drop for RcLog<T> {
    fn drop(&mut self) {
        println!("Dropando RcLog, contagem forte: {}", Rc::strong_count(&self.inner));
    }
}

fn main() {
    let a = RcLog::new(42);
    let b = a.clone();
    drop(a);
    println!("b ainda vivo");
}

Rc<T>: contagem de referências

Compartilhamento de ownership

Rc::clone

Limitações

Casos de uso

Referências

Exercícios

Mais desta categoria

Deref e Drop

Canais (channels)

RefCell e mutabilidade interior

`Rc::clone`

`Limitações`

`Casos de uso`

`Referências`

`Exercícios`