Язык программирования Rust

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

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

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

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

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

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

Совместное использование данных

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

Рисунок 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. А когда при создании c мы снова пытаемся использовать a, это запрещено: a уже перемещён.

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

Вместо этого изменим определение List, заменив Box<T> на Rc<T>, как в листинге 15-18. Теперь каждый вариант Cons хранит значение и Rc<T>, указывающий на List. При создании b мы не забираем владение a, а клонируем Rc<List>, который хранит a. Так число ссылок увеличивается с одной до двух, и a и b совместно владеют данными в этом Rc<List>. При создании c мы тоже клонируем a, и число ссылок увеличивается с двух до трёх. Каждый вызов 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));
}

Rc<T> нет в прелюдии, поэтому его нужно подключить инструкцией use. В 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;

// --пропуск--

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<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> выходит из области видимости.

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

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