Писать качественный софт сложно. Написание тестов, обдумывание возникших сайдэффектов, муки выбора между оптимизацией скорости выполнения и использованием памяти. Идеальная программа — та, которая никогда не запускается. Никаких тебе мук выбора, багов и забот. Но что, если мы пойдем дальше, что если мы получим ответ на наш вопрос еще до того, как программа скомпилируется?
В этом году я хотел написать идеальную программу для решения челленджа Advent of Code. Если идеальная программа и может существовать, она должна быть написана на Rust. Давайте помучаем декларативные макросы Rust для получения ответа на задачу первого дня Advent of Code в виде ошибки компиляции.
$ cargo build Compiling advent-of-code-2024 v0.1.0 (/home/glados/Code/advent-of-code-2024) error[E0080]: evaluation of constant value failed --> src/main.rs:142:5 | 142 | panic!("{}", format!("The answer is {answer}")); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'The answer is 11', src/main.rs:142:5Задача
Прочитайте условие задачи тут.
Грубо говоря, требуется следующее: получив две колонки чисел, отсортируйте обе, рассчитайте абсолютную разницу между соответствующими элементами и просуммируйте их.
Если ваша религия позволяет на такое смотреть, вот решение на python:
"""Warning: This code completes in a shocking O(n log n) time complexity and allocates memory with reckless abandon.""" input = [ 3, 4, 4, 3, 2, 5, 1, 3, 3, 9, 3, 3, ] left = sorted(input[::2]) right = sorted(input[1::2]) print(sum(abs(l - r) for l, r in zip(left, right))) # 11 Решение на python не только еле читаемое, так еще и невероятно медленное — O(n log n). Если мы не хотим, чтобы ИИ отобрал у нас работу, надо стремиться к более высокой планке. Скоро все медленнее O(1) станет неприемлемым.
Благородный порыв, но далеко не идеальная программа.
Совершенство
Если мы хотим поистине идеальную программу — ту, которая дает нам ответ ни разу не запускаясь, нам потребуется переместить процесс вычисления в сам компилятор. Современный Rust предлагает два способа выполнения вычислений на этапе компиляции: вычисление констант и декларативные макросы.
Технически, использование вычисления констант для расчета значения на этапе компиляции подходит больше всего. Вычисление констант в Rust сильно развилось за последнее время и стало крайне мощным инструментом. Но заголовок статьи говорит «с помощью макросов Rust», так что их мы и будем использовать.
Разделение списка
Первый шаг — разделить имеющиеся колонки на 2 списка.
let answer = day1! { 3 4 4 3 2 5 1 3 3 9 3 3 };Вот так выглядит макрос:
macro_rules! day1 { // match two numbers at a time, storing them in left and right lists (@split [$($lcol:tt)*] [$($rcol:tt)*] $l:tt $r:tt $($tail:tt)*) => { day1!(@split [$($lcol)* $l] [$($rcol)* $r] $($tail)*) }; // base case when no numbers remain (@split [$($lcol:tt)*] [$($rcol:tt)*]) => { todo!() }; // entry ($($tail:tt)*) => { day1!(@split [] [] $($tail)*) }; }Не залезая в дебри их работы, макросы, определяемые с помощью macro_rules! это набор шаблонов и раскрытий. О них можно думать как о наборе правил из двух частей:
macro_rules! some_macro { (pattern1) => { expansion1 }; (pattern2) => { expansion2 }; /* ... */ }Каждое правило говорит: «Если видишь такой шаблон, заменяй его этим раскрытием». Макрос продолжает применять правила до тех пор, пока не останется частей для раскрытия. Синтаксис шаблонов может быть сложным, но мы остановимся на наиболее простых шаблонах в рамках данной статьи.
Начнем с простого шаблона ($a:tt) => { $a $a };. Для Rust он означает:
-
Обрабатывай один токен
(tt)и называй егоa. -
Замени его, повторяя токен дважды
Так foo становится foo foo, а 1 становится 1 1.
Последовательность токенов также может быть сопоставлена с помощью ($($tail:tt)*). Символ *, как и в регулярных выражениях, означает ноль или больше повторений. К примеру, для входного значения 1 2 3:
-
Раскрытие
($($tail)*)раскрывается обратно в1 2 3 -
Раскрытие
($($tail:$tail)*)превращается в1:1 2:2 3:3
По сути, все во внутренних скобках дублируется для каждого подходящего токена.
И наконец, шаблоны могут сопоставляться с токенами напрямую. Шаблон (abc $($tail:tt)*) будет срабатывать для любого входного значения, начинающегося с токена abc.
Этого введения должно быть достаточно, чтобы понять входное правило
// entry ($($tail:tt)*) => { day1!(@split [] [] $($tail)*) };Это этап подготовки. Тут мы
-
Сопоставляем 0 или более токенов (весь/любой ввод).
-
Оборачиваем в новый макрос, начинающийся со
@split. -
Добавляем два пустых списка, которые в итоге будут содержать правую и левую колонки чисел.
-
В конце оставляем наши входные значения нетронутыми.
@split позволяет нам управлять следующим совпадением, задав новое правило для шаблона, начинающегося с @split. Название @_name_ обусловлено конвенцией языка. Это может быть любая последовательность токенов, для которой требуется задать совпадение.
Таким образом, day1!( 1 2 3 4) раскрывается в day1!(@split [] [] 1 2 3 4).
Настоящая магия начинается дальше.
// match two numbers at a time, storing them in left and right lists (@split [$($lcol:tt)*] [$($rcol:tt)*] $l:tt $r:tt $($tail:tt)*) => { day1!(@split [$($lcol)* $l] [$($rcol)* $r] $($tail)*) };Это может выглядеть сложно, но достаточно легко понять на примере.
Начиная с раскрытия с предыдущего шага day1!(@split [] [] 1 2 3 4), под шаблон попадают:
-
Литерал токена
@split -
Пустые списки
[] []([$($lcol:tt)*] [$($(rcol:tt)*]) -
Первое число
1($l) -
Второе число
2($r) -
И все остальные токены
3 4($($tail:tt)*)
Затем правило раскрывается в day1!(@split [1] [2] 3 4). Раскрытие в свою очередь создает новый макрос, который:
-
Добавляет
1в конец первого списка ([$($lcol)* $l]) -
Добавляет
2в конец второго списка ([$($(rcol)* $r]) -
Остальные токены остаются в конце
3 4($($tail)*)
Другими словами, мы отслеживаем состояние колонок в двух списках и оставляем необработанные токены в конце. Это сопоставляет два токена из еще не обработанного ввода, а раскрытие помещает их в нужный список.
Постепенное сопоставление токенов из хвоста и рекурсивная обработка остальных — паттерн, который называется tt munching. Сохранение результата для последующей обработки другими правилами называют push down accumulation.
Процесс продолжается, пока не остается необработанных токенов на входе.
day1!(@split [] [] 1 2 3 4) // Match and split first pair (1,2) -> day1!(@split [1] [2] 3 4) // Match and split second pair (3,4) -> day1!(@split [1 3] [2 4]) // No more pairs to match. move to base caseНа данном этапе у нас не осталось токенов, которые можно подставить в $l $r и текущее правило становится неприменимо. Это приводит нас к последнему правилу, относящемуся к разделению списка.
// base case when no numbers remain (@split [$($lcol:tt)*] [$($rcol:tt)*]) => { todo!() };Теперь у нас есть два списка несортированных токенов и мы можем приступить к следующей фазе нашей идеальной программы.
Сортировка списка
Надеюсь, что прошлая часть была мягким введением в декларативные макросы в rust, потому что эта часть немного проклята.
Дальше нам нужно отсортировать последовательность 2 1 4 3 с прошлого шага до 1 2 3 4 на этапе компиляции. Проблема в том, что макросы не умеют работать с условиями, они лишь обрабатывают последовательности и раскрывают токены. Нет способа сказать «если a > b, раскрой в b a, в противном случае — в a b». По крайней мере не напрямую.
Конечно можно забрутфорсить сравнение, прописав шаблоны для каждой возможной комбинации.
(@sort 1 1) => { 1 1 }; (@sort 1 2) => { 1 2 }; (@sort 2 1) => { 1 2 }; (@sort 1 3) => { 1 3 }; (@sort 3 1) => { 1 3 }; /* ... */Но это было бы очень костыльно…
Продолжая эту идею, мы можем реализовать сортировку пузырьком в виде декларативного макроса.
Полный макрос сортировки пузырьком
macro_rules! bubble_sort { (@bubble [$($work:tt)*] [$($final:tt)*] 1 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 1 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 2 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 3 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 1 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 2 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 2 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 3 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 2 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 3 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 3 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 3 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 3 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 4 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 4 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 5 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 5 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 6 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 6 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 7] [$($final)*] 7 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 7] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 7 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 7] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 7] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 8] [$($final)*] 8 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 8 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 8] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 2 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 2] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 3 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 3] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 4 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 4] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 5 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 5] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 6 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 6] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 7 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 7] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 8 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 8] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] 9 9 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 9] [$($final)*] 9 $($tail)*) }; (@bubble [$($work:tt)*] [$($final:tt)*] $tail:tt) => { bubble_sort!(@bubble [] [$($final)* $tail] $($work)* ) }; (@bubble [] [$($final:tt)*]) => { todo!() }; // entry ($($sortme:tt)* ) => { bubble_sort!(@bubble [] [] $($sortme)* ) } }В основе лежит два типа правил.
Первое — правило сравнения, которое обрабатывает пары чисел:
(@bubble [$($work:tt)*] [$($final:tt)*] 2 1 $($tail:tt)*) => { bubble_sort!(@bubble [$($work)* 1] [$($final)*] 2 $($tail)*) };Такое правило последовательно берет два числа, добавляет наименьшее в рабочий список и оставляет большее число с остальными числами для сравнения.
Это повторяется, пока не останется одно число, на этом этапе мы уже знаем, что оно наибольшее из данной партии. Второе правило добавляет наибольшее число в финальный отсортированный список, обнуляет рабочий список и продолжает обработку оставшихся чисел.
(@bubble [$($work:tt)*] [$($final:tt)*] $tail:tt) => { bubble_sort!(@bubble [] [$($final)* $tail] $($work)*) };Вот так выглядит процесс вживую:
bubble_sort!(@bubble [] [] 4 3 2 1) // Initial state bubble_sort!(@bubble [3] [] 4 2 1) // 3 < 4, add 3 to work bubble_sort!(@bubble [3 2] [] 4 1) // 2 < 4, add 2 to work bubble_sort!(@bubble [3 2 1] [] 4) // 1 < 4, add 1 to work bubble_sort!(@bubble [] [4] 3 2 1) // 4 is largest, add to final bubble_sort!(@bubble [2] [4] 3 1) // 2 < 3, add 2 to work bubble_sort!(@bubble [2 1] [] 3) // 1 < 3, add 1 to work bubble_sort!(@bubble [] [4 3] 2 1) // 3 is largest, add to final bubble_sort!(@bubble [1] [4 3] 2) // 1 < 2, add 1 to work bubble_sort!(@bubble [] [4 3 2] 1) // 2 is largest, add to final bubble_sort!(@bubble [] [4 3 2 1]) // 1 is largest, add to finalИ наконец, базовое условие, когда больше сортировать нечего.
([] [$($final:tt)*]) => { todo!() }На данном этапе в final содержится отсортированная последовательность токенов, готовая к дальнейшей обработке.
Собираем все воедино
К сожалению, у нас две проблемы:
-
Наша сортировка пузырьком обрабатывает один список за раз, а списка у нас два.
-
Мы не можем использовать вложенное раскрытие макросов.
Давайте посмотрим, почему вложенность не работает. Выглядит логично:
(@split [$($lcol:tt)*] [$($(rcol:tt)*]) => { answer!( [bubble_sort!($($lcol)*)] [bubble_sort!($($rcol)*)] ) };Но не работает. Получая на вводе [1 3 2] [4 6 5], мы бы хотели, чтобы сначала раскрылись макросы bubble_sort, чтобы получить нечто такое:
answer!([3 2 1] [6 5 4])Но система макросов в Rust работает не так. Компилятор распознает answer! как макрос и будет пытаться искать внутри него правила для токенов [bubble_sort!($($lcol)*)] [bubble_sort!($($rcol)*)].
Нет какого‑либо способа «передать» раскрытие макроса обратно внешнему макросу. Поэтому мы и использовали push down accumulation. Макросы не могут быть вложены. Вместо «передачи» значений выше, мы сохраняем промежуточное состояние как токены в начале и передаем следующему раскрытию.
Вместо этого мы воспользуемся другим паттерном — колбэками, чтобы получить обратно отсортированные списки в качестве входного значения другого макроса. Паттерн колбэков включает в себя передачу имени макроса для раскрытия.
macro_rules! duplicate_and_call { ($callback:tt $($tail:tt)*) => { $callback!($($tail)* $($tail)*) } } // Now when we call: duplicate_and_call!(foo 1 2 3) // It expands to: foo!(1 2 3 1 2 3)Вызов duplicate_and_call!(foo 1 2 3) раскрывается в foo!(1 2 3 1 2 3). Это по сути позволяет передать раскрытие (1 2 3 1 2 3) другому макросу для дальнейшей обработки.
Каждое правило bubble_sort обновлено, чтобы захватывать колбэк ($callback:tt) и его аргументы (($($state:tt)*)). Они в свою очередь просто передаются дальше без изменений, пока не достигается финальное правило. Пришло время написать его.
(@bubble $callback:tt ($($args:tt)*) [] [$($final:tt)*]) => { $callback!( $($args)* [$($final)*] ) };Вот пример того, как был бы раскрыт макрос bubble_sort с новым финальным правилом.
bubble_sort!(foo (blah blah) 5 4 6) // initial input /* all the intermediate bubble_sort steps */ bubble_sort!(@bubble foo (blah blah) [] [6 5 4]) // terminal rule foo!(blah blah [6 5 4])Макрос bubble_sort принимает в качестве входного значения название колбэка, произвольные аргументы и несортированный список. В конечном итоге он передаст аргументы вместе с отсортированным списком в квадратных скобках макросу колбэка.
Используя это, мы можем написать макрос double_bubble, принимающий два несортированных списка из split_list и раскрывающийся в два сортированных, используя bubble_sort.
macro_rules! double_bubble { // match the two unsorted lists ([$($l:tt)*] [$($r:tt)*]) => { // sort the right list, and forward it to double_bubble!(@stage1 bubble_sort!(double_bubble (@stage1 [$($l)*]) $($r)*) }; // match the unsorted left list and the sorted right list (@stage1 [$($unsorted:tt)*] [$($sorted:tt)*]) => { // sort the left list and forward both to double_bubble!(@stage2 bubble_sort!(double_bubble (@stage2 [$($sorted)*]) $($unsorted)*) }; // Match two sorted lists (@stage2 [$($l:tt)*] [$($r:tt)*]) => { todo!() }; }Пропуская раскрытия bubble_sort, вот так выглядит процесс раскрытия double_bubble.
double_bubble!([2 1 3] [5 4 6]) // initial input -> bubble_sort!(double_bubble (@stage1 [2 1 3]) 5 4 6) // sort first list /* bubble sort expansions */ -> double_bubble!(@stage1 [2 1 3] [6 5 4]) // first list sorted -> bubble_sort!(double_bubble (@stage2 [6 5 4]) 2 1 3) // sort second list /* bubble sort expansions */ -> double_bubble!(@stage2 [6 5 4] [3 2 1]) // both lists sortedИ теперь, когда у нас есть два сортированных списка, мы можем вызвать наше выражение.
Ответ
Последний шаг — вызов выражения для вычисления ответа. Вы же помните, наша цель — сложить абсолютную разницу между парами чисел в списках.
(@stage2 [$($l:tt)*] [$($r:tt)*]) => { $( { if $l > $r { $l - $r } else { $r - $l} } + )* 0 };Вот и все! Получив на входе нечто вроде [3 2 1] [6 5 4], наш макрос раскроется в выражение:
if 3 > 6 { 3 - 6 } else { 6 - 3 } + if 2 > 5 { 2 - 5 } else { 5 - 2 } + if 1 > 4 { 1 - 4 } else { 4 - 1 } + 0 Мы получаем абсолютную разницу между каждой из пар и складываем их вместе. Готово!
Вот только это выражение нигде не выполняется. Хоть я и сказал, что const не будет, я использую const_str::format для форматирования строки и отображения результата в панике на этапе компиляции.
const fn _main() -> usize { const answer: usize = day1! { 3 4 4 3 2 5 1 3 3 9 3 3 }; panic!("{}", format!("The answer is {answer}")); }$ cargo run -r Compiling advent-of-code-2024 v0.1.0 (/home/glados/Code/advent-of-code-2024) error[E0080]: evaluation of constant value failed --> src/main.rs:142:5 | 142 | panic!("{}", format!("The answer is {answer}")); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'The answer is 11', src/main.rs:142:5 ... For more information about this error, try `rustc --explain E0080`. error: could not compile `advent-of-code-2024` (bin "advent-of-code-2024") due to 1 previous errorВот так выглядит макрос полностью в playground.
И теперь мы действительно закончили. Идеальная программа готова. Компилятор дает нам ответ еще до того, как мы задали вопрос. Никакого оверхеда в рантайме, никаких багов, никаких проблем. Идеальная программа — та, которой не было.
ссылка на оригинал статьи https://habr.com/ru/articles/869716/
Добавить комментарий