[Analyzer] Checker for iterators dereferenced beyond their range.

[baloghadamsoftware]

Summary

This checker checks for iterators dereferenced when they are equal to the end() of their container. Return value of any end() method is tracked if its type has the same properties as a typical iterator (can be incremented, dereferenced, and its name ends with "iterator", "iter" or "it"). STL functions that search a value or range are evaluated by the checker as an optimization.

[NoQ]

Wow, you managed to check something that could be checked without going through a hell of modeling dozens of STL methods, and probably even without stepping on poor C++ temporary object modeling in the analyzer, which sounds great.

These comments are incomplete because i didn't yet take my time to understand how your program state traits work; hope to come back to this a bit later.

Adding Alexey because he's fond of iterators.

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

116

Maybe llvm::PointerUnion?

176

I think functions should always begin with a stack frame context, not sure, does this ever get violated? Do we have checkBeginBlock? Sorry if i'm wrong.

184

LLVM cast<> should be used, because it asserts cast correctness through LLVM's custom RTTI (and LocationContext child classes do support that).

196

I think this trick needs more comments/explaining. It is very unusual. Are you trying to model effects of passing an iterator by value into a function? What part of these effects are not modeled magically by the core?

359

So the thing about evalCall is that every call can only be eval'ed by only one checker. So if you're doing this, you should be sure that your checker is modelling all effects of the call on everything in the program state, manually, and any checker that relies on that modelling should make sure that your checker is turned on.

Because the functions you are modelling are pure, i think it's, in general, a good idea to evalCall() them. Other checkers should be able to rely on PreCall/PostCall events to model their state changes.

So the question is, in what checker do we want this modelling to happen. Because your checker is looking for very specific errors, it might be a good idea to eventually split it into a separate checker. I think, at least, a FIXME for this task should be left around. I'm also currently tackling with a single checker to model all standard library functions (D20811), maybe i'd come up with a way to merge it there.

444

Accessing end() is a UB, we should probably generate a fatal error node here.

447

I think path-sensitive checkers should present their findings proudly. After all, they did their best to find a single execution path on which the problem certainly manifests.

522

Number of arguments of CE should be checked beforehand. Yes, it is UB to modify namespace std:: to introduce functions with same names but less arguments, but we still should not crash when we see such code.

569

It's not analyzer's fault :) We're inspecting the AST here.

Anyway, does CXXRecordDecl::needsImplicitCopyAssignment() look useful?

test/Analysis/iterator-past-end.cpp

4

We should probably separate this into an #include-able header in test/Analysis/Inputs/.

Also, there's always a bit of concern that it wasn't copy-pasted from a standard library implementation with an incompatible license such as (L)GPL. Which often happens when you do your best to emulate the normal way of defining things as closely as possible.

[baloghadamsoftware]

Updated according to the comments. Also fixed a bug and moved access check to pre-call instead of post-call.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

196

If I pass an iterator by value (the most usual case) I have to assign its position (in or out of range) to the formal parameter from the actual one.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

569

No, it does not. I need to check whether the type is copiable, since that is a criteria for being an operator (copiable via constructor and assignment, deleteable, incrementable and dereferencable). It seems that while copy constructor and destructor is generated automatically, copy assignment not, at least not in this simple case. So I defaulted it to true, and I set it to false if I find a deleted or a non-public copy assignment.

test/Analysis/iterator-past-end.cpp

4

I did it now, but first one of my tests failed. I fixed the bug, but it turned out that if I include these types and functions, no method or function is checked, just conjured symbols are generated. Should including not behave the same as copying the contents? This happened even if I removed the pragma.

[NoQ]

Thanks!! Will try to look at the rest of the stuff as soon as possible><

test/Analysis/iterator-past-end.cpp

4

Aha, i guess that's because we don't inline STL headers. See mayInlineCXXStandardLibrary() / -analyzer-config c++-stdlib-inlining.

The lesson to learn here is that it's a good idea to make tests as similar to real code as possible. Because on real code, it would probably also not be inlined.

[baloghadamsoftware]

test/Analysis/iterator-past-end.cpp

4

Actually, I always test first on real code, and it seemed to be inlined. But now, even if I removed the pragma it was not inlined.

[a.sidorin]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

157

This can be written some shorter: if (const auto *InstCall = dyn_cast<CXXInstance>(&Call)

210

As I remember, PostCall is also called for ObjC calls like ObjCMethodCall which may not have FunctionDecl as their callee. So, Func may be a nullptr and needs a check.

220

isa<StackFrameContext>(LCtx)?
And cast<> below already does the same check with an assertion.

259

Just C.getLocationContext()?

306

This loop may be C++11-fied.

323

What will happen if we compare two iterators related to different containers? I guess the result will be undefined but I'm not sure if we can track it in this checker without referencing the owning container. Let's leave this code as-is but I think this choice deserves a comment.

338

Maybe we should just swap Rhs and Lhs if LPos is null? So, we can avoid code duplication.

424

What will happen if we write something like this:

bool Eq1 = it1 == it2;
bool Eq2 = it3 == it4;
if (Eq1) {...}?

As I understand, we'll assume the second condition instead of first.

455

I'm not sure it's totally correct. -- for begin() will give us out-of-range iterator. According to header description, we're catching just "past-end" iterators, but this is confusing a bit for me.
Moreover, if we're out of end() in multiple positions, a single -- will not make the iterator valid again. You use a good conservative approach, but could you please add a comment describing it?

572

Just C.getLocationContext().

574

You can use overload which does not require the tag.

575

getLocationContext => LCtx

606

A common way of defining iterator types is just their declaration as pointers. I'm not sure this code will work well in such cases.
You can see some example in LLVM containers like SmallVector, where iterators are declared in the following way:

typedef T *iterator;
typedef const T *const_iterator;

619

HasCopyCtor, HasCopyAssign, etc.

621

We usually prefer informative names like "Method" or "Ctor".

624

There was a comment. Phabricator disallows me to delete my own comments so I was forced to edit it. Nevermind.

[a.sidorin]

Thank you for this patch! I like some solutions used in it but I also have some comments (inline).

[zaks.anna]

Actually, I always test first on real code, and it seemed to be inlined. But now, even if I
removed the pragma it was not inlined.

Looks like this patch is interfering with this inlining suppression. We had many false positives without it. Mainly, the analyzer would not understand the invariants of the container data structures.

ExprEngine::defaultEvalCall calls mayInlineCallKind which contains this:
`// Conditionally control the inlining of methods on objects that look

// like C++ containers.
if (!Opts.mayInlineCXXContainerMethods())
  if (!Ctx.getSourceManager().isInMainFile(FD->getLocation()))
    if (isContainerMethod(Ctx, FD))
      return false;`

test/Analysis/iterator-past-end.cpp

4

We often do forward declare in the implementation file as it is done here. We mainly use the Inputs directory to simulate system headers.

[NoQ]

I think i managed to understand the reasoning behind your solutions! Right now i definitely approve all the high-level logic apart from the handling of left/right SVals for evalAssume, which i think could be easily improved upon without significant drawbacks. See the inline comment.

As for inlining STL headers - ouch. It was supposed to be working (i.e. never inlining), it'd probably be great to know why it gets inlined. STL headers are confusing much more often than helpful to the analyzer in most cases. That said, if we're going to ever revert this decision, i think it's great to have more stuff already working, so i'd not worry about that. If moving stuff to a header defeats the purpose of some of your tests (eg. tests that specifically test what happens if the function is inlined), then probably it'd be a good idea to duplicate the tests, eg:

// RUN: ... -DUSE_HEADER=0 ...
// RUN: ... -DUSE_HEADER=1 ...

#if USE_HEADER
#include "Inputs/..."
#else
// Paste header here.
#endif

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

196

Had a look. So, essentially, the core copies argument values to parameter regions in enterStackFrame() without ever notifying checkers about it in any way. Okaay. Yep, let's stick to that for now, as i've no better approach in mind.

424

Had a look. So the problem is, we obtain the result of the comparison as a symbol, from which it is too hard to recover the operands in order to move iterator position data from one value to another.

Normally we obtain a simple SymbolConjured for the return value of the operator==() call (or, similarly, operator!=()). For plain-value iterators (eg. typedef T *iterator) we might be obtaining an actual binary symbolic expression, but even then it's not quite clear how to obtain operands (the structure of the expression might have changed due to algebraic simplifications). Additionally, LHS and RHS aren't necessarily symbols (they might be semi-concrete), so composing symbolic expressions from them in general is problematic with our symbol hierarchy, which is rarely a problem for numbers but for structural symbols it'd be a mess.

For now i suggest, instead of storing only the last LHS and RHS, to save a map from symbols (which are results of comparisons) to (LHS value, RHS value) pairs. This map should, apart from the obvious, be cleaned up whenever one of the iterators in the pair gets mutated (incremented or decremented). This should take care of the problem Alexey points out, and should work with semi-concrete stuff.

For the future i suggest to let users construct their own symbols and symbolic expressions more easily. In fact, if only we had all iterators as regions, we should have probably used SymbolMetadata for this purpose: it's easy to both recover the parent region from it and use it in symbolic expressions. We could also deprecate the confusing structural symbols (provide default-bound lazy compound values for conjured structures instead), and then it'd be possible to transition to SymbolMetadata entirely.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

581

Ouch, i have one more concern, which can be expressed with the following false-positive test which currently fails:

void foo() {
  std::vector<int> vec;
  vec.push_back(2016);
  auto i = vec.find(vec.begin(), vec.end(), 2016);
  *i; // no-warning
}

Not instantly sure what to do with this. You can avoid state splits until you are actually sure if both branches are possible, but that'd suppress a lot of useful positives. Such positives could be suppressed with assertions, of course, but i'd still hope there aren't too many of those.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

581

I mean, std::find(... ><

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

424

Thank you for the suggestion. I am not sure if I fully understand you. If I create a map where the key is the resulting symbol of the comparison, it will not work because evalAssume is called for the innermost comparison. So if the body of operator== (or operator!=) is inlined, then I get a binary symbolic expression in evalAssume, not the SymbolConjured. This binary Symbolic expression is a comparison of the internals of the iterators, e.g. the internal pointer. So the key will not match any LHS and RHS value pair in the map. I also thought on such solution earlier but I dismissed it because of this.

581

False positives can occur whenever we are sure that we will find the element so we do not check for the result to be equal with end().

[baloghadamsoftware]

Interim version, updated according to some of the comments.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

338

Instead of swapping I moved the code into a separate function and I call this functions now with differenet parameters.

574

There is an overload that does not requires a tag, but it requires a type instad.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

424

Maybe if I evaluate the operator==() call for iterators using evalCall()?

[NoQ]

Sorry for inactivity, been thinking quite a bit about this checker. The checker is very cool because it is an excellent showcase of our API problems in the realm of C++ checkers. Once the checker is committed, we could try various things to make it easier to develop other checkers like this in the future. Also the check is very useful, and improving C++ support in the analyzer is very desired, so again thank you for your work.

Right now the course of action, i think, is to

• Agree on the evalAssume() implementation (i'm still not quite understanding what the problem is here, see the new inline comments);
• Add some more comments into the code (especially comment up all the object-copy handling, when iterator state moves from one symbol/region to another symbol/region upon various events).

Then, i think, we should land the commit, assuming that you have a desire to address more issues in subsequent commits to eventually enable it by default.

For enabling by default, the following should most likely be addressed:

• We should probably not warn by default on unchecked std::find (see comments following the push_back(2016) example), unless some strong arguments against such code patterns are provided;
• A BugReporterVisitor should be added to report iterator state changes to the user across the diagnostic path;
• Our code owners often have strong opinions regarding warning message wording.

Then there are a few ideas on finding more bugs, which you shouldn't necessarily implement, that came up during the review, eg.:

• Alexey suspects that iterators implemented as plain pointers (commonly used in LLVM itself) might be unsupported;
• Alexey points out that ++/-- may be handled in a less conservative manner;
• More checks could be implemented in this checker, eg. passing end() as first argument of std::find() is an instant bug (somebody accidentally swapped begin and end?).

A list of ideas on improving core experience, mostly for myself because i seem to be the only one with strong opinions on this:

• Provide a checker callback for structure copies, which would unify the multitude of similar callbacks in this checker;
• Consider removing the conjured structure symbol hack.

Did i forget anything?

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

205

This code definitely deserves comments. I managed to understand that this is a workaround for completely replacing the conjured symbol with a lazy value upon calling a method over temporary, which the core does from time to time, and i suspect that this code may break whenever more than one checker starts doing this (i.e. you'd have to skip more than one predecessor node in this case).

I still think that the root cause here is conjured structural symbols which i'd probably prefer to get rid of completely, and then this hack wouldn't be necessary.

424

Well, even if the body of the comparison operator is inlined, PreStmt/PostStmt callbacks should still work, and it doesn't really matter if there's a SymbolConjured or not, we can still add the symbolic expression to our map as a key.

Essentially, you ignore whatever happens in the iterator's operator==() when it's inlined (including any evalAssume events), then in PostStmt of operator==() you map the return-value symbol of the operator to the operator's arguments (operands), then whenever an assumption is being made against the return-value symbol, you carry over this assumption to the operands. I think it shouldn't really matter if the operator call was inlined.

The only unexpected thing that may happen due to inlining is if the inlined operator returns a concrete value (plain true or plain false) instead of the symbol, but in this case what we need to do is to just carry over the assumption to the operands instantly.

581

Yep, so there's a bit of grey area here. The test case i wrote is very artificial, i.e. it is not idiomatic, in fact there aren't many cases when doing find() is actually useful when we're sure the element is there.

However, if we eventually enable this checker by default (move out of the alpha.* package), then i think we need to come up with a better behavior for this case:

• maybe it depends on container type (eg. for map-like containers we may know that the key is there but we don't know the value?);
• maybe it's a good idea to add a checker option to enable or disable the warning upon using unchecked find results;
• maybe we'd learn to reason about containers a bit better, even though it'd be hard.

So i've a feeling this can be moved to a FIXME/later, but it's definitely something to think about.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

424

Sorry, maybe my phrasing was not accurate enough. The problem is that the assumption is not being made against the return-value symbol of the operator==(), but if inlined, against the internal == operator. So I do not have the same key in evalAssume() thus I cannot access the operands from the map I stored in checkPostCall(). The only solution I can imagine is that I evalCall() the operator==() but then we lose the opportunity to check anything inside the body of the operator.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

205

I think I do not fully understand you here: do you mean some fix in the core?

[zaks.anna]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

220

At least one advantage of the assert is that it provides an error message. I'd not try to minimize the number of asserts.

424

Thanks for working on this!!!

We've discussed this with Artem and Devin in more detail and here are the notes from the conversation.

Just to summarize, Artem's proposal is to replace the two trates for RHS and LHS with a map from a symbol that represents the result of the iterator comparison to LHS SVal, RHS SVal, and the relation between them (== | !=).

Are you concerned about this case:

bool operator==(const it&RHS) {

return x == RHS.x; // If evalAssume is called here, we are just going to ignore it.

} // We get a post call and can fill in the map from binary symbolic expression to LHS and RHS.

You are right, we will get a binary symbolic expression and not SymbolConjured. And we will not fill in the map until the return from the inlined operator. However, even if the operator is inlined, we will be calling PostCall on it after the return. So at that point, the (binary symbolic expression) -> (LHS, RHS, ==) entry will be added to the map, where the LHS and RHS will be the arguments to the call. The evalAssume will be called on the caller side.

Another example:
bool operator==(const it&RHS) {

if (x == RHS.x)
  return y = RHS.y;
return false; // <- Constant is returned.

}
In this case, a concrete value is returned on one of the branches. The suggestion is not to rely on evalAssume, but record the relation of the iterators based on the value of the constant being returned. When the expression is evaluated on the caller side, one of the branches will be unreachable anyway, so we will not loose precision here even if we do nothing on evalAssume.

Also, could you please add examples that use the inlined and non-inlined operators in the following way to make sure everything still works:

if ( ! (i==e) )

Very Important: You should test your patch with eagerly assume option turned on since this mode the analyzer is on by default and running without eagerly assume is outdated. An option to run without eagerly assume should be removed altogether.

[baloghadamsoftware]

Updated according to comments.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

210

You are right, and the same is true for PreCall.

220

I agree, but I think Alexei is rigt here: cast<> already has the assert we need here.

323

That will be part of another checker, but where exactly to put the comment you suggest?

424

OK, I did it. My initial problem was that I believed that the return value in checkPostCall will be different from the symbolic expression representing the internal comparison, but no, it was the same. I also put a new trick into evalAssume for the negated case you mention. Furthermore, if eagerly assume is enabled, we get concrete integer as result in checkPostCall so we process the iterator there in this case.

In the automatic test I cannot test inlined operators, because it does not inline anything that is included from a remote file. But I tested it manually, everything seems to work.

[baloghadamsoftware]

In D25660#590778, @NoQ wrote:

• Agree on the evalAssume() implementation (i'm still not quite understanding what the problem is here, see the new inline comments);

I think it will be settled soon.

• We should probably not warn by default on unchecked std::find (see comments following the push_back(2016) example), unless some strong arguments against such code patterns are provided;

It is automatic. The role of evalCall is only to reduce the exploded graph. If I remove it, we get the same result (that is why we have a nonStdFind there, to check this case). but with far more states. Especially in case of vector, where the GNU implementation is quite complicated because of optimizations.

• A BugReporterVisitor should be added to report iterator state changes to the user across the diagnostic path;

I also thought of this. The question is where to start the chain.

• Our code owners often have strong opinions regarding warning message wording.

I need suggestions here.

Then there are a few ideas on finding more bugs, which you shouldn't necessarily implement, that came up during the review, eg.:

• Alexey suspects that iterators implemented as plain pointers (commonly used in LLVM itself) might be unsupported;

I think it is supported now.

• Alexey points out that ++/-- may be handled in a less conservative manner;

That is a future plan, but then it also results in a new name for the checker, e.g. IteratorRange.

• More checks could be implemented in this checker, eg. passing end() as first argument of std::find() is an instant bug (somebody accidentally swapped begin and end?).

Good idea, but what if it is intentional? I do not mean that we pass end() directly, but if we do a loop of find() functions where the beginning of the next range is always the successor of the last found element, we may result in a range of [end(), end()[, which I think is a valid empty range:

const auto start = v.begin();
while(true) {
   const auto item = find(start, v.end());
   if(item==v.end())
      break;
   doSomething(*item);
   start = ++item;
}

A list of ideas on improving core experience, mostly for myself because i seem to be the only one with strong opinions on this:

• Provide a checker callback for structure copies, which would unify the multitude of similar callbacks in this checker;

A callback? Or just move the copy into a simple (or template?) function?

• Consider removing the conjured structure symbol hack.

Which hack do you mean here? In evalCall() of the various std functions? As I mentioned, they can be removed, but then we will get more states in the exploded graph.

Did i forget anything?

[zaks.anna]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

424

You can test the inlining case by turning on inlining of containers. I think it's important to add a test since the logic is somewhat complicated and it's possible the analyzer will change the treatment of containers in the future. Here is the option. I'd just add another test case with that option enabled:

/// Returns whether or not methods of C++ container objects may be considered
/// for inlining.
///
/// This is controlled by the 'c++-container-inlining' config option, which
/// accepts the values "true" and "false".
bool mayInlineCXXContainerMethods();

[baloghadamsoftware]

Test updated to include test case where system headers are inlined.

[baloghadamsoftware]

test/Analysis/Inputs/system-header-simulator-for-iterators.h

62 ↗

(On Diff #78527)

Maybe we should merge this file with the system-header-simulator-cxx.h? It already contains a vector type but no iterators.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

205

I am not sure why I am handleing CXXOperatorCall here. Instead, I should handle every call, but only instance calls. For final solution would it not be better to make the checker explicitely metrialize a temporary object here instead of just creating it silently? Then my existing checker function would catch it.

[NoQ]

In D25660#598576, @baloghadamsoftware wrote:

In D25660#590778, @NoQ wrote:

• Agree on the evalAssume() implementation (i'm still not quite understanding what the problem is here, see the new inline comments);

I think it will be settled soon.

This part makes a lot of sense to me now, cool!

Hmm, so we model !($x) as $x == 0. That's tricky. Maybe we should also consider a test like if ( (i == v.end()) == true ); once it's done, we're be doing as good of a job as RangeConstraintManager does on numeric symbols, which would be great and not worth improving further.

• We should probably not warn by default on unchecked std::find (see comments following the push_back(2016) example), unless some strong arguments against such code patterns are provided;

It is automatic. The role of evalCall is only to reduce the exploded graph. If I remove it, we get the same result (that is why we have a nonStdFind there, to check this case). but with far more states. Especially in case of vector, where the GNU implementation is quite complicated because of optimizations.

Yep, i agree that some kind of evalCall is useful. However, it's now causing more positives than it should, and i think this behavior needs to be eventually avoided, because false positives are very scary - eg. we should try to end up with one state instead of two. Because by splitting states, we declare the possibility of both branches, which in this case is not always correct.

• A BugReporterVisitor should be added to report iterator state changes to the user across the diagnostic path;

I also thought of this. The question is where to start the chain.

At least, the very last state update to the region that failed (without copies) should be easy to support. Copies would be tricky - i'm thinking of tagging nodes where copies happened with special program point tags that help us understand which region was the source for the copy.

• More checks could be implemented in this checker, eg. passing end() as first argument of std::find() is an instant bug (somebody accidentally swapped begin and end?).

Good idea, but what if it is intentional? I do not mean that we pass end() directly, but if we do a loop of find() functions where the beginning of the next range is always the successor of the last found element, we may result in a range of [end(), end()[, which I think is a valid empty range:

const auto start = v.begin();
while(true) {
   const auto item = find(start, v.end());
   if(item==v.end())
      break;
   doSomething(*item);
   start = ++item;
}

I misread the docs, sorry><

A list of ideas on improving core experience, mostly for myself because i seem to be the only one with strong opinions on this:

• Provide a checker callback for structure copies, which would unify the multitude of similar callbacks in this checker;

A callback? Or just move the copy into a simple (or template?) function?

A callback would certainly be better, because it removes a lot of boilerplate from the checker (to subscribe to one callback instead of five would be great). But that's a future plan, not for this patch.

• Consider removing the conjured structure symbol hack.

Which hack do you mean here? In evalCall() of the various std functions? As I mentioned, they can be removed, but then we will get more states in the exploded graph.

I've just made an attempt in D27202.

---

I think this is good to go as an alpha checker!
I'm still in favor of more comments in this code.
One more minor inline nit.

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

460

This produces a -Wparentheses warning, i think we should silence it by putting an extra () around operator = because the assignment is intentional here.

[zaks.anna]

It's awesome to see that all the major issues have been addressed. Thank you for working on this and diligently working through the code review!!!

I have a few minor comments below.

Could you add this example yours as a "no-warning" test case:
const auto start = v.begin();
while(true) {

const auto item = find(start, v.end());
if(item==v.end())
   break;
doSomething(*item);
start = ++item;

}

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

167

How about: "C++ STL Error" -> "Misuse of STL APIs"

387

Please, quote svn revision number instead of phabricator number.

396

You could simplify the code a bit by moving all these identifier lookups into a subrutine and/or just have a single statement guard checking f they have been initialized.

446

I agree with Artem that the future readers and maintainers of this code would greatly benefit if there were higher level comments explaining how this checker works. For example, here, we are saving the information about the comparison because iterators are value types...

722

Would isInStdNamespace() from BugReporterVisitor.cpp be useful here? It would be fine to add this API to the CheckerContext or some other place accessible from here and the BugReporter.

733

This could be useful for other checkers as well. Maybe refactor this out as part of a subsequent commit?

test/Analysis/Inputs/system-header-simulator-for-iterators.h

62 ↗

(On Diff #78527)

Yes, we the headers are supposed to be reusable for different checkers!

test/Analysis/iterator-past-end.cpp

74

The error message is not very good for the find API cases. There is only a possibility of access past end. Also its much better to be explicit about what went wrong here - the user forgot to check the return value of find. We could say something like "The value returned from 'find' needs to be checked before it's accessed".

We'd need to implement a custom BugReporterVisitor that detects if the iterator is a return value from some method that needs checking. This can be & should be a separate patch.

[zaks.anna]

Also, have you evaluated this on real codebases? What results do you see? Are there any false positives found? Are there any true positives found?

[baloghadamsoftware]

Minor corrections, comments, some new tests, test input headers merged.

[baloghadamsoftware]

D27202 is now a dependency, but cannot add it.

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

167

OK, I copied it from another checker :-)

[zaks.anna]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

722

Is there a reason not to use isInStdNamespace() instead of the inTopLevelNamespace()? We can add the API to Checker Context.

[NoQ]

A quick example of how a bug reporter visitor for this checker may look like - it needs to be expanded significantly but here's a start:

Visitor.patch4 KBDownload

report-999911.html7 KBDownload

<== example of how it looks.

See, for example, MallocChecker to understand the rest of the bureaucracy around bug reporter visitors.

[zaks.anna]

Thanks Artem!

Just to be clear, I think this patch should be committed once "inTopLevelNamespace" issue is addressed. That is the only issue pending as far as I can see.

The visitor should be a separate patch.

[baloghadamsoftware]

Now isInStdNamespace is used. Hack is back so D27202 is not a dependency now.

[baloghadamsoftware]

In D25660#613519, @zaks.anna wrote:

Also, have you evaluated this on real codebases? What results do you see? Are there any false positives found? Are there any true positives found?

I am doing it right now. Unfortunately I found a crash which I fixed, but then it turned out that overwrites of the iterator variable are not handled. I am working on this problem.

[zaks.anna]

I am doing it right now. Unfortunately I found a crash which I fixed,

Is it fixed in this patch?

but then it turned out that overwrites of the iterator variable are not handled. I am working on this
problem.

My suggestion is to commit this patch and address the iterator variable overwrites separately, so that it would be more incremental and easier to review. Does this sound good to you?

[zaks.anna]

And thank you for the awesome work and addressing the review comments!!!

include/clang/StaticAnalyzer/Checkers/Checkers.td

 } // end: "cplusplus"
 
 let ParentPackage = CplusplusAlpha in {
 
 def VirtualCallChecker : Checker<"VirtualCall">,
   HelpText<"Check virtual function calls during construction or destruction">,
   DescFile<"VirtualCallChecker.cpp">;
 
+def IteratorPastEndChecker : Checker<"IteratorPastEnd">,
+  HelpText<"Check iterators used past end">,
+  DescFile<"IteratorPastEndChecker.cpp">;
+
 } // end: "alpha.cplusplus"
 
 
 //===----------------------------------------------------------------------===//
 // Valist checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = ValistAlpha in {

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp
   FixedAddressChecker.cpp
   GenericTaintChecker.cpp
   IdenticalExprChecker.cpp
+  IteratorPastEndChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

+//===-- IteratorPastEndChecker.cpp --------------------------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for using iterators outside their range (past end). Usage
+// means here dereferencing, incrementing etc.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+#include <utility>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+struct IteratorPosition {
+private:
+  enum Kind { InRange, OutofRange } K;
+  IteratorPosition(Kind InK) : K(InK) {}
+
+public:
+  bool isInRange() const { return K == InRange; }
+  bool isOutofRange() const { return K == OutofRange; }
+
+  static IteratorPosition getInRange() { return IteratorPosition(InRange); }
+  static IteratorPosition getOutofRange() {
+    return IteratorPosition(OutofRange);
+  }
+
+  bool operator==(const IteratorPosition &X) const { return K == X.K; }
+  bool operator!=(const IteratorPosition &X) const { return K != X.K; }
+  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
+};
+
+typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
+
+struct IteratorComparison {
+private:
+  RegionOrSymbol Left, Right;
+  bool Equality;
+
+public:
+  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
+      : Left(L), Right(R), Equality(Eq) {}
+
+  RegionOrSymbol getLeft() const { return Left; }
+  RegionOrSymbol getRight() const { return Right; }
+  bool isEquality() const { return Equality; }
+  bool operator==(const IteratorComparison &X) const {
+    return Left == X.Left && Right == X.Right && Equality == X.Equality;
+  }
+  bool operator!=(const IteratorComparison &X) const {
+    return Left != X.Left || Right != X.Right || Equality != X.Equality;
+  }
+  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
+};
+
+class IteratorPastEndChecker
+    : public Checker<
+          check::PreCall, check::PostCall, check::PostStmt<CXXConstructExpr>,
+          check::PostStmt<DeclStmt>, check::PostStmt<MaterializeTemporaryExpr>,
+          check::BeginFunction, check::DeadSymbols, eval::Assume, eval::Call> {
+  mutable IdentifierInfo *II_std = nullptr, *II_find = nullptr,
+                         *II_find_end = nullptr, *II_find_first_of = nullptr,
+                         *II_find_if = nullptr, *II_find_if_not = nullptr,
+                         *II_lower_bound = nullptr, *II_upper_bound = nullptr,
+                         *II_search = nullptr, *II_search_n = nullptr;
+
+  std::unique_ptr<BugType> PastEndBugType;
+
+  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
+                        const SVal &RVal, OverloadedOperatorKind Op) const;
+  void handleAccess(CheckerContext &C, const SVal &Val) const;
+  void handleDecrement(CheckerContext &C, const SVal &Val) const;
+  void handleEnd(CheckerContext &C, const SVal &RetVal) const;
+
+  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
+  bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
+  bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
+  bool evalSearch(CheckerContext &C, const CallExpr *CE) const;
+  bool evalSearchN(CheckerContext &C, const CallExpr *CE) const;
+  void Find(CheckerContext &C, const CallExpr *CE) const;
+
+  void reportPastEndBug(const StringRef &Message, const SVal &Val,
+                        CheckerContext &C, ExplodedNode *ErrNode) const;
+  void initIdentifiers(ASTContext &Ctx) const;
+
+public:
+  IteratorPastEndChecker();
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkBeginFunction(CheckerContext &C) const;
+  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
+  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                     CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
+                             bool Assumption) const;
+  bool evalCall(const CallExpr *CE, CheckerContext &C) const;
+};
+}
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
+                               IteratorPosition)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
+                               IteratorComparison)
+
+#define INIT_ID(Id)                                                            \
+  if (!II_##Id)                                                                \
+  II_##Id = &Ctx.Idents.get(#Id)
+
+namespace {
+
+static bool isIteratorType(const QualType &Type);
+static bool isIterator(const CXXRecordDecl *CRD);
+static bool isEndCall(const FunctionDecl *Func);
+static bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
+static bool isAccessOperator(OverloadedOperatorKind OK);
+static bool isDecrementOperator(OverloadedOperatorKind OK);
+static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II);
+static BinaryOperator::Opcode getOpcode(const SymExpr *SE);
+static const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
+static const ProgramStateRef processComparison(ProgramStateRef State,
+                                               RegionOrSymbol LVal,
+                                               RegionOrSymbol RVal, bool Equal);
+static const ProgramStateRef saveComparison(ProgramStateRef State,
+                                            const SymExpr *Condition,
+                                            const SVal &LVal, const SVal &RVal,
+                                            bool Eq);
+static const IteratorComparison *loadComparison(ProgramStateRef State,
+                                                const SymExpr *Condition);
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                                   const SVal &Val);
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                                   RegionOrSymbol RegOrSym);
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+                                           const SVal &Val,
+                                           IteratorPosition Pos);
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+                                           RegionOrSymbol RegOrSym,
+                                           IteratorPosition Pos);
+static ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
+                                              RegionOrSymbol RegOrSym,
+                                              IteratorPosition Pos, bool Equal);
+static bool contradictingIteratorPositions(IteratorPosition Pos1,
+                                           IteratorPosition Pos2, bool Equal);
+}
+
+IteratorPastEndChecker::IteratorPastEndChecker() {
+  PastEndBugType.reset(
+      new BugType(this, "Iterator Past End", "Misuse of STL APIs"));
+  PastEndBugType->setSuppressOnSink(true);
+}
+
+void IteratorPastEndChecker::checkPreCall(const CallEvent &Call,
+                                          CheckerContext &C) const {
+  // Check for access past end
+  const auto *Func = Call.getDecl()->getAsFunction();
+  if (!Func)
+    return;
+  if (Func->isOverloadedOperator()) {
+    if (isAccessOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleAccess(C, InstCall->getCXXThisVal());
+      } else {
+        handleAccess(C, Call.getArgSVal(0));
+      }
+    }
+  }
+}
+
+void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
+                                           CheckerContext &C) const {
+  // Record end() iterators, iterator decrementation and comparison
+  const auto *Func = Call.getDecl()->getAsFunction();
+  if (!Func)
+    return;
+  if (Func->isOverloadedOperator()) {
+    const auto Op = Func->getOverloadedOperator();
+    if (isSimpleComparisonOperator(Op)) {
+      if (Func->isCXXInstanceMember()) {
+        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+        handleComparison(C, InstCall.getReturnValue(), InstCall.getCXXThisVal(),
+                         InstCall.getArgSVal(0), Op);
+      } else {
+        handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
+                         Call.getArgSVal(1), Op);
+      }
+    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+      if (Func->isCXXInstanceMember()) {
+        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+        handleDecrement(C, InstCall.getCXXThisVal());
+      } else {
+        handleDecrement(C, Call.getArgSVal(0));
+      }
+    }
+  } else if (Func->isCXXInstanceMember()) {
+    if (!isEndCall(Func))
+      return;
+    if (!isIteratorType(Call.getResultType()))
+      return;
+    handleEnd(C, Call.getReturnValue());
+  }
+}
+
+void IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const {
+  // Copy state of iterator arguments to iterator parameters
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+
+  const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
+  if (!Site)
+    return;
+
+  const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
+  if (!FD)
+    return;
+
+  const auto *CE = dyn_cast<CallExpr>(Site);
+  if (!CE)
+    return;
+
+  bool Change = false;
+  int idx = 0;
+  for (const auto P : FD->parameters()) {
+    auto Param = State->getLValue(P, LCtx);
+    auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
+    const auto *Pos = getIteratorPosition(State, Arg);
+    if (!Pos)
+      continue;
+    State = setIteratorPosition(State, Param, *Pos);
+    Change = true;
+  }
+  if (Change) {
+    C.addTransition(State);
+  }
+}
+
+void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE,
+                                           CheckerContext &C) const {
+  // Transfer iterator state in case of copy or move by constructor
+  const auto *ctr = CCE->getConstructor();
+  if (!ctr->isCopyOrMoveConstructor())
+    return;
+  const auto *RHSExpr = CCE->getArg(0);
+
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+
+  const auto RetVal = State->getSVal(CCE, LCtx);
+
+  const auto RHSVal = State->getSVal(RHSExpr, LCtx);
+  const auto *RHSPos = getIteratorPosition(State, RHSVal);
+  if (!RHSPos)
+    return;
+  State = setIteratorPosition(State, RetVal, *RHSPos);
+  C.addTransition(State);
+}
+
+void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS,
+                                           CheckerContext &C) const {
+  // Transfer iterator state to new variable declaration
+  for (const auto *D : DS->decls()) {
+    const auto *VD = dyn_cast<VarDecl>(D);
+    if (!VD || !VD->hasInit())
+      continue;
+
+    auto State = C.getState();
+    const auto *LCtx = C.getPredecessor()->getLocationContext();
+    const auto *Pos =
+        getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx));
+    if (!Pos)
+      continue;
+    State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos);
+    C.addTransition(State);
+  }
+}
+
+void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                                           CheckerContext &C) const {
+  /* Transfer iterator state for to temporary objects */
+  auto State = C.getState();
+  const auto *LCtx = C.getPredecessor()->getLocationContext();
+  const auto *Pos =
+      getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
+  if (!Pos)
+    return;
+  State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
+  C.addTransition(State);
+}
+
+void IteratorPastEndChecker::checkDeadSymbols(SymbolReaper &SR,
+                                              CheckerContext &C) const {
+  auto State = C.getState();
+
+  auto RegionMap = State->get<IteratorRegionMap>();
+  for (const auto Reg : RegionMap) {
+    if (!SR.isLiveRegion(Reg.first)) {
+      State = State->remove<IteratorRegionMap>(Reg.first);
+    }
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (const auto Sym : SymbolMap) {
+    if (SR.isDead(Sym.first)) {
+      State = State->remove<IteratorSymbolMap>(Sym.first);
+    }
+  }
+
+  auto ComparisonMap = State->get<IteratorComparisonMap>();
+  for (const auto Comp : ComparisonMap) {
+    if (SR.isDead(Comp.first)) {
+      State = State->remove<IteratorComparisonMap>(Comp.first);
+    }
+  }
+}
+
+ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State,
+                                                   SVal Cond,
+                                                   bool Assumption) const {
+  // Load recorded comparison and transfer iterator state between sides
+  // according to comparison operator and assumption
+  const auto *SE = Cond.getAsSymExpr();
+  if (!SE)
+    return State;
+
+  auto Opc = getOpcode(SE);
+  if (Opc != BO_EQ && Opc != BO_NE)
+    return State;
+
+  bool Negated = false;
+  const auto *Comp = loadComparison(State, SE);
+  if (!Comp) {
+    // Try negated comparison, which is a SymExpr to 0 integer comparison
+    const auto *SIE = dyn_cast<SymIntExpr>(SE);
+    if (!SIE)
+      return State;
+
+    if (SIE->getRHS() != 0)
+      return State;
+
+    SE = SIE->getLHS();
+    Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
+    Opc = getOpcode(SE);
+    if (Opc != BO_EQ && Opc != BO_NE)
+      return State;
+
+    Comp = loadComparison(State, SE);
+    if (!Comp)
+      return State;
+  }
+
+  return processComparison(State, Comp->getLeft(), Comp->getRight(),
+                           (Comp->isEquality() == Assumption) != Negated);
+}
+
+// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions
+//       checker (see patch r284960) or another similar checker for C++ STL
+//       functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions).
+bool IteratorPastEndChecker::evalCall(const CallExpr *CE,
+                                      CheckerContext &C) const {
+  const FunctionDecl *FD = C.getCalleeDecl(CE);
+  if (!FD)
+    return false;
+
+  ASTContext &Ctx = C.getASTContext();
+  initIdentifiers(Ctx);
+
+  if (FD->getKind() == Decl::Function) {
+    if (inTopLevelNamespace(FD, II_std)) {
+      if (FD->getIdentifier() == II_find) {
+        return evalFind(C, CE);
+      } else if (FD->getIdentifier() == II_find_end) {
+        return evalFindEnd(C, CE);
+      } else if (FD->getIdentifier() == II_find_first_of) {
+        return evalFindFirstOf(C, CE);
+      } else if (FD->getIdentifier() == II_find_if) {
+        return evalFindIf(C, CE);
+      } else if (FD->getIdentifier() == II_find_if) {
+        return evalFindIf(C, CE);
+      } else if (FD->getIdentifier() == II_find_if_not) {
+        return evalFindIfNot(C, CE);
+      } else if (FD->getIdentifier() == II_upper_bound) {
+        return evalUpperBound(C, CE);
+      } else if (FD->getIdentifier() == II_lower_bound) {
+        return evalLowerBound(C, CE);
+      } else if (FD->getIdentifier() == II_search) {
+        return evalSearch(C, CE);
+      } else if (FD->getIdentifier() == II_search_n) {
+        return evalSearchN(C, CE);
+      }
+    }
+  }
+
+  return false;
+}
+
+void IteratorPastEndChecker::handleComparison(CheckerContext &C,
+                                              const SVal &RetVal,
+                                              const SVal &LVal,
+                                              const SVal &RVal,
+                                              OverloadedOperatorKind Op) const {
+  // Record the operands and the operator of the comparison for the next
+  // evalAssume, if the result is a symbolic expression. If it is a concrete
+  // value (only one branch is possible), then transfer the state between
+  // the operands according to the operator and the result
+  auto State = C.getState();
+  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
+    const auto *LPos = getIteratorPosition(State, LVal);
+    const auto *RPos = getIteratorPosition(State, RVal);
+    if (!LPos && !RPos)
+      return;
+    State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
+    C.addTransition(State);
+  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
+    if ((State = processComparison(
+             State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
+             (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
+      C.addTransition(State);
+    } else {
+      C.generateSink(State, C.getPredecessor());
+    }
+  }
+}
+
+void IteratorPastEndChecker::handleAccess(CheckerContext &C,
+                                          const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && Pos->isOutofRange()) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportPastEndBug("Iterator accessed past its end.", Val, C, N);
+  }
+}
+
+void IteratorPastEndChecker::handleDecrement(CheckerContext &C,
+                                             const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && Pos->isOutofRange()) {
+    State = setIteratorPosition(State, Val, IteratorPosition::getInRange());
+    // FIXME: We could also check for iterators ahead of their beginnig in the
+    //       future, but currently we do not care for such errors. We also
+    //       assume that the iterator is not past its end by more then one
+    //       position.
+    C.addTransition(State);
+  }
+}
+
+void IteratorPastEndChecker::handleEnd(CheckerContext &C,
+                                       const SVal &RetVal) const {
+  auto State = C.getState();
+  State = setIteratorPosition(State, RetVal, IteratorPosition::getOutofRange());
+  C.addTransition(State);
+}
+
+bool IteratorPastEndChecker::evalFind(CheckerContext &C,
+                                      const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalFindEnd(CheckerContext &C,
+                                         const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalFindFirstOf(CheckerContext &C,
+                                             const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalFindIf(CheckerContext &C,
+                                        const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalFindIfNot(CheckerContext &C,
+                                           const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalLowerBound(CheckerContext &C,
+                                            const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalUpperBound(CheckerContext &C,
+                                            const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalSearch(CheckerContext &C,
+                                        const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorPastEndChecker::evalSearchN(CheckerContext &C,
+                                         const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+void IteratorPastEndChecker::Find(CheckerContext &C, const CallExpr *CE) const {
+  auto state = C.getState();
+  auto &svalBuilder = C.getSValBuilder();
+  const auto *LCtx = C.getLocationContext();
+
+  auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
+  auto SecondParam = state->getSVal(CE->getArg(1), LCtx);
+
+  auto stateFound = state->BindExpr(CE, LCtx, RetVal);
+  auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam);
+
+  C.addTransition(stateFound);
+  C.addTransition(stateNotFound);
+}
+
+void IteratorPastEndChecker::reportPastEndBug(const StringRef &Message,
+                                              const SVal &Val,
+                                              CheckerContext &C,
+                                              ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*PastEndBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+void IteratorPastEndChecker::initIdentifiers(ASTContext &Ctx) const {
+  INIT_ID(std);
+  INIT_ID(find);
+  INIT_ID(find_end);
+  INIT_ID(find_first_of);
+  INIT_ID(find_if);
+  INIT_ID(find_if_not);
+  INIT_ID(lower_bound);
+  INIT_ID(upper_bound);
+  INIT_ID(search);
+  INIT_ID(search_n);
+}
+
+namespace {
+
+static bool isIteratorType(const QualType &Type) {
+  if (Type->isPointerType())
+    return true;
+
+  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  return isIterator(CRD);
+}
+
+static bool isIterator(const CXXRecordDecl *CRD) {
+  if (!CRD)
+    return false;
+
+  const auto Name = CRD->getName();
+  if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
+        Name.endswith_lower("it")))
+    return false;
+
+  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
+       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
+  for (const auto *Method : CRD->methods()) {
+    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
+      if (Ctor->isCopyConstructor()) {
+        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
+      }
+      continue;
+    }
+    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
+      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
+      continue;
+    }
+    if (Method->isCopyAssignmentOperator()) {
+      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
+      continue;
+    }
+    if (!Method->isOverloadedOperator())
+      continue;
+    const auto OPK = Method->getOverloadedOperator();
+    if (OPK == OO_PlusPlus) {
+      HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
+      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
+      continue;
+    }
+    if (OPK == OO_Star) {
+      HasDerefOp = (Method->getNumParams() == 0);
+      continue;
+    }
+  }
+
+  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
+         HasPostIncrOp && HasDerefOp;
+}
+
+static bool isEndCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  return IdInfo->getName().endswith_lower("end");
+}
+
+static bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
+  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
+}
+
+static bool isAccessOperator(OverloadedOperatorKind OK) {
+  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
+         OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
+         OK == OO_Subscript;
+}
+
+static bool isDecrementOperator(OverloadedOperatorKind OK) {
+  return OK == OO_MinusEqual || OK == OO_MinusMinus;
+}
+
+static BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
+  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
+    return BSE->getOpcode();
+  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
+    const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
+    if (!COE)
+      return BO_Comma; // Extremal value, neither EQ nor NE
+    if (COE->getOperator() == OO_EqualEqual) {
+      return BO_EQ;
+    } else if (COE->getOperator() == OO_ExclaimEqual) {
+      return BO_NE;
+    }
+    return BO_Comma; // Extremal value, neither EQ nor NE
+  }
+  return BO_Comma; // Extremal value, neither EQ nor NE
+}
+
+static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II) {
+  const auto *ND = dyn_cast<NamespaceDecl>(D->getDeclContext());
+  if (!ND)
+    return false;
+
+  if (ND->getIdentifier() != II)
+    return false;
+
+  return isa<TranslationUnitDecl>(ND->getDeclContext());
+}
+
+static const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return Reg;
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return Sym;
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return LCVal->getRegion();
+  }
+  return RegionOrSymbol();
+}
+
+static const ProgramStateRef processComparison(ProgramStateRef State,
+                                               RegionOrSymbol LVal,
+                                               RegionOrSymbol RVal,
+                                               bool Equal) {
+  const auto *LPos = getIteratorPosition(State, LVal);
+  const auto *RPos = getIteratorPosition(State, RVal);
+  if (LPos && !RPos) {
+    State = adjustIteratorPosition(State, RVal, *LPos, Equal);
+  } else if (!LPos && RPos) {
+    State = adjustIteratorPosition(State, LVal, *RPos, Equal);
+  } else if (LPos && RPos) {
+    if (contradictingIteratorPositions(*LPos, *RPos, Equal)) {
+      return nullptr;
+    }
+  }
+  return State;
+}
+
+static const ProgramStateRef saveComparison(ProgramStateRef State,
+                                            const SymExpr *Condition,
+                                            const SVal &LVal, const SVal &RVal,
+                                            bool Eq) {
+  const auto Left = getRegionOrSymbol(LVal);
+  const auto Right = getRegionOrSymbol(RVal);
+  if (!Left || !Right)
+    return State;
+  return State->set<IteratorComparisonMap>(Condition,
+                                           IteratorComparison(Left, Right, Eq));
+}
+
+static const IteratorComparison *loadComparison(ProgramStateRef State,
+                                                const SymExpr *Condition) {
+  return State->get<IteratorComparisonMap>(Condition);
+}
+
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                                   const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->get<IteratorRegionMap>(Reg);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->get<IteratorSymbolMap>(Sym);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->get<IteratorRegionMap>(LCVal->getRegion());
+  }
+  return nullptr;
+}
+
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                                   RegionOrSymbol RegOrSym) {
+  if (RegOrSym.is<const MemRegion *>()) {
+    return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
+  } else if (RegOrSym.is<SymbolRef>()) {
+    return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
+  }
+  return nullptr;
+}
+
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+                                           const SVal &Val,
+                                           IteratorPosition Pos) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->set<IteratorRegionMap>(Reg, Pos);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->set<IteratorSymbolMap>(Sym, Pos);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
+  }
+  return nullptr;
+}
+
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+                                           RegionOrSymbol RegOrSym,
+                                           IteratorPosition Pos) {
+  if (RegOrSym.is<const MemRegion *>()) {
+    return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
+                                         Pos);
+  } else if (RegOrSym.is<SymbolRef>()) {
+    return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
+  }
+  return nullptr;
+}
+
+static ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
+                                              RegionOrSymbol RegOrSym,
+                                              IteratorPosition Pos,
+                                              bool Equal) {
+
+  if ((Pos.isInRange() && Equal) || (Pos.isOutofRange() && !Equal)) {
+    return setIteratorPosition(State, RegOrSym, IteratorPosition::getInRange());
+  } else if (Pos.isOutofRange() && Equal) {
+    return setIteratorPosition(State, RegOrSym,
+                               IteratorPosition::getOutofRange());
+  } else {
+    return State;
+  }
+}
+
+static bool contradictingIteratorPositions(IteratorPosition Pos1,
+                                           IteratorPosition Pos2, bool Equal) {
+  return ((Pos1 != Pos2) && Equal) ||
+         ((Pos1.isOutofRange() && Pos2.isOutofRange()) && !Equal);
+}
+}
+
+void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<IteratorPastEndChecker>();
+}

