crates/mbe/src/expander/matcher.rs

   1 //! FIXME: write short doc here
   2
   3 use crate::{
   4     expander::{Binding, Bindings, Fragment},
   5     parser::{Op, RepeatKind, Separator},
   6     subtree_source::SubtreeTokenSource,
   7     tt_iter::TtIter,
   8     ExpandError, MetaTemplate,
   9 };
  10
  11 use super::ExpandResult;
  12 use parser::{FragmentKind::*, TreeSink};
  13 use syntax::{SmolStr, SyntaxKind};
  14 use tt::buffer::{Cursor, TokenBuffer};
  15
  16 impl Bindings {
  17     fn push_optional(&mut self, name: &SmolStr) {
  18         // FIXME: Do we have a better way to represent an empty token ?
  19         // Insert an empty subtree for empty token
  20         let tt = tt::Subtree::default().into();
  21         self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
  22     }
  23
  24     fn push_empty(&mut self, name: &SmolStr) {
  25         self.inner.insert(name.clone(), Binding::Empty);
  26     }
  27
  28     fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> {
  29         for (key, value) in nested.inner {
  30             if !self.inner.contains_key(&key) {
  31                 self.inner.insert(key.clone(), Binding::Nested(Vec::new()));
  32             }
  33             match self.inner.get_mut(&key) {
  34                 Some(Binding::Nested(it)) => {
  35                     // insert empty nested bindings before this one
  36                     while it.len() < idx {
  37                         it.push(Binding::Nested(vec![]));
  38                     }
  39                     it.push(value);
  40                 }
  41                 _ => {
  42                     return Err(ExpandError::BindingError(format!(
  43                         "could not find binding `{}`",
  44                         key
  45                     )));
  46                 }
  47             }
  48         }
  49         Ok(())
  50     }
  51 }
  52
  53 macro_rules! err {
  54     () => {
  55         ExpandError::BindingError(format!(""))
  56     };
  57     ($($tt:tt)*) => {
  58         ExpandError::BindingError(format!($($tt)*))
  59     };
  60 }
  61
  62 #[derive(Debug, Default)]
  63 pub(super) struct Match {
  64     pub(super) bindings: Bindings,
  65     /// We currently just keep the first error and count the rest to compare matches.
  66     pub(super) err: Option<ExpandError>,
  67     pub(super) err_count: usize,
  68     /// How many top-level token trees were left to match.
  69     pub(super) unmatched_tts: usize,
  70 }
  71
  72 impl Match {
  73     fn add_err(&mut self, err: ExpandError) {
  74         let prev_err = self.err.take();
  75         self.err = prev_err.or(Some(err));
  76         self.err_count += 1;
  77     }
  78 }
  79
  80 /// Matching errors are added to the `Match`.
  81 pub(super) fn match_(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
  82     let mut res = Match::default();
  83     let mut src = TtIter::new(src);
  84
  85     match_tokens(&mut res, pattern, &mut src);
  86
  87     if src.len() > 0 {
  88         res.unmatched_tts += src.len();
  89         res.add_err(err!("leftover tokens"));
  90     }
  91
  92     res
  93 }
  94
  95 fn match_tokens(res: &mut Match, pattern: &MetaTemplate, src: &mut TtIter) {
  96     for op in pattern.iter() {
  97         match op {
  98             Op::Leaf(lhs) => {
  99                 if let Err(err) = match_leaf(lhs, src) {
 100                     res.add_err(err);
 101                     continue;
 102                 }
 103             }
 104             Op::Subtree { tokens, delimiter: delim } => {
 105                 let rhs = match src.expect_subtree() {
 106                     Ok(s) => s,
 107                     Err(()) => {
 108                         res.add_err(err!("expected subtree"));
 109                         continue;
 110                     }
 111                 };
 112                 if delim.map(|it| it.kind) != rhs.delimiter_kind() {
 113                     res.add_err(err!("mismatched delimiter"));
 114                     continue;
 115                 }
 116                 let mut src = TtIter::new(rhs);
 117                 match_tokens(res, tokens, &mut src);
 118                 if src.len() > 0 {
 119                     res.add_err(err!("leftover tokens"));
 120                 }
 121             }
 122             Op::Var { name, kind, .. } => {
 123                 let kind = match kind {
 124                     Some(k) => k,
 125                     None => {
 126                         res.add_err(ExpandError::UnexpectedToken);
 127                         continue;
 128                     }
 129                 };
 130                 let ExpandResult { value: matched, err: match_err } =
 131                     match_meta_var(kind.as_str(), src);
 132                 match matched {
 133                     Some(fragment) => {
 134                         res.bindings.inner.insert(name.clone(), Binding::Fragment(fragment));
 135                     }
 136                     None if match_err.is_none() => res.bindings.push_optional(name),
 137                     _ => {}
 138                 }
 139                 if let Some(err) = match_err {
 140                     res.add_err(err);
 141                 }
 142             }
 143             Op::Repeat { tokens: subtree, kind, separator } => {
 144                 match_repeat(res, subtree, *kind, separator, src);
 145             }
 146         }
 147     }
 148 }
 149
 150 fn match_leaf(lhs: &tt::Leaf, src: &mut TtIter) -> Result<(), ExpandError> {
 151     let rhs = match src.expect_leaf() {
 152         Ok(l) => l,
 153         Err(()) => {
 154             return Err(err!("expected leaf: `{}`", lhs));
 155         }
 156     };
 157     match (lhs, rhs) {
 158         (
 159             tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
 160             tt::Leaf::Punct(tt::Punct { char: rhs, .. }),
 161         ) if lhs == rhs => (),
 162         (
 163             tt::Leaf::Ident(tt::Ident { text: lhs, .. }),
 164             tt::Leaf::Ident(tt::Ident { text: rhs, .. }),
 165         ) if lhs == rhs => (),
 166         (
 167             tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
 168             tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
 169         ) if lhs == rhs => (),
 170         _ => {
 171             return Err(ExpandError::UnexpectedToken);
 172         }
 173     }
 174
 175     Ok(())
 176 }
 177
 178 fn match_repeat(
 179     res: &mut Match,
 180     pattern: &MetaTemplate,
 181     kind: RepeatKind,
 182     separator: &Option<Separator>,
 183     src: &mut TtIter,
 184 ) {
 185     // Dirty hack to make macro-expansion terminate.
 186     // This should be replaced by a proper macro-by-example implementation
 187     let mut limit = 65536;
 188     let mut counter = 0;
 189
 190     for i in 0.. {
 191         let mut fork = src.clone();
 192
 193         if let Some(separator) = &separator {
 194             if i != 0 && !fork.eat_separator(separator) {
 195                 break;
 196             }
 197         }
 198
 199         let mut nested = Match::default();
 200         match_tokens(&mut nested, pattern, &mut fork);
 201         if nested.err.is_none() {
 202             limit -= 1;
 203             if limit == 0 {
 204                 log::warn!(
 205                     "match_lhs exceeded repeat pattern limit => {:#?}\n{:#?}\n{:#?}\n{:#?}",
 206                     pattern,
 207                     src,
 208                     kind,
 209                     separator
 210                 );
 211                 break;
 212             }
 213             *src = fork;
 214
 215             if let Err(err) = res.bindings.push_nested(counter, nested.bindings) {
 216                 res.add_err(err);
 217             }
 218             counter += 1;
 219             if counter == 1 {
 220                 if let RepeatKind::ZeroOrOne = kind {
 221                     break;
 222                 }
 223             }
 224         } else {
 225             break;
 226         }
 227     }
 228
 229     match (kind, counter) {
 230         (RepeatKind::OneOrMore, 0) => {
 231             res.add_err(ExpandError::UnexpectedToken);
 232         }
 233         (_, 0) => {
 234             // Collect all empty variables in subtrees
 235             let mut vars = Vec::new();
 236             collect_vars(&mut vars, pattern);
 237             for var in vars {
 238                 res.bindings.push_empty(&var)
 239             }
 240         }
 241         _ => (),
 242     }
 243 }
 244
 245 fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragment>> {
 246     let fragment = match kind {
 247         "path" => Path,
 248         "expr" => Expr,
 249         "ty" => Type,
 250         "pat" => Pattern,
 251         "stmt" => Statement,
 252         "block" => Block,
 253         "meta" => MetaItem,
 254         "item" => Item,
 255         _ => {
 256             let tt_result = match kind {
 257                 "ident" => input
 258                     .expect_ident()
 259                     .map(|ident| Some(tt::Leaf::from(ident.clone()).into()))
 260                     .map_err(|()| err!("expected ident")),
 261                 "tt" => input.expect_tt().map(Some).map_err(|()| err!()),
 262                 "lifetime" => input
 263                     .expect_lifetime()
 264                     .map(|tt| Some(tt))
 265                     .map_err(|()| err!("expected lifetime")),
 266                 "literal" => {
 267                     let neg = input.eat_char('-');
 268                     input
 269                         .expect_literal()
 270                         .map(|literal| {
 271                             let lit = tt::Leaf::from(literal.clone());
 272                             match neg {
 273                                 None => Some(lit.into()),
 274                                 Some(neg) => Some(tt::TokenTree::Subtree(tt::Subtree {
 275                                     delimiter: None,
 276                                     token_trees: vec![neg, lit.into()],
 277                                 })),
 278                             }
 279                         })
 280                         .map_err(|()| err!())
 281                 }
 282                 // `vis` is optional
 283                 "vis" => match input.eat_vis() {
 284                     Some(vis) => Ok(Some(vis)),
 285                     None => Ok(None),
 286                 },
 287                 _ => Err(ExpandError::UnexpectedToken),
 288             };
 289             return tt_result.map(|it| it.map(Fragment::Tokens)).into();
 290         }
 291     };
 292     let result = input.expect_fragment(fragment);
 293     result.map(|tt| if kind == "expr" { tt.map(Fragment::Ast) } else { tt.map(Fragment::Tokens) })
 294 }
 295
 296 fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &MetaTemplate) {
 297     for op in pattern.iter() {
 298         match op {
 299             Op::Var { name, .. } => buf.push(name.clone()),
 300             Op::Leaf(_) => (),
 301             Op::Subtree { tokens, .. } => collect_vars(buf, tokens),
 302             Op::Repeat { tokens, .. } => collect_vars(buf, tokens),
 303         }
 304     }
 305 }
 306
 307 impl<'a> TtIter<'a> {
 308     fn eat_separator(&mut self, separator: &Separator) -> bool {
 309         let mut fork = self.clone();
 310         let ok = match separator {
 311             Separator::Ident(lhs) => match fork.expect_ident() {
 312                 Ok(rhs) => rhs.text == lhs.text,
 313                 _ => false,
 314             },
 315             Separator::Literal(lhs) => match fork.expect_literal() {
 316                 Ok(rhs) => match rhs {
 317                     tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
 318                     tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
 319                     tt::Leaf::Punct(_) => false,
 320                 },
 321                 _ => false,
 322             },
 323             Separator::Puncts(lhss) => lhss.iter().all(|lhs| match fork.expect_punct() {
 324                 Ok(rhs) => rhs.char == lhs.char,
 325                 _ => false,
 326             }),
 327         };
 328         if ok {
 329             *self = fork;
 330         }
 331         ok
 332     }
 333
 334     fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
 335         match self.peek_n(0) {
 336             Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '\'' => {
 337                 return self.expect_lifetime();
 338             }
 339             _ => (),
 340         }
 341
 342         let tt = self.next().ok_or_else(|| ())?.clone();
 343         let punct = match tt {
 344             tt::TokenTree::Leaf(tt::Leaf::Punct(punct)) if punct.spacing == tt::Spacing::Joint => {
 345                 punct
 346             }
 347             _ => return Ok(tt),
 348         };
 349
 350         let (second, third) = match (self.peek_n(0), self.peek_n(1)) {
 351             (
 352                 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))),
 353                 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p3))),
 354             ) if p2.spacing == tt::Spacing::Joint => (p2.char, Some(p3.char)),
 355             (Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))), _) => (p2.char, None),
 356             _ => return Ok(tt),
 357         };
 358
 359         match (punct.char, second, third) {
 360             ('.', '.', Some('.'))
 361             | ('.', '.', Some('='))
 362             | ('<', '<', Some('='))
 363             | ('>', '>', Some('=')) => {
 364                 let tt2 = self.next().unwrap().clone();
 365                 let tt3 = self.next().unwrap().clone();
 366                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
 367             }
 368             ('-', '=', _)
 369             | ('-', '>', _)
 370             | (':', ':', _)
 371             | ('!', '=', _)
 372             | ('.', '.', _)
 373             | ('*', '=', _)
 374             | ('/', '=', _)
 375             | ('&', '&', _)
 376             | ('&', '=', _)
 377             | ('%', '=', _)
 378             | ('^', '=', _)
 379             | ('+', '=', _)
 380             | ('<', '<', _)
 381             | ('<', '=', _)
 382             | ('=', '=', _)
 383             | ('=', '>', _)
 384             | ('>', '=', _)
 385             | ('>', '>', _)
 386             | ('|', '=', _)
 387             | ('|', '|', _) => {
 388                 let tt2 = self.next().unwrap().clone();
 389                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
 390             }
 391             _ => Ok(tt),
 392         }
 393     }
 394
 395     fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
 396         let punct = self.expect_punct()?;
 397         if punct.char != '\'' {
 398             return Err(());
 399         }
 400         let ident = self.expect_ident()?;
 401
 402         Ok(tt::Subtree {
 403             delimiter: None,
 404             token_trees: vec![
 405                 tt::Leaf::Punct(*punct).into(),
 406                 tt::Leaf::Ident(ident.clone()).into(),
 407             ],
 408         }
 409         .into())
 410     }
 411
 412     fn expect_fragment(
 413         &mut self,
 414         fragment_kind: parser::FragmentKind,
 415     ) -> ExpandResult<Option<tt::TokenTree>> {
 416         struct OffsetTokenSink<'a> {
 417             cursor: Cursor<'a>,
 418             error: bool,
 419         }
 420
 421         impl<'a> TreeSink for OffsetTokenSink<'a> {
 422             fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
 423                 if kind == SyntaxKind::LIFETIME_IDENT {
 424                     n_tokens = 2;
 425                 }
 426                 for _ in 0..n_tokens {
 427                     self.cursor = self.cursor.bump_subtree();
 428                 }
 429             }
 430             fn start_node(&mut self, _kind: SyntaxKind) {}
 431             fn finish_node(&mut self) {}
 432             fn error(&mut self, _error: parser::ParseError) {
 433                 self.error = true;
 434             }
 435         }
 436
 437         let buffer = TokenBuffer::from_tokens(&self.inner.as_slice());
 438         let mut src = SubtreeTokenSource::new(&buffer);
 439         let mut sink = OffsetTokenSink { cursor: buffer.begin(), error: false };
 440
 441         parser::parse_fragment(&mut src, &mut sink, fragment_kind);
 442
 443         let mut err = None;
 444         if !sink.cursor.is_root() || sink.error {
 445             err = Some(err!("expected {:?}", fragment_kind));
 446         }
 447
 448         let mut curr = buffer.begin();
 449         let mut res = vec![];
 450
 451         if sink.cursor.is_root() {
 452             while curr != sink.cursor {
 453                 if let Some(token) = curr.token_tree() {
 454                     res.push(token);
 455                 }
 456                 curr = curr.bump();
 457             }
 458         }
 459         self.inner = self.inner.as_slice()[res.len()..].iter();
 460         if res.len() == 0 && err.is_none() {
 461             err = Some(err!("no tokens consumed"));
 462         }
 463         let res = match res.len() {
 464             1 => Some(res[0].cloned()),
 465             0 => None,
 466             _ => Some(tt::TokenTree::Subtree(tt::Subtree {
 467                 delimiter: None,
 468                 token_trees: res.into_iter().map(|it| it.cloned()).collect(),
 469             })),
 470         };
 471         ExpandResult { value: res, err }
 472     }
 473
 474     fn eat_vis(&mut self) -> Option<tt::TokenTree> {
 475         let mut fork = self.clone();
 476         match fork.expect_fragment(Visibility) {
 477             ExpandResult { value: tt, err: None } => {
 478                 *self = fork;
 479                 tt
 480             }
 481             ExpandResult { value: _, err: Some(_) } => None,
 482         }
 483     }
 484
 485     fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
 486         let mut fork = self.clone();
 487         match fork.expect_char(c) {
 488             Ok(_) => {
 489                 let tt = self.next().cloned();
 490                 *self = fork;
 491                 tt
 492             }
 493             Err(_) => None,
 494         }
 495     }
 496 }