crates/mbe/src/parser.rs

   1 //! Parser recognizes special macro syntax, `$var` and `$(repeat)*`, in token
   2 //! trees.
   3
   4 use smallvec::SmallVec;
   5 use syntax::SmolStr;
   6 use tt::Delimiter;
   7
   8 use crate::{tt_iter::TtIter, ParseError};
   9
  10 #[derive(Clone, Debug, PartialEq, Eq)]
  11 pub(crate) struct MetaTemplate(pub(crate) Vec<Op>);
  12
  13 #[derive(Debug, Clone, Copy)]
  14 pub(crate) enum OpDelimited<'a> {
  15     Op(&'a Op),
  16     Open,
  17     Close,
  18 }
  19
  20 #[derive(Debug, Clone, Copy)]
  21 pub(crate) struct OpDelimitedIter<'a> {
  22     inner: &'a Vec<Op>,
  23     delimited: Option<&'a Delimiter>,
  24     idx: usize,
  25 }
  26
  27 impl<'a> OpDelimitedIter<'a> {
  28     pub(crate) fn is_eof(&self) -> bool {
  29         let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
  30         self.idx >= len
  31     }
  32
  33     pub(crate) fn peek(&self) -> Option<OpDelimited<'a>> {
  34         match self.delimited {
  35             None => self.inner.get(self.idx).map(OpDelimited::Op),
  36             Some(_) => match self.idx {
  37                 0 => Some(OpDelimited::Open),
  38                 i if i == self.inner.len() + 1 => Some(OpDelimited::Close),
  39                 i => self.inner.get(i - 1).map(OpDelimited::Op),
  40             },
  41         }
  42     }
  43
  44     pub(crate) fn reset(&self) -> Self {
  45         Self { inner: &self.inner, idx: 0, delimited: self.delimited }
  46     }
  47 }
  48
  49 impl<'a> Iterator for OpDelimitedIter<'a> {
  50     type Item = OpDelimited<'a>;
  51
  52     fn next(&mut self) -> Option<Self::Item> {
  53         let res = self.peek();
  54         self.idx += 1;
  55         res
  56     }
  57
  58     fn size_hint(&self) -> (usize, Option<usize>) {
  59         let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
  60         let remain = len.checked_sub(self.idx).unwrap_or(0);
  61         (remain, Some(remain))
  62     }
  63 }
  64
  65 impl<'a> MetaTemplate {
  66     pub(crate) fn iter(&self) -> impl Iterator<Item = &Op> {
  67         self.0.iter()
  68     }
  69
  70     pub(crate) fn iter_delimited(
  71         &'a self,
  72         delimited: Option<&'a Delimiter>,
  73     ) -> OpDelimitedIter<'a> {
  74         OpDelimitedIter { inner: &self.0, idx: 0, delimited }
  75     }
  76 }
  77
  78 #[derive(Clone, Debug, PartialEq, Eq)]
  79 pub(crate) enum Op {
  80     Var { name: SmolStr, kind: Option<SmolStr>, id: tt::TokenId },
  81     Repeat { tokens: MetaTemplate, kind: RepeatKind, separator: Option<Separator> },
  82     Leaf(tt::Leaf),
  83     Subtree { tokens: MetaTemplate, delimiter: Option<Delimiter> },
  84 }
  85
  86 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  87 pub(crate) enum RepeatKind {
  88     ZeroOrMore,
  89     OneOrMore,
  90     ZeroOrOne,
  91 }
  92
  93 #[derive(Clone, Debug, Eq)]
  94 pub(crate) enum Separator {
  95     Literal(tt::Literal),
  96     Ident(tt::Ident),
  97     Puncts(SmallVec<[tt::Punct; 3]>),
  98 }
  99
 100 // Note that when we compare a Separator, we just care about its textual value.
 101 impl PartialEq for Separator {
 102     fn eq(&self, other: &Separator) -> bool {
 103         use Separator::*;
 104
 105         match (self, other) {
 106             (Ident(ref a), Ident(ref b)) => a.text == b.text,
 107             (Literal(ref a), Literal(ref b)) => a.text == b.text,
 108             (Puncts(ref a), Puncts(ref b)) if a.len() == b.len() => {
 109                 let a_iter = a.iter().map(|a| a.char);
 110                 let b_iter = b.iter().map(|b| b.char);
 111                 a_iter.eq(b_iter)
 112             }
 113             _ => false,
 114         }
 115     }
 116 }
 117
 118 impl Separator {
 119     pub(crate) fn tt_count(&self) -> usize {
 120         match self {
 121             Separator::Literal(_) => 1,
 122             Separator::Ident(_) => 1,
 123             Separator::Puncts(it) => it.len(),
 124         }
 125     }
 126 }
 127
 128 pub(crate) fn parse_template(template: &tt::Subtree) -> Result<Vec<Op>, ParseError> {
 129     parse_inner(&template, Mode::Template).into_iter().collect()
 130 }
 131
 132 pub(crate) fn parse_pattern(pattern: &tt::Subtree) -> Result<Vec<Op>, ParseError> {
 133     parse_inner(&pattern, Mode::Pattern).into_iter().collect()
 134 }
 135
 136 #[derive(Clone, Copy)]
 137 enum Mode {
 138     Pattern,
 139     Template,
 140 }
 141
 142 fn parse_inner(tt: &tt::Subtree, mode: Mode) -> Vec<Result<Op, ParseError>> {
 143     let mut src = TtIter::new(&tt);
 144     std::iter::from_fn(move || {
 145         let first = src.next()?;
 146         Some(next_op(first, &mut src, mode))
 147     })
 148     .collect()
 149 }
 150
 151 macro_rules! err {
 152     ($($tt:tt)*) => {
 153         ParseError::UnexpectedToken(($($tt)*).to_string())
 154     };
 155 }
 156
 157 macro_rules! bail {
 158     ($($tt:tt)*) => {
 159         return Err(err!($($tt)*))
 160     };
 161 }
 162
 163 fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Result<Op, ParseError> {
 164     let res = match first {
 165         tt::TokenTree::Leaf(leaf @ tt::Leaf::Punct(tt::Punct { char: '$', .. })) => {
 166             // Note that the '$' itself is a valid token inside macro_rules.
 167             let second = match src.next() {
 168                 None => return Ok(Op::Leaf(leaf.clone())),
 169                 Some(it) => it,
 170             };
 171             match second {
 172                 tt::TokenTree::Subtree(subtree) => {
 173                     let (separator, kind) = parse_repeat(src)?;
 174                     let tokens = parse_inner(&subtree, mode)
 175                         .into_iter()
 176                         .collect::<Result<Vec<Op>, ParseError>>()?;
 177                     Op::Repeat { tokens: MetaTemplate(tokens), separator, kind }
 178                 }
 179                 tt::TokenTree::Leaf(leaf) => match leaf {
 180                     tt::Leaf::Punct(punct) => {
 181                         static UNDERSCORE: SmolStr = SmolStr::new_inline("_");
 182
 183                         if punct.char != '_' {
 184                             return Err(ParseError::Expected("_".to_string()));
 185                         }
 186                         let name = UNDERSCORE.clone();
 187                         let kind = eat_fragment_kind(src, mode)?;
 188                         let id = punct.id;
 189                         Op::Var { name, kind, id }
 190                     }
 191                     tt::Leaf::Ident(ident) if ident.text == "crate" => {
 192                         // We simply produce identifier `$crate` here. And it will be resolved when lowering ast to Path.
 193                         Op::Leaf(tt::Leaf::from(tt::Ident { text: "$crate".into(), id: ident.id }))
 194                     }
 195                     tt::Leaf::Ident(ident) => {
 196                         let name = ident.text.clone();
 197                         let kind = eat_fragment_kind(src, mode)?;
 198                         let id = ident.id;
 199                         Op::Var { name, kind, id }
 200                     }
 201                     tt::Leaf::Literal(lit) => {
 202                         if is_boolean_literal(&lit) {
 203                             let name = lit.text.clone();
 204                             let kind = eat_fragment_kind(src, mode)?;
 205                             let id = lit.id;
 206                             Op::Var { name, kind, id }
 207                         } else {
 208                             bail!("bad var 2");
 209                         }
 210                     }
 211                 },
 212             }
 213         }
 214         tt::TokenTree::Leaf(tt) => Op::Leaf(tt.clone()),
 215         tt::TokenTree::Subtree(subtree) => {
 216             let tokens =
 217                 parse_inner(&subtree, mode).into_iter().collect::<Result<Vec<Op>, ParseError>>()?;
 218             Op::Subtree { tokens: MetaTemplate(tokens), delimiter: subtree.delimiter }
 219         }
 220     };
 221     Ok(res)
 222 }
 223
 224 fn eat_fragment_kind<'a>(src: &mut TtIter<'a>, mode: Mode) -> Result<Option<SmolStr>, ParseError> {
 225     if let Mode::Pattern = mode {
 226         src.expect_char(':').map_err(|()| err!("bad fragment specifier 1"))?;
 227         let ident = src.expect_ident().map_err(|()| err!("bad fragment specifier 1"))?;
 228         return Ok(Some(ident.text.clone()));
 229     };
 230     Ok(None)
 231 }
 232
 233 fn is_boolean_literal(lit: &tt::Literal) -> bool {
 234     matches!(lit.text.as_str(), "true" | "false")
 235 }
 236
 237 fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), ParseError> {
 238     let mut separator = Separator::Puncts(SmallVec::new());
 239     for tt in src {
 240         let tt = match tt {
 241             tt::TokenTree::Leaf(leaf) => leaf,
 242             tt::TokenTree::Subtree(_) => return Err(ParseError::InvalidRepeat),
 243         };
 244         let has_sep = match &separator {
 245             Separator::Puncts(puncts) => !puncts.is_empty(),
 246             _ => true,
 247         };
 248         match tt {
 249             tt::Leaf::Ident(_) | tt::Leaf::Literal(_) if has_sep => {
 250                 return Err(ParseError::InvalidRepeat)
 251             }
 252             tt::Leaf::Ident(ident) => separator = Separator::Ident(ident.clone()),
 253             tt::Leaf::Literal(lit) => separator = Separator::Literal(lit.clone()),
 254             tt::Leaf::Punct(punct) => {
 255                 let repeat_kind = match punct.char {
 256                     '*' => RepeatKind::ZeroOrMore,
 257                     '+' => RepeatKind::OneOrMore,
 258                     '?' => RepeatKind::ZeroOrOne,
 259                     _ => {
 260                         match &mut separator {
 261                             Separator::Puncts(puncts) => {
 262                                 if puncts.len() == 3 {
 263                                     return Err(ParseError::InvalidRepeat);
 264                                 }
 265                                 puncts.push(*punct)
 266                             }
 267                             _ => return Err(ParseError::InvalidRepeat),
 268                         }
 269                         continue;
 270                     }
 271                 };
 272                 let separator = if has_sep { Some(separator) } else { None };
 273                 return Ok((separator, repeat_kind));
 274             }
 275         }
 276     }
 277     Err(ParseError::InvalidRepeat)
 278 }