lib/StaticAnalyzer/Core/ExprEngine.cpp

case Stmt::ObjCBridgedCastExprClass: {
       getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
       Bldr.addNodes(Dst);
       break;
     }
 
     case Expr::MaterializeTemporaryExprClass: {
       Bldr.takeNodes(Pred);
       const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
-      CreateCXXTemporaryObject(MTE, Pred, Dst);
+      ExplodedNodeSet dstPrevisit;
+      getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
+      ExplodedNodeSet dstExpr;
+      for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
+                                     e = dstPrevisit.end(); i != e ; ++i) {
+        CreateCXXTemporaryObject(MTE, *i, dstExpr);
+      }
+      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
       Bldr.addNodes(Dst);
       break;
     }
 
     case Stmt::InitListExprClass:
       Bldr.takeNodes(Pred);
       VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
       Bldr.addNodes(Dst);

test/Analysis/Inputs/system-header-simulator-cxx.h

 // Like the compiler, the static analyzer treats some functions differently if
 // they come from a system header -- for example, it is assumed that system
 // functions do not arbitrarily free() their parameters, and that some bugs
 // found in system headers cannot be fixed by the user and should be
 // suppressed.
 #pragma clang system_header
 
 typedef unsigned char uint8_t;
 
 typedef __typeof__(sizeof(int)) size_t;
 void *memmove(void *s1, const void *s2, size_t n);
 
