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