[clang-tidy] Add misc-invalidated-iterators check.

[mnbvmar]

Summary

This is the alpha version of a check looking for possible uses of invalidated references or iterators.

As for now, only references to std::vector are checked. (This is quite easy to fix, though).
As for now, it considers only references to the elements. Considering pointers or iterators is harder and probably requires some deeper analysis (as in misc-use-after-move check).

[Eugene.Zelenko]

Please mention this check in docs/ReleaseNotes.rst (see previous releases as example).

test/clang-tidy/misc-invalidated-iterators.cpp

63

Unnecessary empty line.

75

Unnecessary empty line.

126

Please fix this.

[Eugene.Zelenko]

General question: isn't Static Analyzer is better place for such workflow checks?

[Prazek]

clang-tidy/misc/InvalidatedIteratorsCheck.cpp

61

Please tests for all of this functions

92

.insert({MemoTuple, false})

99

I guess this might be to optimistic assumption. Normally we should be pesimistic to not introduce false positives. I will run thi check on llvm code base with SmallVector instead of std::vector and will see.

175–179

const auto BlockMap = std::make_unique<StmtToBlockMap>(TheCFG.get(), Result.Context)

etc.

182–184

remove extra braces

docs/clang-tidy/checks/misc-invalidated-iterators.rst

18

suggest changing it to
ref = 42;

When first reading I thought that it is iterator

test/clang-tidy/misc-invalidated-iterators.cpp

11–17

iterator in vector is just raw pointer, so I guess you can replace it with

using iterator = Type*;

29

Few testcases:

• passing vector as pointer
• passing vector as copy, it shouldn't care what happens

to modyfied vector.

• modyfing vector inside loop - does it finds it? like: for (auto &ref : vec) { vec.push_back(42); ref = 42; }

125

add new line to file end

[Prazek]

In D29151#656887, @Eugene.Zelenko wrote:

General question: isn't Static Analyzer is better place for such workflow checks?

Probably yes, but it is much harder to implement this there. Other problem is that it would be probably a part
of one of the alpha checks, that are not developed and I don't know if they will ever be fully supported.

clang-tidy/misc/InvalidatedIteratorsCheck.h

35

drop clang-tidy. It's cleaner

37

).

[Eugene.Zelenko]

In D29151#657435, @Prazek wrote:

In D29151#656887, @Eugene.Zelenko wrote:

General question: isn't Static Analyzer is better place for such workflow checks?

Probably yes, but it is much harder to implement this there. Other problem is that it would be probably a part
of one of the alpha checks, that are not developed and I don't know if they will ever be fully supported.

But it'll be necessary to re-implement part of Static Analyzer functionality in Clang-tidy. Will it be generic enough to be used for similar purposes?

It'll be good idea to find out Static Analyzer release criteria.

[zaks.anna]

The static analyzer is definitely the place to go for bug detection that requires path sensitivity. It's also reasonably good for anything that needs flow-sensitivity. Although, most flow-sensitive analysis (such as liveness) now live in lib/Analysis/, which is used by both Sema and the Clang Static Analyzer. Both path-sensitive and flow-sensitive analysis are based on clang's CFG. I do not know of clang-tidy uses CFG or lib/Analysis/.

Here are the wikipedia definitions of sensitivity I am referring to:
//- A flow-sensitive analysis takes into account the order of statements in a program. For example, a flow-insensitive pointer alias analysis may determine "variables x and y may refer to the same location", while a flow-sensitive analysis may determine "after statement 20, variables x and y may refer to the same location".

• A path-sensitive analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance, if a branch contains a condition x>0, then on the fall-through path, the analysis would assume that x<=0 and on the target of the branch it would assume that indeed x>0 holds. //

There is work underway in the analyzer for adding IteratorPastEnd checker. The first commit was rather large and has been reviewed here https://reviews.llvm.org/D25660. That checker is very close to be moved out of alpha. Moving it out of alpha is pending evaluation on real codebases to ensure that the false positive rates are low and enhancements to error reporting.

Other problem is that it would be probably a part
of one of the alpha checks, that are not developed and I don't know if they will ever be fully supported.

There seems to be a misconception about what the alpha checkers are. All checkers start in alpha package to allow in-tree incremental development. Once the checkers are complete, they should move out of alpha. The criteria is that the code should pass the review, the checker needs to have low false positive rates, finally, the error reports should be of good quality (some checks greatly benefit from extra path hints that can be implemented with a visitor). These are motivated by providing a good user experience to end users. (We do have several checkers that are "stuck in alpha". A lot of them are abandoned experiments that just need to be deleted; others could probably be made production quality with some extra effort.)

[Prazek]

In D29151#658484, @zaks.anna wrote:

The static analyzer is definitely the place to go for bug detection that requires path sensitivity. It's also reasonably good for anything that needs flow-sensitivity. Although, most flow-sensitive analysis (such as liveness) now live in lib/Analysis/, which is used by both Sema and the Clang Static Analyzer. Both path-sensitive and flow-sensitive analysis are based on clang's CFG. I do not know of clang-tidy uses CFG or lib/Analysis/.

