mgrang created this revision.
mgrang added reviewers: NoQ, george.karpenkov, whisperity, Szelethus.
mgrang added a project: clang.
Herald added subscribers: Charusso, jdoerfert, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware, xazax.hun,
mgorny.
Added a checker for non-determinism caused by iterating unordered containers
like std::unordered_set containing pointer elements.
Repository:
rC Clang
https://reviews.llvm.org/D59279
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp
test/Analysis/Inputs/system-header-simulator-cxx.h
test/Analysis/ptr-iter.cpp
Index: test/Analysis/ptr-iter.cpp
===================================================================
--- /dev/null
+++ test/Analysis/ptr-iter.cpp
@@ -0,0 +1,27 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.nondeterminism.PointerIteration %s -analyzer-output=text -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+template<class T>
+void f(T x);
+
+void PointerIteration() {
+ int a = 1, b = 2;
+ std::set<int> OrderedIntSet = {a, b};
+ std::set<int *> OrderedPointerSet = {&a, &b};
+ std::unordered_set<int> UnorderedIntSet = {a, b};
+ std::unordered_set<int *> 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: 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<class BidirIt, class UnaryPredicate>
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<Key>,
+ class Alloc = std::allocator<Key>
+> class set {
+ public:
+ set(initializer_list<Key> __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<Key>,
+ class Compare = std::less<Key>,
+ class Alloc = std::allocator<Key>
+> class unordered_set {
+ public:
+ unordered_set(initializer_list<Key> __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: lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp
@@ -0,0 +1,92 @@
+//=== PointerIterationChecker.cpp - Pointer Iteration 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 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<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 PointerIterationChecker *Checker) {
+ auto *ADC = AM.getAnalysisDeclContext(D);
+
+ const auto *MarkedStmt = Match.getNodeAs<Stmt>(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);
+}
+
+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<PointerIterationChecker>();
+}
+
+bool ento::shouldRegisterPointerIterationChecker(const LangOptions &LO) {
+ return LO.CPlusPlus;
+}
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: 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<HasDocumentation>;
+
def PointerSortingChecker : Checker<"PointerSorting">,
HelpText<"Check for non-determinism caused by sorting of pointers">,
Documentation<HasDocumentation>;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
