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