Here are the wikipedia definitions of sensitivity I am referring to:
//- A flow-sensitive analysis takes into account the order of statements in a program. For example, a flow-insensitive pointer alias analysis may determine "variables x and y may refer to the same location", while a flow-sensitive analysis may determine "after statement 20, variables x and y may refer to the same location".

• A path-sensitive analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance, if a branch contains a condition x>0, then on the fall-through path, the analysis would assume that x<=0 and on the target of the branch it would assume that indeed x>0 holds. //

There is work underway in the analyzer for adding IteratorPastEnd checker. The first commit was rather large and has been reviewed here https://reviews.llvm.org/D25660. That checker is very close to be moved out of alpha. Moving it out of alpha is pending evaluation on real codebases to ensure that the false positive rates are low and enhancements to error reporting.

Other problem is that it would be probably a part
of one of the alpha checks, that are not developed and I don't know if they will ever be fully supported.

There seems to be a misconception about what the alpha checkers are. All checkers start in alpha package to allow in-tree incremental development. Once the checkers are complete, they should move out of alpha. The criteria is that the code should pass the review, the checker needs to have low false positive rates, finally, the error reports should be of good quality (some checks greatly benefit from extra path hints that can be implemented with a visitor). These are motivated by providing a good user experience to end users. (We do have several checkers that are "stuck in alpha". A lot of them are abandoned experiments that just need to be deleted; others could probably be made production quality with some extra effort.)

I think we need some sort of clear guidelines on where what functionality should be added. Even right now there are clang-tidy checks that finds subset of alpha checks, but probably having lower false positive rate. The other example is Use after move, that is doing similar thing as uninitialized values analysis in clang.

[Eugene.Zelenko]

I think we need some sort of clear guidelines on where what functionality should be added. Even right now there are clang-tidy checks that finds subset of alpha checks, but probably having lower false positive rate. The other example is Use after move, that is doing similar thing as uninitialized values analysis in clang.

I agree with this and could add that we also need similar guidelines for Clang diagnostics too. Some of Clang-tidy and Static Analyzer checks are more suited for Clang diagnostics (unused constructs, deadcode.DeadStores, etc). It will be reasonable if we have discussions to decide better place for particular check instead of just swallowing patches.

[zaks.anna]

Before clang-tidy came into existence the guidelines were very clear. One should write a clang warning if the diagnostic:

• can be implemented without path-insensitive analysis (including flow-sensitive)
• is checking for language rules (not specific API misuse)

In my view, this should still be the rule going forward because compiler warnings are most effective in reaching users.

The Clang Static Analyzer used to be the place for all other diagnostics. Most of the checkers it contains rely on path-sensitive analysis. Note that one might catch the same bug with flow-sensitive as well as path-sensitive analysis. So in some of those cases, we have both warnings as well as analyzer checkers finding the same type of user error. However, the checkers can catch more bugs since they are path-sensitive. The analyzer also has several flow-sensitive/ AST matching checkers. Those checks could not have been written as warnings mainly because they check for APIs, which are not part of the language.

My understanding is that clang-tidy supports fixits, which the clang static analyzer currently does not support. However, there could be other benefits to placing not path-sensitive checks there as well. I am not sure. I've also heard opinions that it's more of a linter tool, so the user expectations could be different.

Even right now there are clang-tidy checks that finds subset of alpha checks, but probably having lower false positive rate.

Again, alpha checks are unfinished work, so we should not use them as examples of checkers that have false positives. Some of them are research projects and should probably be deleted.

[alexfh]

In D29151#662504, @zaks.anna wrote:

Before clang-tidy came into existence the guidelines were very clear. One should write a clang warning if the diagnostic:

• can be implemented without path-insensitive analysis (including flow-sensitive)
• is checking for language rules (not specific API misuse)

In my view, this should still be the rule going forward because compiler warnings are most effective in reaching users.

The Clang Static Analyzer used to be the place for all other diagnostics. Most of the checkers it contains rely on path-sensitive analysis. Note that one might catch the same bug with flow-sensitive as well as path-sensitive analysis. So in some of those cases, we have both warnings as well as analyzer checkers finding the same type of user error. However, the checkers can catch more bugs since they are path-sensitive. The analyzer also has several flow-sensitive/ AST matching checkers. Those checks could not have been written as warnings mainly because they check for APIs, which are not part of the language.

My understanding is that clang-tidy supports fixits, which the clang static analyzer currently does not support. However, there could be other benefits to placing not path-sensitive checks there as well. I am not sure. I've also heard opinions that it's more of a linter tool, so the user expectations could be different.

Even right now there are clang-tidy checks that finds subset of alpha checks, but probably having lower false positive rate.

Again, alpha checks are unfinished work, so we should not use them as examples of checkers that have false positives. Some of them are research projects and should probably be deleted.

I tried to come up with some advice on where checks should go in http://clang.llvm.org/extra/clang-tidy/#choosing-the-right-place-for-your-check:

Clang diagnostic: if the check is generic enough, targets code patterns that most probably are bugs (rather than style or readability issues), can be implemented effectively and with extremely low false positive rate, it may make a good Clang diagnostic.

