mgrang updated this revision to Diff 190453.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59279/new/
https://reviews.llvm.org/D59279
Files:
docs/analyzer/checkers.rst
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
www/analyzer/alpha_checks.html
Index: www/analyzer/alpha_checks.html
===================================================================
--- www/analyzer/alpha_checks.html
+++ www/analyzer/alpha_checks.html
@@ -1182,6 +1182,24 @@
<thead><tr><td>Name, Description</td><td>Example</td></tr></thead>
<tbody>
+<tr><td><a id="alpha.nondeterminism.PointerIteration"><div class="namedescr expandable"><span class="name">
+alpha.nondeterminism.PointerIteration</span><span class="lang">
+(C++)</span><div class="descr">
+Check for non-determinism caused by iterating unordered containers of pointers.</div></div></a></td>
+<td><div class="exampleContainer expandable">
+<div class="example"><pre>
+// C++
+void test() {
+ int a = 1, b = 2;
+ std::unordered_set<int *> UnorderedPointerSet = {&a, &b};
+
+ for (auto i : UnorderedPointerSet) // warn
+ f(i);
+}
+</pre></div></div></td></tr>
+</tbody></table>
+
+<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">
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<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,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<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);
+}
+
+// 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<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>;
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<int *> UnorderedPointerSet = {&a, &b};
+
+ for (auto i : UnorderedPointerSet) // warn
+ f(i);
+ }
+
alpha.nondeterminism.PointerSorting (C++)
"""""""""""""""""""""""""""""""""""""""""
Check for non-determinism caused by sorting of pointers.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
