#compiler и #story

Как написать свой компилятор? ⚙️🛠

По моему мнению, лучший туториал по созданию компилятора своего языка на C++: My First Language Frontend

Теория и практика написания компиляторов - это целый мир, который развивается уже несколько десятилетий. Энтузиасты создают свои разнообразные языки программирования (интересный список), часто в одиночку.

В туториале рассматривается, как написать компилятор для простого тьюринг-полного языка, на котором возможны такие программы:

# Compute the x'th fibonacci number.
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

# This expression will compute the 40th number.
fib(40)

По очереди разбираются типичные вопросы и pipeline:
(1) Лексический анализ - перевод исходного кода в лексемы
(2) Синтаксический анализ - перевод лексем в AST: абстрактное синтаксическое дерево (написание несложного LL(1)-анализатора языка)
(3) Кодогенерация - перевод AST в промежуточное представление LLVM IR; на этом этапе можно узнать теорию о SSA и графе потока управления
(4) Оптимизация кода - включение нескольких оптимизаторов (список оптимизаторов тут) и теория по ним
(5) Компиляция кода в объектный файл
(6) ... и по желанию многие другие вопросы: debug-символы, типы, управление памятью, стандартная библиотека...

В компиляторе языка C++ все вышеописанные куски имеют ультимативную сложность (и всякие нестандартные пункты как стадия препроцессора 🤯), но на примере простого языка можно разобраться, как работает компилятор и даже как создать свой.

Мне больше всего понравилась возможность слинковать код на другом языке с кодом на C++: сделал небольшое описание на github.

#creepy

Можно ли рекурсивно вызывать метод main()? 🔄

(минутка бесполезной информации)

Когда-то давно я читал набор вопросов к собеседованию по C++, и там встретился такой: "можно ли вызывать метод main() из программы"?

int main() {
    int n;
    std::cin >> n;
    if (n != 0) {
        return main();
    }
    return 0;
}

Казалось бы, зачем так делать почему бы нельзя было так сделать?

Во всех известных мне окружениях функция main() в действительности не является точкой входа - сначала вызывается функция, сгенерированная компилятором, которая проинициализирует глобальные переменные. А сам main() ничем не отличается от других функций.

Linkage функции main() является implementation-defined (ссылка на стандарт): обычно имя функции не манглится. Также написано, что main() не должен вызываться в программе.

Стандарт говорит, что рекурсивный вызов main() запрещен (ссылка на стандарт).

Однако все современные компиляторы успешно компилируют такой код! Они могут выводить warning, если компилировать с опцией -Wmain: ссылка на godbolt.

Поэтому ответ на вопрос такой - рекурсивно вызывать main() нельзя, но компилятор будет компилировать это, если не указывать специальные флаги как -Wmain или -pedantic.

#books

Обзор книги "C++20: Get the Details" 📚

