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