1//=== Iterator.h - 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#ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
14#define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
15
16#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
19
20namespace clang {
21namespace ento {
22namespace iterator {
23
24// Abstract position of an iterator. This helps to handle all three kinds
25// of operators in a common way by using a symbolic position.
26struct IteratorPosition {
27private:
28
29 // Container the iterator belongs to
30 const MemRegion *Cont;
31
32 // Whether iterator is valid
33 const bool Valid;
34
35 // Abstract offset
36 const SymbolRef Offset;
37
38 IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
39 : Cont(C), Valid(V), Offset(Of) {}
40
41public:
42 const MemRegion *getContainer() const { return Cont; }
43 bool isValid() const { return Valid; }
44 SymbolRef getOffset() const { return Offset; }
45
46 IteratorPosition invalidate() const {
47 return IteratorPosition(Cont, false, Offset);
48 }
49
50 static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
51 return IteratorPosition(C, true, Of);
52 }
53
54 IteratorPosition setTo(SymbolRef NewOf) const {
55 return IteratorPosition(Cont, Valid, NewOf);
56 }
57
58 IteratorPosition reAssign(const MemRegion *NewCont) const {
59 return IteratorPosition(NewCont, Valid, Offset);
60 }
61
62 bool operator==(const IteratorPosition &X) const {
63 return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
64 }
65
66 bool operator!=(const IteratorPosition &X) const { return !(*this == X); }
67
68 void Profile(llvm::FoldingSetNodeID &ID) const {
69 ID.AddPointer(Ptr: Cont);
70 ID.AddInteger(I: Valid);
71 ID.Add(x: Offset);
72 }
73};
74
75// Structure to record the symbolic begin and end position of a container
76struct ContainerData {
77private:
78 const SymbolRef Begin, End;
79
80 ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
81
82public:
83 static ContainerData fromBegin(SymbolRef B) {
84 return ContainerData(B, nullptr);
85 }
86
87 static ContainerData fromEnd(SymbolRef E) {
88 return ContainerData(nullptr, E);
89 }
90
91 SymbolRef getBegin() const { return Begin; }
92 SymbolRef getEnd() const { return End; }
93
94 ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
95
96 ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
97
98 bool operator==(const ContainerData &X) const {
99 return Begin == X.Begin && End == X.End;
100 }
101
102 bool operator!=(const ContainerData &X) const { return !(*this == X); }
103
104 void Profile(llvm::FoldingSetNodeID &ID) const {
105 ID.Add(x: Begin);
106 ID.Add(x: End);
107 }
108};
109
110class IteratorSymbolMap {};
111class IteratorRegionMap {};
112class ContainerMap {};
113
114using IteratorSymbolMapTy =
115 CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
116using IteratorRegionMapTy =
117 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
118using ContainerMapTy =
119 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
120
121} // namespace iterator
122
123template<>
124struct ProgramStateTrait<iterator::IteratorSymbolMap>
125 : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {
126 static void *GDMIndex() { static int Index; return &Index; }
127};
128
129template<>
130struct ProgramStateTrait<iterator::IteratorRegionMap>
131 : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> {
132 static void *GDMIndex() { static int Index; return &Index; }
133};
134
135template<>
136struct ProgramStateTrait<iterator::ContainerMap>
137 : public ProgramStatePartialTrait<iterator::ContainerMapTy> {
138 static void *GDMIndex() { static int Index; return &Index; }
139};
140
141namespace iterator {
142
143bool isIteratorType(const QualType &Type);
144bool isIterator(const CXXRecordDecl *CRD);
145bool isComparisonOperator(OverloadedOperatorKind OK);
146bool isInsertCall(const FunctionDecl *Func);
147bool isEraseCall(const FunctionDecl *Func);
148bool isEraseAfterCall(const FunctionDecl *Func);
149bool isEmplaceCall(const FunctionDecl *Func);
150bool isAccessOperator(OverloadedOperatorKind OK);
151bool isAccessOperator(UnaryOperatorKind OK);
152bool isAccessOperator(BinaryOperatorKind OK);
153bool isDereferenceOperator(OverloadedOperatorKind OK);
154bool isDereferenceOperator(UnaryOperatorKind OK);
155bool isDereferenceOperator(BinaryOperatorKind OK);
156bool isIncrementOperator(OverloadedOperatorKind OK);
157bool isIncrementOperator(UnaryOperatorKind OK);
158bool isDecrementOperator(OverloadedOperatorKind OK);
159bool isDecrementOperator(UnaryOperatorKind OK);
160bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
161bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK);
162const ContainerData *getContainerData(ProgramStateRef State,
163 const MemRegion *Cont);
164const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val);
165ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,
166 const IteratorPosition &Pos);
167ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,
168 const MemRegion *Cont,
169 ConstCFGElementRef Elem,
170 const LocationContext *LCtx,
171 unsigned blockCount);
172ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
173 OverloadedOperatorKind Op, SVal Distance);
174ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
175 long Scale);
176bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
177 BinaryOperator::Opcode Opc);
178bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
179 BinaryOperator::Opcode Opc);
180
181} // namespace iterator
182} // namespace ento
183} // namespace clang
184
185#endif
186