Clang static analyzer check: if the check requires some sort of control flow analysis, it should probably be implemented as a static analyzer check.

clang-tidy check is a good choice for linter-style checks, checks that are related to a certain coding style, checks that address code readability, etc.

There's no doubt path-sensitive checks should go to Static Analyzer, since it provides all the infrastructure for path-sensitive analyses. Whatever meets the criteria for a Clang diagnostic should be a diagnostic. Whatever needs automated fixes (and can be implemented on AST or preprocessor level) should go to clang-tidy.

But there's still a large set of analyses that don't clearly fall into one of the categories above and can be implemented both in Clang Static Analyzer and in clang-tidy. Currently there are no firm rules about those, only recommendations on the clang-tidy page (quoted above). We might need to agree upon some reasonable guidelines, though.

For example, IMO, AST-based analyses make more sense in clang-tidy for a few reasons:

1. They usually are easier expressible in terms of AST matchers, and clang-tidy allows to use AST matchers with less boilerplate.
2. Clang Static Analyzer is linked into clang, where AST matchers are undesired, since they tend to blow the size of binary significantly.
3. It's more consistent to keep all similar analyses together, it simplifies search for already implemented similar functionality and code reviews.

Flow-sensitive analyses (that don't need any path-sensitivity) seem to be equally suitable for SA and clang-tidy (unless I'm missing something), so I don't feel strongly as to where they should go.

WDYT?

[Prazek]

In D29151#665948, @alexfh wrote:

In D29151#662504, @zaks.anna wrote:

Before clang-tidy came into existence the guidelines were very clear. One should write a clang warning if the diagnostic:

• can be implemented without path-insensitive analysis (including flow-sensitive)
• is checking for language rules (not specific API misuse)

In my view, this should still be the rule going forward because compiler warnings are most effective in reaching users.

The Clang Static Analyzer used to be the place for all other diagnostics. Most of the checkers it contains rely on path-sensitive analysis. Note that one might catch the same bug with flow-sensitive as well as path-sensitive analysis. So in some of those cases, we have both warnings as well as analyzer checkers finding the same type of user error. However, the checkers can catch more bugs since they are path-sensitive. The analyzer also has several flow-sensitive/ AST matching checkers. Those checks could not have been written as warnings mainly because they check for APIs, which are not part of the language.

My understanding is that clang-tidy supports fixits, which the clang static analyzer currently does not support. However, there could be other benefits to placing not path-sensitive checks there as well. I am not sure. I've also heard opinions that it's more of a linter tool, so the user expectations could be different.

Even right now there are clang-tidy checks that finds subset of alpha checks, but probably having lower false positive rate.

Again, alpha checks are unfinished work, so we should not use them as examples of checkers that have false positives. Some of them are research projects and should probably be deleted.

I tried to come up with some advice on where checks should go in http://clang.llvm.org/extra/clang-tidy/#choosing-the-right-place-for-your-check:

Clang diagnostic: if the check is generic enough, targets code patterns that most probably are bugs (rather than style or readability issues), can be implemented effectively and with extremely low false positive rate, it may make a good Clang diagnostic.

Clang static analyzer check: if the check requires some sort of control flow analysis, it should probably be implemented as a static analyzer check.

clang-tidy check is a good choice for linter-style checks, checks that are related to a certain coding style, checks that address code readability, etc.

There's no doubt path-sensitive checks should go to Static Analyzer, since it provides all the infrastructure for path-sensitive analyses. Whatever meets the criteria for a Clang diagnostic should be a diagnostic. Whatever needs automated fixes (and can be implemented on AST or preprocessor level) should go to clang-tidy.

But there's still a large set of analyses that don't clearly fall into one of the categories above and can be implemented both in Clang Static Analyzer and in clang-tidy. Currently there are no firm rules about those, only recommendations on the clang-tidy page (quoted above). We might need to agree upon some reasonable guidelines, though.

For example, IMO, AST-based analyses make more sense in clang-tidy for a few reasons:

1. They usually are easier expressible in terms of AST matchers, and clang-tidy allows to use AST matchers with less boilerplate.
2. Clang Static Analyzer is linked into clang, where AST matchers are undesired, since they tend to blow the size of binary significantly.
3. It's more consistent to keep all similar analyses together, it simplifies search for already implemented similar functionality and code reviews.

Flow-sensitive analyses (that don't need any path-sensitivity) seem to be equally suitable for SA and clang-tidy (unless I'm missing something), so I don't feel strongly as to where they should go.

WDYT?

This sounds resonable. I think there are also other factors like:

• heuristics: clang-tidy tends to look for bugs based on some heuristics. E.g use-after-move consider methods as reinitializing based on method names (like clear).

This is approach works great if the heuristic is good enough to not have many false positives, but generally it will have some false positives and false negatives.

• flexibility: The other problem is that check can be flexible, for example to work on every vector-like container. I think static analyzer tends to be more conservative about bugs it wants to find. E.g we know how std::vector works, so the check will find only bugs associated with it trying to not introduce false positives