+template <typename T, typename Ptr, typename Ref> struct __iterator {
+  typedef __iterator<T, T *, T &> iterator;
+  typedef __iterator<T, const T *, const T &> const_iterator;
+
+  __iterator(const Ptr p) : ptr(p) {}
+
+  __iterator<T, Ptr, Ref> operator++() { return *this; }
+  __iterator<T, Ptr, Ref> operator++(int) { return *this; }
+  __iterator<T, Ptr, Ref> operator--() { return *this; }
+  __iterator<T, Ptr, Ref> operator--(int) { return *this; }
+  Ref operator*() const { return *ptr; }
+  Ptr operator->() const { return *ptr; }
+
+  bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
+  bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
+
+  bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
+  bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
+
+private:
+  Ptr ptr;
+};
+
 namespace std {
   template <class T1, class T2>
   struct pair {
     T1 first;
     T2 second;
     
     pair() : first(), second() {}
     pair(const T1 &a, const T2 &b) : first(a), second(b) {}
     
     template<class U1, class U2>
     pair(const pair<U1, U2> &other) : first(other.first), second(other.second) {}
   };
   
   typedef __typeof__(sizeof(int)) size_t;
   
   template<typename T>
   class vector {
+    typedef __iterator<T, T *, T &> iterator;
+    typedef __iterator<T, const T *, const T &> const_iterator;
+
     T *_start;
     T *_finish;
     T *_end_of_storage;
   public:
     vector() : _start(0), _finish(0), _end_of_storage(0) {}
     ~vector();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
     
     void push_back();
     T pop_back();
 
     T &operator[](size_t n) {
       return _start[n];
     }
     
     const T &operator[](size_t n) const {
       return _start[n];
     }
     
-    T *begin() { return _start; }
-    const T *begin() const { return _start; }
-
-    T *end() { return _finish; }
-    const T *end() const { return _finish; }
+    iterator begin() { return iterator(_start); }
+    const_iterator begin() const { return const_iterator(_start); }
+    iterator end() { return iterator(_finish); }
+    const_iterator end() const { return const_iterator(_finish); }
   };
   
   class exception {
   public:
     exception() throw();
     virtual ~exception() throw();
     virtual const char *what() const throw() {
       return 0;
>::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {
     return __result;
   }
 
   template<class InputIter, class OutputIter>
   OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
     return __copy_backward(II, IE, OI);
   }
 
+  template <class InputIterator, class T>
+  InputIterator find(InputIterator first, InputIterator last, const T &val);
+  template <class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
+                            ForwardIterator2 first2, ForwardIterator2 last2);
+  template <class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator1 find_first_of(ForwardIterator1 first1,
+                                 ForwardIterator1 last1,
+                                 ForwardIterator2 first2,
+                                 ForwardIterator2 last2);
+  template <class InputIterator, class UnaryPredicate>
+  InputIterator find_if(InputIterator first, InputIterator last,
+                        UnaryPredicate pred);
+  template <class InputIterator, class UnaryPredicate>
+  InputIterator find_if_not(InputIterator first, InputIterator last,
+                            UnaryPredicate pred);
+  template <class InputIterator, class T>
+  InputIterator lower_bound(InputIterator first, InputIterator last,
+                            const T &val);
+  template <class InputIterator, class T>
+  InputIterator upper_bound(InputIterator first, InputIterator last,
+                            const T &val);
+  template <class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
+                          ForwardIterator2 first2, ForwardIterator2 last2);
+  template <class ForwardIterator1, class ForwardIterator2>
+  ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1,
+                            ForwardIterator2 first2, ForwardIterator2 last2);
+
   struct input_iterator_tag { };
   struct output_iterator_tag { };
   struct forward_iterator_tag : public input_iterator_tag { };
   struct bidirectional_iterator_tag : public forward_iterator_tag { };
   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
 
 }
 

