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 
20 namespace clang {
21 namespace ento {
22 namespace 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.
26 struct IteratorPosition {
27 private:
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 
41 public:
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 {
67     return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
68   }
69 
70   void Profile(llvm::FoldingSetNodeID &ID) const {
71     ID.AddPointer(Cont);
72     ID.AddInteger(Valid);
73     ID.Add(Offset);
74   }
75 };
76 
77 // Structure to record the symbolic begin and end position of a container
78 struct ContainerData {
79 private:
80   const SymbolRef Begin, End;
81 
82   ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
83 
84 public:
85   static ContainerData fromBegin(SymbolRef B) {
86     return ContainerData(B, nullptr);
87   }
88 
89   static ContainerData fromEnd(SymbolRef E) {
90     return ContainerData(nullptr, E);
91   }
92 
93   SymbolRef getBegin() const { return Begin; }
94   SymbolRef getEnd() const { return End; }
95 
96   ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
97 
98   ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
99 
100   bool operator==(const ContainerData &X) const {
101     return Begin == X.Begin && End == X.End;
102   }
103 
104   bool operator!=(const ContainerData &X) const {
105     return Begin != X.Begin || End != X.End;
106   }
107 
108   void Profile(llvm::FoldingSetNodeID &ID) const {
109     ID.Add(Begin);
110     ID.Add(End);
111   }
112 };
113 
114 class IteratorSymbolMap {};
115 class IteratorRegionMap {};
116 class ContainerMap {};
117 
118 using IteratorSymbolMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
119 using IteratorRegionMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
120 using ContainerMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
121 
122 } // namespace iterator
123 
124 template<>
125 struct ProgramStateTrait<iterator::IteratorSymbolMap>
126   : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {
127   static void *GDMIndex() { static int Index; return &Index; }
128 };
129 
130 template<>
131 struct ProgramStateTrait<iterator::IteratorRegionMap>
132   : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> {
133   static void *GDMIndex() { static int Index; return &Index; }
134 };
135 
136 template<>
137 struct ProgramStateTrait<iterator::ContainerMap>
138   : public ProgramStatePartialTrait<iterator::ContainerMapTy> {
139   static void *GDMIndex() { static int Index; return &Index; }
140 };
141 
142 namespace iterator {
143 
144 bool isIteratorType(const QualType &Type);
145 bool isIterator(const CXXRecordDecl *CRD);
146 bool isComparisonOperator(OverloadedOperatorKind OK);
147 bool isInsertCall(const FunctionDecl *Func);
148 bool isEraseCall(const FunctionDecl *Func);
149 bool isEraseAfterCall(const FunctionDecl *Func);
150 bool isEmplaceCall(const FunctionDecl *Func);
151 bool isAccessOperator(OverloadedOperatorKind OK);
152 bool isDereferenceOperator(OverloadedOperatorKind OK);
153 bool isIncrementOperator(OverloadedOperatorKind OK);
154 bool isDecrementOperator(OverloadedOperatorKind OK);
155 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
156 const ContainerData *getContainerData(ProgramStateRef State,
157                                       const MemRegion *Cont);
158 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
159                                             const SVal &Val);
160 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
161                                     const IteratorPosition &Pos);
162 ProgramStateRef advancePosition(ProgramStateRef State,
163                                 const SVal &Iter,
164                                 OverloadedOperatorKind Op,
165                                 const SVal &Distance);
166 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
167              BinaryOperator::Opcode Opc);
168 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
169              BinaryOperator::Opcode Opc);
170 
171 } // namespace iterator
172 } // namespace ento
173 } // namespace clang
174 
175 #endif
176