rust: add "bits", a custom bitflags implementation

One common thing that device emulation does is manipulate bitmasks, for example
to check whether two bitmaps have common bits.  One example in the pl011 crate
is the checks for pending interrupts, where an interrupt cause corresponds to
at least one interrupt source from a fixed set.

Unfortunately, this is one case where Rust *can* provide some kind of
abstraction but it does so with a rather Perl-ish There Is More Way To
Do It.  It is not something where a crate like "bilge" helps, because
it only covers the packing of bits in a structure; operations like "are
all bits of Y set in X" almost never make sense for bit-packed structs;
you need something else, there are several crates that do it and of course
we're going to roll our own.

In particular I examined three:

- bitmask (https://docs.rs/bitmask/0.5.0/bitmask/) does not support const
  at all.  This is a showstopper because one of the ugly things in the
  current pl011 code is the ugliness of code that defines interrupt masks
  at compile time:

    pub const E: Self = Self(Self::OE.0 | Self::BE.0 | Self::PE.0 | Self::FE.0);

  or even worse:

    const IRQMASK: [u32; 6] = [
      Interrupt::E.0 | Interrupt::MS.0 | Interrupt::RT.0 | Interrupt::TX.0 | Interrupt::RX.0,
      ...
    }

  You would have to use roughly the same code---"bitmask" only helps with
  defining the struct.

- bitmask_enum (https://docs.rs/bitmask-enum/2.2.5/bitmask_enum/) does not
  have a good separation of "valid" and "invalid" bits, so for example "!x"
  will invert all 16 bits if you choose u16 as the representation -- even if
  you only defined 10 bits.  This makes it easier to introduce subtle bugs
  in comparisons.

- bitflags (https://docs.rs/bitflags/2.6.0/bitflags/) is generally the most
  used such crate and is the one that I took most inspiration from with
  respect to the syntax.  It's a pretty sophisticated implementation,
  with a lot of bells and whistles such as an implementation of "Iter"
  that returns the bits one at a time.

The main thing that all of them lack, however, is a way to simplify the
ugly definitions like the above.  "bitflags" includes const methods that
perform AND/OR/XOR of masks (these are necessary because Rust operator
overloading does not support const yet, and therefore overloaded operators
cannot be used in the definition of a "static" variable), but they become
even more verbose and unmanageable, like

  Interrupt::E.union(Interrupt::MS).union(Interrupt::RT).union(Interrupt::TX).union(Interrupt::RX)

This was the main reason to create "bits", which allows something like

  bits!(Interrupt: E | MS | RT | TX | RX)

and expands it 1) add "Interrupt::" in front of all identifiers 2) convert
operators to the wordy const functions like "union".  It supports boolean
operators "&", "|", "^", "!" and parentheses, with a relatively simple
recursive descent parser that's implemented in qemu_api_macros.

Since I don't remember exactly how the macro was developed, I cannot exclude
that it contains code from "bitflags".  Therefore, I am conservatively leaving
in the MIT and Apache 2.0 licenses from bitflags.  In fact, I think there
would be a benefit in being able to push code back to "bitflags" anyway
whenever applicable, so that the two libraries do not diverge too much,
so that's another reason to use this.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

2 files changed, 241 insertions, 0 deletions

diff --git a/rust/qemu-api-macros/src/bits.rs b/rust/qemu-api-macros/src/bits.rs
new file mode 100644
index 0000000..5ba8475
--- /dev/null
+++ b/rust/qemu-api-macros/src/bits.rs
@@ -0,0 +1,229 @@
+// SPDX-License-Identifier: MIT or Apache-2.0 or GPL-2.0-or-later
+
+// shadowing is useful together with "if let"
+#![allow(clippy::shadow_unrelated)]
+
+use proc_macro2::{
+    Delimiter, Group, Ident, Punct, Spacing, Span, TokenStream, TokenTree, TokenTree as TT,
+};
+
+use crate::utils::MacroError;
+
+pub struct BitsConstInternal {
+    typ: TokenTree,
+}
+
+fn paren(ts: TokenStream) -> TokenTree {
+    TT::Group(Group::new(Delimiter::Parenthesis, ts))
+}
+
+fn ident(s: &'static str) -> TokenTree {
+    TT::Ident(Ident::new(s, Span::call_site()))
+}
+
+fn punct(ch: char) -> TokenTree {
+    TT::Punct(Punct::new(ch, Spacing::Alone))
+}
+
+/// Implements a recursive-descent parser that translates Boolean expressions on
+/// bitmasks to invocations of `const` functions defined by the `bits!` macro.
+impl BitsConstInternal {
+    // primary ::= '(' or ')'
+    //           | ident
+    //           | '!' ident
+    fn parse_primary(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        let next = match tok {
+            TT::Group(ref g) => {
+                if g.delimiter() != Delimiter::Parenthesis && g.delimiter() != Delimiter::None {
+                    return Err(MacroError::Message("expected parenthesis".into(), g.span()));
+                }
+                let mut stream = g.stream().into_iter();
+                let Some(first_tok) = stream.next() else {
+                    return Err(MacroError::Message(
+                        "expected operand, found ')'".into(),
+                        g.span(),
+                    ));
+                };
+                let mut output = TokenStream::new();
+                // start from the lowest precedence
+                let next = self.parse_or(first_tok, &mut stream, &mut output)?;
+                if let Some(tok) = next {
+                    return Err(MacroError::Message(
+                        format!("unexpected token {tok}"),
+                        tok.span(),
+                    ));
+                }
+                out.extend(Some(paren(output)));
+                it.next()
+            }
+            TT::Ident(_) => {
+                let mut output = TokenStream::new();
+                output.extend([
+                    self.typ.clone(),
+                    TT::Punct(Punct::new(':', Spacing::Joint)),
+                    TT::Punct(Punct::new(':', Spacing::Joint)),
+                    tok,
+                ]);
+                out.extend(Some(paren(output)));
+                it.next()
+            }
+            TT::Punct(ref p) => {
+                if p.as_char() != '!' {
+                    return Err(MacroError::Message("expected operand".into(), p.span()));
+                }
+                let Some(rhs_tok) = it.next() else {
+                    return Err(MacroError::Message(
+                        "expected operand at end of input".into(),
+                        p.span(),
+                    ));
+                };
+                let next = self.parse_primary(rhs_tok, it, out)?;
+                out.extend([punct('.'), ident("invert"), paren(TokenStream::new())]);
+                next
+            }
+            _ => {
+                return Err(MacroError::Message("unexpected literal".into(), tok.span()));
+            }
+        };
+        Ok(next)
+    }
+
+    fn parse_binop<
+        F: Fn(
+            &Self,
+            TokenTree,
+            &mut dyn Iterator<Item = TokenTree>,
+            &mut TokenStream,
+        ) -> Result<Option<TokenTree>, MacroError>,
+    >(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+        ch: char,
+        f: F,
+        method: &'static str,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        let mut next = f(self, tok, it, out)?;
+        while next.is_some() {
+            let op = next.as_ref().unwrap();
+            let TT::Punct(ref p) = op else { break };
+            if p.as_char() != ch {
+                break;
+            }
+
+            let Some(rhs_tok) = it.next() else {
+                return Err(MacroError::Message(
+                    "expected operand at end of input".into(),
+                    p.span(),
+                ));
+            };
+            let mut rhs = TokenStream::new();
+            next = f(self, rhs_tok, it, &mut rhs)?;
+            out.extend([punct('.'), ident(method), paren(rhs)]);
+        }
+        Ok(next)
+    }
+
+    // sub ::= primary ('-' primary)*
+    pub fn parse_sub(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        self.parse_binop(tok, it, out, '-', Self::parse_primary, "difference")
+    }
+
+    // and ::= sub ('&' sub)*
+    fn parse_and(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        self.parse_binop(tok, it, out, '&', Self::parse_sub, "intersection")
+    }
+
+    // xor ::= and ('&' and)*
+    fn parse_xor(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        self.parse_binop(tok, it, out, '^', Self::parse_and, "symmetric_difference")
+    }
+
+    // or ::= xor ('|' xor)*
+    pub fn parse_or(
+        &self,
+        tok: TokenTree,
+        it: &mut dyn Iterator<Item = TokenTree>,
+        out: &mut TokenStream,
+    ) -> Result<Option<TokenTree>, MacroError> {
+        self.parse_binop(tok, it, out, '|', Self::parse_xor, "union")
+    }
+
+    pub fn parse(
+        it: &mut dyn Iterator<Item = TokenTree>,
+    ) -> Result<proc_macro2::TokenStream, MacroError> {
+        let mut pos = Span::call_site();
+        let mut typ = proc_macro2::TokenStream::new();
+
+        // Gobble everything up to an `@` sign, which is followed by a
+        // parenthesized expression; that is, all token trees except the
+        // last two form the type.
+        let next = loop {
+            let tok = it.next();
+            if let Some(ref t) = tok {
+                pos = t.span();
+            }
+            match tok {
+                None => break None,
+                Some(TT::Punct(ref p)) if p.as_char() == '@' => {
+                    let tok = it.next();
+                    if let Some(ref t) = tok {
+                        pos = t.span();
+                    }
+                    break tok;
+                }
+                Some(x) => typ.extend(Some(x)),
+            }
+        };
+
+        let Some(tok) = next else {
+            return Err(MacroError::Message(
+                "expected expression, do not call this macro directly".into(),
+                pos,
+            ));
+        };
+        let TT::Group(ref _group) = tok else {
+            return Err(MacroError::Message(
+                "expected parenthesis, do not call this macro directly".into(),
+                tok.span(),
+            ));
+        };
+        let mut out = TokenStream::new();
+        let state = Self {
+            typ: TT::Group(Group::new(Delimiter::None, typ)),
+        };
+
+        let next = state.parse_primary(tok, it, &mut out)?;
+
+        // A parenthesized expression is a single production of the grammar,
+        // so the input must have reached the last token.
+        if let Some(tok) = next {
+            return Err(MacroError::Message(
+                format!("unexpected token {tok}"),
+                tok.span(),
+            ));
+        }
+        Ok(out)
+    }
+}
diff --git a/rust/qemu-api-macros/src/lib.rs b/rust/qemu-api-macros/src/lib.rs
index f97449b..ceb79f0 100644
--- a/rust/qemu-api-macros/src/lib.rs
+++ b/rust/qemu-api-macros/src/lib.rs
@@ -12,6 +12,9 @@ use syn::{
 mod utils;
 use utils::MacroError;
 
+mod bits;
+use bits::BitsConstInternal;
+
 fn get_fields<'a>(
     input: &'a DeriveInput,
     msg: &str,
@@ -219,3 +222,12 @@ pub fn derive_tryinto(input: TokenStream) -> TokenStream {
 
     TokenStream::from(expanded)
 }
+
+#[proc_macro]
+pub fn bits_const_internal(ts: TokenStream) -> TokenStream {
+    let ts = proc_macro2::TokenStream::from(ts);
+    let mut it = ts.into_iter();
+
+    let expanded = BitsConstInternal::parse(&mut it).unwrap_or_else(Into::into);
+    TokenStream::from(expanded)
+}