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