Das Schreiben komplexer Makros in Rust: Umgekehrte polnische Notation

(Dies ist ein Crossposting eines Tutorials, das ursprünglich in meinem persönlichen Blog veröffentlicht wurde)

Neben anderen interessanten Features verfügt Rust über ein leistungsfähiges Makrosystem. Leider hatte ich auch nach dem Lesen von The Rust Programming Language (aka The Book) und verschiedenen Tutorials noch zu kämpfen, als es darum ging, ein Makro zu implementieren, das die Verarbeitung komplexer Listen verschiedener Elemente beinhaltet. Ich hatte Schwierigkeiten zu verstehen, wie es gemacht werden sollte, und es dauerte einige Zeit, bis ich dieses Aha-Erlebnis hatte und anfing, Makros für alles zu missbrauchen :) (Okay, nicht für alles wie bei diesem „Ich verwende Makros, weil ich keine Funktionen einsetzen und Typen und Lebensdauern spezifizieren will“-Alles, wie ich es bei einigen Leuten gesehen habe, sondern überall da, wo sie tatsächlich nützlich sind.)

CC BY 2.0 Foto von Conor Lawless

Also, hier ist mein Versuch einer Beschreibung der Prinzipien hinter dem Schreiben solcher Makros. Ich gehe davon aus, dass Sie den Abschnitt über Makros in The Book gelesen haben und mit grundlegenden Makro-Definitionen und Token-Typen vertraut sind.

Als Beispiel für dieses Tutorial nehme ich eine umgekehrte polnische Notation. Sie ist interessant, weil sie relativ einfach ist und Sie sie vielleicht bereits aus der Schule kennen, aber um sie statisch zur Compile-Zeit zu implementieren, muss man bereits einen rekursiven Makroansatz verwenden.

Die umgekehrte polnische Notation (auch Postfixnotation genannt) verwendet einen Stapel für alle Operationen, sodass jeder Operand auf den Stapel gelegt wird und jeder [binäre] Operator zwei Operanden aus dem Stapel nimmt, das Ergebnis auswertet und es zurücklegt. Ein Ausdruck wie der folgende:

2 3 + 4 *

2 3 + 4 *

lautet übersetzt:

Lege 2 auf den Stapel.
Lege 3 auf den Stapel.
Nimm die beiden letzten Werte vom Stapel ( 3 und 2), wende den Operator + an und lege das Ergebnis ( 5) zurück auf den Stapel.
Lege 4 auf den Stapel.
Nimm die beiden letzten Werte vom Stapel ( 4 und 5), wende den Operator * ( 4 * 5) an und lege das Ergebnis ( 20) zurück auf den Stapel.
Am Ende des Ausdrucks ist der einzige Wert auf dem Stapel das Ergebnis ( 20).

In einer gebräuchlicheren Infixnotation, die in der Mathematik und den modernsten Programmiersprachen verwendet wird, würde der Ausdruck so aussehen: (2 + 3) * 4.

macro_rules! rpn {
  // TODO
}

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

Schreiben wir also ein Makro, das RPN zur Compile-Zeit auswertet, indem es sie in eine Infixnotation konvertiert, die Rust versteht.

Beginnen wir mit dem Ablegen von Zahlen auf dem Stapel.

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

Makros erlauben derzeit den Abgleich von Literalen nicht, und expr funktioniert für uns nicht, weil es versehentlich eine Sequenz wie 2 + 3 ... abgleichen kann, anstatt nur eine einzelne Zahl zu verwenden. Also greifen wir auf tt zurück, einen generischen Token-Matcher, der nur einen Token-Baum abgleicht (es kann sich um ein primitives Token wie Literal/Identifikator/Lebensdauer/usw. oder einen Ausdruck in ()/ []/ {}-Klammern handeln, der mehr Token enthält):

Jetzt benötigen wir eine Variable für den Stapel.

Makros können keine echten Variablen verwenden, da wir wollen, dass dieser Stapel nur zur Compile-Zeit vorhanden ist. Stattdessen besteht der Trick darin, eine separate Token-Sequenz zu haben, die weitergegeben und als eine Art Akkumulator verwendet werden kann.

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

In unserem Fall stellen wir sie als durch Kommas getrennte Sequenz von expr dar (da wir sie nicht nur für einfache Zahlen, sondern auch für intermediäre Infix-Ausdrücke verwenden) und setzen sie in Klammern, um sie vom Rest der Eingabe zu trennen:

Eine Token-Sequenz ist aber nicht wirklich eine Variable – man kann sie nicht an Ort und Stelle ändern und danach etwas tun. Stattdessen kann man eine neue Kopie dieser Token-Sequenz mit den erforderlichen Änderungen erstellen und das gleiche Makro rekursiv erneut aufrufen.

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

