Rust. Borrow checker через итераторы28.04.2020 03:33

Привет, Хабр!

Я уже около года изучаю и, в свободное время, пишу на расте. Мне нравится как его авторы решили проблему управления памятью и обошлись без сборщика мусора — через концепцию заимствования. В этой статье подойду к этой идее через итераторы.

Последнее время scala является моим основным языком, так что сравнения будут с ней, но их не много и все интуитивно понятные, без магии :).
Статья рассчитана на тех кто что-то слышал о rust’e, но в детали не вдавался.

фотографии взяты отсюда и отсюда

Предисловие

В jvm языках принято прятать работу со ссылками, то есть там мы почти всегда работаем со ссылочными типами данных, поэтому решили спрятать амперсанд (&).
В расте же есть явные ссылки, например на integer — `&i32`, ссылку можно разыменовать через `*`, так же может быть ссылка на ссылку и тогда её надо будет дважды разыменовывать `**`.

Iterator

При написании кода очень часто нужно отфильтровать коллекцию условием (предикатом). В скале взять чётные элементы выглядело бы как-то так:

    val vec = Vector(1,2,3,4)
    val result = vec.filter(e => e % 2 == 0)

Заглянем в сорцы:

  private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Repr = {
    val b = newBuilder
    for (x <- this)
      if (p(x) != isFlipped) b += x

    b.result
  }

Не вдаваясь в детали `newBuilder’a`, видно что создаётся новая коллекция, итератором пробегаемся по старой и если предикат вернул true, то добавляем элемент. Несмотря на то что коллекция новая, её элементы на самом деле это ссылки на элементы из первой коллекции, и если, вдруг, эти элементы будут мутабельны, то их изменение будет общим для обоих коллекций.

Теперь попробуем сделать аналогичное в расте. Я сразу дам рабочий пример, а потом буду рассматривать различия.

    let v: Vec = vec![1, 2, 3, 4];
    let result: Vec<&i32> = v.iter().filter(|e| **e % 2 == 0).collect();

