]> git.lizzy.rs Git - rust.git/blob - src/librustc_parse/parser/mod.rs
Rollup merge of #75485 - RalfJung:pin, r=nagisa
[rust.git] / src / librustc_parse / parser / mod.rs
1 pub mod attr;
2 mod diagnostics;
3 mod expr;
4 mod generics;
5 mod item;
6 mod nonterminal;
7 mod pat;
8 mod path;
9 mod stmt;
10 mod ty;
11
12 use crate::lexer::UnmatchedBrace;
13 use diagnostics::Error;
14 pub use path::PathStyle;
15
16 use rustc_ast::ast::DUMMY_NODE_ID;
17 use rustc_ast::ast::{self, AttrStyle, AttrVec, Const, CrateSugar, Extern, Unsafe};
18 use rustc_ast::ast::{
19     Async, MacArgs, MacDelimiter, Mutability, StrLit, Visibility, VisibilityKind,
20 };
21 use rustc_ast::ptr::P;
22 use rustc_ast::token::{self, DelimToken, Token, TokenKind};
23 use rustc_ast::tokenstream::{self, DelimSpan, TokenStream, TokenTree, TreeAndJoint};
24 use rustc_ast_pretty::pprust;
25 use rustc_errors::{struct_span_err, Applicability, DiagnosticBuilder, FatalError, PResult};
26 use rustc_session::parse::ParseSess;
27 use rustc_span::source_map::{respan, Span, DUMMY_SP};
28 use rustc_span::symbol::{kw, sym, Ident, Symbol};
29 use tracing::debug;
30
31 use std::{cmp, mem, slice};
32
33 bitflags::bitflags! {
34     struct Restrictions: u8 {
35         const STMT_EXPR         = 1 << 0;
36         const NO_STRUCT_LITERAL = 1 << 1;
37     }
38 }
39
40 #[derive(Clone, Copy, PartialEq, Debug)]
41 enum SemiColonMode {
42     Break,
43     Ignore,
44     Comma,
45 }
46
47 #[derive(Clone, Copy, PartialEq, Debug)]
48 enum BlockMode {
49     Break,
50     Ignore,
51 }
52
53 /// Like `maybe_whole_expr`, but for things other than expressions.
54 #[macro_export]
55 macro_rules! maybe_whole {
56     ($p:expr, $constructor:ident, |$x:ident| $e:expr) => {
57         if let token::Interpolated(nt) = &$p.token.kind {
58             if let token::$constructor(x) = &**nt {
59                 let $x = x.clone();
60                 $p.bump();
61                 return Ok($e);
62             }
63         }
64     };
65 }
66
67 /// If the next tokens are ill-formed `$ty::` recover them as `<$ty>::`.
68 #[macro_export]
69 macro_rules! maybe_recover_from_interpolated_ty_qpath {
70     ($self: expr, $allow_qpath_recovery: expr) => {
71         if $allow_qpath_recovery && $self.look_ahead(1, |t| t == &token::ModSep) {
72             if let token::Interpolated(nt) = &$self.token.kind {
73                 if let token::NtTy(ty) = &**nt {
74                     let ty = ty.clone();
75                     $self.bump();
76                     return $self.maybe_recover_from_bad_qpath_stage_2($self.prev_token.span, ty);
77                 }
78             }
79         }
80     };
81 }
82
83 #[derive(Clone)]
84 pub struct Parser<'a> {
85     pub sess: &'a ParseSess,
86     /// The current token.
87     pub token: Token,
88     /// The previous token.
89     pub prev_token: Token,
90     restrictions: Restrictions,
91     expected_tokens: Vec<TokenType>,
92     token_cursor: TokenCursor,
93     desugar_doc_comments: bool,
94     /// This field is used to keep track of how many left angle brackets we have seen. This is
95     /// required in order to detect extra leading left angle brackets (`<` characters) and error
96     /// appropriately.
97     ///
98     /// See the comments in the `parse_path_segment` function for more details.
99     unmatched_angle_bracket_count: u32,
100     max_angle_bracket_count: u32,
101     /// A list of all unclosed delimiters found by the lexer. If an entry is used for error recovery
102     /// it gets removed from here. Every entry left at the end gets emitted as an independent
103     /// error.
104     pub(super) unclosed_delims: Vec<UnmatchedBrace>,
105     last_unexpected_token_span: Option<Span>,
106     /// Span pointing at the `:` for the last type ascription the parser has seen, and whether it
107     /// looked like it could have been a mistyped path or literal `Option:Some(42)`).
108     pub last_type_ascription: Option<(Span, bool /* likely path typo */)>,
109     /// If present, this `Parser` is not parsing Rust code but rather a macro call.
110     subparser_name: Option<&'static str>,
111 }
112
113 impl<'a> Drop for Parser<'a> {
114     fn drop(&mut self) {
115         emit_unclosed_delims(&mut self.unclosed_delims, &self.sess);
116     }
117 }
118
119 #[derive(Clone)]
120 struct TokenCursor {
121     frame: TokenCursorFrame,
122     stack: Vec<TokenCursorFrame>,
123     cur_token: Option<TreeAndJoint>,
124     collecting: Option<Collecting>,
125 }
126
127 #[derive(Clone)]
128 struct TokenCursorFrame {
129     delim: token::DelimToken,
130     span: DelimSpan,
131     open_delim: bool,
132     tree_cursor: tokenstream::Cursor,
133     close_delim: bool,
134 }
135
136 /// Used to track additional state needed by `collect_tokens`
137 #[derive(Clone, Debug)]
138 struct Collecting {
139     /// Holds the current tokens captured during the most
140     /// recent call to `collect_tokens`
141     buf: Vec<TreeAndJoint>,
142     /// The depth of the `TokenCursor` stack at the time
143     /// collection was started. When we encounter a `TokenTree::Delimited`,
144     /// we want to record the `TokenTree::Delimited` itself,
145     /// but *not* any of the inner tokens while we are inside
146     /// the new frame (this would cause us to record duplicate tokens).
147     ///
148     /// This `depth` fields tracks stack depth we are recording tokens.
149     /// Only tokens encountered at this depth will be recorded. See
150     /// `TokenCursor::next` for more details.
151     depth: usize,
152 }
153
154 impl TokenCursorFrame {
155     fn new(span: DelimSpan, delim: DelimToken, tts: &TokenStream) -> Self {
156         TokenCursorFrame {
157             delim,
158             span,
159             open_delim: delim == token::NoDelim,
160             tree_cursor: tts.clone().into_trees(),
161             close_delim: delim == token::NoDelim,
162         }
163     }
164 }
165
166 impl TokenCursor {
167     fn next(&mut self) -> Token {
168         loop {
169             let tree = if !self.frame.open_delim {
170                 self.frame.open_delim = true;
171                 TokenTree::open_tt(self.frame.span, self.frame.delim).into()
172             } else if let Some(tree) = self.frame.tree_cursor.next_with_joint() {
173                 tree
174             } else if !self.frame.close_delim {
175                 self.frame.close_delim = true;
176                 TokenTree::close_tt(self.frame.span, self.frame.delim).into()
177             } else if let Some(frame) = self.stack.pop() {
178                 self.frame = frame;
179                 continue;
180             } else {
181                 return Token::new(token::Eof, DUMMY_SP);
182             };
183
184             // Don't set an open delimiter as our current token - we want
185             // to leave it as the full `TokenTree::Delimited` from the previous
186             // iteration of this loop
187             if !matches!(tree.0, TokenTree::Token(Token { kind: TokenKind::OpenDelim(_), .. })) {
188                 self.cur_token = Some(tree.clone());
189             }
190
191             if let Some(collecting) = &mut self.collecting {
192                 if collecting.depth == self.stack.len() {
193                     debug!(
194                         "TokenCursor::next():  collected {:?} at depth {:?}",
195                         tree,
196                         self.stack.len()
197                     );
198                     collecting.buf.push(tree.clone())
199                 }
200             }
201
202             match tree.0 {
203                 TokenTree::Token(token) => return token,
204                 TokenTree::Delimited(sp, delim, tts) => {
205                     let frame = TokenCursorFrame::new(sp, delim, &tts);
206                     self.stack.push(mem::replace(&mut self.frame, frame));
207                 }
208             }
209         }
210     }
211
212     fn next_desugared(&mut self) -> Token {
213         let (data, attr_style, sp) = match self.next() {
214             Token { kind: token::DocComment(_, attr_style, data), span } => {
215                 (data, attr_style, span)
216             }
217             tok => return tok,
218         };
219
220         // Searches for the occurrences of `"#*` and returns the minimum number of `#`s
221         // required to wrap the text.
222         let mut num_of_hashes = 0;
223         let mut count = 0;
224         for ch in data.as_str().chars() {
225             count = match ch {
226                 '"' => 1,
227                 '#' if count > 0 => count + 1,
228                 _ => 0,
229             };
230             num_of_hashes = cmp::max(num_of_hashes, count);
231         }
232
233         let delim_span = DelimSpan::from_single(sp);
234         let body = TokenTree::Delimited(
235             delim_span,
236             token::Bracket,
237             [
238                 TokenTree::token(token::Ident(sym::doc, false), sp),
239                 TokenTree::token(token::Eq, sp),
240                 TokenTree::token(TokenKind::lit(token::StrRaw(num_of_hashes), data, None), sp),
241             ]
242             .iter()
243             .cloned()
244             .collect::<TokenStream>(),
245         );
246
247         self.stack.push(mem::replace(
248             &mut self.frame,
249             TokenCursorFrame::new(
250                 delim_span,
251                 token::NoDelim,
252                 &if attr_style == AttrStyle::Inner {
253                     [TokenTree::token(token::Pound, sp), TokenTree::token(token::Not, sp), body]
254                         .iter()
255                         .cloned()
256                         .collect::<TokenStream>()
257                 } else {
258                     [TokenTree::token(token::Pound, sp), body]
259                         .iter()
260                         .cloned()
261                         .collect::<TokenStream>()
262                 },
263             ),
264         ));
265
266         self.next()
267     }
268 }
269
270 #[derive(Clone, PartialEq)]
271 enum TokenType {
272     Token(TokenKind),
273     Keyword(Symbol),
274     Operator,
275     Lifetime,
276     Ident,
277     Path,
278     Type,
279     Const,
280 }
281
282 impl TokenType {
283     fn to_string(&self) -> String {
284         match *self {
285             TokenType::Token(ref t) => format!("`{}`", pprust::token_kind_to_string(t)),
286             TokenType::Keyword(kw) => format!("`{}`", kw),
287             TokenType::Operator => "an operator".to_string(),
288             TokenType::Lifetime => "lifetime".to_string(),
289             TokenType::Ident => "identifier".to_string(),
290             TokenType::Path => "path".to_string(),
291             TokenType::Type => "type".to_string(),
292             TokenType::Const => "const".to_string(),
293         }
294     }
295 }
296
297 #[derive(Copy, Clone, Debug)]
298 enum TokenExpectType {
299     Expect,
300     NoExpect,
301 }
302
303 /// A sequence separator.
304 struct SeqSep {
305     /// The separator token.
306     sep: Option<TokenKind>,
307     /// `true` if a trailing separator is allowed.
308     trailing_sep_allowed: bool,
309 }
310
311 impl SeqSep {
312     fn trailing_allowed(t: TokenKind) -> SeqSep {
313         SeqSep { sep: Some(t), trailing_sep_allowed: true }
314     }
315
316     fn none() -> SeqSep {
317         SeqSep { sep: None, trailing_sep_allowed: false }
318     }
319 }
320
321 pub enum FollowedByType {
322     Yes,
323     No,
324 }
325
326 fn token_descr_opt(token: &Token) -> Option<&'static str> {
327     Some(match token.kind {
328         _ if token.is_special_ident() => "reserved identifier",
329         _ if token.is_used_keyword() => "keyword",
330         _ if token.is_unused_keyword() => "reserved keyword",
331         token::DocComment(..) => "doc comment",
332         _ => return None,
333     })
334 }
335
336 pub(super) fn token_descr(token: &Token) -> String {
337     let token_str = pprust::token_to_string(token);
338     match token_descr_opt(token) {
339         Some(prefix) => format!("{} `{}`", prefix, token_str),
340         _ => format!("`{}`", token_str),
341     }
342 }
343
344 impl<'a> Parser<'a> {
345     pub fn new(
346         sess: &'a ParseSess,
347         tokens: TokenStream,
348         desugar_doc_comments: bool,
349         subparser_name: Option<&'static str>,
350     ) -> Self {
351         let mut parser = Parser {
352             sess,
353             token: Token::dummy(),
354             prev_token: Token::dummy(),
355             restrictions: Restrictions::empty(),
356             expected_tokens: Vec::new(),
357             token_cursor: TokenCursor {
358                 frame: TokenCursorFrame::new(DelimSpan::dummy(), token::NoDelim, &tokens),
359                 stack: Vec::new(),
360                 cur_token: None,
361                 collecting: None,
362             },
363             desugar_doc_comments,
364             unmatched_angle_bracket_count: 0,
365             max_angle_bracket_count: 0,
366             unclosed_delims: Vec::new(),
367             last_unexpected_token_span: None,
368             last_type_ascription: None,
369             subparser_name,
370         };
371
372         // Make parser point to the first token.
373         parser.bump();
374
375         parser
376     }
377
378     fn next_tok(&mut self, fallback_span: Span) -> Token {
379         let mut next = if self.desugar_doc_comments {
380             self.token_cursor.next_desugared()
381         } else {
382             self.token_cursor.next()
383         };
384         if next.span.is_dummy() {
385             // Tweak the location for better diagnostics, but keep syntactic context intact.
386             next.span = fallback_span.with_ctxt(next.span.ctxt());
387         }
388         next
389     }
390
391     crate fn unexpected<T>(&mut self) -> PResult<'a, T> {
392         match self.expect_one_of(&[], &[]) {
393             Err(e) => Err(e),
394             // We can get `Ok(true)` from `recover_closing_delimiter`
395             // which is called in `expected_one_of_not_found`.
396             Ok(_) => FatalError.raise(),
397         }
398     }
399
400     /// Expects and consumes the token `t`. Signals an error if the next token is not `t`.
401     pub fn expect(&mut self, t: &TokenKind) -> PResult<'a, bool /* recovered */> {
402         if self.expected_tokens.is_empty() {
403             if self.token == *t {
404                 self.bump();
405                 Ok(false)
406             } else {
407                 self.unexpected_try_recover(t)
408             }
409         } else {
410             self.expect_one_of(slice::from_ref(t), &[])
411         }
412     }
413
414     /// Expect next token to be edible or inedible token.  If edible,
415     /// then consume it; if inedible, then return without consuming
416     /// anything.  Signal a fatal error if next token is unexpected.
417     pub fn expect_one_of(
418         &mut self,
419         edible: &[TokenKind],
420         inedible: &[TokenKind],
421     ) -> PResult<'a, bool /* recovered */> {
422         if edible.contains(&self.token.kind) {
423             self.bump();
424             Ok(false)
425         } else if inedible.contains(&self.token.kind) {
426             // leave it in the input
427             Ok(false)
428         } else if self.last_unexpected_token_span == Some(self.token.span) {
429             FatalError.raise();
430         } else {
431             self.expected_one_of_not_found(edible, inedible)
432         }
433     }
434
435     // Public for rustfmt usage.
436     pub fn parse_ident(&mut self) -> PResult<'a, Ident> {
437         self.parse_ident_common(true)
438     }
439
440     fn parse_ident_common(&mut self, recover: bool) -> PResult<'a, Ident> {
441         match self.token.ident() {
442             Some((ident, is_raw)) => {
443                 if !is_raw && ident.is_reserved() {
444                     let mut err = self.expected_ident_found();
445                     if recover {
446                         err.emit();
447                     } else {
448                         return Err(err);
449                     }
450                 }
451                 self.bump();
452                 Ok(ident)
453             }
454             _ => Err(match self.prev_token.kind {
455                 TokenKind::DocComment(..) => {
456                     self.span_fatal_err(self.prev_token.span, Error::UselessDocComment)
457                 }
458                 _ => self.expected_ident_found(),
459             }),
460         }
461     }
462
463     /// Checks if the next token is `tok`, and returns `true` if so.
464     ///
465     /// This method will automatically add `tok` to `expected_tokens` if `tok` is not
466     /// encountered.
467     fn check(&mut self, tok: &TokenKind) -> bool {
468         let is_present = self.token == *tok;
469         if !is_present {
470             self.expected_tokens.push(TokenType::Token(tok.clone()));
471         }
472         is_present
473     }
474
475     /// Consumes a token 'tok' if it exists. Returns whether the given token was present.
476     pub fn eat(&mut self, tok: &TokenKind) -> bool {
477         let is_present = self.check(tok);
478         if is_present {
479             self.bump()
480         }
481         is_present
482     }
483
484     /// If the next token is the given keyword, returns `true` without eating it.
485     /// An expectation is also added for diagnostics purposes.
486     fn check_keyword(&mut self, kw: Symbol) -> bool {
487         self.expected_tokens.push(TokenType::Keyword(kw));
488         self.token.is_keyword(kw)
489     }
490
491     /// If the next token is the given keyword, eats it and returns `true`.
492     /// Otherwise, returns `false`. An expectation is also added for diagnostics purposes.
493     // Public for rustfmt usage.
494     pub fn eat_keyword(&mut self, kw: Symbol) -> bool {
495         if self.check_keyword(kw) {
496             self.bump();
497             true
498         } else {
499             false
500         }
501     }
502
503     fn eat_keyword_noexpect(&mut self, kw: Symbol) -> bool {
504         if self.token.is_keyword(kw) {
505             self.bump();
506             true
507         } else {
508             false
509         }
510     }
511
512     /// If the given word is not a keyword, signals an error.
513     /// If the next token is not the given word, signals an error.
514     /// Otherwise, eats it.
515     fn expect_keyword(&mut self, kw: Symbol) -> PResult<'a, ()> {
516         if !self.eat_keyword(kw) { self.unexpected() } else { Ok(()) }
517     }
518
519     /// Is the given keyword `kw` followed by a non-reserved identifier?
520     fn is_kw_followed_by_ident(&self, kw: Symbol) -> bool {
521         self.token.is_keyword(kw) && self.look_ahead(1, |t| t.is_ident() && !t.is_reserved_ident())
522     }
523
524     fn check_or_expected(&mut self, ok: bool, typ: TokenType) -> bool {
525         if ok {
526             true
527         } else {
528             self.expected_tokens.push(typ);
529             false
530         }
531     }
532
533     fn check_ident(&mut self) -> bool {
534         self.check_or_expected(self.token.is_ident(), TokenType::Ident)
535     }
536
537     fn check_path(&mut self) -> bool {
538         self.check_or_expected(self.token.is_path_start(), TokenType::Path)
539     }
540
541     fn check_type(&mut self) -> bool {
542         self.check_or_expected(self.token.can_begin_type(), TokenType::Type)
543     }
544
545     fn check_const_arg(&mut self) -> bool {
546         self.check_or_expected(self.token.can_begin_const_arg(), TokenType::Const)
547     }
548
549     /// Checks to see if the next token is either `+` or `+=`.
550     /// Otherwise returns `false`.
551     fn check_plus(&mut self) -> bool {
552         self.check_or_expected(
553             self.token.is_like_plus(),
554             TokenType::Token(token::BinOp(token::Plus)),
555         )
556     }
557
558     /// Eats the expected token if it's present possibly breaking
559     /// compound tokens like multi-character operators in process.
560     /// Returns `true` if the token was eaten.
561     fn break_and_eat(&mut self, expected: TokenKind) -> bool {
562         if self.token.kind == expected {
563             self.bump();
564             return true;
565         }
566         match self.token.kind.break_two_token_op() {
567             Some((first, second)) if first == expected => {
568                 let first_span = self.sess.source_map().start_point(self.token.span);
569                 let second_span = self.token.span.with_lo(first_span.hi());
570                 self.token = Token::new(first, first_span);
571                 self.bump_with(Token::new(second, second_span));
572                 true
573             }
574             _ => {
575                 self.expected_tokens.push(TokenType::Token(expected));
576                 false
577             }
578         }
579     }
580
581     /// Eats `+` possibly breaking tokens like `+=` in process.
582     fn eat_plus(&mut self) -> bool {
583         self.break_and_eat(token::BinOp(token::Plus))
584     }
585
586     /// Eats `&` possibly breaking tokens like `&&` in process.
587     /// Signals an error if `&` is not eaten.
588     fn expect_and(&mut self) -> PResult<'a, ()> {
589         if self.break_and_eat(token::BinOp(token::And)) { Ok(()) } else { self.unexpected() }
590     }
591
592     /// Eats `|` possibly breaking tokens like `||` in process.
593     /// Signals an error if `|` was not eaten.
594     fn expect_or(&mut self) -> PResult<'a, ()> {
595         if self.break_and_eat(token::BinOp(token::Or)) { Ok(()) } else { self.unexpected() }
596     }
597
598     /// Eats `<` possibly breaking tokens like `<<` in process.
599     fn eat_lt(&mut self) -> bool {
600         let ate = self.break_and_eat(token::Lt);
601         if ate {
602             // See doc comment for `unmatched_angle_bracket_count`.
603             self.unmatched_angle_bracket_count += 1;
604             self.max_angle_bracket_count += 1;
605             debug!("eat_lt: (increment) count={:?}", self.unmatched_angle_bracket_count);
606         }
607         ate
608     }
609
610     /// Eats `<` possibly breaking tokens like `<<` in process.
611     /// Signals an error if `<` was not eaten.
612     fn expect_lt(&mut self) -> PResult<'a, ()> {
613         if self.eat_lt() { Ok(()) } else { self.unexpected() }
614     }
615
616     /// Eats `>` possibly breaking tokens like `>>` in process.
617     /// Signals an error if `>` was not eaten.
618     fn expect_gt(&mut self) -> PResult<'a, ()> {
619         if self.break_and_eat(token::Gt) {
620             // See doc comment for `unmatched_angle_bracket_count`.
621             if self.unmatched_angle_bracket_count > 0 {
622                 self.unmatched_angle_bracket_count -= 1;
623                 debug!("expect_gt: (decrement) count={:?}", self.unmatched_angle_bracket_count);
624             }
625             Ok(())
626         } else {
627             self.unexpected()
628         }
629     }
630
631     fn expect_any_with_type(&mut self, kets: &[&TokenKind], expect: TokenExpectType) -> bool {
632         kets.iter().any(|k| match expect {
633             TokenExpectType::Expect => self.check(k),
634             TokenExpectType::NoExpect => self.token == **k,
635         })
636     }
637
638     fn parse_seq_to_before_tokens<T>(
639         &mut self,
640         kets: &[&TokenKind],
641         sep: SeqSep,
642         expect: TokenExpectType,
643         mut f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
644     ) -> PResult<'a, (Vec<T>, bool /* trailing */, bool /* recovered */)> {
645         let mut first = true;
646         let mut recovered = false;
647         let mut trailing = false;
648         let mut v = vec![];
649         while !self.expect_any_with_type(kets, expect) {
650             if let token::CloseDelim(..) | token::Eof = self.token.kind {
651                 break;
652             }
653             if let Some(ref t) = sep.sep {
654                 if first {
655                     first = false;
656                 } else {
657                     match self.expect(t) {
658                         Ok(false) => {}
659                         Ok(true) => {
660                             recovered = true;
661                             break;
662                         }
663                         Err(mut expect_err) => {
664                             let sp = self.prev_token.span.shrink_to_hi();
665                             let token_str = pprust::token_kind_to_string(t);
666
667                             // Attempt to keep parsing if it was a similar separator.
668                             if let Some(ref tokens) = t.similar_tokens() {
669                                 if tokens.contains(&self.token.kind) {
670                                     self.bump();
671                                 }
672                             }
673
674                             // If this was a missing `@` in a binding pattern
675                             // bail with a suggestion
676                             // https://github.com/rust-lang/rust/issues/72373
677                             if self.prev_token.is_ident() && self.token.kind == token::DotDot {
678                                 let msg = format!(
679                                     "if you meant to bind the contents of \
680                                     the rest of the array pattern into `{}`, use `@`",
681                                     pprust::token_to_string(&self.prev_token)
682                                 );
683                                 expect_err
684                                     .span_suggestion_verbose(
685                                         self.prev_token.span.shrink_to_hi().until(self.token.span),
686                                         &msg,
687                                         " @ ".to_string(),
688                                         Applicability::MaybeIncorrect,
689                                     )
690                                     .emit();
691                                 break;
692                             }
693
694                             // Attempt to keep parsing if it was an omitted separator.
695                             match f(self) {
696                                 Ok(t) => {
697                                     // Parsed successfully, therefore most probably the code only
698                                     // misses a separator.
699                                     expect_err
700                                         .span_suggestion_short(
701                                             self.sess.source_map().next_point(sp),
702                                             &format!("missing `{}`", token_str),
703                                             token_str,
704                                             Applicability::MaybeIncorrect,
705                                         )
706                                         .emit();
707
708                                     v.push(t);
709                                     continue;
710                                 }
711                                 Err(mut e) => {
712                                     // Parsing failed, therefore it must be something more serious
713                                     // than just a missing separator.
714                                     expect_err.emit();
715
716                                     e.cancel();
717                                     break;
718                                 }
719                             }
720                         }
721                     }
722                 }
723             }
724             if sep.trailing_sep_allowed && self.expect_any_with_type(kets, expect) {
725                 trailing = true;
726                 break;
727             }
728
729             let t = f(self)?;
730             v.push(t);
731         }
732
733         Ok((v, trailing, recovered))
734     }
735
736     /// Parses a sequence, not including the closing delimiter. The function
737     /// `f` must consume tokens until reaching the next separator or
738     /// closing bracket.
739     fn parse_seq_to_before_end<T>(
740         &mut self,
741         ket: &TokenKind,
742         sep: SeqSep,
743         f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
744     ) -> PResult<'a, (Vec<T>, bool, bool)> {
745         self.parse_seq_to_before_tokens(&[ket], sep, TokenExpectType::Expect, f)
746     }
747
748     /// Parses a sequence, including the closing delimiter. The function
749     /// `f` must consume tokens until reaching the next separator or
750     /// closing bracket.
751     fn parse_seq_to_end<T>(
752         &mut self,
753         ket: &TokenKind,
754         sep: SeqSep,
755         f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
756     ) -> PResult<'a, (Vec<T>, bool /* trailing */)> {
757         let (val, trailing, recovered) = self.parse_seq_to_before_end(ket, sep, f)?;
758         if !recovered {
759             self.eat(ket);
760         }
761         Ok((val, trailing))
762     }
763
764     /// Parses a sequence, including the closing delimiter. The function
765     /// `f` must consume tokens until reaching the next separator or
766     /// closing bracket.
767     fn parse_unspanned_seq<T>(
768         &mut self,
769         bra: &TokenKind,
770         ket: &TokenKind,
771         sep: SeqSep,
772         f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
773     ) -> PResult<'a, (Vec<T>, bool)> {
774         self.expect(bra)?;
775         self.parse_seq_to_end(ket, sep, f)
776     }
777
778     fn parse_delim_comma_seq<T>(
779         &mut self,
780         delim: DelimToken,
781         f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
782     ) -> PResult<'a, (Vec<T>, bool)> {
783         self.parse_unspanned_seq(
784             &token::OpenDelim(delim),
785             &token::CloseDelim(delim),
786             SeqSep::trailing_allowed(token::Comma),
787             f,
788         )
789     }
790
791     fn parse_paren_comma_seq<T>(
792         &mut self,
793         f: impl FnMut(&mut Parser<'a>) -> PResult<'a, T>,
794     ) -> PResult<'a, (Vec<T>, bool)> {
795         self.parse_delim_comma_seq(token::Paren, f)
796     }
797
798     /// Advance the parser by one token using provided token as the next one.
799     fn bump_with(&mut self, next_token: Token) {
800         // Bumping after EOF is a bad sign, usually an infinite loop.
801         if self.prev_token.kind == TokenKind::Eof {
802             let msg = "attempted to bump the parser past EOF (may be stuck in a loop)";
803             self.span_bug(self.token.span, msg);
804         }
805
806         // Update the current and previous tokens.
807         self.prev_token = mem::replace(&mut self.token, next_token);
808
809         // Diagnostics.
810         self.expected_tokens.clear();
811     }
812
813     /// Advance the parser by one token.
814     pub fn bump(&mut self) {
815         let next_token = self.next_tok(self.token.span);
816         self.bump_with(next_token);
817     }
818
819     /// Look-ahead `dist` tokens of `self.token` and get access to that token there.
820     /// When `dist == 0` then the current token is looked at.
821     pub fn look_ahead<R>(&self, dist: usize, looker: impl FnOnce(&Token) -> R) -> R {
822         if dist == 0 {
823             return looker(&self.token);
824         }
825
826         let frame = &self.token_cursor.frame;
827         looker(&match frame.tree_cursor.look_ahead(dist - 1) {
828             Some(tree) => match tree {
829                 TokenTree::Token(token) => token,
830                 TokenTree::Delimited(dspan, delim, _) => {
831                     Token::new(token::OpenDelim(delim), dspan.open)
832                 }
833             },
834             None => Token::new(token::CloseDelim(frame.delim), frame.span.close),
835         })
836     }
837
838     /// Returns whether any of the given keywords are `dist` tokens ahead of the current one.
839     fn is_keyword_ahead(&self, dist: usize, kws: &[Symbol]) -> bool {
840         self.look_ahead(dist, |t| kws.iter().any(|&kw| t.is_keyword(kw)))
841     }
842
843     /// Parses asyncness: `async` or nothing.
844     fn parse_asyncness(&mut self) -> Async {
845         if self.eat_keyword(kw::Async) {
846             let span = self.prev_token.uninterpolated_span();
847             Async::Yes { span, closure_id: DUMMY_NODE_ID, return_impl_trait_id: DUMMY_NODE_ID }
848         } else {
849             Async::No
850         }
851     }
852
853     /// Parses unsafety: `unsafe` or nothing.
854     fn parse_unsafety(&mut self) -> Unsafe {
855         if self.eat_keyword(kw::Unsafe) {
856             Unsafe::Yes(self.prev_token.uninterpolated_span())
857         } else {
858             Unsafe::No
859         }
860     }
861
862     /// Parses constness: `const` or nothing.
863     fn parse_constness(&mut self) -> Const {
864         if self.eat_keyword(kw::Const) {
865             Const::Yes(self.prev_token.uninterpolated_span())
866         } else {
867             Const::No
868         }
869     }
870
871     /// Parses mutability (`mut` or nothing).
872     fn parse_mutability(&mut self) -> Mutability {
873         if self.eat_keyword(kw::Mut) { Mutability::Mut } else { Mutability::Not }
874     }
875
876     /// Possibly parses mutability (`const` or `mut`).
877     fn parse_const_or_mut(&mut self) -> Option<Mutability> {
878         if self.eat_keyword(kw::Mut) {
879             Some(Mutability::Mut)
880         } else if self.eat_keyword(kw::Const) {
881             Some(Mutability::Not)
882         } else {
883             None
884         }
885     }
886
887     fn parse_field_name(&mut self) -> PResult<'a, Ident> {
888         if let token::Literal(token::Lit { kind: token::Integer, symbol, suffix }) = self.token.kind
889         {
890             self.expect_no_suffix(self.token.span, "a tuple index", suffix);
891             self.bump();
892             Ok(Ident::new(symbol, self.prev_token.span))
893         } else {
894             self.parse_ident_common(false)
895         }
896     }
897
898     fn parse_mac_args(&mut self) -> PResult<'a, P<MacArgs>> {
899         self.parse_mac_args_common(true).map(P)
900     }
901
902     fn parse_attr_args(&mut self) -> PResult<'a, MacArgs> {
903         self.parse_mac_args_common(false)
904     }
905
906     fn parse_mac_args_common(&mut self, delimited_only: bool) -> PResult<'a, MacArgs> {
907         Ok(
908             if self.check(&token::OpenDelim(DelimToken::Paren))
909                 || self.check(&token::OpenDelim(DelimToken::Bracket))
910                 || self.check(&token::OpenDelim(DelimToken::Brace))
911             {
912                 match self.parse_token_tree() {
913                     TokenTree::Delimited(dspan, delim, tokens) =>
914                     // We've confirmed above that there is a delimiter so unwrapping is OK.
915                     {
916                         MacArgs::Delimited(dspan, MacDelimiter::from_token(delim).unwrap(), tokens)
917                     }
918                     _ => unreachable!(),
919                 }
920             } else if !delimited_only {
921                 if self.eat(&token::Eq) {
922                     let eq_span = self.prev_token.span;
923                     let mut is_interpolated_expr = false;
924                     if let token::Interpolated(nt) = &self.token.kind {
925                         if let token::NtExpr(..) = **nt {
926                             is_interpolated_expr = true;
927                         }
928                     }
929                     let token_tree = if is_interpolated_expr {
930                         // We need to accept arbitrary interpolated expressions to continue
931                         // supporting things like `doc = $expr` that work on stable.
932                         // Non-literal interpolated expressions are rejected after expansion.
933                         self.parse_token_tree()
934                     } else {
935                         self.parse_unsuffixed_lit()?.token_tree()
936                     };
937
938                     MacArgs::Eq(eq_span, token_tree.into())
939                 } else {
940                     MacArgs::Empty
941                 }
942             } else {
943                 return self.unexpected();
944             },
945         )
946     }
947
948     fn parse_or_use_outer_attributes(
949         &mut self,
950         already_parsed_attrs: Option<AttrVec>,
951     ) -> PResult<'a, AttrVec> {
952         if let Some(attrs) = already_parsed_attrs {
953             Ok(attrs)
954         } else {
955             self.parse_outer_attributes().map(|a| a.into())
956         }
957     }
958
959     /// Parses a single token tree from the input.
960     pub(crate) fn parse_token_tree(&mut self) -> TokenTree {
961         match self.token.kind {
962             token::OpenDelim(..) => {
963                 let frame = mem::replace(
964                     &mut self.token_cursor.frame,
965                     self.token_cursor.stack.pop().unwrap(),
966                 );
967                 self.token = Token::new(TokenKind::CloseDelim(frame.delim), frame.span.close);
968                 self.bump();
969                 TokenTree::Delimited(frame.span, frame.delim, frame.tree_cursor.stream)
970             }
971             token::CloseDelim(_) | token::Eof => unreachable!(),
972             _ => {
973                 self.bump();
974                 TokenTree::Token(self.prev_token.clone())
975             }
976         }
977     }
978
979     /// Parses a stream of tokens into a list of `TokenTree`s, up to EOF.
980     pub fn parse_all_token_trees(&mut self) -> PResult<'a, Vec<TokenTree>> {
981         let mut tts = Vec::new();
982         while self.token != token::Eof {
983             tts.push(self.parse_token_tree());
984         }
985         Ok(tts)
986     }
987
988     pub fn parse_tokens(&mut self) -> TokenStream {
989         let mut result = Vec::new();
990         loop {
991             match self.token.kind {
992                 token::Eof | token::CloseDelim(..) => break,
993                 _ => result.push(self.parse_token_tree().into()),
994             }
995         }
996         TokenStream::new(result)
997     }
998
999     /// Evaluates the closure with restrictions in place.
1000     ///
1001     /// Afters the closure is evaluated, restrictions are reset.
1002     fn with_res<T>(&mut self, res: Restrictions, f: impl FnOnce(&mut Self) -> T) -> T {
1003         let old = self.restrictions;
1004         self.restrictions = res;
1005         let res = f(self);
1006         self.restrictions = old;
1007         res
1008     }
1009
1010     fn is_crate_vis(&self) -> bool {
1011         self.token.is_keyword(kw::Crate) && self.look_ahead(1, |t| t != &token::ModSep)
1012     }
1013
1014     /// Parses `pub`, `pub(crate)` and `pub(in path)` plus shortcuts `crate` for `pub(crate)`,
1015     /// `pub(self)` for `pub(in self)` and `pub(super)` for `pub(in super)`.
1016     /// If the following element can't be a tuple (i.e., it's a function definition), then
1017     /// it's not a tuple struct field), and the contents within the parentheses isn't valid,
1018     /// so emit a proper diagnostic.
1019     pub(crate) fn parse_visibility(&mut self, fbt: FollowedByType) -> PResult<'a, Visibility> {
1020         maybe_whole!(self, NtVis, |x| x);
1021
1022         self.expected_tokens.push(TokenType::Keyword(kw::Crate));
1023         if self.is_crate_vis() {
1024             self.bump(); // `crate`
1025             self.sess.gated_spans.gate(sym::crate_visibility_modifier, self.prev_token.span);
1026             return Ok(respan(self.prev_token.span, VisibilityKind::Crate(CrateSugar::JustCrate)));
1027         }
1028
1029         if !self.eat_keyword(kw::Pub) {
1030             // We need a span for our `Spanned<VisibilityKind>`, but there's inherently no
1031             // keyword to grab a span from for inherited visibility; an empty span at the
1032             // beginning of the current token would seem to be the "Schelling span".
1033             return Ok(respan(self.token.span.shrink_to_lo(), VisibilityKind::Inherited));
1034         }
1035         let lo = self.prev_token.span;
1036
1037         if self.check(&token::OpenDelim(token::Paren)) {
1038             // We don't `self.bump()` the `(` yet because this might be a struct definition where
1039             // `()` or a tuple might be allowed. For example, `struct Struct(pub (), pub (usize));`.
1040             // Because of this, we only `bump` the `(` if we're assured it is appropriate to do so
1041             // by the following tokens.
1042             if self.is_keyword_ahead(1, &[kw::Crate]) && self.look_ahead(2, |t| t != &token::ModSep)
1043             // account for `pub(crate::foo)`
1044             {
1045                 // Parse `pub(crate)`.
1046                 self.bump(); // `(`
1047                 self.bump(); // `crate`
1048                 self.expect(&token::CloseDelim(token::Paren))?; // `)`
1049                 let vis = VisibilityKind::Crate(CrateSugar::PubCrate);
1050                 return Ok(respan(lo.to(self.prev_token.span), vis));
1051             } else if self.is_keyword_ahead(1, &[kw::In]) {
1052                 // Parse `pub(in path)`.
1053                 self.bump(); // `(`
1054                 self.bump(); // `in`
1055                 let path = self.parse_path(PathStyle::Mod)?; // `path`
1056                 self.expect(&token::CloseDelim(token::Paren))?; // `)`
1057                 let vis = VisibilityKind::Restricted { path: P(path), id: ast::DUMMY_NODE_ID };
1058                 return Ok(respan(lo.to(self.prev_token.span), vis));
1059             } else if self.look_ahead(2, |t| t == &token::CloseDelim(token::Paren))
1060                 && self.is_keyword_ahead(1, &[kw::Super, kw::SelfLower])
1061             {
1062                 // Parse `pub(self)` or `pub(super)`.
1063                 self.bump(); // `(`
1064                 let path = self.parse_path(PathStyle::Mod)?; // `super`/`self`
1065                 self.expect(&token::CloseDelim(token::Paren))?; // `)`
1066                 let vis = VisibilityKind::Restricted { path: P(path), id: ast::DUMMY_NODE_ID };
1067                 return Ok(respan(lo.to(self.prev_token.span), vis));
1068             } else if let FollowedByType::No = fbt {
1069                 // Provide this diagnostic if a type cannot follow;
1070                 // in particular, if this is not a tuple struct.
1071                 self.recover_incorrect_vis_restriction()?;
1072                 // Emit diagnostic, but continue with public visibility.
1073             }
1074         }
1075
1076         Ok(respan(lo, VisibilityKind::Public))
1077     }
1078
1079     /// Recovery for e.g. `pub(something) fn ...` or `struct X { pub(something) y: Z }`
1080     fn recover_incorrect_vis_restriction(&mut self) -> PResult<'a, ()> {
1081         self.bump(); // `(`
1082         let path = self.parse_path(PathStyle::Mod)?;
1083         self.expect(&token::CloseDelim(token::Paren))?; // `)`
1084
1085         let msg = "incorrect visibility restriction";
1086         let suggestion = r##"some possible visibility restrictions are:
1087 `pub(crate)`: visible only on the current crate
1088 `pub(super)`: visible only in the current module's parent
1089 `pub(in path::to::module)`: visible only on the specified path"##;
1090
1091         let path_str = pprust::path_to_string(&path);
1092
1093         struct_span_err!(self.sess.span_diagnostic, path.span, E0704, "{}", msg)
1094             .help(suggestion)
1095             .span_suggestion(
1096                 path.span,
1097                 &format!("make this visible only to module `{}` with `in`", path_str),
1098                 format!("in {}", path_str),
1099                 Applicability::MachineApplicable,
1100             )
1101             .emit();
1102
1103         Ok(())
1104     }
1105
1106     /// Parses `extern string_literal?`.
1107     fn parse_extern(&mut self) -> PResult<'a, Extern> {
1108         Ok(if self.eat_keyword(kw::Extern) {
1109             Extern::from_abi(self.parse_abi())
1110         } else {
1111             Extern::None
1112         })
1113     }
1114
1115     /// Parses a string literal as an ABI spec.
1116     fn parse_abi(&mut self) -> Option<StrLit> {
1117         match self.parse_str_lit() {
1118             Ok(str_lit) => Some(str_lit),
1119             Err(Some(lit)) => match lit.kind {
1120                 ast::LitKind::Err(_) => None,
1121                 _ => {
1122                     self.struct_span_err(lit.span, "non-string ABI literal")
1123                         .span_suggestion(
1124                             lit.span,
1125                             "specify the ABI with a string literal",
1126                             "\"C\"".to_string(),
1127                             Applicability::MaybeIncorrect,
1128                         )
1129                         .emit();
1130                     None
1131                 }
1132             },
1133             Err(None) => None,
1134         }
1135     }
1136
1137     /// Records all tokens consumed by the provided callback,
1138     /// including the current token. These tokens are collected
1139     /// into a `TokenStream`, and returned along with the result
1140     /// of the callback.
1141     ///
1142     /// Note: If your callback consumes an opening delimiter
1143     /// (including the case where you call `collect_tokens`
1144     /// when the current token is an opening delimeter),
1145     /// you must also consume the corresponding closing delimiter.
1146     ///
1147     /// That is, you can consume
1148     /// `something ([{ }])` or `([{}])`, but not `([{}]`
1149     ///
1150     /// This restriction shouldn't be an issue in practice,
1151     /// since this function is used to record the tokens for
1152     /// a parsed AST item, which always has matching delimiters.
1153     pub fn collect_tokens<R>(
1154         &mut self,
1155         f: impl FnOnce(&mut Self) -> PResult<'a, R>,
1156     ) -> PResult<'a, (R, TokenStream)> {
1157         // Record all tokens we parse when parsing this item.
1158         let tokens: Vec<TreeAndJoint> = self.token_cursor.cur_token.clone().into_iter().collect();
1159         debug!("collect_tokens: starting with {:?}", tokens);
1160
1161         // We need special handling for the case where `collect_tokens` is called
1162         // on an opening delimeter (e.g. '('). At this point, we have already pushed
1163         // a new frame - however, we want to record the original `TokenTree::Delimited`,
1164         // for consistency with the case where we start recording one token earlier.
1165         // See `TokenCursor::next` to see how `cur_token` is set up.
1166         let prev_depth =
1167             if matches!(self.token_cursor.cur_token, Some((TokenTree::Delimited(..), _))) {
1168                 if self.token_cursor.stack.is_empty() {
1169                     // There is nothing below us in the stack that
1170                     // the function could consume, so the only thing it can legally
1171                     // capture is the entire contents of the current frame.
1172                     return Ok((f(self)?, TokenStream::new(tokens)));
1173                 }
1174                 // We have already recorded the full `TokenTree::Delimited` when we created
1175                 // our `tokens` vector at the start of this function. We are now inside
1176                 // a new frame corresponding to the `TokenTree::Delimited` we already recoreded.
1177                 // We don't want to record any of the tokens inside this frame, since they
1178                 // will be duplicates of the tokens nested inside the `TokenTree::Delimited`.
1179                 // Therefore, we set our recording depth to the *previous* frame. This allows
1180                 // us to record a sequence like: `(foo).bar()`: the `(foo)` will be recored
1181                 // as our initial `cur_token`, while the `.bar()` will be recored after we
1182                 // pop the `(foo)` frame.
1183                 self.token_cursor.stack.len() - 1
1184             } else {
1185                 self.token_cursor.stack.len()
1186             };
1187         let prev_collecting =
1188             self.token_cursor.collecting.replace(Collecting { buf: tokens, depth: prev_depth });
1189
1190         let ret = f(self);
1191
1192         let mut collected_tokens = if let Some(collecting) = self.token_cursor.collecting.take() {
1193             collecting.buf
1194         } else {
1195             let msg = "our vector went away?";
1196             debug!("collect_tokens: {}", msg);
1197             self.sess.span_diagnostic.delay_span_bug(self.token.span, &msg);
1198             // This can happen due to a bad interaction of two unrelated recovery mechanisms
1199             // with mismatched delimiters *and* recovery lookahead on the likely typo
1200             // `pub ident(` (#62895, different but similar to the case above).
1201             return Ok((ret?, TokenStream::default()));
1202         };
1203
1204         debug!("collect_tokens: got raw tokens {:?}", collected_tokens);
1205
1206         // If we're not at EOF our current token wasn't actually consumed by
1207         // `f`, but it'll still be in our list that we pulled out. In that case
1208         // put it back.
1209         let extra_token = if self.token != token::Eof { collected_tokens.pop() } else { None };
1210
1211         if let Some(mut collecting) = prev_collecting {
1212             // If we were previously collecting at the same depth,
1213             // then the previous call to `collect_tokens` needs to see
1214             // the tokens we just recorded.
1215             //
1216             // If we were previously recording at an lower `depth`,
1217             // then the previous `collect_tokens` call already recorded
1218             // this entire frame in the form of a `TokenTree::Delimited`,
1219             // so there is nothing else for us to do.
1220             if collecting.depth == prev_depth {
1221                 collecting.buf.extend(collected_tokens.iter().cloned());
1222                 collecting.buf.extend(extra_token);
1223                 debug!("collect_tokens: updating previous buf to {:?}", collecting);
1224             }
1225             self.token_cursor.collecting = Some(collecting)
1226         }
1227
1228         Ok((ret?, TokenStream::new(collected_tokens)))
1229     }
1230
1231     /// `::{` or `::*`
1232     fn is_import_coupler(&mut self) -> bool {
1233         self.check(&token::ModSep)
1234             && self.look_ahead(1, |t| {
1235                 *t == token::OpenDelim(token::Brace) || *t == token::BinOp(token::Star)
1236             })
1237     }
1238 }
1239
1240 crate fn make_unclosed_delims_error(
1241     unmatched: UnmatchedBrace,
1242     sess: &ParseSess,
1243 ) -> Option<DiagnosticBuilder<'_>> {
1244     // `None` here means an `Eof` was found. We already emit those errors elsewhere, we add them to
1245     // `unmatched_braces` only for error recovery in the `Parser`.
1246     let found_delim = unmatched.found_delim?;
1247     let mut err = sess.span_diagnostic.struct_span_err(
1248         unmatched.found_span,
1249         &format!(
1250             "mismatched closing delimiter: `{}`",
1251             pprust::token_kind_to_string(&token::CloseDelim(found_delim)),
1252         ),
1253     );
1254     err.span_label(unmatched.found_span, "mismatched closing delimiter");
1255     if let Some(sp) = unmatched.candidate_span {
1256         err.span_label(sp, "closing delimiter possibly meant for this");
1257     }
1258     if let Some(sp) = unmatched.unclosed_span {
1259         err.span_label(sp, "unclosed delimiter");
1260     }
1261     Some(err)
1262 }
1263
1264 pub fn emit_unclosed_delims(unclosed_delims: &mut Vec<UnmatchedBrace>, sess: &ParseSess) {
1265     *sess.reached_eof.borrow_mut() |=
1266         unclosed_delims.iter().any(|unmatched_delim| unmatched_delim.found_delim.is_none());
1267     for unmatched in unclosed_delims.drain(..) {
1268         if let Some(mut e) = make_unclosed_delims_error(unmatched, sess) {
1269             e.emit();
1270         }
1271     }
1272 }