compiler/rustc_parse/src/lexer/tokentrees.rs

   1 use super::{StringReader, UnmatchedBrace};
   2
   3 use rustc_ast::token::{self, DelimToken, Token};
   4 use rustc_ast::tokenstream::{
   5     DelimSpan,
   6     Spacing::{self, *},
   7     TokenStream, TokenTree, TreeAndSpacing,
   8 };
   9 use rustc_ast_pretty::pprust::token_to_string;
  10 use rustc_data_structures::fx::FxHashMap;
  11 use rustc_errors::PResult;
  12 use rustc_span::Span;
  13
  14 impl<'a> StringReader<'a> {
  15     pub(super) fn into_token_trees(self) -> (PResult<'a, TokenStream>, Vec<UnmatchedBrace>) {
  16         let mut tt_reader = TokenTreesReader {
  17             string_reader: self,
  18             token: Token::dummy(),
  19             open_braces: Vec::new(),
  20             unmatched_braces: Vec::new(),
  21             matching_delim_spans: Vec::new(),
  22             last_unclosed_found_span: None,
  23             last_delim_empty_block_spans: FxHashMap::default(),
  24             matching_block_spans: Vec::new(),
  25         };
  26         let res = tt_reader.parse_all_token_trees();
  27         (res, tt_reader.unmatched_braces)
  28     }
  29 }
  30
  31 struct TokenTreesReader<'a> {
  32     string_reader: StringReader<'a>,
  33     token: Token,
  34     /// Stack of open delimiters and their spans. Used for error message.
  35     open_braces: Vec<(token::DelimToken, Span)>,
  36     unmatched_braces: Vec<UnmatchedBrace>,
  37     /// The type and spans for all braces
  38     ///
  39     /// Used only for error recovery when arriving to EOF with mismatched braces.
  40     matching_delim_spans: Vec<(token::DelimToken, Span, Span)>,
  41     last_unclosed_found_span: Option<Span>,
  42     /// Collect empty block spans that might have been auto-inserted by editors.
  43     last_delim_empty_block_spans: FxHashMap<token::DelimToken, Span>,
  44     /// Collect the spans of braces (Open, Close). Used only
  45     /// for detecting if blocks are empty and only braces.
  46     matching_block_spans: Vec<(Span, Span)>,
  47 }
  48
  49 impl<'a> TokenTreesReader<'a> {
  50     // Parse a stream of tokens into a list of `TokenTree`s, up to an `Eof`.
  51     fn parse_all_token_trees(&mut self) -> PResult<'a, TokenStream> {
  52         let mut buf = TokenStreamBuilder::default();
  53
  54         self.bump();
  55         while self.token != token::Eof {
  56             buf.push(self.parse_token_tree()?);
  57         }
  58
  59         Ok(buf.into_token_stream())
  60     }
  61
  62     // Parse a stream of tokens into a list of `TokenTree`s, up to a `CloseDelim`.
  63     fn parse_token_trees_until_close_delim(&mut self) -> TokenStream {
  64         let mut buf = TokenStreamBuilder::default();
  65         loop {
  66             if let token::CloseDelim(..) = self.token.kind {
  67                 return buf.into_token_stream();
  68             }
  69
  70             match self.parse_token_tree() {
  71                 Ok(tree) => buf.push(tree),
  72                 Err(mut e) => {
  73                     e.emit();
  74                     return buf.into_token_stream();
  75                 }
  76             }
  77         }
  78     }
  79
  80     fn parse_token_tree(&mut self) -> PResult<'a, TreeAndSpacing> {
  81         let sm = self.string_reader.sess.source_map();
  82
  83         match self.token.kind {
  84             token::Eof => {
  85                 let msg = "this file contains an unclosed delimiter";
  86                 let mut err =
  87                     self.string_reader.sess.span_diagnostic.struct_span_err(self.token.span, msg);
  88                 for &(_, sp) in &self.open_braces {
  89                     err.span_label(sp, "unclosed delimiter");
  90                     self.unmatched_braces.push(UnmatchedBrace {
  91                         expected_delim: token::DelimToken::Brace,
  92                         found_delim: None,
  93                         found_span: self.token.span,
  94                         unclosed_span: Some(sp),
  95                         candidate_span: None,
  96                     });
  97                 }
  98
  99                 if let Some((delim, _)) = self.open_braces.last() {
 100                     if let Some((_, open_sp, close_sp)) =
 101                         self.matching_delim_spans.iter().find(|(d, open_sp, close_sp)| {
 102                             if let Some(close_padding) = sm.span_to_margin(*close_sp) {
 103                                 if let Some(open_padding) = sm.span_to_margin(*open_sp) {
 104                                     return delim == d && close_padding != open_padding;
 105                                 }
 106                             }
 107                             false
 108                         })
 109                     // these are in reverse order as they get inserted on close, but
 110                     {
 111                         // we want the last open/first close
 112                         err.span_label(*open_sp, "this delimiter might not be properly closed...");
 113                         err.span_label(
 114                             *close_sp,
 115                             "...as it matches this but it has different indentation",
 116                         );
 117                     }
 118                 }
 119                 Err(err)
 120             }
 121             token::OpenDelim(delim) => {
 122                 // The span for beginning of the delimited section
 123                 let pre_span = self.token.span;
 124
 125                 // Parse the open delimiter.
 126                 self.open_braces.push((delim, self.token.span));
 127                 self.bump();
 128
 129                 // Parse the token trees within the delimiters.
 130                 // We stop at any delimiter so we can try to recover if the user
 131                 // uses an incorrect delimiter.
 132                 let tts = self.parse_token_trees_until_close_delim();
 133
 134                 // Expand to cover the entire delimited token tree
 135                 let delim_span = DelimSpan::from_pair(pre_span, self.token.span);
 136
 137                 match self.token.kind {
 138                     // Correct delimiter.
 139                     token::CloseDelim(d) if d == delim => {
 140                         let (open_brace, open_brace_span) = self.open_braces.pop().unwrap();
 141                         let close_brace_span = self.token.span;
 142
 143                         if tts.is_empty() {
 144                             let empty_block_span = open_brace_span.to(close_brace_span);
 145                             if !sm.is_multiline(empty_block_span) {
 146                                 // Only track if the block is in the form of `{}`, otherwise it is
 147                                 // likely that it was written on purpose.
 148                                 self.last_delim_empty_block_spans.insert(delim, empty_block_span);
 149                             }
 150                         }
 151
 152                         //only add braces
 153                         if let (DelimToken::Brace, DelimToken::Brace) = (open_brace, delim) {
 154                             self.matching_block_spans.push((open_brace_span, close_brace_span));
 155                         }
 156
 157                         if self.open_braces.is_empty() {
 158                             // Clear up these spans to avoid suggesting them as we've found
 159                             // properly matched delimiters so far for an entire block.
 160                             self.matching_delim_spans.clear();
 161                         } else {
 162                             self.matching_delim_spans.push((
 163                                 open_brace,
 164                                 open_brace_span,
 165                                 close_brace_span,
 166                             ));
 167                         }
 168                         // Parse the closing delimiter.
 169                         self.bump();
 170                     }
 171                     // Incorrect delimiter.
 172                     token::CloseDelim(other) => {
 173                         let mut unclosed_delimiter = None;
 174                         let mut candidate = None;
 175
 176                         if self.last_unclosed_found_span != Some(self.token.span) {
 177                             // do not complain about the same unclosed delimiter multiple times
 178                             self.last_unclosed_found_span = Some(self.token.span);
 179                             // This is a conservative error: only report the last unclosed
 180                             // delimiter. The previous unclosed delimiters could actually be
 181                             // closed! The parser just hasn't gotten to them yet.
 182                             if let Some(&(_, sp)) = self.open_braces.last() {
 183                                 unclosed_delimiter = Some(sp);
 184                             };
 185                             if let Some(current_padding) = sm.span_to_margin(self.token.span) {
 186                                 for (brace, brace_span) in &self.open_braces {
 187                                     if let Some(padding) = sm.span_to_margin(*brace_span) {
 188                                         // high likelihood of these two corresponding
 189                                         if current_padding == padding && brace == &other {
 190                                             candidate = Some(*brace_span);
 191                                         }
 192                                     }
 193                                 }
 194                             }
 195                             let (tok, _) = self.open_braces.pop().unwrap();
 196                             self.unmatched_braces.push(UnmatchedBrace {
 197                                 expected_delim: tok,
 198                                 found_delim: Some(other),
 199                                 found_span: self.token.span,
 200                                 unclosed_span: unclosed_delimiter,
 201                                 candidate_span: candidate,
 202                             });
 203                         } else {
 204                             self.open_braces.pop();
 205                         }
 206
 207                         // If the incorrect delimiter matches an earlier opening
 208                         // delimiter, then don't consume it (it can be used to
 209                         // close the earlier one). Otherwise, consume it.
 210                         // E.g., we try to recover from:
 211                         // fn foo() {
 212                         //     bar(baz(
 213                         // }  // Incorrect delimiter but matches the earlier `{`
 214                         if !self.open_braces.iter().any(|&(b, _)| b == other) {
 215                             self.bump();
 216                         }
 217                     }
 218                     token::Eof => {
 219                         // Silently recover, the EOF token will be seen again
 220                         // and an error emitted then. Thus we don't pop from
 221                         // self.open_braces here.
 222                     }
 223                     _ => {}
 224                 }
 225
 226                 Ok(TokenTree::Delimited(delim_span, delim, tts).into())
 227             }
 228             token::CloseDelim(delim) => {
 229                 // An unexpected closing delimiter (i.e., there is no
 230                 // matching opening delimiter).
 231                 let token_str = token_to_string(&self.token);
 232                 let msg = format!("unexpected closing delimiter: `{}`", token_str);
 233                 let mut err =
 234                     self.string_reader.sess.span_diagnostic.struct_span_err(self.token.span, &msg);
 235
 236                 // Braces are added at the end, so the last element is the biggest block
 237                 if let Some(parent) = self.matching_block_spans.last() {
 238                     if let Some(span) = self.last_delim_empty_block_spans.remove(&delim) {
 239                         // Check if the (empty block) is in the last properly closed block
 240                         if (parent.0.to(parent.1)).contains(span) {
 241                             err.span_label(
 242                                 span,
 243                                 "block is empty, you might have not meant to close it",
 244                             );
 245                         } else {
 246                             err.span_label(parent.0, "this opening brace...");
 247
 248                             err.span_label(parent.1, "...matches this closing brace");
 249                         }
 250                     } else {
 251                         err.span_label(parent.0, "this opening brace...");
 252
 253                         err.span_label(parent.1, "...matches this closing brace");
 254                     }
 255                 }
 256
 257                 err.span_label(self.token.span, "unexpected closing delimiter");
 258                 Err(err)
 259             }
 260             _ => {
 261                 let tt = TokenTree::Token(self.token.take());
 262                 let mut spacing = self.bump();
 263                 if !self.token.is_op() {
 264                     spacing = Alone;
 265                 }
 266                 Ok((tt, spacing))
 267             }
 268         }
 269     }
 270
 271     fn bump(&mut self) -> Spacing {
 272         let (spacing, token) = self.string_reader.next_token();
 273         self.token = token;
 274         spacing
 275     }
 276 }
 277
 278 #[derive(Default)]
 279 struct TokenStreamBuilder {
 280     buf: Vec<TreeAndSpacing>,
 281 }
 282
 283 impl TokenStreamBuilder {
 284     fn push(&mut self, (tree, joint): TreeAndSpacing) {
 285         if let Some((TokenTree::Token(prev_token), Joint)) = self.buf.last() {
 286             if let TokenTree::Token(token) = &tree {
 287                 if let Some(glued) = prev_token.glue(token) {
 288                     self.buf.pop();
 289                     self.buf.push((TokenTree::Token(glued), joint));
 290                     return;
 291                 }
 292             }
 293         }
 294         self.buf.push((tree, joint))
 295     }
 296
 297     fn into_token_stream(self) -> TokenStream {
 298         TokenStream::new(self.buf)
 299     }
 300 }