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