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

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