Écrire des macros complexes dans Rust : Notation polonaise inverse (RPN)

(Ceci est une publication croisée d'un tutoriel publié à l'origine sur mon blog personnel)

Rust dispose, entre autres fonctionnalités intéressantes, d’un puissant système de macro. Malheureusement, même après la lecture de The Book et de divers tutoriels, lorsque j'ai essayé d'implémenter une macro impliquant le traitement de listes complexes d'éléments différents, j'ai toujours eu du mal à comprendre comment y parvenir. Et il a fallu un certain temps pour arriver à ce moment de « déclic », et j’ai commencé à mal utiliser les macros pour tout :) (ok, pas tout comme dans i-am-using-macros-because-i-dont-want-to-use-functions-and-specify-types-and-lifetimes everything comme j'ai vu certaines personnes le faire, mais n'importe où c'est réellement utile)

Voici donc mon point de vue sur la description des principes sous-jacents à l’écriture de ces macros. Cela suppose que vous ayez lu la section Macros du The Book et que vous maîtrisiez bien les définitions de macros de base et les types de jetons.

Je prendrai une notation polonaise inverse comme exemple pour ce tutoriel. C'est intéressant parce que c'est assez simple, vous le connaissez peut-être déjà à l'école. Et, pourtant, pour le mettre en œuvre de manière statique au moment de la compilation, vous devez déjà utiliser une approche par macros récursive.

La notation polonaise inverse (également appelée notation postfixe) utilise une pile pour toutes ses opérations, de sorte que n’importe quel opérande est placé sur la pile et que n’importe quel opérateur [binaire] extrait deux opérandes de la pile, évalue le résultat et le restitue. Donc, une expression comme celle-ci :

2 3 + 4 *

se traduit par :

1. Mettez 2 sur la pile.
2. Mettez 3 sur la pile.
3. Prenez les deux dernières valeurs de la pile ( 3 et 2), appliquez l'opérateur + et restituez le résultat ( 5) sur la pile.
4. Mettez 4 sur la pile.
5. Prenez les deux dernières valeurs de la pile ( 4 et 5), appliquez l'opérateur * ( 4 * 5 ) et restituez le résultat ( 20) sur la pile.
6. En fin d'expression, la valeur unique sur la pile est le résultat ( 20).

Dans une notation infixe plus courante, utilisée en mathématiques et dans la plupart des langages de programmation modernes, l'expression ressemblerait à (2 + 3) * 4.

Écrivons donc une macro qui évaluerait RPN au moment de la compilation en la convertissant en une notation infixe comprise par Rust.

macro_rules! rpn {
  // TODO
}

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

Commençons par placer des chiffres sur la pile.

Actuellement, les macros n'autorisent pas les littéraux de correspondance, et expr ne fonctionnera pas pour nous car il peut accidentellement faire correspondre une séquence comme 2 + 3 ... au lieu de prendre un seul chiffre. Nous allons donc recourir à tt, un matcher de combinaison générique qui correspond à un seul arbre de jetons (qu'il s'agisse d'un jeton primitif tel que littérale/identifiant/durée de vie/ etc. ou une expression mise entre parenthèses () / [] / {} - contenant plus de jetons) :

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

Maintenant, nous allons avoir besoin d'une variable pour la pile.

Les macros ne peuvent pas utiliser de vraies variables, car nous voulons que cette pile n'existe qu'au moment de la compilation. Donc, au lieu de cela, l’astuce est d’avoir une autre séquence de jetons qui peut être distribuée et utilisée comme une sorte d’accumulateur.

