clippy_lints/src/cyclomatic_complexity.rs

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