(можно скачать тут - https://www.tgoop.com/progbook/6082)

Стандарт C++11 по количеству и влиянию нововведений был революционным для языка, он сделал C++ фактически новым языком.

Стандарт C++20 - самый влиятельный после C++11, с кучей новых вещей.

В книге на 530 (!) страниц описываются нововведения, то есть "дифф" между C++17 и C++20. Несмотря на размер книги, воды там нет 🚱 Все написано по делу, прилагаются самые подробные объяснения и примеры кода.

Чувствуется, что в книгу вложено огромное количество труда. Почти все вещи объяснены лучше, чем "в интернете" (на cppreference.com и подобных сайтах). Для "больших" нововведений описываются предпосылки и другая редкая информация.

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

#advice

"Это как std::vector, но на 20% круче" 🕶

Часто приходится иметь дело с множеством объектов, и также как-то их переупорядочивать, находить в них объект по ключу, и так далее - в зависимости от бизнес-сценария.

Пусть у нас есть объекты класса Meal (блюда ресторана 🍝), тогда обычно несколько блюд представляют так:

std::vector<Meal> meals;

И также где-то находятся методы, которые делают то, что нужно

void SortAlphabetically(std::vector<Meal>& meals);
void SortByCostDesc(std::vector<Meal>& meals);
const Meal* FindMealById(const std::vector<Meal>& meals, std::string_view id);

Это подход уменьшает читабельность кода, потому что множество объектов живет как бы в отрыве от своих методов.

Я несколько раз успешно применял подход - унаследоваться от std::vector и определить там все нужные методы. Получается примерно так:

class MealList : public std::vector<Meal> {
public:
    static MealList ParseFromJson(const nlohmann::json& json);

    void SortAlphabetically();
    void SortByCostDesc();
    const Meal* FindMealById(std::string_view id) const;

private:
    MealList() = default;  
};

И определения методов находятся в соответствующем .cpp-файле.

MealList держит все методы "при себе" и при этом сохраняет всю остальную семантику std::vector (например, возможность range-based for loop).

#story #retro

Путь Александра Степанова - автора STL в C++ 🔆

Для современных детей смартфоны существовали всегда, и кнопочные телефоны - это что-то древнее и не стоящее внимания, а проводные телефоны - и вовсе атрибут фильмов про СССР.

Так же для программистов, которые начали свой путь 10-15 лет назад, STL существовал всегда. Однако STL имеет интересную историю.

Я наткнулся на страницу в Википедии про Александра Степанова - автора STL и прочитал ее, много интервью с ним, и некоторые его книги. Коллекция этих материалов есть на stepanovpapers.com.

У Александра, на мой взгляд, биография начинается крайне необычно:
⬛️ Родился в 1950 году в Москве
⬛️ В 1972 году закончил мехмат МГУ
⬛️ С 1972 по 1976 год работал программистом (разработка мини-компьютера для управления гидроэлектростанциями)
⬛️ В 1977 году эмигрировал в США

Я слабо представляю себе, сколько в 1972 (!) году в мире было полноценных программистов, которые реально писали свои дебаггеры, линкеры, операционные системы реального времени. Наверное, в то время это были единичные специалисты.

Также мне было интересно, каким образом можно было эмигрировать из СССР в США в 1977 году с таким важным бэкграундом, учитывая истории про необычные побеги в те годы. К сожалению, ни в одном интервью этот вопрос не затрагивается 🙁 Лишь какие-то избитые фразы как в интервью 2003 года:

Я покинул СССР, потому что не любил советскую власть, а Microsoft - это советская власть в программировании.

Однако вернемся к интервью и книгам. Любое интервью будет интересным, потому что раскрывает какие-то малоизвестные факты. Александр вообще создатель обобщенного программирования как такового, до C++ он реализовал этот подход в языках Scheme и Ada.

Можно почитать это интервью - там присутствуют приколы, например вопрос «расшифровывается ли STL как "Stepanov and Lee"?»; а также факт, что первые идеи про обобщенное программирование пришли Александру в 1976 году в полубессознательном состоянии, когда он находился в больнице с пищевым отравлением.
Также в интервью Александр высказывает мнение о ненужности ООП и Java (определенный как money oriented programming (MOP))

Из книг мне больше понравился Notes for the Programming course at Adobe 2005-2006.
На первых страницах Александр описывает, как он в 1972-1976 годах сам себя научил принципам хорошего кода.
Сначала он писал проект (например, дебаггер), через несколько месяцев переписывал его с нуля с знанием всех ошибок дизайна, затем это повторялось, и так далее.
Затем он писал проекты не как попало, а с учетом принципов (размер функции не более 20 строк, выделение общего кода в общие функции и т.д.). Этот эксперимент был крайне удачным и упростил разработку.

Александр заметил, что чем больше программа, тем меньше у нее application-specific (или non-general) кода и больше general кода.
В современных десктопных приложениях содержание non-general кода намного меньше чем 1%. Сейчас это самоочевидно, если посмотреть на объем кода операционной системы и Qt/WinForms. Но в то время это было далеко не так очевидно, потому что разработка велась очень близко к "железу".

Сейчас обобщенное программирование - обычное дело, но в те времена это было довольно контркультурное движение. Оно не соответствует концепции "top-down design", потому что это утверждение о том, что можно хорошо спроектировать какой-то компонент без особых знаний о том, как этот компонент будет использоваться 🤔

Из упомянутой выше книги можно прочитать первые несколько глав - там находится очень редкая информация о том, как правильно дизайнить обобщенные классы (как std::vector), и о том, как должны были бы выглядеть разные места C++ с точки зрения Александра (но Страуструп запретил). Потом в книге начинается переизобретение std::move (книга 2006 года), и это читать не имеет смысла.

#story #carbon

Язык Carbon как наследник С++ - о чем молчат его авторы? 🕵️

Многие уже слышали о языке Carbon, который Google представляет как "наследник C++". Всего лишь за несколько дней туда уже наставили 16k лайков.

О нем можно рассказать с трех точек зрения: (1) почему его делают, (2) что в нем планируется, (3) что может быть дальше.

🤔 Почему его делают?
По словам авторов, основной проблемой C++ является огромная сложность внесения в него изменений.

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

Окончательный баттхерт произошел в феврале 2020 года, когда комитет отказался ломать ABI (подробнее об этом можно почитать тут), тогда стало ясно что C++ продолжит развиваться черепашьим темпом, и Google стал подпольно создавать свой C++ 2.0

🤔 Что в нем планируется?
Самое главное - то, что C++ и Carbon могут подключать хидеры друг друга, то есть в наличии двунаправленная совместимость языков (как между Java и Kotlin). Я подозреваю, что это сделано через патч в Clang, который при виде файла с нужным расширением по-нужному парсит его в промежуточное представление, а дальше всё вместе оптимизируется.

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

(*) около языка: менеджер пакетов, сильная стандартная библиотека (если там будет как в Python, то я балдю бом бом), быстрый процесс "стандартизации", и прочее...

(*) сам язык: pattern matching (как в Rust), рефлексия (пока доки нет, но будет), traits (тоже как в Rust), работа с типами, в будущем memory safety, и прочее...

(*) полно мелочей: адекватная иерархия наследования, классы final по умолчанию, проверка на NRVO, и прочее...

🤔 Что может быть дальше?

Здесь я опишу факты, в которых я +- уверен, а выводы на их основе можно сделать самому 👻

(1) У Google есть гигантский админресурс, чтобы продвинуть любой нужный партии язык в массы - реклама на C++-конвенциях, массовый выпуск курсов (например на Coursera), обучение в вузах...

Так что при желании язык можно продвигать "нерыночными" способами (вряд ли Go выстрелил бы сам в "дикой природе").

(2) У Google есть технический ресурс, чтобы создать C++ 2.0 и не сильно обоср*ться, потому что многие очень активные контрибьюторы в Clang и в Стандарт C++ работают в Google.

(3) Самое печальное: "Экономика" развития C++ и Carbon будет кардинально отличаться.

Дело в том, что если в C++ контрибьютят в основном "подвижники", крайне заинтересованные в основном нематериально люди, то Carbon разрабатывается корпорацией.

При работе в FAANG (и в десятках компаний под них косящих) важно не то, как ты делаешь, а что ты делаешь.
Повышение при прочих равных получает обычно не чувак, который круто знает C++, хорошо делает задачи и покрывает тестами, а тот, кто выкатил какую-нибудь хрень с высоким visibility и показал красивые графики. И обычно всем пофигу что там нет тестов или код говно - выкатилось, ну и хорошо.

Поэтому есть риск, что из-за личных планов "выкатить что-то крутое, показать манагеру, и пойти на повышение" Carbon может проэволюционировать в какое-то болото.

#retro #books #compiler

Обзор книги "Компилятор языка Си для микроЭВМ" (1989 г.) 📚

Эта книга - перевод на русский язык "The Small-C Handbook" 1984 года.

Я прочитал эту книгу, чтобы понять, как сильно изменились компиляторы за многие годы. Книга имеет историческую ценность как окно в реалии разработки 30-40 лет назад.

Как "микроЭВМ" рассматривается популярный тогда микропроцессор Intel 8080. Он имеет 8-разрядную архитектуру, семь 8-битных регистров, и 16-разрядную адресацию памяти (что дает адресацию 64 Кбайт = 65 536 байт памяти).

В странах Организации Варшавского Договора многие технологии копировались. Функциональным аналогом Intel 8080 была микросхема КР580ВМ80А, разработанная Киевским НИИ микроприборов, поэтому советские программисты могли успешно читать книги про Intel 8080.

Микропроцессор - вещь полезная, ее можно использовать в компьютерах, светофорах, принтерах, игровых автоматах, синтезаторах, измерительных приборах...

Под "Small C" понимается подмножество языка Си, которое самописный компилятор может скомпилировать. Small C слабо отличается от "полного" Си.
Доступны все основные конструкции, но например типов всего два - char (1 байт) и int (2 байта). Intel 8080 в базовой комплектации не умел работать с float-числами, для них нужен отдельный сопроцессор Intel 8231/8232.

Книга состоит из нескольких частей.
В ч.1 описан микропроцессор 8080, система его команд, обзор ассемблеров, загрузчиков и компоновщиков программ. Базовые вещи за несколько десятилетий не изменились.
В ч.2 описан язык Small C, который как по мне почти ничем не отличается от "полного" C.
В ч.3 самое интересное - описывается компилятор и все что с ним связано, как разные конструкции должны выглядеть в ассемблере, всякие мелочи (кросскомпиляция, etc.).

Прямо в книге приводится исходник компилятора - портянка на половину книги. Я нашел эти исходники на гитхабе, лучше смотреть там (файлы от cc.def до cc42.c).

Какие есть особенности у компиляторов того времени / такого типа:

🚀 Всего за ~3000 строк кода можно сделать свой компилятор Си на коленке, кому не лень. А сейчас LLVM занимает не меньше 11mln строк кода на C/C++.
Когда технология простая, то каждый может ее скопировать/сделать, но с развитием технологии выживают всего несколько реализаций.
Компиляторы C/C++, веб-браузеры, операционные системы - раньше их было значительно больше, но сейчас это единичные программы.

🚀 Компилятор однопроходный - парсит файл один раз сверху вниз. Компиляция очень быстрая.
Компилятор языка C++ уже не может быть однопроходным. Например, из-за шаблонов или constexpr-кода. Самый простой пример - парсинг класса: сначала парсятся сигнатуры всех методов и полей, только потом тела методов.

class TSomeClass {
public:
    int GetValue() const {
        return Value_; // C++ "видит" Value_, хотя он определен "позже"
    }
private:
    int Value_;
};

🚀 Нет никаких оптимизаций кода (кроме самых элементарных как сжатия выражения 2+3 в константу 5).
В книге есть глава о том, как писать "оптимальный код", там дикие советы наподобии:
🤯 "глобальные переменные лучше локальных"
🤯 "лучше всего сравнивать выражения с константной равной 0"
🤯 "++i лучше чем i++"
Потому что компилятор сгенерирует меньше ассемблерных команд, если им следовать!

🚀 Вместе с предыдущим пунктом - нет промежуточного представления кода (например AST) для анализа - компилятор генерирует ассемблер не отходя от кассы. Например, во время парсинга if-выражения создаются метки и команды условного перехода на метку.

🚀 Есть разнообразные ограничения с расчетом того, что компилятор сам работает на не то чтобы мощной машине.
Например нельзя иметь в файле больше 130 штук #define, названия переменных длиннее 9 символов, больше 200 глобальных переменных...
Сам код изобилует обращениями к глобальным переменным.

#books

Обзор книги "C++ Lambda Story" 📚

(можно посмотреть тут - https://leanpub.com/cpplambda)

Как известно, язык C++ очень простой, всего лишь за 157 страниц можно понять, как работают лямбды в C++ ✨
Перед прочтением можно пересмотреть видеоприкол C++ Lambda Ace Attorney 😃

В книге есть исследование по всей сфере вопроса: как без лямбд обходились до C++11, и как возможности лямбд расширялись от стандарта к стандарту (C++14/17/20).

Изначальная идея лямбд простая - запись

    auto lam = [](double param) { /* do something */ };

...функционально должна работать примерно как

    struct {
        void operator()(double param) const { /* do something */ }
    } lam;

...то есть быть более простой записью для функтора (объект класса с operator()), которые широко использовались в C++98/03.

Все дальнейшие изменения в дизайне лямбд связаны с общим развитием языка, чтобы приспособить к функтору новые фичи.
Книга дает представление, как лямбды выглядят "внутри", поэтому многие рассмотренные вопросы становятся самоочевидными:
🤔 почему capture нужно делать только для автоматических переменных;
🤔 как делать capture для this;
🤔 серьезная разница между лямбдами которые ничего не capture-ят, и которые делают это; и многое другое...

Многое я уже знал заранее (даже лазил в части компилятора, который генерирует лямбды), поэтому мне было интересно, найдутся ли неизвестные мне интересные факты? Оказалось, что такое есть:

🚀 Начиная с C++20 можно создавать объект лямбды (раньше было нельзя)

auto foo = [](int a, int b) { return a + b; };
decltype(foo) bar;
// ^ (до C++20) error: no matching constructor for initialization of 'decltype(foo)'

это нужно для передачи типа лямбды, например как параметра в std::set - пример на godbolt

🚀 Начиная с C++17 можно использовать std::invoke для улучшения читабельности в немедленных вызовах лямбд:

auto v1 = [&]{ /* .../ }();
auto v2 = std::invoke([&]{ /* .../ });

пример на godbolt

🚀 Если лямбда ничего не capture-ит, то она может быть сконвертирована в указатель на функцию.
Если написать + перед лямбдой, то мы получим указатель на функцию, а не объект лямбды (потому что + можно применять на указатель, а на объект лямбды нельзя).
Это самый простой способ без static_cast-ов. Тред на stackoverflow.

🚀 От лямбды (точнее от ее класса) можно унаследоваться разными способами.
В таком случае получившийся класс будет представлять из себя класс с несколькими operator()(...) (с разными аргументами). Есть несколько паттернов, где это применимо, но выглядит это довольно жутко и редко где нужно.
Например, есть такой паттерн из доки для std::visit:

std::visit(overloaded{
    [](A a) { std::cout << a.name << std::endl; },
    [](B b) { std::cout << b.type << std::endl; },
    [](C c) { std::cout << c.age << std::endl; }
}, something);

Остальные "приколы" меня не очень удивили: лямбды в контейнере, особенности лямбд в многопоточке, capture объекта [*this], шаблонные лямбды... Они выглядели самоочевидными, но кому-то может быть интересным 🙂

#compiler #cringe

Колхозное компиляторостроение 🌾🚜🐄

Мсье PG выложил критический пост про "компилятор Python в C++" с реддита.

Не стоит заниматься такими вещами, как компилирование (точнее, транслирование) Python в C++, потому что это совершенно разные языки.
При всем желании перевести получится только базовый минимум языка, без кода как val = 1; val = 'hello' (где меняется тип переменной).
Но это мелочи - посмотрим, чем является компилятор.

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

Там используется встроенный лексер питона (библиотека tokenize), чтобы получить лексемы (токены), а потом по этим токенам итерируются один за другим и просто транслируют слово на Python в слово на C++: compiler.py.
Таким образом малореально "скомпилировать" более-менее сложную программу на Python, транслятор очень негибкий.

Для таких задач лучше подходит встроенный лексер+парсер питона (библиотека ast).
Для AST используется идиома "visitor": можно "посещать" ноды дерева и генерировать код. Почти все тулзы для исходного кода (в том числе для трансляции кода) используют визиторы.
Примерно в таком стиле может выглядеть транслятор кода - gist.github.com

C++ по задумке нужен как "промежуточное представление", чтобы в конечном счете из Python получить оптимизированный бинарник.
Это тоже неудачная идея - лучше переводить Python в LLVM IR, потому что он более универсальный чем C++.
По запросу python llvm находятся какие-то проекты на эту тему.

В целом переводить Python "для оптимизации" в какое-то другое представление не имеет смысла - многие Python-библиотеки написаны на C/C++ и из Python у них только наружный интерфейс.

#library

Классическая механика на C++ - обзор движка Box2D 🚀

Box2D это физический движок, используется в основном в играх. Игры с Box2D можно посмотреть на YouTube. Самой популярной игрой является, наверное, Angry Birds.

Box2D рассчитывает физику абсолютно твердых тел, то есть в нем нельзя эмулировать движение жидкостей или делать игры наподобии Worms.

✏️ "Фигура" в Box2D это круг, многоугольник (не больше 8 углов), или отрезок.
✏️ "Тело" состоит из 1+ фигур, можно придать свою плотность, коэффициент трения и упругость.
✏️ Телу можно придавать "ограничения", например запрещать вращение или движение по оси X/Y.
✏️ Между телами могут быть "связи", которые будут держать тела вместе, разных типов.
✏️ У "связей" также могут быть разные ограничения, например в эмуляции человеческого локтя ограничен возможный угол между частями руки.
✏️ "Мир" содержит в себе эти объекты и управляет памятью и эмуляцией движения.
✏️ В любой момент можно добавлять/удалять тела, применять силу, вращение, импульс... Также можно проверять коллизии тел, делать raycast, вычислять расстояние между телами и многое другое.

Эти понятия можно комбинировать в самые сложные конфигурации - пример транспорта на YouTube.

Константа time step определяет, сколько времени "прошло" с предыдущего перерасчета мира. Обычно мир пересчитывают 60 раз в секунду (time step = 1.0f / 60.0f).

В алгоритмах используется простая математика. Из старших классов школы - вычисление нормалей, матрицы вращения, произведение векторов, тригонометрия. Из первого курса вуза - метод Эйлера.

Box2D можно сбилдить всего за 5 секунд, даже вместе с тестовым приложением.
Он написан на суржике C и C++: не используются namespace, константы через enum, есть самодельные списки объектов и т.д.
Например, если объект должен находиться в списке, то указатель на следующий объект списка находится прямо в классе, а не "снаружи":

for (b2Body* b = myWorld->GetBodyList(); b; b = b->GetNext())
    b->... // do something with the body

В Box2D используется реализация двух популярных типов аллокаторов:
💾 Аллокатор маленьких объектов (b2BlockAllocator) - вместо того, чтобы постоянно вызывать malloc/free для маленьких объектов, этот аллокатор сразу запрашивает 16kb памяти и создает объекты там (пока есть место).
💾 Аллокатор на стеке (b2StackAllocator) - на стеке лежит 100kb памяти, объекты создаются там.
Это позволяет во время "перерасчета мира" обходиться без аллокаций памяти.

Все объекты нужно создавать через "мир" (b2World):
b2Body* b = myWorld->CreateBody(&bodyDef);
Удалять тоже нужно через "мир", хотя деструктор b2World::~b2World() очистит всё что не удалено вручную.

⏱ Движок использует разные техники, чтобы быстрее делать перерасчет мира.
Если перемещение (угол/импульс/...) объектов считается быстро, то для быстрого расчета коллизий нужно использовать структуры данных.
Можно подробно почитать об этой проблеме на wikipedia. Целью оптимизаций является получение алгоритма за O(N) вместо O(N^2), где N-количество объектов.
Box2D использует "динамическое дерево" (b2DynamicTree) - весь мир делится на две части, каждая часть тоже делится на две, и так далее.

🐷 Можно на примере свинок из Angry Birds придумать игровую логику.
Если вы играли в Angry Birds, то помните, что свинки довольно хрупкие, но они могут остаться в живых (потеряв "здоровье"), если упадут с небольшой высоты, или на них упадет некрупная балка.
Мерой урона для свинки может считаться импульс коллизии с другим предметом.

strength = M_свинка * V_свинка + M_предмет * V_предмет

Можно итерироваться по всем "контактам" между телами, чтобы поймать начало коллизии:

for (b2Contact* contact = world->GetContactList(); contact; contact = contact->GetNext())
    contact->... //do something with the contact

Но это неэффективно и некрасиво. Лучше использовать коллбек на коллизию через b2ContactListener

#compiler

[Часть 1/2]
Как работает статический анализ кода? Обзор clang-tidy 🧹🧹🧹

clang-tidy нужен, чтобы поправлять исходники C++ (или хотя бы выводить warning-и). В других языках такой инструмент называется "linter" и часто встроен в сам язык и/или стандартизирован (например PEP8 в Python).

clang-tidy умеет диагностировать разные баги, устаревший код, подозрительные паттерны кода. Возможных проверок очень много (список). Например, проверка на неэффективный push_back в векторе: ссылка. На своем коде можно исполнять любые проверки.

Несмотря на то, что проверок уже почти 300 штук, все равно можно придумать идею для своих проверок.

✏️ Описание проверки
Я придумал свою проверку. Как до C++17 объявлялись константные переменные? По-правильному примерно так:

// в .h-файле:
extern const std::string DVCC_DVVC_BLOCK_TYPE_NAME;
// в .cpp-файле:
const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

Вообще можно в .h-файле определить константную переменную, и это скомпилируется, но будет плохо, потому что const-переменные по умолчанию static. Это значит что каждый .cpp-файл будет иметь дело с локальной копией одной и той же переменной 👻

// так плохо! в .h-файле:
const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

Начиная с C++17 можно записывать значения подобных переменных не отходя от кассы:

// в .h-файле
inline const std::string DVCC_DVVC_BLOCK_TYPE_NAME = "Dolby Vision configuration";

И вот моя проверка должна находить первые два плохие случая и предлагать писать по-новому, как в третьем случае.

✏️ Как это работает в коде
Я это сделал в феврале (тут pull request), но до прода не дотащил, так как ревью медленно проходит (примерно раз в три месяца).

Посмотрим по коду, как эта вещь работает ⚙️ Сначала надо ограничить возможные языки - нужен C++17 или выше:

  bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
    return LangOpts.CPlusPlus17;
  }

Clang переводит исходники в AST (Absract Syntax Tree). Проверки работают исключительно на AST Matchers - это конструкция для нахождения нужных нод дерева. AST Matchers пишутся легко, но из-за сложности стандарта они постоянно патчатся, чтобы покрыть крайние случаи 🐸

Надо придумать и "зарегистрировать" AST Matcher для интересующих нас нод. Это должны быть объявления переменных, причем глобальные константные не-inline переменные на уровне файла (т.е. не внутри класса).

Достаточно ли этого? Нет... Если посмотреть Стандарт, то окажется, что из рассмотрения нужно выкинуть переменные внутри анонимного namespace (их точно бесполезно исправлять), шаблонные переменные (они неявно inline), volatile переменные (тут не помню почему), а также переменные внутри extern "C" на всякий случай:

  auto NonInlineConstVarDecl =
      varDecl(hasGlobalStorage(),
              hasDeclContext(anyOf(translationUnitDecl(),
                                   namespaceDecl())), // is at file scope
              hasType(isConstQualified()),            // const-qualified
              unless(anyOf(
                  isInAnonymousNamespace(), // not within an anonymous namespace
                  isTemplateVariable(),     // non-template
                  isInline(),               // non-inline
                  hasType(isVolatileQualified()), // non-volatile
                  isExternC()                     // not "extern C" variable
                  )));

Регистрируем матчер для поиска extern объявлений (AST Matchers можно смешивать):

    Finder->addMatcher(varDecl(NonInlineConstVarDecl, isExternallyVisible())
                           .bind("extern-var-declaration"),
                       this);

Регистрируем матчер для поиска не-inline определений:

    Finder->addMatcher(varDecl(NonInlineConstVarDecl, isDefinition(),
                               unless(isExternallyVisible()))
                           .bind("non-inline-var-definition"),
                       this);

#compiler

[Часть 2/2]
Как работает статический анализ кода? Обзор clang-tidy 🧹🧹🧹

В коде, который реагирует на найденную ноду, нужно определить текст warning-a:

  const VarDecl *D = nullptr;
  StringRef Msg;
  bool InsertInlineKeyword = false;

  if ((D = Result.Nodes.getNodeAs<VarDecl>("non-inline-var-definition"))) {
    Msg = "global constant %0 should be marked as 'inline'";
    InsertInlineKeyword = true;
  } else {
    D = Result.Nodes.getNodeAs<VarDecl>("extern-var-declaration");
    Msg = "global constant %0 should be converted to C++17 'inline variable'";
  }

Если мы увидели, что переменная объявлена не в хидере, то ничего не делаем, возвращаем из функции (на уровне AST Matchers это пока нельзя ловить).

Теперь можно вывести красивый warning в месте объявления переменной.
Если у нас случай с определением не-inline переменной, то заодно можно поправить исходник, приписав "inline " перед объявлением переменной (во время работы clang-tidy поправит исходник):

  DiagnosticBuilder Diag = diag(D->getLocation(), Msg) << D;
  if (InsertInlineKeyword)
    Diag << FixItHint::CreateInsertion(D->getBeginLoc(), "inline ");

Теперь вы знаете, как примерно работает статический анализ кода 🙂

#story

Эмуляция физических процессов с использованием численных методов 🌊

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

Сначала физический процесс нужно описать математической моделью. Это теория, которую шаг за шагом проходят в вузах:
📚 Общая теория дифференциальных уравнений и всего что с ними связано (обычно 1-годовой курс в вузе)
📚 Векторный анализ, который впрочем у нас не являлся отдельным предметом, а изучался в рамках математического анализа ближе к концу 1.5-годового курса
📚 От физики обычно берут уже некие давно известные формулы - достаточно несколько месяцев изучать материалы по нужной сфере (гидродинамика/электромагнетизм/...)
📚 Предмет уравнения математической физики комбинируют прошлые шаги и досконально изучают некоторые уравнения за 0.5-годовой курс.

Как выглядят одни из простейших уравнений (без "источников тепла" и пр. влияний):
🔬 Уравнение теплопроводности (там есть гифка с симуляцией)
🔬 Волновое уравнение (симуляция на ютубе)

Что вообще нужно для компьютерной симуляции физического явления, кроме математической модели?
Моделирование происходит на конечной области (по пространству и по времени), поэтому нужны правильно заданные начальные и/или граничные условия - то есть состояние в области в момент t = 0 и, возможно, состояние на границах области в каждый момент t.

Этого достаточно для симуляции - то есть компьютеру не нужно искать аналитическое решение математической модели.
В некоторых случаях это даже невозможно сделать - до сих пор не найдено аналитическое решение уравнений Навье-Стокса (для симуляции жидкости)!

Область симулируемого явления представляется в виде сетки.
Представим, что мы в двухмерной модели имеем область NxM сантиметров. Тогда нам нужно выбрать "шаг" h см, так чтобы мы получили массив из (N/h)x(M/h) точек.
Теперь все функции модели дискретизируются, то есть вычисляются в данных точках.

Это нужно по простой причине - теперь производные можно вычислять на базе соседних точек. Вот что можно подставить вместо f'(x), т.е. производной от f(x):

(f(x+h) - f(x-h)) / 2h

а так можно представить производную второго порядка f''(x):

(f(x + h) - 2f(x) + f(x-h)) / 4h^2

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

Многие симуляции хорошо распараллеливаются, приводятся к матричному виду, и могут успешно вычисляться на суперкомпьютерах или на GPU - это еще один скилл, которым нужно овладеть 📚

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

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

Бонус: симуляция аэродинамики разных предметов на ютубе 🎥

#madskillz

Итераторы с неопределенным концом 🏁

Итераторы это одна из главных концепций C++. У каждого класса контейнера (set/vector/list/...) в C++ есть свой соответствующий класс итератора (для доступа к своим данным).

Класс, для которого определен итератор, должен иметь методы begin() и end(), по вызову которых отдаются объекты итератора.
Класс итератора должен иметь методы operator++() и operator*().
Наличия этих методов достаточно для использования итератора в разных стандартных методах и в range-based for loop.

Обычно итераторы итерируются по всем объектам от begin() до end():

    const std::vector<int> vec{1, 3, 5, 7, 9};
    // внизу аналог выражения `for (int value : vec) { /* ... */ }`
    auto __begin = vec.begin();
    auto __end = vec.end();
    for ( ; __begin != __end; ++__begin) {
        int value = *__begin;
        /* do something with `value`... */
    }

Однако бывают случаи, когда end() нельзя вычислить заранее и нужно делать на каждом шагу проверку, не пора ли выходить из цикла. В стандарте C++20 встречается такой костыль:
1️⃣ Завести пустой мусорный класс std::default_sentinel_t
2️⃣ Метод end() класса-"контейнера" должен отдавать объект мусорного класса

    std::default_sentinel_t end() { 
        return {}; 
    }

(а метод begin() продолжает отдавать объект итератора)
3️⃣ Класс итератора должен определить оператор сравнения с объектом мусорного класса:

    bool operator==(std::default_sentinel_t) const { 
        return /* какое-то условие */; 
    }

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

Какие есть реально используемые use cases:
🎯 std::counted_iterator - обертка над каким-нибудь другим итератором, итерируется по не более чем N элементам
🎯 Поддержка range-based for для корутин - чтобы можно было в цикле забирать новые значения от корутины, пока она активна (класс итератора - class Iter)

#compiler

Как компилятор замеряет скорость компиляции? 🕰

В C++ легко сделать так, чтобы проект собирался очень долго. В моем личном топе - юнит-тест (в виде одного .cpp-файла) компилировался 4.5 минуты.

К счастью, скорость компиляции можно дебажить. Во время компиляции одного файла нужно указать настройку -ftime-trace:

-ftime-trace
    Turn on time profiler. Generates JSON file based on output filename. Results can be analyzed with chrome://tracing or Speedscope App for flamegraph visualization.
-ftime-trace-granularity=<arg>
    Minimum time granularity (in microseconds) traced by time profiler

Команда может выглядеть так:

clang++ main.cpp -c -ftime-trace -ftime-trace-granularity=50

Получившийся json-файл main.json можно визуализовать на 🔬SpeedScope. (На гитхабе есть гифка, как это примерно выглядит)

Что делает компилятор:
⚙️ Перед началом компиляции, если задана настройка -ftime-trace, clang вызовет метод llvm::timeTraceProfilerInitialize.
⚙️ В этом методе проинициализируется объект структуры llvm::TimeTraceProfiler.
⚙️ Когда начинается какое-то событие, нужно вызвать метод llvm::TimeTraceProfiler::begin, чтобы запомнить время начала.
⚙️ Когда событие заканчивается, нужно вызвать метод llvm::TimeTraceProfiler::end, чтобы добавить запись о событии.
⚙️ Как видно по коду, используется стек, потому что события вложены друг в друга (например внутри события "компиляция файла" есть событие "распарсить класс").
⚙️ После компиляции файла вызывается метод llvm::TimeTraceProfiler::write для записи в json-файл.

По умолчанию параметр -ftime-trace-granularity равен 500 (500 микросекунд). Записываются не все события, а только достаточно "долгие", которые длились дольше чем 500μs - участок кода.

В коде нужные методы не вызывают "вручную" - используется стандартная идиома RAII в виде структуры llvm::TimeTraceScope.
Как видно, в момент вызова конструктора "событие начинается", вызова деструктора "событие заканчивается".
(если компиляция вызывалась без флага -ftime-trace, то этот объект не делает ничего)

Можно привести примеры - вот так засекается время на инстанциацию шаблонов (которая происходит после парсинга файла): PerformPendingInstantiations.
Пока происходит инстанциация шаблонов, засекаются всякие "вложенные" события, например InstantiateFunction.

Вот так компилятор нехитрым образом делает нужный flame graph 🙂
По моему опыту наблюдений за скоростью компиляции, "фронтенд" компилятора (парсинг файла в AST) занимает в 3-20 раз больше времени чем "бэкенд" (перевод AST в LLVM IR, оптимизация и перевод в бинарник).
Основная причина этого дисбаланса - огромный объем исходного файла после того, как раскроются все #include (в почти всех современных проектах на C++).

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