Почему проверка типов в Swift работает медленно

Компилятор Swift может занимать абсурдно много времени при компиляции выражений из-за того, как происходит вывод типов (types inference). Вот объяснение создателя Swift Криса Латтнера (взято из его выступления на Mojo и отредактировано для ясности):

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

Позвольте мне объяснить, что он имеет в виду, на примере:

enum ThreatLevel {
    case normal
    case midnight
}

enum KeyTime {
    case midnight
    case midday
}

func setThreatLevel(_ level: ThreatLevel) {...}

func setThreatLevel(_ level: Int) {...}

setThreatLevel(.midnight)

В последней строке setThreatLevel может ссылаться на одну из двух функций, а .midnight может означать ThreatLevel.midnight или KeyTime.midnight. Компилятор Swift должен найти комбинацию, которая позволит сделать вывод, что мы имеем в виду setThreatLevel(_ level: ThreatLevel) и ThreatLevel.midnight. Это становится проблемой для выражений с большим количеством возможных комбинаций. Обычно это связано с перегрузкой операторов и протоколами ExpressibleBy, потому что каждый литерал (строка, число, булево, словарь, массив) и каждый оператор (* / + — и т. д.) умножают комбинации, которые должен рассмотреть механизм проверки типов.

В этом примере все происходит медленно:

let address = "127.0.0.1"
let username = "steve"
let password = "1234"
let channel = 11

let url = "http://" + username 
            + ":" + password 
            + "@" + address 
            + "/api/" + channel 
            + "/picture"

print(url)

Swiftc тратит 42 секунды на эти 12 строк на M1 Pro2, только чтобы выплюнуть пресловутую ошибку: «компилятор не в состоянии проверить тип этого выражения за разумное время; попробуйте разбить выражение на отдельные подвыражения». За то же время clang может выполнить чистую сборку моего проекта на языке C объемом 59,000 строк 38 раз. Этот пример содержит ошибку, которую компилятор не обнаруживает: оператор + не может добавить channel Int к литералу String. В стандартной библиотеке есть 17 перегрузок оператора + и 9 типов, использующих протокол ExpressibleByStringLiteral. Это приводит к экспоненциальной комбинации типов и операторов, которые компилятор пытается согласовать. В качестве нижней границы, просто учитывая, что пять строковых литералов могут быть девятью возможными типами, получается 59,049 комбинаций.

Вы можете исправить код, преобразовав channel в String:

let url = "http://" + username 
            + ":" + password 
            + "@" + address 
            + "/api/" + String(channel) 
            + "/picture"

Теперь он успешно компилируется за 0.19 секунды!

Возможно, вы думаете, что строки — это сложно или что-то в этом роде, так вот вам очень разумное математическое выражение:

let offset: Double = 5.0;
let index: Int = 10;
let angle = (180.0 - offset + index * 5.0) * .pi / 180;

Снова получаем error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressionsна этот раз спустя «всего» 8 секунд. Ошибка, которую он не может обнаружить, связана с index * 5.0, то есть с Int, умноженным на Double, что можно исправить с помощью Double(index) * 5.0. Даже игрушечные компиляторы быстро обнаруживают и регистрируют эквивалентные несоответствия типов.

Мои друзья в Apple говорят мне, что они просто научились не писать выражения больше определенной длины, чтобы время компиляции оставалось приемлемым. Я слышал похожие истории от друзей из iOS-команды Delta и других компаний.

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

Вывод типа выражения решает ограничения неэффективно и иногда может вести себя сверхлинейно или даже экспоненциально.

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

1. Добавить в swiftc флаг, переключающий на новый механизм проверки типов, который запрашивает добавление информации о типе в случае неоднозначности, а не решает проблему ограничений с экспоненциальным временем. Есть много способов сделать это, требующих различной степени изменений в коде конечного пользователя, но я хочу сказать, что я готов написать несколько аннотаций типов в обмен на быструю, предсказуемую производительность.
2. Сделайте функцию, которая автоматически добавляет аннотации типов, приведения и имена перечислений в существующий код, где это необходимо для компиляции с новым средством проверки типов.
3. Обновите все примеры кода для компиляции с новым средством проверки типов.
4. Сделайте функцию Xcode для скрытия/свертывания/деэмуляции требуемых теперь аннотаций типов, чтобы облегчить переход для людей.
5. Включить флаг по умолчанию для новых проектов Xcode.
6. Отменить старый инструмент проверки типов

Если вы хотите узнать больше о проверке типов в Swift, начните с чтения Type Checker Design and Implementation. Исходный код средства проверки типов находится в папке swift/lib/Sema.