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