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