Skip to content

Commit bbebabf

Browse files
borsbors
committed
Auto merge of #117143 - estebank:issue-117080, r=<try>
Avoid unbounded O(n^2) when parsing nested type args When encountering code like `f::<f::<f::<f::<f::<f::<f::<f::<...` with unmatched closing angle brackets, add a linear check that avoids the exponential behavior of the parse recovery mechanism. Fix #117080.
2 parents 151256b + 54dffa1 commit bbebabf

File tree

82 files changed

+51
-6
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

82 files changed

+51
-6
lines changed

‎compiler/rustc_parse/src/parser/mod.rs

+4-2
Original file line numberDiff line numberDiff line change
@@ -159,8 +159,9 @@ pub struct Parser<'a> {
159159
/// appropriately.
160160
///
161161
/// See the comments in the `parse_path_segment` function for more details.
162-
unmatched_angle_bracket_count: u32,
163-
max_angle_bracket_count: u32,
162+
unmatched_angle_bracket_count: u16,
163+
max_angle_bracket_count: u16,
164+
angle_bracket_nesting: u16,
164165

165166
last_unexpected_token_span: Option<Span>,
166167
/// If present, this `Parser` is not parsing Rust code but rather a macro call.
@@ -394,6 +395,7 @@ impl<'a> Parser<'a> {
394395
break_last_token: false,
395396
unmatched_angle_bracket_count: 0,
396397
max_angle_bracket_count: 0,
398+
angle_bracket_nesting: 0,
397399
last_unexpected_token_span: None,
398400
subparser_name,
399401
capture_state: CaptureState {

‎compiler/rustc_parse/src/parser/path.rs

+21-4
Original file line numberDiff line numberDiff line change
@@ -487,10 +487,24 @@ impl<'a> Parser<'a> {
487487
// Take a snapshot before attempting to parse - we can restore this later.
488488
let snapshot = is_first_invocation.then(|| self.clone());
489489

490+
self.angle_bracket_nesting += 1;
490491
debug!("parse_generic_args_with_leading_angle_bracket_recovery: (snapshotting)");
491492
match self.parse_angle_args(ty_generics) {
492-
Ok(args) => Ok(args),
493+
Ok(args) => {
494+
self.angle_bracket_nesting -= 1;
495+
Ok(args)
496+
}
497+
Err(mut e) if self.angle_bracket_nesting > 10 => {
498+
self.angle_bracket_nesting -= 1;
499+
// When encountering severly malformed code where there are several levels of
500+
// nested unclosed angle args (`f::<f::<f::<f::<...`), we avoid severe O(n^2)
501+
// behavior by bailing out earlier (#117080).
502+
e.emit();
503+
rustc_errors::FatalError.raise();
504+
}
493505
Err(e) if is_first_invocation && self.unmatched_angle_bracket_count > 0 => {
506+
self.angle_bracket_nesting -= 1;
507+
494508
// Swap `self` with our backup of the parser state before attempting to parse
495509
// generic arguments.
496510
let snapshot = mem::replace(self, snapshot.unwrap());
@@ -520,8 +534,8 @@ impl<'a> Parser<'a> {
520534
// Make a span over ${unmatched angle bracket count} characters.
521535
// This is safe because `all_angle_brackets` ensures that there are only `<`s,
522536
// i.e. no multibyte characters, in this range.
523-
let span =
524-
lo.with_hi(lo.lo() + BytePos(snapshot.unmatched_angle_bracket_count));
537+
let span = lo
538+
.with_hi(lo.lo() + BytePos(snapshot.unmatched_angle_bracket_count.into()));
525539
self.sess.emit_err(errors::UnmatchedAngle {
526540
span,
527541
plural: snapshot.unmatched_angle_bracket_count > 1,
@@ -531,7 +545,10 @@ impl<'a> Parser<'a> {
531545
self.parse_angle_args(ty_generics)
532546
}
533547
}
534-
Err(e) => Err(e),
548+
Err(e) => {
549+
self.angle_bracket_nesting -= 1;
550+
Err(e)
551+
}
535552
}
536553
}
537554

‎tests/ui/parser/deep-unmatched-angle-brackets.rs

+13
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
trait Mul<T> {
2+
type Output;
3+
}
4+
trait Matrix: Mul<<Self as Matrix>::Row, Output = ()> {
5+
type Row;
6+
type Transpose: Matrix<Row = Self::Row>;
7+
}
8+
fn is_mul<S, T: Mul<S, Output = ()>>() {}
9+
fn f<T: Matrix>() {
10+
is_mul::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<>();
11+
//~^ ERROR expected one of `!`, `+`, `,`, `::`, or `>`, found `(`
12+
}
13+
fn main() {}

‎tests/ui/parser/deep-unmatched-angle-brackets.stderr

+13
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
error: expected one of `!`, `+`, `,`, `::`, or `>`, found `(`
2+
--> $DIR/deep-unmatched-angle-brackets.rs:10:415
3+
|
4+
LL | ...::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<>();
5+
| ^ expected one of `!`, `+`, `,`, `::`, or `>`
6+
|
7+
help: you might have meant to end the type parameters here
8+
|
9+
LL | is_mul::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<>>();
10+
| +
11+
12+
error: aborting due to previous error
13+

‎tests/ui/parser/issue-100197-mut-let.fixed ‎tests/ui/parser/issues/issue-100197-mut-let.fixed

File renamed without changes.

‎tests/ui/parser/issue-100197-mut-let.rs ‎tests/ui/parser/issues/issue-100197-mut-let.rs

File renamed without changes.

‎tests/ui/parser/issue-100197-mut-let.stderr ‎tests/ui/parser/issues/issue-100197-mut-let.stderr

File renamed without changes.

‎tests/ui/parser/issue-101477-enum.fixed ‎tests/ui/parser/issues/issue-101477-enum.fixed

File renamed without changes.

‎tests/ui/parser/issue-101477-enum.rs ‎tests/ui/parser/issues/issue-101477-enum.rs

File renamed without changes.

‎tests/ui/parser/issue-101477-enum.stderr ‎tests/ui/parser/issues/issue-101477-enum.stderr

File renamed without changes.

‎tests/ui/parser/issue-101477-let.fixed ‎tests/ui/parser/issues/issue-101477-let.fixed

File renamed without changes.

‎tests/ui/parser/issue-101477-let.rs ‎tests/ui/parser/issues/issue-101477-let.rs

File renamed without changes.

‎tests/ui/parser/issue-101477-let.stderr ‎tests/ui/parser/issues/issue-101477-let.stderr

File renamed without changes.

‎tests/ui/parser/issue-102806.rs ‎tests/ui/parser/issues/issue-102806.rs

File renamed without changes.

‎tests/ui/parser/issue-102806.stderr ‎tests/ui/parser/issues/issue-102806.stderr

File renamed without changes.

‎tests/ui/parser/issue-103143.rs ‎tests/ui/parser/issues/issue-103143.rs

File renamed without changes.

‎tests/ui/parser/issue-103143.stderr ‎tests/ui/parser/issues/issue-103143.stderr

File renamed without changes.

‎tests/ui/parser/issue-103381.fixed ‎tests/ui/parser/issues/issue-103381.fixed

File renamed without changes.

‎tests/ui/parser/issue-103381.rs ‎tests/ui/parser/issues/issue-103381.rs

File renamed without changes.

‎tests/ui/parser/issue-103381.stderr ‎tests/ui/parser/issues/issue-103381.stderr

File renamed without changes.

‎tests/ui/parser/issue-103425.rs ‎tests/ui/parser/issues/issue-103425.rs

File renamed without changes.

‎tests/ui/parser/issue-103425.stderr ‎tests/ui/parser/issues/issue-103425.stderr

File renamed without changes.

‎tests/ui/parser/issue-103451.rs ‎tests/ui/parser/issues/issue-103451.rs

File renamed without changes.

‎tests/ui/parser/issue-103451.stderr ‎tests/ui/parser/issues/issue-103451.stderr

File renamed without changes.

‎tests/ui/parser/issue-103748-ICE-wrong-braces.rs ‎tests/ui/parser/issues/issue-103748-ICE-wrong-braces.rs

File renamed without changes.

‎tests/ui/parser/issue-103748-ICE-wrong-braces.stderr ‎tests/ui/parser/issues/issue-103748-ICE-wrong-braces.stderr

File renamed without changes.

‎tests/ui/parser/issue-104620.rs ‎tests/ui/parser/issues/issue-104620.rs

File renamed without changes.

‎tests/ui/parser/issue-104620.stderr ‎tests/ui/parser/issues/issue-104620.stderr

File renamed without changes.

‎tests/ui/parser/issue-104867-inc-dec-2.rs ‎tests/ui/parser/issues/issue-104867-inc-dec-2.rs

File renamed without changes.

‎tests/ui/parser/issue-104867-inc-dec-2.stderr ‎tests/ui/parser/issues/issue-104867-inc-dec-2.stderr

File renamed without changes.

‎tests/ui/parser/issue-104867-inc-dec.rs ‎tests/ui/parser/issues/issue-104867-inc-dec.rs

File renamed without changes.

‎tests/ui/parser/issue-104867-inc-dec.stderr ‎tests/ui/parser/issues/issue-104867-inc-dec.stderr

File renamed without changes.

‎tests/ui/parser/issue-105366.fixed ‎tests/ui/parser/issues/issue-105366.fixed

File renamed without changes.

‎tests/ui/parser/issue-105366.rs ‎tests/ui/parser/issues/issue-105366.rs

File renamed without changes.

‎tests/ui/parser/issue-105366.stderr ‎tests/ui/parser/issues/issue-105366.stderr

File renamed without changes.

‎tests/ui/parser/issue-105634.rs ‎tests/ui/parser/issues/issue-105634.rs

File renamed without changes.

‎tests/ui/parser/issue-107705.rs ‎tests/ui/parser/issues/issue-107705.rs

File renamed without changes.

‎tests/ui/parser/issue-107705.stderr ‎tests/ui/parser/issues/issue-107705.stderr

File renamed without changes.

‎tests/ui/parser/issue-108495-dec.rs ‎tests/ui/parser/issues/issue-108495-dec.rs

File renamed without changes.

‎tests/ui/parser/issue-108495-dec.stderr ‎tests/ui/parser/issues/issue-108495-dec.stderr

File renamed without changes.

‎tests/ui/parser/issue-112188.fixed ‎tests/ui/parser/issues/issue-112188.fixed

File renamed without changes.

‎tests/ui/parser/issue-112188.rs ‎tests/ui/parser/issues/issue-112188.rs

File renamed without changes.

‎tests/ui/parser/issue-112188.stderr ‎tests/ui/parser/issues/issue-112188.stderr

File renamed without changes.

‎tests/ui/parser/issue-113342.rs ‎tests/ui/parser/issues/issue-113342.rs

File renamed without changes.

‎tests/ui/parser/issue-113342.stderr ‎tests/ui/parser/issues/issue-113342.stderr

File renamed without changes.

‎tests/ui/parser/issue-17718-parse-const.rs ‎tests/ui/parser/issues/issue-17718-parse-const.rs

File renamed without changes.

‎tests/ui/parser/issue-39616.rs ‎tests/ui/parser/issues/issue-39616.rs

File renamed without changes.

‎tests/ui/parser/issue-39616.stderr ‎tests/ui/parser/issues/issue-39616.stderr

File renamed without changes.

‎tests/ui/parser/issue-49257.rs ‎tests/ui/parser/issues/issue-49257.rs

File renamed without changes.

‎tests/ui/parser/issue-49257.stderr ‎tests/ui/parser/issues/issue-49257.stderr

File renamed without changes.

‎tests/ui/parser/issue-61858.rs ‎tests/ui/parser/issues/issue-61858.rs

File renamed without changes.

‎tests/ui/parser/issue-61858.stderr ‎tests/ui/parser/issues/issue-61858.stderr

File renamed without changes.

‎tests/ui/parser/issue-68091-unicode-ident-after-if.rs ‎tests/ui/parser/issues/issue-68091-unicode-ident-after-if.rs

File renamed without changes.

‎tests/ui/parser/issue-68091-unicode-ident-after-if.stderr ‎tests/ui/parser/issues/issue-68091-unicode-ident-after-if.stderr

File renamed without changes.

‎tests/ui/parser/issue-68092-unicode-ident-after-incomplete-expr.rs ‎tests/ui/parser/issues/issue-68092-unicode-ident-after-incomplete-expr.rs

File renamed without changes.

‎tests/ui/parser/issue-68092-unicode-ident-after-incomplete-expr.stderr ‎tests/ui/parser/issues/issue-68092-unicode-ident-after-incomplete-expr.stderr

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-1.rs ‎tests/ui/parser/issues/issue-68987-unmatch-issue-1.rs

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-1.stderr ‎tests/ui/parser/issues/issue-68987-unmatch-issue-1.stderr

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-2.rs ‎tests/ui/parser/issues/issue-68987-unmatch-issue-2.rs

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-2.stderr ‎tests/ui/parser/issues/issue-68987-unmatch-issue-2.stderr

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-3.rs ‎tests/ui/parser/issues/issue-68987-unmatch-issue-3.rs

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue-3.stderr ‎tests/ui/parser/issues/issue-68987-unmatch-issue-3.stderr

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue.rs ‎tests/ui/parser/issues/issue-68987-unmatch-issue.rs

File renamed without changes.

‎tests/ui/parser/issue-68987-unmatch-issue.stderr ‎tests/ui/parser/issues/issue-68987-unmatch-issue.stderr

File renamed without changes.

‎tests/ui/parser/issue-81804.rs ‎tests/ui/parser/issues/issue-81804.rs

File renamed without changes.

‎tests/ui/parser/issue-81804.stderr ‎tests/ui/parser/issues/issue-81804.stderr

File renamed without changes.

‎tests/ui/parser/issue-81827.rs ‎tests/ui/parser/issues/issue-81827.rs

File renamed without changes.

‎tests/ui/parser/issue-81827.stderr ‎tests/ui/parser/issues/issue-81827.stderr

File renamed without changes.

‎tests/ui/parser/issue-87694-duplicated-pub.rs ‎tests/ui/parser/issues/issue-87694-duplicated-pub.rs

File renamed without changes.

‎tests/ui/parser/issue-87694-duplicated-pub.stderr ‎tests/ui/parser/issues/issue-87694-duplicated-pub.stderr

File renamed without changes.

‎tests/ui/parser/issue-87694-misplaced-pub.rs ‎tests/ui/parser/issues/issue-87694-misplaced-pub.rs

File renamed without changes.

‎tests/ui/parser/issue-87694-misplaced-pub.stderr ‎tests/ui/parser/issues/issue-87694-misplaced-pub.stderr

File renamed without changes.

‎tests/ui/parser/issue-90728.rs ‎tests/ui/parser/issues/issue-90728.rs

File renamed without changes.

‎tests/ui/parser/issue-90728.stderr ‎tests/ui/parser/issues/issue-90728.stderr

File renamed without changes.

‎tests/ui/parser/issue-91421.rs ‎tests/ui/parser/issues/issue-91421.rs

File renamed without changes.

‎tests/ui/parser/issue-91421.stderr ‎tests/ui/parser/issues/issue-91421.stderr

File renamed without changes.

‎tests/ui/parser/issue-99625-enum-struct-mutually-exclusive.fixed ‎tests/ui/parser/issues/issue-99625-enum-struct-mutually-exclusive.fixed

File renamed without changes.

‎tests/ui/parser/issue-99625-enum-struct-mutually-exclusive.rs ‎tests/ui/parser/issues/issue-99625-enum-struct-mutually-exclusive.rs

File renamed without changes.

‎tests/ui/parser/issue-99625-enum-struct-mutually-exclusive.stderr ‎tests/ui/parser/issues/issue-99625-enum-struct-mutually-exclusive.stderr

File renamed without changes.

‎tests/ui/parser/issue-99910-const-let-mutually-exclusive.fixed ‎tests/ui/parser/issues/issue-99910-const-let-mutually-exclusive.fixed

File renamed without changes.

‎tests/ui/parser/issue-99910-const-let-mutually-exclusive.rs ‎tests/ui/parser/issues/issue-99910-const-let-mutually-exclusive.rs

File renamed without changes.

‎tests/ui/parser/issue-99910-const-let-mutually-exclusive.stderr ‎tests/ui/parser/issues/issue-99910-const-let-mutually-exclusive.stderr

File renamed without changes.

0 commit comments

Comments
 (0)