compilerplugins/clang/loopvartoosmall.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * Based on LLVM/Clang.
   6  *
   7  * This file is distributed under the University of Illinois Open Source
   8  * License. See LICENSE.TXT for details.
   9  *
  10 */
  11
  12 #ifndef LO_CLANG_SHARED_PLUGINS
  13
  14 #include <algorithm>
  15 #include <cassert>
  16 #include <list>
  17 #include <map>
  18
  19 #include "plugin.hxx"
  20 //#include "clang/AST/CXXInheritance.h"
  21
  22 // Idea from bubli. Check that the index variable in a for loop is able to cover the range
  23 // revealed by the terminating condition.
  24 // If not, we might end up in an endless loop, or just not process certain parts.
  25
  26 namespace
  27 {
  28
  29 class LoopVarTooSmall:
  30     public loplugin::FilteringPlugin<LoopVarTooSmall>
  31 {
  32 public:
  33     explicit LoopVarTooSmall(loplugin::InstantiationData const & data):
  34         FilteringPlugin(data) {}
  35
  36     virtual void run() override {
  37         TraverseDecl(compiler.getASTContext().getTranslationUnitDecl());
  38     }
  39
  40     bool VisitForStmt( const ForStmt* stmt ) {
  41         checkExpr(stmt->getCond());
  42         return true;
  43     }
  44
  45     bool VisitWhileStmt(WhileStmt const * stmt) {
  46         checkExpr(stmt->getCond());
  47         return true;
  48     }
  49
  50     bool VisitDoStmt(DoStmt const * stmt) {
  51         checkExpr(stmt->getCond());
  52         return true;
  53     }
  54
  55 private:
  56     unsigned getIntValueWidth(QualType type) const;
  57
  58     void checkSubExpr(Expr const * expr, bool positive);
  59
  60     void checkExpr(Expr const * expr);
  61
  62     struct Comparison {
  63         BinaryOperator const * op;
  64         unsigned rhsWidth;
  65     };
  66
  67     struct Comparisons {
  68         std::list<Comparison> comparisons;
  69         unsigned lhsWidth;
  70     };
  71
  72     std::map<Decl const *, Comparisons> comparisons_;
  73 };
  74
  75 unsigned LoopVarTooSmall::getIntValueWidth(QualType type) const {
  76     if (auto const et = type->getAs<EnumType>()) {
  77         auto const ed = et->getDecl();
  78         if (!ed->isFixed()) {
  79             unsigned pos = ed->getNumPositiveBits();
  80             unsigned neg = ed->getNumNegativeBits();
  81             return neg == 0 ? std::max(pos, 1U) : std::max(pos + 1, neg);
  82         }
  83     }
  84     return compiler.getASTContext().getIntWidth(type);
  85 }
  86
  87 void LoopVarTooSmall::checkSubExpr(Expr const * expr, bool positive) {
  88     auto const e = expr->IgnoreImplicit()->IgnoreParenImpCasts();
  89     if (auto const uo = dyn_cast<UnaryOperator>(e)) {
  90         if (uo->getOpcode() == UO_LNot) {
  91             checkSubExpr(uo->getSubExpr(), !positive);
  92         }
  93         return;
  94     }
  95     const BinaryOperator* binOp = dyn_cast<BinaryOperator>(e);
  96     if (!binOp)
  97         return;
  98     bool less;
  99     if (positive) {
 100         switch (binOp->getOpcode()) {
 101         case BO_LAnd:
 102             checkSubExpr(binOp->getLHS(), true);
 103             checkSubExpr(binOp->getRHS(), true);
 104             return;
 105         case BO_LT:
 106         case BO_NE:
 107             less = true;
 108             break;
 109         case BO_LE:
 110             less = false;
 111             break;
 112         default:
 113             return;
 114         }
 115     } else {
 116         switch (binOp->getOpcode()) {
 117         case BO_LOr:
 118             checkSubExpr(binOp->getLHS(), false);
 119             checkSubExpr(binOp->getRHS(), false);
 120             return;
 121         case BO_GE:
 122         case BO_EQ:
 123             less = true;
 124             break;
 125         case BO_GT:
 126             less = false;
 127             break;
 128         default:
 129             return;
 130         }
 131     }
 132     auto lhs = dyn_cast<DeclRefExpr>(binOp->getLHS()->IgnoreParenImpCasts());
 133     if (!lhs)
 134         return;
 135     QualType qt = lhs->getType();
 136     if (!qt->isIntegralOrEnumerationType())
 137         return;
 138     unsigned qt1BitWidth = getIntValueWidth(qt);
 139     auto lhsDecl = lhs->getDecl();
 140     if (!isa<VarDecl>(lhsDecl)) {
 141         if (auto fd = dyn_cast<FieldDecl>(lhsDecl)) {
 142             if (fd->isBitField()) {
 143                 qt1BitWidth = std::max(
 144                     qt1BitWidth,
 145                     fd->getBitWidthValue(compiler.getASTContext()));
 146             }
 147         } else {
 148             return;
 149         }
 150     }
 151     const Expr* binOpRHS = binOp->getRHS()->IgnoreParenImpCasts();
 152     QualType qt2 = binOpRHS->getType();
 153     if (!qt2->isIntegralType(compiler.getASTContext()))
 154         return;
 155     unsigned qt2BitWidth;
 156     llvm::APSInt aIntResult;
 157     // Work around missing Clang 3.9 fix <https://reviews.llvm.org/rL271762>
 158     // "Sema: do not attempt to sizeof a dependent type", causing Clang 3.8 to
 159     // crash during EvaluateAsInt() on expressions of the form
 160     //
 161     //   sizeof (T)
 162     //
 163     // with dependent type T:
 164     if (!binOpRHS->isValueDependent()
 165         && compat::EvaluateAsInt(binOpRHS, aIntResult, compiler.getASTContext()))
 166     {
 167         if (less && aIntResult.isStrictlyPositive()) {
 168             --aIntResult;
 169         }
 170         qt2BitWidth = aIntResult.isUnsigned() || !aIntResult.isNegative()
 171             ? std::max(aIntResult.getActiveBits(), 1U)
 172             : aIntResult.getBitWidth() - aIntResult.countLeadingOnes() + 1;
 173     } else {
 174         // Ignore complex expressions for now, promotion rules on conditions
 175         // like "i < (size()+1)" make it hard to guess at a correct type:
 176         if (isa<BinaryOperator>(binOpRHS) || isa<ConditionalOperator>(binOpRHS))
 177         {
 178             return;
 179         }
 180         qt2BitWidth = getIntValueWidth(qt2);
 181         if (auto dre = dyn_cast<DeclRefExpr>(binOpRHS)) {
 182             if (auto fd = dyn_cast<FieldDecl>(dre->getDecl())) {
 183                 if (fd->isBitField()) {
 184                     qt2BitWidth = std::max(
 185                         qt2BitWidth,
 186                         fd->getBitWidthValue(compiler.getASTContext()));
 187                 }
 188             }
 189         }
 190     }
 191
 192     auto i = comparisons_.find(lhsDecl);
 193     if (i == comparisons_.end()) {
 194         i = (comparisons_.insert(
 195                  decltype(comparisons_)::value_type(lhsDecl, {{}, qt1BitWidth}))
 196              .first);
 197     } else {
 198         assert(i->second.lhsWidth == qt1BitWidth);
 199     }
 200     bool ins = true;
 201     for (auto j = i->second.comparisons.begin();
 202          j != i->second.comparisons.end();)
 203     {
 204         if (qt2BitWidth > j->rhsWidth) {
 205             ins = false;
 206             break;
 207         } else if (qt2BitWidth < j->rhsWidth) {
 208             j = i->second.comparisons.erase(j);
 209         } else {
 210             ++j;
 211         }
 212     }
 213     if (ins) {
 214         i->second.comparisons.push_back({binOp, qt2BitWidth});
 215     }
 216 }
 217
 218 void LoopVarTooSmall::checkExpr(Expr const * expr) {
 219     if (expr != nullptr && !ignoreLocation(expr)) {
 220         assert(comparisons_.empty());
 221         checkSubExpr(expr, true);
 222         for (auto const & i: comparisons_) {
 223             for (auto const & j: i.second.comparisons) {
 224                 if (i.second.lhsWidth < j.rhsWidth) {
 225                     report(
 226                         DiagnosticsEngine::Warning,
 227                         "loop index type %0 is narrower than length type %1",
 228                         j.op->getExprLoc())
 229                         << j.op->getLHS()->IgnoreImpCasts()->getType()
 230                         << j.op->getRHS()->IgnoreImpCasts()->getType()
 231                         << j.op->getSourceRange();
 232                 }
 233             }
 234         }
 235         comparisons_.clear();
 236     }
 237 }
 238
 239 loplugin::Plugin::Registration< LoopVarTooSmall > loopvartoosmall("loopvartoosmall");
 240
 241 }
 242
 243 #endif // LO_CLANG_SHARED_PLUGINS
 244
 245 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */