Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -94,6 +94,8 @@ def CloneDetectionAlpha : Package<"clone">, InPackage, Hidden; +def NonDeterminismAlpha : Package<"nondeterminism">, InPackage, Hidden; + //===----------------------------------------------------------------------===// // Core Checkers. //===----------------------------------------------------------------------===// @@ -825,3 +827,15 @@ DescFile<"UnixAPIChecker.cpp">; } // end optin.portability + +//===----------------------------------------------------------------------===// +// NonDeterminism checkers. +//===----------------------------------------------------------------------===// + +let ParentPackage = NonDeterminismAlpha in { + +def PointerSortingChecker : Checker<"PointerSorting">, + HelpText<"Checks for non-determinism caused by sorting of pointer-like elements">, + DescFile<"PointerSortingChecker.cpp">; + +} // end alpha.nondeterminism Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -74,6 +74,7 @@ ObjCUnusedIVarsChecker.cpp PaddingChecker.cpp PointerArithChecker.cpp + PointerSortingChecker.cpp PointerSubChecker.cpp PthreadLockChecker.cpp RetainCountChecker.cpp Index: lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp @@ -0,0 +1,114 @@ +//===------------------ PointerSortingChecker.cpp -------------------------===// +// +// 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 "ClangSACheckers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" + +using namespace clang; +using namespace ento; +using namespace ast_matchers; + +namespace { + +// ID of a node at which the diagnostic would be emitted. +const char *WarnAtNode = "sort"; + +class PointerSortingChecker : public Checker { +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(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 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. +auto matchSortWithPointers() -> decltype(decl()) { + 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") + ); + + 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) { + // Run this checker only for C++. + if (!Mgr.getLangOpts().CPlusPlus) + return; + + Mgr.registerChecker(); +} Index: test/Analysis/ptr-sort.cpp =================================================================== --- /dev/null +++ test/Analysis/ptr-sort.cpp @@ -0,0 +1,57 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.nondeterminism.PointerSorting %s -analyzer-output=text -verify + +#include "Inputs/system-header-simulator-cxx.h" +namespace std { + template + bool is_sorted(ForwardIt first, ForwardIt last); + + template + void nth_element(RandomIt first, RandomIt nth, RandomIt last); + + template + void partial_sort(RandomIt first, RandomIt middle, RandomIt last); + + template + void sort (RandomIt first, RandomIt last); + + template + void stable_sort(RandomIt first, RandomIt last); + + template + BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p); + + template + BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p); +} + +bool f (int x) { return true; } +bool g (int *x) { return true; } + +void PointerSorting() { + int a = 1, b = 2, c = 3; + std::vector V1 = {a, b}; + std::vector 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] +}