src/libsyntax/parse/parser/path.rs

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