/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

Source (jump to first uncovered line)
//=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Defines common functions to be used by the itertor checkers .
//
//===----------------------------------------------------------------------===//

#include "Iterator.h"

namespace clang {
namespace ento {
namespace iterator {

bool isIteratorType(const QualType &Type) {
  if (Type->isPointerType())
    return true;

  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
  return isIterator(CRD);
}

bool isIterator(const CXXRecordDecl *CRD) {
  if (!CRD)
    return false;

  const auto Name = CRD->getName();
  if (!(Name.ends_with_insensitive("iterator") ||
        Name.ends_with_insensitive("iter")209 || Name.ends_with_insensitive("it")209))
    return false;

  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
  for (const auto *Method : CRD->methods()) {
    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
      if (Ctor->isCopyConstructor()) {
        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
      }
      continue;
    }
    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
      continue;
    }
    if (Method->isCopyAssignmentOperator()) {
      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
      continue;
    }
    if (!Method->isOverloadedOperator())
      continue;
    const auto OPK = Method->getOverloadedOperator();
    if (OPK == OO_PlusPlus) {
      HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0)7.44k;
      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
      continue;
    }
    if (OPK == OO_Star) {
      HasDerefOp = (Method->getNumParams() == 0);
      continue;
    }
  }

  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
         HasPostIncrOp && HasDerefOp;
}

bool isComparisonOperator(OverloadedOperatorKind OK) {
  return OK == OO_EqualEqual || OK == OO_ExclaimEqual42 || OK == OO_Less32 ||
         OK == OO_LessEqual32 || OK == OO_Greater32 || OK == OO_GreaterEqual32;
}

bool isInsertCall(const FunctionDecl *Func) {
  const auto *IdInfo = Func->getIdentifier();
  if (!IdInfo)
    return false;
  if (Func->getNumParams() < 2 || Func->getNumParams() > 326)
    return false;
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
    return false;
  return IdInfo->getName() == "insert";
}

bool isEmplaceCall(const FunctionDecl *Func) {
  const auto *IdInfo = Func->getIdentifier();
  if (!IdInfo)
    return false;
  if (Func->getNumParams() < 2)
    return false;
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
    return false;
  return IdInfo->getName() == "emplace";
}

bool isEraseCall(const FunctionDecl *Func) {
  const auto *IdInfo = Func->getIdentifier();
  if (!IdInfo)
    return false;
  if (Func->getNumParams() < 1 || Func->getNumParams() > 240)
    return false;
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
    return false;
  if (Func->getNumParams() == 2 &&
      !isIteratorType(Func->getParamDecl(1)->getType())22)
    return false;
  return IdInfo->getName() == "erase";
}

bool isEraseAfterCall(const FunctionDecl *Func) {
  const auto *IdInfo = Func->getIdentifier();
  if (!IdInfo)
    return false;
  if (Func->getNumParams() < 1 || Func->getNumParams() > 226)
    return false;
  if (!isIteratorType(Func->getParamDecl(0)->getType()))
    return false;
  if (Func->getNumParams() == 2 &&
      !isIteratorType(Func->getParamDecl(1)->getType()))
    return false;
  return IdInfo->getName() == "erase_after";
}

bool isAccessOperator(OverloadedOperatorKind OK) {
  return isDereferenceOperator(OK) || isIncrementOperator(OK)40 ||
         isDecrementOperator(OK)24 || isRandomIncrOrDecrOperator(OK)16;
}

bool isAccessOperator(UnaryOperatorKind OK) {
  return isDereferenceOperator(OK) || isIncrementOperator(OK)16 ||
         isDecrementOperator(OK)6;
}

bool isAccessOperator(BinaryOperatorKind OK) {
  return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
}

bool isDereferenceOperator(OverloadedOperatorKind OK) {
  return OK == OO_Star || OK == OO_Arrow78 || OK == OO_ArrowStar74 ||
         OK == OO_Subscript74;
}

bool isDereferenceOperator(UnaryOperatorKind OK) {
  return OK == UO_Deref;
}

bool isDereferenceOperator(BinaryOperatorKind OK) {
  return OK == BO_PtrMemI;
}

bool isIncrementOperator(OverloadedOperatorKind OK) {
  return OK == OO_PlusPlus;
}

bool isIncrementOperator(UnaryOperatorKind OK) {
  return OK == UO_PreInc || OK == UO_PostInc1.15k;
}

bool isDecrementOperator(OverloadedOperatorKind OK) {
  return OK == OO_MinusMinus;
}

