| 1 |
//=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// Defines common functions to be used by the itertor checkers . |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "Iterator.h" |
| 14 |
|
| 15 |
namespace clang { |
| 16 |
namespace ento { |
| 17 |
namespace iterator { |
| 18 |
|
| 19 |
bool isIteratorType(const QualType &Type) { |
| 20 |
if (Type->isPointerType()) |
| 21 |
return true; |
| 22 |
|
| 23 |
const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); |
| 24 |
return isIterator(CRD); |
| 25 |
} |
| 26 |
|
| 27 |
bool isIterator(const CXXRecordDecl *CRD) { |
| 28 |
if (!CRD) |
| 29 |
return false; |
| 30 |
|
| 31 |
const auto Name = CRD->getName(); |
| 32 |
if (!(Name.endswith_insensitive("iterator") || |
| 33 |
Name.endswith_insensitive("iter") || Name.endswith_insensitive("it"))) |
| 34 |
return false; |
| 35 |
|
| 36 |
bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false, |
| 37 |
HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false; |
| 38 |
for (const auto *Method : CRD->methods()) { |
| 39 |
if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) { |
| 40 |
if (Ctor->isCopyConstructor()) { |
| 41 |
HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public; |
| 42 |
} |
| 43 |
continue; |
| 44 |
} |
| 45 |
if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) { |
| 46 |
HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public; |
| 47 |
continue; |
| 48 |
} |
| 49 |
if (Method->isCopyAssignmentOperator()) { |
| 50 |
HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public; |
| 51 |
continue; |
| 52 |
} |
| 53 |
if (!Method->isOverloadedOperator()) |
| 54 |
continue; |
| 55 |
const auto OPK = Method->getOverloadedOperator(); |
| 56 |
if (OPK == OO_PlusPlus) { |
| 57 |
HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0); |
| 58 |
HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1); |
| 59 |
continue; |
| 60 |
} |
| 61 |
if (OPK == OO_Star) { |
| 62 |
HasDerefOp = (Method->getNumParams() == 0); |
| 63 |
continue; |
| 64 |
} |
| 65 |
} |
| 66 |
|
| 67 |
return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp && |
| 68 |
HasPostIncrOp && HasDerefOp; |
| 69 |
} |
| 70 |
|
| 71 |
bool isComparisonOperator(OverloadedOperatorKind OK) { |
| 72 |
return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less || |
| 73 |
OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual; |
| 74 |
} |
| 75 |
|
| 76 |
bool isInsertCall(const FunctionDecl *Func) { |
| 77 |
const auto *IdInfo = Func->getIdentifier(); |
| 78 |
if (!IdInfo) |
| 79 |
return false; |
| 80 |
if (Func->getNumParams() < 2 || Func->getNumParams() > 3) |
| 81 |
return false; |
| 82 |
if (!isIteratorType(Func->getParamDecl(0)->getType())) |
| 83 |
return false; |
| 84 |
return IdInfo->getName() == "insert"; |
| 85 |
} |
| 86 |
|
| 87 |
bool isEmplaceCall(const FunctionDecl *Func) { |
| 88 |
const auto *IdInfo = Func->getIdentifier(); |
| 89 |
if (!IdInfo) |
| 90 |
return false; |
| 91 |
if (Func->getNumParams() < 2) |
| 92 |
return false; |
| 93 |
if (!isIteratorType(Func->getParamDecl(0)->getType())) |
| 94 |
return false; |
| 95 |
return IdInfo->getName() == "emplace"; |
| 96 |
} |
| 97 |
|
| 98 |
bool isEraseCall(const FunctionDecl *Func) { |
| 99 |
const auto *IdInfo = Func->getIdentifier(); |
| 100 |
if (!IdInfo) |
| 101 |
return false; |
| 102 |
if (Func->getNumParams() < 1 || Func->getNumParams() > 2) |
| 103 |
return false; |
| 104 |
if (!isIteratorType(Func->getParamDecl(0)->getType())) |
| 105 |
return false; |
| 106 |
if (Func->getNumParams() == 2 && |
| 107 |
!isIteratorType(Func->getParamDecl(1)->getType())) |
| 108 |
return false; |
| 109 |
return IdInfo->getName() == "erase"; |
| 110 |
} |
| 111 |
|
| 112 |
bool isEraseAfterCall(const FunctionDecl *Func) { |
| 113 |
const auto *IdInfo = Func->getIdentifier(); |
| 114 |
if (!IdInfo) |
| 115 |
return false; |
| 116 |
if (Func->getNumParams() < 1 || Func->getNumParams() > 2) |
| 117 |
return false; |
| 118 |
if (!isIteratorType(Func->getParamDecl(0)->getType())) |
| 119 |
return false; |
| 120 |
if (Func->getNumParams() == 2 && |
| 121 |
!isIteratorType(Func->getParamDecl(1)->getType())) |
| 122 |
return false; |
| 123 |
return IdInfo->getName() == "erase_after"; |
| 124 |
} |
| 125 |
|
| 126 |
bool isAccessOperator(OverloadedOperatorKind OK) { |
| 127 |
return isDereferenceOperator(OK) || isIncrementOperator(OK) || |
| 128 |
isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); |
| 129 |
} |
| 130 |
|
| 131 |
bool isAccessOperator(UnaryOperatorKind OK) { |
| 132 |
return isDereferenceOperator(OK) || isIncrementOperator(OK) || |
| 133 |
isDecrementOperator(OK); |
| 134 |
} |
| 135 |
|
| 136 |
bool isAccessOperator(BinaryOperatorKind OK) { |
| 137 |
return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK); |
| 138 |
} |
| 139 |
|
| 140 |
bool isDereferenceOperator(OverloadedOperatorKind OK) { |
| 141 |
return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || |
| 142 |
OK == OO_Subscript; |
| 143 |
} |
| 144 |
|
| 145 |
bool isDereferenceOperator(UnaryOperatorKind OK) { |
| 146 |
return OK == UO_Deref; |
| 147 |
} |
| 148 |
|
| 149 |
bool isDereferenceOperator(BinaryOperatorKind OK) { |
| 150 |
return OK == BO_PtrMemI; |
| 151 |
} |
| 152 |
|
| 153 |
bool isIncrementOperator(OverloadedOperatorKind OK) { |
| 154 |
return OK == OO_PlusPlus; |
| 155 |
} |
| 156 |
|
| 157 |
bool isIncrementOperator(UnaryOperatorKind OK) { |
| 158 |
return OK == UO_PreInc || OK == UO_PostInc; |
| 159 |
} |
| 160 |
|
| 161 |
bool isDecrementOperator(OverloadedOperatorKind OK) { |
| 162 |
return OK == OO_MinusMinus; |
| 163 |
} |
| 164 |
|
| 165 |
bool isDecrementOperator(UnaryOperatorKind OK) { |
| 166 |
return OK == UO_PreDec || OK == UO_PostDec; |
| 167 |
} |
| 168 |
|
| 169 |
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { |
| 170 |
return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || |
| 171 |
OK == OO_MinusEqual; |
| 172 |
} |
| 173 |
|
| 174 |
bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) { |
| 175 |
return OK == BO_Add || OK == BO_AddAssign || |
| 176 |
OK == BO_Sub || OK == BO_SubAssign; |
| 177 |
} |
| 178 |
|
| 179 |
const ContainerData *getContainerData(ProgramStateRef State, |
| 180 |
const MemRegion *Cont) { |
| 181 |
return State->get<ContainerMap>(Cont); |
| 182 |
} |
| 183 |
|
| 184 |
const IteratorPosition *getIteratorPosition(ProgramStateRef State, |
| 185 |
const SVal &Val) { |
| 186 |
if (auto Reg = Val.getAsRegion()) { |
| 187 |
Reg = Reg->getMostDerivedObjectRegion(); |
| 188 |
return State->get<IteratorRegionMap>(Reg); |
| 189 |
} else if (const auto Sym = Val.getAsSymbol()) { |
| 190 |
return State->get<IteratorSymbolMap>(Sym); |
| 191 |
} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { |
| 192 |
return State->get<IteratorRegionMap>(LCVal->getRegion()); |
| 193 |
} |
| 194 |
return nullptr; |
| 195 |
} |
| 196 |
|
| 197 |
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, |
| 198 |
const IteratorPosition &Pos) { |
| 199 |
if (auto Reg = Val.getAsRegion()) { |
| 200 |
Reg = Reg->getMostDerivedObjectRegion(); |
| 201 |
return State->set<IteratorRegionMap>(Reg, Pos); |
| 202 |
} else if (const auto Sym = Val.getAsSymbol()) { |
| 203 |
return State->set<IteratorSymbolMap>(Sym, Pos); |
| 204 |
} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { |
| 205 |
return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos); |
| 206 |
} |
| 207 |
return nullptr; |
| 208 |
} |
| 209 |
|
| 210 |
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, |
| 211 |
const MemRegion *Cont, const Stmt* S, |
| 212 |
const LocationContext *LCtx, |
| 213 |
unsigned blockCount) { |
| 214 |
auto &StateMgr = State->getStateManager(); |
| 215 |
auto &SymMgr = StateMgr.getSymbolManager(); |
| 216 |
auto &ACtx = StateMgr.getContext(); |
| 217 |
|
| 218 |
auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount); |
| 219 |
State = assumeNoOverflow(State, Sym, 4); |
| 220 |
return setIteratorPosition(State, Val, |
| 221 |
IteratorPosition::getPosition(Cont, Sym)); |
| 222 |
} |
| 223 |
|
| 224 |
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, |
| 225 |
OverloadedOperatorKind Op, |
| 226 |
const SVal &Distance) { |
| 227 |
const auto *Pos = getIteratorPosition(State, Iter); |
| 228 |
if (!Pos) |
| 229 |
return nullptr; |
| 230 |
|
| 231 |
auto &SymMgr = State->getStateManager().getSymbolManager(); |
| 232 |
auto &SVB = State->getStateManager().getSValBuilder(); |
| 233 |
auto &BVF = State->getStateManager().getBasicVals(); |
| 234 |
|
| 235 |
assert ((Op == OO_Plus || Op == OO_PlusEqual || |
| 236 |
Op == OO_Minus || Op == OO_MinusEqual) && |
| 237 |
"Advance operator must be one of +, -, += and -=."); |
| 238 |
auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; |
| 239 |
const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>(); |
| 240 |
if (!IntDistOp) |
| 241 |
return nullptr; |
| 242 |
|
| 243 |
// For concrete integers we can calculate the new position |
| 244 |
nonloc::ConcreteInt IntDist = *IntDistOp; |
| 245 |
|
| 246 |
if (IntDist.getValue().isNegative()) { |
| 247 |
IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue())); |
| 248 |
BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add; |
| 249 |
} |
| 250 |
const auto NewPos = |
| 251 |
Pos->setTo(SVB.evalBinOp(State, BinOp, |
| 252 |
nonloc::SymbolVal(Pos->getOffset()), |
| 253 |
IntDist, SymMgr.getType(Pos->getOffset())) |
| 254 |
.getAsSymbol()); |
| 255 |
return setIteratorPosition(State, Iter, NewPos); |
| 256 |
} |
| 257 |
|
| 258 |
// This function tells the analyzer's engine that symbols produced by our |
| 259 |
// checker, most notably iterator positions, are relatively small. |
| 260 |
// A distance between items in the container should not be very large. |
| 261 |
// By assuming that it is within around 1/8 of the address space, |
| 262 |
// we can help the analyzer perform operations on these symbols |
| 263 |
// without being afraid of integer overflows. |
| 264 |
// FIXME: Should we provide it as an API, so that all checkers could use it? |
| 265 |
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, |
| 266 |
long Scale) { |
| 267 |
SValBuilder &SVB = State->getStateManager().getSValBuilder(); |
| 268 |
BasicValueFactory &BV = SVB.getBasicValueFactory(); |
| 269 |
|
| 270 |
QualType T = Sym->getType(); |
| 271 |
assert(T->isSignedIntegerOrEnumerationType()); |
| 272 |
APSIntType AT = BV.getAPSIntType(T); |
| 273 |
|
| 274 |
ProgramStateRef NewState = State; |
| 275 |
|
| 276 |
llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); |
| 277 |
SVal IsCappedFromAbove = |
| 278 |
SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), |
| 279 |
nonloc::ConcreteInt(Max), SVB.getConditionType()); |
| 280 |
if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { |
| 281 |
NewState = NewState->assume(*DV, true); |
| 282 |
if (!NewState) |
| 283 |
return State; |
| 284 |
} |
| 285 |
|
| 286 |
llvm::APSInt Min = -Max; |
| 287 |
SVal IsCappedFromBelow = |
| 288 |
SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), |
| 289 |
nonloc::ConcreteInt(Min), SVB.getConditionType()); |
| 290 |
if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { |
| 291 |
NewState = NewState->assume(*DV, true); |
| 292 |
if (!NewState) |
| 293 |
return State; |
| 294 |
} |
| 295 |
|
| 296 |
return NewState; |
| 297 |
} |
| 298 |
|
| 299 |
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, |
| 300 |
BinaryOperator::Opcode Opc) { |
| 301 |
return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); |
| 302 |
} |
| 303 |
|
| 304 |
bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, |
| 305 |
BinaryOperator::Opcode Opc) { |
| 306 |
auto &SVB = State->getStateManager().getSValBuilder(); |
| 307 |
|
| 308 |
const auto comparison = |
| 309 |
SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()); |
| 310 |
|
| 311 |
assert(isa<DefinedSVal>(comparison) && |
| 312 |
"Symbol comparison must be a `DefinedSVal`"); |
| 313 |
|
| 314 |
return !State->assume(comparison.castAs<DefinedSVal>(), false); |
| 315 |
} |
| 316 |
|
| 317 |
} // namespace iterator |
| 318 |
} // namespace ento |
| 319 |
} // namespace clang |