xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/Iterator.h (revision 647cbc5de815c5651677bf8582797f716ec7b48d)
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