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