Написание сложных макросов на Rust: обратная польская нотация

автор Ингвар Степанян

(Это кросспост руководства, первоначально опубликованного в моем личном блоге)

Среди других интересных особенностей Rust имеет мощную систему макросов. К сожалению, даже после прочтения Книги и различных туториалов, когда дело дошло до попытки реализовать макрос, включающий обработку сложных списков различных элементов, я все еще изо всех сил пытался понять, как это должно быть сделано, и потребовалось некоторое время, прежде чем я дошел до этого. «динь» и начал неправильно использовать макросы для всего :) (хорошо, не все, как в я-я-использую-макросы-потому-что-я-не-хочу-использовать-функции-и-указывать-типы -и-пожизненно все, как это делают некоторые люди, но везде, где это действительно полезно)

Итак, вот мой взгляд на описание принципов написания таких макросов. Предполагается, что вы прочитали раздел Макросы из Книги и знакомы с основными определениями макросов и типами токенов.

В качестве примера для этого урока я возьму обратную польскую нотацию. Это интересно, потому что это достаточно просто, вы, возможно, уже знакомы с ним со школы, и все же, чтобы реализовать его статически во время компиляции, вам уже нужно использовать подход рекурсивных макросов.

Обратная польская нотация (также называемая постфиксной нотацией) использует стек для всех своих операций, так что любой операнд помещается в стек, а любой оператор [binary] берет два операнда из стека, оценивает результат и ставит обратно. Таким образом, выражение, подобное следующему:

2 3 + 4 *

переводится как:

1. Поместите 2 в стек.
2. Поместите 3 в стек.
3. Возьмите два последних значения из стека (3 и 2), примените оператор + и поместите результат (5) обратно в стек.
4. Поместите 4 в стек.
5. Возьмите два последних значения из стека (4 и 5), примените оператор * (4 * 5) и поместите результат (20) обратно в стек.
6. Конец выражения, единственное значение в стеке — это результат (20).

В более распространенной инфиксной нотации, используемой в математике и большинстве современных языков программирования, выражение будет выглядеть как (2 + 3) * 4.

Итак, давайте напишем макрос, который будет оценивать RPN во время компиляции, преобразуя его в инфиксную нотацию, которую понимает Rust.

macro_rules! rpn { 
  // TODO 
} 
println!("{}", rpn!(2 3 + 4 *)); // 20

Начнем с помещения чисел в стек.

Макросы в настоящее время не позволяют сопоставлять литералы, и expr не будет работать для нас, потому что он может случайно сопоставить последовательность, такую ​​​​как 2 + 3 ..., вместо того, чтобы принимать только одно число, поэтому мы прибегнем к tt — универсальному сопоставителю токенов, который соответствует только одному токену. дерево (будь то примитивный токен, такой как литерал/идентификатор/время жизни/и т. д., или выражение в скобках ()/[]/{}, содержащее больше токенов):

macro_rules! rpn { 
  ($num:tt) => { 
     // TODO 
  }; 
}

Теперь нам понадобится переменная для стека.

Макросы не могут использовать настоящие переменные, потому что мы хотим, чтобы этот стек существовал только во время компиляции. Таким образом, вместо этого трюк состоит в том, чтобы иметь отдельную последовательность токенов, которую можно передавать и использовать в качестве своего рода аккумулятора.

В нашем случае давайте представим его как последовательность expr, разделенных запятыми (поскольку мы будем использовать ее не только для простых чисел, но и для промежуточных инфиксных выражений), и заключим ее в скобки, чтобы отделить от остальной части ввода:

macro_rules! rpn { 
  ([ $($stack:expr),* ] $num:tt) => { 
     // TODO 
  }; 
}

Теперь последовательность токенов на самом деле не является переменной — вы не можете изменить ее на месте и сделать что-то потом. Вместо этого вы можете создать новую копию этой последовательности токенов с необходимыми изменениями и снова рекурсивно вызвать тот же макрос.

Если вы пришли из функционального языка или работали с какой-либо библиотекой, предоставляющей неизменяемые данные, оба этих подхода — изменение данных путем создания измененной копии и обработка списков с помощью рекурсии — вероятно, вам уже знакомы:

macro_rules! rpn { 
  ([ $($stack:expr),* ] $num:tt) => { 
    rpn!([ $num $(, $stack)* ]) 
  }; 
}

Теперь, очевидно, случай с одним числом довольно маловероятен и не очень интересен для нас, поэтому нам нужно сопоставить что-нибудь еще после этого числа как последовательность из нуля или более токенов tt, которые можно передать следующему вызову. нашего макроса для дальнейшего сопоставления и обработки:

macro_rules! rpn { 
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => { 
      rpn!([ $num $(, $stack)* ] $($rest)*) 
  }; 
}

На данный момент нам все еще не хватает поддержки оператора. Как мы сопоставляем операторов?

Если бы наш RPN представлял собой последовательность токенов, которые мы хотели бы обрабатывать точно так же, мы могли бы просто использовать список, например $($token:tt)*. К сожалению, это не дало бы нам возможности пройтись по списку и либо добавить операнд, либо применить оператор в зависимости от каждой лексемы.

В Книге говорится, что «система макросов вообще не имеет дело с двусмысленностью синтаксического анализа», и это верно для одной ветки макросов — мы не можем сопоставить последовательность чисел, за которой следует такой оператор, как $($num:tt)* +, потому что + также является допустимым токеном и может соответствовать группе tt, но здесь снова помогают рекурсивные макросы.

Если у вас есть разные ветки в определении макроса, Rust будет пробовать их одну за другой, поэтому мы можем поместить ветки нашего оператора перед числовой и, таким образом, избежать любого конфликта:

macro_rules! rpn { 
  ([ $($stack:expr),* ] + $($rest:tt)*) => { 
    // TODO 
  }; 
  ([ $($stack:expr),* ] - $($rest:tt)*) => { 
    // TODO 
  }; 
  
  ([ $($stack:expr),* ] * $($rest:tt)*) => { 
    // TODO 
  }; 
  ([ $($stack:expr),* ] / $($rest:tt)*) => { 
    // TODO 
  }; 
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => { 
    rpn!([ $num $(, $stack)* ] $($rest)*) 
  }; 
}

Как я уже говорил ранее, операторы применяются к последним двум числам в стеке, поэтому нам нужно будет сопоставить их отдельно, «вычислить» результат (построить регулярное инфиксное выражение) и положить его обратно:

macro_rules! rpn { 
  ([ $b:expr, $a:expr $(, $stack:expr)* ] + $($rest:tt)*) => { 
    rpn!([ $a + $b $(, $stack)* ] $($rest)*) 
  }; 
  ([ $b:expr, $a:expr $(, $stack:expr)* ] - $($rest:tt)*) => { 
    rpn!([ $a - $b $(, $stack)* ] $($rest)*) 
  }; 
  ([ $b:expr, $a:expr $(, $stack:expr)* ] * $($rest:tt)*) => { 
    rpn!([ $a * $b $(,$stack)* ] $($rest)*) 
  }; 
  ([ $b:expr, $a:expr $(, $stack:expr)* ] / $($rest:tt)*) => { 
    rpn!([ $a / $b $(,$stack)* ] $($rest)*) 
  }; 
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => { 
    rpn!([ $num $(, $stack)* ] $($rest)*) 
  }; 
}

Я не очень люблю такие очевидные повторения, но, как и в случае с литералами, нет специального типа токена для сопоставления операторов.

Однако мы можем добавить помощника, который будет отвечать за оценку, и делегировать ему любую явную ветку оператора.

В макросах вы не можете использовать внешний помощник, но единственное, в чем вы можете быть уверены, так это в том, что ваши макросы уже находятся в области действия, поэтому обычный трюк состоит в том, чтобы иметь ветку в том же макросе, «помеченную» каким-то уникальным последовательность токенов и вызовите ее рекурсивно, как мы это делали в обычных ветвях.

В качестве такого маркера возьмем @op, а внутри него примем любой оператор через tt (tt в таком контексте будет однозначным, т.к. мы будем передавать этому хелперу только операторы).

И стек больше не нужно разворачивать в каждую отдельную ветку — так как мы его ранее оборачивали в скобки [], его можно сопоставить как любое другое дерево токенов (tt), а затем передать в наш хелпер:

macro_rules! rpn { 
  (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => { 
   rpn!([ $a $op $b $(, $stack)* ] $($rest)*) 
  }; 
  ($stack:tt + $($rest:tt)*) => { 
   rpn!(@op $stack + $($rest)*) 
  }; 
  ($stack:tt - $($rest:tt)*) => { 
   rpn!(@op $stack - $($rest)*) 
  }; 
  ($stack:tt * $($rest:tt)*) => { 
   rpn!(@op $stack * $($rest)*) 
  }; 
  ($stack:tt / $($rest:tt)*) => { 
   rpn!(@op $stack / $($rest)*) 
  }; 
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => { 
    rpn!([ $num $(, $stack)* ] $($rest)*) 
  }; 
}

Теперь любые токены обрабатываются соответствующими ветвями, и нам нужно просто обработать последний случай, когда стек содержит один элемент и больше не осталось токенов:

macro_rules! rpn { 
  // ... 
 
  ([ $result:expr ]) => { 
    $result 
  }; 
}

На этом этапе, если вы вызовете этот макрос с пустым стеком и выражением RPN, он уже даст правильный результат:

"Игровая площадка"

println!("{}", rpn!([] 2 3 + 4 *)); // 20

Тем не менее, наш стек — это деталь реализации, и мы действительно не хотели бы, чтобы каждый потребитель передал пустой стек, поэтому давайте добавим в конце еще одну универсальную ветку, которая будет служить точкой входа, и автоматически добавим []:

"Игровая площадка"

macro_rules! rpn { 
  // ... 
  ($($tokens:tt)*) => { 
    rpn!([] $($tokens)*) 
  }; 
} 
println!("{}", rpn!(2 3 + 4 *)); // 20

Наш макрос работает даже для более сложных выражений, например, со страницы Википедии про RPN!

println!("{}", rpn!(15 7 1 1 + - / 3 * 2 1 1 + + -)); // 5

Обработка ошибок

Теперь кажется, что все работает гладко для правильных выражений RPN, но для того, чтобы макрос был готов к работе, мы должны быть уверены, что он также может обрабатывать неверный ввод с разумным сообщением об ошибке.

Во-первых, давайте попробуем вставить еще одно число в середину и посмотрим, что произойдет:

println!("{}", rpn!(2 3 7 + 4 *));

Вывод:

error[E0277]: the trait bound `[{integer}; 2]: std::fmt::Display` is not satisfied --> src/main.rs:36:20 
   | 
36 | println!("{}", rpn!(2 3 7 + 4 *)); 
   |                ^^^^^^^^^^^^^^^^^ `[{integer}; 2]` cannot be formatted with the default formatter; try using `:?` instead if you are using a format string 
   | 
   = help: the trait `std::fmt::Display` is not implemented for `[{integer}; 2]` 
   = note: required by `std::fmt::Display::fmt`

Хорошо, это определенно не выглядит полезным, поскольку не предоставляет никакой информации, относящейся к фактической ошибке в выражении.

Чтобы выяснить, что произошло, нам нужно будет отладить наши макросы. Для этого мы будем использовать функцию trace_macros (и, как и для любой другой дополнительной функции компилятора, вам понадобится ночная версия Rust). Мы не хотим отслеживать вызов println!, поэтому разделим вычисление RPN на переменную:

"Игровая площадка"

#![feature(trace_macros)] 
macro_rules! rpn { /* ... */ } 
fn main() { 
  trace_macros!(true); 
  let e = rpn!(2 3 7 + 4 *); 
  trace_macros!(false); println!("{}", e); 
}

В выводе мы теперь увидим, как наш макрос рекурсивно оценивается шаг за шагом:

note: trace_macro 
  --> src/main.rs:39:13 
   | 
39 |     let e = rpn!(2 3 7 + 4 *); 
   |             ^^^^^^^^^^^^^^^^^ 
   | 
   = note: expanding `rpn! { 2 3 7 + 4 * }` 
   = note: to `rpn ! ( [ ] 2 3 7 + 4 * )` 
   = note: expanding `rpn! { [ ] 2 3 7 + 4 * }` 
   = note: to `rpn ! ( [ 2 ] 3 7 + 4 * )` 
   = note: expanding `rpn! { [ 2 ] 3 7 + 4 * }` 
   = note: to `rpn ! ( [ 3 , 2 ] 7 + 4 * )` 
   = note: expanding `rpn! { [ 3 , 2 ] 7 + 4 * }` 
   = note: to `rpn ! ( [ 7 , 3 , 2 ] + 4 * )` 
   = note: expanding `rpn! { [ 7 , 3 , 2 ] + 4 * }` 
   = note: to `rpn ! ( @ op [ 7 , 3 , 2 ] + 4 * )` 
   = note: expanding `rpn! { @ op [ 7 , 3 , 2 ] + 4 * }` 
   = note: to `rpn ! ( [ 3 + 7 , 2 ] 4 * )` 
   = note: expanding `rpn! { [ 3 + 7 , 2 ] 4 * }` 
   = note: to `rpn ! ( [ 4 , 3 + 7 , 2 ] * )`  
   = note: expanding `rpn! { [ 4 , 3 + 7 , 2 ] * }` 
   = note: to `rpn ! ( @ op [ 4 , 3 + 7 , 2 ] * )` 
   = note: expanding `rpn! { @ op [ 4 , 3 + 7 , 2 ] * }` 
   = note: to `rpn ! ( [ 3 + 7 * 4 , 2 ] )` 
   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }` 
   = note: to `rpn ! ( [ ] [ 3 + 7 * 4 , 2 ] )` 
   = note: expanding `rpn! { [ ] [ 3 + 7 * 4 , 2 ] }` 
   = note: to `rpn ! ( [ [ 3 + 7 * 4 , 2 ] ] )` 
   = note: expanding `rpn! { [ [ 3 + 7 * 4 , 2 ] ] }` 
   = note: to `[(3 + 7) * 4, 2]`

Если мы внимательно просмотрим трассировку, то заметим, что проблема возникает на следующих шагах:

= note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }` 
= note: to `rpn ! ( [ ] [ 3 + 7 * 4 , 2 ] )`

