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