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