С прошлой осени Нивен проходит стажировку, разрабатывая новую модель псевдонимов для Rust: древовидные заимствования (tree borrows). Секундочку, уже слышу, как вы вопрошаете: а разве в Rust ещё нет своей псевдонимной модели? Разве вы, автор, не рассказываете повсюду о «стековых заимствованиях»? Действительно, так и есть, но стековые заимствования — всего лишь один из возможных вариантов реализации для модели псевдонимов, и с этим вариантом есть свои проблемы. Древовидные заимствования призваны учесть опыт, усвоенный при работе со стековыми заимствованиями, и построить новую модель, не такую проблемную. Также при её проектировании принимаются немного иные решения, с учётом некоторых нужных компромиссов и той тонкой настройки, которая, возможно, должна быть привнесена в эти модели, и только потом настанет время решать, какую же из этих моделей принять в Rust в качестве официальной.

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

Для краткости я буду иногда называть стековые заимствования «СЗ», а древовидные заимствования — «ДЗ».

Двухэтапные заимствования

Основная новизна древовидных заимствований заключается в том, что в них как следует организована поддержка двухэтапного заимствования. Двухэтапное заимствование — это механизм, введённый в NLL, и благодаря нему становится приемлемым, например, следующий код:

fn two_phase(mut x: Vec<usize>) {
    x.push(x.len());}

Данный код непрост потому, что при удалении сахара он превращается в нечто подобное:

fn two_phase(mut x: Vec<usize>) {
    let arg0 = &mut x;
    let arg1 = Vec::len(&x);
    Vec::push(arg0, arg1);}

Совершенно ясно, что в этом коде нарушаются обычные правила проверки заимствования, так как при вызове  x.len() у нас в коде x в изменяемом виде заимствуется в arg0! Тем не менее, компилятор примет этот код. Вот что тут происходит: тот &mut x, что сохранён в arg0, обрабатывается в два этапа: на этапе резервирования x всё ещё поддаётся считыванию через другие ссылки. Только после того как нам фактически требуется записать информацию в arg0 (или вызвать функцию, которая сможет осуществить такую запись), ссылка окажется «активирована». Таким образом, с этого момента и далее «активация» будет действовать с этой ссылки и далее по ходу выполнения кода (пока не истечёт срок действия (время жизни) заимствования), и никакой доступ к этому коду через другие ссылки разрешаться не будет. Подробнее см. в этом RFC и в главе rustc-dev-guide о двухэтапных заимствованиях. В контексте этого поста важен единственный затрагиваемый там аспект, а именно: когда в некотором вызове метода заимствование происходит неявно (например, x.push(...)), Rust будет трактовать такое заимствование как двухэтапное. Когда вы пишете &mut у себя в коде, этот оборот считается обычной изменяемой ссылкой, без этапа «резервирования».

В контексте псевдонимной модели двухэтапные заимствования — большая проблема: к тому времени, как выполнится x.len(), уже существует arg0, а она, будучи изменяемой ссылкой, не будет допускать операций чтения через другие указатели. Следовательно, стековые заимствования тут просто сдаются и, в принципе, трактуют двухэтапные заимствования как сырые указатели. Разумеется, это нас не устраивает, поэтому в ДЗ мы добавляем поддержку для двухэтапных заимствований. Более того, мы трактуем все изменяемые ссылки как двухэтапные заимствования. Эта политика более мягкая, чем та, что действует на уровне проверки заимствований, зато она позволяет совершенно единообразно обращаться со всеми изменяемыми ссылками. (Возможно, этот момент нуждается в доработке, но, как вскоре будет показано, у такого решения есть серьёзные неожиданные преимущества.)

Вот почему, в первую очередь, нам и требуется дерево: как arg0, так и ссылка, передаваемая Vec::len, являются потомками x. В данном случае стека уже не хватает, чтобы представить такие родительско-дочерние отношения. Как только будет налажена работа с деревом, моделирование двухэтапных заимствований приобретает логичность: исходным состоянием для них является Reserved, и в этом состоянии допускается чтение из других, несвязанных указателей. Только при первой записи по ссылке (или при записи с участием одного из потомков ссылки) переходим в состояние Active, и после этого операции считывания по другим, несвязанным указателям больше не допускаются. (Подробнее об этом см. в посте Нивена. Отдельно заострю внимание на одном неприятном сюрпризе, который здесь таится: если в работу вовлечены UnsafeCell, то зарезервированной изменяемой ссылке потребуется выдерживать мутацию, производимую через несвязанные указатели! Иными словами, на правила совмещения имён, действующие для &mut T, теперь влияет наличие UnsafeCell. Не думаю, что этот момент осознавали при внедрении двухэтапных заимствований, но и избежать его, по-видимому, сложно. Так что даже в ретроспективе неясно, какова могла бы быть в данном случае альтернатива).

