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