[Analyzer] Checker for non-determinism caused by sorting of pointer-like elements

[mgrang]

Summary

Added a new category of checkers for non-determinism. Added a checker for non-determinism
caused due to sorting containers with pointer-like elements.

[NoQ]

Hmm, this might make a good optin.* checker. Also i see that this is a pure AST-based checker; did you consider putting this into clang-tidy? Like, you shouldn't if you're not using clang-tidy yourself (it's a bit messy) but this is an option. Also we're actively using ASTMatchers in Analyzer checkers anyway these days because they're just shorter and easier to read and generally cool.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

91–100 ↗

(On Diff #159849)

This heuristic ("the argument of std::sort is a class whose first field is of pointer type") is quite wonky, do you have a plan on how to make it more precise?

[Szelethus]

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

91–100 ↗

(On Diff #159849)

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

Since RandomIt must satisfy RandomAccesIterator, maybe you could obtain the value type with std::iterator_traits<It>::value_type, and check whether it's a pointer type.

[whisperity]

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

88 ↗

(On Diff #159849)

Brrr... equals. StringRef has a == and != operator which accepts string literals on the other side, which would result in a more concise code.

Also, this heuristic can be applied without extra changes (apart from those mentioned by NoQ and might be mentioned later by others) to other sorting functions, such as std::stable_sort and std::stable_partition. Perhaps it would be worthy to enable checking those functions too.

[Szelethus]

I'm only a beginner, but here are some things that caught my eye. I really like the idea! :)

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

28 ↗

(On Diff #159849)

This comment holds little value.

46 ↗

(On Diff #159849)

// end of anonymous namespace

88 ↗

(On Diff #159849)

Maybe II->isStr("sort")?

93 ↗

(On Diff #159849)

Is there a reason for not directly acquiring the record declaration?

119 ↗

(On Diff #159849)

// end of anonymous namespace

test/Analysis/ptr-sort.cpp

1 ↗

(On Diff #159849)

Always run the core checkers too.
-analyzer-checker=core,alpha.nondeterminism.PointerSorting

[whisperity]

The basics of the heuristics look okay as comparing pointers from non-continuous block of memory is undefined, it would be worthy to check if no compiler warning (perhaps by specifying -W -Wall -Wextra -Weverything and various others of these enable-all flags!) is emitted if std::sort is instantiated for such a use case.

There is a chance for a serious false positive with the current approach! One thing which you should add as a FIXME, and implement in a follow-up patch. Using std::sort, std::unique and then erase is common technique for deduplicating a container (which in some cases [[https://stackoverflow.com/a/1041939/1428773 | might even be quicker than using, let's say std::set]]). In case my container contains arbitrary memory addresses (e.g. multiple things give me different stuff but might give the same thing multiple times) which I don't want to do things with more than once, I might use sort-unique-erase and the sort call will emit a report.

[george.karpenkov]

All the comments above + if anything, should use ASTMatchers.

[NoQ]

I'm only a beginner, but here are some things that caught my eye. I really like the idea! :)

Thanks, i appreciate help with reviews greatly.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

93 ↗

(On Diff #159849)

I suspect it's about typedefs. We usually use getCanonicalType() for this purpose.

test/Analysis/ptr-sort.cpp

1 ↗

(On Diff #159849)

This is a good discipline, but it's not very useful in case of AST-based checkers because they don't interact at all with each other.

[mgrang]

Thanks for all your review comments. I will try to address them soon.

Meanwhile, I have started an email thread on the general problem of writing checkers/sanitizers to detect non-deterministic behaviors. See http://lists.llvm.org/pipermail/llvm-dev/2018-August/125191.html.

The background for this is that I had already added support in LLVM to uncover 2 types of non-deterministic behaviors: iteration of unordered containers and sorting of keys with same values. But that is only for LLVM code, not user code. I now wanted to write checkers so that we could detect non-deterministic behavior in user code. It would be great if the reviewers here could chip-in with comments/suggestions for this. Thanks!

[NoQ]

I guess one of the things the analyzer could find with path-sensitive analysis is direct comparison of non-aliasing pointers. Not only this is non-deterministic, but there's a related problem that comparison for equality would always yield false and is therefore useless. However, there will be many false negatives because most of the time it's hard to figure out if pointers alias by looking at a small part of the program (a call stack of at most 3-4 functions in the middle of nowhere), as the analyzer does.

[mgrang]

Changed patch to use AST Matchers.

[mgrang]

This was my first time using AST matchers so it took me a while to figure out how exactly to get this right. clang-query helped a lot. Backspace seems to be a problem with clang-query though.

[mgrang]

Added checks for more algorithms: stable_sort, is_sorted, partial_sort, partition, stable_partition, nth_element.

[Szelethus]

I think testcases for non-class iterator objects would be valuable.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

72–76 ↗

(On Diff #161165)

I'm not a matcher-expert, but here we go:

As I understand it, you're matching iterator objects that wrap a pointer to pointer. Would it match this case?:

void fill(int **IntPointerArray);

int main() {
  int *IntPointerArray[20]; // or a simple int array
  fill(IntPointerArray);

  std::sort(IntPointerArray, IntPointerArray + 20);
}

int** is an RandomAccessIterator, but is not a CXXRecordDecl. As I mentioned earlier, it might be worth taking a look at hasType, and attempt to acquire value_type, as it is required for STL algorithms (it could be in a base class as well). value_type is also predefined through std::iterator_traits for pointer iterators like int**.

[Szelethus]

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

72–76 ↗

(On Diff #161165)

Also, this could lead to false positives, as iterators may store pointers to pointers that don't compare memory addresses. And it could maybe cause false negatives, if the value_type is a pointer type but the elements are stored in wrappers.

As I understand it.

[mgrang]

In D50488#1203876, @Szelethus wrote:

I think testcases for non-class iterator objects would be valuable.

Thanks @Szelethus. Yes, as you correctly pointed out this would not match non-class iterator objects.

This is my first time with ASTMatchers and I am not sure how to get the value_type from hasType (I don't see a matcher for value_types in ASTMatchers.h). Would I end up using a visitor for that? If yes, then maybe the entire check for pointer types needs to be done via visitors? Sorry for the newbie questions :)

[mgrang]

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

72–76 ↗

(On Diff #161165)

Yes, I will try to fine tune the heuristic in subsequent patches. I have noted the false-positives in the FIXME.

[Szelethus]

In D50488#1204655, @mgrang wrote:

This is my first time with ASTMatchers and I am not sure how to get the value_type from hasType (I don't see a matcher for value_types in ASTMatchers.h). Would I end up using a visitor for that? If yes, then maybe the entire check for pointer types needs to be done via visitors? Sorry for the newbie questions :)

I played around for a bit, my clang-query is a little out of date, but here's what I found: You can match typedefs with typedefDecl(), and using by typeAliasDecl(), and then add hasName("value_type") as a parameter. As to how to check whether a type has any of these, I'm a little unsure myself, but you could use hasDescendant, and narrow down the matches.

I'm not sure whether this checks inherited type declarations, and it sure doesn't check template specializations of std::iterator_traits, but it is a good start :) I'll revisit this when I have a little more time on my hand.

[whisperity]

Minor comments in-line, looking good on first glance.

I'm not sure if we discussed, has this checker been tried on some in-the-wild examples? To see if there are some real findings or crashes?
There is a good selection of projects here in this tool: https://github.com/Xazax-hun/csa-testbench.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

52 ↗

(On Diff #161165)

I generally have a concern about calling these thing "keys". How did you mean this? The file's top comment says elements.

81–87 ↗

(On Diff #161165)

Please order this listing.

102 ↗

(On Diff #161165)

emitDiagnostics takes a const T&. To prevent unnecessary copy operations in this iteration, you should also use const BoundNode &Match.

46 ↗

(On Diff #159849)

This comment can be marked as Done.

[whisperity]

@Szelethus clang-query seems to sometimes not include matcher functions that are perfectly available in the code... I recently had some issue with using isUserDefined(), it was available in my code, but clang-query always rejected it. Seems there isn't an automatic 1:1 mapping between the two.

@NoQ What is your decision about introducing a new NonDeterminism group? Should be, shan't be, is this name right?

[mgrang]

Addressed comments.

[mgrang]

In D50488#1222837, @whisperity wrote:

I'm not sure if we discussed, has this checker been tried on some in-the-wild examples? To see if there are some real findings or crashes?
There is a good selection of projects here in this tool: https://github.com/Xazax-hun/csa-testbench.

Thanks @whisperity for pointing me to the Static Analyzer tests. I will run the checker on it and report my findings here.

[mgrang]

In D50488#1207398, @Szelethus wrote:

In D50488#1204655, @mgrang wrote:

This is my first time with ASTMatchers and I am not sure how to get the value_type from hasType (I don't see a matcher for value_types in ASTMatchers.h). Would I end up using a visitor for that? If yes, then maybe the entire check for pointer types needs to be done via visitors? Sorry for the newbie questions :)

I played around for a bit, my clang-query is a little out of date, but here's what I found: You can match typedefs with typedefDecl(), and using by typeAliasDecl(), and then add hasName("value_type") as a parameter. As to how to check whether a type has any of these, I'm a little unsure myself, but you could use hasDescendant, and narrow down the matches.

I'm not sure whether this checks inherited type declarations, and it sure doesn't check template specializations of std::iterator_traits, but it is a good start :) I'll revisit this when I have a little more time on my hand.

I played around a lot with clang-query in the past week but I haven't been able to match typedefDecl with hasName("value_type"). Here are some matchers I tried:

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0,          stmt(hasDescendant(expr(hasType(typedefType(hasDeclaration(typedefNameDecl(hasName("value_type")))))))))))

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0,            hasDescendant(expr(hasType(typedefType(hasDeclaration(typedefDecl(matchesName(".*value.*"))))))))))

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0,            hasDescendant(declRefExpr(to(fieldDecl(hasName("value_type"))))))))))

Here's the AST dump for the IntPointerArray example:

FunctionDecl 0x639e958 <../../tst/s.cpp:5:1, line:10:1> line:5:5 main 'int ()'
`-CompoundStmt 0x639f1d0 <col:12, line:10:1>
  |-DeclStmt 0x639ead0 <line:6:3, col:27>
  | `-VarDecl 0x639ea70 <col:3, col:26> col:8 used IntPointerArray 'int *[20]'
  |-CallExpr 0x639ebd0 <line:7:3, col:23> 'void'
  | |-ImplicitCastExpr 0x639ebb8 <col:3> 'void (*)(int **)' <FunctionToPointerDecay>
  | | `-DeclRefExpr 0x639eb68 <col:3> 'void (int **)' lvalue Function 0x639e890 'fill' 'void (int **)'
  | `-ImplicitCastExpr 0x639ec00 <col:8> 'int **' <ArrayToPointerDecay>
  |   `-DeclRefExpr 0x639eb40 <col:8> 'int *[20]' lvalue Var 0x639ea70 'IntPointerArray' 'int *[20]'
  `-CallExpr 0x639f180 <line:9:3, col:50> 'void'
|-ImplicitCastExpr 0x639f168 <col:3, col:8> 'void (*)(int **, int **)' <FunctionToPointerDecay>
    | `-DeclRefExpr 0x639f0d0 <col:3, col:8> 'void (int **, int **)' lvalue Function 0x639efd0 'sort' 'void (int **, int **)' (FunctionTemplate 0x638dd18 'sort')
    |-ImplicitCastExpr 0x639f1b8 <col:13> 'int **' <ArrayToPointerDecay>
    | `-DeclRefExpr 0x639ec98 <col:13> 'int *[20]' lvalue Var 0x639ea70 'IntPointerArray' 'int *[20]'
    `-BinaryOperator 0x639ed20 <col:30, col:48> 'int **' '+'
      |-ImplicitCastExpr 0x639ed08 <col:30> 'int **' <ArrayToPointerDecay>
      | `-DeclRefExpr 0x639ecc0 <col:30> 'int *[20]' lvalue Var 0x639ea70 'IntPointerArray' 'int *[20]'
      `-IntegerLiteral 0x639ece8 <col:48> 'int' 20

[whisperity]

Make sure you use only the C++ projects like BitCoin, LLVM/Clang, ProtoBuf and such from the Xazax CSA Test suite because this checker is not really applicable to C projects.

Generally I like the idea (personally I've ran into a similar issue to ordering of sets in Java missed and on another OS we failed the tests where they tried to stringify elements and compare the output...) very much, this is one of those subleties you can really miss when writing and when reviewing code, and it will only bite you in the ass months down the line.

I think I'll summon @martong here, ASTMatchers are not my fortée, but he has been tinkering with them much recently.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

108–110 ↗

(On Diff #163876)

Speaking of not being applicable to C code, I think this snippet here should allow you to skip running the checker if you are not on a C++ file:

if (!Mgr.getLangOpts().CPlusPlus)
      return;

[martong]

From this little information I have hear are my thoughts:

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0, hasDescendant(declRefExpr(to(fieldDecl(hasName("value_type"))))))))))

I think this is a good direction, but keep in mind that value_type is a typedef, thus you should use the typedefNameDecl matcher instead of the fieldDecl.

(Also if I understand correctly then this is good that this matcher does not match in case of the intPointerArray example, because the array does not have any member at all ...)

[mgrang]

In D50488#1224480, @martong wrote:

From this little information I have hear are my thoughts:

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0, hasDescendant(declRefExpr(to(fieldDecl(hasName("value_type"))))))))))

I think this is a good direction, but keep in mind that value_type is a typedef, thus you should use the typedefNameDecl matcher instead of the fieldDecl.

Thanks @martong Yes, I tried another matcher with typedefNameDecl which also did not match:

match callExpr(allOf (callee(functionDecl(hasName("std::sort"))), hasArgument(0, stmt(hasDescendant(expr(hasType(typedefType(hasDeclaration(typedefNameDecl(hasName("value_type")))))))))))

(Also if I understand correctly then this is good that this matcher does not match in case of the intPointerArray example, because the array does not have any member at all ...)

How then do you think I should try matching the IntPointerArray example? I am now leaning towards not doing this via AST Matchers as I am not sure if I can easily match more complex cases.

[mgrang]

Enabled checker only for C++.

[Szelethus]

How then do you think I should try matching the IntPointerArray example? I am now leaning towards not doing this via AST Matchers as I am not sure if I can easily match more complex cases.

I've sadly reached the end of my knowledge on AST based analysis, but just to throw this in there, are you aware of this amazing guide about the static analyzer? https://github.com/haoNoQ/clang-analyzer-guide/releases There are a couple sections I believe could help you.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

108–110 ↗

(On Diff #163876)

Actually, I'm very much shooting in the dark here, but wouldn't this work with objective C++?

[george.karpenkov]

Why explicitly skip C projects? We would not be able to match std::X functions anyway.

[george.karpenkov]

The code looks fine to me; @mgrang What evaluation steps have you performed? You note there are a few notable false positives, do you have ideas for suppressing those?

[whisperity]

In D50488#1225064, @george.karpenkov wrote:

Why explicitly skip C projects? We would not be able to match std::X functions anyway.

Why spend time constructing matchers and running on the AST when we are sure that generating any result is impossible? Skipping the entire useless traversal of the tree can end up saving precious execution time that should not be overlooked.

[NoQ]

I'm generally fine with landing the patch as long as the overall direction is chosen (and be moved towards) for how to safely identify the non-deterministic iterators (my previous inline question). This has to be addressed before we move out of alpha, but i believe we should pick at least some direction now, because i've very little idea about how to actually do that safely, and i'm worried that we'll get stuck in a dead end here.

Package name sounds good.

test/Analysis/ptr-sort.cpp

1 ↗

(On Diff #164086)

There's no need to test with -analyzer-output=text for a syntactic check, because you're not checking path diagnostics. It'll make tests tidier by not forcing you to test notes.

If you ever decide to add extra "note" pieces to your checker, they'll be shown in the default output anyway.

[whisperity]

Hey @mgrang! Let's see some results on some projects and answer NoQ's comment, then I think we can put this in for all the world to see.

[mgrang]

In D50488#1246321, @whisperity wrote:

Hey @mgrang! Let's see some results on some projects and answer NoQ's comment, then I think we can put this in for all the world to see.

Was busy with CppCon 2018 in the past couple of weeks so could not work on this. Hope to test this out soon.

[george.karpenkov]

I'm marking it as "needs changes" for now -- the idea seems reasonable, but it's hard to tell without a thorough evaluation on at least a few codebases.
Additionally, we should figure out a checker group for this - if "alpha" means "work in progress", then it should be under something else, like "linting" or similar.

[mgrang]

Reviving this now that I have some cycles to work on this.

So I tried running this on csa-testbench projects but I didn't have much success. I always run into a bunch of build/env related errors:

python run_experiments.py --config myconfig.json

15:05:20 [libcxx] Checking out project... 
[ERROR] Unknown option: json

15:05:22 [libcxx] LOC: ?.
15:05:22 [libcxx] Generating build log... 
15:05:22 [libcxx_master] Analyzing project... 
[ERROR] Traceback (most recent call last):
  File "/local/mnt/workspace/mgrang/comm_analyzer/CodeChecker/cc_bin/CodeChecker.py", line 20, in <module>
    from shared.ttypes import RequestFailed
ImportError: No module named shared.ttypes

Not sure why it tries to invoke cc_bin/CodeChecker.py. There's already a bin/CodeChecker.py.

I installed CodeChecker and various other dependencies mentioned in the README. Here's what myconfig.json looks like:

{
  "projects": [
    {
      "url": "git://github.com/chapuni/libcxx.git",
      "name": "libcxx",
      "clang_sa_args": "--analyze -Xanalyzer -analyzer-checker=alpha.nondeterminism.PointerSorting",
      "clang_path": "path/to/llvm/install/bin",
      "binary_dir": "build"
    },
    {
      "name": "bitcoin",
      "url": "https://github.com/bitcoin/bitcoin.git",
      "tag": "v0.15.1",
      "clang_sa_args": "--analyze -Xanalyzer -analyzer-checker=alpha.nondeterminism.PointerSorting",
      "clang_path": "path/to/llvm/install/bin",
      "binary_dir": "build"
    },
    {
      "name": "xerces-c",
      "url": "https://github.com/apache/xerces-c.git",
      "prepared": true,
      "clang_sa_args": "--analyze -Xanalyzer -analyzer-checker=alpha.nondeterminism.PointerSorting",
      "clang_path": "path/to/llvm/install/bin",
      "binary_dir": "build"
    }
  ],

  "CodeChecker": {
    "url": "http://localhost:8001/Default",
    "analyze_args": "",
    "store_args": ""
  }
}

[Szelethus]

@rnkovacs and @xazax.hun might be able to help with that?

[xazax.hun]

In D50488#1395483, @mgrang wrote:

Reviving this now that I have some cycles to work on this.

So I tried running this on csa-testbench projects but I didn't have much success. I always run into a bunch of build/env related errors:

python run_experiments.py --config myconfig.json

15:05:20 [libcxx] Checking out project... 
[ERROR] Unknown option: json

15:05:22 [libcxx] LOC: ?.
15:05:22 [libcxx] Generating build log... 
15:05:22 [libcxx_master] Analyzing project... 
[ERROR] Traceback (most recent call last):
  File "/local/mnt/workspace/mgrang/comm_analyzer/CodeChecker/cc_bin/CodeChecker.py", line 20, in <module>
    from shared.ttypes import RequestFailed
ImportError: No module named shared.ttypes

Hi!

Sorry for the late response. Does CodeChecker work for you (when not using the testbench)?
I think one of the most common reason for such errors is when we do not source the virtualenv of CodeChecker so the dependencies are not available.

[mgrang]

In D50488#1397721, @xazax.hun wrote:

In D50488#1395483, @mgrang wrote:

Reviving this now that I have some cycles to work on this.

So I tried running this on csa-testbench projects but I didn't have much success. I always run into a bunch of build/env related errors:

python run_experiments.py --config myconfig.json

15:05:20 [libcxx] Checking out project... 
[ERROR] Unknown option: json

15:05:22 [libcxx] LOC: ?.
15:05:22 [libcxx] Generating build log... 
15:05:22 [libcxx_master] Analyzing project... 
[ERROR] Traceback (most recent call last):
  File "/local/mnt/workspace/mgrang/comm_analyzer/CodeChecker/cc_bin/CodeChecker.py", line 20, in <module>
    from shared.ttypes import RequestFailed
ImportError: No module named shared.ttypes

Hi!

Sorry for the late response. Does CodeChecker work for you (when not using the testbench)?
I think one of the most common reason for such errors is when we do not source the virtualenv of CodeChecker so the dependencies are not available.

[mgrang]

I guess I hadn't sourced the CodeChecker venv correctly. Now that I did source it and started the CodeChecker server I seem to be progressing. The error I get now is compiler related (which I will dig into).

12:51:35 [bitcoin] Checking out project... 
[ERROR] Unknown option: json

[ERROR] configure: error: in `csa-testbench/projects/bitcoin':
configure: error: C++ compiler cannot create executables
See `config.log' for more details

Should I be worried about the "[ERROR] Unknown option: json" message?

[mgrang]

The error I now get is:

clang is not able to compile a simple test program.
/usr/bin/ld: unrecognised emulation mode: armelf_linux_eabi
  Supported emulations: elf_x86_64 elf32_x86_64 elf_i386 elf_iamcu i386linux
  elf_l1om elf_k1om i386pep i386pe

This is because I need to pass the correct -target and -L options to config. I see that there is a configure_command option that can be set. However, different projects use different build systems (make, cmake, bake, etc). How do we then pass flags to their respective configures?

[mgrang]

I hacked around the run_experiments.py to set CMAKE_C_FLAGS and now I see the following error in stats.html. Note: I see the same error with an existing checker like PointerArithmChecker. And I do not hit this assert when I run the checker outside of csa-testbench.

Assertion `CheckerTags.count(tag) != 0 && "Requested checker is not registered! Maybe you should add it as a " "dependency in Checkers.td?"'

Here's my config file:

{
  "projects": [
    {
      "name": "TinyXML2",
      "url": "https://github.com/leethomason/tinyxml2.git",
      "clang_sa_args": "-target x86_64-linux-gnu -L /usr/lib/x86_64-linux-gnu -B /usr/lib/x86_64-linux-gnu -B /usr/lib/gcc/x86_64-linux-gnu/5 -L /usr/lib/gcc/x86_64-linux-gnu/5 --analyze -Xanalyzer -analyzer-checker=core -Xanalyzer -analyzer-checker=alpha.core.PointerArithm -Xclang -analyzer-stats",
      "clang_path": "path/install/bin",
      "binary_dir": "build"
    }
  ],

  "CodeChecker": {
    "url": "http://localhost:8001/Default",
    "analyze_args": "",
    "store_args": ""
  }
}

[whisperity]

Yeah, it seems upstream has moved away due to @Szelethus' implementation of a much more manageable "checker dependency" system. You most likely will have to rebase your patch first, then check what you missed which got added to other merged, existing checkers.

[mgrang]

In D50488#1400823, @whisperity wrote:

Yeah, it seems upstream has moved away due to @Szelethus' implementation of a much more manageable "checker dependency" system. You most likely will have to rebase your patch first, then check what you missed which got added to other merged, existing checkers.

Yes, I see that D55429, D54438 added a new dependency field for checkers. However, I see that not all checkers need/have that field. In this case, shouldn't providing a ento::shouldRegisterPointerSortingChecker function which returns true be enough to register the checker?
Moreover, as I said I hit this assert only when invoking the checker via csa-testbench. Outside that it seems to work fine. For example, my unit test Analysis/ptr-sort.cpp passes.

[Szelethus]

In D50488#1402699, @mgrang wrote:

In D50488#1400823, @whisperity wrote:

Yeah, it seems upstream has moved away due to @Szelethus' implementation of a much more manageable "checker dependency" system. You most likely will have to rebase your patch first, then check what you missed which got added to other merged, existing checkers.

Moreover, as I said I hit this assert only when invoking the checker via csa-testbench. Outside that it seems to work fine. For example, my unit test Analysis/ptr-sort.cpp passes.

It's because it invokes CodeChecker, which by default enables valist.Uninitialized, but not ValistBase. Do you have assert failures after my hotfix?

Yes, I see that D55429, D54438 added a new dependency field for checkers. However, I see that not all checkers need/have that field. In this case, shouldn't providing a ento::shouldRegisterPointerSortingChecker function which returns true be enough to register the checker?

It is enough, and this really is not documented properly. There is a revision to solve this problem here: D58065. I guess your input, as someone who didn't participate in the checker dependency related patch reviews would be invaluable, in terms of whether my description is understandable enough.

Edit: and yes, the Dependency field in Checkers.td is completely optional. The shouldRegister function is a tool to prevent checkers being enabled for a particular language -- some C++ checkers, for example, crash when a code is being analyzed according to the C standard.

[mgrang]

It's because it invokes CodeChecker, which by default enables valist.Uninitialized, but not ValistBase. Do you have assert failures after my hotfix?

@Szelethus Thanks. I run into this assert when run through CodeChecker:

Assertion `CheckerTags.count(tag) != 0 && "Requested checker is not registered! Maybe you should add it as a " "dependency in Checkers.td?"'

Is there a workaround?

[mgrang]

Also I don't see the helptext for PointerSorting when I run:

clang -cc1 -analyzer-checker-help | grep Pointer

  alpha.core.PointerArithm        Check for pointer arithmetic on locations other than array elements
  alpha.core.PointerSub           Check for pointer subtractions on two pointers pointing to different memory chunks
  alpha.nondeterminism.PointerSorting
  cplusplus.InnerPointer          Check for inner pointers of C++ containers used after re/deallocation

[mgrang]

There is a revision to solve this problem here: D58065. I guess your input, as someone who didn't participate in the checker dependency related patch reviews would be invaluable, in terms of whether my description is understandable enough.

Thanks. I took a look at the documentation and it looks fine to me (modulo the comments from other reviewers and a couple of minor typos). I feel the csa-testbench documentation (https://github.com/Xazax-hun/csa-testbench) is very minimal and does not document a lot of intricacies which I had to figure out by trial-and-error.

[Szelethus]

In D50488#1403197, @mgrang wrote:

It's because it invokes CodeChecker, which by default enables valist.Uninitialized, but not ValistBase. Do you have assert failures after my hotfix?

@Szelethus Thanks. I run into this assert when run through CodeChecker:

Assertion `CheckerTags.count(tag) != 0 && "Requested checker is not registered! Maybe you should add it as a " "dependency in Checkers.td?"'

Is there a workaround?

Uhh, I'm afraid the only way out is to actually fix the problem :) couple questions:

1. Are you *sure* that you rebased to rC354235 (which is the hotfix I mentioned), CodeChecker runs *that* clang when the assert failure happens?
2. Can you provide a stacktrace? Luckily, that would for sure point me to the problematic checker.

In D50488#1403199, @mgrang wrote:

Also I don't see the helptext for PointerSorting when I run:

clang -cc1 -analyzer-checker-help | grep Pointer

  alpha.core.PointerArithm        Check for pointer arithmetic on locations other than array elements
  alpha.core.PointerSub           Check for pointer subtractions on two pointers pointing to different memory chunks
  alpha.nondeterminism.PointerSorting
  cplusplus.InnerPointer          Check for inner pointers of C++ containers used after re/deallocation

How about clang -cc1 -analyzer-checker-help | grep Pointer -A3? There could be a linebreak after the ckecker's name (raises the question though whether it should be there).

In D50488#1403212, @mgrang wrote:

There is a revision to solve this problem here: D58065. I guess your input, as someone who didn't participate in the checker dependency related patch reviews would be invaluable, in terms of whether my description is understandable enough.

Thanks. I took a look at the documentation and it looks fine to me (modulo the comments from other reviewers and a couple of minor typos). I feel the csa-testbench documentation (https://github.com/Xazax-hun/csa-testbench) is very minimal and does not document a lot of intricacies which I had to figure out by trial-and-error.

Due to an upcoming conference, I didn't bother with it much, i just used CodeChecker on its own, which is fairly well documented.
I'm trying to move my checker out of alpha, and my testing goes as follows:

1. Clone LLVM+Clang, cppcheck, rtags, bitcoin, xerces (you could throw in vim, tmux, as your checker isnt C++ exclusive (see edit), or whatever else)
2. Create compile_commands.json either with CMake (-DCANE_GENERATE_COMPILE_COMMANDS, or smt similar), or CodeChecker log
3. CodeChecker analyze projects, paying attention to not forgetting the CodeChecker flag --verbose debug_analyzer (and enabling your checker ofc), and piping the output to a file
4. Create a CodeChecker server, CodeChecker store the results, and stare at the web gui for hours. Its very pretty btw ;)

Csa-testbench is a work in progress, so I guess you can expect more in the future :)

Thanks for your work, even through a few annoyances, very much appreciated!

Edit: Since your checker is C++ exclusive, please return true only if LangOpts.CPlusPlus is true in the shouldRegister function. Didn't catch my eye at first.

[mgrang]

In D50488#1403653, @Szelethus wrote:

In D50488#1403197, @mgrang wrote:

It's because it invokes CodeChecker, which by default enables valist.Uninitialized, but not ValistBase. Do you have assert failures after my hotfix?

@Szelethus Thanks. I run into this assert when run through CodeChecker:

Assertion `CheckerTags.count(tag) != 0 && "Requested checker is not registered! Maybe you should add it as a " "dependency in Checkers.td?"'

Is there a workaround?

Uhh, I'm afraid the only way out is to actually fix the problem :) couple questions:

1. Are you *sure* that you rebased to rC354235 (which is the hotfix I mentioned), CodeChecker runs *that* clang when the assert failure happens?

I guess, I totally missed your hotfix. After sync'ing to the latest sources I no longer hit the assert. Thanks!

2. Can you provide a stacktrace? Luckily, that would for sure point me to the problematic checker.

In D50488#1403199, @mgrang wrote:

Also I don't see the helptext for PointerSorting when I run:

clang -cc1 -analyzer-checker-help | grep Pointer

  alpha.core.PointerArithm        Check for pointer arithmetic on locations other than array elements
  alpha.core.PointerSub           Check for pointer subtractions on two pointers pointing to different memory chunks
  alpha.nondeterminism.PointerSorting
  cplusplus.InnerPointer          Check for inner pointers of C++ containers used after re/deallocation

How about clang -cc1 -analyzer-checker-help | grep Pointer -A3? There could be a linebreak after the ckecker's name (raises the question though whether it should be there).

Yep, line break it was. I see the help text with -A1.

In D50488#1403212, @mgrang wrote:

There is a revision to solve this problem here: D58065. I guess your input, as someone who didn't participate in the checker dependency related patch reviews would be invaluable, in terms of whether my description is understandable enough.

Thanks. I took a look at the documentation and it looks fine to me (modulo the comments from other reviewers and a couple of minor typos). I feel the csa-testbench documentation (https://github.com/Xazax-hun/csa-testbench) is very minimal and does not document a lot of intricacies which I had to figure out by trial-and-error.

Due to an upcoming conference, I didn't bother with it much, i just used CodeChecker on its own, which is fairly well documented.
I'm trying to move my checker out of alpha, and my testing goes as follows:

1. Clone LLVM+Clang, cppcheck, rtags, bitcoin, xerces (you could throw in vim, tmux, as your checker isnt C++ exclusive (see edit), or whatever else)
2. Create compile_commands.json either with CMake (-DCANE_GENERATE_COMPILE_COMMANDS, or smt similar), or CodeChecker log
3. CodeChecker analyze projects, paying attention to not forgetting the CodeChecker flag --verbose debug_analyzer (and enabling your checker ofc), and piping the output to a file
4. Create a CodeChecker server, CodeChecker store the results, and stare at the web gui for hours. Its very pretty btw ;)

Csa-testbench is a work in progress, so I guess you can expect more in the future :)

Thanks for your work, even through a few annoyances, very much appreciated!

Edit: Since your checker is C++ exclusive, please return true only if LangOpts.CPlusPlus is true in the shouldRegister function. Didn't catch my eye at first.

Done.

[mgrang]

So I was able compile a couple of C++ code bases through csa-testbench. I built cppcheck and tinyxml2 without any problems. cppcheck has one invocation std::sort but the keys are not pointers whereas tinyxml2 does not use std::sort. I tried bitcoin, rtags, xerces but run into a lot of configure/build errors.

[mgrang]

In D50488#1405094, @mgrang wrote:

So I was able compile a couple of C++ code bases through csa-testbench. I built cppcheck and tinyxml2 without any problems. cppcheck has one invocation std::sort but the keys are not pointers whereas tinyxml2 does not use std::sort. I tried bitcoin, rtags, xerces but run into a lot of configure/build errors.

@Szelethus Are you able to build bitcoin, xerces, etc? I seem to hit "Could not link against boost_filesystem" errors with bitcoin. I have installed dependencies mentioned in https://stackoverflow.com/questions/9132335/configure-error-could-not-link-against-boost-system/47773206 and https://github.com/bitcoin/bitcoin/issues/8749.

[Charusso]

bitcoin:

sudo apt-get install build-essential libtool autotools-dev automake pkg-config libssl-dev libevent-dev bsdmainutils python3 libboost-all-dev software-properties-common libminiupnpc-dev libzmq3-dev libqt5gui5 libqt5core5a libqt5dbus5 qttools5-dev qttools5-dev-tools libprotobuf-dev protobuf-compiler
sudo add-apt-repository ppa:bitcoin/bitcoin
sudo apt-get update
sudo apt-get install libdb4.8-dev libdb4.8++-dev

git clone https://github.com/bitcoin/bitcoin.git
cd bitcoin

./autogen.sh
./configure
CodeChecker log -b "make -j13" -o compile_commands.json

xerces:

wget http://www-eu.apache.org/dist//xerces/c/3/sources/xerces-c-3.2.2.tar.gz
tar xf xerces-c-3.2.2.tar.gz
mv xerces-c-3.2.2 xerces
rm xerces-c-3.2.2.tar.gz
cd xerces

./configure
CodeChecker log -b "make -j13" -o compile_commands.json

where -j13 means 13 threads.

[mgrang]

In D50488#1407695, @Charusso wrote:

bitcoin:

sudo apt-get install build-essential libtool autotools-dev automake pkg-config libssl-dev libevent-dev bsdmainutils python3 libboost-all-dev software-properties-common libminiupnpc-dev libzmq3-dev libqt5gui5 libqt5core5a libqt5dbus5 qttools5-dev qttools5-dev-tools libprotobuf-dev protobuf-compiler
sudo add-apt-repository ppa:bitcoin/bitcoin
sudo apt-get update
sudo apt-get install libdb4.8-dev libdb4.8++-dev

git clone https://github.com/bitcoin/bitcoin.git
cd bitcoin

./autogen.sh
./configure
CodeChecker log -b "make -j13" -o compile_commands.json

xerces:

wget http://www-eu.apache.org/dist//xerces/c/3/sources/xerces-c-3.2.2.tar.gz
tar xf xerces-c-3.2.2.tar.gz
mv xerces-c-3.2.2 xerces
rm xerces-c-3.2.2.tar.gz
cd xerces

./configure
CodeChecker log -b "make -j13" -o compile_commands.json

where -j13 means 13 threads.

Thanks @Charusso . I have already tried these steps.

By running just ./configure I get this error:

configure: error: cannot figure out how to use std::atomic

Instead, this is the configure command I use for bitcoin:

./configure --disable-wallet CFLAGS='-target x86_64-linux-gnu -L /usr/lib/x86_64-linux-gnu -B /usr/lib/x86_64-linux-gnu -B /usr/lib/gcc/x86_64-linux-gnu/5 -L /usr/lib/gcc/x86_64-linux-gnu/5 -I /usr/include/c++/5 -I /usr/include/x86_64-linux-gnu/c++/5' CXXFLAGS='-target x86_64-linux-gnu -L /usr/lib/x86_64-linux-gnu -B /usr/lib/x86_64-linux-gnu -B /usr/lib/gcc/x86_64-linux-gnu/5 -L /usr/lib/gcc/x86_64-linux-gnu/5 -I /usr/include/c++/5 -I /usr/include/x86_64-linux-gnu/c++/5'

And then I hit this:

configure: error: Could not link against boost_filesystem !

[Szelethus]

In D50488#1405094, @mgrang wrote:

So I was able compile a couple of C++ code bases through csa-testbench. I built cppcheck and tinyxml2 without any problems. cppcheck has one invocation std::sort but the keys are not pointers whereas tinyxml2 does not use std::sort. I tried bitcoin, rtags, xerces but run into a lot of configure/build errors.

Thats great. How about LLVM+Clang? That'll be a pain in the butt to analyze, but is pretty great for testing. Also, did you clone rtags with the git option --recursive?

include/clang/StaticAnalyzer/Checkers/Checkers.td

97 ↗

(On Diff #187695)

Hmmm, okay, so your checker ks C++ exclusive I belive? How about making this checker reside in alpha.cplusplus? Rgard this one as more of a question.

lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

1 ↗

(On Diff #187695)

Missing emacs thingie here?

30 ↗

(On Diff #187695)

I heard somewhere that LLVM::StringLiteral is used for global constexpr strings? Anyway, constexpr could be added here if I'm wrong sbout that :)

110 ↗

(On Diff #187695)

This is no longer needed, your checker wont be registered if the shouldRegister function returns false.

[Szelethus]

But, as a work-in-progress alpha checker, the direction is set and looks great. Please let @NoQ have the final say.

[mgrang]

include/clang/StaticAnalyzer/Checkers/Checkers.td

97 ↗

(On Diff #187695)

This particular checker is C++ exclusive. The reason behind creating a new non-determinism category was so that we could add more language-agnostic checkers for non-determinism in future.

[mgrang]

In D50488#1407884, @Szelethus wrote:

In D50488#1405094, @mgrang wrote:

So I was able compile a couple of C++ code bases through csa-testbench. I built cppcheck and tinyxml2 without any problems. cppcheck has one invocation std::sort but the keys are not pointers whereas tinyxml2 does not use std::sort. I tried bitcoin, rtags, xerces but run into a lot of configure/build errors.

Thats great. How about LLVM+Clang? That'll be a pain in the butt to analyze, but is pretty great for testing. Also, did you clone rtags with the git option --recursive?

LLVM does not directly use std::sort. It calls llvm::sort which in-turn calls std::sort (but it does have std::stable_sort, etc). However, I run into a host of errors while building LLVM inside csa-testbench. Maybe, once this patch lands, I could use llvm as a bootstrap stage1 compiler with this checker enabled.

Also, did you clone rtags with the git option --recursive?

Yes, I followed the build instructions from https://github.com/Andersbakken/rtags. But run into these errors:

./configure //this invokes "cmake" "." -DCMAKE_EXPORT_COMPILE_COMMANDS=1
  The compiler uses a libstdc++ without c++11 regex support.

./configure --clang-cxxflags '-std=c++11' //this invokes "cmake" "." -DCMAKE_EXPORT_COMPILE_COMMANDS=1 -DLIBCLANG_CXXFLAGS="-std=c++11"
  It's likely that the include file <clang-c/Index.h> could not be found!

I tried installing libclang-dev, libclang-3.8-dev, libclang-6.0-dev as well as adding -I include paths for clang-c to configure but I am not able to go past the above error.

[mgrang]

In D50488#1407975, @Szelethus wrote:

But, as a work-in-progress alpha checker, the direction is set and looks great. Please let @NoQ have the final say.

Thanks a lot @Szelethus! I will wait for @NoQ 's comments.

[mgrang]

In D50488#1409565, @mgrang wrote:

In D50488#1407975, @Szelethus wrote:

But, as a work-in-progress alpha checker, the direction is set and looks great. Please let @NoQ have the final say.

Thanks a lot @Szelethus! I will wait for @NoQ 's comments.

@NoQ Could you please review this patch?

[mgrang]

@NoQ Ping 2 for reviews please.

[NoQ]

Ok, thanks, sounds good! Let's land and see where it goes.

test/Analysis/ptr-sort.cpp

4–25 ↗

(On Diff #188232)

Please feel free to put these directly into system-header-simulator-cxx.h.

cfe/trunk/docs/analyzer/checkers.rst

 
 
 .. code-block:: c
 
  void test() {
    int y = strlen((char *)&test); // warn
  }
 
+alpha.nondeterminism.PointerSorting (C++)
+"""""""""""""""""""""""""
+Check for non-determinism caused by sorting of pointers.
+
+.. code-block:: c
+
+ void test() {
+  int a = 1, b = 2;
+  std::vector<int *> V = {&a, &b};
+  std::sort(V.begin(), V.end()); // warn
+ }
+
 
 Debug Checkers
 ---------------
 
 .. _debug-checkers:
 
 
 debug

cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td

 // intended for API modeling that is not controlled by the target triple.
 def APIModeling : Package<"apiModeling">;
 def GoogleAPIModeling : Package<"google">, ParentPackage<APIModeling>;
 
 def Debug : Package<"debug">;
 
 def CloneDetectionAlpha : Package<"clone">, ParentPackage<Alpha>;
 
+def NonDeterminismAlpha : Package<"nondeterminism">, ParentPackage<Alpha>;
+
 //===----------------------------------------------------------------------===//
 // Core Checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Core in {
 
 def DereferenceChecker : Checker<"NullDereference">,
   HelpText<"Check for dereferences of null pointers">,

 
 let ParentPackage = PortabilityOptIn in {
 
 def UnixAPIPortabilityChecker : Checker<"UnixAPI">,
   HelpText<"Finds implementation-defined behavior in UNIX/Posix functions">,
   Documentation<NotDocumented>;
 
 } // end optin.portability
+
+//===----------------------------------------------------------------------===//
+// NonDeterminism checkers.
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = NonDeterminismAlpha in {
+
+def PointerSortingChecker : Checker<"PointerSorting">,
+  HelpText<"Check for non-determinism caused by sorting of pointers">,
+  Documentation<HasDocumentation>;
+
+} // end alpha.nondeterminism

cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   ObjCMissingSuperCallChecker.cpp
   ObjCPropertyChecker.cpp
   ObjCSelfInitChecker.cpp
   ObjCSuperDeallocChecker.cpp
   ObjCUnusedIVarsChecker.cpp
   OSObjectCStyleCast.cpp
   PaddingChecker.cpp
   PointerArithChecker.cpp
+  PointerSortingChecker.cpp
   PointerSubChecker.cpp
   PthreadLockChecker.cpp
   RetainCountChecker/RetainCountChecker.cpp
   RetainCountChecker/RetainCountDiagnostics.cpp
   ReturnPointerRangeChecker.cpp
   ReturnUndefChecker.cpp
   RunLoopAutoreleaseLeakChecker.cpp
   SimpleStreamChecker.cpp

cfe/trunk/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp

+//=== PointerSortingChecker.cpp - Pointer sorting checker ------*- C++ -*--===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines PointerSortingChecker which checks for non-determinism
+// caused due to sorting containers with pointer-like elements.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+using namespace clang;
+using namespace ento;
+using namespace ast_matchers;
+
+namespace {
+
+// ID of a node at which the diagnostic would be emitted.
+constexpr llvm::StringLiteral WarnAtNode = "sort";
+
+class PointerSortingChecker : public Checker<check::ASTCodeBody> {
+public:
+  void checkASTCodeBody(const Decl *D,
+                        AnalysisManager &AM,
+                        BugReporter &BR) const;
+};
+
+static void emitDiagnostics(const BoundNodes &Match, const Decl *D,
+                            BugReporter &BR, AnalysisManager &AM,
+                            const PointerSortingChecker *Checker) {
+  auto *ADC = AM.getAnalysisDeclContext(D);
+
+  const auto *MarkedStmt = Match.getNodeAs<CallExpr>(WarnAtNode);
+  assert(MarkedStmt);
+
+  auto Range = MarkedStmt->getSourceRange();
+  auto Location = PathDiagnosticLocation::createBegin(MarkedStmt,
+                                                      BR.getSourceManager(),
+                                                      ADC);
+  std::string Diagnostics;
+  llvm::raw_string_ostream OS(Diagnostics);
+  OS << "Sorting pointer-like elements "
+     << "can result in non-deterministic ordering";
+
+  BR.EmitBasicReport(ADC->getDecl(), Checker,
+                     "Sorting of pointer-like elements", "Non-determinism",
+                     OS.str(), Location, Range);
+}
+
+auto callsName(const char *FunctionName) -> decltype(callee(functionDecl())) {
+  return callee(functionDecl(hasName(FunctionName)));
+}
+
+// FIXME: Currently we simply check if std::sort is used with pointer-like
+// elements. This approach can have a big false positive rate. Using std::sort,
+// std::unique and then erase is common technique for deduplicating a container
+// (which in some cases might even be quicker than using, let's say std::set).
+// In case a container contains arbitrary memory addresses (e.g. multiple
+// things give different stuff but might give the same thing multiple times)
+// which we don't want to do things with more than once, we might use
+// sort-unique-erase and the sort call will emit a report.
+auto matchSortWithPointers() -> decltype(decl()) {
+  // Match any of these function calls.
+  auto SortFuncM = anyOf(
+                     callsName("std::is_sorted"),
+                     callsName("std::nth_element"),
+                     callsName("std::partial_sort"),
+                     callsName("std::partition"),
+                     callsName("std::sort"),
+                     callsName("std::stable_partition"),
+                     callsName("std::stable_sort")
+                    );
+
+  // Match only if the container has pointer-type elements.
+  auto IteratesPointerEltsM = hasArgument(0,
+                                hasType(cxxRecordDecl(has(
+                                  fieldDecl(hasType(hasCanonicalType(
+                                    pointsTo(hasCanonicalType(pointerType()))
+                                  )))
+                              ))));
+
+  auto PointerSortM = stmt(callExpr(allOf(SortFuncM, IteratesPointerEltsM))
+                      ).bind(WarnAtNode);
+
+  return decl(forEachDescendant(PointerSortM));
+}
+
+void PointerSortingChecker::checkASTCodeBody(const Decl *D,
+                                             AnalysisManager &AM,
+                                             BugReporter &BR) const {
+  auto MatcherM = matchSortWithPointers();
+
+  auto Matches = match(MatcherM, *D, AM.getASTContext());
+  for (const auto &Match : Matches)
+    emitDiagnostics(Match, D, BR, AM, this);
+}
+
+} // end of anonymous namespace
+
+void ento::registerPointerSortingChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<PointerSortingChecker>();
+}
+
+bool ento::shouldRegisterPointerSortingChecker(const LangOptions &LO) {
+  return LO.CPlusPlus;
+}

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

 namespace __cxxabiv1 {
 extern "C" {
 extern char *__cxa_demangle(const char *mangled_name,
                             char *output_buffer,
                             size_t *length,
                             int *status);
 }}
 namespace abi = __cxxabiv1;
+
+namespace std {
+  template<class ForwardIt>
+  bool is_sorted(ForwardIt first, ForwardIt last);
+
+  template <class RandomIt>
+  void nth_element(RandomIt first, RandomIt nth, RandomIt last);
+
+  template<class RandomIt>
+  void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
+
+  template<class RandomIt>
+  void sort (RandomIt first, RandomIt last);
+
+  template<class RandomIt>
+  void stable_sort(RandomIt first, RandomIt last);
+
+  template<class BidirIt, class UnaryPredicate>
+  BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p);
+
+  template<class BidirIt, class UnaryPredicate>
+  BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);
+}

cfe/trunk/test/Analysis/ptr-sort.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.nondeterminism.PointerSorting %s -analyzer-output=text -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+bool f (int x) { return true; }
+bool g (int *x) { return true; }
+
+void PointerSorting() {
+  int a = 1, b = 2, c = 3;
+  std::vector<int> V1 = {a, b};
+  std::vector<int *> V2 = {&a, &b};
+
+  std::is_sorted(V1.begin(), V1.end());                    // no-warning
+  std::nth_element(V1.begin(), V1.begin() + 1, V1.end());  // no-warning
+  std::partial_sort(V1.begin(), V1.begin() + 1, V1.end()); // no-warning
+  std::sort(V1.begin(), V1.end());                         // no-warning
+  std::stable_sort(V1.begin(), V1.end());                  // no-warning
+  std::partition(V1.begin(), V1.end(), f);                 // no-warning
+  std::stable_partition(V1.begin(), V1.end(), g);          // no-warning
+
+  std::is_sorted(V2.begin(), V2.end()); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::nth_element(V2.begin(), V2.begin() + 1, V2.end()); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::partial_sort(V2.begin(), V2.begin() + 1, V2.end()); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::sort(V2.begin(), V2.end()); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::stable_sort(V2.begin(), V2.end()); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::partition(V2.begin(), V2.end(), f); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  std::stable_partition(V2.begin(), V2.end(), g); // expected-warning {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+  // expected-note@-1 {{Sorting pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerSorting]
+}

cfe/trunk/www/analyzer/alpha_checks.html

 <li><a href="#core_alpha_checkers">Core Alpha Checkers</a></li>
 <li><a href="#cplusplus_alpha_checkers">C++ Alpha Checkers</a></li>
 <li><a href="#llvm_alpha_checkers">LLVM Checkers</a></li>
 <li><a href="#valist_alpha_checkers">Variable Argument Alpha Checkers</a></li>
 <li><a href="#deadcode_alpha_checkers">Dead Code Alpha Checkers</a></li>
 <li><a href="#osx_alpha_checkers">OS X Alpha Checkers</a></li>
 <li><a href="#security_alpha_checkers">Security Alpha Checkers</a></li>
 <li><a href="#unix_alpha_checkers">Unix Alpha Checkers</a></li>
+<li><a href="#nondeterminism_alpha_checkers">Non-determinism Alpha Checkers</a></li>
 </ul>
 
 <!-- ============================= clone alpha ============================= -->
 
 <h3 id="clone_alpha_checkers">Clone Alpha Checkers</h3>
 <table class="checkers">
 <colgroup><col class="namedescr"><col class="example"></colgroup>
 <thead><tr><td>Name, Description</td><td>Example</td></tr></thead>
void test(char *y) {
   char x[4];
   if (strlen(y) == 4)
     strncpy(x, y, 5); // warn
 }
 </pre></div></div></td></tr>
 
 </tbody></table>
 
+<!-- =========================== nondeterminism alpha =========================== -->
+<h3 id="nondeterminism_alpha_checkers">Non-determinism Alpha Checkers</h3>
+<table class="checkers">
+<colgroup><col class="namedescr"><col class="example"></colgroup>
+<thead><tr><td>Name, Description</td><td>Example</td></tr></thead>
+
+<tbody>
+<tr><td><a id="alpha.nondeterminism.PointerSorting"><div class="namedescr expandable"><span class="name">
+alpha.nondeterminism.PointerSorting</span><span class="lang">
+(C++)</span><div class="descr">
+Check for non-determinism caused by sorting of pointers.</div></div></a></td>
+<td><div class="exampleContainer expandable">
+<div class="example"><pre>
+// C++
+void test() {
+ int a = 1, b = 2;
+ std::vector<int *> V = {&a, &b};
+ std::sort(V.begin(), V.end()); // warn
+}
+</pre></div></div></td></tr>
+</tbody></table>
+
 </div> <!-- page -->
 </div> <!-- content -->
 </body>
 </html>