crates/mbe/src/lib.rs

   1 //! `mbe` (short for Macro By Example) crate contains code for handling
   2 //! `macro_rules` macros. It uses `TokenTree` (from `tt` package) as the
   3 //! interface, although it contains some code to bridge `SyntaxNode`s and
   4 //! `TokenTree`s as well!
   5
   6 mod parser;
   7 mod mbe_expander;
   8 mod syntax_bridge;
   9 mod tt_iter;
  10 mod subtree_source;
  11
  12 #[cfg(test)]
  13 mod tests;
  14
  15 use std::fmt;
  16
  17 pub use tt::{Delimiter, DelimiterKind, Punct};
  18
  19 use crate::{
  20     parser::{parse_pattern, parse_template, Op},
  21     tt_iter::TtIter,
  22 };
  23
  24 #[derive(Debug, PartialEq, Eq)]
  25 pub enum ParseError {
  26     Expected(String),
  27     RepetitionEmtpyTokenTree,
  28 }
  29
  30 #[derive(Debug, PartialEq, Eq, Clone)]
  31 pub enum ExpandError {
  32     NoMatchingRule,
  33     UnexpectedToken,
  34     BindingError(String),
  35     ConversionError,
  36     InvalidRepeat,
  37     ProcMacroError(tt::ExpansionError),
  38     UnresolvedProcMacro,
  39     Other(String),
  40 }
  41
  42 impl From<tt::ExpansionError> for ExpandError {
  43     fn from(it: tt::ExpansionError) -> Self {
  44         ExpandError::ProcMacroError(it)
  45     }
  46 }
  47
  48 impl fmt::Display for ExpandError {
  49     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  50         match self {
  51             ExpandError::NoMatchingRule => f.write_str("no rule matches input tokens"),
  52             ExpandError::UnexpectedToken => f.write_str("unexpected token in input"),
  53             ExpandError::BindingError(e) => f.write_str(e),
  54             ExpandError::ConversionError => f.write_str("could not convert tokens"),
  55             ExpandError::InvalidRepeat => f.write_str("invalid repeat expression"),
  56             ExpandError::ProcMacroError(e) => e.fmt(f),
  57             ExpandError::UnresolvedProcMacro => f.write_str("unresolved proc macro"),
  58             ExpandError::Other(e) => f.write_str(e),
  59         }
  60     }
  61 }
  62
  63 pub use crate::syntax_bridge::{
  64     ast_to_token_tree, parse_to_token_tree, syntax_node_to_token_tree, token_tree_to_syntax_node,
  65     TokenMap,
  66 };
  67
  68 /// This struct contains AST for a single `macro_rules` definition. What might
  69 /// be very confusing is that AST has almost exactly the same shape as
  70 /// `tt::TokenTree`, but there's a crucial difference: in macro rules, `$ident`
  71 /// and `$()*` have special meaning (see `Var` and `Repeat` data structures)
  72 #[derive(Clone, Debug, PartialEq, Eq)]
  73 pub struct MacroRules {
  74     rules: Vec<Rule>,
  75     /// Highest id of the token we have in TokenMap
  76     shift: Shift,
  77 }
  78
  79 #[derive(Clone, Debug, PartialEq, Eq)]
  80 struct Rule {
  81     lhs: MetaTemplate,
  82     rhs: MetaTemplate,
  83 }
  84
  85 #[derive(Clone, Debug, PartialEq, Eq)]
  86 struct MetaTemplate {
  87     delimiter: Option<Delimiter>,
  88     tokens: Vec<Result<Op, ExpandError>>,
  89 }
  90
  91 impl<'a> MetaTemplate {
  92     fn iter(&self) -> impl Iterator<Item = &Result<Op, ExpandError>> {
  93         self.tokens.iter()
  94     }
  95
  96     fn delimiter_kind(&self) -> Option<DelimiterKind> {
  97         self.delimiter.map(|it| it.kind)
  98     }
  99 }
 100
 101 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 102 struct Shift(u32);
 103
 104 impl Shift {
 105     fn new(tt: &tt::Subtree) -> Shift {
 106         // Note that TokenId is started from zero,
 107         // We have to add 1 to prevent duplication.
 108         let value = max_id(tt).map_or(0, |it| it + 1);
 109         return Shift(value);
 110
 111         // Find the max token id inside a subtree
 112         fn max_id(subtree: &tt::Subtree) -> Option<u32> {
 113             subtree
 114                 .token_trees
 115                 .iter()
 116                 .filter_map(|tt| match tt {
 117                     tt::TokenTree::Subtree(subtree) => {
 118                         let tree_id = max_id(subtree);
 119                         match subtree.delimiter {
 120                             Some(it) if it.id != tt::TokenId::unspecified() => {
 121                                 Some(tree_id.map_or(it.id.0, |t| t.max(it.id.0)))
 122                             }
 123                             _ => tree_id,
 124                         }
 125                     }
 126                     tt::TokenTree::Leaf(tt::Leaf::Ident(ident))
 127                         if ident.id != tt::TokenId::unspecified() =>
 128                     {
 129                         Some(ident.id.0)
 130                     }
 131                     _ => None,
 132                 })
 133                 .max()
 134         }
 135     }
 136
 137     /// Shift given TokenTree token id
 138     fn shift_all(self, tt: &mut tt::Subtree) {
 139         for t in tt.token_trees.iter_mut() {
 140             match t {
 141                 tt::TokenTree::Leaf(leaf) => match leaf {
 142                     tt::Leaf::Ident(ident) => ident.id = self.shift(ident.id),
 143                     tt::Leaf::Punct(punct) => punct.id = self.shift(punct.id),
 144                     tt::Leaf::Literal(lit) => lit.id = self.shift(lit.id),
 145                 },
 146                 tt::TokenTree::Subtree(tt) => {
 147                     if let Some(it) = tt.delimiter.as_mut() {
 148                         it.id = self.shift(it.id);
 149                     };
 150                     self.shift_all(tt)
 151                 }
 152             }
 153         }
 154     }
 155
 156     fn shift(self, id: tt::TokenId) -> tt::TokenId {
 157         if id == tt::TokenId::unspecified() {
 158             return id;
 159         }
 160         tt::TokenId(id.0 + self.0)
 161     }
 162
 163     fn unshift(self, id: tt::TokenId) -> Option<tt::TokenId> {
 164         id.0.checked_sub(self.0).map(tt::TokenId)
 165     }
 166 }
 167
 168 #[derive(Debug, Eq, PartialEq)]
 169 pub enum Origin {
 170     Def,
 171     Call,
 172 }
 173
 174 impl MacroRules {
 175     pub fn parse(tt: &tt::Subtree) -> Result<MacroRules, ParseError> {
 176         // Note: this parsing can be implemented using mbe machinery itself, by
 177         // matching against `$($lhs:tt => $rhs:tt);*` pattern, but implementing
 178         // manually seems easier.
 179         let mut src = TtIter::new(tt);
 180         let mut rules = Vec::new();
 181         while src.len() > 0 {
 182             let rule = Rule::parse(&mut src)?;
 183             rules.push(rule);
 184             if let Err(()) = src.expect_char(';') {
 185                 if src.len() > 0 {
 186                     return Err(ParseError::Expected("expected `;`".to_string()));
 187                 }
 188                 break;
 189             }
 190         }
 191
 192         for rule in rules.iter() {
 193             validate(&rule.lhs)?;
 194         }
 195
 196         Ok(MacroRules { rules, shift: Shift::new(tt) })
 197     }
 198
 199     pub fn expand(&self, tt: &tt::Subtree) -> ExpandResult<tt::Subtree> {
 200         // apply shift
 201         let mut tt = tt.clone();
 202         self.shift.shift_all(&mut tt);
 203         mbe_expander::expand(self, &tt)
 204     }
 205
 206     pub fn map_id_down(&self, id: tt::TokenId) -> tt::TokenId {
 207         self.shift.shift(id)
 208     }
 209
 210     pub fn map_id_up(&self, id: tt::TokenId) -> (tt::TokenId, Origin) {
 211         match self.shift.unshift(id) {
 212             Some(id) => (id, Origin::Call),
 213             None => (id, Origin::Def),
 214         }
 215     }
 216 }
 217
 218 impl Rule {
 219     fn parse(src: &mut TtIter) -> Result<Rule, ParseError> {
 220         let mut lhs = src
 221             .expect_subtree()
 222             .map_err(|()| ParseError::Expected("expected subtree".to_string()))?
 223             .clone();
 224         lhs.delimiter = None;
 225         src.expect_char('=').map_err(|()| ParseError::Expected("expected `=`".to_string()))?;
 226         src.expect_char('>').map_err(|()| ParseError::Expected("expected `>`".to_string()))?;
 227         let mut rhs = src
 228             .expect_subtree()
 229             .map_err(|()| ParseError::Expected("expected subtree".to_string()))?
 230             .clone();
 231         rhs.delimiter = None;
 232
 233         let lhs = MetaTemplate { tokens: parse_pattern(&lhs), delimiter: None };
 234         let rhs = MetaTemplate { tokens: parse_template(&rhs), delimiter: None };
 235
 236         Ok(crate::Rule { lhs, rhs })
 237     }
 238 }
 239
 240 fn to_parse_error(e: &ExpandError) -> ParseError {
 241     let msg = match e {
 242         ExpandError::InvalidRepeat => "invalid repeat".to_string(),
 243         _ => "invalid macro definition".to_string(),
 244     };
 245     ParseError::Expected(msg)
 246 }
 247
 248 fn validate(pattern: &MetaTemplate) -> Result<(), ParseError> {
 249     for op in pattern.iter() {
 250         let op = op.as_ref().map_err(|e| to_parse_error(&e))?;
 251
 252         match op {
 253             Op::Subtree(subtree) => validate(&subtree)?,
 254             Op::Repeat { subtree, separator, .. } => {
 255                 // Checks that no repetition which could match an empty token
 256                 // https://github.com/rust-lang/rust/blob/a58b1ed44f5e06976de2bdc4d7dc81c36a96934f/src/librustc_expand/mbe/macro_rules.rs#L558
 257
 258                 if separator.is_none() {
 259                     if subtree.iter().all(|child_op| {
 260                         match child_op.as_ref().map_err(to_parse_error) {
 261                             Ok(Op::Var { kind, .. }) => {
 262                                 // vis is optional
 263                                 if kind.as_ref().map_or(false, |it| it == "vis") {
 264                                     return true;
 265                                 }
 266                             }
 267                             Ok(Op::Repeat { kind, .. }) => {
 268                                 return matches!(
 269                                     kind,
 270                                     parser::RepeatKind::ZeroOrMore | parser::RepeatKind::ZeroOrOne
 271                                 )
 272                             }
 273                             _ => {}
 274                         }
 275                         false
 276                     }) {
 277                         return Err(ParseError::RepetitionEmtpyTokenTree);
 278                     }
 279                 }
 280                 validate(subtree)?
 281             }
 282             _ => (),
 283         }
 284     }
 285     Ok(())
 286 }
 287
 288 #[derive(Debug, Clone, Eq, PartialEq)]
 289 pub struct ExpandResult<T> {
 290     pub value: T,
 291     pub err: Option<ExpandError>,
 292 }
 293
 294 impl<T> ExpandResult<T> {
 295     pub fn ok(value: T) -> Self {
 296         Self { value, err: None }
 297     }
 298
 299     pub fn only_err(err: ExpandError) -> Self
 300     where
 301         T: Default,
 302     {
 303         Self { value: Default::default(), err: Some(err) }
 304     }
 305
 306     pub fn str_err(err: String) -> Self
 307     where
 308         T: Default,
 309     {
 310         Self::only_err(ExpandError::Other(err))
 311     }
 312
 313     pub fn map<U>(self, f: impl FnOnce(T) -> U) -> ExpandResult<U> {
 314         ExpandResult { value: f(self.value), err: self.err }
 315     }
 316
 317     pub fn result(self) -> Result<T, ExpandError> {
 318         self.err.map(Err).unwrap_or(Ok(self.value))
 319     }
 320 }
 321
 322 impl<T: Default> From<Result<T, ExpandError>> for ExpandResult<T> {
 323     fn from(result: Result<T, ExpandError>) -> Self {
 324         result.map_or_else(|e| Self::only_err(e), |it| Self::ok(it))
 325     }
 326 }