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