I will try to think about other factors, but firstly let me give a couple of examples. Please tell me where would you put these checks and exactly why:

use-after-move:

• does complex walk on CFG similar to path analysis
• has heuristics what is reinitialization

this check:

• uses the same utilities as use-after-move
• will works for different types of containers like std::unordered_map or llvm::DenseMap, which indicates heuristics

check null after dereference, looks for code like:

int *p = foo();
*p = 42;
if (p) {;;;}
//of 
if (!p) {;;;}

Some checks from static analyzer will find the body of if (!p) as dead code, and could probably find if (p) as expression always true.
I am not sure how it would handle cases like

int *p = foo();
*p = 42;
if (b) {
  p = otherFoo();
}

if (!p) {;;;}

Should static analyzer flag use like this?
If we want to have low false positive rate, then probably not.
On the other hand I would love if clang-tidy would flag this, because it seems like a buggy code (if (!p) {;;;} could be hoisted to the other if)

Another example, fiding out of range:

int glob[10];

int sum = 0;
for (int i = 0; i <= 10; i++) {
  sum += glob[i];
}

So this sounds like it a good diagnostic for clang, and even gcc finds it, but only with -O2.
Of course it won't flag cases like:

for (int i = 0; i <= 10; i++) {
  if (glob[i] == v)
    return true;
}

Because the loop might end before going to element pass array. I am not sure how well we can model
this with static analyzer, and if it is even possible to write check that would warn about cases like this, that are bugs (we can optimize it to single return true).

[zaks.anna]

I tried to come up with some advice on where checks should go in http://clang.llvm.org/extra/clang-tidy/#choosing-the-right-place-for-your-check

The guidelines stated on the clang-tidy page seem reasonable to me.

For example, IMO, AST-based analyses make more sense in clang-tidy for a few reasons:

They usually are easier expressible in terms of AST matchers, and clang-tidy allows to use AST matchers with less boilerplate.
Clang Static Analyzer is linked into clang, where AST matchers are undesired, since they tend to blow the size of binary significantly.
It's more consistent to keep all similar analyses together, it simplifies search for already implemented similar functionality and code reviews.

I agree that there is a gray area specifically in the AST-matching-based bug finding, which unfortunately leads to duplication of effort. However, we currently cannot ban/move all AST-based checks out of the analyzer. The main problem I see with restricting the AST-based analysis to clang-tidy is impact on the end users. While clang-tidy does export the clang static analyzer results, the reverse does not hold. There are many end users who do not use clang-tidy but do use the clang static analyzer (either directly or through scan-build). Until that is the case, I do not think we should disallow AST based checks from the analyzer, especially if they come from contributors who are interested in contributing to this tool. Note that the format in which the results are presented from these tools is not uniform, which makes transition more complicated.

The AST matchers can be used from the analyzer and if the code size becomes a problem, we could consider moving the analyzer out of the clang codebase.

Generally, I am not a big fan of the split between the checks based on the technology used to implement them since it does not lead to a great user interface - the end users do not think in terms of path-sensitive/flow-sensitive/AST-matching, they just want to enable specific functionality such as find bugs or ensure they follow coding guidelines. This is why I like the existing guidelines with their focus on what clang-tidy is from user perspective:

clang-tidy check is a good choice for linter-style checks, checks that are related to a certain coding style, checks that address code readability, etc.

Another thing that could be worth adding here is that clang-tidy finds bugs that tend to be easy to fix and, in most cases, provide the fixits. (I believe, this is one of the major strengths of the clang-tidy tool!)

Flow-sensitive analyses (that don't need any path-sensitivity) seem to be equally suitable for SA and clang-tidy (unless I'm missing something), so I don't feel strongly as to where they should go.

As far as I know, currently, all flow-sensitive analysis are in the Analysis library in clang. These are analysis for compiler warnings and analysis used by the static analyzer. I believe this is where future analysis should go as well, especially, for analysis that could have multiple clients. If clang code size impact turns out to be a serious problem, we could also have that library provide APIs that could be used from other tools/checks. (Note, the analysis could be implemented in the library, but the users of the analysis (checks) can be elsewhere.)

Regarding the points about "heuristics" and "flexibility", the analyzer is full of heuristics and fuzzy API matching. These techniques are very common in static analysis in general as we are trying to solve undecidable problems and heuristics is the only way to go.

[Prazek]

In D29151#668197, @zaks.anna wrote:

I tried to come up with some advice on where checks should go in http://clang.llvm.org/extra/clang-tidy/#choosing-the-right-place-for-your-check

The guidelines stated on the clang-tidy page seem reasonable to me.

For example, IMO, AST-based analyses make more sense in clang-tidy for a few reasons:

They usually are easier expressible in terms of AST matchers, and clang-tidy allows to use AST matchers with less boilerplate.
Clang Static Analyzer is linked into clang, where AST matchers are undesired, since they tend to blow the size of binary significantly.
It's more consistent to keep all similar analyses together, it simplifies search for already implemented similar functionality and code reviews.

