Logarithmic counting macro

I was reading @DanielKeep's Little Book of Rust Macros, when I realized there's a much better way of counting things than what's listed in that chapter.

The following approach is similar to Recursion, with the difference that every (one or two) recursive calls, the number of tokens to count is divided by two, instead of being reduced by one. Therefore, the recursion depth is up to twice the binary logarithm of the number of tokens to count, or O(log n), and the expanded tree is likewise very small.

macro_rules! count_tts {
    ()        => {0usize};
    ($one:tt) => {1usize};
    ($($pairs:tt $_p:tt)*) => {
        count_tts!($($pairs)*) << 1usize
    };
    ($odd:tt $($rest:tt)*) => {
        count_tts!($($rest)*) | 1usize
    };
}

Here is the expansion for 51 tokens:

count_tts!(---------------------------------------------------)
count_tts!(--------------------------------------------------) | 1
count_tts!(-------------------------)     << 1 | 1
count_tts!(------------------------)  | 1 << 1 | 1
count_tts!(------------)         << 1 | 1 << 1 | 1
count_tts!(------)          << 1 << 1 | 1 << 1 | 1
count_tts!(---)        << 1 << 1 << 1 | 1 << 1 | 1
count_tts!(--)     | 1 << 1 << 1 << 1 | 1 << 1 | 1
count_tts!(-) << 1 | 1 << 1 << 1 << 1 | 1 << 1 | 1
            1 << 1 | 1 << 1 << 1 << 1 | 1 << 1 | 1 == 51

With this approach, the default recursion limit (64) is enough to count up to 2^64 tokens, which is more data than hard drives will be able to hold for the foreseeable future. :wink: It is quite fast (twice as fast as the Slice Length, for an input of 100,000 tokens) and it produces a constant expression.

The macro is trivially correct, but I assert_eq'ed it on all numbers from 0 to 50, just to be on the safe side.

I went ahead and sent him a PR.

6 Likes

This is similar to how typenum handles things (as opposed to peano).

1 Like