bool isDecrementOperator(UnaryOperatorKind OK) {
  return OK == UO_PreDec || OK == UO_PostDec801;
}

bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
  return OK == OO_Plus || OK == OO_PlusEqual1.12k || OK == OO_Minus839 ||
         OK == OO_MinusEqual795;
}

bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
  return OK == BO_Add || OK == BO_AddAssign542 ||
         OK == BO_Sub394 || OK == BO_SubAssign348;
}

const ContainerData *getContainerData(ProgramStateRef State,
                                      const MemRegion *Cont) {
  return State->get<ContainerMap>(Cont);
}

const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                            const SVal &Val) {
  if (auto Reg = Val.getAsRegion()) {
    Reg = Reg->getMostDerivedObjectRegion();
    return State->get<IteratorRegionMap>(Reg);
  } else if (const auto 13.8kSym13.8k = Val.getAsSymbol()) {
    return State->get<IteratorSymbolMap>(Sym);
  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
    return State->get<IteratorRegionMap>(LCVal->getRegion());
  }
  return nullptr;
}

ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                    const IteratorPosition &Pos) {
  if (auto Reg = Val.getAsRegion()) {
    Reg = Reg->getMostDerivedObjectRegion();
    return State->set<IteratorRegionMap>(Reg, Pos);
  } else if (const auto 3.73kSym3.73k = Val.getAsSymbol()) {
    return State->set<IteratorSymbolMap>(Sym, Pos);
  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
  }
  return nullptr;
}

ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
                                       const MemRegion *Cont, const Stmt* S,
                                       const LocationContext *LCtx,
                                       unsigned blockCount) {
  auto &StateMgr = State->getStateManager();
  auto &SymMgr = StateMgr.getSymbolManager();
  auto &ACtx = StateMgr.getContext();

  auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount);
  State = assumeNoOverflow(State, Sym, 4);
  return setIteratorPosition(State, Val,
                             IteratorPosition::getPosition(Cont, Sym));
}

ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
                                OverloadedOperatorKind Op,
                                const SVal &Distance) {
  const auto *Pos = getIteratorPosition(State, Iter);
  if (!Pos)
    return nullptr;

  auto &SymMgr = State->getStateManager().getSymbolManager();
  auto &SVB = State->getStateManager().getSValBuilder();
  auto &BVF = State->getStateManager().getBasicVals();

  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
           Op == OO_Minus || Op == OO_MinusEqual) &&
          "Advance operator must be one of +, -, += and -=.");
  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual916) ? BO_Add896 : BO_Sub518;
  const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
  if (!IntDistOp)
    return nullptr;

  // For concrete integers we can calculate the new position
  nonloc::ConcreteInt IntDist = *IntDistOp;

  if (IntDist.getValue().isNegative()) {
    IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
    BinOp = (BinOp == BO_Add) ? BO_Sub186 : BO_Add32;
  }
  const auto NewPos =
    Pos->setTo(SVB.evalBinOp(State, BinOp,
                             nonloc::SymbolVal(Pos->getOffset()),
                             IntDist, SymMgr.getType(Pos->getOffset()))
               .getAsSymbol());
  return setIteratorPosition(State, Iter, NewPos);
}

// This function tells the analyzer's engine that symbols produced by our
// checker, most notably iterator positions, are relatively small.
// A distance between items in the container should not be very large.
// By assuming that it is within around 1/8 of the address space,
// we can help the analyzer perform operations on these symbols
// without being afraid of integer overflows.
// FIXME: Should we provide it as an API, so that all checkers could use it?
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
                                 long Scale) {
  SValBuilder &SVB = State->getStateManager().getSValBuilder();
  BasicValueFactory &BV = SVB.getBasicValueFactory();

  QualType T = Sym->getType();
  assert(T->isSignedIntegerOrEnumerationType());
  APSIntType AT = BV.getAPSIntType(T);

  ProgramStateRef NewState = State;

  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
  SVal IsCappedFromAbove =
      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
                      nonloc::ConcreteInt(Max), SVB.getConditionType());
  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
    NewState = NewState->assume(*DV, true);
    if (!NewState)
      return State;
  }

  llvm::APSInt Min = -Max;
  SVal IsCappedFromBelow =
      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
                      nonloc::ConcreteInt(Min), SVB.getConditionType());
  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
    NewState = NewState->assume(*DV, true);
    if (!NewState)
      return State;
  }

  return NewState;
}

bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
             BinaryOperator::Opcode Opc) {
  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
}

bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
             BinaryOperator::Opcode Opc) {
  auto &SVB = State->getStateManager().getSValBuilder();

  const auto comparison =
    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());

  assert(isa<DefinedSVal>(comparison) &&
         "Symbol comparison must be a `DefinedSVal`");

  return !State->assume(comparison.castAs<DefinedSVal>(), false);
}

} // namespace iterator
} // namespace ento
} // namespace clang

Coverage Report

Created: 2023-09-21 18:56

Line	Count	Source (jump to first uncovered line)
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	18.9k	bool isIteratorType(const QualType &Type) {
20	18.9k	if (Type->isPointerType())
21	1.85k	return true;
22
23	17.0k	const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24	17.0k	return isIterator(CRD);
25	18.9k	}
26
27	17.0k	bool isIterator(const CXXRecordDecl *CRD) {
28	17.0k	if (!CRD)
29	9.41k	return false;
30
31	7.65k	const auto Name = CRD->getName();
32	7.65k	if (!(Name.ends_with_insensitive("iterator") \|\|
33	7.65k	Name.ends_with_insensitive("iter")209 \|\| Name.ends_with_insensitive("it")209 ))
34	209	return false;
35
36	7.44k	bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
37	7.44k	HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
38	143k	for (const auto *Method : CRD->methods()) {
39	143k	if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
40	26.2k	if (Ctor->isCopyConstructor()) {
41	7.44k	HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
42	7.44k	}
43	26.2k	continue;
44	26.2k	}
45	117k	if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
46	7.44k	HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
47	7.44k	continue;
48	7.44k	}
49	109k	if (Method->isCopyAssignmentOperator()) {
50	12	HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
51	12	continue;
52	12	}
53	109k	if (!Method->isOverloadedOperator())
54	7.43k	continue;
55	102k	const auto OPK = Method->getOverloadedOperator();
56	102k	if (OPK == OO_PlusPlus) {
57	14.8k	HasPreIncrOp = HasPreIncrOp \|\| (Method->getNumParams() == 0)7.44k ;
58	14.8k	HasPostIncrOp = HasPostIncrOp \|\| (Method->getNumParams() == 1);
59	14.8k	continue;
60	14.8k	}
61	87.3k	if (OPK == OO_Star) {
62	7.44k	HasDerefOp = (Method->getNumParams() == 0);
63	7.44k	continue;
64	7.44k	}
65	87.3k	}
66
67	7.44k	return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
68	7.44k	HasPostIncrOp && HasDerefOp;
69	7.65k	}
70
71	46	bool isComparisonOperator(OverloadedOperatorKind OK) {
72	46	return OK == OO_EqualEqual \|\| OK == OO_ExclaimEqual42 \|\| OK == OO_Less32 \|\|
73	46	OK == OO_LessEqual32 \|\| OK == OO_Greater32 \|\| OK == OO_GreaterEqual32 ;
74	46	}
75
76	208	bool isInsertCall(const FunctionDecl *Func) {
77	208	const auto *IdInfo = Func->getIdentifier();
78	208	if (!IdInfo)
79	36	return false;
80	172	if (Func->getNumParams() < 2 \|\| Func->getNumParams() > 326 )
81	146	return false;
82	26	if (!isIteratorType(Func->getParamDecl(0)->getType()))
83	0	return false;
84	26	return IdInfo->getName() == "insert";
85	26	}
86
87	186	bool isEmplaceCall(const FunctionDecl *Func) {
88	186	const auto *IdInfo = Func->getIdentifier();
89	186	if (!IdInfo)
90	36	return false;
91	150	if (Func->getNumParams() < 2)
92	146	return false;
93	4	if (!isIteratorType(Func->getParamDecl(0)->getType()))
94	0	return false;
95	4	return IdInfo->getName() == "emplace";
96	4	}
97
98	222	bool isEraseCall(const FunctionDecl *Func) {
99	222	const auto *IdInfo = Func->getIdentifier();
100	222	if (!IdInfo)
101	36	return false;
102	186	if (Func->getNumParams() < 1 \|\| Func->getNumParams() > 240 )
103	158	return false;
104	28	if (!isIteratorType(Func->getParamDecl(0)->getType()))
105	0	return false;
106	28	if (Func->getNumParams() == 2 &&
107	28	!isIteratorType(Func->getParamDecl(1)->getType())22 )
108	14	return false;
109	14	return IdInfo->getName() == "erase";
110	28	}
111
112	208	bool isEraseAfterCall(const FunctionDecl *Func) {
113	208	const auto *IdInfo = Func->getIdentifier();
114	208	if (!IdInfo)
115	36	return false;
116	172	if (Func->getNumParams() < 1 \|\| Func->getNumParams() > 226 )
117	158	return false;
118	14	if (!isIteratorType(Func->getParamDecl(0)->getType()))
119	0	return false;
120	14	if (Func->getNumParams() == 2 &&
121	14	!isIteratorType(Func->getParamDecl(1)->getType()))
122	14	return false;
123	0	return IdInfo->getName() == "erase_after";
124	14	}
125
126	48	bool isAccessOperator(OverloadedOperatorKind OK) {
127	48	return isDereferenceOperator(OK) \|\| isIncrementOperator(OK)40 \|\|
128	48	isDecrementOperator(OK)24 \|\| isRandomIncrOrDecrOperator(OK)16 ;
129	48	}
130
131	20	bool isAccessOperator(UnaryOperatorKind OK) {
132	20	return isDereferenceOperator(OK) \|\| isIncrementOperator(OK)16 \|\|
133	20	isDecrementOperator(OK)6 ;
134	20	}
135
136	17	bool isAccessOperator(BinaryOperatorKind OK) {
137	17	return isDereferenceOperator(OK) \|\| isRandomIncrOrDecrOperator(OK);
138	17	}
139
140	94	bool isDereferenceOperator(OverloadedOperatorKind OK) {
141	94	return OK == OO_Star \|\| OK == OO_Arrow78 \|\| OK == OO_ArrowStar74 \|\|
142	94	OK == OO_Subscript74 ;
143	94	}
144
145	235	bool isDereferenceOperator(UnaryOperatorKind OK) {
146	235	return OK == UO_Deref;
147	235	}
148
149	116	bool isDereferenceOperator(BinaryOperatorKind OK) {
150	116	return OK == BO_PtrMemI;
151	116	}
152
153	1.12k	bool isIncrementOperator(OverloadedOperatorKind OK) {
154	1.12k	return OK == OO_PlusPlus;
155	1.12k	}
156
157	1.47k	bool isIncrementOperator(UnaryOperatorKind OK) {
158	1.47k	return OK == UO_PreInc \|\| OK == UO_PostInc1.15k ;
159	1.47k	}
160
161	739	bool isDecrementOperator(OverloadedOperatorKind OK) {
162	739	return OK == OO_MinusMinus;
163	739	}
164
165	991	bool isDecrementOperator(UnaryOperatorKind OK) {
166	991	return OK == UO_PreDec \|\| OK == UO_PostDec801 ;
167	991	}
168
169	1.17k	bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
170	1.17k	return OK == OO_Plus \|\| OK == OO_PlusEqual1.12k \|\| OK == OO_Minus839 \|\|
171	1.17k	OK == OO_MinusEqual795 ;
172	1.17k	}
173
174	626	bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
175	626	return OK == BO_Add \|\| OK == BO_AddAssign542 \|\|
176	626	OK == BO_Sub394 \|\| OK == BO_SubAssign348 ;
177	626	}
178
179		const ContainerData *getContainerData(ProgramStateRef State,
180	9.13k	const MemRegion *Cont) {
181	9.13k	return State->get<ContainerMap>(Cont);
182	9.13k	}
183
184		const IteratorPosition *getIteratorPosition(ProgramStateRef State,
185	29.6k	const SVal &Val) {
186	29.6k	if (auto Reg = Val.getAsRegion()) {
187	15.7k	Reg = Reg->getMostDerivedObjectRegion();
188	15.7k	return State->get<IteratorRegionMap>(Reg);
189	15.7k	} else if (const auto 13.8k Sym13.8k = Val.getAsSymbol()) {
190	736	return State->get<IteratorSymbolMap>(Sym);
191	13.1k	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
192	12.9k	return State->get<IteratorRegionMap>(LCVal->getRegion());
193	12.9k	}
194	169	return nullptr;
195	29.6k	}
196
197		ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
198	10.5k	const IteratorPosition &Pos) {
199	10.5k	if (auto Reg = Val.getAsRegion()) {
200	6.80k	Reg = Reg->getMostDerivedObjectRegion();
201	6.80k	return State->set<IteratorRegionMap>(Reg, Pos);
202	6.80k	} else if (const auto 3.73k Sym3.73k = Val.getAsSymbol()) {
203	199	return State->set<IteratorSymbolMap>(Sym, Pos);
204	3.53k	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
205	3.52k	return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
206	3.52k	}
207	6	return nullptr;
208	10.5k	}
209
210		ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
211		const MemRegion Cont, const Stmt S,
212		const LocationContext *LCtx,
213	479	unsigned blockCount) {
214	479	auto &StateMgr = State->getStateManager();
215	479	auto &SymMgr = StateMgr.getSymbolManager();
216	479	auto &ACtx = StateMgr.getContext();
217
218	479	auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount);
219	479	State = assumeNoOverflow(State, Sym, 4);
220	479	return setIteratorPosition(State, Val,
221	479	IteratorPosition::getPosition(Cont, Sym));
222	479	}
223
224		ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
225		OverloadedOperatorKind Op,
226	1.55k	const SVal &Distance) {
227	1.55k	const auto *Pos = getIteratorPosition(State, Iter);
228	1.55k	if (!Pos)
229	145	return nullptr;
230
231	1.41k	auto &SymMgr = State->getStateManager().getSymbolManager();
232	1.41k	auto &SVB = State->getStateManager().getSValBuilder();
233	1.41k	auto &BVF = State->getStateManager().getBasicVals();
234
235	1.41k	assert ((Op == OO_Plus \|\| Op == OO_PlusEqual \|\|
236	1.41k	Op == OO_Minus \|\| Op == OO_MinusEqual) &&
237	1.41k	"Advance operator must be one of +, -, += and -=.");
238	1.41k	auto BinOp = (Op == OO_Plus \|\| Op == OO_PlusEqual916 ) ? BO_Add896 : BO_Sub518 ;
239	1.41k	const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
240	1.41k	if (!IntDistOp)
241	10	return nullptr;
242
243		// For concrete integers we can calculate the new position
244	1.40k	nonloc::ConcreteInt IntDist = *IntDistOp;
245
246	1.40k	if (IntDist.getValue().isNegative()) {
247	218	IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
248	218	BinOp = (BinOp == BO_Add) ? BO_Sub186 : BO_Add32 ;
249	218	}
250	1.40k	const auto NewPos =
251	1.40k	Pos->setTo(SVB.evalBinOp(State, BinOp,
252	1.40k	nonloc::SymbolVal(Pos->getOffset()),
253	1.40k	IntDist, SymMgr.getType(Pos->getOffset()))
254	1.40k	.getAsSymbol());
255	1.40k	return setIteratorPosition(State, Iter, NewPos);
256	1.41k	}
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	2.79k	long Scale) {
267	2.79k	SValBuilder &SVB = State->getStateManager().getSValBuilder();
268	2.79k	BasicValueFactory &BV = SVB.getBasicValueFactory();
269
270	2.79k	QualType T = Sym->getType();
271	2.79k	assert(T->isSignedIntegerOrEnumerationType());
272	2.79k	APSIntType AT = BV.getAPSIntType(T);
273
274	2.79k	ProgramStateRef NewState = State;
275
276	2.79k	llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
277	2.79k	SVal IsCappedFromAbove =
278	2.79k	SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
279	2.79k	nonloc::ConcreteInt(Max), SVB.getConditionType());
280	2.79k	if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
281	2.79k	NewState = NewState->assume(*DV, true);
282	2.79k	if (!NewState)
283	0	return State;
284	2.79k	}
285
286	2.79k	llvm::APSInt Min = -Max;
287	2.79k	SVal IsCappedFromBelow =
288	2.79k	SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
289	2.79k	nonloc::ConcreteInt(Min), SVB.getConditionType());
290	2.79k	if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
291	2.79k	NewState = NewState->assume(*DV, true);
292	2.79k	if (!NewState)
293	0	return State;
294	2.79k	}
295
296	2.79k	return NewState;
297	2.79k	}
298
299		bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
300	2.09k	BinaryOperator::Opcode Opc) {
301	2.09k	return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
302	2.09k	}
303
304		bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
305	2.83k	BinaryOperator::Opcode Opc) {
306	2.83k	auto &SVB = State->getStateManager().getSValBuilder();
307
308	2.83k	const auto comparison =
309	2.83k	SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
310
311	2.83k	assert(isa<DefinedSVal>(comparison) &&
312	2.83k	"Symbol comparison must be a `DefinedSVal`");
313
314	2.83k	return !State->assume(comparison.castAs<DefinedSVal>(), false);
315	2.83k	}
316
317		} // namespace iterator
318		} // namespace ento
319		} // namespace clang