contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h

   1 //===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines some basic utility classes for use by ThreadSafetyTIL.h
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
  15 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
  16
  17 #include "clang/AST/Decl.h"
  18 #include "clang/Basic/LLVM.h"
  19 #include "llvm/ADT/StringRef.h"
  20 #include "llvm/ADT/iterator_range.h"
  21 #include "llvm/Support/Allocator.h"
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <cstring>
  25 #include <iterator>
  26 #include <ostream>
  27 #include <string>
  28 #include <vector>
  29
  30 namespace clang {
  31
  32 class Expr;
  33
  34 namespace threadSafety {
  35 namespace til {
  36
  37 // Simple wrapper class to abstract away from the details of memory management.
  38 // SExprs are allocated in pools, and deallocated all at once.
  39 class MemRegionRef {
  40 private:
  41   union AlignmentType {
  42     double d;
  43     void *p;
  44     long double dd;
  45     long long ii;
  46   };
  47
  48 public:
  49   MemRegionRef() = default;
  50   MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
  51
  52   void *allocate(size_t Sz) {
  53     return Allocator->Allocate(Sz, alignof(AlignmentType));
  54   }
  55
  56   template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
  57
  58   template <typename T> T *allocateT(size_t NumElems) {
  59     return Allocator->Allocate<T>(NumElems);
  60   }
  61
  62 private:
  63   llvm::BumpPtrAllocator *Allocator = nullptr;
  64 };
  65
  66 } // namespace til
  67 } // namespace threadSafety
  68
  69 } // namespace clang
  70
  71 inline void *operator new(size_t Sz,
  72                           clang::threadSafety::til::MemRegionRef &R) {
  73   return R.allocate(Sz);
  74 }
  75
  76 namespace clang {
  77 namespace threadSafety {
  78
  79 std::string getSourceLiteralString(const Expr *CE);
  80
  81 namespace til {
  82
  83 // A simple fixed size array class that does not manage its own memory,
  84 // suitable for use with bump pointer allocation.
  85 template <class T> class SimpleArray {
  86 public:
  87   SimpleArray() = default;
  88   SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
  89       : Data(Dat), Size(Sz), Capacity(Cp) {}
  90   SimpleArray(MemRegionRef A, size_t Cp)
  91       : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {}
  92   SimpleArray(const SimpleArray<T> &A) = delete;
  93
  94   SimpleArray(SimpleArray<T> &&A)
  95       : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
  96     A.Data = nullptr;
  97     A.Size = 0;
  98     A.Capacity = 0;
  99   }
 100
 101   SimpleArray &operator=(SimpleArray &&RHS) {
 102     if (this != &RHS) {
 103       Data = RHS.Data;
 104       Size = RHS.Size;
 105       Capacity = RHS.Capacity;
 106
 107       RHS.Data = nullptr;
 108       RHS.Size = RHS.Capacity = 0;
 109     }
 110     return *this;
 111   }
 112
 113   // Reserve space for at least Ncp items, reallocating if necessary.
 114   void reserve(size_t Ncp, MemRegionRef A) {
 115     if (Ncp <= Capacity)
 116       return;
 117     T *Odata = Data;
 118     Data = A.allocateT<T>(Ncp);
 119     Capacity = Ncp;
 120     memcpy(Data, Odata, sizeof(T) * Size);
 121   }
 122
 123   // Reserve space for at least N more items.
 124   void reserveCheck(size_t N, MemRegionRef A) {
 125     if (Capacity == 0)
 126       reserve(u_max(InitialCapacity, N), A);
 127     else if (Size + N < Capacity)
 128       reserve(u_max(Size + N, Capacity * 2), A);
 129   }
 130
 131   using iterator = T *;
 132   using const_iterator = const T *;
 133   using reverse_iterator = std::reverse_iterator<iterator>;
 134   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 135
 136   size_t size() const { return Size; }
 137   size_t capacity() const { return Capacity; }
 138
 139   T &operator[](unsigned i) {
 140     assert(i < Size && "Array index out of bounds.");
 141     return Data[i];
 142   }
 143
 144   const T &operator[](unsigned i) const {
 145     assert(i < Size && "Array index out of bounds.");
 146     return Data[i];
 147   }
 148
 149   T &back() {
 150     assert(Size && "No elements in the array.");
 151     return Data[Size - 1];
 152   }
 153
 154   const T &back() const {
 155     assert(Size && "No elements in the array.");
 156     return Data[Size - 1];
 157   }
 158
 159   iterator begin() { return Data; }
 160   iterator end() { return Data + Size; }
 161
 162   const_iterator begin() const { return Data; }
 163   const_iterator end() const { return Data + Size; }
 164
 165   const_iterator cbegin() const { return Data; }
 166   const_iterator cend() const { return Data + Size; }
 167
 168   reverse_iterator rbegin() { return reverse_iterator(end()); }
 169   reverse_iterator rend() { return reverse_iterator(begin()); }
 170
 171   const_reverse_iterator rbegin() const {
 172     return const_reverse_iterator(end());
 173   }
 174
 175   const_reverse_iterator rend() const {
 176     return const_reverse_iterator(begin());
 177   }
 178
 179   void push_back(const T &Elem) {
 180     assert(Size < Capacity);
 181     Data[Size++] = Elem;
 182   }
 183
 184   // drop last n elements from array
 185   void drop(unsigned n = 0) {
 186     assert(Size > n);
 187     Size -= n;
 188   }
 189
 190   void setValues(unsigned Sz, const T& C) {
 191     assert(Sz <= Capacity);
 192     Size = Sz;
 193     for (unsigned i = 0; i < Sz; ++i) {
 194       Data[i] = C;
 195     }
 196   }
 197
 198   template <class Iter> unsigned append(Iter I, Iter E) {
 199     size_t Osz = Size;
 200     size_t J = Osz;
 201     for (; J < Capacity && I != E; ++J, ++I)
 202       Data[J] = *I;
 203     Size = J;
 204     return J - Osz;
 205   }
 206
 207   llvm::iterator_range<reverse_iterator> reverse() {
 208     return llvm::make_range(rbegin(), rend());
 209   }
 210
 211   llvm::iterator_range<const_reverse_iterator> reverse() const {
 212     return llvm::make_range(rbegin(), rend());
 213   }
 214
 215 private:
 216   // std::max is annoying here, because it requires a reference,
 217   // thus forcing InitialCapacity to be initialized outside the .h file.
 218   size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
 219
 220   static const size_t InitialCapacity = 4;
 221
 222   T *Data = nullptr;
 223   size_t Size = 0;
 224   size_t Capacity = 0;
 225 };
 226
 227 }  // namespace til
 228
 229 // A copy on write vector.
 230 // The vector can be in one of three states:
 231 // * invalid -- no operations are permitted.
 232 // * read-only -- read operations are permitted.
 233 // * writable -- read and write operations are permitted.
 234 // The init(), destroy(), and makeWritable() methods will change state.
 235 template<typename T>
 236 class CopyOnWriteVector {
 237   class VectorData {
 238   public:
 239     unsigned NumRefs = 1;
 240     std::vector<T> Vect;
 241
 242     VectorData() = default;
 243     VectorData(const VectorData &VD) : Vect(VD.Vect) {}
 244   };
 245
 246 public:
 247   CopyOnWriteVector() = default;
 248   CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
 249
 250   CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
 251     destroy();
 252     Data = V.Data;
 253     V.Data = nullptr;
 254     return *this;
 255   }
 256
 257   // No copy constructor or copy assignment.  Use clone() with move assignment.
 258   CopyOnWriteVector(const CopyOnWriteVector &) = delete;
 259   CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete;
 260
 261   ~CopyOnWriteVector() { destroy(); }
 262
 263   // Returns true if this holds a valid vector.
 264   bool valid() const  { return Data; }
 265
 266   // Returns true if this vector is writable.
 267   bool writable() const { return Data && Data->NumRefs == 1; }
 268
 269   // If this vector is not valid, initialize it to a valid vector.
 270   void init() {
 271     if (!Data) {
 272       Data = new VectorData();
 273     }
 274   }
 275
 276   // Destroy this vector; thus making it invalid.
 277   void destroy() {
 278     if (!Data)
 279       return;
 280     if (Data->NumRefs <= 1)
 281       delete Data;
 282     else
 283       --Data->NumRefs;
 284     Data = nullptr;
 285   }
 286
 287   // Make this vector writable, creating a copy if needed.
 288   void makeWritable() {
 289     if (!Data) {
 290       Data = new VectorData();
 291       return;
 292     }
 293     if (Data->NumRefs == 1)
 294       return;   // already writeable.
 295     --Data->NumRefs;
 296     Data = new VectorData(*Data);
 297   }
 298
 299   // Create a lazy copy of this vector.
 300   CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
 301
 302   using const_iterator = typename std::vector<T>::const_iterator;
 303
 304   const std::vector<T> &elements() const { return Data->Vect; }
 305
 306   const_iterator begin() const { return elements().cbegin(); }
 307   const_iterator end() const { return elements().cend(); }
 308
 309   const T& operator[](unsigned i) const { return elements()[i]; }
 310
 311   unsigned size() const { return Data ? elements().size() : 0; }
 312
 313   // Return true if V and this vector refer to the same data.
 314   bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
 315
 316   // Clear vector.  The vector must be writable.
 317   void clear() {
 318     assert(writable() && "Vector is not writable!");
 319     Data->Vect.clear();
 320   }
 321
 322   // Push a new element onto the end.  The vector must be writable.
 323   void push_back(const T &Elem) {
 324     assert(writable() && "Vector is not writable!");
 325     Data->Vect.push_back(Elem);
 326   }
 327
 328   // Gets a mutable reference to the element at index(i).
 329   // The vector must be writable.
 330   T& elem(unsigned i) {
 331     assert(writable() && "Vector is not writable!");
 332     return Data->Vect[i];
 333   }
 334
 335   // Drops elements from the back until the vector has size i.
 336   void downsize(unsigned i) {
 337     assert(writable() && "Vector is not writable!");
 338     Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
 339   }
 340
 341 private:
 342   CopyOnWriteVector(VectorData *D) : Data(D) {
 343     if (!Data)
 344       return;
 345     ++Data->NumRefs;
 346   }
 347
 348   VectorData *Data = nullptr;
 349 };
 350
 351 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
 352   return ss.write(str.data(), str.size());
 353 }
 354
 355 } // namespace threadSafety
 356 } // namespace clang
 357
 358 #endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H