src/librustc_parse/parser/path.rs

   1 use super::{Parser, TokenType};
   2 use crate::maybe_whole;
   3 use rustc_errors::{PResult, Applicability, pluralize};
   4 use syntax::ast::{self, QSelf, Path, PathSegment, Ident, ParenthesizedArgs, AngleBracketedArgs};
   5 use syntax::ast::{AnonConst, GenericArg, AssocTyConstraint, AssocTyConstraintKind, BlockCheckMode};
   6 use syntax::token::{self, Token};
   7 use syntax_pos::source_map::{Span, BytePos};
   8 use syntax_pos::symbol::{kw, sym};
   9
  10 use std::mem;
  11 use log::debug;
  12
  13 /// Specifies how to parse a path.
  14 #[derive(Copy, Clone, PartialEq)]
  15 pub enum PathStyle {
  16     /// In some contexts, notably in expressions, paths with generic arguments are ambiguous
  17     /// with something else. For example, in expressions `segment < ....` can be interpreted
  18     /// as a comparison and `segment ( ....` can be interpreted as a function call.
  19     /// In all such contexts the non-path interpretation is preferred by default for practical
  20     /// reasons, but the path interpretation can be forced by the disambiguator `::`, e.g.
  21     /// `x<y>` - comparisons, `x::<y>` - unambiguously a path.
  22     Expr,
  23     /// In other contexts, notably in types, no ambiguity exists and paths can be written
  24     /// without the disambiguator, e.g., `x<y>` - unambiguously a path.
  25     /// Paths with disambiguators are still accepted, `x::<Y>` - unambiguously a path too.
  26     Type,
  27     /// A path with generic arguments disallowed, e.g., `foo::bar::Baz`, used in imports,
  28     /// visibilities or attributes.
  29     /// Technically, this variant is unnecessary and e.g., `Expr` can be used instead
  30     /// (paths in "mod" contexts have to be checked later for absence of generic arguments
  31     /// anyway, due to macros), but it is used to avoid weird suggestions about expected
  32     /// tokens when something goes wrong.
  33     Mod,
  34 }
  35
  36 impl<'a> Parser<'a> {
  37     /// Parses a qualified path.
  38     /// Assumes that the leading `<` has been parsed already.
  39     ///
  40     /// `qualified_path = <type [as trait_ref]>::path`
  41     ///
  42     /// # Examples
  43     /// `<T>::default`
  44     /// `<T as U>::a`
  45     /// `<T as U>::F::a<S>` (without disambiguator)
  46     /// `<T as U>::F::a::<S>` (with disambiguator)
  47     pub(super) fn parse_qpath(&mut self, style: PathStyle) -> PResult<'a, (QSelf, Path)> {
  48         let lo = self.prev_span;
  49         let ty = self.parse_ty()?;
  50
  51         // `path` will contain the prefix of the path up to the `>`,
  52         // if any (e.g., `U` in the `<T as U>::*` examples
  53         // above). `path_span` has the span of that path, or an empty
  54         // span in the case of something like `<T>::Bar`.
  55         let (mut path, path_span);
  56         if self.eat_keyword(kw::As) {
  57             let path_lo = self.token.span;
  58             path = self.parse_path(PathStyle::Type)?;
  59             path_span = path_lo.to(self.prev_span);
  60         } else {
  61             path_span = self.token.span.to(self.token.span);
  62             path = ast::Path { segments: Vec::new(), span: path_span };
  63         }
  64
  65         // See doc comment for `unmatched_angle_bracket_count`.
  66         self.expect(&token::Gt)?;
  67         if self.unmatched_angle_bracket_count > 0 {
  68             self.unmatched_angle_bracket_count -= 1;
  69             debug!("parse_qpath: (decrement) count={:?}", self.unmatched_angle_bracket_count);
  70         }
  71
  72         self.expect(&token::ModSep)?;
  73
  74         let qself = QSelf { ty, path_span, position: path.segments.len() };
  75         self.parse_path_segments(&mut path.segments, style)?;
  76
  77         Ok((qself, Path { segments: path.segments, span: lo.to(self.prev_span) }))
  78     }
  79
  80     /// Parses simple paths.
  81     ///
  82     /// `path = [::] segment+`
  83     /// `segment = ident | ident[::]<args> | ident[::](args) [-> type]`
  84     ///
  85     /// # Examples
  86     /// `a::b::C<D>` (without disambiguator)
  87     /// `a::b::C::<D>` (with disambiguator)
  88     /// `Fn(Args)` (without disambiguator)
  89     /// `Fn::(Args)` (with disambiguator)
  90     pub fn parse_path(&mut self, style: PathStyle) -> PResult<'a, Path> {
  91         maybe_whole!(self, NtPath, |path| {
  92             if style == PathStyle::Mod &&
  93                path.segments.iter().any(|segment| segment.args.is_some()) {
  94                 self.diagnostic().span_err(path.span, "unexpected generic arguments in path");
  95             }
  96             path
  97         });
  98
  99         let lo = self.meta_var_span.unwrap_or(self.token.span);
 100         let mut segments = Vec::new();
 101         let mod_sep_ctxt = self.token.span.ctxt();
 102         if self.eat(&token::ModSep) {
 103             segments.push(PathSegment::path_root(lo.shrink_to_lo().with_ctxt(mod_sep_ctxt)));
 104         }
 105         self.parse_path_segments(&mut segments, style)?;
 106
 107         Ok(Path { segments, span: lo.to(self.prev_span) })
 108     }
 109
 110     pub(super) fn parse_path_segments(
 111         &mut self,
 112         segments: &mut Vec<PathSegment>,
 113         style: PathStyle,
 114     ) -> PResult<'a, ()> {
 115         loop {
 116             let segment = self.parse_path_segment(style)?;
 117             if style == PathStyle::Expr {
 118                 // In order to check for trailing angle brackets, we must have finished
 119                 // recursing (`parse_path_segment` can indirectly call this function),
 120                 // that is, the next token must be the highlighted part of the below example:
 121                 //
 122                 // `Foo::<Bar as Baz<T>>::Qux`
 123                 //                      ^ here
 124                 //
 125                 // As opposed to the below highlight (if we had only finished the first
 126                 // recursion):
 127                 //
 128                 // `Foo::<Bar as Baz<T>>::Qux`
 129                 //                     ^ here
 130                 //
 131                 // `PathStyle::Expr` is only provided at the root invocation and never in
 132                 // `parse_path_segment` to recurse and therefore can be checked to maintain
 133                 // this invariant.
 134                 self.check_trailing_angle_brackets(&segment, token::ModSep);
 135             }
 136             segments.push(segment);
 137
 138             if self.is_import_coupler() || !self.eat(&token::ModSep) {
 139                 return Ok(());
 140             }
 141         }
 142     }
 143
 144     pub(super) fn parse_path_segment(&mut self, style: PathStyle) -> PResult<'a, PathSegment> {
 145         let ident = self.parse_path_segment_ident()?;
 146
 147         let is_args_start = |token: &Token| match token.kind {
 148             token::Lt | token::BinOp(token::Shl) | token::OpenDelim(token::Paren)
 149             | token::LArrow => true,
 150             _ => false,
 151         };
 152         let check_args_start = |this: &mut Self| {
 153             this.expected_tokens.extend_from_slice(
 154                 &[TokenType::Token(token::Lt), TokenType::Token(token::OpenDelim(token::Paren))]
 155             );
 156             is_args_start(&this.token)
 157         };
 158
 159         Ok(if style == PathStyle::Type && check_args_start(self) ||
 160               style != PathStyle::Mod && self.check(&token::ModSep)
 161                                       && self.look_ahead(1, |t| is_args_start(t)) {
 162             // We use `style == PathStyle::Expr` to check if this is in a recursion or not. If
 163             // it isn't, then we reset the unmatched angle bracket count as we're about to start
 164             // parsing a new path.
 165             if style == PathStyle::Expr {
 166                 self.unmatched_angle_bracket_count = 0;
 167                 self.max_angle_bracket_count = 0;
 168             }
 169
 170             // Generic arguments are found - `<`, `(`, `::<` or `::(`.
 171             self.eat(&token::ModSep);
 172             let lo = self.token.span;
 173             let args = if self.eat_lt() {
 174                 // `<'a, T, A = U>`
 175                 let (args, constraints) =
 176                     self.parse_generic_args_with_leaning_angle_bracket_recovery(style, lo)?;
 177                 self.expect_gt()?;
 178                 let span = lo.to(self.prev_span);
 179                 AngleBracketedArgs { args, constraints, span }.into()
 180             } else {
 181                 // `(T, U) -> R`
 182                 let (inputs, _) = self.parse_paren_comma_seq(|p| p.parse_ty())?;
 183                 let span = ident.span.to(self.prev_span);
 184                 let output = self.parse_ret_ty(false, false)?;
 185                 ParenthesizedArgs { inputs, output, span }.into()
 186             };
 187
 188             PathSegment { ident, args, id: ast::DUMMY_NODE_ID }
 189         } else {
 190             // Generic arguments are not found.
 191             PathSegment::from_ident(ident)
 192         })
 193     }
 194
 195     pub(super) fn parse_path_segment_ident(&mut self) -> PResult<'a, Ident> {
 196         match self.token.kind {
 197             token::Ident(name, _) if name.is_path_segment_keyword() => {
 198                 let span = self.token.span;
 199                 self.bump();
 200                 Ok(Ident::new(name, span))
 201             }
 202             _ => self.parse_ident(),
 203         }
 204     }
 205
 206     /// Parses generic args (within a path segment) with recovery for extra leading angle brackets.
 207     /// For the purposes of understanding the parsing logic of generic arguments, this function
 208     /// can be thought of being the same as just calling `self.parse_generic_args()` if the source
 209     /// had the correct amount of leading angle brackets.
 210     ///
 211     /// ```ignore (diagnostics)
 212     /// bar::<<<<T as Foo>::Output>();
 213     ///      ^^ help: remove extra angle brackets
 214     /// ```
 215     fn parse_generic_args_with_leaning_angle_bracket_recovery(
 216         &mut self,
 217         style: PathStyle,
 218         lo: Span,
 219     ) -> PResult<'a, (Vec<GenericArg>, Vec<AssocTyConstraint>)> {
 220         // We need to detect whether there are extra leading left angle brackets and produce an
 221         // appropriate error and suggestion. This cannot be implemented by looking ahead at
 222         // upcoming tokens for a matching `>` character - if there are unmatched `<` tokens
 223         // then there won't be matching `>` tokens to find.
 224         //
 225         // To explain how this detection works, consider the following example:
 226         //
 227         // ```ignore (diagnostics)
 228         // bar::<<<<T as Foo>::Output>();
 229         //      ^^ help: remove extra angle brackets
 230         // ```
 231         //
 232         // Parsing of the left angle brackets starts in this function. We start by parsing the
 233         // `<` token (incrementing the counter of unmatched angle brackets on `Parser` via
 234         // `eat_lt`):
 235         //
 236         // *Upcoming tokens:* `<<<<T as Foo>::Output>;`
 237         // *Unmatched count:* 1
 238         // *`parse_path_segment` calls deep:* 0
 239         //
 240         // This has the effect of recursing as this function is called if a `<` character
 241         // is found within the expected generic arguments:
 242         //
 243         // *Upcoming tokens:* `<<<T as Foo>::Output>;`
 244         // *Unmatched count:* 2
 245         // *`parse_path_segment` calls deep:* 1
 246         //
 247         // Eventually we will have recursed until having consumed all of the `<` tokens and
 248         // this will be reflected in the count:
 249         //
 250         // *Upcoming tokens:* `T as Foo>::Output>;`
 251         // *Unmatched count:* 4
 252         // `parse_path_segment` calls deep:* 3
 253         //
 254         // The parser will continue until reaching the first `>` - this will decrement the
 255         // unmatched angle bracket count and return to the parent invocation of this function
 256         // having succeeded in parsing:
 257         //
 258         // *Upcoming tokens:* `::Output>;`
 259         // *Unmatched count:* 3
 260         // *`parse_path_segment` calls deep:* 2
 261         //
 262         // This will continue until the next `>` character which will also return successfully
 263         // to the parent invocation of this function and decrement the count:
 264         //
 265         // *Upcoming tokens:* `;`
 266         // *Unmatched count:* 2
 267         // *`parse_path_segment` calls deep:* 1
 268         //
 269         // At this point, this function will expect to find another matching `>` character but
 270         // won't be able to and will return an error. This will continue all the way up the
 271         // call stack until the first invocation:
 272         //
 273         // *Upcoming tokens:* `;`
 274         // *Unmatched count:* 2
 275         // *`parse_path_segment` calls deep:* 0
 276         //
 277         // In doing this, we have managed to work out how many unmatched leading left angle
 278         // brackets there are, but we cannot recover as the unmatched angle brackets have
 279         // already been consumed. To remedy this, we keep a snapshot of the parser state
 280         // before we do the above. We can then inspect whether we ended up with a parsing error
 281         // and unmatched left angle brackets and if so, restore the parser state before we
 282         // consumed any `<` characters to emit an error and consume the erroneous tokens to
 283         // recover by attempting to parse again.
 284         //
 285         // In practice, the recursion of this function is indirect and there will be other
 286         // locations that consume some `<` characters - as long as we update the count when
 287         // this happens, it isn't an issue.
 288
 289         let is_first_invocation = style == PathStyle::Expr;
 290         // Take a snapshot before attempting to parse - we can restore this later.
 291         let snapshot = if is_first_invocation {
 292             Some(self.clone())
 293         } else {
 294             None
 295         };
 296
 297         debug!("parse_generic_args_with_leading_angle_bracket_recovery: (snapshotting)");
 298         match self.parse_generic_args() {
 299             Ok(value) => Ok(value),
 300             Err(ref mut e) if is_first_invocation && self.unmatched_angle_bracket_count > 0 => {
 301                 // Cancel error from being unable to find `>`. We know the error
 302                 // must have been this due to a non-zero unmatched angle bracket
 303                 // count.
 304                 e.cancel();
 305
 306                 // Swap `self` with our backup of the parser state before attempting to parse
 307                 // generic arguments.
 308                 let snapshot = mem::replace(self, snapshot.unwrap());
 309
 310                 debug!(
 311                     "parse_generic_args_with_leading_angle_bracket_recovery: (snapshot failure) \
 312                      snapshot.count={:?}",
 313                     snapshot.unmatched_angle_bracket_count,
 314                 );
 315
 316                 // Eat the unmatched angle brackets.
 317                 for _ in 0..snapshot.unmatched_angle_bracket_count {
 318                     self.eat_lt();
 319                 }
 320
 321                 // Make a span over ${unmatched angle bracket count} characters.
 322                 let span = lo.with_hi(
 323                     lo.lo() + BytePos(snapshot.unmatched_angle_bracket_count)
 324                 );
 325                 self.diagnostic()
 326                     .struct_span_err(
 327                         span,
 328                         &format!(
 329                             "unmatched angle bracket{}",
 330                             pluralize!(snapshot.unmatched_angle_bracket_count)
 331                         ),
 332                     )
 333                     .span_suggestion(
 334                         span,
 335                         &format!(
 336                             "remove extra angle bracket{}",
 337                             pluralize!(snapshot.unmatched_angle_bracket_count)
 338                         ),
 339                         String::new(),
 340                         Applicability::MachineApplicable,
 341                     )
 342                     .emit();
 343
 344                 // Try again without unmatched angle bracket characters.
 345                 self.parse_generic_args()
 346             },
 347             Err(e) => Err(e),
 348         }
 349     }
 350
 351     /// Parses (possibly empty) list of lifetime and type arguments and associated type bindings,
 352     /// possibly including trailing comma.
 353     fn parse_generic_args(&mut self) -> PResult<'a, (Vec<GenericArg>, Vec<AssocTyConstraint>)> {
 354         let mut args = Vec::new();
 355         let mut constraints = Vec::new();
 356         let mut misplaced_assoc_ty_constraints: Vec<Span> = Vec::new();
 357         let mut assoc_ty_constraints: Vec<Span> = Vec::new();
 358
 359         let args_lo = self.token.span;
 360
 361         loop {
 362             if self.check_lifetime() && self.look_ahead(1, |t| !t.is_like_plus()) {
 363                 // Parse lifetime argument.
 364                 args.push(GenericArg::Lifetime(self.expect_lifetime()));
 365                 misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
 366             } else if self.check_ident()
 367                 && self.look_ahead(1, |t| t == &token::Eq || t == &token::Colon)
 368             {
 369                 // Parse associated type constraint.
 370                 let lo = self.token.span;
 371                 let ident = self.parse_ident()?;
 372                 let kind = if self.eat(&token::Eq) {
 373                     AssocTyConstraintKind::Equality {
 374                         ty: self.parse_ty()?,
 375                     }
 376                 } else if self.eat(&token::Colon) {
 377                     AssocTyConstraintKind::Bound {
 378                         bounds: self.parse_generic_bounds(Some(self.prev_span))?,
 379                     }
 380                 } else {
 381                     unreachable!();
 382                 };
 383
 384                 let span = lo.to(self.prev_span);
 385
 386                 // Gate associated type bounds, e.g., `Iterator<Item: Ord>`.
 387                 if let AssocTyConstraintKind::Bound { .. } = kind {
 388                     self.sess.gated_spans.gate(sym::associated_type_bounds, span);
 389                 }
 390
 391                 constraints.push(AssocTyConstraint {
 392                     id: ast::DUMMY_NODE_ID,
 393                     ident,
 394                     kind,
 395                     span,
 396                 });
 397                 assoc_ty_constraints.push(span);
 398             } else if self.check_const_arg() {
 399                 // Parse const argument.
 400                 let expr = if let token::OpenDelim(token::Brace) = self.token.kind {
 401                     self.parse_block_expr(
 402                         None, self.token.span, BlockCheckMode::Default, ast::AttrVec::new()
 403                     )?
 404                 } else if self.token.is_ident() {
 405                     // FIXME(const_generics): to distinguish between idents for types and consts,
 406                     // we should introduce a GenericArg::Ident in the AST and distinguish when
 407                     // lowering to the HIR. For now, idents for const args are not permitted.
 408                     if self.token.is_bool_lit() {
 409                         self.parse_literal_maybe_minus()?
 410                     } else {
 411                         return Err(
 412                             self.fatal("identifiers may currently not be used for const generics")
 413                         );
 414                     }
 415                 } else {
 416                     self.parse_literal_maybe_minus()?
 417                 };
 418                 let value = AnonConst {
 419                     id: ast::DUMMY_NODE_ID,
 420                     value: expr,
 421                 };
 422                 args.push(GenericArg::Const(value));
 423                 misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
 424             } else if self.check_type() {
 425                 // Parse type argument.
 426                 args.push(GenericArg::Type(self.parse_ty()?));
 427                 misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
 428             } else {
 429                 break
 430             }
 431
 432             if !self.eat(&token::Comma) {
 433                 break
 434             }
 435         }
 436
 437         // FIXME: we would like to report this in ast_validation instead, but we currently do not
 438         // preserve ordering of generic parameters with respect to associated type binding, so we
 439         // lose that information after parsing.
 440         if misplaced_assoc_ty_constraints.len() > 0 {
 441             let mut err = self.struct_span_err(
 442                 args_lo.to(self.prev_span),
 443                 "associated type bindings must be declared after generic parameters",
 444             );
 445             for span in misplaced_assoc_ty_constraints {
 446                 err.span_label(
 447                     span,
 448                     "this associated type binding should be moved after the generic parameters",
 449                 );
 450             }
 451             err.emit();
 452         }
 453
 454         Ok((args, constraints))
 455     }
 456 }