Wenn Sie aus dem Bereich der funktionalen Sprache kommen oder bereits mit einer Bibliothek gearbeitet haben, die unveränderliche Daten bereitstellt, sind Ihnen diese beiden Ansätze – das Verändern von Daten durch Erstellen einer modifizierten Kopie und die Verarbeitung von Listen mit Rekursion – wahrscheinlich bereits bekannt:

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

Nun, offensichtlich ist der Fall mit nur einer einzigen Zahl eher unwahrscheinlich und für uns nicht sehr interessant. Also müssen wir alles andere nach dieser Zahl als eine Sequenz von null oder mehr tt-Token abgleichen, die an den nächsten Aufruf unseres Makros zum weiteren Abgleich und zur Verarbeitung übergeben werden kann:

An diesem Punkt fehlt noch die Unterstützung des Operators. Wie gleichen wir die Operatoren ab?

Wenn unsere RPN eine Sequenz von Token wäre, die wir auf genau die gleiche Weise verarbeiten wollen, könnten wir einfach eine Liste wie $($token:tt)* verwenden. Leider würde uns das nicht die Möglichkeit geben, die Liste durchzugehen und abhängig von jedem Token entweder einen Operanden abzulegen oder einen Operator anzuwenden.

The Book sagt, dass ein „Makro-System sich überhaupt nicht mit Parse-Mehrdeutigkeit befasst.“ Das gilt für einen einzelnen Makro-Zweig – wir können keine Folge von Zahlen gefolgt von einem Operator wie $($num:tt)* + abgleichen, weil +auch ein gültiges Token ist und von der tt-Gruppe abgeglichen werden könnte. Aber hier helfen wieder rekursive Makros.

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

Wenn Sie in Ihrer Makro-Definition verschiedene Zweige haben, wird Rust diese nacheinander ausprobieren, sodass wir unsere Operatorzweige vor die numerischen stellen und auf diese Weise Konflikte vermeiden können:

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

Wie bereits erwähnt, werden Operatoren auf die letzten beiden Zahlen auf dem Stapel angewendet, daher müssen wir sie separat abgleichen, das Ergebnis „auswerten“ (einen regulären Infix-Ausdruck erstellen) und es zurücklegen:

Ich bin nicht wirklich ein Fan von solchen offensichtlichen Wiederholungen, aber wie bei den Literalen gibt es keinen speziellen Token-Typ, der Operatoren abgleicht.

Wir können jedoch einen Helfer hinzufügen, der für die Auswertung verantwortlich ist, und jeden expliziten Operatorzweig an ihn delegieren.

In Makros können Sie nicht wirklich einen externen Helfer verwenden, aber das einzige, worüber Sie sich sicher sein können, ist, dass Ihre Makros bereits im Gültigkeitsbereich sind, daher besteht der übliche Trick darin, einen Zweig im gleichen Makro mit einer eindeutigen Token-Sequenz „markiert“ zu haben und ihn rekursiv zu aufzurufen, wie wir es in regulären Zweigen getan haben.

Lassen Sie uns @op als solchen Marker verwenden und jeden Operator über tt darin akzeptieren ( tt wäre in einem solchen Kontext eindeutig, da wir nur Operatoren an diesen Helfer übergeben).

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

Und der Stapel muss nicht mehr in jedem einzelnen Zweig erweitert werden – da wir ihn früher in []-Klammern gesetzt haben, kann er wie jeder andere Token-Baum (tt) abgeglichen und dann an unseren Helfer übergeben werden:

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

Jetzt werden alle Token von entsprechenden Zweigen verarbeitet und wir müssen nur den letzten Fall behandeln, wenn der Stapel ein einzelnes Element enthält und keine Token mehr übrig sind:

Wenn Sie dieses Makro mit einem leeren Stapel und einem RPN-Ausdruck aufrufen, wird an diesem Punkt bereits ein korrektes Ergebnis erzielt:

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

Playground

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

