[Analyzer] Checker for non-determinism caused by iteration of unordered container of pointers

Summary: Added a checker for non-determinism caused by iterating unordered containers like std::unordered_set containing pointer elements.

Reviewers: NoQ, george.karpenkov, whisperity, Szelethus, baloghadamsoftware

Reviewed By: Szelethus

Subscribers: mgorny, xazax.hun, baloghadamsoftware, szepet, rnkovacs, a.sidorin, mikhail.ramalho, donat.nagy, dkrupp, jdoerfert, Charusso, cfe-commits

Tags: #clang

Differential Revision: https://reviews.llvm.org/D59279

llvm-svn: 361664

1 files changed, 100 insertions, 0 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/PointerIterationChecker.cpp
new file mode 100644
index 00000000000..307e59b8eeb
--- /dev/null
+++ b/clang/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;
+}