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 { return !(*this == X); } 67 68 void Profile(llvm::FoldingSetNodeID &ID) const { 69 ID.AddPointer(Cont); 70 ID.AddInteger(Valid); 71 ID.Add(Offset); 72 } 73 }; 74 75 // Structure to record the symbolic begin and end position of a container 76 struct ContainerData { 77 private: 78 const SymbolRef Begin, End; 79 80 ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {} 81 82 public: 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(Begin); 106 ID.Add(End); 107 } 108 }; 109 110 class IteratorSymbolMap {}; 111 class IteratorRegionMap {}; 112 class ContainerMap {}; 113 114 using IteratorSymbolMapTy = 115 CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition); 116 using IteratorRegionMapTy = 117 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition); 118 using ContainerMapTy = 119 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData); 120 121 } // namespace iterator 122 123 template<> 124 struct ProgramStateTrait<iterator::IteratorSymbolMap> 125 : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> { 126 static void *GDMIndex() { static int Index; return &Index; } 127 }; 128 129 template<> 130 struct ProgramStateTrait<iterator::IteratorRegionMap> 131 : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> { 132 static void *GDMIndex() { static int Index; return &Index; } 133 }; 134 135 template<> 136 struct ProgramStateTrait<iterator::ContainerMap> 137 : public ProgramStatePartialTrait<iterator::ContainerMapTy> { 138 static void *GDMIndex() { static int Index; return &Index; } 139 }; 140 141 namespace iterator { 142 143 bool isIteratorType(const QualType &Type); 144 bool isIterator(const CXXRecordDecl *CRD); 145 bool isComparisonOperator(OverloadedOperatorKind OK); 146 bool isInsertCall(const FunctionDecl *Func); 147 bool isEraseCall(const FunctionDecl *Func); 148 bool isEraseAfterCall(const FunctionDecl *Func); 149 bool isEmplaceCall(const FunctionDecl *Func); 150 bool isAccessOperator(OverloadedOperatorKind OK); 151 bool isAccessOperator(UnaryOperatorKind OK); 152 bool isAccessOperator(BinaryOperatorKind OK); 153 bool isDereferenceOperator(OverloadedOperatorKind OK); 154 bool isDereferenceOperator(UnaryOperatorKind OK); 155 bool isDereferenceOperator(BinaryOperatorKind OK); 156 bool isIncrementOperator(OverloadedOperatorKind OK); 157 bool isIncrementOperator(UnaryOperatorKind OK); 158 bool isDecrementOperator(OverloadedOperatorKind OK); 159 bool isDecrementOperator(UnaryOperatorKind OK); 160 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); 161 bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK); 162 const ContainerData *getContainerData(ProgramStateRef State, 163 const MemRegion *Cont); 164 const IteratorPosition *getIteratorPosition(ProgramStateRef State, 165 const SVal &Val); 166 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, 167 const IteratorPosition &Pos); 168 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, 169 const MemRegion *Cont, const Stmt* S, 170 const LocationContext *LCtx, 171 unsigned blockCount); 172 ProgramStateRef advancePosition(ProgramStateRef State, 173 const SVal &Iter, 174 OverloadedOperatorKind Op, 175 const SVal &Distance); 176 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 177 long Scale); 178 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 179 BinaryOperator::Opcode Opc); 180 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 181 BinaryOperator::Opcode Opc); 182 183 } // namespace iterator 184 } // namespace ento 185 } // namespace clang 186 187 #endif 188