Index: docs/analyzer/checkers.rst =================================================================== --- docs/analyzer/checkers.rst +++ docs/analyzer/checkers.rst @@ -211,8 +211,8 @@ .. _cplusplus-checkers: -cpluslus -^^^^^^^^ +cplusplus +^^^^^^^^^ C++ Checkers. @@ -1943,6 +1943,20 @@ int y = strlen((char *)&test); // warn } +alpha.nondeterminism.PointerIteration (C++) +""""""""""""""""""""""""""""""""""""""""""" +Check for non-determinism caused by iterating unordered containers of pointers. + +.. code-block:: c + + void test() { + int a = 1, b = 2; + std::unordered_set UnorderedPointerSet = {&a, &b}; + + for (auto i : UnorderedPointerSet) // warn + f(i); + } + alpha.nondeterminism.PointerSorting (C++) """"""""""""""""""""""""""""""""""""""""" Check for non-determinism caused by sorting of pointers. Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -1052,6 +1052,10 @@ let ParentPackage = NonDeterminismAlpha in { +def PointerIterationChecker : Checker<"PointerIteration">, + HelpText<"Checks for non-determinism caused by iteration of unordered containers of pointers">, + Documentation; + def PointerSortingChecker : Checker<"PointerSorting">, HelpText<"Check for non-determinism caused by sorting of pointers">, Documentation; Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -75,6 +75,7 @@ OSObjectCStyleCast.cpp PaddingChecker.cpp PointerArithChecker.cpp + PointerIterationChecker.cpp PointerSortingChecker.cpp PointerSubChecker.cpp PthreadLockChecker.cpp Index: lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp @@ -0,0 +1,100 @@ +//== PointerIterationChecker.cpp ------------------------------- -*- C++ -*--=// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines PointerIterationChecker which checks for non-determinism +// caused due to iteration of unordered containers of pointer 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 = "iter"; + +class PointerIterationChecker : 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 PointerIterationChecker *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 << "Iteration of pointer-like elements " + << "can result in non-deterministic ordering"; + + BR.EmitBasicReport(ADC->getDecl(), Checker, + "Iteration of pointer-like elements", "Non-determinism", + OS.str(), Location, Range); +} + +// Assumption: Iteration of ordered containers of pointers is deterministic. + +// TODO: Currently, we only check for std::unordered_set. Other unordered +// containers like std::unordered_map also need to be handled. + +// TODO: Currently, we do not check what the for loop does with the iterated +// pointer values. Not all iterations may cause non-determinism. For example, +// counting or summing up the elements should not be non-deterministic. + +auto matchUnorderedIterWithPointers() -> decltype(decl()) { + + auto UnorderedContainerM = declRefExpr(to(varDecl(hasType( + recordDecl(hasName("std::unordered_set") + ))))); + + auto PointerTypeM = varDecl(hasType(hasCanonicalType(pointerType()))); + + auto PointerIterM = stmt(cxxForRangeStmt( + hasLoopVariable(PointerTypeM), + hasRangeInit(UnorderedContainerM) + )).bind(WarnAtNode); + + return decl(forEachDescendant(PointerIterM)); +} + +void PointerIterationChecker::checkASTCodeBody(const Decl *D, + AnalysisManager &AM, + BugReporter &BR) const { + auto MatcherM = matchUnorderedIterWithPointers(); + + auto Matches = match(MatcherM, *D, AM.getASTContext()); + for (const auto &Match : Matches) + emitDiagnostics(Match, D, BR, AM, this); +} + +} // end of anonymous namespace + +void ento::registerPointerIterationChecker(CheckerManager &Mgr) { + Mgr.registerChecker(); +} + +bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) { + return LO.CPlusPlus; +} Index: test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- test/Analysis/Inputs/system-header-simulator-cxx.h +++ test/Analysis/Inputs/system-header-simulator-cxx.h @@ -845,3 +845,64 @@ template BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p); } + +namespace std { + +template< class T = void > +struct less; + +template< class T > +struct allocator; + +template< class Key > +struct hash; + +template< + class Key, + class Compare = std::less, + class Alloc = std::allocator +> class set { + public: + set(initializer_list __list) {} + + class iterator { + public: + iterator(Key *key): ptr(key) {} + iterator operator++() { ++ptr; return *this; } + bool operator!=(const iterator &other) const { return ptr != other.ptr; } + const Key &operator*() const { return *ptr; } + private: + Key *ptr; + }; + + public: + Key *val; + iterator begin() const { return iterator(val); } + iterator end() const { return iterator(val + 1); } +}; + +template< + class Key, + class Hash = std::hash, + class Compare = std::less, + class Alloc = std::allocator +> class unordered_set { + public: + unordered_set(initializer_list __list) {} + + class iterator { + public: + iterator(Key *key): ptr(key) {} + iterator operator++() { ++ptr; return *this; } + bool operator!=(const iterator &other) const { return ptr != other.ptr; } + const Key &operator*() const { return *ptr; } + private: + Key *ptr; + }; + + public: + Key *val; + iterator begin() const { return iterator(val); } + iterator end() const { return iterator(val + 1); } +}; +} Index: test/Analysis/ptr-iter.cpp =================================================================== --- /dev/null +++ test/Analysis/ptr-iter.cpp @@ -0,0 +1,28 @@ +// RUN: %clang_analyze_cc1 %s -analyzer-output=text -verify \ +// RUN: -analyzer-checker=core,alpha.nondeterminism.PointerIteration + +#include "Inputs/system-header-simulator-cxx.h" + +template +void f(T x); + +void PointerIteration() { + int a = 1, b = 2; + std::set OrderedIntSet = {a, b}; + std::set OrderedPointerSet = {&a, &b}; + std::unordered_set UnorderedIntSet = {a, b}; + std::unordered_set UnorderedPointerSet = {&a, &b}; + + for (auto i : OrderedIntSet) // no-warning + f(i); + + for (auto i : OrderedPointerSet) // no-warning + f(i); + + for (auto i : UnorderedIntSet) // no-warning + f(i); + + for (auto i : UnorderedPointerSet) // expected-warning {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration] +// expected-note@-1 {{Iteration of pointer-like elements can result in non-deterministic ordering}} [alpha.nondeterminism.PointerIteration] + f(i); +} Index: www/analyzer/alpha_checks.html =================================================================== --- www/analyzer/alpha_checks.html +++ www/analyzer/alpha_checks.html @@ -1182,6 +1182,24 @@ Name, DescriptionExample + + + + +