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
15namespace clang {
16namespace ento {
17namespace iterator {
18
19bool 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
27bool isIterator(const CXXRecordDecl *CRD) {
28  if (!CRD)
29    return false;
30
31  const auto Name = CRD->getName();
32  if (!(Name.ends_with_insensitive("iterator") ||
33        Name.ends_with_insensitive("iter") || Name.ends_with_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
71bool 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
76bool 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
87bool 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
98bool 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
112bool 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
126bool isAccessOperator(OverloadedOperatorKind OK) {
127  return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
128         isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
129}
130
131bool isAccessOperator(UnaryOperatorKind OK) {
132  return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
133         isDecrementOperator(OK);
134}
135
136bool isAccessOperator(BinaryOperatorKind OK) {
137  return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
138}
139
140bool isDereferenceOperator(OverloadedOperatorKind OK) {
141  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
142         OK == OO_Subscript;
143}
144
145bool isDereferenceOperator(UnaryOperatorKind OK) {
146  return OK == UO_Deref;
147}
148
149bool isDereferenceOperator(BinaryOperatorKind OK) {
150  return OK == BO_PtrMemI;
151}
152
153bool isIncrementOperator(OverloadedOperatorKind OK) {
154  return OK == OO_PlusPlus;
155}
156
157bool isIncrementOperator(UnaryOperatorKind OK) {
158  return OK == UO_PreInc || OK == UO_PostInc;
159}
160
161bool isDecrementOperator(OverloadedOperatorKind OK) {
162  return OK == OO_MinusMinus;
163}
164
165bool isDecrementOperator(UnaryOperatorKind OK) {
166  return OK == UO_PreDec || OK == UO_PostDec;
167}
168
169bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
170  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
171         OK == OO_MinusEqual;
172}
173
174bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
175  return OK == BO_Add || OK == BO_AddAssign ||
176         OK == BO_Sub || OK == BO_SubAssign;
177}
178
179const ContainerData *getContainerData(ProgramStateRef State,
180                                      const MemRegion *Cont) {
181  return State->get<ContainerMap>(Cont);
182}
183
184const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val) {
185  if (auto Reg = Val.getAsRegion()) {
186    Reg = Reg->getMostDerivedObjectRegion();
187    return State->get<IteratorRegionMap>(Reg);
188  } else if (const auto Sym = Val.getAsSymbol()) {
189    return State->get<IteratorSymbolMap>(Sym);
190  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
191    return State->get<IteratorRegionMap>(LCVal->getRegion());
192  }
193  return nullptr;
194}
195
196ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,
197                                    const IteratorPosition &Pos) {
198  if (auto Reg = Val.getAsRegion()) {
199    Reg = Reg->getMostDerivedObjectRegion();
200    return State->set<IteratorRegionMap>(Reg, Pos);
201  } else if (const auto Sym = Val.getAsSymbol()) {
202    return State->set<IteratorSymbolMap>(Sym, Pos);
203  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
204    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
205  }
206  return nullptr;
207}
208
209ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,
210                                       const MemRegion *Cont, const Stmt *S,
211                                       const LocationContext *LCtx,
212                                       unsigned blockCount) {
213  auto &StateMgr = State->getStateManager();
214  auto &SymMgr = StateMgr.getSymbolManager();
215  auto &ACtx = StateMgr.getContext();
216
217  auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount);
218  State = assumeNoOverflow(State, Sym, 4);
219  return setIteratorPosition(State, Val,
220                             IteratorPosition::getPosition(Cont, Sym));
221}
222
223ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
224                                OverloadedOperatorKind Op, SVal Distance) {
225  const auto *Pos = getIteratorPosition(State, Iter);
226  if (!Pos)
227    return nullptr;
228
229  auto &SymMgr = State->getStateManager().getSymbolManager();
230  auto &SVB = State->getStateManager().getSValBuilder();
231  auto &BVF = State->getStateManager().getBasicVals();
232
233  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
234           Op == OO_Minus || Op == OO_MinusEqual) &&
235          "Advance operator must be one of +, -, += and -=.");
236  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
237  const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
238  if (!IntDistOp)
239    return nullptr;
240
241  // For concrete integers we can calculate the new position
242  nonloc::ConcreteInt IntDist = *IntDistOp;
243
244  if (IntDist.getValue().isNegative()) {
245    IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
246    BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
247  }
248  const auto NewPos =
249    Pos->setTo(SVB.evalBinOp(State, BinOp,
250                             nonloc::SymbolVal(Pos->getOffset()),
251                             IntDist, SymMgr.getType(Pos->getOffset()))
252               .getAsSymbol());
253  return setIteratorPosition(State, Iter, NewPos);
254}
255
256// This function tells the analyzer's engine that symbols produced by our
257// checker, most notably iterator positions, are relatively small.
258// A distance between items in the container should not be very large.
259// By assuming that it is within around 1/8 of the address space,
260// we can help the analyzer perform operations on these symbols
261// without being afraid of integer overflows.
262// FIXME: Should we provide it as an API, so that all checkers could use it?
263ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
264                                 long Scale) {
265  SValBuilder &SVB = State->getStateManager().getSValBuilder();
266  BasicValueFactory &BV = SVB.getBasicValueFactory();
267
268  QualType T = Sym->getType();
269  assert(T->isSignedIntegerOrEnumerationType());
270  APSIntType AT = BV.getAPSIntType(T);
271
272  ProgramStateRef NewState = State;
273
274  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
275  SVal IsCappedFromAbove =
276      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
277                      nonloc::ConcreteInt(Max), SVB.getConditionType());
278  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
279    NewState = NewState->assume(*DV, true);
280    if (!NewState)
281      return State;
282  }
283
284  llvm::APSInt Min = -Max;
285  SVal IsCappedFromBelow =
286      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
287                      nonloc::ConcreteInt(Min), SVB.getConditionType());
288  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
289    NewState = NewState->assume(*DV, true);
290    if (!NewState)
291      return State;
292  }
293
294  return NewState;
295}
296
297bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
298             BinaryOperator::Opcode Opc) {
299  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
300}
301
302bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
303             BinaryOperator::Opcode Opc) {
304  auto &SVB = State->getStateManager().getSValBuilder();
305
306  const auto comparison =
307    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
308
309  assert(isa<DefinedSVal>(comparison) &&
310         "Symbol comparison must be a `DefinedSVal`");
311
312  return !State->assume(comparison.castAs<DefinedSVal>(), false);
313}
314
315} // namespace iterator
316} // namespace ento
317} // namespace clang
318