Почему появляются баги? Существует много причин, но если мы взглянем на конкретные примеры, то сможем увидеть закономерности — и спроектировать наши системы так, чтобы избежать целых классов ошибок. 

Под катом автор блога Considerations on Codecrafting рассматривает ошибки, связанные с наложением ссылок, предлагает методы их предотвращения и призывает внедрить эти методы на уровне проектирования новых языков.

---

1. Мой первый ArrayList

Предположим, вы снова первокурсник, изучаете структуры данных и алгоритмы, и вас попросили реализовать на Java списочный массив. Вы можете написать что-то вроде:

public class MyList<E> {
    private E[] arr;
    private int length;

    public MyList() {
        arr = (E[]) new Object[0];
        length = 0;
    }

    public void ensureCapacity(int minCapacity) {
        if (minCapacity > arr.length) {
            int new_capacity = Math.max(minCapacity, arr.length * 2);
            E[] new_arr = (E[]) new Object[new_capacity];
            System.arraycopy(arr, 0, new_arr, 0, length);
            arr = new_arr;
        }
    }

    public boolean add(E e) {
        ensureCapacity(length + 1);
        arr[length++] = e;
        return true;
    }

    public boolean addAll(MyList<? extends E> c) {
        ensureCapacity(length + c.length);
        for (int i = 0; i < c.length; i++) {
            arr[length++] = c.arr[i];
        }
        return true;
    }
}

Код в целом корректен, но содержит небольшую ошибку. Метод addAll предназначен для добавления всех элементов одного списка в другой. Однако что будет, если мы передадим в addAll второй указатель на тот же список?  

