Solving Advent of Code at Compile Time with Rust Macros
Intro
Producing good software is difficult. Writing tests, reasoning about unintended effects, tedious considerations about time vs memory trade-offs. The perfect program is one that never runs at all. No trade-offs, no bugs, no worries. But what if we go further, what if we could get our answer before the program even finishes compiling?
This year I want to write a perfect program to solve an advent of code challenge. If a perfect program can exist, it must be written in Rust. Lets abuse leverage Rust's declarative macros to get the answer to advent of code day one as a compiler error.
$ 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
The Problem
Go read the full problem description.
Roughly summarized, given two columns of numbers, sort both columns, calculate the absolute difference between corresponding elements, and sum all differences together.
If you can bear to witness it, a python solution is shown below.
"""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
Not only is the python solution barely legible, it is also horribly slow at O(n log n). If we want to keep AI from taking over programming jobs, we need to set the bar higher. Anything above O(1) will soon be unacceptable1.
A noble attempt, but far from a perfect program.
Perfection
If we truly want a perfect program, one that gives us answers without ever executing, we need to move our computation into the compiler itself. Modern Rust offers two main approaches for compile-time computation: constant evaluation and declarative macros.
Technically, it would make the most sense to use constant evaluation to calculate a compile time value. Const evaluation in Rust has come a long way in recent years and is a very powerful tool. But the title of the blog says "with Rust macros" so we will use declarative macros instead2.
Splitting the list
Step one is to split the input columns into two lists.
let answer = day1! {
3 4
4 3
2 5
1 3
3 9
3 3
};
Here is the macro:
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)*) };
}
Without getting too much into the weeds with rust macros, a macro defined with macro_rules! is a series of patterns and expansions. Think of it as a series of rules, each with two parts:
macro_rules! some_macro {
(pattern1) => { expansion1 };
(pattern2) => { expansion2 };
/* ... */
}
Each rule says, "if you see this pattern, replace it with this expansion". The macro keeps applying these rules until there's nothing left to expand3. The pattern syntax can be complicated, but we'll stick to the simplest patterns here.
Starting with a simple pattern ($a:tt) => { $a $a };. This tells Rust:
- match a single token (tt)4 and name it
a. - replace it by repeating the token twice.
So foo becomes foo foo and 1 becomes 1 1.
A series of tokens can also be matched using ($($tail:tt)*). The * means zero or more, like in a regex. For example, given the input 1 2 3:
- The expansion
($($tail)*)expands back to1 2 3 - The expansion
($($tail:$tail)*)becomes1:1 2:2 3:3
Essentially, everything in the innermost parenthesis is repeated for each matched token.
Lastly, patterns can also match tokens directly. The pattern (abc $($tail:tt)*) will match any input that starts with the token abc.
With that crash course, that should be enough to understand the entry rule
// entry
($($tail:tt)*) => { day1!(@split [] [] $($tail)*) };
This is our setup phase. We
- Match 0 or more tokens (all/any input).
- Wrap them in a new macro starting with
@split. - Add two empty lists, which will eventually hold our left and right columns.
- Keep the original input tokens at the end.
The @split allows us to control the next pattern to be matched by defining another rule with a pattern that starts with @split. The @_name_ is a rust convention. It could be any set of tokens to explicitly match against.
So day1!( 1 2 3 4) expands to day1!(@split [] [] 1 2 3 4).
The real magic happens in the next rule.
// 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)*)
};
This may look complicated, but is easy to understand by following an example.
Starting with the expansion from the previous step day1!(@split [] [] 1 2 3 4), the pattern matches:
- The token literal
@split - Two empty lists
[] []([$($lcol:tt)*] [$($(rcol:tt)*]) - The first number
1($l) - The second number
2($r) - And all remaining tokens
3 4($($tail:tt)*)
The rule then expands to day1!(@split [1] [2] 3 4). Broken down, the expansion creates a new macro that:
- Includes
1at the end of the first list ([$($lcol)* $l]) - Includes
2and the end of the second list ([$($(rcol)* $r]) - Keeps the remaining tokens at the end
3 4($($tail)*)
In other words, we are tracking the state of our columns in two lists and keeping not yet processed tokens at the end. This matches two tokens from the unprocessed input and the expansion places them into the correct list.
Incrementally matching tokens from the tail and recursively processing the rest is a pattern called tt munching. Storing the result to be matched by future rules is a pattern called push down accumulation.
This process continues until there are no more unprocessed input tokens.
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
At this point, there are no more tokens for $l $r to match, and the pattern for the current rule no longer applies. This leads to the final rule related to splitting the list.
// base case when no numbers remain
(@split [$($lcol:tt)*] [$($rcol:tt)*]) => {
todo!()
};
At this point we have two lists of unsorted tokens ready for the next phase of our perfect program.
Sorting a list
The last section was hopefully a gentle introduction to declarative macros in rust because this section is a little cursed.
Next we want to sort a sequence from the previous step like 2 1 4 3 into 1 2 3 4 at compile time. The issue is macros can't do conditional logic, they only match patterns and expand tokens. There is no way to say if a > b, expand to 'b a', else 'a b'. At least not directly.
You could brute force comparison by including a pattern for every possible pair being compared.
(@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 };
/* ... */
But that would be horribly hacky...
Expanding on this idea, we can implement bubble sort as a declarative macro.
Full Bubble Sort Macro
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)* ) }
}
At the core, there are only two types of rules.
First is a comparison rule that processes pairs of numbers:
(@bubble [$($work:tt)*] [$($final:tt)*] 2 1 $($tail:tt)*) => {
bubble_sort!(@bubble [$($work)* 1] [$($final)*] 2 $($tail)*)
};
This type of rule incrementally matches two numbers, adds the smaller of the two to our working list, and leaves the larger with the remaining numbers to compare.
This is repeated until only one number remains, at which point we know it is the largest of the current batch. The second rule adds the largest number to the final sorted list, resets the working list, and continues with the remaining numbers.
(@bubble [$($work:tt)*] [$($final:tt)*] $tail:tt) => {
bubble_sort!(@bubble [] [$($final)* $tail] $($work)*)
};
Here is the process visualized on sample input:
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
Finally a base case for when there is nothing left to sort.
([] [$($final:tt)*]) => {
todo!()
}
At this point, final contains the sorted sequence of tokens ready to be further processed.
Putting it all together
Unfortunately we now have two problems:
- Our bubble_sort only handles one list at a time, but we have two lists.
- We cannot nest macro expansions.
Let's see why nesting does not work. This looks logical:
(@split [$($lcol:tt)*] [$($(rcol:tt)*]) => {
answer!(
[bubble_sort!($($lcol)*)]
[bubble_sort!($($rcol)*)]
)
};
But this doesn't work. Given the input [1 3 2] [4 6 5], we would like the bubble_sort macros to expand first, so that we get something like
answer!([3 2 1] [6 5 4])
But that is not how the rust macro system works. The compiler will recognize answer! as a macro and look for rules within that macro that match the literal tokens [bubble_sort!($($lcol)*)] [bubble_sort!($($rcol)*)].
There is no way to "pass" the expansion of one macro back to a higher macro. This is why we have been using push down accumulation. Macros cannot be nested. Instead of "passing" values back up, we keep intermediate state as tokens at the start and forward them down to the next macro expansion.
Instead we will use another pattern, callbacks, to get our sorted lists back "up" as input to another macro. the callback pattern involves passing the name of a macro to be expanded.
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)
Calling duplicate_and_call!(foo 1 2 3) expands to foo!(1 2 3 1 2 3). This effectively allows the expansion (1 2 3 1 2 3) to be passed to another macro to be further processed.
Now, every bubble_sort rule is updated to also match a callback ($callback:tt) and additional args for that callback (($($state:tt)*)). These are simply forwarded unchanged until the terminal rule is reached. Now, the terminal rule can be written.
(@bubble $callback:tt ($($args:tt)*) [] [$($final:tt)*]) => {
$callback!( $($args)* [$($final)*] )
};
Here's an example of how the bubble_sort macro would be expanded wit the new terminal rule.
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])
The bubble_sort macro takes as input a callback name, arbitrary args, and an unsorted list. It will eventually pass the args followed by the sorted list wrapped in square brackets to the callback macro.
We can use this to write a double_bubble macro, which takes the two unsorted lists from split_list and expands to two sorted lists using 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!()
};
}
Skipping the bubble_sort expansions, here is how the double_bubble macro is expanded.
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
And now that we at last have our two sorted lists, we can emit our expression.
The Answer
The last step is to emit an expression to compute the answer. Remember, the goal is to add the absolute difference between each pair between the lists.
(@stage2 [$($l:tt)*] [$($r:tt)*]) => {
$(
{ if $l > $r { $l - $r } else { $r - $l} } +
)* 0
};
That's it! Given an input like [3 2 1] [6 5 4] the macro will expand to an expression:
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
We get the absolute difference between each pair and add them up. All done!
Except this expression is not evaluated anywhere. Even though I said no const at the start, I will use the const_str::format crate to get constant string formatting and display the result in a compile time panic.
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
Here is the full macro on playground.
And now we really are all done. The perfect program complete. The compiler gives us the answer before we even ask the question. No runtime overhead, no bugs, no problems. The perfect program is the program that never was.
This is sarcasm if you were unsure. Python is great.↩
Inspired by Aurorans Solis' RustConf 2023 talk, "Anything you can do, I can do worse with macro_rules".↩
Or it hits a recursion limit.↩
Technically a token tree, which can be a group of tokens as well.↩