When steffahn posted the macro I asked about the other day, I had no idea how it worked, it seemed like black magic!, so I decided to see if I could figure it out by putting in more comments and generally playing around with it. I thought others might be interested, this is the result:
/// Binary search macro.
/// Parameters are variable we are searching for ($x) and list of numbers ( or anything comparable with $x ).
// Rust macro features used ( per https://doc.rust-lang.org/1.7.0/book/macros.html )
// $ is used to define match variables.
// expr stands for expression
// tt stands for token tree
// * means zero or more repetitions.
// + means one or more repetitions.
// @ is used for labelling sub-macros.
macro_rules! find_index
{
// Initial rule, invoke step A with count set to zero and empty list of neps.
// nep stands for number-expression-pair { number; expression }
( $x:ident, [ $($num:expr),+ ] ) =>
{
find_index!( @A, $x, [ $($num)+ ], 0, [] )
};
// Step A: pair the numbers with values generated by counting from 0.
// Parameters are x, input list of numbers, count, output list of neps.
// If the input list of numbers is not empty..
( @A, $x:ident, [ $firstnum:tt $($more_nums:expr)* ], $count:expr, [ $($out_nep:tt)* ] ) =>
{
// .. append nep {$firstnum; $count} to the output list.
find_index!( @A, $x, [ $($more_nums)*], ($count+1), [ $($out_nep)* {$firstnum; $count} ] )
};
// If the input list of numbers is empty, step A is complete, move to step B.
( @A, $x:ident, [], $count:expr, $neps:tt ) =>
{
find_index!( @B, $x, $neps, [] )
};
// If the initial parameters are (say) x and [5,7,9,13] then the step A evaluates to
// find_index! ( @ B, x, [], [{(5); 0} [(7); (0 + 1)] {(9); ((0 + 1) + 1)} {(13); (((0 + 1) + 1) + 1)}] )
// or simplified:
// find_index! ( @ B, x, [], [ {5; 0} {7; 1} {9; 2} {13; 3} ] )
// Step B: generate the final binary search expression from the [number; expr] pairs.
// Parameters are x, input list, output list.
// We keep pairing neps in the input list, putting them in output list.
// When the input is exhausted, the output becomes the input for the next iteration.
// Step B terminates when the input list is a single nep, and the output list is empty.
// Input list has two neps ..
( @B, $x:ident, [ { $num1:expr; $exp1:expr } { $num2:expr; $exp2:expr } $($more_nep:tt)* ], [$($out_nep:tt)*] ) =>
{
// .. append a nep to output, consisting of first number and comparison of x with second number, choosing $exp1 or $exp2.
find_index!( @B, $x, [ $($more_nep)* ], [ $($out_nep)* { $num1; ( if $x < $num2 {$exp1} else {$exp2} ) } ] )
};
// Input list is empty ..
( @B, $x:ident, [], $neps:tt ) =>
{
// .. swap input and output, start next iteration in step B.
find_index!( @B, $x, $neps, [] )
};
// Input list is single nep, append it to output ( which is not empty since + means 1 or more repetitions ).
( @B, $x:ident, [ {$num:expr; $exp:tt} ], [ $($out_nep:tt)+ ] ) =>
{
find_index!( @B, $x, [], [ $($out_nep)+ {$num; $exp} ] )
};
// Input list is single nep, output is empty, we are done.
( @B, $x:ident, [ {$num:expr; $final_exp:expr} ], [] ) =>
{
$final_exp
};
}
Of course there are probably too many comments here, the comments are saying what the macro is doing in too much detail and are mostly redundant, so not proper regular style for anyone who knows Rust macro syntax in detail, this was a learning exercise for me.
Please feel free to ask questions, suggest how the comments could be improved, or other suggestions. I still haven't exactly explained still how the algorithm works, although I do now understand it, just about!
