Auto merge of #10827 - y21:large-stack-frames, r=dswij

new lint: `large_stack_frames`

This implements a lint that looks for functions that use a lot of stack space.

It uses the MIR because conveniently every temporary gets its own local and I think it maps best to stack space used in a function.
It's probably going to be quite inaccurate in release builds, but at least for debug builds where opts are less aggressive on LLVM's side I think this is accurate "enough".

(This does not work for generic functions yet. Not sure if I should try to get it working in this PR or if it could land without it for now and be added in a followup PR.)

I also put it under the nursery category because this probably needs more work...

changelog: new lint: [`large_stack_frames`]

9 files changed, 264 insertions, 0 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2d62bfd4f99..85fddc97047 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4883,6 +4883,7 @@ Released 2018-09-13
 [`large_futures`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_futures
 [`large_include_file`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_include_file
 [`large_stack_arrays`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_stack_arrays
+[`large_stack_frames`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_stack_frames
 [`large_types_passed_by_value`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_types_passed_by_value
 [`len_without_is_empty`]: https://rust-lang.github.io/rust-clippy/master/index.html#len_without_is_empty
 [`len_zero`]: https://rust-lang.github.io/rust-clippy/master/index.html#len_zero
diff --git a/book/src/lint_configuration.md b/book/src/lint_configuration.md
index b2e11d8de67..085dff8e63b 100644
--- a/book/src/lint_configuration.md
+++ b/book/src/lint_configuration.md
@@ -338,6 +338,16 @@ The maximum allowed size for arrays on the stack
 * [`large_const_arrays`](https://rust-lang.github.io/rust-clippy/master/index.html#large_const_arrays)
 
 
+## `stack-size-threshold`
+The maximum allowed stack size for functions in bytes
+
+**Default Value:** `512000` (`u64`)
+
+---
+**Affected lints:**
+* [`large_stack_frames`](https://rust-lang.github.io/rust-clippy/master/index.html#large_stack_frames)
+
+
 ## `vec-box-size-threshold`
 The size of the boxed type in bytes, where boxing in a `Vec` is allowed
 
diff --git a/clippy_lints/src/declared_lints.rs b/clippy_lints/src/declared_lints.rs
index 769774b27c4..523faa302dc 100644
--- a/clippy_lints/src/declared_lints.rs
+++ b/clippy_lints/src/declared_lints.rs
@@ -228,6 +228,7 @@ pub(crate) static LINTS: &[&crate::LintInfo] = &[
     crate::large_futures::LARGE_FUTURES_INFO,
     crate::large_include_file::LARGE_INCLUDE_FILE_INFO,
     crate::large_stack_arrays::LARGE_STACK_ARRAYS_INFO,
+    crate::large_stack_frames::LARGE_STACK_FRAMES_INFO,
     crate::len_zero::COMPARISON_TO_EMPTY_INFO,
     crate::len_zero::LEN_WITHOUT_IS_EMPTY_INFO,
     crate::len_zero::LEN_ZERO_INFO,
diff --git a/clippy_lints/src/large_stack_frames.rs b/clippy_lints/src/large_stack_frames.rs
new file mode 100644
index 00000000000..9c0cc978a39
--- /dev/null
+++ b/clippy_lints/src/large_stack_frames.rs
@@ -0,0 +1,162 @@
+use std::ops::AddAssign;
+
+use clippy_utils::diagnostics::span_lint_and_note;
+use clippy_utils::fn_has_unsatisfiable_preds;
+use rustc_hir::def_id::LocalDefId;
+use rustc_hir::intravisit::FnKind;
+use rustc_hir::Body;
+use rustc_hir::FnDecl;
+use rustc_lint::{LateContext, LateLintPass};
+use rustc_session::declare_tool_lint;
+use rustc_session::impl_lint_pass;
+use rustc_span::Span;
+
+declare_clippy_lint! {
+    /// ### What it does
+    /// Checks for functions that use a lot of stack space.
+    ///
+    /// This often happens when constructing a large type, such as an array with a lot of elements,
+    /// or constructing *many* smaller-but-still-large structs, or copying around a lot of large types.
+    ///
+    /// This lint is a more general version of [`large_stack_arrays`](https://rust-lang.github.io/rust-clippy/master/#large_stack_arrays)
+    /// that is intended to look at functions as a whole instead of only individual array expressions inside of a function.
+    ///
+    /// ### Why is this bad?
+    /// The stack region of memory is very limited in size (usually *much* smaller than the heap) and attempting to
+    /// use too much will result in a stack overflow and crash the program.
+    /// To avoid this, you should consider allocating large types on the heap instead (e.g. by boxing them).
+    ///
+    /// Keep in mind that the code path to construction of large types does not even need to be reachable;
+    /// it purely needs to *exist* inside of the function to contribute to the stack size.
+    /// For example, this causes a stack overflow even though the branch is unreachable:
+    /// ```rust,ignore
+    /// fn main() {
+    ///     if false {
+    ///         let x = [0u8; 10000000]; // 10 MB stack array
+    ///         black_box(&x);
+    ///     }
+    /// }
+    /// ```
+    ///
+    /// ### Known issues
+    /// False positives. The stack size that clippy sees is an estimated value and can be vastly different
+    /// from the actual stack usage after optimizations passes have run (especially true in release mode).
+    /// Modern compilers are very smart and are able to optimize away a lot of unnecessary stack allocations.
+    /// In debug mode however, it is usually more accurate.
+    ///
+    /// This lint works by summing up the size of all variables that the user typed, variables that were
+    /// implicitly introduced by the compiler for temporaries, function arguments and the return value,
+    /// and comparing them against a (configurable, but high-by-default).
+    ///
+    /// ### Example
+    /// This function creates four 500 KB arrays on the stack. Quite big but just small enough to not trigger `large_stack_arrays`.
+    /// However, looking at the function as a whole, it's clear that this uses a lot of stack space.
+    /// ```rust
+    /// struct QuiteLargeType([u8; 500_000]);
+    /// fn foo() {
+    ///     // ... some function that uses a lot of stack space ...
+    ///     let _x1 = QuiteLargeType([0; 500_000]);
+    ///     let _x2 = QuiteLargeType([0; 500_000]);
+    ///     let _x3 = QuiteLargeType([0; 500_000]);
+    ///     let _x4 = QuiteLargeType([0; 500_000]);
+    /// }
+    /// ```
+    ///
+    /// Instead of doing this, allocate the arrays on the heap.
+    /// This currently requires going through a `Vec` first and then converting it to a `Box`:
+    /// ```rust
+    /// struct NotSoLargeType(Box<[u8]>);
+    ///
+    /// fn foo() {
+    ///     let _x1 = NotSoLargeType(vec![0; 500_000].into_boxed_slice());
+    /// //                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  Now heap allocated.
+    /// //                                                                The size of `NotSoLargeType` is 16 bytes.
+    /// //  ...
+    /// }
+    /// ```
+    #[clippy::version = "1.71.0"]
+    pub LARGE_STACK_FRAMES,
+    nursery,
+    "checks for functions that allocate a lot of stack space"
+}
+
+pub struct LargeStackFrames {
+    maximum_allowed_size: u64,
+}
+
+impl LargeStackFrames {
+    #[must_use]
+    pub fn new(size: u64) -> Self {
+        Self {
+            maximum_allowed_size: size,
+        }
+    }
+}
+
+impl_lint_pass!(LargeStackFrames => [LARGE_STACK_FRAMES]);
+
+#[derive(Copy, Clone)]
+enum Space {
+    Used(u64),
+    Overflow,
+}
+
+impl Space {
+    pub fn exceeds_limit(self, limit: u64) -> bool {
+        match self {
+            Self::Used(used) => used > limit,
+            Self::Overflow => true,
+        }
+    }
+}
+
+impl AddAssign<u64> for Space {
+    fn add_assign(&mut self, rhs: u64) {
+        if let Self::Used(lhs) = self {
+            match lhs.checked_add(rhs) {
+                Some(sum) => *self = Self::Used(sum),
+                None => *self = Self::Overflow,
+            }
+        }
+    }
+}
+
+impl<'tcx> LateLintPass<'tcx> for LargeStackFrames {
+    fn check_fn(
+        &mut self,
+        cx: &LateContext<'tcx>,
+        _: FnKind<'tcx>,
+        _: &'tcx FnDecl<'tcx>,
+        _: &'tcx Body<'tcx>,
+        span: Span,
+        local_def_id: LocalDefId,
+    ) {
+        let def_id = local_def_id.to_def_id();
+        // Building MIR for `fn`s with unsatisfiable preds results in ICE.
+        if fn_has_unsatisfiable_preds(cx, def_id) {
+            return;
+        }
+
+        let mir = cx.tcx.optimized_mir(def_id);
+        let param_env = cx.tcx.param_env(def_id);
+
+        let mut frame_size = Space::Used(0);
+
+        for local in &mir.local_decls {
+            if let Ok(layout) = cx.tcx.layout_of(param_env.and(local.ty)) {
+                frame_size += layout.size.bytes();
+            }
+        }
+
+        if frame_size.exceeds_limit(self.maximum_allowed_size) {
+            span_lint_and_note(
+                cx,
+                LARGE_STACK_FRAMES,
+                span,
+                "this function allocates a large amount of stack space",
+                None,
+                "allocating large amounts of stack space can overflow the stack",
+            );
+        }
+    }
+}
diff --git a/clippy_lints/src/lib.rs b/clippy_lints/src/lib.rs
index dcf1c6f64a4..71447724790 100644
--- a/clippy_lints/src/lib.rs
+++ b/clippy_lints/src/lib.rs
@@ -168,6 +168,7 @@ mod large_enum_variant;
 mod large_futures;
 mod large_include_file;
 mod large_stack_arrays;
+mod large_stack_frames;
 mod len_zero;
 mod let_if_seq;
 mod let_underscore;
@@ -1042,6 +1043,8 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf:
             min_ident_chars_threshold,
         })
     });
+    let stack_size_threshold = conf.stack_size_threshold;
+    store.register_late_pass(move |_| Box::new(large_stack_frames::LargeStackFrames::new(stack_size_threshold)));
     // add lints here, do not remove this comment, it's used in `new_lint`
 }
 
diff --git a/clippy_lints/src/utils/conf.rs b/clippy_lints/src/utils/conf.rs
index 0a581e0ab9b..f6c7c1fa065 100644
--- a/clippy_lints/src/utils/conf.rs
+++ b/clippy_lints/src/utils/conf.rs
@@ -387,6 +387,10 @@ define_Conf! {
     ///
     /// The maximum allowed size for arrays on the stack
     (array_size_threshold: u64 = 512_000),
+    /// Lint: LARGE_STACK_FRAMES.
+    ///
+    /// The maximum allowed stack size for functions in bytes
+    (stack_size_threshold: u64 = 512_000),
     /// Lint: VEC_BOX.
     ///
     /// The size of the boxed type in bytes, where boxing in a `Vec` is allowed
diff --git a/tests/ui-toml/toml_unknown_key/conf_unknown_key.stderr b/tests/ui-toml/toml_unknown_key/conf_unknown_key.stderr
index c546d95eb46..d8ce0e2f55d 100644
--- a/tests/ui-toml/toml_unknown_key/conf_unknown_key.stderr
+++ b/tests/ui-toml/toml_unknown_key/conf_unknown_key.stderr
@@ -44,6 +44,7 @@ error: error reading Clippy's configuration file: unknown field `foobar`, expect
            semicolon-inside-block-ignore-singleline
            semicolon-outside-block-ignore-multiline
            single-char-binding-names-threshold
+           stack-size-threshold
            standard-macro-braces
            suppress-restriction-lint-in-const
            third-party
@@ -109,6 +110,7 @@ error: error reading Clippy's configuration file: unknown field `barfoo`, expect
            semicolon-inside-block-ignore-singleline
            semicolon-outside-block-ignore-multiline
            single-char-binding-names-threshold
+           stack-size-threshold
            standard-macro-braces
            suppress-restriction-lint-in-const
            third-party
diff --git a/tests/ui/large_stack_frames.rs b/tests/ui/large_stack_frames.rs
new file mode 100644
index 00000000000..cd9d0c8a67a
--- /dev/null
+++ b/tests/ui/large_stack_frames.rs
@@ -0,0 +1,44 @@
+#![allow(unused, incomplete_features)]
+#![warn(clippy::large_stack_frames)]
+#![feature(unsized_locals)]
+
+use std::hint::black_box;
+
+fn generic<T: Default>() {
+    let x = T::default();
+    black_box(&x);
+}
+
+fn unsized_local() {
+    let x: dyn std::fmt::Display = *(Box::new(1) as Box<dyn std::fmt::Display>);
+    black_box(&x);
+}
+
+struct ArrayDefault<const N: usize>([u8; N]);
+
+impl<const N: usize> Default for ArrayDefault<N> {
+    fn default() -> Self {
+        Self([0; N])
+    }
+}
+
+fn many_small_arrays() {
+    let x = [0u8; 500_000];
+    let x2 = [0u8; 500_000];
+    let x3 = [0u8; 500_000];
+    let x4 = [0u8; 500_000];
+    let x5 = [0u8; 500_000];
+    black_box((&x, &x2, &x3, &x4, &x5));
+}
+
+fn large_return_value() -> ArrayDefault<1_000_000> {
+    Default::default()
+}
+
+fn large_fn_arg(x: ArrayDefault<1_000_000>) {
+    black_box(&x);
+}
+
+fn main() {
+    generic::<ArrayDefault<1_000_000>>();
+}
diff --git a/tests/ui/large_stack_frames.stderr b/tests/ui/large_stack_frames.stderr
new file mode 100644
index 00000000000..d57df8596fe
--- /dev/null
+++ b/tests/ui/large_stack_frames.stderr
@@ -0,0 +1,37 @@
+error: this function allocates a large amount of stack space
+  --> $DIR/large_stack_frames.rs:25:1
+   |
+LL | / fn many_small_arrays() {
+LL | |     let x = [0u8; 500_000];
+LL | |     let x2 = [0u8; 500_000];
+LL | |     let x3 = [0u8; 500_000];
+...  |
+LL | |     black_box((&x, &x2, &x3, &x4, &x5));
+LL | | }
+   | |_^
+   |
+   = note: allocating large amounts of stack space can overflow the stack
+   = note: `-D clippy::large-stack-frames` implied by `-D warnings`
+
+error: this function allocates a large amount of stack space
+  --> $DIR/large_stack_frames.rs:34:1
+   |
+LL | / fn large_return_value() -> ArrayDefault<1_000_000> {
+LL | |     Default::default()
+LL | | }
+   | |_^
+   |
+   = note: allocating large amounts of stack space can overflow the stack
+
+error: this function allocates a large amount of stack space
+  --> $DIR/large_stack_frames.rs:38:1
+   |
+LL | / fn large_fn_arg(x: ArrayDefault<1_000_000>) {
+LL | |     black_box(&x);
+LL | | }
+   | |_^
+   |
+   = note: allocating large amounts of stack space can overflow the stack
+
+error: aborting due to 3 previous errors
+