Поскольку [ 3 + 7 * 4 , 2 ] не соответствовало ветке ([$result:expr]) => ... в качестве конечного выражения, вместо этого оно было перехвачено нашей последней всеобъемлющей ветвью ($($tokens:tt)*) => ..., добавлено пустым стеком [], а затем исходное [ 3 + 7 * 4 , 2 ] было сопоставлено универсальным $num:tt и помещено в стек как единое целое. конечное значение.

Чтобы этого не произошло, давайте вставим между этими двумя последними еще одну ветвь, которая соответствовала бы любому стеку.

Это произойдет только тогда, когда у нас закончатся токены, но в стеке не будет ровно одного конечного значения, поэтому мы можем рассматривать это как ошибку компиляции и создавать более полезное сообщение об ошибке, используя встроенный макрос compile_error!.

Обратите внимание, что мы не можем использовать format! в этом контексте, так как он использует API-интерфейсы времени выполнения для форматирования строки, и вместо этого нам придется ограничиться встроенными макросами concat! и stringify! для форматирования сообщения:

"Игровая площадка"

macro_rules! rpn { 
  // ... 
  ([ $result:expr ]) => { 
    $result 
  }; 
  ([ $($stack:expr),* ]) => { 
    compile_error!(concat!( 
      "Could not find final value for the expression, perhaps you missed an operator? Final stack: ", 
      stringify!([ $($stack),* ]) 
    )) 
  }; 
  ($($tokens:tt)*) => { 
    rpn!([] $($tokens)*) 
  }; 
}

Сообщение об ошибке теперь более осмысленно и содержит по крайней мере некоторые сведения о текущем состоянии оценки:

error: Could not find final value for the expression, perhaps you missed an operator? Final stack: [ (3 + 7) * 4 , 2 ] 
  --> src/main.rs:31:9 
   | 
31 |         compile_error!(concat!("Could not find final value for the expression, perhaps you missed an operator? Final stack: ", stringify!([$($stack),*]))) 
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
... 
40 |     println!("{}", rpn!(2 3 7 + 4 *)); 
   |                  ----------------- in this macro invocation

Но что, если вместо этого мы пропустим какое-то число?

"Игровая площадка"

println!("{}", rpn!(2 3 + *));

К сожалению, это все еще не слишком полезно:

error: expected expression, found `@` 
  --> src/main.rs:15:14 
   | 
15 |          rpn!(@op $stack * $($rest)*) 
   |               ^ 
... 
40 |     println!("{}", rpn!(2 3 + *)); 
   |                    ------------- in this macro invocation

Если вы попытаетесь использовать trace_macros, то даже он по какой-то причине не расширит стек здесь, но, к счастью, относительно понятно, что происходит - @op имеет очень специфические условия относительно того, что должно сопоставляться (он ожидает как минимум два значения на стек), а когда это невозможно, @ сопоставляется таким же слишком жадным $num:tt и помещается в стек.

Чтобы избежать этого, мы снова добавим еще одну ветку для соответствия всему, что начинается с @op, что еще не было сопоставлено, и вызовет ошибку компиляции:

"Игровая площадка"

macro_rules! rpn { 
  (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => { 
   rpn!([ $a $op $b $(, $stack)* ] $($rest)*) 
  }; 
  (@op $stack:tt $op:tt $($rest:tt)*) => { 
    compile_error!(concat!( 
      "Could not apply operator `", 
      stringify!($op), 
      "` to the current stack: ", 
      stringify!($stack) 
   )) 
  }; 
  // ... 
}

Давай попробуем еще:

error: Could not apply operator `*` to the current stack: [ 2 + 3 ] 
  --> src/main.rs:9:9 
   | 
 9 |          compile_error!(concat!("Could not apply operator ", stringify!($op), " to current stack: ", stringify!($stack))) 
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
... 
46 |     println!("{}", rpn!(2 3 + *)); 
   |                    ------------- in this macro invocation

Намного лучше! Теперь наш макрос может оценивать любое выражение RPN во время компиляции и изящно обрабатывает наиболее распространенные ошибки, так что давайте завершим его и скажем, что он готов к работе :)

Мы могли бы добавить еще много небольших улучшений, но я хотел бы оставить их за рамками этого демонстрационного руководства.

Не стесняйтесь, дайте мне знать, было ли это полезно и/или какие темы вы хотели бы видеть более освещенными в Твиттере!

Первоначально опубликовано на blog.cloudflare.com 31 января 2018 г.