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

Box<T>: данные в куче

Самый простой умный указатель — «коробка» (box), её тип записывается как Box<T>. Коробки позволяют хранить данные не на стеке, а в куче. На стеке остаётся лишь указатель на данные в куче. Чем стек отличается от кучи, можно освежить в памяти по главе 4.

Накладных расходов на производительность у коробок нет, если не считать того, что данные хранятся в куче, а не на стеке. Но и особых дополнительных возможностей у них тоже нет. Чаще всего коробки нужны в таких ситуациях:

• когда размер типа неизвестен при компиляции, а значение этого типа нужно использовать там, где требуется точный размер;
• когда данных много и нужно передать владение ими, гарантировав, что при этом данные не будут копироваться;
• когда нужно владеть значением и важно лишь то, что его тип реализует определённый трейт, а не то, какой это конкретно тип.

Первую ситуацию мы разберём в разделе «Рекурсивные типы с помощью коробок». Во втором случае передача владения большим объёмом данных может занимать много времени, ведь данные копируются по стеку. Чтобы ускорить это, большой объём данных можно положить в коробку в куче. Тогда по стеку копируется лишь маленький указатель, а данные, на которые он указывает, остаются на одном месте в куче. Третий случай называется трейт-объектом (trait object); ему посвящён раздел «Трейт-объекты: абстракция над общим поведением» главы 18. Так что то, что вы узнаете здесь, пригодится вам снова и там!

Хранение данных в куче

Прежде чем обсуждать, когда Box<T> нужна для хранения данных в куче, разберём синтаксис и то, как работать со значениями внутри Box<T>.

В листинге 15-1 показано, как с помощью коробки хранить значение i32 в куче.

fn main() {
    let b = Box::new(5);
    println!("b = {b}");
}

Мы определяем переменную b со значением Box, которая указывает на значение 5, размещённое в куче. Программа выведет b = 5: к данным в коробке здесь можно обращаться почти так же, как если бы они лежали на стеке. Как и любое значение-владелец, коробка освобождается, когда выходит из области видимости (как b в конце main). Освобождается и сама коробка (она на стеке), и данные, на которые она указывает (они в куче).

Класть в кучу одно-единственное значение не очень полезно, так что сами по себе коробки в таком виде вы будете использовать редко. В большинстве случаев значения вроде одного i32 уместнее хранить на стеке, где они и хранятся по умолчанию. Давайте посмотрим на случай, когда коробки позволяют определить типы, которые без них определить было бы нельзя.

Рекурсивные типы с помощью коробок

Значение рекурсивного типа может содержать внутри себя другое значение того же типа. С рекурсивными типами есть проблема: Rust должен знать при компиляции, сколько места занимает тип. А вложенность значений рекурсивного типа теоретически может продолжаться бесконечно, так что Rust не может знать, сколько места нужно значению. А размер коробки известен, поэтому если вставить коробку в определение рекурсивного типа, такой тип становится возможным.

В качестве примера рекурсивного типа рассмотрим cons-список. Это тип данных, часто встречающийся в функциональных языках программирования. Тип cons-списка, который мы определим, простой, если не считать рекурсии, так что понятия из этого примера пригодятся вам всякий раз, когда вы столкнётесь с более сложными ситуациями с рекурсивными типами.

Что такое cons-список

Cons-список (cons list) — структура данных, пришедшая из языка программирования Lisp и его диалектов. Он состоит из вложенных пар и представляет собой лисповскую версию связного списка. Название идёт от функции cons в Lisp (сокращение от construct function — «функция-конструктор»), которая создаёт новую пару из двух своих аргументов. Вызывая cons для пары из значения и другой пары, можно строить cons-списки из рекурсивно вложенных пар.

Вот, например, cons-список со списком 1, 2, 3 в псевдокоде — каждая пара в скобках:

(1, (2, (3, Nil)))

Каждый элемент cons-списка содержит две части: значение текущего элемента и следующий элемент. Последний элемент списка содержит только значение Nil и не имеет следующего. Cons-список получается рекурсивными вызовами функции cons. Каноническое название базового случая рекурсии — Nil. Учтите, что это не то же самое, что «null» или «nil» из главы 6, то есть недопустимое или отсутствующее значение.

В Rust cons-список используется нечасто. Когда в Rust нужен список элементов, обычно лучше подходит Vec<T>. Другие, более сложные рекурсивные типы данных действительно бывают полезны в разных ситуациях, но, начав в этой главе с cons-списка, мы сможем разобраться, как коробки позволяют определить рекурсивный тип данных, не отвлекаясь на лишнее.

