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