test/Analysis/diagnostics/explicit-suppression.cpp

class C {
   // The virtual function is to make C not trivially copy assignable so that we call the
   // variant of std::copy() that does not defer to memmove().
   virtual int f();
 };
 
 void testCopyNull(C *I, C *E) {
   std::copy(I, E, (C *)0);
 #ifndef SUPPRESSED
-  // expected-warning@../Inputs/system-header-simulator-cxx.h:166 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:191 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/inlining/stl.cpp

 // RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,cplusplus.NewDelete,debug.ExprInspection -analyzer-config c++-container-inlining=true -analyzer-config c++-stdlib-inlining=false -std=c++11 -verify %s
 // RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,cplusplus.NewDelete,debug.ExprInspection -analyzer-config c++-container-inlining=true -analyzer-config c++-stdlib-inlining=true -std=c++11 -DINLINE=1 -verify %s
 
 #include "../Inputs/system-header-simulator-cxx.h"
 
 void clang_analyzer_eval(bool);
 
 void testVector(std::vector<int> &nums) {
-  if (nums.begin()) return;
-  if (nums.end()) return;
+  if (nums.begin() != nums.end()) return;
   
   clang_analyzer_eval(nums.size() == 0);
 #if INLINE
   // expected-warning@-2 {{TRUE}}
 #else
   // expected-warning@-4 {{UNKNOWN}}
 #endif
 }

test/Analysis/iterator-past-end.cpp

+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void simple_good(const std::vector<int> &v) {
+  auto i = v.end();
+  if (i != v.end())
+    *i; // no-warning
+}
+
+void simple_good_negated(const std::vector<int> &v) {
+  auto i = v.end();
+  if (!(i == v.end()))
+    *i; // no-warning
+}
+
+void simple_bad(const std::vector<int> &v) {
+  auto i = v.end();
+  *i; // expected-warning{{Iterator accessed past its end}}
+}
+
+void copy(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  *i2; // expected-warning{{Iterator accessed past its end}}
+}
+
+void decrease(const std::vector<int> &v) {
+  auto i = v.end();
+  --i;
+  *i; // no-warning
+}
+
+void copy_and_decrease1(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i1; // no-warning
+}
+
+void copy_and_decrease2(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i2; // expected-warning{{Iterator accessed past its end}}
+}
+
+void copy_and_increase1(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i1 == v.end())
+    *i2; // no-warning
+}
+
+void copy_and_increase2(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i2 == v.end())
+    *i2; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_find(std::vector<int> &vec, int e) {
+  auto first = std::find(vec.begin(), vec.end(), e);
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_find(std::vector<int> &vec, int e) {
+  auto first = std::find(vec.begin(), vec.end(), e);
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_find_end(std::vector<int> &vec, std::vector<int> &seq) {
+  auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+  if (vec.end() != last)
+    *last; // no-warning
+}
+
+void bad_find_end(std::vector<int> &vec, std::vector<int> &seq) {
+  auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+  *last; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
+  auto first =
+      std::find_first_of(vec.begin(), vec.end(), seq.begin(), seq.end());
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
+  auto first = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+bool odd(int i) { return i % 2; }
+
+void good_find_if(std::vector<int> &vec) {
+  auto first = std::find_if(vec.begin(), vec.end(), odd);
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_if(std::vector<int> &vec, int e) {
+  auto first = std::find_if(vec.begin(), vec.end(), odd);
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_find_if_not(std::vector<int> &vec) {
+  auto first = std::find_if_not(vec.begin(), vec.end(), odd);
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_if_not(std::vector<int> &vec, int e) {
+  auto first = std::find_if_not(vec.begin(), vec.end(), odd);
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_lower_bound(std::vector<int> &vec, int e) {
+  auto first = std::lower_bound(vec.begin(), vec.end(), e);
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_lower_bound(std::vector<int> &vec, int e) {
+  auto first = std::lower_bound(vec.begin(), vec.end(), e);
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_upper_bound(std::vector<int> &vec, int e) {
+  auto last = std::lower_bound(vec.begin(), vec.end(), e);
+  if (vec.end() != last)
+    *last; // no-warning
+}
+
+void bad_upper_bound(std::vector<int> &vec, int e) {
+  auto last = std::lower_bound(vec.begin(), vec.end(), e);
+  *last; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_search(std::vector<int> &vec, std::vector<int> &seq) {
+  auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_search(std::vector<int> &vec, std::vector<int> &seq) {
+  auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_search_n(std::vector<int> &vec, std::vector<int> &seq) {
+  auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
+  if (vec.end() != nth)
+    *nth; // no-warning
+}
+
+void bad_search_n(std::vector<int> &vec, std::vector<int> &seq) {
+  auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
+  *nth; // expected-warning{{Iterator accessed past its end}}
+}
+
+template <class InputIterator, class T>
+InputIterator nonStdFind(InputIterator first, InputIterator last,
+                         const T &val) {
+  for (auto i = first; i != last; ++i) {
+    if (*i == val) {
+      return i;
+    }
+  }
+  return last;
+}
+
+void good_non_std_find(std::vector<int> &vec, int e) {
+  auto first = nonStdFind(vec.begin(), vec.end(), e);
+  if (vec.end() != first)
+    *first; // no-warning
+}
+
+void bad_non_std_find(std::vector<int> &vec, int e) {
+  auto first = nonStdFind(vec.begin(), vec.end(), e);
+  *first; // expected-warning{{Iterator accessed past its end}}
+}
+
+void tricky(std::vector<int> &vec, int e) {
+  const auto first = vec.begin();
+  const auto comp1 = (first != vec.end()), comp2 = (first == vec.end());
+  if (comp1)
+    *first;
+}
+
+void loop(std::vector<int> &vec, int e) {
+  auto start = vec.begin();
+  while (true) {
+    auto item = std::find(start, vec.end(), e);
+    if (item == vec.end())
+      break;
+    *item;          // no-warning
+    start = ++item; // no-warning
+  }
+}