Dans notre cas, représentons-la comme une séquence de expr séparée par des virgules (puisque nous l'utilisons non seulement pour les nombres simples, mais également pour les expressions infixes intermédiaires) et encapsulons-la entre crochets pour la séparer du reste de l'entrée :

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

Maintenant, une séquence de jetons n'est pas vraiment une variable. Vous ne pouvez pas la modifier sur place et faire quelque chose après. Au lieu de cela, vous pouvez créer une nouvelle copie de cette séquence de jetons avec les modifications nécessaires et rappeler de manière récurrente la même macro.

Si vous êtes habitué au langage fonctionnel ou avez déjà travaillé avec une bibliothèque qui fournissait des données immuables auparavant, ces deux approches, à-savoir : la mutation de données par la création d’une copie modifiée et le traitement de listes avec une récursion, vous sont probablement déjà familières :

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

Maintenant, le cas avec un seul chiffre est plutôt improbable et peu intéressant pour nous, nous devrons donc faire correspondre tout ce qui suit ce chiffre sous la forme d'une séquence de zéro ou plusieurs jetons tt, qui peut être placée à la prochaine utilisation de notre macro pour une correspondance et un traitement plus poussés :

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

À ce stade, le support des opérateurs est toujours manquant. Comment réalisons-nous la correspondance des opérateurs ?

Si notre RPN est une séquence de jetons que nous voudrions traiter exactement de la même manière, nous pourrions simplement utiliser une liste telle que $($ token: tt)*. Malheureusement, cela ne nous donnerait pas la possibilité de parcourir la liste et de placer un opérande ou d’appliquer un opérateur en fonction de chaque jeton.

The Book dit que « le système de macros ne traite pas du tout l'ambiguïté de l'analyse », et c'est vrai pour une seule branche de macros. Nous ne pouvons pas faire correspondre une séquence de nombres suivie d’un opérateur comme $ ($ num: tt) * + car + est également un jeton valide et peut être associé au groupe tt, mais c’est là que les macros récursives peuvent à nouveau aider.

Si vous avez différentes branches dans votre définition de macro, Rust les essaiera une par une, afin que nous puissions placer nos branches d'opérateurs avant les branches numériques et ainsi éviter tout conflit :

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)*)
  };
}

Comme je le disais plus tôt, les opérateurs sont appliqués aux deux derniers chiffres de la pile, nous devrons donc les faire correspondre séparément, « évaluer » le résultat (construire une expression infixe régulière) et le replacer :

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)*)
  };
}

Je ne suis pas vraiment amateur de répétitions aussi évidentes, mais, comme avec les littéraux, il n'y a pas de type de jeton spécial pour faire correspondre les opérateurs.

Toutefois, ce que nous pouvons faire est d’ajouter un assistant responsable de l’évaluation et de lui déléguer toute branche d’opérateur explicite.

Dans les macros, vous ne pouvez pas vraiment utiliser un assistant externe, mais la seule chose dont vous pouvez être sûr, c'est que vos macros sont déjà à portée. L'astuce habituelle consiste donc à avoir une branche dans la même macro « marquée » avec une séquence de jetons unique, et de l’appeler récursivement comme nous le faisions dans les branches normales.

Utilisons @op comme ce marqueur et acceptons tous les opérateurs via tt à l’intérieur ( tt serait sans ambiguïté dans ce contexte car nous ne passerons que des opérateurs à cet assistant).

Et la pile n'a plus besoin d'être développée dans chaque branche distincte. Puisque nous l'avons déjà enveloppée dans des crochets [], elle peut être comparée à n'importe quel autre arbre de jetons (tt), puis passée dans notre aide :

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)*)
  };
}

Désormais, tous les jetons sont traités par les branches correspondantes et nous devons simplement gérer le cas final lorsque la pile contient un seul élément et qu'il ne reste plus de jetons :

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

À ce stade, si vous appelez cette macro avec une pile vide et une expression RPN, le résultat produit sera déjà correct :

Terrain de jeu

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

Toutefois, notre pile est un détail d'implémentation et il ne faut vraiment pas que tous les consommateurs transmettent une pile vide. Nous allons donc ajouter une autre branche fourre-tout à la fin qui servirait de point d'entrée et ajouter [] automatiquement :

Terrain de jeu

macro_rules! rpn {
  // ...

  ($($tokens:tt)*) => {
    rpn!([] $($tokens)*)
  };
}

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

