[clang-tidy] Add new hicpp-multiway-paths-covered check for missing branches

Summary:
This check searches for missing `else` branches in `if-else if`-chains and
missing `default` labels in `switch` statements, that use integers as condition.

It is very similar to -Wswitch, but concentrates on integers only, since enums are
already covered.

The option to warn for missing `else` branches is deactivated by default, since it is
very noise on larger code bases.

Running it on LLVM:
{F5354858} for default configuration
{F5354866} just for llvm/lib/Analysis/ScalarEvolution.cpp, the else-path checker is very noisy!

Reviewers: alexfh, aaron.ballman, hokein

Reviewed By: aaron.ballman

Subscribers: lebedev.ri, Eugene.Zelenko, cfe-commits, mgorny, JDevlieghere, xazax.hun

Tags: #clang-tools-extra

Differential Revision: https://reviews.llvm.org/D37808



git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@318600 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 234 insertions, 0 deletions

diff --git a/clang-tidy/hicpp/CMakeLists.txt b/clang-tidy/hicpp/CMakeLists.txt
index fd15d485..5489629c 100644
--- a/clang-tidy/hicpp/CMakeLists.txt
+++ b/clang-tidy/hicpp/CMakeLists.txt
@@ -2,6 +2,7 @@ set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyHICPPModule
   ExceptionBaseclassCheck.cpp
+  MultiwayPathsCoveredCheck.cpp
   NoAssemblerCheck.cpp
   HICPPTidyModule.cpp
   SignedBitwiseCheck.cpp
diff --git a/clang-tidy/hicpp/HICPPTidyModule.cpp b/clang-tidy/hicpp/HICPPTidyModule.cpp
index 359cd579..1c1aeb6d 100644
--- a/clang-tidy/hicpp/HICPPTidyModule.cpp
+++ b/clang-tidy/hicpp/HICPPTidyModule.cpp
@@ -35,6 +35,7 @@
 #include "../readability/FunctionSizeCheck.h"
 #include "../readability/IdentifierNamingCheck.h"
 #include "ExceptionBaseclassCheck.h"
+#include "MultiwayPathsCoveredCheck.h"
 #include "NoAssemblerCheck.h"
 #include "SignedBitwiseCheck.h"
 
@@ -53,6 +54,8 @@ public:
         "hicpp-exception-baseclass");
     CheckFactories.registerCheck<SignedBitwiseCheck>(
         "hicpp-signed-bitwise");
