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