186 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Defines common functions to be used by the itertor checkers .10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H14#define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H15 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 kinds25// of operators in a common way by using a symbolic position.26struct IteratorPosition {27private:28 29 // Container the iterator belongs to30 const MemRegion *Cont;31 32 // Whether iterator is valid33 const bool Valid;34 35 // Abstract offset36 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 { 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 container76struct ContainerData {77private:78 const SymbolRef Begin, End;79 80 ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}81 82public: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 110class IteratorSymbolMap {};111class IteratorRegionMap {};112class ContainerMap {};113 114using IteratorSymbolMapTy =115 CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);116using IteratorRegionMapTy =117 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);118using ContainerMapTy =119 CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);120 121} // namespace iterator122 123template<>124struct ProgramStateTrait<iterator::IteratorSymbolMap>125 : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {126 static void *GDMIndex() { static int Index; return &Index; }127};128 129template<>130struct ProgramStateTrait<iterator::IteratorRegionMap>131 : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> {132 static void *GDMIndex() { static int Index; return &Index; }133};134 135template<>136struct ProgramStateTrait<iterator::ContainerMap>137 : public ProgramStatePartialTrait<iterator::ContainerMapTy> {138 static void *GDMIndex() { static int Index; return &Index; }139};140 141namespace iterator {142 143bool isIteratorType(const QualType &Type);144bool isIterator(const CXXRecordDecl *CRD);145bool isComparisonOperator(OverloadedOperatorKind OK);146bool isInsertCall(const FunctionDecl *Func);147bool isEraseCall(const FunctionDecl *Func);148bool isEraseAfterCall(const FunctionDecl *Func);149bool isEmplaceCall(const FunctionDecl *Func);150bool isAccessOperator(OverloadedOperatorKind OK);151bool isAccessOperator(UnaryOperatorKind OK);152bool isAccessOperator(BinaryOperatorKind OK);153bool isDereferenceOperator(OverloadedOperatorKind OK);154bool isDereferenceOperator(UnaryOperatorKind OK);155bool isDereferenceOperator(BinaryOperatorKind OK);156bool isIncrementOperator(OverloadedOperatorKind OK);157bool isIncrementOperator(UnaryOperatorKind OK);158bool isDecrementOperator(OverloadedOperatorKind OK);159bool isDecrementOperator(UnaryOperatorKind OK);160bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);161bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK);162const ContainerData *getContainerData(ProgramStateRef State,163 const MemRegion *Cont);164const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val);165ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,166 const IteratorPosition &Pos);167ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,168 const MemRegion *Cont,169 ConstCFGElementRef Elem,170 const LocationContext *LCtx,171 unsigned blockCount);172ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,173 OverloadedOperatorKind Op, SVal Distance);174ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,175 long Scale);176bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,177 BinaryOperator::Opcode Opc);178bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,179 BinaryOperator::Opcode Opc);180 181} // namespace iterator182} // namespace ento183} // namespace clang184 185#endif186