public static void main(String... args) {
    MyList s = new MyList<Integer>();
    s.add(42);
    s.addAll(s); // boom!
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
    at MyList.addAll(MyList.java:28)
    at MyList.main(MyList.java:37)

Рассмотрим подробнее реализацию addAll:

public boolean addAll(MyList<? extends E> c) {
    ensureCapacity(length + c.length);
    for (int i = 0; i < c.length; i++) {
        arr[length++] = c.arr[i];
    }
    return true;
}

Сначала мы убеждаемся, что у this достаточно места для добавления элементов из c, вызывая ensureCapacity(length + c.length), а затем добавляем эти элементы один за другим. Проблема в том, что в коде есть соглашение: c.length не меняется, пока мы добавляем элементы.

Если c.length каким-то образом возрастёт во время выполнения addAll, у нас может не хватить места для хранения всех новых элементов, несмотря на зарезервированное дополнительное место c.length в начале метода. Поскольку сам addAll не изменяет c.length, подобная ситуация может показаться невозможной (исключая случай гонки потоков).

Однако если c указывает на тот же объект, что и this, то каждый раз, когда мы выполняем length++ в середине цикла, c.length также возрастает, поскольку length и c.length указывают на одно и то же поле. Это означает, что цикл for будет работать бесконечно, многократно копируя c в конец списка, пока мы не достигнем границы лежащего в основе решения массива и не получим критический сбой программы с ArrayIndexOutOfBoundsException.

2. DAO

Теперь рассмотрим один известный реально существующий баг. DAO — это смарт-контракт, опубликованный в блокчейне Ethereum в 2016 году. Идея DAO заключалась в создании управляемого машиной инвестиционного фонда, где каждый мог бы вносить и снимать деньги, а операции регулировались бы исключительно кодом смарт-контракта, выполняемого на компьютерах «майнеров» в сети Ethereum. 

Любой человек мог внести деньги, вызвав функцию в смарт-контракте, а затем снять их вызовом другой функции. Предполагалось, что смарт-контракт отслеживает, какая сумма принадлежит пользователю, и не позволяет ему снять больше денег, чем он первоначально внёс: чтобы один человек не мог просто украсть деньги всех остальных.

К сожалению, один предприимчивый пользователь заметил в контракте ошибку, которая позволила ему обойти эту проверку и снимать «свои деньги» несколько раз без изменения внутреннего баланса контракта. Таким образом он смог вывести из контракта все деньги, внесённые остальными (около 150 миллионов долларов). Что же пошло не так?

Вот соответствующий код смарт-контракта DAO с добавленными комментариями:

function splitDAO(
  uint _proposalID,
  address _newCurator
) noEther onlyTokenholders returns (bool _success) {

  ...
  // XXXXX Move ether and assign new Tokens.  Notice how this is done first!
  uint fundsToBeMoved =
      (balances[msg.sender] * p.splitData[0].splitBalance) /
      p.splitData[0].totalSupply;
  if (p.splitData[0].newDAO.createTokenProxy.value(fundsToBeMoved)(msg.sender) == false) // XXXXX This is the line the attacker wants to run more than once
      throw;

  ...
  // Burn DAO Tokens
  Transfer(msg.sender, 0, balances[msg.sender]);
  withdrawRewardFor(msg.sender); // be nice, and get his rewards
  // XXXXX Notice the preceding line is critically before the next few
  totalSupply -= balances[msg.sender]; // XXXXX AND THIS IS DONE LAST
  balances[msg.sender] = 0; // XXXXX AND THIS IS DONE LAST TOO
  paidOut[msg.sender] = 0;
  return true;
}

Источник

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

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

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

В примере с MyList соглашение было временно нарушено из-за наличия двух указателей на одну область памяти. В случае с DAO наложение ссылок было более заковыристым.

Как выяснилось, Solidity (язык, на котором написаны смарт-контракты Ethereum) позволяет определить фоллбэк при отправке денег в контракт, и эта функция может выполнить произвольный код. Поэтому злоумышленник просто создал смарт-контракт с функцией отката, которая пытается повторно вывести деньги из DAO, а затем попросил DAO вывести деньги в его смарт-контракт. Когда DAO отправлял деньги злоумышленнику, срабатывала функция отката, которая снова вызывала функцию вывода средств DAO, в то время как оригинальная функция вывода средств все еще была запущена и значение баланса еще не обновилось, — что позволяло бесконечно выводить деньги.

3. Uber

В 2022 году компания Uber опубликовала в своем блоге пост с подробным описанием наиболее распространенных типов ошибок, которые они видели в своём Go-коде на продакшене. Самым частым паттерном, который они наблюдали, был одновременный доступ к слайсам, как в следующем примере.

Слайсы в Go — это, по сути, неинкапсулированная версия нашего класса MyList из первого примера. Они состоят из кортежа (data pointer, length, capacity). Когда вы присваиваете или передаете значение слайса, все эти поля копируются по значению. Длина и вместимость копируются по значению, указатель на данные также копируется по значению, что эквивалентно передаче массива данных по ссылке. Это позволяет легко получить несколько значений слайсов, которые используют один и тот же массив данных, но имеют не согласованные значения длины и вместимости.

Программист Uber осознал необходимость защиты от состояния гонки и добавил мьютекс в функцию safeAppend. Однако это лишь предотвращает одновременный запуск safeAppend несколькими потоками и, соответственно, одновременную запись в myResults. Чтение же myResults в строке 14 вообще не защищено этим мьютексом.

То есть чтение myResults (которое передается в results в строке 11) может происходить в то время, когда в myResults ведется запись в строке 6. Из-за этого при чтении могут появиться мусорные данные. Например, если поле вместимости myResult обновляется раньше, чем поле указателя данных, и в итоге results копирует значение вместимости, не соответствующую указателю данных. В примере Uber нигде не показано, что results используется, но если бы он использовался, это могло бы привести к выходу за границы памяти, — а значит, к выполнению произвольного кода и критическим уязвимостям безопасности.

Среда выполнения Go имеет соглашение, согласно которому три поля значения слайса являются согласованными, и это соглашение нарушается при одновременном доступе к нескольким ссылкам на myResults. В частности, при доступе для изменения myResults в одной из созданных горутин одновременно с доступом на чтение myResults из главного треда.

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

Соглашения и наложение ссылок

Что общего между тремя ошибками выше? В каждом случае нарушалось соглашение — благодаря нескольким ссылкам на одно и то же значение.

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

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

Предотвращение ошибок наложения ссылок

Теперь, когда мы распознали проблему, логичный вопрос — как предотвратить подобные ошибки.

Оказывается, мы это уже проходили. Нулевой указатель был назван «ошибкой на миллиард долларов» из-за огромного количества багов, которые породил. Десятилетиями программисты просто пожимали плечами и принимали как факт жизни NullPointerExceptions (или seg faults, или undefined is not a functions, в зависимости от предпочитаемого вами яда). Нужно просто больше стараться, чтобы не оступиться, верно?

Однако совсем недавно программисты поняли, что так быть не должно: появилось новое поколение языков программирования, в которых возможность для значения быть равным null кодируется в системе типов. Вместо того чтобы каждое значение могло быть null, такими могут быть только те значения, которые явно обозначены программистом. Для остальных значений компилятор будет статически проверять, что они никогда не будут пустыми, что значительно сокращает количество потенциальных ошибок, связанных с нулевым указателем. Люди всегда будут время от времени ошибаться, поэтому важно разрабатывать системы, которые будут ловить и предотвращать эти ошибки.

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

Управление наложением указателей на уровне типов

Как может выглядеть такой язык?

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

Ниже я буду записывать ссылки как shr и xcl соответственно, например, xcl List или shr Map, но вы, вероятно, захотите использовать другой синтаксис в своем языке. Смысл этого поста в том, чтобы проиллюстрировать, как проверка типов может быть использована для исключения большинства ошибок наложения ссылок, а не в том, чтобы диктовать вам синтаксис на поверхностном уровне.

Какие правила требуются этим типам? Во-первых, при создании нового объекта результирующая ссылка гарантированно уникальна, поэтому все объекты начинаются с xcl. Более того, вы всегда можете неявно преобразовать эксклюзивную ссылку в общую, но не наоборот, точно так же, как допускающая пустые значения ссылка может быть неявно преобразована в не допускающую, но не наоборот.

Некопируемые типы

Последнее правило здесь: эксклюзивные ссылки не могут быть скопированы. (Конечно, вы можете преобразовать эксклюзивную ссылку в общую и затем копировать ее сколько угодно). Это означает, что когда вы используете эксклюзивную ссылку, она перемещается, а не копируется. Компилятор должен убедиться, что к старой переменной больше нет доступа. Например:

let foo: xcl Foo = new Foo;
let bar = foo; // foo is moved to bar
foo; // compile error - foo can't be accessed any more

Разрешения и удаление соглашений

В случае с нулевыми указателями требуемый тип входных данных очевиден. Если часть кода обращается к ссылке без проверки на ноль, то она должна принять ненулевую ссылку. Если же проверка на ноль выполняется явно, то вместо нее можно взять ссылку с нулевым значением. Что эквивалентно управлению наложением указателей на уровне типов? Когда нам действительно нужна эксклюзивная ссылка, а когда можно обойтись общими ссылками?

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

Например, представьте, что у нас есть тип UInt для (изменяемых) беззнаковых целочисленных объектов и тип NonZero, который представляет UInts с дополнительным соглашением хранения ненулевого значения. Мы можем написать функцию, которая принимает ненулевое значение int и временно нарушает соглашение следующим образом:

fn increment(x: xcl NonZero) -> xcl NonZero {
    let x = x as UInt; // remove invariant
    *x += 1;
    // check for overflow and ensure value is nonzero
    if *x == 0 {
        *x = 0xFFFFFFFF; // saturate at max value
    }
    // add the invariant back
    return x as NonZero;
}

Лично мне нравится думать о xcl и shr как о правах доступа для связанных ссылок. Однако это не совсем то же самое, что права доступа типа «можно читать» или «можно писать», о которых вы, вероятно, привыкли думать как о «разрешениях». Скорее, xcl —  это разрешение предполагать, что никто другой не обращается к этому значению, что, в свою очередь, подразумевает разрешение на удаление соглашений.

Конечно, вы можете создать сколь угодно структурированную систему разрешений, если захотите. Например, у вас может быть один тип разрешения для указателей, когда только вы можете писать в указатель, но могут существовать другие копии, которые могут читать это значение. Но система xcl/shr с двумя разрешениями иллюстрирует все необходимые фундаментальные соображения, поэтому я буду придерживаться ее для простоты.

Временные права доступа

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

Предположим, например, что мы хотим вызвать нашу функцию increment дважды. Придется сделать что-то вроде этого:

fn increment_twice(x: xcl NonZero) -> xcl NonZero {
    let x = increment(x);
    let x = increment(x);
    return x;
}

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

Нужна возможность делать что-то вроде:

fn increment(x: xcl NonZero) {
    // ...
}

fn increment_twice(x: xcl NonZero) {
    increment(x);
    increment(x); // ??? 
}

Однако функция increment_twice не работает, потому что x уже был перемещен при первом вызове increment. Интуитивно кажется, что код должен работать. В конце концов, increment нужен только временный эксклюзивный доступ к x. После завершения вызова increment он не удерживает никаких ссылок на x, поэтому у нас должна быть возможность снова рассматривать x как эксклюзив в родительской функции increment_twice и, таким образом, иметь возможность вызвать increment во второй раз.

Решение заключается во временных правах доступа. Вместо того чтобы предоставлять increment постоянный эксклюзивный доступ к x, мы предоставляем ему временный эксклюзивный доступ к x на время вызова, и таким образом можем вызвать его снова после завершения первого вызова.

Предоставление прав доступа

Как же это реализовать? В частности, как сделать проверку типов без дорогостоящего межпроцедурного анализа кода? Как представить всю информацию, необходимую для проверки временных прав доступа, только в аннотациях типов?

В дополнение к праву доступа (xcl или shr), каждый тип ссылки опционально имеет параметр grant, который отслеживает предоставление временных прав доступа и когда они могут быть отменены. В синтаксисе примера я буду писать гранты с использованием ведущего апострофа, то есть 'a xcl Foo. Обратите внимание, что гранты существуют исключительно во время компиляции. Типы прав доступа служат лишь для статической проверки типов, чтобы предотвратить ошибки. Во время выполнения все компилируется в обычные указатели, и никаких накладных расходов во время выполнения не возникает.

Кроме того, я введу ключевое слово 'call для обозначения отрезка времени, в которое происходил текущий вызов функции. Таким образом, мы можем записать increment следующим образом:

fn increment(x: 'call xcl NonZero) {
    // ...
}

Обратите внимание, что параметры гранта всегда будут обобщенными, потому что каждый экземпляр каждого вызова будет иметь свой грант. Поэтому 'call здесь — это сокращение от «любой 'а такой, что 'a продолжается, по крайней мере, столько же, сколько 'call». Для примера синтаксиса запишем это как:

fn increment<'a: 'call>(x: 'a xcl NonZero) {
    // ...
}

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

fn increment<'a: 'call>(x: 'a xcl NonZero) -> 'a xcl NonZero {
    // ...
    return x as NonZero;
}

Поскольку аргумент и возвращаемое значение имеют один и тот же параметр grant, компилятор может узнать, что возвращаемое значение зависит от входных данных, не заглядывая в тело функции.

Теперь вернемся к increment_twice и сделаем ее немного интереснее, через сохранение возвращаемого значения и добавление нескольких дополнительных вызовов increment; попытаемся инкрементировать в общей сложности четыре раза, но будем использовать для последнего вызова устаревшую ссылку, что должно привести к ошибке компиляции:

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    let y = increment(x);
    increment(y); // ok
    increment(x); // also ok
    increment(y); // compile error - y's permission grant has been revoked by this point
}

Расщепление прав доступа

Чтобы проверить этот код, нам нужно ввести понятие расщепления прав доступа, а это является самой неинтуитивной частью проверки наложения ссылок.

Мы уже попробовали это на примере начальной версии некопируемых типов:

let a: xcl Foo = new Foo;
let b = a; 
// b has type xcl Foo, a has type undefined

По сути, a имеет определенное количество разрешений на доступ к своему содержимому. В простом случае с некопируемыми типами мы передаем все разрешения новому значению всякий раз, когда читаем переменную. Это означает, что исходная переменная a больше не имеет никаких разрешений и, следовательно, не может быть доступна.

Однако вместо того, чтобы передавать разрешения a постоянно при чтении, мы можем передать только часть разрешений, а именно ту часть, которая разрешает доступ до определенного момента времени. Тогда к b можно будет обращаться только до этого момента, а к a — только после этого момента; таким образом исключается конфликт, связанный с тем, что оба они имеют (ограниченное по времени) эксклюзивное разрешение.

Более конкретно: когда мы читаем a, мы присваиваем прочитанному значению (b) тип '0 xcl Foo, где '0 — свежесгенерированная переменная гранта, показывающая, что к b можно обращаться до тех пор, пока грант '0 не будет отозван. Тем временем a будет иметь тип «можно получить доступ как xcl Foo, предварительно отозвав грант '0». Мы напишем 'n -* T, чтобы представить тип «можно отозвать 'n, чтобы получить доступ как T», поэтому a будет иметь тип '0 -* xcl Foo. Обратите внимание, что -* — это просто пример синтаксиса для обсуждения. На практике эти типы будут использоваться только для внутреннего учета компилятором и никогда не будут открыты пользователю, поэтому неважно, что синтаксис некрасивый.

Пример проверки типов

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

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    let y = increment(x);
    increment(y); // ok
    increment(x); // also ok
    increment(y); // compile error - y's permission grant has been revoked by this point
}

