Rc<T> — умный указатель с подсчётом ссылок

В большинстве случаев владение понятно: вы точно знаете, какая переменная владеет данным значением. Однако бывают случаи, когда одно значение может иметь нескольких владельцев. Например, в структурах данных графа несколько рёбер могут указывать на один и тот же узел, и этот узел концептуально принадлежит всем рёбрам, которые на него указывают. Узел не должен очищаться, пока на него не останется указывающих рёбер и, следовательно, не останется владельцев.

Вам нужно явно включить множественное владение, используя тип Rust Rc<T>, что является сокращением от reference counting (подсчёт ссылок). Тип Rc<T> отслеживает количество ссылок на значение, чтобы определить, используется ли значение ещё. Если ссылок на значение ноль, значение может быть очищено без того, чтобы какие-либо ссылки стали недействительными.

Представьте Rc<T> как телевизор в гостиной. Когда один человек входит, чтобы посмотреть телевизор, он включает его. Другие могут зайти в комнату и смотреть телевизор. Когда последний человек выходит из комнаты, он выключает телевизор, потому что он больше не используется. Если кто-то выключит телевизор, пока другие ещё смотрят его, среди оставшихся зрителей поднимется возмущение!

Мы используем тип Rc<T>, когда хотим разместить некоторые данные в куче для чтения несколькими частями нашей программы и не можем определить во время компиляции, какая часть закончит использование данных последней. Если бы мы знали, какая часть закончит последней, мы могли бы просто сделать эту часть владельцем данных, и обычные правила владения, применяемые во время компиляции, вступили бы в силу.

Обратите внимание, что Rc<T> предназначен только для использования в однопоточных сценариях. Когда мы обсудим конкурентность в Главе 16, мы рассмотрим, как делать подсчёт ссылок в многопоточных программах.

Разделение данных

Давайте вернёмся к нашему примеру с cons list из Листинга 15-5. Напомним, что мы определили его с помощью Box<T>. На этот раз мы создадим два списка, которые оба разделяют владение третьим списком. Концептуально это выглядит подобно Рисунку 15-3.

Связный список с меткой 'a', указывающий на три элемента. Первый элемент содержит целое число 5 и указывает на второй элемент. Второй элемент содержит целое число 10 и указывает на третий элемент. Третий элемент содержит значение 'Nil', которое означает конец списка; он никуда не указывает. Связный список с меткой 'b' указывает на элемент, содержащий целое число 3, который указывает на первый элемент списка 'a'. Связный список с меткой 'c' указывает на элемент, содержащий целое число 4, который также указывает на первый элемент списка 'a', так что хвосты списков 'b' и 'c' оба являются списком 'a'.

Рисунок 15-3: Два списка, b и c, разделяющие владение третьим списком, a

Мы создадим список a, содержащий 5, а затем 10. Затем мы создадим ещё два списка: b, который начинается с 3, и c, который начинается с 4. Затем оба списка b и c продолжат первый список a, содержащий 5 и 10. Другими словами, оба списка будут разделять первый список, содержащий 5 и 10.

Попытка реализовать этот сценарий с использованием нашего определения List с Box<T> не сработает, как показано в Листинге 15-17.

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let a = Cons(5, Box::new(Cons(10, Box::new(Nil))));
    let b = Cons(3, Box::new(a));
    let c = Cons(4, Box::new(a));
}

Когда мы компилируем этот код, мы получаем эту ошибку:

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
error[E0382]: use of moved value: `a`
  --> src/main.rs:11:30
   |
 9 |     let a = Cons(5, Box::new(Cons(10, Box::new(Nil))));
   |         - move occurs because `a` has type `List`, which does not implement the `Copy` trait
10 |     let b = Cons(3, Box::new(a));
   |                              - value moved here
11 |     let c = Cons(4, Box::new(a));
   |                              ^ value used here after move
   |
note: if `List` implemented `Clone`, you could clone the value
  --> src/main.rs:1:1
   |
 1 | enum List {
   | ^^^^^^^^^ consider implementing `Clone` for this type
...
10 |     let b = Cons(3, Box::new(a));
   |                              - you could clone this value

For more information about this error, try `rustc --explain E0382`.
error: could not compile `cons-list` (bin "cons-list") due to 1 previous error

Варианты Cons владеют данными, которые они содержат, поэтому, когда мы создаём список b, a перемещается в b, и b владеет a. Затем, когда мы пытаемся использовать a снова при создании c, это не разрешено, потому что a был перемещён.

Мы могли бы изменить определение Cons, чтобы оно содержало ссылки вместо этого, но тогда нам пришлось бы указывать параметры времени жизни. Указывая параметры времени жизни, мы указывали бы, что каждый элемент в списке будет жить по крайней мере так же долго, как весь список. Это так для элементов и списков в Листинге 15-17, но не в каждом сценарии.

Вместо этого мы изменим наше определение List, чтобы использовать Rc<T> вместо Box<T>, как показано в Листинге 15-18. Каждый вариант Cons теперь будет содержать значение и Rc<T>, указывающий на List. Когда мы создаём b, вместо того чтобы забирать владение a, мы клонируем Rc<List>, который удерживает a, тем самым увеличивая количество ссылок с одного до двух и позволяя a и b разделять владение данными в этом Rc<List>. Мы также клонируем a при создании c, увеличивая количество ссылок с двух до трёх. Каждый раз, когда мы вызываем Rc::clone, счётчик ссылок на данные внутри Rc<List> будет увеличиваться, и данные не будут очищены, пока на них не останется нуль ссылок.

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
    let b = Cons(3, Rc::clone(&a));
    let c = Cons(4, Rc::clone(&a));
}

