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::ty;
   6 use rustc::hir::*;
   7 use rustc::hir::intravisit::{Visitor, walk_expr, NestedVisitorMap};
   8 use syntax::ast::Attribute;
   9 use syntax::attr;
  10 use syntax::codemap::Span;
  11
  12 use utils::{in_macro, LimitStack, span_help_and_lint, paths, match_type};
  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 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         CyclomaticComplexity { 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>, expr: &'tcx Expr, span: Span) {
  46         if in_macro(cx, span) {
  47             return;
  48         }
  49
  50         let cfg = CFG::new(cx.tcx, expr);
  51         let n = cfg.graph.len_nodes() as u64;
  52         let e = cfg.graph.len_edges() as u64;
  53         if e + 2 < n {
  54             // the function has unreachable code, other lints should catch this
  55             return;
  56         }
  57         let cc = e + 2 - n;
  58         let mut helper = CCHelper {
  59             match_arms: 0,
  60             divergence: 0,
  61             short_circuits: 0,
  62             returns: 0,
  63             cx: cx,
  64         };
  65         helper.visit_expr(expr);
  66         let CCHelper { match_arms, divergence, short_circuits, returns, .. } = helper;
  67         let ret_ty = cx.tcx.tables().node_id_to_type(expr.id);
  68         let ret_adjust = if match_type(cx, ret_ty, &paths::RESULT) {
  69             returns
  70         } else {
  71             returns / 2
  72         };
  73
  74         if cc + divergence < match_arms + short_circuits {
  75             report_cc_bug(cx, cc, match_arms, divergence, short_circuits, ret_adjust, span);
  76         } else {
  77             let mut rust_cc = cc + divergence - match_arms - short_circuits;
  78             // prevent degenerate cases where unreachable code contains `return` statements
  79             if rust_cc >= ret_adjust {
  80                 rust_cc -= ret_adjust;
  81             }
  82             if rust_cc > self.limit.limit() {
  83                 span_help_and_lint(cx,
  84                                    CYCLOMATIC_COMPLEXITY,
  85                                    span,
  86                                    &format!("the function has a cyclomatic complexity of {}", rust_cc),
  87                                    "you could split it up into multiple smaller functions");
  88             }
  89         }
  90     }
  91 }
  92
  93 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for CyclomaticComplexity {
  94     fn check_item(&mut self, cx: &LateContext<'a, 'tcx>, item: &'tcx Item) {
  95         if let ItemFn(_, _, _, _, _, eid) = item.node {
  96             if !attr::contains_name(&item.attrs, "test") {
  97                 self.check(cx, cx.tcx.map.expr(eid), item.span);
  98             }
  99         }
 100     }
 101
 102     fn check_impl_item(&mut self, cx: &LateContext<'a, 'tcx>, item: &'tcx ImplItem) {
 103         if let ImplItemKind::Method(_, eid) = item.node {
 104             self.check(cx, cx.tcx.map.expr(eid), item.span);
 105         }
 106     }
 107
 108     fn check_trait_item(&mut self, cx: &LateContext<'a, 'tcx>, item: &'tcx TraitItem) {
 109         if let MethodTraitItem(_, Some(eid)) = item.node {
 110             self.check(cx, cx.tcx.map.expr(eid), item.span);
 111         }
 112     }
 113
 114     fn enter_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 115         self.limit.push_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 116     }
 117     fn exit_lint_attrs(&mut self, cx: &LateContext<'a, 'tcx>, attrs: &'tcx [Attribute]) {
 118         self.limit.pop_attrs(cx.sess(), attrs, "cyclomatic_complexity");
 119     }
 120 }
 121
 122 struct CCHelper<'a, 'tcx: 'a> {
 123     match_arms: u64,
 124     divergence: u64,
 125     returns: u64,
 126     short_circuits: u64, // && and ||
 127     cx: &'a LateContext<'a, 'tcx>,
 128 }
 129
 130 impl<'a, 'tcx> Visitor<'tcx> for CCHelper<'a, 'tcx> {
 131     fn visit_expr(&mut self, e: &'tcx Expr) {
 132         match e.node {
 133             ExprMatch(_, ref arms, _) => {
 134                 walk_expr(self, e);
 135                 let arms_n: u64 = arms.iter().map(|arm| arm.pats.len() as u64).sum();
 136                 if arms_n > 1 {
 137                     self.match_arms += arms_n - 2;
 138                 }
 139             }
 140             ExprCall(ref callee, _) => {
 141                 walk_expr(self, e);
 142                 let ty = self.cx.tcx.tables().node_id_to_type(callee.id);
 143                 match ty.sty {
 144                     ty::TyFnDef(_, _, ty) |
 145                     ty::TyFnPtr(ty) if ty.sig.skip_binder().output.sty == ty::TyNever => {
 146                         self.divergence += 1;
 147                     }
 148                     _ => (),
 149                 }
 150             }
 151             ExprClosure(..) => (),
 152             ExprBinary(op, _, _) => {
 153                 walk_expr(self, e);
 154                 match op.node {
 155                     BiAnd | BiOr => self.short_circuits += 1,
 156                     _ => (),
 157                 }
 158             }
 159             ExprRet(_) => self.returns += 1,
 160             _ => walk_expr(self, e),
 161         }
 162     }
 163     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 164         NestedVisitorMap::None
 165     }
 166 }
 167
 168 #[cfg(feature="debugging")]
 169 fn report_cc_bug(_: &LateContext, cc: u64, narms: u64, div: u64, shorts: u64, returns: u64, span: Span) {
 170     span_bug!(span,
 171               "Clippy encountered a bug calculating cyclomatic complexity: cc = {}, arms = {}, \
 172                div = {}, shorts = {}, returns = {}. Please file a bug report.",
 173               cc,
 174               narms,
 175               div,
 176               shorts,
 177               returns);
 178 }
 179 #[cfg(not(feature="debugging"))]
 180 fn report_cc_bug(cx: &LateContext, cc: u64, narms: u64, div: u64, shorts: u64, returns: u64, span: Span) {
 181     if cx.current_level(CYCLOMATIC_COMPLEXITY) != Level::Allow {
 182         cx.sess().span_note_without_error(span,
 183                                           &format!("Clippy encountered a bug calculating cyclomatic complexity \
 184                                                     (hide this message with `#[allow(cyclomatic_complexity)]`): \
 185                                                     cc = {}, arms = {}, div = {}, shorts = {}, returns = {}. \
 186                                                     Please file a bug report.",
 187                                                    cc,
 188                                                    narms,
 189                                                    div,
 190                                                    shorts,
 191                                                    returns));
 192     }
 193 }