1480093f4SDimitry Andric //=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
2480093f4SDimitry Andric //
3480093f4SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4480093f4SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5480093f4SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6480093f4SDimitry Andric //
7480093f4SDimitry Andric //===----------------------------------------------------------------------===//
8480093f4SDimitry Andric //
9480093f4SDimitry Andric // Defines common functions to be used by the itertor checkers .
10480093f4SDimitry Andric //
11480093f4SDimitry Andric //===----------------------------------------------------------------------===//
12480093f4SDimitry Andric
13480093f4SDimitry Andric #include "Iterator.h"
14480093f4SDimitry Andric
15480093f4SDimitry Andric namespace clang {
16480093f4SDimitry Andric namespace ento {
17480093f4SDimitry Andric namespace iterator {
18480093f4SDimitry Andric
isIteratorType(const QualType & Type)19480093f4SDimitry Andric bool isIteratorType(const QualType &Type) {
20480093f4SDimitry Andric if (Type->isPointerType())
21480093f4SDimitry Andric return true;
22480093f4SDimitry Andric
23480093f4SDimitry Andric const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24480093f4SDimitry Andric return isIterator(CRD);
25480093f4SDimitry Andric }
26480093f4SDimitry Andric
isIterator(const CXXRecordDecl * CRD)27480093f4SDimitry Andric bool isIterator(const CXXRecordDecl *CRD) {
28480093f4SDimitry Andric if (!CRD)
29480093f4SDimitry Andric return false;
30480093f4SDimitry Andric
31480093f4SDimitry Andric const auto Name = CRD->getName();
3206c3fb27SDimitry Andric if (!(Name.ends_with_insensitive("iterator") ||
3306c3fb27SDimitry Andric Name.ends_with_insensitive("iter") || Name.ends_with_insensitive("it")))
34480093f4SDimitry Andric return false;
35480093f4SDimitry Andric
36480093f4SDimitry Andric bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
37480093f4SDimitry Andric HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
38480093f4SDimitry Andric for (const auto *Method : CRD->methods()) {
39480093f4SDimitry Andric if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
40480093f4SDimitry Andric if (Ctor->isCopyConstructor()) {
41480093f4SDimitry Andric HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
42480093f4SDimitry Andric }
43480093f4SDimitry Andric continue;
44480093f4SDimitry Andric }
45480093f4SDimitry Andric if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
46480093f4SDimitry Andric HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
47480093f4SDimitry Andric continue;
48480093f4SDimitry Andric }
49480093f4SDimitry Andric if (Method->isCopyAssignmentOperator()) {
50480093f4SDimitry Andric HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
51480093f4SDimitry Andric continue;
52480093f4SDimitry Andric }
53480093f4SDimitry Andric if (!Method->isOverloadedOperator())
54480093f4SDimitry Andric continue;
55480093f4SDimitry Andric const auto OPK = Method->getOverloadedOperator();
56480093f4SDimitry Andric if (OPK == OO_PlusPlus) {
57480093f4SDimitry Andric HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
58480093f4SDimitry Andric HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
59480093f4SDimitry Andric continue;
60480093f4SDimitry Andric }
61480093f4SDimitry Andric if (OPK == OO_Star) {
62480093f4SDimitry Andric HasDerefOp = (Method->getNumParams() == 0);
63480093f4SDimitry Andric continue;
64480093f4SDimitry Andric }
65480093f4SDimitry Andric }
66480093f4SDimitry Andric
67480093f4SDimitry Andric return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
68480093f4SDimitry Andric HasPostIncrOp && HasDerefOp;
69480093f4SDimitry Andric }
70480093f4SDimitry Andric
isComparisonOperator(OverloadedOperatorKind OK)71480093f4SDimitry Andric bool isComparisonOperator(OverloadedOperatorKind OK) {
72480093f4SDimitry Andric return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
73480093f4SDimitry Andric OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
74480093f4SDimitry Andric }
75480093f4SDimitry Andric
isInsertCall(const FunctionDecl * Func)76480093f4SDimitry Andric bool isInsertCall(const FunctionDecl *Func) {
77480093f4SDimitry Andric const auto *IdInfo = Func->getIdentifier();
78480093f4SDimitry Andric if (!IdInfo)
79480093f4SDimitry Andric return false;
80480093f4SDimitry Andric if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
81480093f4SDimitry Andric return false;
82480093f4SDimitry Andric if (!isIteratorType(Func->getParamDecl(0)->getType()))
83480093f4SDimitry Andric return false;
84480093f4SDimitry Andric return IdInfo->getName() == "insert";
85480093f4SDimitry Andric }
86480093f4SDimitry Andric
isEmplaceCall(const FunctionDecl * Func)87480093f4SDimitry Andric bool isEmplaceCall(const FunctionDecl *Func) {
88480093f4SDimitry Andric const auto *IdInfo = Func->getIdentifier();
89480093f4SDimitry Andric if (!IdInfo)
90480093f4SDimitry Andric return false;
91480093f4SDimitry Andric if (Func->getNumParams() < 2)
92480093f4SDimitry Andric return false;
93480093f4SDimitry Andric if (!isIteratorType(Func->getParamDecl(0)->getType()))
94480093f4SDimitry Andric return false;
95480093f4SDimitry Andric return IdInfo->getName() == "emplace";
96480093f4SDimitry Andric }
97480093f4SDimitry Andric
isEraseCall(const FunctionDecl * Func)98480093f4SDimitry Andric bool isEraseCall(const FunctionDecl *Func) {
99480093f4SDimitry Andric const auto *IdInfo = Func->getIdentifier();
100480093f4SDimitry Andric if (!IdInfo)
101480093f4SDimitry Andric return false;
102480093f4SDimitry Andric if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
103480093f4SDimitry Andric return false;
104480093f4SDimitry Andric if (!isIteratorType(Func->getParamDecl(0)->getType()))
105480093f4SDimitry Andric return false;
106480093f4SDimitry Andric if (Func->getNumParams() == 2 &&
107480093f4SDimitry Andric !isIteratorType(Func->getParamDecl(1)->getType()))
108480093f4SDimitry Andric return false;
109480093f4SDimitry Andric return IdInfo->getName() == "erase";
110480093f4SDimitry Andric }
111480093f4SDimitry Andric
isEraseAfterCall(const FunctionDecl * Func)112480093f4SDimitry Andric bool isEraseAfterCall(const FunctionDecl *Func) {
113480093f4SDimitry Andric const auto *IdInfo = Func->getIdentifier();
114480093f4SDimitry Andric if (!IdInfo)
115480093f4SDimitry Andric return false;
116480093f4SDimitry Andric if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
117480093f4SDimitry Andric return false;
118480093f4SDimitry Andric if (!isIteratorType(Func->getParamDecl(0)->getType()))
119480093f4SDimitry Andric return false;
120480093f4SDimitry Andric if (Func->getNumParams() == 2 &&
121480093f4SDimitry Andric !isIteratorType(Func->getParamDecl(1)->getType()))
122480093f4SDimitry Andric return false;
123480093f4SDimitry Andric return IdInfo->getName() == "erase_after";
124480093f4SDimitry Andric }
125480093f4SDimitry Andric
isAccessOperator(OverloadedOperatorKind OK)126480093f4SDimitry Andric bool isAccessOperator(OverloadedOperatorKind OK) {
127480093f4SDimitry Andric return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
128480093f4SDimitry Andric isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
129480093f4SDimitry Andric }
130480093f4SDimitry Andric
isAccessOperator(UnaryOperatorKind OK)1315ffd83dbSDimitry Andric bool isAccessOperator(UnaryOperatorKind OK) {
1325ffd83dbSDimitry Andric return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
1335ffd83dbSDimitry Andric isDecrementOperator(OK);
1345ffd83dbSDimitry Andric }
1355ffd83dbSDimitry Andric
isAccessOperator(BinaryOperatorKind OK)1365ffd83dbSDimitry Andric bool isAccessOperator(BinaryOperatorKind OK) {
1375ffd83dbSDimitry Andric return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
1385ffd83dbSDimitry Andric }
1395ffd83dbSDimitry Andric
isDereferenceOperator(OverloadedOperatorKind OK)140480093f4SDimitry Andric bool isDereferenceOperator(OverloadedOperatorKind OK) {
141480093f4SDimitry Andric return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
142480093f4SDimitry Andric OK == OO_Subscript;
143480093f4SDimitry Andric }
144480093f4SDimitry Andric
isDereferenceOperator(UnaryOperatorKind OK)1455ffd83dbSDimitry Andric bool isDereferenceOperator(UnaryOperatorKind OK) {
1465ffd83dbSDimitry Andric return OK == UO_Deref;
1475ffd83dbSDimitry Andric }
1485ffd83dbSDimitry Andric
isDereferenceOperator(BinaryOperatorKind OK)1495ffd83dbSDimitry Andric bool isDereferenceOperator(BinaryOperatorKind OK) {
1505ffd83dbSDimitry Andric return OK == BO_PtrMemI;
1515ffd83dbSDimitry Andric }
1525ffd83dbSDimitry Andric
isIncrementOperator(OverloadedOperatorKind OK)153480093f4SDimitry Andric bool isIncrementOperator(OverloadedOperatorKind OK) {
154480093f4SDimitry Andric return OK == OO_PlusPlus;
155480093f4SDimitry Andric }
156480093f4SDimitry Andric
isIncrementOperator(UnaryOperatorKind OK)1575ffd83dbSDimitry Andric bool isIncrementOperator(UnaryOperatorKind OK) {
1585ffd83dbSDimitry Andric return OK == UO_PreInc || OK == UO_PostInc;
1595ffd83dbSDimitry Andric }
1605ffd83dbSDimitry Andric
isDecrementOperator(OverloadedOperatorKind OK)161480093f4SDimitry Andric bool isDecrementOperator(OverloadedOperatorKind OK) {
162480093f4SDimitry Andric return OK == OO_MinusMinus;
163480093f4SDimitry Andric }
164480093f4SDimitry Andric
isDecrementOperator(UnaryOperatorKind OK)1655ffd83dbSDimitry Andric bool isDecrementOperator(UnaryOperatorKind OK) {
1665ffd83dbSDimitry Andric return OK == UO_PreDec || OK == UO_PostDec;
1675ffd83dbSDimitry Andric }
1685ffd83dbSDimitry Andric
isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)169480093f4SDimitry Andric bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
170480093f4SDimitry Andric return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
171480093f4SDimitry Andric OK == OO_MinusEqual;
172480093f4SDimitry Andric }
173480093f4SDimitry Andric
isRandomIncrOrDecrOperator(BinaryOperatorKind OK)1745ffd83dbSDimitry Andric bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
1755ffd83dbSDimitry Andric return OK == BO_Add || OK == BO_AddAssign ||
1765ffd83dbSDimitry Andric OK == BO_Sub || OK == BO_SubAssign;
1775ffd83dbSDimitry Andric }
1785ffd83dbSDimitry Andric
getContainerData(ProgramStateRef State,const MemRegion * Cont)179480093f4SDimitry Andric const ContainerData *getContainerData(ProgramStateRef State,
180480093f4SDimitry Andric const MemRegion *Cont) {
181480093f4SDimitry Andric return State->get<ContainerMap>(Cont);
182480093f4SDimitry Andric }
183480093f4SDimitry Andric
getIteratorPosition(ProgramStateRef State,SVal Val)184*647cbc5dSDimitry Andric const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val) {
185480093f4SDimitry Andric if (auto Reg = Val.getAsRegion()) {
186480093f4SDimitry Andric Reg = Reg->getMostDerivedObjectRegion();
187480093f4SDimitry Andric return State->get<IteratorRegionMap>(Reg);
188480093f4SDimitry Andric } else if (const auto Sym = Val.getAsSymbol()) {
189480093f4SDimitry Andric return State->get<IteratorSymbolMap>(Sym);
190480093f4SDimitry Andric } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
191480093f4SDimitry Andric return State->get<IteratorRegionMap>(LCVal->getRegion());
192480093f4SDimitry Andric }
193480093f4SDimitry Andric return nullptr;
194480093f4SDimitry Andric }
195480093f4SDimitry Andric
setIteratorPosition(ProgramStateRef State,SVal Val,const IteratorPosition & Pos)196*647cbc5dSDimitry Andric ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,
197480093f4SDimitry Andric const IteratorPosition &Pos) {
198480093f4SDimitry Andric if (auto Reg = Val.getAsRegion()) {
199480093f4SDimitry Andric Reg = Reg->getMostDerivedObjectRegion();
200480093f4SDimitry Andric return State->set<IteratorRegionMap>(Reg, Pos);
201480093f4SDimitry Andric } else if (const auto Sym = Val.getAsSymbol()) {
202480093f4SDimitry Andric return State->set<IteratorSymbolMap>(Sym, Pos);
203480093f4SDimitry Andric } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
204480093f4SDimitry Andric return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
205480093f4SDimitry Andric }
206480093f4SDimitry Andric return nullptr;
207480093f4SDimitry Andric }
208480093f4SDimitry Andric
createIteratorPosition(ProgramStateRef State,SVal Val,const MemRegion * Cont,const Stmt * S,const LocationContext * LCtx,unsigned blockCount)209*647cbc5dSDimitry Andric ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,
2105ffd83dbSDimitry Andric const MemRegion *Cont, const Stmt *S,
2115ffd83dbSDimitry Andric const LocationContext *LCtx,
2125ffd83dbSDimitry Andric unsigned blockCount) {
2135ffd83dbSDimitry Andric auto &StateMgr = State->getStateManager();
2145ffd83dbSDimitry Andric auto &SymMgr = StateMgr.getSymbolManager();
2155ffd83dbSDimitry Andric auto &ACtx = StateMgr.getContext();
2165ffd83dbSDimitry Andric
2175ffd83dbSDimitry Andric auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount);
2185ffd83dbSDimitry Andric State = assumeNoOverflow(State, Sym, 4);
2195ffd83dbSDimitry Andric return setIteratorPosition(State, Val,
2205ffd83dbSDimitry Andric IteratorPosition::getPosition(Cont, Sym));
2215ffd83dbSDimitry Andric }
2225ffd83dbSDimitry Andric
advancePosition(ProgramStateRef State,SVal Iter,OverloadedOperatorKind Op,SVal Distance)223*647cbc5dSDimitry Andric ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
224*647cbc5dSDimitry Andric OverloadedOperatorKind Op, SVal Distance) {
225480093f4SDimitry Andric const auto *Pos = getIteratorPosition(State, Iter);
226480093f4SDimitry Andric if (!Pos)
227480093f4SDimitry Andric return nullptr;
228480093f4SDimitry Andric
229480093f4SDimitry Andric auto &SymMgr = State->getStateManager().getSymbolManager();
230480093f4SDimitry Andric auto &SVB = State->getStateManager().getSValBuilder();
2315ffd83dbSDimitry Andric auto &BVF = State->getStateManager().getBasicVals();
232480093f4SDimitry Andric
233480093f4SDimitry Andric assert ((Op == OO_Plus || Op == OO_PlusEqual ||
234480093f4SDimitry Andric Op == OO_Minus || Op == OO_MinusEqual) &&
235480093f4SDimitry Andric "Advance operator must be one of +, -, += and -=.");
236480093f4SDimitry Andric auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
2375ffd83dbSDimitry Andric const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
2385ffd83dbSDimitry Andric if (!IntDistOp)
2395ffd83dbSDimitry Andric return nullptr;
2405ffd83dbSDimitry Andric
241480093f4SDimitry Andric // For concrete integers we can calculate the new position
2425ffd83dbSDimitry Andric nonloc::ConcreteInt IntDist = *IntDistOp;
2435ffd83dbSDimitry Andric
2445ffd83dbSDimitry Andric if (IntDist.getValue().isNegative()) {
2455ffd83dbSDimitry Andric IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
2465ffd83dbSDimitry Andric BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
2475ffd83dbSDimitry Andric }
248480093f4SDimitry Andric const auto NewPos =
249480093f4SDimitry Andric Pos->setTo(SVB.evalBinOp(State, BinOp,
250480093f4SDimitry Andric nonloc::SymbolVal(Pos->getOffset()),
2515ffd83dbSDimitry Andric IntDist, SymMgr.getType(Pos->getOffset()))
252480093f4SDimitry Andric .getAsSymbol());
253480093f4SDimitry Andric return setIteratorPosition(State, Iter, NewPos);
254480093f4SDimitry Andric }
255480093f4SDimitry Andric
2565ffd83dbSDimitry Andric // This function tells the analyzer's engine that symbols produced by our
2575ffd83dbSDimitry Andric // checker, most notably iterator positions, are relatively small.
2585ffd83dbSDimitry Andric // A distance between items in the container should not be very large.
2595ffd83dbSDimitry Andric // By assuming that it is within around 1/8 of the address space,
2605ffd83dbSDimitry Andric // we can help the analyzer perform operations on these symbols
2615ffd83dbSDimitry Andric // without being afraid of integer overflows.
2625ffd83dbSDimitry Andric // FIXME: Should we provide it as an API, so that all checkers could use it?
assumeNoOverflow(ProgramStateRef State,SymbolRef Sym,long Scale)2635ffd83dbSDimitry Andric ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
2645ffd83dbSDimitry Andric long Scale) {
2655ffd83dbSDimitry Andric SValBuilder &SVB = State->getStateManager().getSValBuilder();
2665ffd83dbSDimitry Andric BasicValueFactory &BV = SVB.getBasicValueFactory();
2675ffd83dbSDimitry Andric
2685ffd83dbSDimitry Andric QualType T = Sym->getType();
2695ffd83dbSDimitry Andric assert(T->isSignedIntegerOrEnumerationType());
2705ffd83dbSDimitry Andric APSIntType AT = BV.getAPSIntType(T);
2715ffd83dbSDimitry Andric
2725ffd83dbSDimitry Andric ProgramStateRef NewState = State;
2735ffd83dbSDimitry Andric
2745ffd83dbSDimitry Andric llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
2755ffd83dbSDimitry Andric SVal IsCappedFromAbove =
2765ffd83dbSDimitry Andric SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
2775ffd83dbSDimitry Andric nonloc::ConcreteInt(Max), SVB.getConditionType());
2785ffd83dbSDimitry Andric if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
2795ffd83dbSDimitry Andric NewState = NewState->assume(*DV, true);
2805ffd83dbSDimitry Andric if (!NewState)
2815ffd83dbSDimitry Andric return State;
2825ffd83dbSDimitry Andric }
2835ffd83dbSDimitry Andric
2845ffd83dbSDimitry Andric llvm::APSInt Min = -Max;
2855ffd83dbSDimitry Andric SVal IsCappedFromBelow =
2865ffd83dbSDimitry Andric SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
2875ffd83dbSDimitry Andric nonloc::ConcreteInt(Min), SVB.getConditionType());
2885ffd83dbSDimitry Andric if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
2895ffd83dbSDimitry Andric NewState = NewState->assume(*DV, true);
2905ffd83dbSDimitry Andric if (!NewState)
2915ffd83dbSDimitry Andric return State;
2925ffd83dbSDimitry Andric }
2935ffd83dbSDimitry Andric
2945ffd83dbSDimitry Andric return NewState;
295480093f4SDimitry Andric }
296480093f4SDimitry Andric
compare(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2,BinaryOperator::Opcode Opc)297480093f4SDimitry Andric bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
298480093f4SDimitry Andric BinaryOperator::Opcode Opc) {
299480093f4SDimitry Andric return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
300480093f4SDimitry Andric }
301480093f4SDimitry Andric
compare(ProgramStateRef State,NonLoc NL1,NonLoc NL2,BinaryOperator::Opcode Opc)302480093f4SDimitry Andric bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
303480093f4SDimitry Andric BinaryOperator::Opcode Opc) {
304480093f4SDimitry Andric auto &SVB = State->getStateManager().getSValBuilder();
305480093f4SDimitry Andric
306480093f4SDimitry Andric const auto comparison =
307480093f4SDimitry Andric SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
308480093f4SDimitry Andric
30981ad6265SDimitry Andric assert(isa<DefinedSVal>(comparison) &&
310480093f4SDimitry Andric "Symbol comparison must be a `DefinedSVal`");
311480093f4SDimitry Andric
312480093f4SDimitry Andric return !State->assume(comparison.castAs<DefinedSVal>(), false);
313480093f4SDimitry Andric }
314480093f4SDimitry Andric
315480093f4SDimitry Andric } // namespace iterator
316480093f4SDimitry Andric } // namespace ento
317480093f4SDimitry Andric } // namespace clang
318