Нам нужно добавить оператор use, чтобы внести Rc<T> в область видимости, потому что он не в прелюдии. В main мы создаём список, содержащий 5 и 10, и сохраняем его в новом Rc<List> в a. Затем, когда мы создаём b и c, мы вызываем функцию Rc::clone и передаём ссылку на Rc<List> в a в качестве аргумента.

Мы могли бы вызвать a.clone() вместо Rc::clone(&a), но в Rust принято использовать Rc::clone в этом случае. Реализация Rc::clone не делает глубокую копию всех данных, как это делают реализации clone для большинства типов. Вызов Rc::clone только увеличивает счётчик ссылок, что не занимает много времени. Глубокие копии данных могут занимать много времени. Используя Rc::clone для подсчёта ссылок, мы можем визуально отличать глубокие копии клонов от видов клонов, которые увеличивают счётчик ссылок. При поиске проблем с производительностью в коде нам нужно рассматривать только глубокие копии клонов и можем игнорировать вызовы Rc::clone.

Клонирование для увеличения счётчика ссылок

Давайте изменим наш рабочий пример в Листинге 15-18, чтобы мы могли видеть, как меняется счётчик ссылок при создании и удалении ссылок на Rc<List> в a.

В Листинге 15-19 мы изменим main так, чтобы вокруг списка c была внутренняя область видимости; тогда мы сможем увидеть, как меняется счётчик ссылок, когда c выходит из области видимости.

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};
use std::rc::Rc;

// --snip--

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
    println!("count after creating a = {}", Rc::strong_count(&a));
    let b = Cons(3, Rc::clone(&a));
    println!("count after creating b = {}", Rc::strong_count(&a));
    {
        let c = Cons(4, Rc::clone(&a));
        println!("count after creating c = {}", Rc::strong_count(&a));
    }
    println!("count after c goes out of scope = {}", Rc::strong_count(&a));
}

В каждой точке программы, где счётчик ссылок изменяется, мы выводим счётчик ссылок, который мы получаем, вызывая функцию Rc::strong_count. Эта функция названа strong_count, а не count, потому что тип Rc<T> также имеет weak_count; мы увидим, для чего используется weak_count, в разделе «Предотвращение циклов ссылок с помощью Weak<T>».

Этот код выводит следующее:

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.45s
     Running `target/debug/cons-list`
count after creating a = 1
count after creating b = 2
count after creating c = 3
count after c goes out of scope = 2

Мы видим, что Rc<List> в a имеет начальный счётчик ссылок 1; затем каждый раз, когда мы вызываем clone, счётчик увеличивается на 1. Когда c выходит из области видимости, счётчик уменьшается на 1. Нам не нужно вызывать функцию для уменьшения счётчика ссылок, как нам нужно вызывать Rc::clone для увеличения счётчика ссылок: реализация трейта Drop уменьшает счётчик ссылок автоматически, когда значение Rc<T> выходит из области видимости.

Что мы не видим в этом примере, так это то, что когда b, а затем a выходят из области видимости в конце main, счётчик становится 0, и Rc<List> полностью очищается. Использование Rc<T> позволяет одному значению иметь нескольких владельцев, и счётчик гарантирует, что значение остаётся действительным, пока любой из владельцев всё ещё существует.

Через неизменяемые ссылки Rc<T> позволяет вам делиться данными между несколькими частями вашей программы только для чтения. Если бы Rc<T> позволял вам также иметь несколько изменяемых ссылок, вы могли бы нарушить одно из правил заимствования, обсуждавшихся в Главе 4: несколько изменяемых заимствований одного и того же места могут вызывать гонки данных и несогласованность. Но возможность изменять данные очень полезна! В следующем разделе мы обсудим шаблон внутренней изменяемости и тип RefCell<T>, который вы можете использовать вместе с Rc<T>, чтобы работать с этим ограничением неизменяемости.