Отложенная уникальность изменяемых ссылок

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

let mut a = [0, 1];
let from = a.as_ptr();
let to = a.as_mut_ptr().add(1); // `from` здесь инвалидируется
std::ptr::copy_nonoverlapping(from, to, 1);

Вот в чём причина недопустимости: здесь as_mut_ptr принимает &mut self, и тем самым постулируется уникальный доступ ко всему массиву. Следовательно, инвалидируется созданный ранее указатель from. Но при древовидных заимствованиях такая операция &mut self является двухэтапным заимствованием! as_mut_ptr на самом деле ничего не записывает, поэтому ссылка остаётся зарезервированной и так и не активируется. Таким образом, указатель from остаётся действительным, а вся программа – чётко определённой. Вызов as_mut_ptr трактуется как чтение *self, но from (что касается и разделяемой ссылки, от которой этот указатель производится), и при такой операции совершенно нормально воспринимаются операции считывания через несвязанные указатели.

Оказывается, что в данном случае можно поменять местами строки from и to , и тогда этот код станет работать и при стековых заимствованиях. Но этот шаг не назвать продуманным: на самом деле, он является следствием совсем не стекового правила, действующего в СЗ. Согласно этому правилу, при операции чтения мы просто отключаем все Unique выше тега, используемого для доступа, но сохраняем в рабочем виде сырые указатели, которые были произведены от тех Unique-указателей. В принципе, сырые указатели могут просуществовать дольше тех изменяемых ссылок, от которых они произведены, а это очень нелогично и потенциально может представлять проблему при анализе программы. При ДЗ программа, где мы меняли местами строки, по-прежнему работает нормально, но уже по другой причине: когда первым делом создаётся to, он остаётся в состоянии зарезервированного двухэтапного заимствования. Это означает, что совершенно нормально создать разделяемую ссылку и произвести от неё from (в динамике это действие соответствует чтению self), ведь при двухэтапных заимствованиях допускаются операции чтения через несвязанные указатели. Только когда происходит запись по указателю to, он (вернее, та &mut self, на основе которой он был создан) превращается в активную изменяемую ссылку, для которой требуется уникальность. Но это происходит уже после возврата as_ptr, поэтому у нас не окажется конфликтующей ссылки &self.

Оказывается, что при согласованном использовании двухэтапных заимствований можно полностью избавиться от этого костыльного правила для СЗ, а также устранить один из наиболее частых источников неопределённого поведения при СЗ. Я на всё это совсем не рассчитывал, так что можно сказать, что мне в данном случае просто немного повезло :).

Правда, отметим, что следующая программа будет нормально работать при СЗ, но окажется недействительной при ДЗ:

let mut a = [0, 1];
let to = a.as_mut_ptr().add(1);
to.write(0);
let from = a.as_ptr();
std::ptr::copy_nonoverlapping(from, to, 1);

Здесь при записи в to активируется двухэтапное заимствование, поэтому обязательно требуется уникальность. Это означает, что &self, созданный для as_ptr (который, как считается, считывает все self) несовместим с to, и именно поэтому to инвалидируется (то есть, становится доступен только для чтения), как только создаётся from. Пока нельзя сказать, что такой паттерн часто встречается в реальной практике. Есть способ избежать таких проблем, какие возникают в вышеприведённом коде: нужно задать все ваши сырые указатели до того, как вы начнёте что-либо делать. При ДЗ вполне нормально вызывать методы, получающие ссылки, например, as_ptr и as_mut_ptr, а затем использовать в разрозненных местах возвращённые ими сырые указатели. Так можно делать, даже если эти ссылки перекрываются друг с другом, но вы обязаны вызвать все эти методы до первого акта записи в сырой указатель. После того, как пройдёт первая запись, при создании дополнительных ссылок могут быть нарушены правила работы с псевдонимами.  

Отсутствует строгое ограничение на доступный диапазон памяти

