Iterator.cpp revision 360784 
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.endswith_lower("iterator") || Name.endswith_lower("iter") ||
33        Name.endswith_lower("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 isDereferenceOperator(OverloadedOperatorKind OK) {
132  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
133         OK == OO_Subscript;
134}
135
136bool isIncrementOperator(OverloadedOperatorKind OK) {
137  return OK == OO_PlusPlus;
138}
139
140bool isDecrementOperator(OverloadedOperatorKind OK) {
141  return OK == OO_MinusMinus;
142}
143
144bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
145  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
146         OK == OO_MinusEqual;
147}
148
149const ContainerData *getContainerData(ProgramStateRef State,
150                                      const MemRegion *Cont) {
151  return State->get<ContainerMap>(Cont);
152}
153
154const IteratorPosition *getIteratorPosition(ProgramStateRef State,
155                                            const SVal &Val) {
156  if (auto Reg = Val.getAsRegion()) {
157    Reg = Reg->getMostDerivedObjectRegion();
158    return State->get<IteratorRegionMap>(Reg);
159  } else if (const auto Sym = Val.getAsSymbol()) {
160    return State->get<IteratorSymbolMap>(Sym);
161  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
162    return State->get<IteratorRegionMap>(LCVal->getRegion());
163  }
164  return nullptr;
165}
166
167ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
168                                    const IteratorPosition &Pos) {
169  if (auto Reg = Val.getAsRegion()) {
170    Reg = Reg->getMostDerivedObjectRegion();
171    return State->set<IteratorRegionMap>(Reg, Pos);
172  } else if (const auto Sym = Val.getAsSymbol()) {
173    return State->set<IteratorSymbolMap>(Sym, Pos);
174  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
175    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
176  }
177  return nullptr;
178}
179
180ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
181                                OverloadedOperatorKind Op,
182                                const SVal &Distance) {
183  const auto *Pos = getIteratorPosition(State, Iter);
184  if (!Pos)
185    return nullptr;
186
187  auto &SymMgr = State->getStateManager().getSymbolManager();
188  auto &SVB = State->getStateManager().getSValBuilder();
189
190  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
191           Op == OO_Minus || Op == OO_MinusEqual) &&
192          "Advance operator must be one of +, -, += and -=.");
193  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
194  if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
195    // For concrete integers we can calculate the new position
196    const auto NewPos =
197      Pos->setTo(SVB.evalBinOp(State, BinOp,
198                               nonloc::SymbolVal(Pos->getOffset()),
199                               *IntDist, SymMgr.getType(Pos->getOffset()))
200                 .getAsSymbol());
201    return setIteratorPosition(State, Iter, NewPos);
202  }
203
204  return nullptr;
205}
206
207bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
208             BinaryOperator::Opcode Opc) {
209  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
210}
211
212bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
213             BinaryOperator::Opcode Opc) {
214  auto &SVB = State->getStateManager().getSValBuilder();
215
216  const auto comparison =
217    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
218
219  assert(comparison.getAs<DefinedSVal>() &&
220    "Symbol comparison must be a `DefinedSVal`");
221
222  return !State->assume(comparison.castAs<DefinedSVal>(), false);
223}
224
225} // namespace iterator
226} // namespace ento
227} // namespace clang
228