I agree that there is a gray area specifically in the AST-matching-based bug finding, which unfortunately leads to duplication of effort. However, we currently cannot ban/move all AST-based checks out of the analyzer. The main problem I see with restricting the AST-based analysis to clang-tidy is impact on the end users. While clang-tidy does export the clang static analyzer results, the reverse does not hold. There are many end users who do not use clang-tidy but do use the clang static analyzer (either directly or through scan-build). Until that is the case, I do not think we should disallow AST based checks from the analyzer, especially if they come from contributors who are interested in contributing to this tool. Note that the format in which the results are presented from these tools is not uniform, which makes transition more complicated.

The AST matchers can be used from the analyzer and if the code size becomes a problem, we could consider moving the analyzer out of the clang codebase.

Generally, I am not a big fan of the split between the checks based on the technology used to implement them since it does not lead to a great user interface - the end users do not think in terms of path-sensitive/flow-sensitive/AST-matching, they just want to enable specific functionality such as find bugs or ensure they follow coding guidelines. This is why I like the existing guidelines with their focus on what clang-tidy is from user perspective:

Agree with it.

clang-tidy check is a good choice for linter-style checks, checks that are related to a certain coding style, checks that address code readability, etc.

Another thing that could be worth adding here is that clang-tidy finds bugs that tend to be easy to fix and, in most cases, provide the fixits. (I believe, this is one of the major strengths of the clang-tidy tool!)

Flow-sensitive analyses (that don't need any path-sensitivity) seem to be equally suitable for SA and clang-tidy (unless I'm missing something), so I don't feel strongly as to where they should go.

As far as I know, currently, all flow-sensitive analysis are in the Analysis library in clang. These are analysis for compiler warnings and analysis used by the static analyzer. I believe this is where future analysis should go as well, especially, for analysis that could have multiple clients. If clang code size impact turns out to be a serious problem, we could also have that library provide APIs that could be used from other tools/checks. (Note, the analysis could be implemented in the library, but the users of the analysis (checks) can be elsewhere.)

Regarding the points about "heuristics" and "flexibility", the analyzer is full of heuristics and fuzzy API matching. These techniques are very common in static analysis in general as we are trying to solve undecidable problems and heuristics is the only way to go.

I guess the main problem is that you can't use clang-tidy checks from scan build, where there are some checks like use-after-move, and bunch of misc checks, that would totally fit into what user want from scan build.

clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssertSideEffectCheck.cpp
+  InvalidatedIteratorsCheck.cpp
   MisplacedConstCheck.cpp
   UnconventionalAssignOperatorCheck.cpp
   BoolPointerImplicitConversionCheck.cpp
   DanglingHandleCheck.cpp
   DefinitionsInHeadersCheck.cpp
   FoldInitTypeCheck.cpp
   ForwardDeclarationNamespaceCheck.cpp
   InaccurateEraseCheck.cpp

clang-tidy/misc/InvalidatedIteratorsCheck.h