Другой серьёзный источник проблем при использовании стековых заимствований — это  ограничение сырых указателей тем типом и теми свойствами изменяемости, с которыми они сразу создавались. При СЗ, когда ссылка приводится к *mut T, на получающийся в результате сырой указатель налагается ограничение: он может обращаться только к памяти, накрытой T. На этом регулярно попадаются люди, берущие сырой указатель на один из элементов массива (или на одно из полей структуры), а затем пользуются арифметикой указателей для доступа к соседним элементам. Более того, когда ссылка приводится к *const T, она на самом деле доступна только для чтения, даже если ссылка была изменяемой! Многие полагают, что противопоставление *const и *mut не играет роли при работе с псевдонимами, так что эта коллизия регулярно приводит к путанице.

При ДЗ эта проблема решается так: мы больше ничего не переразмечаем при приведении ссылки к сырому указателю. Сырой указатель просто использует тот же тег, что и та ссылка, от которой он произведён. Тем самым он наследует изменяемость этой ссылки и доступный для обращения диапазон адресов. Более того, ссылки не строго ограничены тем диапазоном памяти, который описан в их типе. Когда &mut T (или &T) создаётся из родительского указателя, мы сначала записываем новую ссылку так, чтобы ей был открыт доступ к диапазону памяти, описанному в T (и считаем, что тем самым открываем доступ для чтения к этому диапазону памяти). Правда, здесь мы также осуществляем ленивую инициализацию: при обращении к адресу в памяти, расположенному за пределами этого диапазона, мы проверяем, возможно ли обратиться к этому адресу с родительского адреса, и если так, то предоставляем такой же доступ потомку. Эта операция повторяется рекурсивно до тех пор, пока не найдётся родитель, обладающий достаточным доступом, либо пока мы не достигнем корня дерева.

Таким образом, ДЗ совместимы с арифметикой указателей в стиле container_of и с типами _extern, поэтому с их помощью мы преодолеваем ещё два ограничения ДЗ.

Также это означает, что следующий код становится допустимым при ДЗ:

let mut x = 0;
let ptr = std::ptr::addr_of_mut!(x);
x = 1;
ptr.read();

При СЗ, работая с ptr и выполняя прямой доступ к локальному x, мы используем два разных тега, поэтому при записи в локальную переменную инвалидируются все направленные на неё указатели. При ДЗ всё уже не так: сырой указатель, при создании направленный прямо на локальную переменную, может принимать произвольные псевдонимы, сохраняя при этом прямой доступ к локальной переменной.

Пожалуй, при ДЗ получаем более логичное поведение, но ценой того, что больше не можем опираться на факты записи в локальные переменные как на сигнал о том, что все возможные псевдонимы уже инвалидированы. Однако, отметим, что при ДЗ подобное разрешено только при наличии addr_of_mut (или addr_of) непосредственно в теле функции! Если создаётся ссылка &mut x, а затем какая-то другая функция производит из неё сырой указатель, то такие сырые указатели действительно инвалидируются при следующей записи в x. Так что я здесь вижу идеальный компромисс: в коде, использующем сырые указатели, снижается риск неопределённого поведения, зато код, в котором сырые указатели не используются (а это легко просматривается на уровне синтаксиса) поддаётся оптимизации не хуже, чем код с СЗ.

Обратите внимание: весь подход, применяемый с ДЗ, опирается на то, что в случае с ДЗ не нужен тот костыль, нарушающий стек (об этом костыле мы говорили в предыдущем разделе). Если сырые указатели в случае СЗ просто наследовали родительский тег, то и инвалидировались они вместе с тем уникальным указателем, от которого были произведены. Таким образом, запрещалось использовать весь код, для поддержки которого и изобретался этот костыль. Соответственно, маловероятно, что вообще найдётся способ обратно портировать эти усовершенствования в парадигму с СЗ.

UnsafeCell

При работе с ДЗ серьёзно изменилась и работа с UnsafeCell. Начнём с того, что удалось исправить другую большую проблему с СЗ: было разрешено превратить &i32 в &Cell<i32>, а после этого уже ничего никогда туда не записывать. Эта практика выпадает из того, как обычно при ДЗ обрабатывается совмещение имён, разрешённое UnsafeCell: такие операции трактуются как приведения к сырым указателям, поэтому при повторном заимствовании  &Cell<i32> просто наследуется тег (и, следовательно, все права доступа) родительского указателя.

Есть и более неоднозначный момент: при ДЗ также меняется степень строгости атрибута «только для чтения» в тех случаях, когда при работе с &T где-то внутри T затесалась UnsafeCell. В частности, для &(i32, Cell<i32>) при ДЗ разрешено изменять оба поля, в том числе, первое, представляющее собой обычное i32. В данном случае вся ссылка трактуется как «здесь разрешено работать с псевдонимом».

