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