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