1 //ProgramStateTrait.h - Partial implementations of ProgramStateTrait -*- 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 //  This file defines partial implementations of template specializations of
10 //  the class ProgramStateTrait<>.  ProgramStateTrait<> is used by ProgramState
11 //  to implement set/get methods for manipulating a ProgramState's
12 //  generic data map.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATETRAIT_H
17 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATETRAIT_H
18 
19 #include "llvm/ADT/ImmutableList.h"
20 #include "llvm/ADT/ImmutableMap.h"
21 #include "llvm/ADT/ImmutableSet.h"
22 #include "llvm/Support/Allocator.h"
23 #include <cstdint>
24 
25 namespace clang {
26 namespace ento {
27 
28   template <typename T> struct ProgramStatePartialTrait;
29 
30   /// Declares a program state trait for type \p Type called \p Name, and
31   /// introduce a type named \c NameTy.
32   /// The macro should not be used inside namespaces.
33   #define REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, Type) \
34     namespace { \
35       class Name {}; \
36       using Name ## Ty = Type; \
37     } \
38     namespace clang { \
39     namespace ento { \
40       template <> \
41       struct ProgramStateTrait<Name> \
42         : public ProgramStatePartialTrait<Name ## Ty> { \
43         static void *GDMIndex() { static int Index; return &Index; } \
44       }; \
45     } \
46     }
47 
48   /// Declares a factory for objects of type \p Type in the program state
49   /// manager. The type must provide a ::Factory sub-class. Commonly used for
50   /// ImmutableMap, ImmutableSet, ImmutableList. The macro should not be used
51   /// inside namespaces.
52   #define REGISTER_FACTORY_WITH_PROGRAMSTATE(Type) \
53     namespace clang { \
54     namespace ento { \
55       template <> \
56       struct ProgramStateTrait<Type> \
57         : public ProgramStatePartialTrait<Type> { \
58         static void *GDMIndex() { static int Index; return &Index; } \
59       }; \
60     } \
61     }
62 
63   /// Helper for registering a map trait.
64   ///
65   /// If the map type were written directly in the invocation of
66   /// REGISTER_TRAIT_WITH_PROGRAMSTATE, the comma in the template arguments
67   /// would be treated as a macro argument separator, which is wrong.
68   /// This allows the user to specify a map type in a way that the preprocessor
69   /// can deal with.
70   #define CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value) llvm::ImmutableMap<Key, Value>
71 
72   /// Declares an immutable map of type \p NameTy, suitable for placement into
73   /// the ProgramState. This is implementing using llvm::ImmutableMap.
74   ///
75   /// \code
76   /// State = State->set<Name>(K, V);
77   /// const Value *V = State->get<Name>(K); // Returns NULL if not in the map.
78   /// State = State->remove<Name>(K);
79   /// NameTy Map = State->get<Name>();
80   /// \endcode
81   ///
82   /// The macro should not be used inside namespaces, or for traits that must
83   /// be accessible from more than one translation unit.
84   #define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value) \
85     REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, \
86                                      CLANG_ENTO_PROGRAMSTATE_MAP(Key, Value))
87 
88   /// Declares an immutable map type \p Name and registers the factory
89   /// for such maps in the program state, but does not add the map itself
90   /// to the program state. Useful for managing lifetime of maps that are used
91   /// as elements of other program state data structures.
92   #define REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(Name, Key, Value) \
93     using Name = llvm::ImmutableMap<Key, Value>; \
94     REGISTER_FACTORY_WITH_PROGRAMSTATE(Name)
95 
96 
97   /// Declares an immutable set of type \p NameTy, suitable for placement into
98   /// the ProgramState. This is implementing using llvm::ImmutableSet.
99   ///
100   /// \code
101   /// State = State->add<Name>(E);
102   /// State = State->remove<Name>(E);
103   /// bool Present = State->contains<Name>(E);
104   /// NameTy Set = State->get<Name>();
105   /// \endcode
106   ///
107   /// The macro should not be used inside namespaces, or for traits that must
108   /// be accessible from more than one translation unit.
109   #define REGISTER_SET_WITH_PROGRAMSTATE(Name, Elem) \
110     REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableSet<Elem>)
111 
112   /// Declares an immutable set type \p Name and registers the factory
113   /// for such sets in the program state, but does not add the set itself
114   /// to the program state. Useful for managing lifetime of sets that are used
115   /// as elements of other program state data structures.
116   #define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem) \
117     using Name = llvm::ImmutableSet<Elem>; \
118     REGISTER_FACTORY_WITH_PROGRAMSTATE(Name)
119 
120 
121   /// Declares an immutable list type \p NameTy, suitable for placement into
122   /// the ProgramState. This is implementing using llvm::ImmutableList.
123   ///
124   /// \code
125   /// State = State->add<Name>(E); // Adds to the /end/ of the list.
126   /// bool Present = State->contains<Name>(E);
127   /// NameTy List = State->get<Name>();
128   /// \endcode
129   ///
130   /// The macro should not be used inside namespaces, or for traits that must
131   /// be accessible from more than one translation unit.
132   #define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem) \
133     REGISTER_TRAIT_WITH_PROGRAMSTATE(Name, llvm::ImmutableList<Elem>)
134 
135   /// Declares an immutable list of type \p Name and registers the factory
136   /// for such lists in the program state, but does not add the list itself
137   /// to the program state. Useful for managing lifetime of lists that are used
138   /// as elements of other program state data structures.
139   #define REGISTER_LIST_FACTORY_WITH_PROGRAMSTATE(Name, Elem) \
140     using Name = llvm::ImmutableList<Elem>; \
141     REGISTER_FACTORY_WITH_PROGRAMSTATE(Name)
142 
143 
144   // Partial-specialization for ImmutableMap.
145   template <typename Key, typename Data, typename Info>
146   struct ProgramStatePartialTrait<llvm::ImmutableMap<Key, Data, Info>> {
147     using data_type = llvm::ImmutableMap<Key, Data, Info>;
148     using context_type = typename data_type::Factory &;
149     using key_type = Key;
150     using value_type = Data;
151     using lookup_type = const value_type *;
152 
153     static data_type MakeData(void *const *p) {
154       return p ? data_type((typename data_type::TreeTy *) *p)
155                : data_type(nullptr);
156     }
157 
158     static void *MakeVoidPtr(data_type B) {
159       return B.getRoot();
160     }
161 
162     static lookup_type Lookup(data_type B, key_type K) {
163       return B.lookup(K);
164     }
165 
166     static data_type Set(data_type B, key_type K, value_type E,
167                          context_type F) {
168       return F.add(B, K, E);
169     }
170 
171     static data_type Remove(data_type B, key_type K, context_type F) {
172       return F.remove(B, K);
173     }
174 
175     static bool Contains(data_type B, key_type K) {
176       return B.contains(K);
177     }
178 
179     static context_type MakeContext(void *p) {
180       return *((typename data_type::Factory *) p);
181     }
182 
183     static void *CreateContext(llvm::BumpPtrAllocator& Alloc) {
184       return new typename data_type::Factory(Alloc);
185     }
186 
187     static void DeleteContext(void *Ctx) {
188       delete (typename data_type::Factory *) Ctx;
189     }
190   };
191 
192   // Partial-specialization for ImmutableSet.
193   template <typename Key, typename Info>
194   struct ProgramStatePartialTrait<llvm::ImmutableSet<Key, Info>> {
195     using data_type = llvm::ImmutableSet<Key, Info>;
196     using context_type = typename data_type::Factory &;
197     using key_type = Key;
198 
199     static data_type MakeData(void *const *p) {
200       return p ? data_type((typename data_type::TreeTy *) *p)
201                : data_type(nullptr);
202     }
203 
204     static void *MakeVoidPtr(data_type B) {
205       return B.getRoot();
206     }
207 
208     static data_type Add(data_type B, key_type K, context_type F) {
209       return F.add(B, K);
210     }
211 
212     static data_type Remove(data_type B, key_type K, context_type F) {
213       return F.remove(B, K);
214     }
215 
216     static bool Contains(data_type B, key_type K) {
217       return B.contains(K);
218     }
219 
220     static context_type MakeContext(void *p) {
221       return *((typename data_type::Factory *) p);
222     }
223 
224     static void *CreateContext(llvm::BumpPtrAllocator &Alloc) {
225       return new typename data_type::Factory(Alloc);
226     }
227 
228     static void DeleteContext(void *Ctx) {
229       delete (typename data_type::Factory *) Ctx;
230     }
231   };
232 
233   // Partial-specialization for ImmutableList.
234   template <typename T>
235   struct ProgramStatePartialTrait<llvm::ImmutableList<T>> {
236     using data_type = llvm::ImmutableList<T>;
237     using key_type = T;
238     using context_type = typename data_type::Factory &;
239 
240     static data_type Add(data_type L, key_type K, context_type F) {
241       return F.add(K, L);
242     }
243 
244     static bool Contains(data_type L, key_type K) {
245       return L.contains(K);
246     }
247 
248     static data_type MakeData(void *const *p) {
249       return p ? data_type((const llvm::ImmutableListImpl<T> *) *p)
250                : data_type(nullptr);
251     }
252 
253     static void *MakeVoidPtr(data_type D) {
254       return const_cast<llvm::ImmutableListImpl<T> *>(D.getInternalPointer());
255     }
256 
257     static context_type MakeContext(void *p) {
258       return *((typename data_type::Factory *) p);
259     }
260 
261     static void *CreateContext(llvm::BumpPtrAllocator &Alloc) {
262       return new typename data_type::Factory(Alloc);
263     }
264 
265     static void DeleteContext(void *Ctx) {
266       delete (typename data_type::Factory *) Ctx;
267     }
268   };
269 
270   // Partial specialization for bool.
271   template <> struct ProgramStatePartialTrait<bool> {
272     using data_type = bool;
273 
274     static data_type MakeData(void *const *p) {
275       return p ? (data_type) (uintptr_t) *p
276                : data_type();
277     }
278 
279     static void *MakeVoidPtr(data_type d) {
280       return (void *) (uintptr_t) d;
281     }
282   };
283 
284   // Partial specialization for unsigned.
285   template <> struct ProgramStatePartialTrait<unsigned> {
286     using data_type = unsigned;
287 
288     static data_type MakeData(void *const *p) {
289       return p ? (data_type) (uintptr_t) *p
290                : data_type();
291     }
292 
293     static void *MakeVoidPtr(data_type d) {
294       return (void *) (uintptr_t) d;
295     }
296   };
297 
298   // Partial specialization for void*.
299   template <> struct ProgramStatePartialTrait<void *> {
300     using data_type = void *;
301 
302     static data_type MakeData(void *const *p) {
303       return p ? *p
304                : data_type();
305     }
306 
307     static void *MakeVoidPtr(data_type d) {
308       return d;
309     }
310   };
311 
312   // Partial specialization for const void *.
313   template <> struct ProgramStatePartialTrait<const void *> {
314     using data_type = const void *;
315 
316     static data_type MakeData(void *const *p) {
317       return p ? *p : data_type();
318     }
319 
320     static void *MakeVoidPtr(data_type d) {
321       return const_cast<void *>(d);
322     }
323   };
324 
325 } // namespace ento
326 } // namespace clang
327 
328 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATETRAIT_H
329