compiler/rustc_parse/src/lexer/tokentrees.rs

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