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 = CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition); 119using IteratorRegionMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition); 120using ContainerMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData); 121 122} // namespace iterator 123 124template<> 125struct ProgramStateTrait<iterator::IteratorSymbolMap> 126 : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> { 127 static void *GDMIndex() { static int Index; return &Index; } 128}; 129 130template<> 131struct ProgramStateTrait<iterator::IteratorRegionMap> 132 : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> { 133 static void *GDMIndex() { static int Index; return &Index; } 134}; 135 136template<> 137struct ProgramStateTrait<iterator::ContainerMap> 138 : public ProgramStatePartialTrait<iterator::ContainerMapTy> { 139 static void *GDMIndex() { static int Index; return &Index; } 140}; 141 142namespace iterator { 143 144bool isIteratorType(const QualType &Type); 145bool isIterator(const CXXRecordDecl *CRD); 146bool isComparisonOperator(OverloadedOperatorKind OK); 147bool isInsertCall(const FunctionDecl *Func); 148bool isEraseCall(const FunctionDecl *Func); 149bool isEraseAfterCall(const FunctionDecl *Func); 150bool isEmplaceCall(const FunctionDecl *Func); 151bool isAccessOperator(OverloadedOperatorKind OK); 152bool isDereferenceOperator(OverloadedOperatorKind OK); 153bool isIncrementOperator(OverloadedOperatorKind OK); 154bool isDecrementOperator(OverloadedOperatorKind OK); 155bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); 156const ContainerData *getContainerData(ProgramStateRef State, 157 const MemRegion *Cont); 158const IteratorPosition *getIteratorPosition(ProgramStateRef State, 159 const SVal &Val); 160ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, 161 const IteratorPosition &Pos); 162ProgramStateRef advancePosition(ProgramStateRef State, 163 const SVal &Iter, 164 OverloadedOperatorKind Op, 165 const SVal &Distance); 166bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 167 BinaryOperator::Opcode Opc); 168bool 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