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

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

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

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

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

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

Использование Rc<T> для совместного использования данных

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

Two lists that share ownership of a third list

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

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

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

Файл: src/main.rs

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));
}

Листинг 15-17: Демонстрация того, что нам не разрешено иметь два списка, использующих тип Box, которые пытаются разделить владение третьим списком

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

$ 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

error: aborting due to previous error

For more information about this error, try `rustc --explain E0382`.
error: could not compile `cons-list`

To learn more, run the command again with --verbose.

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

Мы могли бы изменить определение типа Cons так, чтобы хранить ссылки, но тогда мы должны были бы указать параметры времени жизни. Указывая параметры времени жизни, пришлось бы указывать, что каждый элемент в списке будет жить как минимум столько же, сколько весь список. Анализатор заимствования, например, не позволил бы нам скомпилировать код let a = Cons(10, &Nil);, потому что временное значение Nil было бы удалено, прежде чем a сможет получить ссылку на него.

Вместо этого мы изменим наше определение типа 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> будет увеличиваться и данные не будут очищены, если на них нет нулевых ссылок.

Файл: src/main.rs

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));
}

Листинг 15-18: Определение List, который использует тип Rc

Нам нужно добавить оператор 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 .

Клонирование Rc<T> увеличивает количество ссылок

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

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

Файл: src/main.rs

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)))));
    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));
}

Листинг 15-19: Печать количества ссылок

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

Код выводит в консоль:

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
    Finished dev [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: множественные изменяемые заимствования в одном и том же месте могут вызвать гонки данных (data races) и несогласованность данных. Но возможность изменять данные очень полезна! В следующем разделе мы обсудим шаблон внутренней изменчивости и тип RefCell<T>, который можно использовать вместе с Rc<T> для работы с этим ограничением.