Начинаем с того, что все переменные (то есть только x) имеют типы, указанные в сигнатуре функции:

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    // types: x: 'b xcl NonZero
    let y = increment(x);
    increment(y); // ok
    increment(x); // also ok
    increment(y); // compile error - y's permission grant has been revoked by this point
}

Теперь мы добрались до x в первом increment(x). Мы генерируем новую переменную гранта, '0, и присваиваем тип '0 xcl NonZero временному значению, считанному из x. Тем временем локальная переменная x меняет свой тип на '0 -* 'b xcl NonZero. Это означает, что в настоящее время она не имеет никаких разрешений, но получит разрешение 'b xcl NonZero, если отменит грант '0.

Далее мы сопоставляем значение аргумента с сигнатурой типа increment, так 'a совпадает с '0. Теперь мы знаем, что возвращаемое значение имеет тот же грант, поэтому y получает тип '0 xcl NonZero.

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    let y = increment(x);
    // types: x: '0 -* 'b xcl NonZero, y: '0 xcl NonZero
    increment(y); // ok
    increment(x); // also ok
    increment(y); // compile error - y's permission grant has been revoked by this point
}

Далее мы делаем то же самое со строкой increment(y), генерируя переменную субгранта '1. Это не имеет значения, потому что на этот раз мы не храним возвращаемое значение и можем отменить грант в любой момент, но я указываю это явно для ясности.

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    let y = increment(x);
    increment(y); // ok
    // types: x: '0 -* 'b xcl NonZero, y: '1 -* '0 xcl NonZero
    increment(x); // also ok
    increment(y); // compile error - y's permission grant has been revoked by this point
}

