[clang-tidy] new check: bugprone-branch-clone

[Szelethus]

Summary

Implement a check for detecting if/else if/else chains where two or more
branches are Type I clones of each other (that is, they contain identical code)
and for detecting switch statements where two or more consecutive branches are
Type I clones of each other.

[Eugene.Zelenko]

clang-tidy/bugprone/BranchCloneCheck.cpp

19

Please use anonymous namespaces only for type declarations. See LLV coding style guide.

43

Please use size_t.

122

Please use size_t. Same for loop variables. Clang complains about such conversions.

docs/ReleaseNotes.rst

70

Please use alphabetical order for new checks list.

docs/clang-tidy/checks/bugprone-branch-clone.rst

6

Please first statement same as Release Notes.

[lebedev.ri]

clang-tidy/bugprone/BranchCloneCheck.cpp

43

Also

for (unsigned i = 0, unsigned Size = LHS.size(); i < Size; i++) {

[whisperity]

Bar the previous comments, I really like this. The test suite is massive and well-constructed. Do we know of any real-world findings, maybe even from LLVM?

[Eugene.Zelenko]

In D54757#1305114, @whisperity wrote:

Bar the previous comments, I really like this. The test suite is massive and well-constructed. Do we know of any real-world findings, maybe even from LLVM?

GCC 7 introduced -Wduplicated-branches, so will be good idea to run this check on associated regression(s).

[whisperity]

In D54757#1305306, @Eugene.Zelenko wrote:

In D54757#1305114, @whisperity wrote:

Bar the previous comments, I really like this. The test suite is massive and well-constructed. Do we know of any real-world findings, maybe even from LLVM?

GCC 7 introduced -Wduplicated-branches, so will be good idea to run this check on associated regression(s).

Compared to Donát's checker, GCC's warning seems much more underperforming. See https://godbolt.org/z/Iq3FC9.

[donat.nagy]

Implement suggested improvements

[donat.nagy]

An example of duplicated code in Clang (it appears in llvm/tools/clang/lib/Frontend/Rewrite/RewriteMacros.cpp starting from line 128):

// If this is a #warning directive or #pragma mark (GNU extensions),
// comment the line out.
if (RawTokens[CurRawTok].is(tok::identifier)) {
  const IdentifierInfo *II = RawTokens[CurRawTok].getIdentifierInfo();
  if (II->getName() == "warning") {
    // Comment out #warning.
    RB.InsertTextAfter(SM.getFileOffset(RawTok.getLocation()), "//");       // THIS IS...
  } else if (II->getName() == "pragma" &&
             RawTokens[CurRawTok+1].is(tok::identifier) &&
             (RawTokens[CurRawTok+1].getIdentifierInfo()->getName() ==
              "mark")) {
    // Comment out #pragma mark.
    RB.InsertTextAfter(SM.getFileOffset(RawTok.getLocation()), "//");       // IDENTICAL TO THIS
  }
}

[JonasToth]

Thank you for this great patch!

Did you consider using clang/Tooling/ASTDiff/* functionality, as there is the possibility of just comparing the AST 'below' the branches?

Please add tests that contain macros as well, and what do you think should happen with them? I think it would be very valuable to figure out that different macro expansion result in the same code.

clang-tidy/bugprone/BranchCloneCheck.cpp

32

maybe plural for the typename would fit better, as its a vector of multiple elements?

47

You can ellide the single-stmt braces here, maybe its better to move the comment above the for then?

72

This if should always be true, no? The matcher will always bind ifParent

84

This detection can and should land in the matcher, to filter as much as possible already while matching.

89

Please don't use else after return. You can ellide the braces in the if as well.

114

you can ellide the braces.

117

This note is misplaced? The exit is at the break.

121

please dont use const for values, only pointers and references

125

braces, i will stop pointing at it. Please do it on the other parts as well

154

i think you can use early return here, if yes, no else afterwards.

165

typo, branhces

188

i think the name FamilyEnd is not very descriptive, maybe SubsequentBranch or so?

197–198

please use std::distance instead

docs/clang-tidy/checks/list.rst

13

spurious change

test/clang-tidy/bugprone-branch-clone.cpp

5

could you please add tests for ternary operators?

[donat.nagy]

Remove braces, move if parent checking to ASTMatcher, other minor improvements

[donat.nagy]

I will add tests for macro handling later.

clang-tidy/bugprone/BranchCloneCheck.cpp

72

I moved this check to the AST matcher.

117

The note was placed correctly, but I replaced it with a break.

docs/clang-tidy/checks/list.rst

13

It was added automatically by the python script, which sorts this list alphabetically. If I remove it now, it will be automatically re-added later.

test/clang-tidy/bugprone-branch-clone.cpp

5

Currently the check does not handle ternary operators, but I added some checks reflecting this.

[donat.nagy]

Minor simplifications, add tests for macro handling

[donat.nagy]

AstDiff:

I looked at the AstDiff library, but I think that it is overkill for my goals. The main feat of the AstDiff library is analyzing and presenting the differences between two AST subtrees, while this checker only needs a simple yes/no answer for "Are these branches identical?".

Macros:

The current implementation of the check only looks at the preprocessed code, therefore it detects the situations where the duplication is created by macros. I added some tests to highlight this behavior. I think that in some situations this would be useful for detecting redundant or incorrect parts of macro-infected code.

clang-tidy/bugprone/BranchCloneCheck.cpp

32

This type represents one branch in a switch statement (which consists of multiple statements). I cannot think of a descriptive, short name which also happens to be plural and I do not want to use a monstrosity like StatementsInSwitchBranch.

By the way, can anyone think of shorter, but still clear names for areStatementsIdentical() and areSwitchBranchesIdentical() ?

188

I have renamed FamilyBegin/FamilyEnd to BeginCurrent/EndCurrent. I kept begin and end in the names to emphasize that this is is an iterator range (and altered the comment to include the expression "iterator range"). Is this naming choice clear enough?

test/clang-tidy/bugprone-branch-clone.cpp

201

The tests for macro handling start here.

[donat.nagy]

Correct a typo (ELSE instead of else)

[Szelethus]

In D54757#1311468, @donat.nagy wrote:

Macros:

The current implementation of the check only looks at the preprocessed code, therefore it detects the situations where the duplication is created by macros. I added some tests to highlight this behavior.

The only option I see to detect macro related errors is to use a Lexer, and compare the tokens one by one, but that might be overkill, and I'm aware of a check in the works that already implements that. I think it's perfectly fine not to cover those cases, but you should definitely document it somewhere, preferably in the rst file.

I think that in some situations this would be useful for detecting redundant or incorrect parts of macro-infected code.

How about this?

#define PANDA_CUTE_FACTOR 9001
#define CAT_CUTE_FACTOR 9001

if (whatever())
  return PANDA_CUTE_FACTOR;
else
  return CAT_CUTE_FACTOR;

Your check would warn here, but it is possible, if not likely that the definition of those macros will eventually change. Again, it's fine not to cover this, but this is a false positive in a sense.

I have to agree with the folks before me, this patch is amazing, great job!

test/clang-tidy/bugprone-branch-clone.cpp

201

Maybe add dividers? :) The //===--------------===// thing, you know.

[JonasToth]

In D54757#1311516, @Szelethus wrote:

In D54757#1311468, @donat.nagy wrote:

Macros:

The current implementation of the check only looks at the preprocessed code, therefore it detects the situations where the duplication is created by macros. I added some tests to highlight this behavior.

The only option I see to detect macro related errors is to use a Lexer, and compare the tokens one by one, but that might be overkill, and I'm aware of a check in the works that already implements that. I think it's perfectly fine not to cover those cases, but you should definitely document it somewhere, preferably in the rst file.

Agreed with the documentation note.
Starting around with the Lexer here will not help, it is too fragile, as macros can change between different builds and so on.

I think that in some situations this would be useful for detecting redundant or incorrect parts of macro-infected code.

How about this?

#define PANDA_CUTE_FACTOR 9001
#define CAT_CUTE_FACTOR 9001

if (whatever())
  return PANDA_CUTE_FACTOR;
else
  return CAT_CUTE_FACTOR;

Your check would warn here, but it is possible, if not likely that the definition of those macros will eventually change. Again, it's fine not to cover this, but this is a false positive in a sense.

Yes, and it is potentially even build-configuration dependent. This is one of the big issues with macros that are impossible(?) to overcome. I would accept this case in the check. (Making it clear in the doc would not hurt).

docs/clang-tidy/checks/list.rst

13

yes. please remove it still, the python script is only run in add_new_check.py, i will commit the fix isolated to master.

test/clang-tidy/bugprone-branch-clone.cpp

5

Thank you. Could you please add a short note to the user-facing documentation that these are not handled.

[JonasToth]

clang-tidy/bugprone/BranchCloneCheck.cpp

32

The name is ok, I missunderstood the sense of the type.
Your other names are fine i think.

[donat.nagy]

test/clang-tidy/bugprone-branch-clone.cpp

5

In fact, I could easily extend the functionality of the checker to cover ternary operators. Would it be an useful addition?

[Eugene.Zelenko]

test/clang-tidy/bugprone-branch-clone.cpp

5

Sure, it'll be great extension of functionality.

[donat.nagy]

Handle ternary operators, improve documentation

[donat.nagy]

At the end of the documentation I stated that the check examines the code after macro expansion. Is this note clear enough?

test/clang-tidy/bugprone-branch-clone.cpp

5

I added support for ternary operators and documented this fact.

[JonasToth]

LGTM, could you please run this check over real world code and check that there are no obvious false positives?

docs/clang-tidy/checks/bugprone-branch-clone.rst

11

please do not indent the .. code-block:: c++ but just the code itself, (following too)

[Eugene.Zelenko]

Please close PR30233 after committing patch.

[donat.nagy]

Minor correction in documentation

[donat.nagy]

I applied this check to the llvm + clang codebase, and I was surprised to see that it produced about 600 results (for comparison, the clang-tidy checks which are enabled by default produce approximately 6000 results together). I didn't go through the whole list, but after examining a few dozen random reports it seems that most of these are true positives: relatively short branches (usually one or two lines of code) are repeated for no obvious reason. I would guess that most of these fall into the "correct but too verbose" case, because otherwise the tests would have caught the problem, but I didn't try to understand their context.

I have seen a few false positives related to preprocessor trickery: when an .inc file is included to create a huge switch, sometimes it will become a huge switch with lots of identical branches. There were also some situations where the check reported identical branches which are annotated with different comments; I don't know if this should be considered a false positive.

If this is acceptable, then I would be grateful if someone would commit this patch for me as I don't have commit rights.

[JonasToth]

In D54757#1316899, @donat.nagy wrote:

I applied this check to the llvm + clang codebase, and I was surprised to see that it produced about 600 results (for comparison, the clang-tidy checks which are enabled by default produce approximately 6000 results together). I didn't go through the whole list, but after examining a few dozen random reports it seems that most of these are true positives: relatively short branches (usually one or two lines of code) are repeated for no obvious reason. I would guess that most of these fall into the "correct but too verbose" case, because otherwise the tests would have caught the problem, but I didn't try to understand their context.

I have seen a few false positives related to preprocessor trickery: when an .inc file is included to create a huge switch, sometimes it will become a huge switch with lots of identical branches. There were also some situations where the check reported identical branches which are annotated with different comments; I don't know if this should be considered a false positive.

If this is acceptable, then I would be grateful if someone would commit this patch for me as I don't have commit rights.

Thank you!
Are the cases with .inc files easily silenceable with // NOLINT comments? In general code-generation through macros is not easily handled with clang-tidy, so all checks have the problem (e.g. GoogleTest is extremly chatty with everything), but would be interesting to know :)

All other cases sound like "a human should look and evaluate" and that's ok for clang-tidy as it doesn't claim finding ONLY bugs, but all kind of issues.

Thank you for the patch, if there are no objections by other reviewers I will commit tomorrow( ~24 hours from now)

[donat.nagy]

Macro-generated long switches: I cannot access the check results right now, but if I recall correctly, the check assigned these errors to certain lines in the .inc files. This means that (1) it is not very easy to to suppress them with //NOLINT comments, but (2) it should be relatively easy to filter them by location (ignore all reports coming from .inc files).

A quick, tangentially related idea: Would it be useful to implement multiline nolint sections (e.g. //BEGINNOLINT – //ENDNOLINT or something similar)? This would be helpful for using clang-tidy on projects that contain some automatically generated fragments.

[JonasToth]

A quick, tangentially related idea: Would it be useful to implement multiline nolint sections (e.g. //BEGINNOLINT – //ENDNOLINT or something similar)? This would be helpful for using clang-tidy on projects that contain some automatically generated fragments.

Yes, I think so. The filtering mechanism we have right now are not sufficient i think.
Features similar to pylint would be great, were you can disable certain checks for scopes (functions, modules, classes). With this kind of functionality we could bring clang-tidy to system-level libraries too, as the "unsafe" code is usually chatty in many regards, but with fine-grained and powerful filtering it should be easier to manage the output.

TL;DR I am in favor of such approaches, a short proposal (with what you plan) on the mailing-list wouldn't hurt for more opinions :)

[JonasToth]

I had to revert this patch because it broke (at least one) buildbot with an assertion-failure (http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/40436/steps/test/logs/stdio)

Could you please take a look at it? I could not reproduce locally though.

[Szelethus]

Reverted in rCTE348344.

[Szelethus]

I'll take a look at this.

In D54757#1319831, @JonasToth wrote:

I had to revert this patch because it broke (at least one) buildbot with an assertion-failure (http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/40436/steps/test/logs/stdio)

Could you please take a look at it? I could not reproduce locally though.

The logs are gone -- do you mind me commiting this again to retrieve the assertation?

[Szelethus]

I actually managed to reproduce the crash.

extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp:200: clang::DiagnosticBuilder clang::tidy::ClangTidyContext::diag(llvm::StringRef, clang::SourceLocation, llvm::StringRef, DiagnosticIDs::Level): Assertion `Loc.isValid()' failed.

[Szelethus]

$ cat orig.cpp
#define a(b) switch (b) {
#define c(b) \
b:
int d;
e() {
a(d) c(2);
c(3)

$ debugBuild/bin/clang-tidy orig.cpp -checks=bugprone-branch-clone --
clang-tidy: ../extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp:200: clang::DiagnosticBuilder clang::tidy::ClangTidyContext::diag(llvm::StringRef, clang::SourceLocation, llvm::StringRef, DiagnosticIDs::Level): Assertion `Loc.isValid()' failed.
#0 0x00007f263c30ee79 llvm::sys::PrintStackTrace(llvm::raw_ostream&) debugBuild/../llvm/lib/Support/Unix/Signals.inc:494:11 #1 0x00007f263c30f029 PrintStackTraceSignalHandler(void*) debugBuild/../llvm/lib/Support/Unix/Signals.inc:558:1
#2 0x00007f263c30d936 llvm::sys::RunSignalHandlers() debugBuild/../llvm/lib/Support/Signals.cpp:67:5 
#3 0x00007f263c30f6db SignalHandler(int) debugBuild/../llvm/lib/Support/Unix/Signals.inc:357:1 #4 0x00007f263bd64890 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
#5 0x00007f2637aefe97 gsignal /build/glibc-OTsEL5/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0 
#6 0x00007f2637af1801 abort /build/glibc-OTsEL5/glibc-2.27/stdlib/abort.c:81:0 
#7 0x00007f2637ae139a __assert_fail_base /build/glibc-OTsEL5/glibc-2.27/assert/assert.c:89:0 
#8 0x00007f2637ae1412 (/lib/x86_64-linux-gnu/libc.so.6+0x30412) 
#9 0x00007f263a64c623 clang::tidy::ClangTidyContext::diag(llvm::StringRef, clang::SourceLocation, llvm::StringRef, clang::DiagnosticIDs::Level) debugBuild/../extra/clang-tidy/Cl
angTidyDiagnosticConsumer.cpp:201:17 #10 0x00007f263a647baf clang::tidy::ClangTidyCheck::diag(clang::SourceLocation, llvm::StringRef, clang::DiagnosticIDs::Level) debugBuild/../extra/clang-tidy/ClangTidyCheck.cpp:23
:3 #11 0x00007f263a28671e clang::tidy::bugprone::BranchCloneCheck::check(clang::ast_matchers::MatchFinder::MatchResult const&) debugBuild/../extra/clang-tidy/bugprone/BranchCloneCheck.cpp:200:9 
#12 0x00007f263a647be9 clang::tidy::ClangTidyCheck::run(clang::ast_matchers::MatchFinder::MatchResult const&) debugBuild/../extra/clang-tidy/ClangTidyCheck.cpp:31:1 #13 0x00007f263ae60174 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::MatchVisitor::visitMatch(clang::ast_matchers::BoundNodes const&) debugBuild/../clang
/lib/ASTMatchers/ASTMatchFinder.cpp:742:7 
#14 0x00007f263af4e699 clang::ast_matchers::internal::BoundNodesTreeBuilder::visitMatches(clang::ast_matchers::internal::BoundNodesTreeBuilder::Visitor*) debugBuild/../clang/lib/
ASTMatchers/ASTMatchersInternal.cpp:75:5 #15 0x00007f263ae5fe66 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchWithFilter(clang::ast_type_traits::DynTypedNode const&) debugBuild/../clang/lib
/ASTMatchers/ASTMatchFinder.cpp:574:7 
#16 0x00007f263ae601c5 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::matchDispatch(clang::Stmt const*) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder
.cpp:597:5
#17 0x00007f263ae5fa7d void clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::Stmt>(clang::Stmt const&) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:499:3
#18 0x00007f263ae6dedd clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseStmt(clang::Stmt*, llvm::SmallVectorImpl<llvm::PointerIntPair<clang::Stmt*, 1u, bool, llvm::PointerLikeTypeTraits<clang::Stmt*>, llvm::PointerIntPairInfo<clang::Stmt*, 1u, llvm::PointerLikeTypeTraits<clang::Stmt*> > > >*) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:868:48
#19 0x00007f263ae904b5 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseCompoundStmt(clang::CompoundStmt*, llvm::SmallVectorImpl<llvm::PointerIntPair<clang::Stmt*, 1u, bool, llvm::PointerLikeTypeTraits<clang::Stmt*>, llvm::PointerIntPairInfo<clang::Stmt*, 1u, llvm::PointerLikeTypeTraits<clang::Stmt*> > > >*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:2175:1
#20 0x00007f263ae806a2 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::dataTraverseNode(clang::Stmt*, llvm::SmallVectorImpl<llvm::PointerIntPair<clang::Stmt*, 1u, bool, llvm::PointerLikeTypeTraits<clang::Stmt*>, llvm::PointerIntPairInfo<clang::Stmt*, 1u, llvm::PointerLikeTypeTraits<clang::Stmt*> > > >*) debugBuild/tools/clang/include/clang/AST/StmtNodes.inc:73:1
#21 0x00007f263ae7c95e clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseStmt(clang::Stmt*, llvm::SmallVectorImpl<llvm::PointerIntPair<clang::Stmt*, 1u, bool, llvm::PointerLikeTypeTraits<clang::Stmt*>, llvm::PointerIntPairInfo<clang::Stmt*, 1u, llvm::PointerLikeTypeTraits<clang::Stmt*> > > >*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:655:7
#22 0x00007f263ae6def9 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseStmt(clang::Stmt*, llvm::SmallVectorImpl<llvm::PointerIntPair<clang::Stmt*, 1u, bool, llvm::PointerLikeTypeTraits<clang::Stmt*>, llvm::PointerIntPairInfo<clang::Stmt*, 1u, llvm::PointerLikeTypeTraits<clang::Stmt*> > > >*) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:868:3
#23 0x00007f263aeb71ca clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseFunctionHelper(clang::FunctionDecl*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:2020:5
#24 0x00007f263ae677be clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseFunctionDecl(clang::FunctionDecl*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:2025:1
#25 0x00007f263ae61df3 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseDecl(clang::Decl*) debugBuild/tools/clang/include/clang/AST/DeclNodes.inc:389:1
#26 0x00007f263ae61281 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseDecl(clang::Decl*) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:860:3
#27 0x00007f263ae6dc58 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseDeclContextHelper(clang::DeclContext*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:1387:7
#28 0x00007f263ae6a3a8 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseTranslationUnitDecl(clang::TranslationUnitDecl*) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:1479:1
#29 0x00007f263ae623f6 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseDecl(clang::Decl*) debugBuild/tools/clang/include/clang/AST/DeclNodes.inc:571:1
#30 0x00007f263ae61281 clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::TraverseDecl(clang::Decl*) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:860:3
#31 0x00007f263adf7e73 clang::RecursiveASTVisitor<clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor>::TraverseAST(clang::ASTContext&) debugBuild/../clang/include/clang/AST/RecursiveASTVisitor.h:183:11
#32 0x00007f263adf7c8d clang::ast_matchers::MatchFinder::matchAST(clang::ASTContext&) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:1037:11
#33 0x00007f263ae60d05 clang::ast_matchers::internal::(anonymous namespace)::MatchASTConsumer::HandleTranslationUnit(clang::ASTContext&) debugBuild/../clang/lib/ASTMatchers/ASTMatchFinder.cpp:930:3
#34 0x00007f263608220b clang::MultiplexConsumer::HandleTranslationUnit(clang::ASTContext&) debugBuild/../clang/lib/Frontend/MultiplexConsumer.cpp:291:23
#35 0x00007f263253655e clang::ParseAST(clang::Sema&, bool, bool) debugBuild/../clang/lib/Parse/ParseAST.cpp:178:12
#36 0x00007f26360432c2 clang::ASTFrontendAction::ExecuteAction() debugBuild/../clang/lib/Frontend/FrontendAction.cpp:1037:1
#37 0x00007f2636042ce0 clang::FrontendAction::Execute() debugBuild/../clang/lib/Frontend/FrontendAction.cpp:938:7
#38 0x00007f2635fbf6ae clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) debugBuild/../clang/lib/Frontend/CompilerInstance.cpp:945:7
#39 0x00007f2638998382 clang::tooling::FrontendActionFactory::runInvocation(std::shared_ptr<clang::CompilerInvocation>, clang::FileManager*, std::shared_ptr<clang::PCHContainerOperations>, clang::DiagnosticConsumer*) debugBuild/../clang/lib/Tooling/Tooling.cpp:369:14
#40 0x00007f263a5f48d1 clang::tidy::runClangTidy(clang::tidy::ClangTidyContext&, clang::tooling::CompilationDatabase const&, llvm::ArrayRef<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, llvm::IntrusiveRefCntPtr<llvm::vfs::OverlayFileSystem>, bool, llvm::StringRef)::ActionFactory::runInvocation(std::shared_ptr<clang::CompilerInvocation>, clang::FileManager*, std::shared_ptr<clang::PCHContainerOperations>, clang::DiagnosticConsumer*) debugBuild/../extra/clang-tidy/ClangTidy.cpp:540:7
#41 0x00007f2638998218 clang::tooling::ToolInvocation::runInvocation(char const*, clang::driver::Compilation*, std::shared_ptr<clang::CompilerInvocation>, std::shared_ptr<clang::PCHContainerOperations>) debugBuild/../clang/lib/Tooling/Tooling.cpp:344:3
#42 0x00007f2638997385 clang::tooling::ToolInvocation::run() debugBuild/../clang/lib/Tooling/Tooling.cpp:329:3
#43 0x00007f2638999577 clang::tooling::ClangTool::run(clang::tooling::ToolAction*) debugBuild/../clang/lib/Tooling/Tooling.cpp:518:11
#44 0x00007f263a5f283a clang::tidy::runClangTidy(clang::tidy::ClangTidyContext&, clang::tooling::CompilationDatabase const&, llvm::ArrayRef<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, llvm::IntrusiveRefCntPtr<llvm::vfs::OverlayFileSystem>, bool, llvm::StringRef) debugBuild/../extra/clang-tidy/ClangTidy.cpp:562:23
#45 0x0000000000243db8 clang::tidy::clangTidyMain(int, char const**) debugBuild/../extra/clang-tidy/tool/ClangTidyMain.cpp:430:7
#46 0x0000000000243342 main debugBuild/../extra/clang-tidy/tool/ClangTidyMain.cpp:491:3
#47 0x00007f2637ad2b97 __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344:0
#48 0x000000000024302a _start (debugBuild/bin/clang-tidy+0x24302a)

[Szelethus]

FIx the above mentioned crash.

diff --git a/clang-tidy/bugprone/BranchCloneCheck.cpp b/clang-tidy/bugprone/BranchCloneCheck.cpp
index f371231..a898311 100644
--- a/clang-tidy/bugprone/BranchCloneCheck.cpp
+++ b/clang-tidy/bugprone/BranchCloneCheck.cpp
@@ -197,8 +197,19 @@ void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {
         diag(BeginCurrent->front()->getBeginLoc(),
              "switch has %0 consecutive identical branches")
             << static_cast<int>(std::distance(BeginCurrent, EndCurrent));
-        diag(Lexer::getLocForEndOfToken((EndCurrent - 1)->back()->getEndLoc(),
-                                        0, *Result.SourceManager,
+
+        SourceLocation EndLoc = (EndCurrent - 1)->back()->getEndLoc();
+        // If the case statement is generated from a macro, it's SourceLocation
+        // may be invalid, resuling in an assertation failure down the line.
+        // While not optimal, try the begin location in this case, it's still
+        // better then nothing.
+        if (EndLoc.isInvalid())
+          EndLoc = (EndCurrent - 1)->back()->getBeginLoc();
+
+        if (EndLoc.isMacroID())
+          EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);
+
+        diag(Lexer::getLocForEndOfToken(EndLoc, 0, *Result.SourceManager,
                                         getLangOpts()),
              "last of these clones ends here", DiagnosticIDs::Note);
       }

[Szelethus]

I changed the testfiles quite a bit, surprisingly, I'd appreciate another accept on this one please :) Seems to me that the changes describe the actual reports far better...

test/clang-tidy/bugprone-branch-clone.cpp

349

...except the removal of these -- I guess

+        if (EndLoc.isMacroID())
+          EndLoc = Context.getSourceManager().getExpansionLoc(EndLoc);

is responsible for this, but I'm not really sure how else can I avoid the assertation failure.

[JonasToth]

Did you run the new version over a big project like llvm again?
If yes LGTM from my side, if not please do that before committing to ensure no new/other problems creeped in.

clang-tidy/bugprone/BranchCloneCheck.h

+//===--- BranchCloneCheck.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_BUGPRONE_BRANCHCLONECHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_BRANCHCLONECHECK_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+/// A check for detecting if/else if/else chains where two or more branches are
+/// Type I clones of each other (that is, they contain identical code) and for
+/// detecting switch statements where two or more consecutive branches are
+/// Type I clones of each other.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/bugprone-branch-clone.html
+class BranchCloneCheck : public ClangTidyCheck {
+public:
+  BranchCloneCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_BRANCHCLONECHECK_H

clang-tidy/bugprone/BranchCloneCheck.cpp

+//===--- BranchCloneCheck.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 "BranchCloneCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/CloneDetection.h"
+#include "llvm/Support/Casting.h"
+
+using namespace clang;
+using namespace clang::ast_matchers;
+
+namespace {
+
+/// Returns true when the statements are Type I clones of each other.
+static bool areStatementsIdentical(const Stmt *LHS, const Stmt *RHS,
+                                   const ASTContext &Context) {
+  llvm::FoldingSetNodeID DataLHS, DataRHS;
+  LHS->Profile(DataLHS, Context, false);
+  RHS->Profile(DataRHS, Context, false);
+  return (DataLHS == DataRHS);
+}
+
+/// A branch in a switch may consist of several statements; while a branch in
+/// an if/else if/else chain is one statement (which may be a CompoundStmt).
+using SwitchBranch = llvm::SmallVector<const Stmt *, 2>;
+
+/// Determines if the bodies of two branches in a switch statements are Type I
+/// clones of each other. This function only examines the body of the branch
+/// and ignores the `case X:` or `default:` at the start of the branch.
+static bool areSwitchBranchesIdentical(const SwitchBranch LHS,
+                                       const SwitchBranch RHS,
+                                       const ASTContext &Context) {
+  if (LHS.size() != RHS.size())
+    return false;
+
+  for (unsigned i = 0; i < LHS.size(); i++) {
+    if (!areStatementsIdentical(LHS[i]->stripLabelLikeStatements(),
+                                RHS[i]->stripLabelLikeStatements(), Context)) {
+      // NOTE: We strip goto labels and annotations in addition to stripping
+      // the `case X:` or `default:` labels, but it is very unlikely that this
+      // would casue false positives in real-world code.
+      return false;
+    }
+  }
+
+  return true;
+}
+
+} // anonymous namespace
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+void BranchCloneCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(switchStmt().bind("switch"), this);
+  Finder->addMatcher(ifStmt(hasParent(stmt().bind("ifParent"))).bind("if"),
+                     this);
+}
+
+void BranchCloneCheck::check(const MatchFinder::MatchResult &Result) {
+  const ASTContext &Context = *Result.Context;
+
+  if (const auto *IS = Result.Nodes.getNodeAs<IfStmt>("if")) {
+    // Check whether this `if` is part of an `else if`:
+    if (const auto *IP =
+            dyn_cast<IfStmt>(Result.Nodes.getNodeAs<Stmt>("ifParent"))) {
+      if (IP->getElse() &&
+          IP->getElse()->getSourceRange() == IS->getSourceRange()) {
+        // This is an `else if`, which was already handled when we found the
+        // `if` statement which started the if/else if/else chain
+        return;
+      }
+    }
+
+    const Stmt *Then = IS->getThen();
+    assert(Then && "An IfStmt must have a `then` branch!");
+    const Stmt *Else = IS->getElse();
+    if (!Else) {
+      // If there is no `else` branch, we may exit early because there is no
+      // chance of duplicated branches.
+      return;
+    } else if (!isa<IfStmt>(Else)) {
+      // Just a simple if with no `else if` branch.
+      if (areStatementsIdentical(Then->IgnoreContainers(),
+                                 Else->IgnoreContainers(), Context)) {
+        diag(IS->getBeginLoc(), "if with identical then and else branches");
+        diag(IS->getElseLoc(), "else branch starts here", DiagnosticIDs::Note);
+      }
+      return;
+    }
+
+    // This is the complicated case when we start an if/else if/else chain.
+    // To find all the duplicates, we collect all the branches into a vector.
+    llvm::SmallVector<const Stmt *, 4> Branches;
+    const IfStmt *Cur = IS;
+    while (Cur) {
+      // Store the `then` branch.
+      Branches.push_back(Cur->getThen());
+
+      // The chain ends if there is no `else` branch.
+      Else = Cur->getElse();
+      if (!Else)
+        break;
+
+      // Check if there is another `else if`...
+      Cur = dyn_cast<IfStmt>(Else);
+      if (!Cur) {
+        // ...this is just a plain `else` branch; we store it.
+        Branches.push_back(Else);
+        // Note: We will exit the while loop here.
+      }
+    }
+
+    const int N = Branches.size();
+    llvm::BitVector KnownAsClone(N);
+
+    for (int i = 0; i < N - 1; i++) {
+      if (KnownAsClone[i]) {
+        // We have already seen Branches[i] as a clone of an earlier branch.
+        continue;
+      }
+      int NumCopies = 1;
+
+      for (int j = i + 1; j < N; j++) {
+        if (KnownAsClone[j] ||
+            !areStatementsIdentical(Branches[i]->IgnoreContainers(),
+                                    Branches[j]->IgnoreContainers(), Context)) {
+          continue;
+        }
+
+        NumCopies++;
+        KnownAsClone[j] = true;
+
+        if (NumCopies == 2) {
+          // We report the first occurence only when we find the second one.
+          diag(Branches[i]->getBeginLoc(),
+               "repeated branch in conditional chain");
+          diag(Lexer::getLocForEndOfToken(Branches[i]->getEndLoc(), 0,
+                                          *Result.SourceManager, getLangOpts()),
+               "end of the original", DiagnosticIDs::Note);
+        }
+
+        diag(Branches[j]->getBeginLoc(), "clone %0 starts here",
+             DiagnosticIDs::Note)
+            << (NumCopies - 1);
+      }
+    }
+  } else if (const auto *SS = Result.Nodes.getNodeAs<SwitchStmt>("switch")) {
+    const CompoundStmt *Body = dyn_cast_or_null<CompoundStmt>(SS->getBody());
+    if (!Body) {
+      // Code like
+      //   switch (x) case 0: case 1: foobar();
+      // is legal and calls foobar() if and only if x is either 0 or 1;
+      // but we do not try to distinguish branches in such code.
+      return;
+    }
+
+    // We will first collect the branhces of the switch statements. For the
+    // sake of simplicity we say that branches are delimited by the SwitchCase
+    // (`case:` or `default:`) children of Body; that is, we ignore `case:` or
+    // `default:` labels embedded inside other statements and we do not follow
+    // the effects of `break` and other control-flow statements.
+    llvm::SmallVector<SwitchBranch, 4> Branches;
+    for (const Stmt *S : Body->body()) {
+      if (isa<SwitchCase>(S)) {
+        // We start a new, empty branch.
+        Branches.emplace_back();
+      }
+      if (!Branches.empty()) {
+        // There may be code before the first branch (which can be dead code
+        // and can be code reached either through goto or through case labels
+        // that are embedded inside e.g. inner compound statements); we do not
+        // store those statements in branches.
+        Branches.back().push_back(S);
+      }
+    }
+
+    auto End = Branches.end();
+    auto FamilyBegin = Branches.begin();
+    while (FamilyBegin < End) {
+      auto FamilyEnd = FamilyBegin + 1;
+      while (FamilyEnd < End &&
+             areSwitchBranchesIdentical(*FamilyBegin, *FamilyEnd, Context)) {
+        ++FamilyEnd;
+      }
+      // At this point the half-open range [FamilyBegin, FamilyEnd) contains a
+      // complete family of consecutive identical branches.
+      if (FamilyEnd > FamilyBegin + 1) {
+        diag(FamilyBegin->front()->getBeginLoc(),
+             "switch has %0 consecutive identical branches")
+            << static_cast<int>(FamilyEnd - FamilyBegin);
+        diag(Lexer::getLocForEndOfToken((FamilyEnd - 1)->back()->getEndLoc(), 0,
+                                        *Result.SourceManager, getLangOpts()),
+             "last of these clones ends here", DiagnosticIDs::Note);
+      }
+      FamilyBegin = FamilyEnd;
+    }
+  } else {
+    llvm_unreachable("No if statement and no switch statement.");
+  }
+}
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang

clang-tidy/bugprone/BugproneTidyModule.cpp

 //===--- BugproneTidyModule.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 "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "../cppcoreguidelines/NarrowingConversionsCheck.h"
 #include "ArgumentCommentCheck.h"
 #include "AssertSideEffectCheck.h"
 #include "BoolPointerImplicitConversionCheck.h"
+#include "BranchCloneCheck.h"
 #include "CopyConstructorInitCheck.h"
 #include "DanglingHandleCheck.h"
 #include "ExceptionEscapeCheck.h"
 #include "FoldInitTypeCheck.h"
 #include "ForwardDeclarationNamespaceCheck.h"
 #include "ForwardingReferenceOverloadCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundingsCheck.h"

 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ArgumentCommentCheck>(
         "bugprone-argument-comment");
     CheckFactories.registerCheck<AssertSideEffectCheck>(
         "bugprone-assert-side-effect");
     CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
         "bugprone-bool-pointer-implicit-conversion");
+    CheckFactories.registerCheck<BranchCloneCheck>(
+        "bugprone-branch-clone");
     CheckFactories.registerCheck<CopyConstructorInitCheck>(
         "bugprone-copy-constructor-init");
     CheckFactories.registerCheck<DanglingHandleCheck>(
         "bugprone-dangling-handle");
     CheckFactories.registerCheck<ExceptionEscapeCheck>(
         "bugprone-exception-escape");
     CheckFactories.registerCheck<FoldInitTypeCheck>(
         "bugprone-fold-init-type");

clang-tidy/bugprone/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyBugproneModule
   ArgumentCommentCheck.cpp
   AssertSideEffectCheck.cpp
   BoolPointerImplicitConversionCheck.cpp
+  BranchCloneCheck.cpp
   BugproneTidyModule.cpp
   CopyConstructorInitCheck.cpp
   DanglingHandleCheck.cpp
   ExceptionEscapeCheck.cpp
   FoldInitTypeCheck.cpp
   ForwardDeclarationNamespaceCheck.cpp
   ForwardingReferenceOverloadCheck.cpp
   InaccurateEraseCheck.cpp

docs/ReleaseNotes.rst

 Improvements to clang-rename
 ----------------------------
 
 The improvements are...
 
 Improvements to clang-tidy
 --------------------------
 
+- New :doc:`bugprone-branch-clone
+  <clang-tidy/checks/bugprone-branch-clone>` check.
+
+  Checks for duplicated branches in ``if/else if/else`` chains and ``switch``
+  statements.
+
 - New :doc:`abseil-duration-division
   <clang-tidy/checks/abseil-duration-division>` check.
 
   Checks for uses of ``absl::Duration`` division that is done in a
   floating-point context, and recommends the use of a function that
   returns a floating-point value.
 
 - New :doc:`abseil-faster-strsplit-delimiter

docs/clang-tidy/checks/bugprone-branch-clone.rst

+.. title:: clang-tidy - bugprone-branch-clone
+
+bugprone-branch-clone
+=====================
+
+Finds ``if/else if/else`` chains where two or more branches are Type I clones
+of each other (that is, they contain identical code) and ``switch`` statements
+where two or more consecutive branches are Type I clones of each other.
+
+  .. code-block:: c++
+
+    if (test_value(x)) {
+      y++;
+      do_something(x, y);
+    } else {
+      y++;
+      do_something(x, y);
+    }
+
+In this simple example (which could arise e.g. as a copy-paste error) the
+``then`` and ``else`` branches are identical and the code is equivalent the
+following shorter and cleaner code:
+
+  .. code-block:: c++
+
+    test_value(x); // can be omitted unless it has side effects
+    y++;
+    do_something(x, y);
+
+
+If this is the inteded behavior, then there is no reason to use a conditional
+statement; otherwise the issue can be solved by fixing the branch that is
+handled incorrectly.
+
+The check also detects repeated branches in longer ``if/else if/else`` chains
+where it would be even harder to notice the problem.
+
+In ``switch`` statements the check only reports repeated branches when they are
+consecutive, because it is relatively common that the ``case:`` labels have
+some natural ordering and rearranging them would decrease the readability of
+the code. For example:
+
+  .. code-block:: c++
+
+    switch (ch) {
+    case 'a':
+      return 10;
+    case 'A':
+      return 10;
+    case 'b':
+      return 11;
+    case 'B':
+      return 11;
+    default:
+      return 10;
+    }
+
+Here the checker reports that the ``'a'`` and ``'A'`` branches are identical
+(and that the ``'b'`` and ``'B'`` branches are also identical), but does not
+report that the ``default:`` branch is also idenical to the first two branches.
+If this is indeed the correct behavior, then it could be implemented as:
+
+  .. code-block:: c++
+
+    switch (ch) {
+    case 'a':
+    case 'A':
+      return 10;
+    case 'b':
+    case 'B':
+      return 11;
+    default:
+      return 10;
+    }
+
+Here the checker does not warn for the repeated ``return 10;``, which is good
+if we want to preserve that ``'a'`` is before ``'b'`` and ``default:`` is the
+last branch.

docs/clang-tidy/checks/list.rst

 .. title:: clang-tidy - Clang-Tidy Checks
 
 Clang-Tidy Checks
 =================
 
 .. toctree::
    abseil-duration-division
    abseil-faster-strsplit-delimiter
    abseil-no-internal-dependencies
    abseil-no-namespace
    abseil-redundant-strcat-calls
-   abseil-string-find-startswith
    abseil-str-cat-append
+   abseil-string-find-startswith
    android-cloexec-accept
    android-cloexec-accept4
    android-cloexec-creat
    android-cloexec-dup
    android-cloexec-epoll-create
    android-cloexec-epoll-create1
    android-cloexec-fopen
    android-cloexec-inotify-init
    android-cloexec-inotify-init1
    android-cloexec-memfd-create
    android-cloexec-open
    android-cloexec-socket
    android-comparison-in-temp-failure-retry
    boost-use-to-string
    bugprone-argument-comment
    bugprone-assert-side-effect
    bugprone-bool-pointer-implicit-conversion
+   bugprone-branch-clone
    bugprone-copy-constructor-init
    bugprone-dangling-handle
    bugprone-exception-escape
    bugprone-fold-init-type
    bugprone-forward-declaration-namespace
    bugprone-forwarding-reference-overload
    bugprone-inaccurate-erase
    bugprone-incorrect-roundings

test/clang-tidy/bugprone-branch-clone.cpp

+// RUN: %check_clang_tidy %s bugprone-branch-clone %t
+
+void test_basic1(int in, int &out) {
+  if (in > 77)
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    out++;
+  else
+// CHECK-MESSAGES: :[[@LINE-1]]:3: note: else branch starts here
+    out++;
+
+  out++;
+}
+
+void test_basic2(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    out++;
+  }
+  else {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: note: else branch starts here
+    out++;
+  }
+
+  out++;
+}
+
+void test_basic3(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    out++;
+  }
+  else
+// CHECK-MESSAGES: :[[@LINE-1]]:3: note: else branch starts here
+    out++;
+
+  out++;
+}
+
+void test_basic4(int in, int &out) {
+  if (in > 77) {
+    out--;
+  }
+  else {
+    out++;
+  }
+}
+
+void test_basic5(int in, int &out) {
+  if (in > 77) {
+    out++;
+  }
+  else {
+    out++;
+    out++;
+  }
+}
+
+void test_basic6(int in, int &out) {
+  if (in > 77) {
+    out++;
+  }
+  else {
+    out++, out++;
+  }
+}
+
+void test_basic7(int in, int &out) {
+  if (in > 77) {
+    out++;
+    out++;
+  }
+  else
+    out++;
+
+  out++;
+}
+
+void test_basic8(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    out++;
+    out++;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+    out++;
+    out++;
+  }
+
+  if (in % 2)
+    out++;
+}
+
+void test_basic9(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    if (in % 2)
+      out++;
+    else
+      out--;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+    if (in % 2)
+      out++;
+    else
+      out--;
+  }
+}
+
+// If we remove the braces from the previous example, the check recognizes it
+// as an `else if`.
+void test_basic10(int in, int &out) {
+  if (in > 77)
+    if (in % 2)
+      out++;
+    else
+      out--;
+  else
+    if (in % 2)
+      out++;
+    else
+      out--;
+
+}
+
+void test_basic11(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    if (in % 2)
+      out++;
+    else
+      out--;
+    if (in % 3)
+      out++;
+    else
+      out--;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+    if (in % 2)
+      out++;
+    else
+      out--;
+    if (in % 3)
+      out++;
+    else
+      out--;
+  }
+}
+
+void test_basic12(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+  }
+}
+
+void test_basic13(int in, int &out) {
+  if (in > 77) {
+    // Empty compound statement is not identical to null statement.
+  } else;
+}
+
+
+void test_chain1(int in, int &out) {
+  if (in > 77)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: end of the original
+  else if (in > 55)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 1 starts here
+    out++;
+
+  out++;
+}
+
+void test_chain2(int in, int &out) {
+  if (in > 77)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: end of the original
+  else if (in > 55)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 1 starts here
+    out++;
+  else if (in > 42)
+    out--;
+  else if (in > 28)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 2 starts here
+    out++;
+  else if (in > 12) {
+    out++;
+    out *= 7;
+  } else if (in > 7) {
+// CHECK-MESSAGES: :[[@LINE-1]]:22: note: clone 3 starts here
+    out++;
+  }
+}
+
+void test_chain3(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:16: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+    out++;
+// CHECK-MESSAGES: :[[@LINE+1]]:4: note: end of the original
+  } else if (in > 55) {
+// CHECK-MESSAGES: :[[@LINE-1]]:23: note: clone 1 starts here
+    out++;
+    out++;
+  } else if (in > 42)
+    out--;
+  else if (in > 28) {
+// CHECK-MESSAGES: :[[@LINE-1]]:21: note: clone 2 starts here
+    out++;
+    out++;
+  } else if (in > 12) {
+    out++;
+    out++;
+    out++;
+    out *= 7;
+  } else if (in > 7) {
+// CHECK-MESSAGES: :[[@LINE-1]]:22: note: clone 3 starts here
+    out++;
+    out++;
+  }
+}
+
+// In this chain there are two clone families; notice that the checker
+// describes all branches of the first one before mentioning the second one.
+void test_chain4(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:16: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+    out++;
+// CHECK-MESSAGES: :[[@LINE+1]]:4: note: end of the original
+  } else if (in > 55) {
+// CHECK-MESSAGES: :[[@LINE-1]]:23: note: clone 1 starts here
+// CHECK-MESSAGES: :[[@LINE+8]]:21: note: clone 2 starts here
+// CHECK-MESSAGES: :[[@LINE+15]]:22: note: clone 3 starts here
+    out++;
+    out++;
+  } else if (in > 42)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out--;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: end of the original
+  else if (in > 28) {
+    out++;
+    out++;
+  } else if (in > 12) {
+    out++;
+    out++;
+    out++;
+    out *= 7;
+  } else if (in > 7) {
+    out++;
+    out++;
+  } else if (in > -3) {
+// CHECK-MESSAGES: :[[@LINE-1]]:23: note: clone 1 starts here
+    out--;
+  }
+}
+
+void test_chain5(int in, int &out) {
+  if (in > 77)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: end of the original
+  else if (in > 55)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 1 starts here
+    out++;
+  else if (in > 42)
+    out--;
+  else if (in > 28)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 2 starts here
+    out++;
+  else if (in > 12) {
+    out++;
+    out *= 7;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: clone 3 starts here
+    out++;
+  }
+}
+
+void test_chain6(int in, int &out) {
+  if (in > 77) {
+// CHECK-MESSAGES: :[[@LINE-1]]:16: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+    out++;
+// CHECK-MESSAGES: :[[@LINE+1]]:4: note: end of the original
+  } else if (in > 55) {
+// CHECK-MESSAGES: :[[@LINE-1]]:23: note: clone 1 starts here
+    out++;
+    out++;
+  } else if (in > 42)
+    out--;
+  else if (in > 28) {
+// CHECK-MESSAGES: :[[@LINE-1]]:21: note: clone 2 starts here
+    out++;
+    out++;
+  } else if (in > 12) {
+    out++;
+    out++;
+    out++;
+    out *= 7;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: clone 3 starts here
+    out++;
+    out++;
+  }
+}
+
+void test_nested(int a, int b, int c, int &out) {
+  if (a > 5) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+27]]:5: note: else branch starts here
+    if (b > 5) {
+// CHECK-MESSAGES: :[[@LINE-1]]:16: warning: repeated branch in conditional chain [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+9]]:6: note: end of the original
+// CHECK-MESSAGES: :[[@LINE+8]]:24: note: clone 1 starts here
+// CHECK-MESSAGES: :[[@LINE+14]]:12: note: clone 2 starts here
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    } else if (b > 15) {
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    } else {
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    }
+  } else {
+    if (b > 5) {
+// CHECK-MESSAGES: :[[@LINE-1]]:16: warning: repeated branch in conditional chain [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+9]]:6: note: end of the original
+// CHECK-MESSAGES: :[[@LINE+8]]:24: note: clone 1 starts here
+// CHECK-MESSAGES: :[[@LINE+14]]:12: note: clone 2 starts here
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    } else if (b > 15) {
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    } else {
+      if (c > 5)
+// CHECK-MESSAGES: :[[@LINE-1]]:7: warning: if with identical then and else branches [bugprone-branch-clone]
+        out++;
+      else
+// CHECK-MESSAGES: :[[@LINE-1]]:7: note: else branch starts here
+        out++;
+    }
+  }
+}
+
+template <class T>
+void test_template_not_instantiated(const T &t) {
+  int a;
+  if (t)
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    a++;
+  else
+// CHECK-MESSAGES: :[[@LINE-1]]:3: note: else branch starts here
+    a++;
+}
+
+template <class T>
+void test_template_instantiated(const T &t) {
+  int a;
+  if (t)
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    a++;
+  else
+// CHECK-MESSAGES: :[[@LINE-1]]:3: note: else branch starts here
+    a++;
+}
+
+template void test_template_instantiated<int>(const int &t);
+
+template <class T>
+void test_template2(T t, int a) {
+  if (a) {
+    T b(0);
+    a += b;
+  } else {
+    int b(0);
+    a += b;
+  }
+}
+
+template void test_template2<int>(int t, int a);
+
+template <class T>
+void test_template3(T t, int a) {
+  if (a) {
+    T b(0);
+    a += b;
+  } else {
+    int b(0);
+    a += b;
+  }
+}
+
+template void test_template3<short>(short t, int a);
+
+template <class T>
+void test_template_two_instances(T t, int &a) {
+  if (a) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    a += int(t);
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+    a += int(t);
+  }
+}
+
+template void test_template_two_instances<short>(short t, int &a);
+template void test_template_two_instances<long>(long t, int &a);
+
+class C {
+  int member;
+  void inline_method(int arg) {
+    if (arg)
+// CHECK-MESSAGES: :[[@LINE-1]]:5: warning: if with identical then and else branches [bugprone-branch-clone]
+      member = 3;
+    else
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+      member = 3;
+  }
+  int other_method();
+};
+
+int C::other_method() {
+  if (member) {
+// CHECK-MESSAGES: :[[@LINE-1]]:3: warning: if with identical then and else branches [bugprone-branch-clone]
+    return 8;
+  } else {
+// CHECK-MESSAGES: :[[@LINE-1]]:5: note: else branch starts here
+    return 8;
+  }
+}
+
+int simple_switch(char ch) {
+  switch (ch) {
+// CHECK-MESSAGES: :[[@LINE+1]]:3: warning: switch has 2 consecutive identical branches [bugprone-branch-clone]
+  case 'a':
+    return 10;
+  case 'A':
+    return 10;
+// CHECK-MESSAGES: :[[@LINE-1]]:14: note: last of these clones ends here
+// CHECK-MESSAGES: :[[@LINE+1]]:3: warning: switch has 2 consecutive identical branches [bugprone-branch-clone]
+  case 'b':
+    return 11;
+  case 'B':
+    return 11;
+// CHECK-MESSAGES: :[[@LINE-1]]:14: note: last of these clones ends here
+// CHECK-MESSAGES: :[[@LINE+1]]:3: warning: switch has 2 consecutive identical branches [bugprone-branch-clone]
+  case 'c':
+    return 10;
+  case 'C':
+    return 10;
+// CHECK-MESSAGES: :[[@LINE-1]]:14: note: last of these clones ends here
+  default:
+    return 0;
+  }
+}
+
+int long_sequence_switch(char ch) {
+  switch (ch) {
+// CHECK-MESSAGES: :[[@LINE+1]]:3: warning: switch has 7 consecutive identical branches [bugprone-branch-clone]
+  case 'a':
+    return 10;
+  case 'A':
+    return 10;
+  case 'b':
+    return 10;
+  case 'B':
+    return 10;
+  case 'c':
+    return 10;
+  case 'C':
+    return 10;
+  default:
+    return 10;
+// CHECK-MESSAGES: :[[@LINE-1]]:14: note: last of these clones ends here
+  }
+}
+
+int nested_switch(int a, int b, int c) {
+  switch (a) {
+// CHECK-MESSAGES: :[[@LINE+2]]:3: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+114]]:6: note: last of these clones ends here
+  case 1:
+    switch (b) {
+// CHECK-MESSAGES: :[[@LINE+2]]:5: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+33]]:8: note: last of these clones ends here
+    case 1:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    case 2:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    default:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    }
+  case 2:
+    switch (b) {
+// CHECK-MESSAGES: :[[@LINE+2]]:5: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+33]]:8: note: last of these clones ends here
+    case 1:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    case 2:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    default:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    }
+  default:
+    switch (b) {
+// CHECK-MESSAGES: :[[@LINE+2]]:5: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+// CHECK-MESSAGES: :[[@LINE+33]]:8: note: last of these clones ends here
+    case 1:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    case 2:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    default:
+      switch (c) {
+// CHECK-MESSAGES: :[[@LINE+1]]:7: warning: switch has 3 consecutive identical branches [bugprone-branch-clone]
+      case 1:
+        return 42;
+      case 2:
+        return 42;
+      default:
+        return 42;
+// CHECK-MESSAGES: :[[@LINE-1]]:18: note: last of these clones ends here
+      }
+    }
+  }
+}
+
+
+// This should not produce warnings, as in switch statements we only report
+// identical branches when they are consecutive. Also note that a branch
+// terminated by a break is different from a branch terminated by the end of
+// the switch statement.
+int interleaved_cases(int a, int b) {
+  switch (a) {
+  case 3:
+  case 4:
+    b = 2;
+    break;
+  case 5:
+    b = 3;
+    break;
+  case 6:
+    b = 2;
+    break;
+  case 7:
+    if (b % 2) {
+      b++;
+    } else {
+      b++;
+      break;
+    }
+    b = 2;
+    break;
+  case 8:
+    b = 2;
+  case 9:
+    b = 3;
+    break;
+  default:
+    b = 3;
+  }
+  return b;
+}
+
+
+// A case: or default: is only considered to be the start of a branch if it is a direct child of the CompoundStmt forming the body of the switch
+int buried_cases(int foo) {
+  switch (foo) {
+    {
+    case 36:
+      return 8;
+    default:
+      return 8;
+    }
+  }
+}
+
+// Here the `case 7:` is a child statement of the GotoLabelStmt, so the checker
+// thinks that it is part of the `case 9:` branch. While this result is
+// counterintuitve, mixing goto labels and switch statements in this fashion is
+// pretty rare, so it does not deserve a special case in the checker code.
+int decorated_cases(int z) {
+  if (!(z % 777)) {
+    goto lucky;
+  }
+  switch (z) {
+// CHECK-MESSAGES: :[[@LINE+1]]:3: warning: switch has 2 consecutive identical branches [bugprone-branch-clone]
+  case 1:
+  case 2:
+  case 3:
+    z++;
+    break;
+  case 4:
+  case 5:
+    z++;
+    break;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: last of these clones ends here
+  case 9:
+    z++;
+    break;
+  lucky:
+  case 7:
+    z += 3;
+    z *= 2;
+    break;
+  case 92:
+    z += 3;
+    z *= 2;
+    break;
+  default:
+    z++;
+  }
+  return z + 92;
+}
+
+// The child of the switch statement is not neccessarily a compound statement,
+// do not crash in this unusual case.
+char no_real_body(int in, int &out) {
+  switch (in)
+  case 42:
+    return 'A';
+
+  if (in > 77)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: warning: repeated branch in conditional chain [bugprone-branch-clone]
+    out++;
+// CHECK-MESSAGES: :[[@LINE-1]]:10: note: end of the original
+  else if (in > 55)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 1 starts here
+    out++;
+  else if (in > 34)
+// CHECK-MESSAGES: :[[@LINE+1]]:5: note: clone 2 starts here
+    out++;
+
+  return '|';
+}
+
+// Duff's device [https://en.wikipedia.org/wiki/Duff's_device]
+// The check does not try to distinguish branches in this sort of convoluted
+// code, but it should avoid crashing.
+void send(short *to, short *from, int count)
+{
+    int n = (count + 7) / 8;
+    switch (count % 8) {
+    case 0: do { *to = *from++;
+    case 7:      *to = *from++;
+    case 6:      *to = *from++;
+    case 5:      *to = *from++;
+    case 4:      *to = *from++;
+    case 3:      *to = *from++;
+    case 2:      *to = *from++;
+    case 1:      *to = *from++;
+            } while (--n > 0);
+    }
+}