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::{declare_lint, lint_array};
   6 use rustc::hir::*;
   7 use rustc::ty;
   8 use rustc::hir::intravisit::{walk_expr, NestedVisitorMap, Visitor};
   9 use syntax::ast::{Attribute, NodeId};
  10 use syntax::codemap::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
  47 impl CyclomaticComplexity {
  48     fn check<'a, 'tcx: 'a>(&mut self, cx: &'a LateContext<'a, 'tcx>, body: &'tcx Body, span: Span) {
  49         if in_macro(span) {
  50             return;
  51         }
  52
  53         let cfg = CFG::new(cx.tcx, body);
  54         let expr = &body.value;
  55         let n = cfg.graph.len_nodes() as u64;
  56         let e = cfg.graph.len_edges() as u64;
  57         if e + 2 < n {
  58             // the function has unreachable code, other lints should catch this
  59             return;
  60         }
  61         let cc = e + 2 - n;
  62         let mut helper = CCHelper {
  63             match_arms: 0,
  64             divergence: 0,
  65             short_circuits: 0,
  66             returns: 0,
  67             cx,
  68         };
  69         helper.visit_expr(expr);
  70         let CCHelper {
  71             match_arms,
  72             divergence,
  73             short_circuits,
  74             returns,
  75             ..
  76         } = helper;
  77         let ret_ty = cx.tables.node_id_to_type(expr.hir_id);
  78         let ret_adjust = if match_type(cx, ret_ty, &paths::RESULT) {
  79             returns
  80         } else {
  81             returns / 2
  82         };
  83
  84         if cc + divergence < match_arms + short_circuits {
  85             report_cc_bug(
  86                 cx,
  87                 cc,
  88                 match_arms,
  89                 divergence,
  90                 short_circuits,
  91                 ret_adjust,
  92                 span,
  93                 body.id().node_id,
  94             );
  95         } else {
  96             let mut rust_cc = cc + divergence - match_arms - short_circuits;
  97             // prevent degenerate cases where unreachable code contains `return` statements
  98             if rust_cc >= ret_adjust {
  99                 rust_cc -= ret_adjust;
 100             }
 101             if rust_cc > self.limit.limit() {
 102                 span_help_and_lint(
 103                     cx,
 104                     CYCLOMATIC_COMPLEXITY,
 105                     span,
 106                     &format!("the function has a cyclomatic complexity of {}", rust_cc),
 107                     "you could split it up into multiple smaller functions",
 108                 );
 109             }
 110         }
 111     }
 112 }
 113
 114 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for CyclomaticComplexity {
 115     fn check_fn(
 116         &mut self,
 117         cx: &LateContext<'a, 'tcx>,
 118         _: intravisit::FnKind<'tcx>,
 119         _: &'tcx FnDecl,
 120         body: &'tcx Body,
 121         span: Span,
 122         node_id: NodeId,
 123     ) {
 124         let def_id = cx.tcx.hir.local_def_id(node_id);
 125         if !cx.tcx.has_attr(def_id, "test") {
 126             self.check(cx, body, span);
 127         }
 128     }
 129
 130     fn enter_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 131         self.limit
 132             .push_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 133     }
 134     fn exit_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 135         self.limit
 136             .pop_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 137     }
 138 }
 139
 140 struct CCHelper<'a, 'tcx: 'a> {
 141     match_arms: u64,
 142     divergence: u64,
 143     returns: u64,
 144     short_circuits: u64, // && and ||
 145     cx: &'a LateContext<'a, 'tcx>,
 146 }
 147
 148 impl<'a, 'tcx> Visitor<'tcx> for CCHelper<'a, 'tcx> {
 149     fn visit_expr(&mut self, e: &'tcx Expr) {
 150         match e.node {
 151             ExprKind::Match(_, ref arms, _) => {
 152                 walk_expr(self, e);
 153                 let arms_n: u64 = arms.iter().map(|arm| arm.pats.len() as u64).sum();
 154                 if arms_n > 1 {
 155                     self.match_arms += arms_n - 2;
 156                 }
 157             },
 158             ExprKind::Call(ref callee, _) => {
 159                 walk_expr(self, e);
 160                 let ty = self.cx.tables.node_id_to_type(callee.hir_id);
 161                 match ty.sty {
 162                     ty::TyFnDef(..) | ty::TyFnPtr(_) => {
 163                         let sig = ty.fn_sig(self.cx.tcx);
 164                         if sig.skip_binder().output().sty == ty::TyNever {
 165                             self.divergence += 1;
 166                         }
 167                     },
 168                     _ => (),
 169                 }
 170             },
 171             ExprKind::Closure(.., _) => (),
 172             ExprKind::Binary(op, _, _) => {
 173                 walk_expr(self, e);
 174                 match op.node {
 175                     BinOpKind::And | BinOpKind::Or => self.short_circuits += 1,
 176                     _ => (),
 177                 }
 178             },
 179             ExprKind::Ret(_) => self.returns += 1,
 180             _ => walk_expr(self, e),
 181         }
 182     }
 183     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 184         NestedVisitorMap::None
 185     }
 186 }
 187
 188 #[cfg(feature = "debugging")]
 189 #[allow(too_many_arguments)]
 190 fn report_cc_bug(_: &LateContext, cc: u64, narms: u64, div: u64, shorts: u64, returns: u64, span: Span, _: NodeId) {
 191     span_bug!(
 192         span,
 193         "Clippy encountered a bug calculating cyclomatic complexity: cc = {}, arms = {}, \
 194          div = {}, shorts = {}, returns = {}. Please file a bug report.",
 195         cc,
 196         narms,
 197         div,
 198         shorts,
 199         returns
 200     );
 201 }
 202 #[cfg(not(feature = "debugging"))]
 203 #[allow(too_many_arguments)]
 204 fn report_cc_bug(cx: &LateContext, cc: u64, narms: u64, div: u64, shorts: u64, returns: u64, span: Span, id: NodeId) {
 205     if !is_allowed(cx, CYCLOMATIC_COMPLEXITY, id) {
 206         cx.sess().span_note_without_error(
 207             span,
 208             &format!(
 209                 "Clippy encountered a bug calculating cyclomatic complexity \
 210                  (hide this message with `#[allow(cyclomatic_complexity)]`): \
 211                  cc = {}, arms = {}, div = {}, shorts = {}, returns = {}. \
 212                  Please file a bug report.",
 213                 cc,
 214                 narms,
 215                 div,
 216                 shorts,
 217                 returns
 218             ),
 219         );
 220     }
 221 }