macro_rules! rpn {
  // ...

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

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

Unser Stapel ist jedoch ein Implementierungsdetail und wir wollen wirklich nicht, dass jeder Abnehmer einen leeren Stapel weitergibt. Also fügen wir am Ende einen weiteren Catch-all-Zweig hinzu, der als Eingangspunkt dient und automatisch [] hinzufügt:

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

Playground

Unser Makro funktioniert sogar für komplexere Ausdrücke wie die auf der Wikipedia-Seite über RPN!

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

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

Fehlerbehandlung

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`

Nun scheint für korrekte RPN-Ausdrücke alles reibungslos zu funktionieren. Aber damit ein Makro produktionsreif ist, müssen wir sicherstellen, dass es auch ungültige Eingaben verarbeiten kann, und zwar mit einer vernünftigen Fehlermeldung.

Zuerst versuchen wir, eine weitere Zahl in der Mitte einzufügen, und sehen uns an, was passiert:

Output:

#![feature(trace_macros)]

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

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

Okay, das sieht definitiv nicht hilfreich aus, da es keine Informationen liefert, die für den eigentlichen Fehler im Ausdruck relevant sind.

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

Um herauszufinden, was passiert ist, müssen wir unsere Makros debuggen. Dazu verwenden wir eine trace_macros-Funktion (dafür benötigen Sie wie für jede andere optionale Compiler-Funktion einen Nightly Release von Rust). Wir wollen den Aufruf println! nicht verfolgen, also separieren wir unsere RPN-Berechnung in einer Variablen:

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

Playground

In der Ausgabe sehen wir nun, wie unser Makro Schritt für Schritt rekursiv ausgewertet wird:

Wenn wir die Ablaufverfolgung sorgfältig durchsehen, stellen wir fest, dass das Problem in den folgenden Schritten entsteht:

Da [ 3 + 7 * 4 , 2 ] nicht von dem Zweig ([$result:expr]) => ... als letzter Ausdruck abgeglichen wurde, wurde es stattdessen von unserem letzten Catch-all ($($tokens:tt)*) => ... eingefangen, wobei ihm ein leerer Stapel [] vorangestellt wurde. Das Original [ 3 + 7 * 4 , 2 ] wurde dann vom generischen $num:tt abgeglichen und als einzelner Endwert auf den Stapel gelegt.

Um dies zu verhindern, fügen wir zwischen den beiden letzten einen weiteren Zweig ein, der jeden Stapel abgleicht.

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

Er wird nur dann getroffen, wenn uns die Token ausgehen und der Stapel nicht genau einen Endwert hat, sodass wir das als Kompilierungsfehler behandeln und eine hilfreichere Fehlermeldung mit dem integriertem compile_error!-Makro erzeugen können.

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

Beachten Sie, dass wir format! in diesem Kontext nicht einsetzen können, da es Laufzeit-APIs verwendet, um eine Zeichenfolge zu formatieren. Stattdessen müssen wir uns auf integrierte concat!- und stringify!-Makros beschränken, um eine Nachricht zu formatieren:

Playground

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

Die Fehlermeldung ist jetzt aussagekräftiger und enthält zumindest einige Details zum aktuellen Auswertungsstand:

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

Aber was ist, wenn uns stattdessen eine Zahl fehlt?

Playground

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

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

  // ...
}

Leider ist das noch nicht allzu hilfreich:

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

Wenn Sie versuchen, trace_macros zu verwenden, wird der Stapel hier aus irgendeinem Grund nicht erweitert, aber glücklicherweise ist relativ klar, was passiert – @op hat sehr spezifische Bedingungen hinsichtlich dem, was abgeglichen werden soll (es erwartet mindestens zwei Werte auf dem Stapel), und wenn es nicht abgleichen kann, wird @ vom gleichen übergierigen $num:tt abgeglichen und auf den Stapel gelegt.

Um dies zu vermeiden, werden wir wieder einen weiteren Zweig hinzufügen, um alles abzugleichen, was mit @ob beginnt, nicht bereits abgeglichen wurde und einen Kompilierungsfehler erzeugt:

Playground

Versuchen wir es noch einmal:

Viel besser! Jetzt kann unser Makro jeden RPN-Ausdruck zur Compile-Zeit auswerten und behandelt die häufigsten Fehler elegant, also belassen wir es dabei und sagen, dass es produktionsreif ist :)

Es gibt noch viele weitere kleine Verbesserungen, die wir hinzufügen könnten, aber ich möchte sie außerhalb dieses Demo-Tutorials belassen.

Lassen Sie mich auf Twitter wissen, ob dies hier nützlich war und/oder welche Themen verstärkt behandelt haben wollen

Entwickler Programmierung Polish

Der Cloudflare-Blog

Das Schreiben komplexer Makros in Rust: Umgekehrte polnische Notation

Fehlerbehandlung

Workers Builds: integrated CI/CD built on the Workers platform

Elephants in tunnels: how Hyperdrive connects to databases inside your VPC networks

Durable Objects aren't just durable, they're fast: a 10x speedup for Cloudflare Queues

Billions and billions (of logs): scaling AI Gateway with the Cloudflare Developer Platform