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 = 119 CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition); 120 using IteratorRegionMapTy = 121 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition); 122 using ContainerMapTy = 123 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData); 124 125 } // namespace iterator 126 127 template<> 128 struct ProgramStateTrait<iterator::IteratorSymbolMap> 129 : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> { 130 static void *GDMIndex() { static int Index; return &Index; } 131 }; 132 133 template<> 134 struct ProgramStateTrait<iterator::IteratorRegionMap> 135 : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> { 136 static void *GDMIndex() { static int Index; return &Index; } 137 }; 138 139 template<> 140 struct ProgramStateTrait<iterator::ContainerMap> 141 : public ProgramStatePartialTrait<iterator::ContainerMapTy> { 142 static void *GDMIndex() { static int Index; return &Index; } 143 }; 144 145 namespace iterator { 146 147 bool isIteratorType(const QualType &Type); 148 bool isIterator(const CXXRecordDecl *CRD); 149 bool isComparisonOperator(OverloadedOperatorKind OK); 150 bool isInsertCall(const FunctionDecl *Func); 151 bool isEraseCall(const FunctionDecl *Func); 152 bool isEraseAfterCall(const FunctionDecl *Func); 153 bool isEmplaceCall(const FunctionDecl *Func); 154 bool isAccessOperator(OverloadedOperatorKind OK); 155 bool isAccessOperator(UnaryOperatorKind OK); 156 bool isAccessOperator(BinaryOperatorKind OK); 157 bool isDereferenceOperator(OverloadedOperatorKind OK); 158 bool isDereferenceOperator(UnaryOperatorKind OK); 159 bool isDereferenceOperator(BinaryOperatorKind OK); 160 bool isIncrementOperator(OverloadedOperatorKind OK); 161 bool isIncrementOperator(UnaryOperatorKind OK); 162 bool isDecrementOperator(OverloadedOperatorKind OK); 163 bool isDecrementOperator(UnaryOperatorKind OK); 164 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); 165 bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK); 166 const ContainerData *getContainerData(ProgramStateRef State, 167 const MemRegion *Cont); 168 const IteratorPosition *getIteratorPosition(ProgramStateRef State, 169 const SVal &Val); 170 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, 171 const IteratorPosition &Pos); 172 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, 173 const MemRegion *Cont, const Stmt* S, 174 const LocationContext *LCtx, 175 unsigned blockCount); 176 ProgramStateRef advancePosition(ProgramStateRef State, 177 const SVal &Iter, 178 OverloadedOperatorKind Op, 179 const SVal &Distance); 180 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 181 long Scale); 182 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 183 BinaryOperator::Opcode Opc); 184 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 185 BinaryOperator::Opcode Opc); 186 187 } // namespace iterator 188 } // namespace ento 189 } // namespace clang 190 191 #endif 192