+    CheckFactories.registerCheck<MultiwayPathsCoveredCheck>(
+        "hicpp-multiway-paths-covered");
     CheckFactories.registerCheck<google::ExplicitConstructorCheck>(
         "hicpp-explicit-conversions");
     CheckFactories.registerCheck<readability::FunctionSizeCheck>(
diff --git a/clang-tidy/hicpp/MultiwayPathsCoveredCheck.cpp b/clang-tidy/hicpp/MultiwayPathsCoveredCheck.cpp
new file mode 100644
index 00000000..3894267d
--- /dev/null
+++ b/clang-tidy/hicpp/MultiwayPathsCoveredCheck.cpp
@@ -0,0 +1,179 @@
+//===--- MultiwayPathsCoveredCheck.cpp - clang-tidy------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MultiwayPathsCoveredCheck.h"
+#include "clang/AST/ASTContext.h"
+
+#include <limits>
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace hicpp {
+
+void MultiwayPathsCoveredCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "WarnOnMissingElse", WarnOnMissingElse);
+}
+
+void MultiwayPathsCoveredCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(
+      stmt(allOf(
+          anyOf(switchStmt(forEachSwitchCase(defaultStmt()))
+                    .bind("switch-default"),
+                switchStmt(unless(hasDescendant(switchCase())))
+                    .bind("degenerate-switch"),
+                // This matcher must be the last one of the three
+                // 'switchStmt' options.
+                // Otherwise the cases 'switch-default' and
+                // 'degenerate-switch' are not found correctly.
+                switchStmt(forEachSwitchCase(unless(defaultStmt())))
+                    .bind("switch-no-default")),
+          switchStmt(hasCondition(allOf(
+              // Match on switch statements that have either a bit-field or an
+              // integer condition. The ordering in 'anyOf()' is important
+              // because the last condition is the most general.
+              anyOf(ignoringImpCasts(memberExpr(hasDeclaration(
+                        fieldDecl(isBitField()).bind("bitfield")))),
+                    hasDescendant(declRefExpr().bind("non-enum-condition"))),
+              // 'unless()' must be the last match here and must be bound,
+              // otherwise the matcher does not work correctly.
+              unless(hasDescendant(declRefExpr(hasType(enumType()))
+                                       .bind("enum-condition")))))))),
+      this);
+
+  // This option is noisy, therefore matching is configurable.
+  if (WarnOnMissingElse) {
+    Finder->addMatcher(
+        ifStmt(allOf(hasParent(ifStmt()), unless(hasElse(anything()))))
+            .bind("else-if"),
+        this);
+  }
+}
+
+static unsigned countCaseLabels(const SwitchStmt *Switch) {
+  unsigned CaseCount = 0;
+
+  const SwitchCase *CurrentCase = Switch->getSwitchCaseList();
+  while (CurrentCase) {
+    ++CaseCount;
+    CurrentCase = CurrentCase->getNextSwitchCase();
+  }
+
+  return CaseCount;
+}
+/// This function calculate 2 ** Bits and returns
+/// numeric_limits<std::size_t>::max() if an overflow occured.
+static std::size_t twoPow(std::size_t Bits) {
+  return Bits >= std::numeric_limits<std::size_t>::digits
+             ? std::numeric_limits<std::size_t>::max()
+             : static_cast<size_t>(1) << Bits;
+}
+/// Get the number of possible values that can be switched on for the type T.
+///
+/// \return - 0 if bitcount could not be determined
+///         - numeric_limits<std::size_t>::max() when overflow appeared due to
+///           more then 64 bits type size.
+static std::size_t getNumberOfPossibleValues(QualType T,
+                                             const ASTContext &Context) {
+  // `isBooleanType` must come first because `bool` is an integral type as well
+  // and would not return 2 as result.
+  if (T->isBooleanType())
+    return 2;
+  else if (T->isIntegralType(Context))
+    return twoPow(Context.getTypeSize(T));
+  else
+    return 1;
+}
+
+void MultiwayPathsCoveredCheck::check(const MatchFinder::MatchResult &Result) {
+  if (const auto *ElseIfWithoutElse =
+          Result.Nodes.getNodeAs<IfStmt>("else-if")) {
+    diag(ElseIfWithoutElse->getLocStart(),
+         "potentially uncovered codepath; add an ending else statement");
+    return;
+  }
+  // Checks the sanity of 'switch' statements that actually do define
+  // a default branch but might be degenerated by having no or only one case.
+  if (const auto *SwitchWithDefault =
+          Result.Nodes.getNodeAs<SwitchStmt>("switch-default")) {
+    handleSwitchWithDefault(SwitchWithDefault);
+    return;
+  }
+  // Checks all 'switch' statements that do not define a default label.
+  // Here the heavy lifting happens.
+  if (const auto *SwitchWithoutDefault =
+          Result.Nodes.getNodeAs<SwitchStmt>("switch-no-default")) {
+    handleSwitchWithoutDefault(SwitchWithoutDefault, Result);
+    return;
+  }
+  // Warns for degenerated 'switch' statements that neither define a case nor
+  // a default label.
+  if (const auto *DegenerateSwitch =
+          Result.Nodes.getNodeAs<SwitchStmt>("degenerate-switch")) {
+    diag(DegenerateSwitch->getLocStart(), "degenerated switch without labels");
+    return;
+  }
+  llvm_unreachable("matched a case, that was not explicitly handled");
+}
+
+void MultiwayPathsCoveredCheck::handleSwitchWithDefault(
+    const SwitchStmt *Switch) {
+  unsigned CaseCount = countCaseLabels(Switch);
+  assert(CaseCount > 0 && "Switch statement with supposedly one default "
+                          "branch did not contain any case labels");
+  if (CaseCount == 1 || CaseCount == 2)
+    diag(Switch->getLocStart(),
+         CaseCount == 1
+             ? "degenerated switch with default label only"
+             : "switch could be better written as an if/else statement");
+}
+
+void MultiwayPathsCoveredCheck::handleSwitchWithoutDefault(
+    const SwitchStmt *Switch, const MatchFinder::MatchResult &Result) {
+  // The matcher only works because some nodes are explicitly matched and
+  // bound but ignored. This is necessary to build the excluding logic for
+  // enums and 'switch' statements without a 'default' branch.
+  assert(!Result.Nodes.getNodeAs<DeclRefExpr>("enum-condition") &&
+         "switch over enum is handled by warnings already, explicitly ignoring "
+         "them");
+  assert(!Result.Nodes.getNodeAs<SwitchStmt>("switch-default") &&
+         "switch stmts with default branch do cover all paths, explicitly "
+         "ignoring them");
+  // Determine the number of case labels. Since 'default' is not present
+  // and duplicating case labels is not allowed this number represents
+  // the number of codepaths. It can be directly compared to 'MaxPathsPossible'
+  // to see if some cases are missing.
+  unsigned CaseCount = countCaseLabels(Switch);
+  // CaseCount == 0 is caught in DegenerateSwitch. Necessary because the
+  // matcher used for here does not match on degenerate 'switch'.
+  assert(CaseCount > 0 && "Switch statement without any case found. This case "
+                          "should be excluded by the matcher and is handled "
+                          "separatly.");
+  std::size_t MaxPathsPossible = [&]() {
+    if (const auto *GeneralCondition =
+            Result.Nodes.getNodeAs<DeclRefExpr>("non-enum-condition"))
+      return getNumberOfPossibleValues(GeneralCondition->getType(),
+                                       *Result.Context);
+    if (const auto *BitfieldDecl =
+            Result.Nodes.getNodeAs<FieldDecl>("bitfield"))
+      return twoPow(BitfieldDecl->getBitWidthValue(*Result.Context));
+    llvm_unreachable("either bit-field or non-enum must be condition");
+  }();
+
+  // FIXME: Transform the 'switch' into an 'if' for CaseCount == 1.
+  if (CaseCount < MaxPathsPossible)
+    diag(Switch->getLocStart(),
+         CaseCount == 1 ? "switch with only one case; use an if statement"
+                        : "potential uncovered code path; add a default label");
+}
+} // namespace hicpp
+} // namespace tidy
+} // namespace clang
diff --git a/clang-tidy/hicpp/MultiwayPathsCoveredCheck.h b/clang-tidy/hicpp/MultiwayPathsCoveredCheck.h
new file mode 100644
index 00000000..58414d4f
--- /dev/null
+++ b/clang-tidy/hicpp/MultiwayPathsCoveredCheck.h
@@ -0,0 +1,51 @@
+//===--- MultiwayPathsCoveredCheck.h - clang-tidy----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_HICPP_MULTIWAY_PATHS_COVERED_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_HICPP_MULTIWAY_PATHS_COVERED_H
+
+#include "../ClangTidy.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include <iostream>
+
+namespace clang {
+namespace tidy {
+namespace hicpp {
+
+/// Find occasions where not all codepaths are explicitly covered in code.
+/// This includes 'switch' without a 'default'-branch and 'if'-'else if'-chains
+/// without a final 'else'-branch.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/hicpp-multiway-paths-covered.html
+class MultiwayPathsCoveredCheck : public ClangTidyCheck {
+public:
+  MultiwayPathsCoveredCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context),
+        WarnOnMissingElse(Options.get("WarnOnMissingElse", 0)) {}
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  void handleSwitchWithDefault(const SwitchStmt *Switch);
+  void handleSwitchWithoutDefault(
+      const SwitchStmt *Switch,
+      const ast_matchers::MatchFinder::MatchResult &Result);
+  /// This option can be configured to warn on missing 'else' branches in an
+  /// 'if-else if' chain. The default is false because this option might be
+  /// noisy on some code bases.
+  const bool WarnOnMissingElse;
+};
+
+} // namespace hicpp
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_HICPP_MULTIWAY_PATHS_COVERED_H