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