clippy_lints/src/cyclomatic_complexity.rs

   1 // Copyright 2014-2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution.
   3 //
   4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   5 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   7 // option. This file may not be copied, modified, or distributed
   8 // except according to those terms.
   9
  10 //! calculate cyclomatic complexity and warn about overly complex functions
  11
  12 use crate::rustc::cfg::CFG;
  13 use crate::rustc::hir::intravisit::{walk_expr, NestedVisitorMap, Visitor};
  14 use crate::rustc::hir::*;
  15 use crate::rustc::lint::{LateContext, LateLintPass, LintArray, LintContext, LintPass};
  16 use crate::rustc::ty;
  17 use crate::rustc::{declare_tool_lint, lint_array};
  18 use crate::syntax::ast::{Attribute, NodeId};
  19 use crate::syntax::source_map::Span;
  20
  21 use crate::utils::{in_macro, is_allowed, match_type, paths, span_help_and_lint, LimitStack};
  22
  23 /// **What it does:** Checks for methods with high cyclomatic complexity.
  24 ///
  25 /// **Why is this bad?** Methods of high cyclomatic complexity tend to be badly
  26 /// readable. Also LLVM will usually optimize small methods better.
  27 ///
  28 /// **Known problems:** Sometimes it's hard to find a way to reduce the
  29 /// complexity.
  30 ///
  31 /// **Example:** No. You'll see it when you get the warning.
  32 declare_clippy_lint! {
  33     pub CYCLOMATIC_COMPLEXITY,
  34     complexity,
  35     "functions that should be split up into multiple functions"
  36 }
  37
  38 pub struct CyclomaticComplexity {
  39     limit: LimitStack,
  40 }
  41
  42 impl CyclomaticComplexity {
  43     pub fn new(limit: u64) -> Self {
  44         Self {
  45             limit: LimitStack::new(limit),
  46         }
  47     }
  48 }
  49
  50 impl LintPass for CyclomaticComplexity {
  51     fn get_lints(&self) -> LintArray {
  52         lint_array!(CYCLOMATIC_COMPLEXITY)
  53     }
  54 }
  55
  56 impl CyclomaticComplexity {
  57     fn check<'a, 'tcx: 'a>(&mut self, cx: &'a LateContext<'a, 'tcx>, body: &'tcx Body, span: Span) {
  58         if in_macro(span) {
  59             return;
  60         }
  61
  62         let cfg = CFG::new(cx.tcx, body);
  63         let expr = &body.value;
  64         let n = cfg.graph.len_nodes() as u64;
  65         let e = cfg.graph.len_edges() as u64;
  66         if e + 2 < n {
  67             // the function has unreachable code, other lints should catch this
  68             return;
  69         }
  70         let cc = e + 2 - n;
  71         let mut helper = CCHelper {
  72             match_arms: 0,
  73             divergence: 0,
  74             short_circuits: 0,
  75             returns: 0,
  76             cx,
  77         };
  78         helper.visit_expr(expr);
  79         let CCHelper {
  80             match_arms,
  81             divergence,
  82             short_circuits,
  83             returns,
  84             ..
  85         } = helper;
  86         let ret_ty = cx.tables.node_id_to_type(expr.hir_id);
  87         let ret_adjust = if match_type(cx, ret_ty, &paths::RESULT) {
  88             returns
  89         } else {
  90             returns / 2
  91         };
  92
  93         if cc + divergence < match_arms + short_circuits {
  94             report_cc_bug(
  95                 cx,
  96                 cc,
  97                 match_arms,
  98                 divergence,
  99                 short_circuits,
 100                 ret_adjust,
 101                 span,
 102                 body.id().node_id,
 103             );
 104         } else {
 105             let mut rust_cc = cc + divergence - match_arms - short_circuits;
 106             // prevent degenerate cases where unreachable code contains `return` statements
 107             if rust_cc >= ret_adjust {
 108                 rust_cc -= ret_adjust;
 109             }
 110             if rust_cc > self.limit.limit() {
 111                 span_help_and_lint(
 112                     cx,
 113                     CYCLOMATIC_COMPLEXITY,
 114                     span,
 115                     &format!("the function has a cyclomatic complexity of {}", rust_cc),
 116                     "you could split it up into multiple smaller functions",
 117                 );
 118             }
 119         }
 120     }
 121 }
 122
 123 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for CyclomaticComplexity {
 124     fn check_fn(
 125         &mut self,
 126         cx: &LateContext<'a, 'tcx>,
 127         _: intravisit::FnKind<'tcx>,
 128         _: &'tcx FnDecl,
 129         body: &'tcx Body,
 130         span: Span,
 131         node_id: NodeId,
 132     ) {
 133         let def_id = cx.tcx.hir().local_def_id(node_id);
 134         if !cx.tcx.has_attr(def_id, "test") {
 135             self.check(cx, body, span);
 136         }
 137     }
 138
 139     fn enter_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 140         self.limit.push_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 141     }
 142     fn exit_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 143         self.limit.pop_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 144     }
 145 }
 146
 147 struct CCHelper<'a, 'tcx: 'a> {
 148     match_arms: u64,
 149     divergence: u64,
 150     returns: u64,
 151     short_circuits: u64, // && and ||
 152     cx: &'a LateContext<'a, 'tcx>,
 153 }
 154
 155 impl<'a, 'tcx> Visitor<'tcx> for CCHelper<'a, 'tcx> {
 156     fn visit_expr(&mut self, e: &'tcx Expr) {
 157         match e.node {
 158             ExprKind::Match(_, ref arms, _) => {
 159                 walk_expr(self, e);
 160                 let arms_n: u64 = arms.iter().map(|arm| arm.pats.len() as u64).sum();
 161                 if arms_n > 1 {
 162                     self.match_arms += arms_n - 2;
 163                 }
 164             },
 165             ExprKind::Call(ref callee, _) => {
 166                 walk_expr(self, e);
 167                 let ty = self.cx.tables.node_id_to_type(callee.hir_id);
 168                 match ty.sty {
 169                     ty::FnDef(..) | ty::FnPtr(_) => {
 170                         let sig = ty.fn_sig(self.cx.tcx);
 171                         if sig.skip_binder().output().sty == ty::Never {
 172                             self.divergence += 1;
 173                         }
 174                     },
 175                     _ => (),
 176                 }
 177             },
 178             ExprKind::Closure(.., _) => (),
 179             ExprKind::Binary(op, _, _) => {
 180                 walk_expr(self, e);
 181                 match op.node {
 182                     BinOpKind::And | BinOpKind::Or => self.short_circuits += 1,
 183                     _ => (),
 184                 }
 185             },
 186             ExprKind::Ret(_) => self.returns += 1,
 187             _ => walk_expr(self, e),
 188         }
 189     }
 190     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 191         NestedVisitorMap::None
 192     }
 193 }
 194
 195 #[cfg(feature = "debugging")]
 196 #[allow(clippy::too_many_arguments)]
 197 fn report_cc_bug(
 198     _: &LateContext<'_, '_>,
 199     cc: u64,
 200     narms: u64,
 201     div: u64,
 202     shorts: u64,
 203     returns: u64,
 204     span: Span,
 205     _: NodeId,
 206 ) {
 207     span_bug!(
 208         span,
 209         "Clippy encountered a bug calculating cyclomatic complexity: cc = {}, arms = {}, \
 210          div = {}, shorts = {}, returns = {}. Please file a bug report.",
 211         cc,
 212         narms,
 213         div,
 214         shorts,
 215         returns
 216     );
 217 }
 218 #[cfg(not(feature = "debugging"))]
 219 #[allow(clippy::too_many_arguments)]
 220 fn report_cc_bug(
 221     cx: &LateContext<'_, '_>,
 222     cc: u64,
 223     narms: u64,
 224     div: u64,
 225     shorts: u64,
 226     returns: u64,
 227     span: Span,
 228     id: NodeId,
 229 ) {
 230     if !is_allowed(cx, CYCLOMATIC_COMPLEXITY, id) {
 231         cx.sess().span_note_without_error(
 232             span,
 233             &format!(
 234                 "Clippy encountered a bug calculating cyclomatic complexity \
 235                  (hide this message with `#[allow(cyclomatic_complexity)]`): \
 236                  cc = {}, arms = {}, div = {}, shorts = {}, returns = {}. \
 237                  Please file a bug report.",
 238                 cc, narms, div, shorts, returns
 239             ),
 240         );
 241     }
 242 }