Index: cfe/trunk/docs/analyzer/checkers.rst =================================================================== --- cfe/trunk/docs/analyzer/checkers.rst +++ cfe/trunk/docs/analyzer/checkers.rst @@ -1943,6 +1943,18 @@ 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 V = {&a, &b}; + std::sort(V.begin(), V.end()); // warn + } + Debug Checkers --------------- Index: cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -94,6 +94,8 @@ def CloneDetectionAlpha : Package<"clone">, ParentPackage; +def NonDeterminismAlpha : Package<"nondeterminism">, ParentPackage; + //===----------------------------------------------------------------------===// // Core Checkers. //===----------------------------------------------------------------------===// @@ -1043,3 +1045,15 @@ Documentation; } // end optin.portability + +//===----------------------------------------------------------------------===// +// NonDeterminism checkers. +//===----------------------------------------------------------------------===// + +let ParentPackage = NonDeterminismAlpha in { + +def PointerSortingChecker : Checker<"PointerSorting">, + HelpText<"Check for non-determinism caused by sorting of pointers">, + Documentation; + +} // end alpha.nondeterminism Index: cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -75,6 +75,7 @@ OSObjectCStyleCast.cpp PaddingChecker.cpp PointerArithChecker.cpp + PointerSortingChecker.cpp PointerSubChecker.cpp PthreadLockChecker.cpp RetainCountChecker/RetainCountChecker.cpp Index: cfe/trunk/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp +++ cfe/trunk/lib/StaticAnalyzer/Checkers/PointerSortingChecker.cpp @@ -0,0 +1,114 @@ +//=== 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 { +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 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(); +} + +bool ento::shouldRegisterPointerSortingChecker(const LangOptions &LO) { + return LO.CPlusPlus; +} Index: cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h +++ cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h @@ -822,3 +822,26 @@ int *status); }} namespace abi = __cxxabiv1; + +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); +} Index: cfe/trunk/test/Analysis/ptr-sort.cpp =================================================================== --- cfe/trunk/test/Analysis/ptr-sort.cpp +++ cfe/trunk/test/Analysis/ptr-sort.cpp @@ -0,0 +1,35 @@ +// 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 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] +} Index: cfe/trunk/www/analyzer/alpha_checks.html =================================================================== --- cfe/trunk/www/analyzer/alpha_checks.html +++ cfe/trunk/www/analyzer/alpha_checks.html @@ -33,6 +33,7 @@
  • OS X Alpha Checkers
  • Security Alpha Checkers
  • Unix Alpha Checkers
    • +
  • Non-determinism Alpha Checkers
    • @@ -1174,6 +1175,28 @@ + +

    Non-determinism Alpha Checkers

    + + + + + + + +
    Name, DescriptionExample
    +