Слияние кода завершено, страница обновится автоматически
Этот документ предназначен для людей, заинтересованных в изучении того, как работает Sorbet с целью участия в развитии проекта.
Для информации о том, как использовать Sorbet, см. https://sorbet.org/docs/overview. Для информации о сборке и тестировании Sorbet, см. README.
Иначе говоря, добро пожаловать!
Этот документ находится в процессе разработки. Пожалуйста, задавайте вопросы при встрече с незаконченными или запутанными разделами!
Sorbet состоит из основного пайплайна проверки типов с несколькими поддерживающими утилитами и данными структурами.Кратко, вот структура папок, которую мы используем (учтите, что это не полная структура, но она должна дать вам общее представление):
sorbet
│ // 1. Основной модуль
├── основной
│ ├── конвейер → Последовательность этапов, передача одного этапа в следующий.
│ ├── lsp → Код специфичный для языкового сервера.
│ ├── опции → Парсинг опций
│ └── автоген → Специфический для Stripe, для автогенерации
│
│ // 2. Этапы (более подробная информация ниже)
├── парсер
├── аст
│ └── десягурт
├── DSL
├── локальные_переменные
├── нэмер
├── решолвер
├── CFG
│ └── билдер
├── инфер
│
│ // 3. Другое
├── общие → Утилиты и вещи, специфичные не для Sorbet, необходимые повсюду.
│ └── ос → Код специфичный для платформы.
├── ядро → Специфичные для Sorbet структуры данных и утилиты.
│ └── типы → Наша система типов используется многими проходами конвейера кода выше.
│
│ // 4. Гели
├── гели
│ ├── sorbet → Ruby-источник для `srb init`.
│ └── sorbet-runtime → Ruby-источник для проверок типа во время выполнения.
└── ···
До сих пор вы должны иметь общее представление о высоком уровне структуры Sorbet.
Оставшаяся часть этой документации не предназначена для последовательного чтения. Вы можете свободно перемещаться между разделами.В частности, чтобы понять фазы, вам нужно понять основные абстракции, но знакомство с фазами мотивирует существование некоторых ключевых абстракций.
При изучении фаз в следующей части может быть полезно рассмотреть эту диаграмму высокого уровня архитектуры основного пайплайна типовой проверки Sorbet:
IR означает "внутреннее представление". Каждая фаза либо переводит одно IR в другое, либо модифицирует существующее IR. Эта таблица показывает порядок фаз, IR, с которыми они работают, и указывает, переводят ли они одно IR в другое или выполняют изменения внутри данного им IR.
*: Несмотря на то что эти этапы модифицируют данное им IR, у них есть ещё одна важная задача — заполнение GlobalState.
**: Этот этап вообще не модифицирует AST. Он просто генерирует ошибки.| | Этап перевода | IR | Этап переписывания | | --- | ---------------- | -- | ------------ | | | | исходные файлы | | | 1 | Parser,-p parse-tree| | | | | |parser::Node| | | 2 | Desugar,-p desugar-tree| | | | 3 | |ast::Expression| Rewriter | | 4 | |ast::Expression| LocalVars,-p rewrite-tree| | 5 | |ast::Expression| Namer,-p name-tree() | | 6 | |ast::Expression| Resolver,-p resolve-tree() | | 6 | |ast::Expression| [DefinitionValidator] (**) | | 6 | |ast::Expression| [ClassFlatten],-p ast| | 7 | CFG,-p cfg --stop-after cfg| | | | 8 | |cfg::CFG| Infer,-p cfg|
Когда вы видите ссылки на файлы ниже, вам следует открыть файл и быстро просмотреть его перед продолжением. Большинство разделов ниже написано в виде руководства по кодовой базе, чтобы помочь вам найти нужное место, а не как полный справочный материал.У Sorbet есть два флага, которые незаменимы при анализе того, что происходит между различными этапами:
-p, --print <state>
***-raw, пока вы не станете знакомым с кодовой базой.--stop-after <phase>
Мы будем рассматривать отдельные фазы и IR ниже.
Парсер, который мы используем, основан на парсере whitequark/parser, популярном парсере для Ruby. Парсер Ruby версии 2.4 был портирован на yacc / C++ Хейли Сомервиллом для использования в её проекте TypedRuby, и с тех пор получил множество внешних вкладов для поддержки последних версий Ruby. Исходники можно найти в директории third_party/parser/.
Мы взаимодействуем с парсером TypedRuby с помощью генерации кода для создания C++ заголовка. Чтобы просмотреть C++ заголовок, сначала скомпилируйте Sorbet, затем найдите его внутри Bazel в директории bazel-genfiles/parser/Node_gen.h.
Заголовок сам по себе генерируется с помощью parser/tools/generate_ast.cc.Общими чертами является то, что IR, созданное парсером, моделирует Ruby очень детализированно. Эта высокая детализация часто превышает границы, необходимые для целей типизации. Мы используем проходы Дессугара и Редактора для упрощения IR перед типизацией.### ДесягARING
Проход десягARING переводит из типа parser::Node в тип ast::Expression. Целью десягARINGера является значительное уменьшение детализации IR парсера.
Чтобы дать вам представление о масштабах десягARINGового прохода, рассмотрим несколько цифр. На момент написания этого материала существует 98 подклассов parser::Node. Существует всего 34 подкласса ast::Expression.
Для просмотра прохода десягARINGа вам потребуется посмотреть на ast/desugar/Desugar.cc. Вы заметите, что это в основном один большой рекурсивный метод с использованием typecase. (См. ниже для дополнительной информации о typecase; это своего рода "функциональное паттерн-матчинг".)
Некоторые примеры того, что мы упрощаем в этом проходе:
case становятся цепочками выражений if/else
+=) становятся обычными присваиваниями (x = x + 1)unless <cond> становится if !<cond>
Если вы передадите опцию -p desugar-tree или -p desugar-tree-raw командной строке sorbet, вы сможете увидеть, как будет выглядеть Ruby-программа после удаления синтаксических сахаров.
ast::Expression и преобразует конкретные Ruby DSL и метапрограммирование в код, который может анализировать Sorbet. В данном контексте DSL могут иметь широкий спектр значений. Некоторые примеры DSL, которые преобразуются этим предпроцессором:- attr_reader и его аналоги преобразуются в простое определение методов, которые были бы определены при выполнении метода attr_reader (вы знали, что attr_reader — это всего лишь обычный метод в Ruby, а не ключевое слово языка?)Chalk::ODM записываются аналогично attr_reader.Основной предпроцессор Rewriter расположен в rewriter/rewriter.cc. Каждый модуль предпроцессора Rewriter находится в своём файле в папке rewriter/.
Мы видим потенциал использования предпроцессора Rewriter как точки расширения для какой-либо системы плагинов. Это позволит более широкому кругу Ruby-разработчиков обучать Sorbet новым DSL, которые они создали. Именно поэтому мы намеренно ограничиваем мощность предпроцессоров Rewriter.
Конкретнее говоря, искусственно ограничивается то, какие части кода вызываются предпроцессорами Rewriter. Иногда было бы удобно обращаться к другим этапам работы Sorbet (например, resolver или infer), но вместо этого мы реализовываем эту функциональность внутри предпроцессора Rewriter. Это позволяет сохранять небольшую поверхность API, которую нам придётся представлять будущим плагинам.
Это довольно короткий предпроцессор. Он конвертирует узлы AST ast::UnresolvedIdent, соответствующие локальным переменным, в узлы ast::Local. Узлы ast::UnresolvedIdent также используются для экземплярных, классовых переменных и глобальных переменных, но эти случаи обрабатываются другими этапами.В большинстве случаев эта задача выполняется очень просто путём прохождения дерева. Одним из трюков является то, что локальные переменные отслеживают, к какому Ruby-блоку (например, do ... end) они принадлежат. (Ruby-блоки вводят новые лексические области; конструкции типа if / else и begin / end не вводят новых областей.)
Название отвечает за создание Symbol для классов, методов, глобальных переменных и аргументов методов. (Противоречащее интуиции, название не отвечает за создание Name. См. ниже различие между [Symbolами] и [Nameами]).
Файл, который вы хотите просмотреть, это namer/namer.cc.
Символы являются каноническим хранилищем информации о определениях в Sorbet. Название проходит по дереву ast::Expression и вызывает различные методы для создания Symbol, который владеется GlobalState, и получает обратную ссылку на то, что было создано (например, enterMethodSymbol и enterClassSymbol). Эти методы возвращают SymbolRef, который концептуально является новым типом обёрткой вокруг указателя на Symbol. См. ниже обсуждение о [Symbolах против SymbolRef][#refs-ie-symbol-vs-symbolref].
Основной структурой данных для этапа названия является таблица символов, которую мы можем распечатать. Взглянем на этот файл:
class A
def method(method_arg)
local = 1 # имя не будет создано
``` @поле = 2
$глобальная = 3
конец
# одиночные методы — это просто методы на классе Singleton
def self.одиночный_метод(одиночный_метод_арг)
# одиночные поля — это просто поля на классе Singleton
@одиночное_поле = 4
конец
@@статическое_поле = 5
конец
Мы увидим следующий вывод таблицы символов:
❯ sorbet --no-stdlib -p symbol-table --stop-after namer docs_example_1.rb
класс ::<корневой>()
поле #$глобальная @ docs_example_1.rb:7
класс ::А < ::<необходимо определить символ>() @ docs_example_1.rb:1
метод ::А#метод(метод_арг) @ docs_example_1.rb:2
аргумент ::А#метод#метод_арг<> @ docs_example_1.rb:2
класс ::<Класс:А>() < ::<необходимо определить символ>() @ docs_example_1.rb:1
метод ::<Класс:А>#одиночный_метод(одиночный_метод_арг) @ docs_example_1.rb:11
аргумент ::<Класс:А>#одиночный_метод#одиночный_метод_арг<> @ docs_example_1.rb:11
Замечания:
Symbol (класс, метод и т.д.).Symbol класса знает, как вернуть его члены. Symbol метода знает, как вернуть его аргументы.Symbolы для определений), но был оптимизирован для параллелизма и скорости.Подробнее см. Namer & Resolver Pipeline.### Разрешитель
После выполнения Namer мы создали [Symbolы] для большинства (но не всех) объектов, однако эти Symbolы ещё не были связаны между собой. Например, после работы Namer у нас было множество Symbolов с меткой <todo sym>, представляющих предков классов. Другой пример: после работы Namer мы создали Symbolы для методов, но ни один из этих Symbolов не содержал информации о типах аргументов.
Решатель выполняет множество специализированных задач, но мы выделим две: разрешение констант и сигнатур. Обсудим каждую в отдельности.
Разрешение констант: После выполнения Namer, литералы констант (например, A::B) в наших деревьях проявляются как UnresolvedConstantLit узлы. Узел ast::UnresolvedConstantLit оборачивает NameRef, в то время как ast::ConstantLit оборачивает SymbolRef. В этих терминах процесс разрешения констант заключается в преобразовании Name в Symbol (UnresolvedConstantLit в ConstantLit).
Разрешение сигнатур: Как только константы были разрешены до правильных Symbolов, можно заполнить информацию о типах (поскольку сигнатуры в основном являются хэшами констант). Для заполнения сигнатур Sorbet анализирует информацию из узлов ast::Send, соответствующих методам создания сигнатур, использует это для создания core::Type и сохраняет эти типы на Symbolах, соответствующих методу и его аргументам.
Чтобы дать вам представление, вот что наш пример Namer выглядит после этапа Resolver:
❯ sorbet --no-stdlib -p symbol-table --stop-after resolver docs_example_1.rb
класс ::<корень> от ::Object ()
поле #$global @ docs_example_1.rb:7
класс ::A от ::Object () @ docs_example_1.rb:1
метод ::A#<static-init> () @ docs_example_1.rb:16
статическое поле ::A#@@static_field -> T.untyped @ docs_example_1.rb:16
поле ::A#@field -> T.untyped @ docs_example_1.rb:5
метод ::A#метод (method_arg) @ docs_example_1.rb:2
аргумент ::A#метод#method_arg<> @ docs_example_1.rb:2
класс ::<Класс:A> от ::<Класс:Object> () @ docs_example_1.rb:1
поле ::<Класс:A>#@singleton_field -> T.untyped @ docs_example_1.rb:13
метод ::<Класс:A>#singleton_method (singleton_method_arg) @ docs_example_1.rb:11
аргумент ::<Класс:A>#singleton_method#singleton_method_arg<> @ docs_example_1.rb:11
-> является новым).<todo sym> отсутствуют (поскольку константы были разрешены).::A#@field).> Разрешение всегда было одной из сложных фаз. Введение параллелизма сделало её ещё более сложной, хотя она всё ещё концептуально следует за теми паттернами, которые здесь обсуждаются.Подробнее см. Пайплайн Namer & Resolver.### ClassFlatten
Класс Flatten представляет собой последнюю фазу, которая обрабатывает AST. Цель состоит в том, чтобы переместить все узлы таким образом, чтобы окончательный результат содержал только верхние уровни классов, а те, в свою очередь, должны содержать только определения методов. Код, который выполняется на верхнем уровне Ruby-класса, собирается в специальный метод self.<static-init> внутри этого класса. Верхние уровни выражений в файле перемещаются в уникальный метод <static-init> на синтетическом объекте <root>.
После этой фазы весь код, который можно проверить на типы, находится в методах. Это значит, что во время следующей фазы CFG мы можем рассматривать только узлы ast::MethodDef AST и игнорировать узлы ast::ClassDef (все информацию, которую мы когда-либо хотели бы получить о классе, уже занесено в GlobalState).
Примечание: Также существует фаза в редакторе, называемая
rewriter::Flatten. Эта фаза предназначена для вынесения вложенныхast::MethodDefна верхний уровень класса. (У этой операции есть некоторые приятные свойства, например, возможно определить всеSymbolбез перехода внутрь тел методов. И поскольку эта операция выполняется в [редакторе], выходные данные кэшируются и аннулируются на уровне файла.)Если у вас есть лучшие названия для этих двух фаз, чтобы сделать их более различимыми, они будут очень желаемыми!### CFG
CFG — это еще одна фаза трансляции, но теперь из ast::Expression в cfg::CFG. Здесь CFG означает "граф управления выполнением".
В отличие от ast::Expression, который является глубоко рекурсивным (то есть ast::If практически состоит из трех подузлов ast::Expression), граф управления выполнением в основном плоский. Для радикального упрощения структуры графа управления выполнением он может выглядеть примерно так:
class ЛокальнаяПеременная {};
class Тип {};
class Инструкция {};
class Привязка {
ЛокальнаяПеременная локальная;
Тип тип;
Инструкция инструкция;
}
class BasicBlock {
vector<Привязка> bindings;
ЛокальнаяПеременная finalCond;
Тип finalType;
BasicBlock * whenTrue;
BasicBlock * whenFalse;
}
class CFG {
vector<BasicBlock *> blocks;
}
CFG представляет собой вектор базовых блоков, а каждый базовый блок — это вектор
инструкций, которые вычисляют что-то и присваивают результат локальной переменной.
Ни одна из инструкций в базовом блоке не может выполнять переход (как условный,
так и безусловный). Однако в конце каждого базового блока допускается один
переход. Мы различаем содержимое одной из переменных в базовом блоке как условие
перехода, и затем записываем, какой другой базовый блок следует использовать для
перехода в зависимости от значения этой переменной (whenTrue при истинном значении,
whenFalse при ложном значении).Снова, структура выше является значительно сокращённой; для более подробной информации
посмотрите на cfg/CFG.h и cfg/Instruction.h.
Обратите внимание, что хотя базовым блокам запрещены внутренние переходы, они всё ещё могут "перескочить" путём вызова других методов.
Некоторые различия между CFG Sorbet и другими CFG, с которыми вы можете быть знакомы:
В Ruby почти каждая инструкция может raise внутри begin ... rescue и перейти к началу блока rescue,
прежде чем последующие выражения в блоке begin будут выполнены. Но в Sorbet мы предполагаем, что переход
к блоку rescue происходит либо сразу после входа в begin, либо после выполнения всех выражений в begin.
Это упрощающее предположение (никогда ничего не было выполнено или всё уже выполнено) практически достаточно для моделирования
контекста чувствительности к управлению потоком типизации переменных внутри блока rescue.
Наш CFG не использует однократное назначение (Single Static Assignment, SSA),
поскольку нам не требовалась мощность, которую предоставляет SSA. Вместо этого мы в основном ограничиваемся тем,
что "фиксируем" переменные во внешних областях на определённый тип, и говорим, что присваивания
этим переменным в вложенных областях (например, внутри цикла или условия) не должны менять тип переменной.Использование CFG для типификации в Sorbet довольно круто. Выполняя типификацию на
CFG и внимательно следя за местоположением файлов (см. core::Loc), алгоритм типификации Sorbet может быть очень общим.
Мы только реализуем типификацию для ~11 видов инструкций (+ управления потоком) вместо всех ~98
видов узлов в parser::Node или всех ~34 видов узлов в ast::Expression. Это также делает проще реализацию анализа мертвого кода и типизации с чувствительностью к контексту. И поскольку базовые блоки не могут прыгать в базовые блоки из другого метода, тела методов можно проверять на соответствие типам независимо от других методов.Примечание: если у вас установлен graphviz, вы можете преобразовать CFG в изображение:
tools/scripts/cfg-view.sh -e 'while true; puts 42; end'
Некоторые заметки о том, как читать эти данные:
true; тонкие стрелки — ветвь false;Infer является последним этапом. Он работает напрямую с объектом типа cfg::CFG. В частности, когда создается CFG, каждое связывание имеет nullptr его локального типа. К концу процесса инференса достижимые связывания внутри базовых блоков будут иметь свои типы аннотированы результатами инференса.
Инференс сам по себе просто выполняет итерацию по лучшей попытке топологической сортировки базовых блоков. ("Лучшая попытка", потому что могут существовать циклы в базовых блоках). Для каждого связывания в каждом базовом блоке мы
processBinding, которое представляет собой большой typecase над каждым типом cfg::Instruction.Сложнейшим аспектом инференса являются проверки инструкций cfg::Send (вызовы методов). Проверка того, хорошо ли типирован вызов метода, и определение того, какой тип возврата должен быть, реализованы в core/types/calls.cc.
Sorbet посещает каждое связывание максимум один раз для принятия решения о его типе. Отсутствует обратное решение для типов или итерация до точки покоя, и нет шага генерации ограничений плюс унификации. Этот одиночный стиль инференса быстрее, потому что мы принимаем одно решение о типировании на каждую инструкцию, но он ограничивает возможности инференса Sorbet в явном виде для пользователя. Также, поскольку CFG может содержать циклы, требуется, чтобы внутри цикла базовых блоков тип переменной не мог расширяться или меняться. (Смотрите http://srb.help/7001). Процесс вывода сам по себе в основном состоит из прохождения конфигурационного графа (CFG) для каждого метода и обработки связей. Он делегирует большую часть реализации системы типов (например, получение типа результата метода, проверка типов аргументов, субтипизация, шаблоны и т. д.) логике, реализованной в core/types/. Ниже приведено обсуждение того, как работает система типов Sorbet.## Ядро
Основные абстракции внутри Sorbet.
Refы (т.е., Symbol против SymbolRef)Sorbet довольно быстрый. Есть несколько причин этому, но одной из них является использование Refов в Sorbet. Ref (с большой буквы R) в Sorbet представляет собой способ уникально идентифицировать выделенный объект.
Например, в Sorbet существует класс Symbol и другой класс SymbolRef. SymbolRef концептуально является новым типом обёртки вокруг указателя на Symbol. Все SymbolRef, указывающие на один и тот же Symbol, равны друг другу, поэтому сравнение можно выполнить быстро. Symbol хранятся в GlobalState, так что всегда можно получить данные для SymbolRef для поиска полей Symbol.
Существуют несколько таких пар данных: Symbol/SymbolRef, Name/NameRef, и File/FileRef являются наиболее распространенными.
Почему не использовать просто указатели? Refы обычно меньше по размеру, чем 8-битовый указатель. Также приятно иметь различие, усиленное в системе типов. Кроме того, операция "dereference" этих типов записывается как foo.data*(), вместо *foo или foo->. Sorbet следует философии, согласно которой медленные операции должны быть длиннее для набора.
Мы используем различные методы .enterFoo на GlobalState для создания новых объектов, управляемых непосредственно GlobalState. Эти методы возвращают FooRef. Эти объекты нельзя создать никаким другим образом.Кроме того, типы SymbolRef, NameRef и FileRef по умолчанию могут быть null. Любой такой Ref может не существовать (можно проверить с помощью метода .exists()).
SymbolыSymbolы являются каноническими хранилищами семантической информации о определениях. Они содержат типы, родителей, вид определения, места, где определения были созданы, и т.д. Большая часть работы пассов Namer и Resolver заключается в заполнении GlobalState точными Symbolами, представляющими каждое определение в программе на Ruby.
Symbolы затем используются последующими пассами для выполнения интересных действий, главным образом для отчета об ошибках проверки типов. Symbolы являются полиморфными в некоторой степени. Есть один класс Symbol, но объект типа Symbol может представлять класс, метод, поле, аргумент и т.д. Происходит упаковка битов для представления всех этих вещей с минимальной нагрузкой, поэтому важно использовать публичные методы Symbol, которые подтверждают, что операции, выполняемые над Symbol, имеют смысл для данного типа Symbol.
Дополнительную информацию можно найти в файлах core/Symbols.h и core/SymbolRef.h.
Эти вещи пока находятся вне основного потока работы и требуют более четкого местоположения.###
Имена
ast::Выражение (также известное как Деревья)Глобальное_состояние + карта деревьев вместо явной рекурсии
cast_tree вернёт nullptr, если передан nullptr. Если вы ожидаете, что объект, который вы пытаетесь преобразовать, не является null, ПОДТВЕРДЬте это!typecase
core::Локация
началоОшибки и уровни строгости- Мы используем startOfError, который сначала проверяет, будет ли эта ошибка явно показана.Возвращает сборщик, чтобы избежать дорогостоящего построения сообщения об ошибке, если мы даже не собираемся отчитываться об этой ошибке на текущем уровне строгости файла.### Система типов
Документация системы типов из файла core/Types.h
T.self_type представляет собой тип возвращаемого значения метода Объект.dup, концептуально
lub → 'или'
glb → 'и'
Внутренний: вычисление результата типа метода как функции на C++, а не через статическое объявление его типа с помощью сигнатур.
Базовые типы против прокси-типов (диссертация Дмитрия 2.4)
Зависимые объектные типы (диссертация)
Настройте переход к определению в вашем редакторе (это возможно)
Используйте sorbet -p и https://sorbet.run широко
Используйте lldb, чтобы остановиться на конкретных функциях и шагнуть через логику на малых примерах
Дополните этот документ о том, что вы узнали о C++
sanityCheck и ENFORCE
sanityCheck: внутренний контроль целостности, выполняется в заранее определённые моменты времени (например, "после дессугара")ENFORCE: встроенные утверждения (до / после выполнения условия)show против toString
show: "что-то, что можно показать пользователю" (как Rust Display трейт)toString: "внутреннее представление" (как Rust Debug трейт)gems/sorbet/ (srb init)
gems/sorbet-runtime/
bazel build //foo --copt=-ftime-trace --spawn_strategy=local
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )