1480093f4SDimitry Andric //=== Iterator.h - Common functions for iterator checkers. ---------*- C++ -*-// 2480093f4SDimitry Andric // 3480093f4SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4480093f4SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5480093f4SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6480093f4SDimitry Andric // 7480093f4SDimitry Andric //===----------------------------------------------------------------------===// 8480093f4SDimitry Andric // 9480093f4SDimitry Andric // Defines common functions to be used by the itertor checkers . 10480093f4SDimitry Andric // 11480093f4SDimitry Andric //===----------------------------------------------------------------------===// 12480093f4SDimitry Andric 13480093f4SDimitry Andric #ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H 14480093f4SDimitry Andric #define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H 15480093f4SDimitry Andric 16480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" 17480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 18480093f4SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" 19480093f4SDimitry Andric 20480093f4SDimitry Andric namespace clang { 21480093f4SDimitry Andric namespace ento { 22480093f4SDimitry Andric namespace iterator { 23480093f4SDimitry Andric 24480093f4SDimitry Andric // Abstract position of an iterator. This helps to handle all three kinds 25480093f4SDimitry Andric // of operators in a common way by using a symbolic position. 26480093f4SDimitry Andric struct IteratorPosition { 27480093f4SDimitry Andric private: 28480093f4SDimitry Andric 29480093f4SDimitry Andric // Container the iterator belongs to 30480093f4SDimitry Andric const MemRegion *Cont; 31480093f4SDimitry Andric 32480093f4SDimitry Andric // Whether iterator is valid 33480093f4SDimitry Andric const bool Valid; 34480093f4SDimitry Andric 35480093f4SDimitry Andric // Abstract offset 36480093f4SDimitry Andric const SymbolRef Offset; 37480093f4SDimitry Andric 38480093f4SDimitry Andric IteratorPosition(const MemRegion *C, bool V, SymbolRef Of) 39480093f4SDimitry Andric : Cont(C), Valid(V), Offset(Of) {} 40480093f4SDimitry Andric 41480093f4SDimitry Andric public: 42480093f4SDimitry Andric const MemRegion *getContainer() const { return Cont; } 43480093f4SDimitry Andric bool isValid() const { return Valid; } 44480093f4SDimitry Andric SymbolRef getOffset() const { return Offset; } 45480093f4SDimitry Andric 46480093f4SDimitry Andric IteratorPosition invalidate() const { 47480093f4SDimitry Andric return IteratorPosition(Cont, false, Offset); 48480093f4SDimitry Andric } 49480093f4SDimitry Andric 50480093f4SDimitry Andric static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { 51480093f4SDimitry Andric return IteratorPosition(C, true, Of); 52480093f4SDimitry Andric } 53480093f4SDimitry Andric 54480093f4SDimitry Andric IteratorPosition setTo(SymbolRef NewOf) const { 55480093f4SDimitry Andric return IteratorPosition(Cont, Valid, NewOf); 56480093f4SDimitry Andric } 57480093f4SDimitry Andric 58480093f4SDimitry Andric IteratorPosition reAssign(const MemRegion *NewCont) const { 59480093f4SDimitry Andric return IteratorPosition(NewCont, Valid, Offset); 60480093f4SDimitry Andric } 61480093f4SDimitry Andric 62480093f4SDimitry Andric bool operator==(const IteratorPosition &X) const { 63480093f4SDimitry Andric return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; 64480093f4SDimitry Andric } 65480093f4SDimitry Andric 6681ad6265SDimitry Andric bool operator!=(const IteratorPosition &X) const { return !(*this == X); } 67480093f4SDimitry Andric 68480093f4SDimitry Andric void Profile(llvm::FoldingSetNodeID &ID) const { 69480093f4SDimitry Andric ID.AddPointer(Cont); 70480093f4SDimitry Andric ID.AddInteger(Valid); 71480093f4SDimitry Andric ID.Add(Offset); 72480093f4SDimitry Andric } 73480093f4SDimitry Andric }; 74480093f4SDimitry Andric 75480093f4SDimitry Andric // Structure to record the symbolic begin and end position of a container 76480093f4SDimitry Andric struct ContainerData { 77480093f4SDimitry Andric private: 78480093f4SDimitry Andric const SymbolRef Begin, End; 79480093f4SDimitry Andric 80480093f4SDimitry Andric ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {} 81480093f4SDimitry Andric 82480093f4SDimitry Andric public: 83480093f4SDimitry Andric static ContainerData fromBegin(SymbolRef B) { 84480093f4SDimitry Andric return ContainerData(B, nullptr); 85480093f4SDimitry Andric } 86480093f4SDimitry Andric 87480093f4SDimitry Andric static ContainerData fromEnd(SymbolRef E) { 88480093f4SDimitry Andric return ContainerData(nullptr, E); 89480093f4SDimitry Andric } 90480093f4SDimitry Andric 91480093f4SDimitry Andric SymbolRef getBegin() const { return Begin; } 92480093f4SDimitry Andric SymbolRef getEnd() const { return End; } 93480093f4SDimitry Andric 94480093f4SDimitry Andric ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); } 95480093f4SDimitry Andric 96480093f4SDimitry Andric ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); } 97480093f4SDimitry Andric 98480093f4SDimitry Andric bool operator==(const ContainerData &X) const { 99480093f4SDimitry Andric return Begin == X.Begin && End == X.End; 100480093f4SDimitry Andric } 101480093f4SDimitry Andric 10281ad6265SDimitry Andric bool operator!=(const ContainerData &X) const { return !(*this == X); } 103480093f4SDimitry Andric 104480093f4SDimitry Andric void Profile(llvm::FoldingSetNodeID &ID) const { 105480093f4SDimitry Andric ID.Add(Begin); 106480093f4SDimitry Andric ID.Add(End); 107480093f4SDimitry Andric } 108480093f4SDimitry Andric }; 109480093f4SDimitry Andric 110480093f4SDimitry Andric class IteratorSymbolMap {}; 111480093f4SDimitry Andric class IteratorRegionMap {}; 112480093f4SDimitry Andric class ContainerMap {}; 113480093f4SDimitry Andric 1145ffd83dbSDimitry Andric using IteratorSymbolMapTy = 1155ffd83dbSDimitry Andric CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition); 1165ffd83dbSDimitry Andric using IteratorRegionMapTy = 1175ffd83dbSDimitry Andric CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition); 1185ffd83dbSDimitry Andric using ContainerMapTy = 1195ffd83dbSDimitry Andric CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData); 120480093f4SDimitry Andric 121480093f4SDimitry Andric } // namespace iterator 122480093f4SDimitry Andric 123480093f4SDimitry Andric template<> 124480093f4SDimitry Andric struct ProgramStateTrait<iterator::IteratorSymbolMap> 125480093f4SDimitry Andric : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> { 126480093f4SDimitry Andric static void *GDMIndex() { static int Index; return &Index; } 127480093f4SDimitry Andric }; 128480093f4SDimitry Andric 129480093f4SDimitry Andric template<> 130480093f4SDimitry Andric struct ProgramStateTrait<iterator::IteratorRegionMap> 131480093f4SDimitry Andric : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> { 132480093f4SDimitry Andric static void *GDMIndex() { static int Index; return &Index; } 133480093f4SDimitry Andric }; 134480093f4SDimitry Andric 135480093f4SDimitry Andric template<> 136480093f4SDimitry Andric struct ProgramStateTrait<iterator::ContainerMap> 137480093f4SDimitry Andric : public ProgramStatePartialTrait<iterator::ContainerMapTy> { 138480093f4SDimitry Andric static void *GDMIndex() { static int Index; return &Index; } 139480093f4SDimitry Andric }; 140480093f4SDimitry Andric 141480093f4SDimitry Andric namespace iterator { 142480093f4SDimitry Andric 143480093f4SDimitry Andric bool isIteratorType(const QualType &Type); 144480093f4SDimitry Andric bool isIterator(const CXXRecordDecl *CRD); 145480093f4SDimitry Andric bool isComparisonOperator(OverloadedOperatorKind OK); 146480093f4SDimitry Andric bool isInsertCall(const FunctionDecl *Func); 147480093f4SDimitry Andric bool isEraseCall(const FunctionDecl *Func); 148480093f4SDimitry Andric bool isEraseAfterCall(const FunctionDecl *Func); 149480093f4SDimitry Andric bool isEmplaceCall(const FunctionDecl *Func); 150480093f4SDimitry Andric bool isAccessOperator(OverloadedOperatorKind OK); 1515ffd83dbSDimitry Andric bool isAccessOperator(UnaryOperatorKind OK); 1525ffd83dbSDimitry Andric bool isAccessOperator(BinaryOperatorKind OK); 153480093f4SDimitry Andric bool isDereferenceOperator(OverloadedOperatorKind OK); 1545ffd83dbSDimitry Andric bool isDereferenceOperator(UnaryOperatorKind OK); 1555ffd83dbSDimitry Andric bool isDereferenceOperator(BinaryOperatorKind OK); 156480093f4SDimitry Andric bool isIncrementOperator(OverloadedOperatorKind OK); 1575ffd83dbSDimitry Andric bool isIncrementOperator(UnaryOperatorKind OK); 158480093f4SDimitry Andric bool isDecrementOperator(OverloadedOperatorKind OK); 1595ffd83dbSDimitry Andric bool isDecrementOperator(UnaryOperatorKind OK); 160480093f4SDimitry Andric bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); 1615ffd83dbSDimitry Andric bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK); 162480093f4SDimitry Andric const ContainerData *getContainerData(ProgramStateRef State, 163480093f4SDimitry Andric const MemRegion *Cont); 164*647cbc5dSDimitry Andric const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val); 165*647cbc5dSDimitry Andric ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val, 166480093f4SDimitry Andric const IteratorPosition &Pos); 167*647cbc5dSDimitry Andric ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val, 1685ffd83dbSDimitry Andric const MemRegion *Cont, const Stmt *S, 1695ffd83dbSDimitry Andric const LocationContext *LCtx, 1705ffd83dbSDimitry Andric unsigned blockCount); 171*647cbc5dSDimitry Andric ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter, 172*647cbc5dSDimitry Andric OverloadedOperatorKind Op, SVal Distance); 1735ffd83dbSDimitry Andric ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 1745ffd83dbSDimitry Andric long Scale); 175480093f4SDimitry Andric bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 176480093f4SDimitry Andric BinaryOperator::Opcode Opc); 177480093f4SDimitry Andric bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 178480093f4SDimitry Andric BinaryOperator::Opcode Opc); 179480093f4SDimitry Andric 180480093f4SDimitry Andric } // namespace iterator 181480093f4SDimitry Andric } // namespace ento 182480093f4SDimitry Andric } // namespace clang 183480093f4SDimitry Andric 184480093f4SDimitry Andric #endif 185