+//===--- InvalidatedIteratorsCheck.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_MISC_INVALIDATED_ITERATORS_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INVALIDATED_ITERATORS_H
+
+#include "../ClangTidy.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// This check warns about the possible use of the invalidated container
+/// iterators, pointers and/or references.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-invalidated-iterators.html
+class InvalidatedIteratorsCheck : public ClangTidyCheck {
+public:
+  InvalidatedIteratorsCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  using ExprMatcherType = ast_matchers::internal::BindableMatcher<Stmt>;
+
+  // Returns the clang-tidy matcher binding to the possibly invalidating uses
+  // of the container (either invoking a dangerous member call or calling
+  // another function with a non-const reference.)
+  ExprMatcherType getModifyingMatcher(const VarDecl *VectorDecl);
+
+  // Checks if given Func can invalidate the container at its given argument
+  // (ArgId). For convienience, number of Func's arguemnts is also passed.
+  bool canFuncInvalidate(const FunctionDecl *Func, unsigned ArgId,
+                         unsigned NumCallArgs, ASTContext *Context);
+
+  // Checks if given Call can invalidate the container provided by Match.
+  bool canCallInvalidate(const CallExpr *Call, ast_matchers::BoundNodes Match,
+                         ASTContext *Context);
+
+  // A cache which remembers the results of canFuncInvalidate calls. It
+  // is necessary in order to prevent canFuncInvalidate from looping or
+  // having exponential time behavior.
+  std::map<std::tuple<const FunctionDecl *, unsigned, unsigned>, bool>
+      CanFuncInvalidateMemo;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INVALIDATED_ITERATORS_H

clang-tidy/misc/InvalidatedIteratorsCheck.cpp

+//===--- InvalidatedIteratorsCheck.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 "InvalidatedIteratorsCheck.h"
+#include "../utils/ExprSequence.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/CFG.h"
+#include <iostream>
+
+using namespace clang::ast_matchers;
+using namespace clang::tidy::utils;
+using namespace clang::ast_type_traits;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+namespace {
+const char BlockFuncName[] = "BlockFunc";
+const char DeclStmtName[] = "DeclarationStmt";
+const char DeclName[] = "Declaration";
+const char ExprName[] = "Expr";
+const char VectorName[] = "TheVector";
+
+const char CallExprName[] = "CallExpr";
+const char CallName[] = "InvalidatingCall";
+const char CalledDeclName[] = "FuncDecl";
+const char CallArgName[] = "CallArg";
+}
+
+void InvalidatedIteratorsCheck::registerMatchers(MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  Finder->addMatcher(
+      declRefExpr(
+          hasDeclaration(
+              varDecl(allOf(hasAncestor(functionDecl().bind(BlockFuncName)),
+                            hasParent(declStmt().bind(DeclStmtName)),
+                            hasType(referenceType()),
+                            hasDescendant(declRefExpr(
+                                hasType(cxxRecordDecl(hasName("std::vector"))),
+                                hasDeclaration(varDecl().bind(VectorName))))))
+                  .bind(DeclName)))
+          .bind(ExprName),
+      this);
+}
+
+InvalidatedIteratorsCheck::ExprMatcherType
+InvalidatedIteratorsCheck::getModifyingMatcher(const VarDecl *VectorDecl) {
+  // An invalidation might occur by directly calling a risky method.
+  auto InvalidateMatcher =
+      cxxMemberCallExpr(has(memberExpr(hasDeclaration(cxxMethodDecl(hasAnyName(
+                                           "push_back", "emplace_back", "clear",
+                                           "insert", "emplace"))),
+                                       has(declRefExpr(hasDeclaration(
+                                           varDecl(equalsNode(VectorDecl))))))))
+          .bind(CallName);
+  // It may also occur by calling a method through a non-const reference.
+  auto FuncCallMatcher =
+      callExpr(hasDeclaration(functionDecl().bind(CalledDeclName)),
+               hasAnyArgument(
+                   declRefExpr(hasDeclaration(varDecl(equalsNode(VectorDecl))))
+                       .bind(CallArgName)))
+          .bind(CallExprName);
+  auto ModifyingMatcher = expr(eachOf(InvalidateMatcher, FuncCallMatcher));
+
+  return ModifyingMatcher;
+}
+
+bool InvalidatedIteratorsCheck::canFuncInvalidate(const FunctionDecl *Func,
+                                                  unsigned ArgId,
+                                                  unsigned NumCallArgs,
+                                                  ASTContext *Context) {
+  // Try to find the result of some previous canFuncInvalidate call
+  // which matches our arguments.
+  const auto MemoTuple = std::make_tuple(Func, ArgId, NumCallArgs);
+  const auto MemoChkIter = CanFuncInvalidateMemo.find(MemoTuple);
+  if (MemoChkIter != CanFuncInvalidateMemo.end())
+    return MemoChkIter->second;
+
+  // Temporarily insert a negative answer so that recursive functions
+  // won't loop our method.
+  const auto InsertResult =
+      CanFuncInvalidateMemo.insert(std::make_pair(MemoTuple, false));
+  assert(InsertResult.second);
+  const auto MemoIter = InsertResult.first;
+
+  if (!Func->hasBody()) {
+    // We cannot assume anything about the function, not knowing its
+    // body; it possibly invalidates our iterators.
+    return (MemoIter->second = true);
+  }
+
+  if (Func->getNumParams() != NumCallArgs) {
+    // Sometimes number of call arguments is not equal to the number
+    // of declaration arguments. As far as we know, it happens only when
+    // calling some class operators. In this case, there is also an
+    // additional *this argument as the first argument of the call.
+    // We should get rid of it so as to match the declaration arguments.
+    assert(Func->getNumParams() == NumCallArgs - 1 &&
+           "Number of function parameters should be equal to number of call "
+           "arguments or call arguments minus one");
+
+    if (ArgId == 0) {
+      // We don't care about member calls. These should be covered in other
+      // matchers.
+      return false;
+    }
+    ArgId--;
+  }
+
+  const auto *Arg = Func->parameters()[ArgId];
+
+  // Get all possible invalidations of the container Arg.
+  auto ModifyingMatcher = functionDecl(hasDescendant(getModifyingMatcher(Arg)));
+
+  const auto Matches = match(ModifyingMatcher, *Func, *Context);
+  for (const auto &Match : Matches) {
+    // A dangerous method possibly invalidates iterators.
+    const bool IsInvalidatingCall =
+        Match.getNodeAs<CXXMemberCallExpr>(CallName) != nullptr;
+    if (IsInvalidatingCall)
+      return (MemoIter->second = true);
+
+    // A recursive call might invalidate.
+    const auto *CallUse = Match.getNodeAs<CallExpr>(CallExprName);
+    assert(CallUse);
+
+    if (canCallInvalidate(CallUse, Match, Context))
+      return (MemoIter->second = true);
+  }
+  return false;
+}
+
+bool InvalidatedIteratorsCheck::canCallInvalidate(
+    const CallExpr *Call, ast_matchers::BoundNodes Match, ASTContext *Context) {
+  const auto *FuncArg = Match.getNodeAs<Expr>(CallArgName);
+  const auto *FuncDecl = Match.getNodeAs<FunctionDecl>(CalledDeclName);
+
+  // Go through all call arguments and check if any of them matches to
+  // our argument and can invalidate iterators pointing to it.
+  for (unsigned i = 0; i < Call->getNumArgs(); ++i) {
+    const auto *Arg = Call->getArg(i);
+
+    if (Arg == FuncArg &&
+        canFuncInvalidate(FuncDecl, i, Call->getNumArgs(), Context))
+      return true;
+  }
+
+  return false;
+}
+
+void InvalidatedIteratorsCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *RefUse = Result.Nodes.getNodeAs<DeclRefExpr>(ExprName);
+  const auto *RefDecl = Result.Nodes.getNodeAs<VarDecl>(DeclName);
+  const auto *RefDeclStmt = Result.Nodes.getNodeAs<DeclStmt>(DeclStmtName);
+  const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>(BlockFuncName);
+  const auto *VectorDecl = Result.Nodes.getNodeAs<VarDecl>(VectorName);
+  Stmt *FuncBody = Func->getBody();
+
+  CFG::BuildOptions Options;
+
+  auto *Context = Result.Context;
+
+  // Construct a CFG and ExprSequence so that it is possible to find possible
+  // sequences of operations.
+  const std::unique_ptr<CFG> TheCFG =
+      CFG::buildCFG(nullptr, FuncBody, Result.Context, Options);
+  const std::unique_ptr<StmtToBlockMap> BlockMap(
+      new StmtToBlockMap(TheCFG.get(), Result.Context));
+  const std::unique_ptr<ExprSequence> Sequence(
+      new ExprSequence(TheCFG.get(), Result.Context));
+  const CFGBlock *Block = BlockMap->blockContainingStmt(RefUse);
+  if (!Block) {
+    return;
+  }
+
+  auto ModifyingMatcher = getModifyingMatcher(VectorDecl);
+
+  for (const auto &BlockElem : *Block) {
+    // In each block, find all possible invalidating operations and process
+    // all of them.
+    const auto StmtPtr = BlockElem.getAs<CFGStmt>();
+    if (!StmtPtr.hasValue())
+      continue;
+    auto Results = match(ModifyingMatcher, *(StmtPtr->getStmt()), *Context);
+
+    for (const auto &Match : Results) {
+      const auto *InvalidatingUse =
+          Match.getNodeAs<CXXMemberCallExpr>(CallName);
+      const auto *CallUse = Match.getNodeAs<CallExpr>(CallExprName);
+
+      // If the candidate invalidating operation is calling the function,
+      // it should be able to invalidate.
+      if (CallUse && !canCallInvalidate(CallUse, Match, Context))
+        continue;
+
+      const Expr *Use =
+          (InvalidatingUse != nullptr ? cast<Expr>(InvalidatingUse)
+                                      : cast<Expr>(CallUse));
+
+      // The incorrect order of operations is:
+      //   1. Declare a reference.
+      //   2. Make a possibly invalidating use of the container.
+      //   3. Use the reference.
+      if (Sequence->potentiallyAfter(Use, RefDeclStmt) &&
+          Sequence->potentiallyAfter(RefUse, Use)) {
+        diag(RefUse->getLocation(), "%0 might be invalidated before the access")
+            << RefDecl;
+        // TODO: add a whole possible chain of invalidations.
+        diag(Use->getExprLoc(), "possible place of invalidation",
+             DiagnosticIDs::Note);
+        return;
+      }
+    }
+  }
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

clang-tidy/misc/MiscTidyModule.cpp

 //===--- MiscTidyModule.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 "ArgumentCommentCheck.h"
 #include "AssertSideEffectCheck.h"
+#include "InvalidatedIteratorsCheck.h"
+#include "MisplacedConstCheck.h"
+#include "UnconventionalAssignOperatorCheck.h"
 #include "BoolPointerImplicitConversionCheck.h"
 #include "DanglingHandleCheck.h"
 #include "DefinitionsInHeadersCheck.h"
 #include "FoldInitTypeCheck.h"
 #include "ForwardDeclarationNamespaceCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundings.h"
 #include "InefficientAlgorithmCheck.h"

 namespace misc {
 
 class MiscModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment");
     CheckFactories.registerCheck<AssertSideEffectCheck>(
         "misc-assert-side-effect");
-    CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
+    CheckFactories.registerCheck<InvalidatedIteratorsCheck>(
+        "misc-invalidated-iterators");
+    CheckFactories.registerCheck<MisplacedConstCheck>(
+        "misc-misplaced-const");
     CheckFactories.registerCheck<UnconventionalAssignOperatorCheck>(
         "misc-unconventional-assign-operator");
     CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
         "misc-bool-pointer-implicit-conversion");
     CheckFactories.registerCheck<DanglingHandleCheck>("misc-dangling-handle");
     CheckFactories.registerCheck<DefinitionsInHeadersCheck>(
         "misc-definitions-in-headers");
     CheckFactories.registerCheck<FoldInitTypeCheck>("misc-fold-init-type");

docs/clang-tidy/checks/list.rst

.. toctree::
    misc-bool-pointer-implicit-conversion
    misc-dangling-handle
    misc-definitions-in-headers
    misc-fold-init-type
    misc-forward-declaration-namespace
    misc-inaccurate-erase
    misc-incorrect-roundings
    misc-inefficient-algorithm
+   misc-invalidated-iterators
    misc-macro-parentheses
    misc-macro-repeated-side-effects
    misc-misplaced-const
    misc-misplaced-widening-cast
    misc-move-const-arg
    misc-move-constructor-init
    misc-move-forwarding-reference
    misc-multiple-statement-macro

docs/clang-tidy/checks/misc-invalidated-iterators.rst

+.. title:: clang-tidy - misc-invalidated-iterators
+
+misc-invalidated-iterators
+==========================
+
+This check finds the possible invalidations of the iterators/references/pointers
+through the container reallocation. If a programmer takes an iterator
+to the element of the container and then twiddles with the container, it is
+possible that the reference does not point to the original variable anymore.
+
+Example:
+
+.. code-block:: c++
+
+  std::vector<int> vec{42};
+  int &ref = vec[0];
+  vec.push_back(2017);
+  ref++;  // Incorrect - 'ref' might have been invalidated at 'push_back'.
+

test/clang-tidy/misc-invalidated-iterators.cpp

+// RUN: %check_clang_tidy %s misc-invalidated-iterators %t
+
+// Sample std::vector implementation.
+namespace std {
+
+template <typename Type>
+class vector {
+  Type tmp;
+
+public:
+  class iterator {
+    Type *data;
+
+  public:
+    iterator(Type *ptr) : data(ptr) {}
+    Type &operator*() { return *data; }
+  };
+
+  vector() {}
+
+  void push_back(Type &&elem) {}
+  void pop_back() {}
+
+  Type &operator[](int position) { return tmp; }
+
+  iterator begin() { return iterator(&tmp); }
+};
+}
+
+// Correct std::vector use.
+void correct_sample() {
+  std::vector<int> VecGood;
+  VecGood.push_back(3);
+
+  int &ElemRef = VecGood[0];
+  ElemRef++;
+  ElemRef *= ElemRef;
+  auto ElemIter = VecGood.begin();
+  (*ElemIter)++;
+  int *ElemPtr = &VecGood[0];
+  (*ElemPtr)++;
+}
+
+// Incorrect std::vector use.
+void incorrect_sample() {
+  std::vector<int> VecBad;
+  VecBad.push_back(3);
+
+  int &ElemRef = VecBad[0];
+  auto ElemIter = VecBad.begin();
+  int *ElemPtr = &VecBad[0];
+
+  VecBad.push_back(42);
+  ElemRef = 42;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'ElemRef' might be invalidated before the access
+  // CHECK-MESSAGES: :[[@LINE-3]]:10: note: possible place of invalidation
+  (*ElemIter)++;
+  // FIXME: Add a warning here.
+  (*ElemPtr)++;
+  // FIXME: Add a warning here.
+}
+
+
+void modifyVector(std::vector<int> &Vec) {
+  Vec.push_back(555);
+}
+
+void callModifyVector(std::vector<int> &Vec) {
+  modifyVector(Vec);
+}
+
+void checkVector(const std::vector<int> &){}
+void anotherCheckVector(std::vector<int>) {}
+
+
+void test_calling() {
+  std::vector<int> VecBad, VecGood;
+  VecBad.push_back(5);
+  VecGood.push_back(18);
+  VecGood.push_back(1818);
+  int &BadRef = VecBad[0];
+  int &GoodRef = VecGood[0];
+
+  modifyVector(VecBad);
+  checkVector(VecGood);
+  anotherCheckVector(VecGood);
+  VecGood.pop_back();
+
+  BadRef++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadRef' might be invalidated before the access
+  // CHECK-MESSAGES: :[[@LINE-7]]:3: note: possible place of invalidation
+  GoodRef++;
+}
+
+void test_recursive_calling() {
+  std::vector<int> RecVecBad, LambdaVecBad;
+  RecVecBad.push_back(99);
+  LambdaVecBad.push_back(0);
+  int &BadRef = RecVecBad[0];
+  int &BadLambdaRef = LambdaVecBad[0];
+
+  auto lambda = [](std::vector<int> &Vec) {
+    callModifyVector(Vec);
+  };
+
+  callModifyVector(RecVecBad);
+  BadRef++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadRef' might be invalidated before the access
+  // CHECK-MESSAGES: :[[@LINE-3]]:3: note: possible place of invalidation
+
+  lambda(LambdaVecBad);
+  BadLambdaRef++;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadLambdaRef' might be invalidated before the access
+  // CHECK-MESSAGES: :[[@LINE-3]]:3: note: possible place of invalidation
+}
+
+void test_argument(std::vector<int> &a, std::vector<int> &b) {
+  int &ElemRef = a[0];
+  int &ElemRefGood = b[0];
+  a.push_back(42);
+  ElemRefGood += 42;
+  ElemRef += 42;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'ElemRef' might be invalidated before the access
+  // CHECK-MESSAGES: :[[@LINE-4]]:5: note: possible place of invalidation
+}
 No newline at end of file