Самое интересное происходит, когда мы доходим до второго вызова increment(x). increment требует аргумент типа 'a xcl NonZero для некоторого 'a, но наша переменная x в данный момент имеет тип '0 -* 'b xcl NonZero. Поэтому мы отзываем грант '0, что меняет тип обратно на 'b xcl NonZero. Поскольку '1 зависит от '0, она также отзывается. y больше недоступна.

После изменения типа x на 'b xcl NonZero' мы можем расщепить его, как и раньше, в результате чего появится новая локальная переменная-грант, поэтому мы генерируем временное значение с типом '2 xcl NonZero для передачи в increment и меняем тип переменной x на '2 -* 'b xcl NonZero'.

fn increment_four_times<'b: 'call>(x: 'b xcl NonZero)  {
    let y = increment(x);
    increment(y); // ok
    increment(x); // also ok
    // types: x: '2 -* 'b xcl NonZero, y: undefined
    increment(y); // compile error - y's permission grant has been revoked by this point
}

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

Первоклассные -* типы

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

Более того, все переменные-гранты локальны для проверяемой функции, и только свежие гранты, определенные в той же функции ('0, '1 и т. д., в отличие от 'b), могут появляться перед -*. Это гарантирует, что мы можем статически отменить гранты во время проверки типов и, следовательно, можем стереть их во время компиляции, а также отсутствие накладных расходов во время выполнения.

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

Вывод типов

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

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

Слон в комнате

А теперь об очевидном: система, которую я описал, похожа на то, как всё устроено в существующем языке программирования Rust и его «проверки заимствований».

Люди часто думают, что Rust трудно изучать из-за его проверки заимствований, и размышляют так: «Может быть, проверка заимствований и нужна, если вы хотите писать на C++ правильно, но зачем она нужна для конкурента Java/Python/Javascript?». Почему мы не можем просто использовать GC и отбросить страшную проверку заимствований?

Однако логика в точности обратная. Верно, что Rust призван заменить C++, и что в Rust есть проверка заимствований, и что проверка заимствований необходима для безопасного управления памятью, к которому люди привыкли в C++. Однако это не значит, что проверка заимствований полезна или необходима только при работе с C++, или что она не полезна в языке со сборщиком мусора. Управление памятью — это наименее интересное применение проверки заимствований.

Одна из целей этого поста — показать, как логика предотвращения общих ошибок неумолимо приводит к чему-то, что хотя бы смутно похоже на проверку заимствований в Rust (конечно, она не обязательно должна быть идентичной — по сравнению с Rust есть большой простор для улучшений!). На самом деле, два из трех языков из раздела примеров с ошибками имеют сборщики мусора. GC не избавляет от необходимости проверять заимствования, а лишь устраняет некоторые неудобства, связанные с их использованием.

Заключение

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

Проверка на null тоже когда-то была необычной, но сейчас, в век Kotlin и TypeScript с его strictNullChecks TypeScript, никто не будет воспринимать язык без проверки на null всерьез. Я думаю, когда-нибудь то же самое произойдет и с проверкой на наложение указателей.

*Примечание от Сравни

В статье автор обозначил ряд любопытных тезисов и привел интересные примеры по теме предотвращения ошибок, связанных с наложением ссылок. При этом в некоторых аспектах его логика показалась нашей команде спорной. В частности, есть решительное подозрение, что при работе в многопоточных средах техника автора с отбором привилегий окажется нерабочей в случае передачи управления в другой поток. (Пример: функция increment запускает корутину — и немедленно выясняется, что у нас нет возможности выяснить, остался у нас доступ к указателю или нет.)

А что о прочитанном думаете вы? Со всем ли согласны, встречались ли с чем-то подобным на практике? Давайте обсудим в комментах!