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