Воооу, воу, что? Двойное разыменование указателя? Просто чтобы отфильтровать вектор? Жёстко :(Но на это есть свои причины.

Выделим чем этот код отличается от скалы:

1. явно получаем итератор на вектор (`iter ()`)
2. в функции предикате зачем-то дважды разыменовываем указатель
3. вызываем `collect ()`
4. ещё и в итоге получился вектор ссылочных типов Vec<&i32>, а не обычных интов

Borrow checker

Зачем же явно вызывать `iter ()` на коллекции? Любому скалисту понятно, что если вызываешь `.filter (…)` то нужно проитерироваться по коллекции. Зачем же в расте явно писать то, что можно сделать неявно? Потому что там есть три разных итератора!

Чтобы разобраться «почему три?» нужно затронуть тему Borrow(заимствовать, брать) checker'a. Той самой штуки за счёт которой раст работает без GC и без явного выделения/освобождения памяти.

Зачем он нужен?
1. Чтобы избежать ситуаций когда несколько указателей указывают в одну и туже область памяти, позволяя её менять. То есть race condition.
2. Чтобы не деаллоцировать одну и туже память несколько раз.

За счёт чего это достигается?
За счёт концепции владения.
В целом концепция владения проста — владеть чем-либо (даже интом) может только один. Владелец может меняться, но он всегда один. Когда мы пишем `let x: i32 = 25` это означает, что произошло выделение памяти под 32 битный int и им владеет некий `x`. Идея владения существует только в уме компилятора, в borrow checker’e. Когда владелец, в данном случае `x` выйдет из области видимости (goes out of scope), то память которой он владеет будет очищена.

Приведу код который не пропустит borrow checker:

struct X; //объявляем структуру

fn test_borrow_checker () -> X {
    let first = X; // создаём экземпляр
    let second = first; // меняем владельца
    let third = first; // раз владелец изменился, то использовать first тут уже нельзя
// компилятор ругнётся словами value used here after move

    return third;
}

`struct X` это что-то вроде `case class X ()` — структура без полей.

Такое поведение супер контринтуитивно, думаю, для всех. Не знаю других языков в которых нельзя было бы «использовать» одну и туже «переменную» дважды. Тут важно прочувствовать этот момент. first вовсе не ссылка на X, это его владелец. Меняя владельца мы как бы убиваем предыдущего, borrow checker не допустит его использования.

fn test_borrow_checker () -> i32 {
    let first = 32;
    let second = first; 
    let third = first; 

    return third;
}

Вернёмся к итераторам. Концепцию «захвата» среди них представляет IntoIter. Он «поглощает» коллекцию давая владение над её элементами. В коде эта идея будет отражена так:

let coll_1 = vec![1,2,3];
let coll_2: Vec = coll_1.into_iter().collect();
//coll_1 doesn't exists anymore

Вызвав `into_iter ()` у coll_1 мы «превратили» его в итератор, поглотили все его элементы, как в предыдущем примере `second` поглотил `first`. После этого любые обращения к coll_1 будут караться borrow checker’ом во время компиляции. Потом собрали эти элементы функцией `collect`, создав новый вектор. Функция `collect` нужна чтобы собрать из итератора коллекцию, для этого приходится явно указывать тип того что мы хотим собрать. По этому у coll_2 явно указан тип.

Окей, в целом описанного выше достаточно для языка программирования, но не особо эффективно будет копировать/клонировать структуры данных каждый раз когда мы хотим передать их, да и иметь возможность изменять что-то тоже надо. Так мы переходим к указателям.

Pointers

Владелец, как мы выяснили, может быть только один. А вот ссылок можно иметь сколько угодно. Некомпилирующийся пример выше может быть исправлен так:

struct X; //объявляем структуру

fn test_borrow_checker () -> X {
    let first = X; // создаём экземпляр
    let second: &X = &first; // не меняем владельца, а берём ссылку на значение
    let third = first; // забираем владение X, всё окей

    return third;
}

Этот код уже валидный, потому что владелец по прежнему один (сначала first, потом third). При этом изменение владельца никак не повлияло на second, ссылка будет продолжать указывать куда указывала. Вся эта логика с владением проверяется только на этапе компиляции, никак не влияя на выделение/перемещение памяти. Более того, можно заметить что тип у second изменился на `&X`! То есть семантика владения и ссылок отражена в типах, что позволяет во время компиляции проверить, например, отсутствие race condition.

Каким образом можно защититься от race condition во время компиляции?
Задав ограничение на кол-во мутабельных ссылок!
Мутабельная ссылка в один момент времени может быть одна и только одна (без иммутабельных). То есть либо одна/несколько иммутабельных, либо одна мутабельная. В коде выглядит так:

//объявляем структуру
struct X {
    x: i32,
} 

fn test_borrow_checker() -> X {
    let mut first = X { x: 20 }; // создаём экземпляр
    let second: &mut X = &mut first; // создаём мутабельную ссылку
    let third: &mut X = &mut first; //  создаём мутабельную ссылку. До тех пор пока мы не используем `second` можно считать что мутабельная ссылка только одна - последняя.
//    second.x = 33;  // если раскоментить эту строку, то это приведёт к тому что у нас появится две мутабельных ссылки одновременно, компилятор не допустит такое
    third.x = 33;

    return first;
}

Пройдёмся по изменениям относительного предыдущего примера. Во-первых, добавили одно поле в структуру, чтобы было что менять, нам ведь нужна мутабельность. Во-вторых, появилось `mut` в объявлении «переменной» `let mut first = …`, это маркер компилятору о мутабельности, как `val` & `var` в скале. В-третьих, все ссылки изменили свой тип с `&X` на `&mut X` (выглядит это, конечно, монструозно. и это без лайфтаймов…), теперь мы можем изменять значение хранящееся по ссылке.
Но я говорил, что мы не можем создавать несколько мутабельных ссылок, мол borrow checker этого не даст, но сам создал две! Да, но проверки там весьма хитрые, как раз поэтому порой неочевидно почему компилятор ругается. Он всеми силами пытается сделать так, чтобы ваша программа скомпилировалась и если совсем никаких вариантов нет уложиться в правила, тогда ошибка, и, возможно, не та которую вы ждёте, а та которая нарушает последнюю его попытку, самую отчаянную и не очевидную для новичка :) Например, вам сообщают что структура не реализует Copy трейт, хотя вы нигде не вызывали никаких копий.
В данном же случае существование двух мутабельных ссылок одновременно позволено потому, что используем мы только одну, то есть `second` можно выбросить и ничего не изменится. Также `second` можно использовать до создания `third` и тогда всё будет окей. Но, если раскомментировать `second.x = 33;`, то получится что две мутабельные ссылки существуют одновременно и никак тут уже не выкрутишься — compile time error.

Iterators

Итак, у нас есть три типа передачи:
1. Поглощение, заимствование, moving
2. Ссылка
3. Мутабельная ссылка

Для каждого типа нужен свой итератор.

1. IntoIter поглощает объекты оригинальной коллекции
2. Iter бегает по ссылкам на объекты
3. IterMut бегает по мутабельным ссылкам на объекты

Возникает вопрос — когда какой использовать. Нет серебряной пули — нужна практика, чтение чужого кода, статей. Приведу пример, демонстрирующий идею.
Допустим есть школа, в ней класс, в классе ученики.

#[derive(PartialEq, Eq)]
enum Sex {
    Male,
    Female
}

struct Scholar {
    name: String,
    age: i32,
    sex: Sex
}

let scholars: Vec = ...;

Вектор школьников мы взяли запросом к базе данных, например. Дальше понадобилось посчитать кол-во девочек в классе. Если мы «поглотим» вектор через `into_iter ()`, то после подсчёта не сможем больше использовать эту коллекцию для подсчёта мальчиков:

fn bad_idea() {
    let scholars: Vec = Vec::new();
    let girls_c = scholars
        .into_iter()
        .filter(|s| (*s).sex == Sex::Female)
        .count();

    let boys_c = scholars 
        .into_iter()
        .filter(|s| (*s).sex == Sex::Male)
        .count();
}

На строке подсчёта мальчиков будет ошибка «value used here after move». Очевидно также, что и мутабельный итератор нам тут ни к чему. По-этому просто `iter ()` и работа с двойной ссылкой:

fn good_idea() {
    let scholars: Vec = Vec::new();
    let girls_c = scholars.iter().filter(|s| (**s).sex == Sex::Female).count();
    let boys_c = scholars.iter().filter(|s| (**s).sex == Sex::Male).count();
}

Вот чтобы увеличить кол-во потенциальных новобранцев в стране уже потребуется мутабельный итератор:

fn very_good_idea() {
    let mut scholars: Vec = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
}

Развивая идею можно сделать из «ребят» солдат и продемонстрировать «поглощающий» итератор:

impl Scholar {
    fn to_soldier(self) -> Soldier {
        Soldier { forgotten_name: self.name, number: some_random_number_generator() }
    }
}

struct Soldier {
    forgotten_name: String,
    number: i32
}

fn good_bright_future() {
    let mut scholars: Vec = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
    let soldiers: Vec = scholars.into_iter().map(|s| s.to_soldier()).collect();
    // нет больше scholars, как это не грустно
}

На этой замечательной ноте, пожалуй, всё.

Остался последний вопрос — откуда взялось двойное разыменование ссылок в `filter`. Дело в том, что предикат представляет собой функцию которая принимает ссылку на аргумент (дабы его не захватить):

    fn filter
(self, predicate: P) -> Filter where
        Self: Sized, P: FnMut(&Self::Item) -> bool,

предикат это FnMut (грубо говоря функция), которая принимает ссылку на свой (self) item и возвращает bool. Так как у нас уже была ссылка от итератора`.iter ()`, то в фильтре появилась вторая. При поглощении итератором (`into_iter`) двойное разыменование ссылки превратилось в обычное.

Продолжение

Большого опыта в написании статей у меня нет, так что буду рад критике.
Если интересно, то могу продолжить. Варианты тем:

• как и когда происходит деаллокация памяти
• время жизни ссылок
• асинхронное программирование
• написание небольшого веб сервиса, можно даже предложить api

Links

• rust book
• Из-за концепции владения реализация таких базовых вещей как, например, связный список перестаёт быть тривиальной. Тут разбирают несколько способов как их реализации

© Habrahabr.ru