paulsemel created this revision.
Herald added subscribers: cfe-commits, mgorny.
\!/ This is only a proof of concept !
The purpose of this checker is to improve the detection of unsequenced
modifications. Indeed, there is a warning the tries to detect those, but this
is not efficient at all.
The goal of this checker is to detect more complicated UM.
Repository:
rC Clang
https://reviews.llvm.org/D44154
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp
Index: lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp
+++ lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp
@@ -0,0 +1,450 @@
+//=== UnsequencedModificationChecker.cpp -------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines UnsequencedModificationChecker, a builtin check in ExprEngine
+// that performs checks for unsequenced modifications.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+#include <list>
+#include <algorithm>
+#include <iostream>
+#include <functional>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+ enum UBType
+ {
+ UB_VAR,
+ UB_ARRAY,
+ UB_POINTER,
+ UB_POINTERINDEX
+ };
+
+ class UBDecl
+ {
+ public:
+ UBDecl(const VarDecl *vd)
+ {
+ this->idx = SVal();
+ this->type = UB_VAR;
+ this->vd = vd;
+ };
+ UBDecl(const VarDecl *vd, enum UBType t)
+ : vd(vd), type(t)
+ {
+ this->idx = SVal();
+ }
+ UBDecl(const VarDecl *vd, SVal index)
+ {
+ this->type = UB_ARRAY;
+ this->vd = vd;
+ this->idx = index;
+ };
+ void changeType(enum UBType t)
+ {
+ this->type = t;
+ };
+ bool operator==(const UBDecl& ub)
+ {
+ if (this->type != ub.type)
+ return false;
+ switch(this->type)
+ {
+ case UB_VAR:
+ case UB_POINTER:
+ return this->vd == ub.vd;
+ case UB_ARRAY:
+ case UB_POINTERINDEX:
+ return this->vd == ub.vd && this->idx == ub.idx;
+ };
+ return false;
+ };
+ const VarDecl *vd;
+ SVal idx;
+ enum UBType type;
+ private:
+ };
+
+ enum UBAction
+ {
+ UBUSED = 1,
+ UBMODIFIED = 2,
+ UBMULTIPLE = 4,
+ };
+
+ class UBListElement
+ {
+ public:
+ UBListElement(std::shared_ptr<UBDecl>& ub, enum UBAction action)
+ :ub(ub), action(action)
+ { };
+ UBListElement(std::shared_ptr<UBDecl>& ub, uint32_t action)
+ :ub(ub), action(action)
+ { };
+ bool operator==(const UBDecl& elt)
+ {
+ return *ub == elt;
+ };
+ std::shared_ptr<UBDecl> ub;
+ uint32_t action;
+ };
+
+ class UBList
+ {
+ public:
+ UBList() = default;
+ void push(std::shared_ptr<UBDecl> ub, enum UBAction action)
+ {
+ auto it = std::find(list.begin(), list.end(), *ub);
+ if (it != list.end())
+ {
+ if (it->action == action && action == UBMODIFIED)
+ it->action = UBMULTIPLE;
+ else
+ it->action |= action;
+ }
+ else
+ list.push_back(UBListElement(ub, action));
+ };
+ void pushCallExpr(std::shared_ptr<UBDecl> ub, uint32_t action)
+ {
+ auto it = std::find(list.begin(), list.end(), *ub);
+ if (it != list.end())
+ {
+ if (action != it->action)
+ it->action = UBMODIFIED;
+ }
+ else
+ list.push_back(UBListElement(ub, action));
+ }
+ void push(std::shared_ptr<UBDecl> ub, uint32_t action)
+ {
+ auto it = std::find(list.begin(), list.end(), *ub);
+ if (it != list.end())
+ {
+ if (it->action == action && action == UBMODIFIED)
+ it->action = UBMULTIPLE;
+ else
+ it->action |= action;
+ }
+ else
+ list.push_back(UBListElement(ub, action));
+ };
+ size_t size()
+ {
+ return list.size();
+ };
+ std::shared_ptr<UBDecl> find_UB()
+ {
+ for (auto &elt : list)
+ {
+ if (elt.action == UBMULTIPLE || elt.action == (UBMODIFIED|UBUSED))
+ return elt.ub;
+ }
+ return nullptr;
+ };
+ std::list<UBListElement> list;
+ };
+
+ class UnsequencedModificationChecker
+ : public Checker< check::PreStmt<Stmt> > {
+
+ mutable std::unique_ptr<BugType> BT;
+
+ public:
+ void checkPreStmt(const Stmt *, CheckerContext &) const;
+
+ private:
+ void BinOpUnsequencedChecker(const BinaryOperator *, CheckerContext&, UBList&) const;
+ void CallExprChecker(const CallExpr *, CheckerContext&, UBList&) const;
+ std::shared_ptr<UBDecl> DetermineType(const Stmt*, UBList&, CheckerContext&) const;
+ std::shared_ptr<UBDecl> DetermineTypeExpr(const Expr*, UBList&, CheckerContext&) const;
+ std::shared_ptr<UBDecl> UnaryOperatorChecker(const UnaryOperator*, UBList&, CheckerContext&) const;
+ std::shared_ptr<UBDecl> DeclarationChecker(const DeclRefExpr*, UBList&, CheckerContext&) const;
+ std::shared_ptr<UBDecl> ArraySubChecker(const ArraySubscriptExpr*, UBList&, CheckerContext&) const;
+ const Expr* CleanExpr(const Expr*) const;
+ std::shared_ptr<UBDecl> DeclStmtChecker(const DeclStmt*, UBList&, CheckerContext&) const;
+ void ReturnStmtChecker(const ReturnStmt* , UBList&, CheckerContext&) const;
+ };
+
+} // end anonymous namespace
+
+const Expr* UnsequencedModificationChecker::CleanExpr(const Expr *E) const
+{
+ const Expr *tmp;
+ do {
+ tmp = E;
+ E = E->IgnoreParens()->IgnoreCasts();
+ } while (E != tmp);
+ return E;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DetermineType(const Stmt* S, UBList& Set,
+ CheckerContext& C) const
+{
+ if (!S)
+ return nullptr;
+ if (const Expr *E = dyn_cast<Expr>(S))
+ return this->DetermineTypeExpr(E, Set, C);
+ else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
+ return this->DeclStmtChecker(DS, Set, C);
+ else if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(S))
+ this->ReturnStmtChecker(RS, Set, C);
+ return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DetermineTypeExpr(const Expr* E, UBList& Set,
+ CheckerContext& C) const
+{
+ if (!E)
+ return nullptr;
+ E = this->CleanExpr(E);
+ if (const BinaryOperator* BO = dyn_cast<BinaryOperator>(E))
+ this->BinOpUnsequencedChecker(BO, C, Set);
+ else if (const UnaryOperator* UO = dyn_cast<UnaryOperator>(E))
+ return this->UnaryOperatorChecker(UO, Set, C);
+ else if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
+ return this->DeclarationChecker(DR, Set, C);
+ else if (const ArraySubscriptExpr *AS = dyn_cast<ArraySubscriptExpr>(E))
+ return this->ArraySubChecker(AS, Set, C);
+ else if (const CallExpr* CE = dyn_cast<CallExpr>(E))
+ this->CallExprChecker(CE, C, Set);
+ return nullptr;
+}
+
+void UnsequencedModificationChecker::ReturnStmtChecker(const ReturnStmt* RS, UBList& Set, CheckerContext& C) const
+{
+ std::shared_ptr<UBDecl> ub = this->DetermineTypeExpr(RS->getRetValue(), Set, C);
+ if (ub)
+ Set.push(ub, UBUSED);
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::UnaryOperatorChecker(const UnaryOperator* UO,
+ UBList& Set,
+ CheckerContext &C) const
+{
+ std::shared_ptr<UBDecl> UB = this->DetermineTypeExpr(UO->getSubExpr(), Set, C);
+ if (!UB)
+ return nullptr;
+ if (UO->isDecrementOp() || UO->isIncrementOp())
+ Set.push(UB, UBMODIFIED);
+ else
+ {
+ UB->changeType(UB_POINTER);
+ return UB;
+ }
+ return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DeclStmtChecker(const DeclStmt* DS, UBList& Set,
+ CheckerContext& C) const
+{
+ if (DS->isSingleDecl())
+ {
+ std::cout << "SingleDecl" << std::endl;
+ if (const VarDecl* VD = dyn_cast<VarDecl>(DS->getSingleDecl()))
+ {
+ if (VD->hasInit())
+ {
+ std::shared_ptr<UBDecl> ptr = this->DetermineTypeExpr(VD->getInit(), Set, C);
+ if (ptr)
+ Set.push(ptr, UBUSED);
+ }
+ return std::make_shared<UBDecl>(VD);
+ }
+ }
+ else
+ std::cout << "GroupDecl" << std::endl;
+ return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DeclarationChecker(const DeclRefExpr* DR, UBList& Set,
+ CheckerContext& C) const
+{
+ if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
+ return std::make_shared<UBDecl>(VD);
+ return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::ArraySubChecker(const ArraySubscriptExpr* AS,
+ UBList& Set, CheckerContext& C) const
+{
+ SVal index = C.getState()->getSVal(AS->getIdx(), C.getLocationContext());
+ const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(AS->getBase()->IgnoreImpCasts());
+ if (DR)
+ {
+ const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
+ if (VD)
+ return std::make_shared<UBDecl>(VD, index);
+ }
+ return nullptr;
+}
+
+void
+UnsequencedModificationChecker::BinOpUnsequencedChecker(const BinaryOperator* Ope,
+ CheckerContext &C,
+ UBList &Set) const
+{
+
+ if (Ope->isAssignmentOp() || Ope->isCompoundAssignmentOp())
+ {
+ std::shared_ptr<UBDecl> ptr = DetermineTypeExpr(Ope->getLHS(), Set, C);
+ if (ptr)
+ Set.push(ptr, UBMODIFIED);
+
+ ptr = DetermineTypeExpr(Ope->getRHS(), Set, C);
+ if (ptr)
+ Set.push(ptr, UBUSED);
+ }
+ else
+ {
+ std::shared_ptr<UBDecl> ptr = DetermineTypeExpr(Ope->getLHS(), Set, C);
+ if (ptr)
+ Set.push(ptr, UBUSED);
+ ptr = DetermineTypeExpr(Ope->getRHS(), Set, C);
+ if (ptr)
+ Set.push(ptr, UBUSED);
+ if ((ptr = Set.find_UB()))
+ {
+ ExplodedNode *N = C.generateErrorNode();
+ if (!N)
+ return;
+
+ if (!BT)
+ BT.reset(
+ new BuiltinBug(this, "Operation leads to an undefined behaviour"));
+
+ SmallString<256> sbuf;
+ llvm::raw_svector_ostream OS(sbuf);
+
+
+ OS << "Unsequenced modifications to '";
+ if (ptr->type == UB_ARRAY)
+ {
+ OS << *ptr->vd << "[";
+ ptr->idx.dumpToStream(OS);
+ OS << "]";
+ }
+ else if (ptr->type == UB_POINTER)
+ OS << "*" << *ptr->vd;
+ else
+ OS << *ptr->vd;
+ OS << "'";
+
+ auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);
+
+ C.emitReport(std::move(report));
+ }
+ }
+}
+
+void
+UnsequencedModificationChecker::CallExprChecker(const CallExpr* CE,
+ CheckerContext &C,
+ UBList &Set) const
+{
+ const Expr *const *args = CE->getArgs();
+ std::shared_ptr<UBDecl> ptr;
+ for (unsigned i = 0; i < CE->getNumArgs(); i++)
+ {
+ ptr = this->DetermineTypeExpr(args[i], Set, C);
+ if (ptr)
+ Set.push(ptr, UBUSED);
+ }
+
+ if ((ptr = Set.find_UB()))
+ {
+ ExplodedNode *N = C.generateErrorNode();
+ if (!N)
+ return;
+
+ if (!BT)
+ BT.reset(
+ new BuiltinBug(this, "Operation leads to an undefined behaviour"));
+
+ SmallString<256> sbuf;
+ llvm::raw_svector_ostream OS(sbuf);
+
+
+ OS << "Unsequenced modifications to '";
+ if (ptr->type == UB_ARRAY)
+ {
+ OS << *ptr->vd << "[";
+ ptr->idx.dumpToStream(OS);
+ OS << "]";
+ }
+ else if (ptr->type == UB_POINTER)
+ OS << "*" << *ptr->vd;
+ else
+ OS << *ptr->vd;
+ OS << "'";
+
+ auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);
+
+ C.emitReport(std::move(report));
+ }
+
+ const FunctionDecl *FD = CE->getDirectCallee();
+ if (FD && (FD = FD->getDefinition()) && FD->hasBody())
+ {
+ const Stmt *Body = FD->getBody();
+ const CompoundStmt *CS;
+ UBList Bodyset;
+ if (Body && (CS = dyn_cast<CompoundStmt>(Body)))
+ {
+ for (auto it = CS->body_begin(); it != CS->body_end(); it++)
+ {
+ UBList Tmpset = UBList();
+ std::shared_ptr<UBDecl> ub = this->DetermineType(*it, Tmpset,C);
+ /* True for all non local */
+ if (ub && ub->vd->hasGlobalStorage())
+ Set.push(ub, UBUSED);
+ for (auto elt = Tmpset.list.begin(); elt != Tmpset.list.end(); elt++)
+ {
+ if (elt->ub->vd->hasGlobalStorage())
+ Bodyset.pushCallExpr(elt->ub, elt->action);
+ }
+ }
+ }
+ for (auto it = Bodyset.list.begin(); it != Bodyset.list.end(); it++)
+ Set.push(it->ub, it->action);
+ }
+
+}
+
+void UnsequencedModificationChecker::checkPreStmt(const Stmt *S,
+ CheckerContext &C) const {
+
+ UBList Set = UBList();
+ if (const Expr* E = dyn_cast<Expr>(S))
+ this->DetermineTypeExpr(E, Set, C);
+}
+
+void ento::registerUnsequencedModificationChecker(CheckerManager &mgr) {
+ mgr.registerChecker<UnsequencedModificationChecker>();
+}
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -87,6 +87,7 @@
UndefResultChecker.cpp
UndefinedArraySubscriptChecker.cpp
UndefinedAssignmentChecker.cpp
+ UnsequencedModificationChecker.cpp
UnixAPIChecker.cpp
UnreachableCodeChecker.cpp
VforkChecker.cpp
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -248,6 +248,10 @@
HelpText<"Check for assigning uninitialized values">,
DescFile<"UndefinedAssignmentChecker.cpp">;
+def UnsequencedModificationChecker : Checker<"UB">,
+ HelpText<"Check for unsequenced modifications">,
+ DescFile<"UnsequencedModificationChecker.cpp">;
+
def UndefBranchChecker : Checker<"Branch">,
HelpText<"Check for uninitialized values used as branch conditions">,
DescFile<"UndefBranchChecker.cpp">;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