Напротив, в СЗ всё устроено так, что первые 4 байта доступны только для чтения, и только в последних 4 байтах допускаются изменения, которые выполняются указателями под псевдонимами.

Такое проектировочное решение было принято потому, что общая философия ДЗ тяготела к тому, чтобы кода было больше, а неопределённого поведения — меньше (разрабатывая СЗ, я двигался в противоположном направлении). Такой выбор был целенаправленно сделан для того, чтобы выжать максимум из тех возможностей проектирования, что открывают нам две эти модели. Конечно же, мы хотели удостовериться, что при ДЗ остаются разрешены все желаемые оптимизации. Неопределённое поведения, в свою очередь, должно было присутствовать в достаточном количестве, чтобы и далее не стоило отказываться от работы с промежуточным представлением LLVM, генерируемым rustc. В этом заключалось «понижение планки» по минимальному необходимому нам количеству неопределённого поведения. Оказывается, что при таких ограничениях можно поддерживать UnsafeCell довольно простым способом: правила совмещения имён, действующие для &T, допускают всего 2 случая. Либо нигде нет ни одного UnsafeCell, и в таком случае ссылка доступна только для чтения, либо ссылка допускает применение псевдонимов. Автор, много размышляющий о доказательстве теорем, описывающих полную семантику Rust и, в том числе, работу с псевдонимами, нашёл этот подход на удивление простым.

Я полагал, что это решение будет воспринято как несколько противоречивое, поэтому мы до сих пор удивляемся, какую отдачу получили от пользователей. Есть хорошая новость: эти правила — далеко не незыблемая догма. Можно менять ДЗ так, чтобы работа с UnsafeCell стилистически сближалась с подходом СЗ. Это отличие (чего не скажешь об описанных ранее) совершенно не зависит от других вариантов, выбранных нами при проектировании. Да, я предпочитаю работать с ДЗ, именно в том виде, в каком они существуют сейчас, но считаю, что в конечном итоге мы придём к такому обращению с UnsafeCell, какое принято в СЗ.

Что насчёт оптимизаций?

Я много написал о том, в чём ДЗ отличается от СЗ на уровне паттернов программирования — какие из этих паттернов приводят к неопределённому поведению. Но что же вторая сторона медали, то есть варианты оптимизации? Естественно, поскольку при СЗ неопределённое поведение встречается чаще, логично ожидать, что при ДЗ разрешается меньше оптимизаций. Действительно, есть большой класс оптимизаций, который теряется в ДЗ: это спекулятивные записи, то есть, вставка записей в те пути кода, которые ранее не приводили к записи на данном участке кода. Это мощная оптимизация, и я был просто счастлив, что её удалось внедрить в СЗ, но она даётся дорогой ценой: изменяемые ссылки обязательно должны быть «уникальными, причём, сразу». Учитывая, насколько распространена проблема «перегретой уникальности» (overeager uniqueness), в настоящее время я склонен полагать, что скорее весь такой код будет легализован, чем будут разрешены спекулятивные записи. У нас по-прежнему сохраняются мощные принципы оптимизации, связанные со считыванием. Когда код всё-таки совершат запись, открывающую простор для новых оптимизаций, я всё равно полагаю, что продвигать в данном случае спекулятивные записи — значит зайти слишком далеко.   

