Rust. Borrow checker через итераторы

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

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

Последнее время 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<i32> = 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 не допустит его использования.

Зачем надо было создавать свою структуру, почему бы не использовать обычный integer?
Вдумчивый читатель может спросить — зачем автор создал тут новую структуру (`struct X`), взял бы, например, тот же integer. По идее да, можно было бы так сделать, но тогда код бы компилировался:


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

    return third;
}

Этот код скомпилируется, потому что borrow checker, увидит что мы дважды используем одно и тоже и попытается скопировать значение, вместо замены владельца. В расте есть трейт Copy, смысл которого это копирование области памяти. То есть в примере с `i32` second получит не владение на число, а его копию(и станет её владельцем), из-за этого third сможет получить владение. Для структуры X я не определил трейт Copy, поэтому там компилятор не смог выкрутиться.

Далеко не всё можно просто скопировать. Например строку нельзя, ведь строка это ссылка на мутируемую область памяти и если мы скопируем эту ссылку, то у нас получится две «владеющие» ссылки на одну и туже область памяти и это разрушит всю концепцию. Для копирования таких сложносоставных структур есть трейт Clone, его отличие в том, что он вызывается только явно. Более детально про copy и clone.

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


let coll_1 = vec![1,2,3];
let coll_2: Vec<i32> = 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


Владелец, как мы выяснили, может быть только один. А вот ссылок можно иметь сколько угодно.


#[derive(Debug)]
struct Y; //объявляем структуру

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

//используем обе
    println!("{:?}", second);
    println!("{:?}", third);

    return first;
}


Этот код уже валидный, потому что владелец по прежнему один. Вся логика с владением проверяется только на этапе компиляции, никак не влияя на выделение/перемещение памяти. Более того, можно заметить что тип у second изменился на `&Y`! То есть семантика владения и ссылок отражена в типах, что позволяет во время компиляции проверить, например, отсутствие 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<Scholar> = ...;

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


fn bad_idea() {
    let scholars: Vec<Scholar> = 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<Scholar> = 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<Scholar> = 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<Scholar> = Vec::new();
    scholars.iter_mut().for_each(|s| (*s).sex = Sex::Male);
    let soldiers: Vec<Soldier> = scholars.into_iter().map(|s| s.to_soldier()).collect();
    // нет больше scholars, как это не грустно
}

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

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


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

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

Продолжение


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

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

Links


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

Подробнее
Реклама

Комментарии 20

    +3

    Отличная статья, читал на одном дыхании. Пишите ещё! Единственное что не понял это функция toSoldier. Функция принимает на вход некий self, а в маппере передаёте ей школьника. Как компилятор вывел из него имя?

      +1

      Функция находится в блоке impl Scholar. Соответственно, она в качестве первого аргумента может принимать:


      • self, т.е. self: Scholar,
      • &self, т.е. self: &Scholar,
      • &mut self, т.е. self: &mut Scholar,
      • и, если не ошибаюсь, аналогично Pin<Box<self>> и Pin<&mut self>, но это уже экзотика;
      • ну, или ничего из перечисленного — тогда это будет не метод, а ассоциированная функция (статический метод, если угодно), которая вызывается на типе, а не на объекте.
        +1

        Не надо так (это означает, что в дизайне структур данных что-то пошло не так, единичные кейсы исключительные кейсы, когда это нужно):


        Pin<Box<self>>

        Да и Pin<T> — это экзотика из-за ее документации. Редкий новичок или поверхностный погруженец позволит съесть свой мозг чайной ложечкой.

      +2
      Этот код уже валидный, потому что владелец по прежнему один (сначала first, потом third). При этом изменение владельца никак не повлияло на second, ссылка будет продолжать указывать куда указывала.

      Нет, нет, нет. Не надо так. Простой контрпример:


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

      В Вашем примере всё работает не потому, что заимствование в second не затронуто перемещением, а потому, что оно попросту не используется, и borrow-checker — как Вы позже заметили применительно к уникальным (изменяемым) заимствованиям — достаточно умный, чтобы это заметить.

        +1
        Да, вы правы, и параграф после этого кода соответственно тоже не точный. Постараюсь исправить сегодня. Спасибо)
        +3
        А можете в таком же духе рассказать про Box, Arc, Pin?
          +3
          Про Box и Arc — они довольно простые, по идее могу. А вот с Pin самому надо доразобраться, так что это хороший повод написать.
          +9
          По-этому просто iter() и работа с двойной ссылкой

          Не обязательно загромождать код оператором разыменования, тк в rust есть deref coercion и компилятор может автоматически разыменовывать ссылки (примерно как в c++):


          fn good_idea() {
              let scholars: Vec<Scholar> = 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();
          }

          Аналогично в других кусках кода.

            0

            О! А это объясняет почему такая «кривлять» как двойное разыменованием на ровном месте есть в языке. Программист его все равно не заметит.


            Правда я так и не понял зачем нужна ссылка на ссылку… они же немутабельные.

              +2

              Тут скорее не "зачем", а "почему". Следите за руками:


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

              Оба этих требования не зависят ни от типа элементов вектора, ни от типа элементов в итераторе — даже несмотря на то, что в некоторых случаях можно просто копировать исходные элементы (и это реально будет делаться, если в цепочку вставить copied()), сигнатуры методов Vec::iter() и Iterator::filter() остаются одни и те же. Отсюда и двойная ссылка — потому что есть две независимые причины эти самые ссылки навесить.

              0

              Можно просто писать ссылку в аргументе лямбды. Так: |&s| ..., Тогда внутри лямбды уже можно точно без разименовывания.

              0
              Спасибо! Очень просто и интересно написано. Продолжайте в том же духе!
                0
                спасибо, приятно такое видеть)
                +2
                Автор, прошу еще статей на rust :)
                  +1

                  Статья огонь, а можно точно также рассказать про lifetime?

                    0
                    Если вы понимаете английский, то рекомендую вот это видео. По идее после его просмотра и некоторого количества самостоятельных экспериментов вопросов остаться не должно.
                      0
                      Вообще, имхо, последняя версия rustbook'а довольно неплохо это объясняет. Лучше первой. Правда в русском переводе есть настолько синтетический и неестественный текст, что иногда вникать тяжело, но в принципе понятно.
                      0
                      Если интересно, то могу продолжить. Варианты тем:
                      Голосую за веб-сервис. API самое очевидное — Conduit. В идеале без макросов ).
                        0
                        Может быть, но апи там довольно сложный — много работы всё это имплементить.
                        А пока не написал статью вам может быть интересна эта статья: docs.qovery.com/guides/tutorial/create-a-blazingly-fast-api-in-rust-part-1
                        Либо мой небольшой репозиторий with actix + diesel: github.com/invis87/ebbinghaus_memory_service
                          0
                          И там и там все на макросах. Это слишком легко написать, но ИМХО сложно объяснить/разобраться что происходит «под капотом».

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое