Приветствую.
В 1936 году Алан Тьюринг опубликовал статью, которая среди прочего доказала одну неприятную вещь: невозможно написать алгоритм, который для любой программы и любого входа определит, остановится программа или нет. Проблема остановки. Мы натыкаемся на неё гораздо чаще, чем кажется. Иногда прямо в Cargo.toml.
Вот, например, ситуация: вы пишете рекурсивный macro_rules!, запускаете cargo build, и компилятор выдаёт:
error: recursion limit reached while expanding `my_macro!` = help: consider adding a `#![recursion_limit = "256"]` attribute to your crate
Вы добавляете #![recursion_limit = "256"]. Или "512". Или "4096". А потом задумываетесь: а точно ли этот макрос вообще завершится?
Эта статья — про рекурсию в макросах Rust. Про то, как она устроена внутри, какие паттерны существуют, почему компилятор не может автоматически гарантировать завершение, и как на всё это смотреть через призму фиксированных точек и систем переписывания.
Что на самом деле делает компилятор, когда раскрывает макрос
Раскрытие макроса — это функция. Входит TokenStream, выходит TokenStream:
expand(TokenStream) = TokenStream
Компилятор вызывает expand, смотрит на результат. Если в результате опять торчат макровызовы — вызывает expand снова. И снова. Получается цепочка: x, expand(x), expand(expand(x)), expand(expand(expand(x))) — и так далее, пока в очередном результате не останется ни одного макровызова. Тогда — всё, раскрытие завершено, компилятор идёт дальше.
Или пока не пройдёт 128 шагов. Тогда просто ошибочка.
Вот это «или» основная проблема. Компилятор не знает, завершится ли цепочка. Он просто крутит expand в цикле и надеется.
Тут стоит проговорить, чем это отличается от того, что делает препроцессор C. В С — тупая текстовая подстановка. Макрос не знает, что он подставляет: строку, число, половину if-а — ему всё равно. В Rust всё устроено принципиально иначе.
У нас тут есть гигиена. Если внутри макроса вы объявили переменную x, она не перекроет x в вызывающем коде. У каждого идентификатора есть так называемый syntax context, метка, по которой компилятор различает «вот эту x из макроса» и «вон ту x из main». Это не всегда работает идеально!
Все фрагменты типизированы. Когда вы пишете $e:expr, компилятор захватывает целое выражение как AST-узел. Не всё до следующей запятой, а именно выражение со скобками, приоритетами, всем. И подставить его можно только туда, где выражение синтаксически допустимо. Попытка сунуть expr на место типа даст ошибку на этапе раскрытия, а не на этапе парсинга результата.
А еще и scope. Макрос видит контекст того крейта, где он определён, а не того, где вызван (кроме случаев с $crate).
Всё вместе это значит, что раскрытие макросов в Rust — не слепая замена текста, а структурное преобразование синтаксического дерева. Рекурсия в таком преобразовании — штука совершенно естественная.
tt-munching: откусил, обработал, передал дальше
Самый известный рекурсивный паттерн в macro_rules! называется tt-munching. «Munching» — буквально «жевание». Макрос берёт первый токен (или группу токенов), что-то с ним делает, а хвост передаёт сам себе.
macro_rules! count_tts { // пустой вход - ноль токенов, базовый случай () => { 0usize }; // откусываем голову, рекурсивно считаем хвост ($_head:tt $($tail:tt)*) => { 1usize + count_tts!($($tail)*) }; } fn main() { let n = count_tts!(a b c d); assert_eq!(n, 4); }
Как это раскрывается?
count_tts!(a b c d) = 1 + count_tts!(b c d) = 1 + 1 + count_tts!(c d) = 1 + 1 + 1 + count_tts!(d) = 1 + 1 + 1 + 1 + count_tts!() = 1 + 1 + 1 + 1 + 0
На каждом шаге хвост становится короче на один токен. Рекурсия конечна по определению.
Это красивый паттерн, настолько, что хочется использовать его везде!
Но есть подвох: рекурсия линейна. Четыре токена — четыре уровня. Сто токенов — сто. А дефолтный recursion_limit — 128. То есть на 129-м токене вы упираетесь в стену.
Можно откусывать по два:
macro_rules! count_tts_by2 { () => { 0usize }; ($one:tt) => { 1usize }; ($a:tt $b:tt $($tail:tt)*) => { 2usize + count_tts_by2!($($tail)*) }; }
Вдвое меньше уровней. Можно по четыре, по восемь. Но асимптотически это всё равно O(n), просто с меньшим коэффициентом. По-настоящему логарифмический подсчёт через macro_rules! возможен, но требует трюков с вложенными группами скобок, и код перестаёт быть чем-то, что хочется поддерживать. Если вам нужно считать 500 токенов на этапе компиляции, вероятно, вам нужен не macro_rules!.
Push-down accumulation: собираем результат по ходу дела
tt-munching хорош, когда обработка каждого токена независима. Но что, если нужно собрать что-то из всех токенов, перевернуть список, склеить в одно выражение, сгенерировать код, зависящий от всего входа?
Тут появляется аккумулятор. Как в функциональных языках, где рекурсия с аккумулятором — стандартный приём. В macro_rules! аккумулятор — это дополнительная группа токенов в аргументах, которая растёт по мере обработки.
macro_rules! reverse { // всё обработано — отдаём аккумулятор (@rev [] [$($acc:tt)*]) => { ($($acc)*) }; // берём первый токен из входа, запихиваем в начало аккумулятора (@rev [$first:tt $($rest:tt)*] [$($acc:tt)*]) => { reverse!(@rev [$($rest)*] [$first $($acc)*]) }; // точка входа ($($input:tt)*) => { reverse!(@rev [$($input)*] []) }; } fn main() { let tuple = reverse!(1 2 3 4); assert_eq!(tuple, (4, 3, 2, 1)); }
Проследим:
reverse!(1 2 3 4) = reverse!(@rev [1 2 3 4] []) = reverse!(@rev [2 3 4] [1]) = reverse!(@rev [3 4] [2 1]) = reverse!(@rev [4] [3 2 1]) = reverse!(@rev [] [4 3 2 1]) = (4 3 2 1)
Необработанная часть [$first $($rest)*] каждый раз теряет элемент. Аккумулятор [$($acc)*] растёт. Общий объём токенов не уменьшается, но для завершимости это неважно. Считается только убывание входа.
Пара слов про @rev. Символ @ — это просто токен-идентификатор, ничего навороченного. Так помечают internal rules — ветки, которые не предназначены для прямого вызова извне. Можно было бы написать __internal или helper, но @ прижился, такой вот короткий, бросается в глаза, не спутаешь ни с чем.
Этот же механизм — push-down accumulation с internal rules, позволяет строить compile-time конечные автоматы. Состояние — это тег (@state_a, @state_b). Переходы — ветки макроса с рекурсией. На каждом шаге автомат откусывает токен, меняет состояние, и вызывает себя.
Рекурсия для генерации impl
Самый массовый реальный кейс рекурсивных макросов — нагенерировать impl для кортежей.
Задача: есть трейт, и мы хотим реализовать его для (A,), для (A, B), для (A, B, C) — и так далее, с одного макровызова. Repetition ($(...)*) тут не справляется, потому что каждый impl другой длины.
trait TupleSum { fn sum(self) -> i64; } macro_rules! impl_tuple_sum { // базовый случай: один элемент ($T:ident) => { impl TupleSum for ($T,) { fn sum(self) -> i64 { self.0 as i64 } } }; // рекурсивный: сначала генерируем для хвоста, // потом для полного списка ($Head:ident $($Tail:ident)+) => { impl_tuple_sum!($($Tail)+); impl TupleSum for ($Head, $($Tail),+) { fn sum(self) -> i64 { let ($Head, $($Tail),+) = self; $Head as i64 $(+ $Tail as i64)+ } } }; } // одним вызовом — четыре impl'а impl_tuple_sum!(A B C D); fn main() { assert_eq!((1i32, 2i32, 3i32).sum(), 6); assert_eq!((10i32,).sum(), 10); }
Вызов impl_tuple_sum!(A B C D) рекурсивно порождает impl_tuple_sum!(B C D), тот — impl_tuple_sum!(C D), тот — impl_tuple_sum!(D). На каждом шаге список идентификаторов теряет голову. Базовый случай — один элемент.
В std так реализован From для кортежей. В десятках крейтов аналогично.
Предохранитель на 128
Дефолтное значение recursion_limit — 128. Это глубина вложенности раскрытий: сколько раз компилятор может войти в expand(), уже находясь внутри другого expand(). Не общее количество раскрытий в программе, а именно глубина стека.
Поднять — одна строчка в корне крейта:
#![recursion_limit = "256"]
Когда это ок? Когда вы точно знаете, что рекурсия конечна, и 128 — просто маловато для вашей задачи. Вот как с impl_tuple_sum!: хотите кортежи до 32 — ставите 256, и всё.
Когда стрёмно? Когда вы уже на "4096" и лимит всё ещё мешает. Обычно это значит, что рекурсия не линейна. Макрос на каждом шаге порождает два рекурсивных вызова, и глубина растёт не как n, а как что-то посерьёзнее. Или что задачу пора решать другим способом.
Вот что ещё неочевидно, recursion_limit распространяется не только на макросы. Тот же счётчик используется при разрешении трейтов и при автодереференсинге. Компилятор рекурсивно проверяет impl Trait for &&...&T, заходит глубоко, бах, та же ошибка, то же сообщение «consider adding #![recursion_limit = "256"]». Одна настройка, несколько механизмов. На практике все это не проблема, но стоит держать в голове.
Фиксированные точки
Теперь к тому, зачем эти слова вынесены в заголовок.
Раскрытие макросов — это, в сущности, поиск фиксированной точки. Мы ищем такой TokenStream, к которому функция expand ничего не добавляет: expand(x) = x. Иначе говоря — программу, в которой нет ни одного макровызова. Каждый шаг раскрытия убирает макросы из кода, и когда их не осталось — мы в фиксированной точке.
Это, конечно, аналогия, а не теорема. Классические результаты о фиксированных точках живут в мире полных решёток и непрерывных монотонных функций. Пространство всех TokenStream это не какая то решетка, а expand не монотонна ни в каком разумном порядке. Так что прямого применения тут нет, и честность требует это сказать.
Мы итерируем функцию и ждём стабилизации. Если есть мера, которая убывает на каждом шаге, процесс конечен, и фиксированная точка достижима. Если такой меры нет — процесс может крутиться вечно.
Например, вот макрос, у которого фиксированная точка недостижима:
macro_rules! forever { ($($t:tt)*) => { forever!($($t)* extra_token) }; }
forever!() раскрывается в forever!(extra_token), то в forever!(extra_token extra_token), и далее. Вход растёт. Никакой фиксированной точки. Компилятор покрутится 128 шагов и выдаст ошибку!
А вот случай похитрее:
macro_rules! sneaky { (done) => { 42 }; ($($t:tt)*) => { sneaky!(done) }; }
Попробуйте мысленно раскрыть sneaky!(what the heck), прежде чем читать дальше.
...
Итак. Вход what the heck — три токена. Первая ветка ждёт ровно один токен done, не подходит. Вторая ветка матчит что угодно и заменяет на sneaky!(done). Один шаг. Дальше done матчит первую ветку — 42. Два шага. Всё.
И так для любого входа. sneaky!() тоже два шага, пустой вход матчит вторую ветку, $($t:tt)* при нуле повторений. sneaky!(done done done) — тоже два. Двухшаговая рекурсия с мгновенным схлопыванием любого входа.
Но из формы макроса это совершенно неочевидно. $($t:tt)* может быть чем угодно, рекурсивный вызов sneaky!(done) — с фиксированным входом, но первый раз видя этот макрос, вы об этом не знаете. Чтобы понять, что он завершается, нужно подумать.
Проблема остановки
Можно ли написать программу, которая для произвольного macro_rules! и произвольного входа определит, завершится ли раскрытие?
Нет.
macro_rules! — это система переписывания термов (TRS). Каждая ветка — правило: левая часть переписывается в правую. Компилятор применяет первое подходящее правило и повторяет. Для произвольных TRS завершимость неразрешима — это прямое следствие неразрешимости проблемы остановки.
Конечно, macro_rules! — не произвольная TRS. Паттерны ограничены типизированными фрагментами, выбор правила детерминирован (first match wins), вход структурирован. Подкласс TRS, который macro_rules! реально реализует, мог бы оказаться разрешимым, но, насколько мне известно, никто этого формально не доказал. И Rust не пытается.
Вместо этого лимит, 128 шагов и стоп.
В общем то говоря recursion_limit — такой вот костыль.
Раз мы уже назвали macro_rules! системой переписывания — стоит развернуть мысль, потому что тут есть кое-что интересное.
У TRS два свойства.
Завершимость (termination): существует ли для каждого входа конечная цепочка переписываний, приводящая к нормальной форме (терму, к которому ни одно правило неприменимо)?
Конфлюэнция (confluence): если к одному терму можно применить несколько правил, приведут ли разные цепочки к одному результату?
В Rust порядок применения правил жёстко задан: первое совпавшее правило выигрывает, раскрытие идёт снаружи внутрь. Конфлюэнция тут вообще не вопрос, выбора нет, результат детерминирован.
А вот завершимость... Классический приём для доказательства завершимости TRS — убывающие ординалы. Берёте вполне упорядоченное множество,такое, где нет бесконечных убывающих цепей. Каждому терму сопоставляете элемент этого множества. Показываете, что при каждом переписывании элемент строго убывает. Раз цепей нет, то процесс конечен.
Для tt-munching ваш ординал — длина входа. Натуральные числа, обычный порядок. На каждом шаге длина уменьшается на один.
Для push-down accumulation — длина необработанной части входа. Аккумулятор растёт, но это другой аргумент, его не считаем.
Для impl_tuple_sum! — количество идентификаторов в списке.
Для forever! — такой меры нет. Вход растёт. Доказательство завершимости невозможно, потому что завершимости нет.
Никто не пишет формальных доказательств завершимости для своих макросов. Но привычка спрашивать себя «а что убывает?» — невероятно полезная. Если вы не можете ткнуть пальцем в убывающую величину, либо вы чего-то не понимаете в своём макросе, либо макрос действительно может зациклиться.
Proc macros: всё те же проблемы
До сих пор мы говорили про macro_rules!, где компилятор хотя бы контролирует процесс. Он сам вызы��ает expand, сам считает глубину, сам останавливается. С процедурными макросами такой роскоши нет.
Proc macro — это обычная функция на Rust, которую компилятор загружает через dlopen и вызывает. Что внутр, его не касается.
Рекурсия тут бывает двух видов, и разница принципиальна.
Первый: proc macro возвращает TokenStream, в котором есть вызов самого себя. Компилятор раскрывает результат, натыкается на макровызов, снова зовёт proc macro. Это рекурсия через компилятор, и recursion_limit тут работает. Каждый такой круг — плюс один к счётчику глубины.
Второй: внутри кода proc macro написано loop {}. Или бесконечная рекурсия обычной функции. Или HTTP-запрос к серверу, который не отвечает. Это обычный код раста. Компилятор не знает, что внутри. recursion_limit бесполезен, он считает только входы/выходы из expand, а тут мы даже из первого expand не вышли.
use proc_macro::TokenStream; #[proc_macro] pub fn oops(_input: TokenStream) -> TokenStream { loop {} // всё, компиляция зависла }
Никакого таймаута. Никакого сообщения. cargo build висит, CPU на 100%, терминал молчит. Если это случилось в CI, вы узнаете, когда пайплайн упадёт по тайм-ауту раннера, через полчаса.
Отладка конечно тут такая себе. cargo expand покажет результат раскрытия, если proc macro хотя бы завершился. Если завис — только eprintln! в код самого proc macro и пересборка. Или дебаггер, но тут уже не знаю, что сказать.
Вот ещё почему proc macros выносят в отдельный крейт. Код proc macro исполняется с теми же правами, что и компилятор. Может читать, ходить в сеть, запускать процессы через Command. Когда вы подключаете чей-то proc macro, вы фактически даёте этому коду запуститься на вашей машине во время компиляции. В macro_rules! самое худшее, что может случиться — компилятор покрутится 128 шагов и остановится.
Как подглядывать за раскрытием
На stable главный инструмент — cargo expand:
$ cargo install cargo-expand $ cargo expand
Показывает финальный результат после всех раскрытия.
На nightly есть trace_macros!, это уже покруче.
#![feature(trace_macros)] macro_rules! count_tts { () => { 0usize }; ($_head:tt $($tail:tt)*) => { 1usize + count_tts!($($tail)*) }; } fn main() { trace_macros!(true); let _ = count_tts!(a b c); trace_macros!(false); }
Компилятор выдаст каждый шаг раскрытия:
note: trace_macro = note: expanding `count_tts! { a b c }` = note: to `1usize + count_tts! (b c)` note: trace_macro = note: expanding `count_tts! { b c }` = note: to `1usize + count_tts! (c)` note: trace_macro = note: expanding `count_tts! { c }` = note: to `1usize + count_tts! ()` note: trace_macro = note: expanding `count_tts! { }` = note: to `0usize`
Вот она, вся рекурсия,вход убывает на каждом шаге, базовый случай на пустом входе. Последовательность x, f(x), f(f(x)), ... перед глазами.
Рядом есть log_syntax!, тоже nightly. Выводит произвольные токены в stderr во время компиляции, что позволяет прощупать промежуточные значения. Оба инструмента живут в unstable с 2015 года.
Ещё есть macro_railroad, рисует синтаксические диаграммы по определению macro_rules!. К рекурсии напрямую не относится, но когда у вас 15 веток и вы уже не помните, какой паттерн куда ведёт, очень спасает.
Альтернативы
macro_rules! хорош для генерации кода по спискам, для кортежей разной длины, для разворачивания повторяющихся impl. Но с каждым годом территория, где он незаменим, сужается.
const fn забрал compile-time арифметику. Раньше, чтобы посчитать факториал на этапе компиляции, нужно было писать рекурсивный макрос с подсчётом через типы или через tt-munching. Сейчас:
const fn factorial(n: u64) -> u64 { match n { 0 | 1 => 1, _ => n * factorial(n - 1), } } const FACT_10: u64 = factorial(10);
Обычный Раст. Никакого recursion_limit, никакого tt-munching, никаких плясок с токенами. У const fn свой лимит — количество шагов интерпретатора MIRI (порядка миллиона по умолчанию), но это совершенно другой механизм, и для вычислений он подходит несравнимо лучше.
Proc macros забирают сложный парсинг. Если вам нужен свой DSL, работа с атрибутами, генерация по внешним данным — syn + quote дают полноценный Rust для трансформации кода. Но и цена ощутима: отдельный крейт, тяжёлые зависимости, тут для простых задач на мой взгляд будет чрезмерно.
build.rs + include! забирает массовую генерацию. Десять тысяч строк однообразного кода по JSON-схеме? Скрипт сборки напишет файл, include! подключит. Никакой рекурсии, никаких лимитов.
Как не зациклить свой макрос
Три проверки, которые можно прогнать в голове, когда пишется рекурсивный macro_rules!.
Первая: что убывает? Рекурсивный вызов должен получать строго меньше входных токенов. Для tt-munching это гарантировано самой формой: $($tail)* всегда короче $_head $($tail)*.
Вторая: аккумулятор не считать. Растёт [$($acc)*]? Да неважно! Для завершимости имеет значение только необработанная часть входа.
Третья: проверить все ветки. Не одну, а все. Одна ветка откусывает токен, а другая принимает $($t:tt)* и вызывает себя с тем же входом плюс что-то ещё. Макрос завершается, только если каждый путь исполнения конечен.
Компилятор Rust не доказывает, что ваш макрос остановится. Не может. Это не недоработка и не лень, это фундаментальное ограничение, которому 90 лет. Вместо доказательства у нас есть неплохой предохранитель: 128 уровней вложенности, одна строчка для повышения.
За этим числом стоит теория, которая старше всех языков программирования вместе взятых. Проблема остановки. Фиксированные точки. Системы переписывания термов. macro_rules! — маленький частный случай, который упирается в те же стены, что и весь computer science.
Не красиво, зато работает!
Если пишете рекурсивный макрос — спросите себя: что убывает на каждом шаге? Если есть ответ, всё будет хорошо. Если нет, ну, у вас есть 128 попыток выяснить это экспериментально.
Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.
