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