Avoid unbounded O(n^2) when parsing nested type args

estebank · estebank · commit 54dffa1441e0 · 2023-10-24T22:22:52.000Z
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.
diff --git a/compiler/rustc_parse/src/parser/mod.rs b/compiler/rustc_parse/src/parser/mod.rs
@@ -159,8 +159,9 @@ pub struct Parser<'a> {
     /// appropriately.
     ///
     /// See the comments in the `parse_path_segment` function for more details.
-    unmatched_angle_bracket_count: u32,
-    max_angle_bracket_count: u32,
+    unmatched_angle_bracket_count: u16,
+    max_angle_bracket_count: u16,
+    angle_bracket_nesting: u16,
 
     last_unexpected_token_span: Option<Span>,
     /// If present, this `Parser` is not parsing Rust code but rather a macro call.
@@ -394,6 +395,7 @@ impl<'a> Parser<'a> {
             break_last_token: false,
             unmatched_angle_bracket_count: 0,
             max_angle_bracket_count: 0,
+            angle_bracket_nesting: 0,
             last_unexpected_token_span: None,
             subparser_name,
             capture_state: CaptureState {
diff --git a/compiler/rustc_parse/src/parser/path.rs b/compiler/rustc_parse/src/parser/path.rs
@@ -487,10 +487,24 @@ impl<'a> Parser<'a> {
         // Take a snapshot before attempting to parse - we can restore this later.
         let snapshot = is_first_invocation.then(|| self.clone());
 
+        self.angle_bracket_nesting += 1;
         debug!("parse_generic_args_with_leading_angle_bracket_recovery: (snapshotting)");
         match self.parse_angle_args(ty_generics) {
-            Ok(args) => Ok(args),
+            Ok(args) => {
+                self.angle_bracket_nesting -= 1;
+                Ok(args)
+            }
+            Err(mut e) if self.angle_bracket_nesting > 10 => {
+                self.angle_bracket_nesting -= 1;
+                // When encountering severly malformed code where there are several levels of
+                // nested unclosed angle args (`f::<f::<f::<f::<...`), we avoid severe O(n^2)
+                // behavior by bailing out earlier (#117080).
+                e.emit();
+                rustc_errors::FatalError.raise();
+            }
             Err(e) if is_first_invocation && self.unmatched_angle_bracket_count > 0 => {
+                self.angle_bracket_nesting -= 1;
+
                 // Swap `self` with our backup of the parser state before attempting to parse
                 // generic arguments.
                 let snapshot = mem::replace(self, snapshot.unwrap());
@@ -520,8 +534,8 @@ impl<'a> Parser<'a> {
                     // Make a span over ${unmatched angle bracket count} characters.
                     // This is safe because `all_angle_brackets` ensures that there are only `<`s,
                     // i.e. no multibyte characters, in this range.
-                    let span =
-                        lo.with_hi(lo.lo() + BytePos(snapshot.unmatched_angle_bracket_count));
+                    let span = lo
+                        .with_hi(lo.lo() + BytePos(snapshot.unmatched_angle_bracket_count.into()));
                     self.sess.emit_err(errors::UnmatchedAngle {
                         span,
                         plural: snapshot.unmatched_angle_bracket_count > 1,
@@ -531,7 +545,10 @@ impl<'a> Parser<'a> {
                     self.parse_angle_args(ty_generics)
                 }
             }
-            Err(e) => Err(e),
+            Err(e) => {
+                self.angle_bracket_nesting -= 1;
+                Err(e)
+            }
         }
     }
 
diff --git a/tests/ui/parser/deep-unmatched-angle-brackets.rs b/tests/ui/parser/deep-unmatched-angle-brackets.rs
@@ -0,0 +1,13 @@
+trait Mul<T> {
+    type Output;
+}
+trait Matrix: Mul<<Self as Matrix>::Row, Output = ()> {
+    type Row;
+    type Transpose: Matrix<Row = Self::Row>;
+}
+fn is_mul<S, T: Mul<S, Output = ()>>() {}
+fn f<T: Matrix>() {
+    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::<>();
+    //~^ ERROR expected one of `!`, `+`, `,`, `::`, or `>`, found `(`
+}
+fn main() {}
diff --git a/tests/ui/parser/deep-unmatched-angle-brackets.stderr b/tests/ui/parser/deep-unmatched-angle-brackets.stderr
@@ -0,0 +1,13 @@
+error: expected one of `!`, `+`, `,`, `::`, or `>`, found `(`
+  --> $DIR/deep-unmatched-angle-brackets.rs:10:415
+   |
+LL | ...::<f::<f::<f::<f::<f::<f::<f::<f::<f::<f::<>();
+   |                                                ^ expected one of `!`, `+`, `,`, `::`, or `>`
+   |
+help: you might have meant to end the type parameters here
+   |
+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::<>>();
+   |                                                                                                                                                                                                                                                                                                                                                                                                                               +
+
+error: aborting due to previous error
+