Notre macro fonctionne même pour des expressions plus complexes, comme celle de la page Wikipédia au sujet de la RPN !

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

Gestion d'erreur

Maintenant, tout semble fonctionner de manière fluide pour les expressions RPN correctes, mais pour qu'une macro soit prête pour la production, nous devons nous assurer qu'elle peut également gérer les entrées non valides avec un message d'erreur raisonnable.

Tout d'abord, essayons d'insérer un autre chiffre au milieu et voyons ce qui se passe :

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

Résultat :

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`

D'accord, cela ne semble résolument pas utile car il ne fournit aucune information pertinente sur l'erreur réelle dans l'expression.

Afin de comprendre ce qui s'est passé, nous devrons déboguer nos macros. Pour cela, nous utiliserons une fonctionnalité trace_macros (et, comme pour toute autre fonctionnalité optionnelle du compilateur, vous aurez besoin d’une version Nightly de Rust). Nous ne voulons pas tracer l’appel println!, nous allons donc séparer notre calcul RPN en une variable :

Terrain de jeu

#![feature(trace_macros)]

macro_rules! rpn { /* ... */ }

fn main() {
  trace_macros!(true);
  let e = rpn!(2 3 7 + 4 *);
  trace_macros!(false);
  println!("{}", e);
}

Dans le résultat, nous verrons désormais comment notre macro est évaluée de manière récursive, étape par étape :

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]`

Si nous examinons attentivement la trace, nous remarquons que le problème provient de ces étapes :

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

Puisque [3 + 7 * 4, 2] ne correspondait pas à la branche ([$ result: expr]) => ...  comme expression finale, il a été attrapé par notre dernière branche fourre-tout ($ ($ tokens: tt) *) => ... à la place, précédée d'une pile vide [] puis l'original [3 + 7 * 4, 2] a été comparé au $num:tt générique et placé sur la pile en tant que valeur finale unique.

Afin d'éviter que cela ne se produise, insérons une autre branche entre ces deux dernières qui correspondrait à n'importe quelle pile.

Elle ne serait touchée que lorsque nous n'aurions plus de jetons, mais la pile n'avait pas une valeur finale exacte. Nous pouvons donc la traiter comme une erreur de compilation et générer un message d'erreur plus utile à l'aide d'une macro compile_error intégrée.

Notez que nous ne pouvons pas utiliser format! dans ce contexte puisqu'il utilise des API d'exécution pour formater une chaîne. Nous devrons plutôt nous limiter aux macros concat! et stringify! intégrés pour formater un message :

Terrain de jeu

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)*)
  };
}

Le message d'erreur est maintenant plus significatif et contient au moins quelques détails sur l'état actuel du progrès :

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

Mais que se passe-t-il si, au contraire, nous manquons un numéro ?

Terrain de jeu

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

Malheureusement, celui-ci n'est toujours pas très utile :

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

Si vous essayez d'utiliser trace_macros, même si cela ne développera pas la pile pour une raison quelconque, heureusement, ce qui se passe est relativement clair. @op a des conditions très spécifiques quant à ce qui doit être mis en correspondance (il attend au moins deux valeurs sur la pile) et, quand il ne les obtient pas, @op est apparié par le même bien trop gourmand $num:tt et placé sur la pile.

Pour éviter cela, encore une fois, nous allons ajouter une autre branche pour correspondre à tout ce qui commence par @op et qui ne correspondait pas déjà, et produire une erreur de compilation :

Terrain de jeu

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)
    ))
  };

  // ...
}

Essayons encore une fois :

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

Beaucoup mieux ! Désormais, notre macro peut évaluer n’importe quelle expression RPN au moment de la compilation et gère gracieusement les erreurs les plus courantes. Invoquons-la un jour et disons qu’elle est prête pour la production :)

Nous pourrions ajouter de nombreuses autres petites améliorations mais j'aimerais les laisser en dehors de ce tutoriel de démonstration.

N'hésitez pas à me dire si cela a été utile et/ou quels sujets vous souhaiteriez voir davantage couvertsur Twitter !