С другой стороны, ДЗ всё-таки разрешают ряд критически важных оптимизаций, которые в СЗ случайно оказались исключены: я говорю о переупорядочивании считываний! При СЗ возникает такая проблема: если начать с «прочитай изменяемую ссылку, затем прочитай разделяемую ссылку», а потом изменить порядок на «прочитай разделяемую ссылку, затем прочитай изменяемую ссылку», то считывание разделяемой ссылки может инвалидировать изменяемую, так что неопределённое поведение может просочиться в код именно в результате переупорядочивания! Такая оптимизация возможна и без наличия какой-либо специальной псевдонимной модели, поэтому тот факт, что СЗ её не допускает — просто вопиющая проблема. Если бы не тот костыль, нарушающий работу со стеком (уже неоднократно упоминавшийся выше), то, думаю, нашёлся бы весьма простой способ исправить эту проблему в СЗ. Но, увы, этот костыль подпирает слишком много имеющегося кода, и если его удалить, то во всём этом коде начнётся неопределённое поведение. В свою очередь, ДЗ ни в каком подобном костыле не нуждаются, поэтому с ними можно сразу всё делать правильно: при операции считывания несвязанные изменяемые ссылки не отключаются полностью, а лишь становятся доступными только для чтения. Таким образом, порядок «прочитай разделяемую ссылку, затем прочитай изменяемую ссылку» эквивалентен «прочитай изменяемую ссылку, затем прочитай разделяемую ссылку», и оптимизации сохраняются. (Из этой ситуации следует, что операции повторного размечивания также можно переупорядочивать, так как функционально это операции чтения. Следовательно, порядок установки различных указателей однозначно неважен, до тех пор, пока вы не попытаетесь через один из этих указателей получить доступ на запись.  

Потенциальная возможность: Unique

Древовидные заимствования готовят почву для одного расширения, которое пока не реализовано, но которое я жду-не дождусь исследовать: Unique может получить смысловую нагрузку. Unique — это приватный тип в стандартной библиотеке Rust, при помощи которого изначально предполагалось выражать требования noalias. Правда, его так и не приспособили к выдаче этого атрибута на уровне LLVM. Unique в основном используется в двух местах стандартной библиотеки: Box и Vec. СЗ (и ДЗ) по-особому обращаются с Box (в духе самого rustc), но не Unique, так что Vec не сопровождается какими-либо требованиями, которые касались бы псевдонимов. Действительно, подход СЗ совершенно неприменим с Vec, поскольку нам никак не узнать, для какого объёма памяти здесь предусмотреть уникальность. Но в ДЗ у нас есть ленивая инициализация, поэтому не приходится заранее фиксировать диапазон памяти, эту память можно сделать уникальной «по факту доступа». Таким образом, можно исследовать, а что будет, если дать Unique семантику в Vec.

Возможно, это и не сработает. Люди склонны бездумно плодить псевдонимы с использованием Vec, например, для реализации арен. С другой стороны, уникальность Vec будет вступать в игру только при перемещении или передаче по значению и только для тех диапазонов памяти, к которым мы действительно обращаемся. Поэтому весьма возможно, что этот механизм будет совместим с аренами. Думаю, наилучший способ это выяснить — реализовать семантику Unique под флагом и поэкспериментировать. Если сработает, то мы сможем избавиться от всей специальной обработки Box и полагаться на то, что Box определяется как новый тип поверх Unique. В результате потенциал для оптимизаций немного сократится (известно, что Box<T> указывает на диапазон памяти размером не менее T, тогда как Unique не располагает такой информацией), но частичное устранение магии в Box — это давно преследуемая цель, так что описанный компромисс кажется приемлемым.

Должен отметить, что на взгляд многих ни Box, ни Vec не должны сопровождаться какими-либо требованиями к псевдонимам. Думаю, сначала нужно разобраться, можно ли сформулировать такие требования к псевдонимам, которые оказались бы достаточно легковесными и, следовательно, совместимыми с имеющимися паттернами программирования. Но, даже если в итоге мы скажем, что Box и Vec должны будут действовать как сырые указатели, всё равно было бы полезно иметь в арсенале Unique и предоставлять его авторам небезопасного кода, желающим выжать всю производительность до капли.

Заключение

Существуют серьёзные различия между стековыми и древовидными заимствованиями. Как видите, практически во всех случаях ДЗ позволяют написать больше кода, чем СЗ, и действительно — на мой взгляд, ДЗ решают две наиболее крупные проблемы СЗ. Во-первых, это перегретая уникальность у изменяемых ссылок и ограничение ссылок и сырых указателей размером того типа, который у них был на момент создания. Авторы небезопасного кода уже заинтересовались!

Чего ДЗ не меняет — так это наличия «протекторов», которые обязывают, чтобы определённые ссылки оставались действительными на протяжении всего вызова функции (независимо от того, будут ли они повторно использоваться). Протекторы абсолютно необходимы, чтобы оправдать существование LLVM-аннотаций noalias, которые хотелось бы выдавать. Также протекторы обеспечивают некоторые сравнительно сильные оптимизации, которые иначе были бы невозможны. Я ожидаю, что в парадигме ДЗ именно протекторы останутся основным источником неопределённого поведения и не думаю, что здесь у нас есть большое поле для манёвра. Поэтому, возможно, нам просто придётся советовать программистам откорректировать код и потратить время на подготовку документации, чтобы максимально широко рассказать об этой деликатной проблеме.

Нивен реализовал древовидные заимствования в Miri, так что можете поэкспериментировать с ней и проверить ваш код, задав MIRIFLAGS=-Zmiri-tree-borrows. Если столкнётесь с какими-нибудь неожиданностями, или что-то вас обеспокоит, то дайте нам знать! Такие вопросы удобно обсуждать в t-opsem Zulip и трекере ошибок UCG.