В листинге 15-2 — определение перечисления для cons-списка. Учтите, что этот код пока не скомпилируется: размер типа List неизвестен, и сейчас мы это покажем.

enum List {
    Cons(i32, List),
    Nil,
}

fn main() {}

Список 1, 2, 3 в типе List выглядел бы как в листинге 15-3.

enum List {
    Cons(i32, List),
    Nil,
}

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

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

fn main() {
    let list = Cons(1, Cons(2, Cons(3, Nil)));
}

Первое значение Cons хранит 1 и ещё одно значение List. Это значение List — ещё один Cons, который хранит 2 и ещё один List. А тот — ещё один Cons с 3 и значением List, которое наконец-то равно Nil — нерекурсивному варианту, обозначающему конец списка.

Если попытаться скомпилировать код из листинга 15-3, получим ошибку из листинга 15-4.

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
2 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

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

Ошибка говорит, что у этого типа «бесконечный размер» (has infinite size). Причина в том, что мы определили List с рекурсивным вариантом: он напрямую содержит ещё одно значение того же типа. Из-за этого Rust не может понять, сколько места нужно для хранения значения List. Разберёмся, почему так. Сначала посмотрим, как Rust определяет, сколько места нужно для значения нерекурсивного типа.

Размер нерекурсивного типа

Вспомните перечисление Message, которое мы определили в листинге 6-2, когда обсуждали перечисления в главе 6:

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

fn main() {}

Чтобы определить, сколько места выделить под значение Message, Rust перебирает все варианты и смотрит, какому нужно больше всего места. Rust видит, что Message::Quit места не нужно вовсе, Message::Move — столько, чтобы поместились два значения i32, и так далее. Использоваться будет только один вариант, так что значению Message нужно не больше места, чем занимает самый большой из его вариантов.

А теперь посмотрим, что происходит, когда Rust пытается определить, сколько места нужно рекурсивному типу вроде перечисления List из листинга 15-2. Компилятор начинает с варианта Cons, который хранит значение типа i32 и значение типа List. Значит, Cons нужно столько места, сколько занимает i32 плюс сколько занимает List. Чтобы узнать, сколько памяти нужно типу List, компилятор смотрит на варианты, начиная с Cons. Вариант Cons хранит значение типа i32 и значение типа List — и так до бесконечности, как показано на рисунке 15-1.

Рисунок 15-1: Бесконечный List из бесконечного числа вариантов Cons

Рекурсивный тип известного размера

Раз Rust не может понять, сколько места выделить под рекурсивно определённый тип, компилятор выдаёт ошибку с полезной подсказкой:

help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

Косвенность (indirection) в этой подсказке означает, что значение нужно хранить не напрямую, а косвенно — изменить структуру данных так, чтобы она хранила указатель на значение.

Box<T> — указатель, поэтому Rust всегда знает, сколько места нужно Box<T>: размер указателя не зависит от объёма данных, на которые он указывает. Значит, в вариант Cons можно положить не само значение List, а Box<T>. Box<T> будет указывать на следующее значение List, которое будет лежать в куче, а не внутри варианта Cons. По сути, у нас по-прежнему список, составленный из списков, содержащих другие списки, но теперь элементы лежат не друг внутри друга, а скорее друг за другом.

Изменим определение перечисления List из листинга 15-2 и его использование из листинга 15-3 на код из листинга 15-5 — и он скомпилируется.

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

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

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
}

Варианту Cons нужно столько места, сколько занимает i32, плюс место под указатель коробки. Вариант Nil не хранит значений, поэтому на стеке ему нужно меньше места, чем Cons. Теперь мы знаем, что любое значение List займёт размер i32 плюс размер указателя коробки. С помощью коробки мы разорвали бесконечную рекурсивную цепочку, и компилятор может определить, сколько места нужно для хранения значения List. Как теперь выглядит вариант Cons, показано на рисунке 15-2.

Рисунок 15-2: List конечного размера — потому что Cons хранит Box

Коробки дают только косвенность и размещение в куче; других особых возможностей, вроде тех, что мы увидим у других умных указателей, у них нет. Зато нет и накладных расходов, которые эти возможности влекут, поэтому коробки полезны в случаях вроде cons-списка, где косвенность — единственное, что нам нужно. Другие применения коробок мы рассмотрим в главе 18.

Тип Box<T> — умный указатель, потому что реализует трейт Deref, благодаря которому со значениями Box<T> можно обращаться как со ссылками. А когда значение Box<T> выходит из области видимости, данные в куче, на которые указывает коробка, тоже освобождаются — благодаря реализации трейта Drop. Эти два трейта ещё важнее для функциональности других умных указателей, о которых пойдёт речь в остальной части главы. Разберём их подробнее.