new lint: `large_stack_frames`

9 files changed, 262 insertions, 1 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2d62bfd4f99..8624fa136e7 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4815,6 +4815,7 @@ Released 2018-09-13
 [`get_last_with_len`]: https://rust-lang.github.io/rust-clippy/master/index.html#get_last_with_len
 [`get_unwrap`]: https://rust-lang.github.io/rust-clippy/master/index.html#get_unwrap
 [`host_endian_bytes`]: https://rust-lang.github.io/rust-clippy/master/index.html#host_endian_bytes
+[`large_stack_frames`]: https://rust-lang.github.io/rust-clippy/master/index.html#large_stack_frames
 [`identity_conversion`]: https://rust-lang.github.io/rust-clippy/master/index.html#identity_conversion
 [`identity_op`]: https://rust-lang.github.io/rust-clippy/master/index.html#identity_op
 [`if_let_mutex`]: https://rust-lang.github.io/rust-clippy/master/index.html#if_let_mutex
diff --git a/book/src/lint_configuration.md b/book/src/lint_configuration.md
index b2e11d8de67..9e8729a1afe 100644
--- a/book/src/lint_configuration.md
+++ b/book/src/lint_configuration.md
@@ -338,7 +338,15 @@ 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)
 
 
-## `vec-box-size-threshold`
+### stack-size-threshold
+The maximum allowed stack size for functions in bytes
+
+**Default Value:** `512000` (`u64`)
+
+* [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
 
 **Default Value:** `4096` (`u64`)
diff --git a/clippy_lints/src/declared_lints.rs b/clippy_lints/src/declared_lints.rs
index 769774b27c4..8fd8705b445 100644
--- a/clippy_lints/src/declared_lints.rs
+++ b/clippy_lints/src/declared_lints.rs
@@ -198,6 +198,7 @@ pub(crate) static LINTS: &[&crate::LintInfo] = &[
     crate::functions::TOO_MANY_ARGUMENTS_INFO,
     crate::functions::TOO_MANY_LINES_INFO,
     crate::future_not_send::FUTURE_NOT_SEND_INFO,
+    crate::large_stack_frames::LARGE_STACK_FRAMES_INFO,
     crate::if_let_mutex::IF_LET_MUTEX_INFO,
     crate::if_not_else::IF_NOT_ELSE_INFO,
     crate::if_then_some_else_none::IF_THEN_SOME_ELSE_NONE_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..2ab1f669460
--- /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_then;
+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 (with `-Zmir-opt-level=0`):
+    /// ```rust,ignore
+    /// fn main() {
+    ///     if false {
+    ///         let x = [0u8; 10000000]; // 10 MB stack array
+    ///         black_box(&x);
+    ///     }
+    /// }
+    /// ```
+    ///
+    /// ### Drawbacks
+    /// 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 locals and comparing them against a (configurable, but high-by-default)
+    /// threshold.
+    /// Note that "locals" in this context refers to [MIR locals](https://rustc-dev-guide.rust-lang.org/mir/index.html#key-mir-vocabulary),
+    /// i.e. real local variables that the user typed, storage for temporary values, function arguments
+    /// and the return value.
+    ///
+    /// ### 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();
+
+        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_then(
+                cx,
+                LARGE_STACK_FRAMES,
+                span,
+                "this function allocates a large amount of stack space",
+                |diag| {
+                    diag.note("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..2fa95e2b447 100644
--- a/clippy_lints/src/lib.rs
+++ b/clippy_lints/src/lib.rs
@@ -142,6 +142,7 @@ mod from_raw_with_void_ptr;
 mod from_str_radix_10;
 mod functions;
 mod future_not_send;
+mod large_stack_frames;
 mod if_let_mutex;
 mod if_not_else;
 mod if_then_some_else_none;
@@ -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..79af9cc9ac0 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
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
+