clang/lib/StaticAnalyzer/Checkers/Iterator.h

   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, SVal Val);
 165 ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,
 166                                     const IteratorPosition &Pos);
 167 ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,
 168                                        const MemRegion *Cont, const Stmt *S,
 169                                        const LocationContext *LCtx,
 170                                        unsigned blockCount);
 171 ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
 172                                 OverloadedOperatorKind Op, SVal Distance);
 173 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
 174                                  long Scale);
 175 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
 176              BinaryOperator::Opcode Opc);
 177 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
 178              BinaryOperator::Opcode Opc);
 179
 180 } // namespace iterator
 181 } // namespace ento
 182 } // namespace clang
 183
 184 #endif