glslang/Include/arrays.h

   1 //
   2 // Copyright (C) 2002-2005  3Dlabs Inc. Ltd.
   3 // Copyright (C) 2012-2013 LunarG, Inc.
   4 //
   5 // All rights reserved.
   6 //
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions
   9 // are met:
  10 //
  11 //    Redistributions of source code must retain the above copyright
  12 //    notice, this list of conditions and the following disclaimer.
  13 //
  14 //    Redistributions in binary form must reproduce the above
  15 //    copyright notice, this list of conditions and the following
  16 //    disclaimer in the documentation and/or other materials provided
  17 //    with the distribution.
  18 //
  19 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  20 //    contributors may be used to endorse or promote products derived
  21 //    from this software without specific prior written permission.
  22 //
  23 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  27 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  31 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  33 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34 // POSSIBILITY OF SUCH DAMAGE.
  35 //
  36
  37 //
  38 // Implement types for tracking GLSL arrays, arrays of arrays, etc.
  39 //
  40
  41 #ifndef _ARRAYS_INCLUDED
  42 #define _ARRAYS_INCLUDED
  43
  44 #include <algorithm>
  45
  46 namespace glslang {
  47
  48 // This is used to mean there is no size yet (unsized), it is waiting to get a size from somewhere else.
  49 const int UnsizedArraySize = 0;
  50
  51 class TIntermTyped;
  52 extern bool SameSpecializationConstants(TIntermTyped*, TIntermTyped*);
  53
  54 // Specialization constants need both a nominal size and a node that defines
  55 // the specialization constant being used.  Array types are the same when their
  56 // size and specialization constant nodes are the same.
  57 struct TArraySize {
  58     unsigned int size;
  59     TIntermTyped* node;  // nullptr means no specialization constant node
  60     bool operator==(const TArraySize& rhs) const
  61     {
  62         if (size != rhs.size)
  63             return false;
  64         if (node == nullptr || rhs.node == nullptr)
  65             return node == rhs.node;
  66
  67         return SameSpecializationConstants(node, rhs.node);
  68     }
  69 };
  70
  71 //
  72 // TSmallArrayVector is used as the container for the set of sizes in TArraySizes.
  73 // It has generic-container semantics, while TArraySizes has array-of-array semantics.
  74 // That is, TSmallArrayVector should be more focused on mechanism and TArraySizes on policy.
  75 //
  76 struct TSmallArrayVector {
  77     //
  78     // TODO: memory: TSmallArrayVector is intended to be smaller.
  79     // Almost all arrays could be handled by two sizes each fitting
  80     // in 16 bits, needing a real vector only in the cases where there
  81     // are more than 3 sizes or a size needing more than 16 bits.
  82     //
  83     POOL_ALLOCATOR_NEW_DELETE(GetThreadPoolAllocator())
  84
  85     TSmallArrayVector() : sizes(nullptr) { }
  86     virtual ~TSmallArrayVector() { dealloc(); }
  87
  88     // For breaking into two non-shared copies, independently modifiable.
  89     TSmallArrayVector& operator=(const TSmallArrayVector& from)
  90     {
  91         if (from.sizes == nullptr)
  92             sizes = nullptr;
  93         else {
  94             alloc();
  95             *sizes = *from.sizes;
  96         }
  97
  98         return *this;
  99     }
 100
 101     int size() const
 102     {
 103         if (sizes == nullptr)
 104             return 0;
 105         return (int)sizes->size();
 106     }
 107
 108     unsigned int frontSize() const
 109     {
 110         assert(sizes != nullptr && sizes->size() > 0);
 111         return sizes->front().size;
 112     }
 113
 114     TIntermTyped* frontNode() const
 115     {
 116         assert(sizes != nullptr && sizes->size() > 0);
 117         return sizes->front().node;
 118     }
 119
 120     void changeFront(unsigned int s)
 121     {
 122         assert(sizes != nullptr);
 123         // this should only happen for implicitly sized arrays, not specialization constants
 124         assert(sizes->front().node == nullptr);
 125         sizes->front().size = s;
 126     }
 127
 128     void push_back(unsigned int e, TIntermTyped* n)
 129     {
 130         alloc();
 131         TArraySize pair = { e, n };
 132         sizes->push_back(pair);
 133     }
 134
 135     void push_back(const TSmallArrayVector& newDims)
 136     {
 137         alloc();
 138         sizes->insert(sizes->end(), newDims.sizes->begin(), newDims.sizes->end());
 139     }
 140
 141     void pop_front()
 142     {
 143         assert(sizes != nullptr && sizes->size() > 0);
 144         if (sizes->size() == 1)
 145             dealloc();
 146         else
 147             sizes->erase(sizes->begin());
 148     }
 149
 150     // 'this' should currently not be holding anything, and copyNonFront
 151     // will make it hold a copy of all but the first element of rhs.
 152     // (This would be useful for making a type that is dereferenced by
 153     // one dimension.)
 154     void copyNonFront(const TSmallArrayVector& rhs)
 155     {
 156         assert(sizes == nullptr);
 157         if (rhs.size() > 1) {
 158             alloc();
 159             sizes->insert(sizes->begin(), rhs.sizes->begin() + 1, rhs.sizes->end());
 160         }
 161     }
 162
 163     unsigned int getDimSize(int i) const
 164     {
 165         assert(sizes != nullptr && (int)sizes->size() > i);
 166         return (*sizes)[i].size;
 167     }
 168
 169     void setDimSize(int i, unsigned int size) const
 170     {
 171         assert(sizes != nullptr && (int)sizes->size() > i);
 172         assert((*sizes)[i].node == nullptr);
 173         (*sizes)[i].size = size;
 174     }
 175
 176     TIntermTyped* getDimNode(int i) const
 177     {
 178         assert(sizes != nullptr && (int)sizes->size() > i);
 179         return (*sizes)[i].node;
 180     }
 181
 182     bool operator==(const TSmallArrayVector& rhs) const
 183     {
 184         if (sizes == nullptr && rhs.sizes == nullptr)
 185             return true;
 186         if (sizes == nullptr || rhs.sizes == nullptr)
 187             return false;
 188         return *sizes == *rhs.sizes;
 189     }
 190     bool operator!=(const TSmallArrayVector& rhs) const { return ! operator==(rhs); }
 191
 192 protected:
 193     TSmallArrayVector(const TSmallArrayVector&);
 194
 195     void alloc()
 196     {
 197         if (sizes == nullptr)
 198             sizes = new TVector<TArraySize>;
 199     }
 200     void dealloc()
 201     {
 202         delete sizes;
 203         sizes = nullptr;
 204     }
 205
 206     TVector<TArraySize>* sizes; // will either hold such a pointer, or in the future, hold the two array sizes
 207 };
 208
 209 //
 210 // Represent an array, or array of arrays, to arbitrary depth.  This is not
 211 // done through a hierarchy of types in a type tree, rather all contiguous arrayness
 212 // in the type hierarchy is localized into this single cumulative object.
 213 //
 214 // The arrayness in TTtype is a pointer, so that it can be non-allocated and zero
 215 // for the vast majority of types that are non-array types.
 216 //
 217 // Order Policy: these are all identical:
 218 //  - left to right order within a contiguous set of ...[..][..][..]... in the source language
 219 //  - index order 0, 1, 2, ... within the 'sizes' member below
 220 //  - outer-most to inner-most
 221 //
 222 struct TArraySizes {
 223     POOL_ALLOCATOR_NEW_DELETE(GetThreadPoolAllocator())
 224
 225     TArraySizes() : implicitArraySize(1), variablyIndexed(false) { }
 226
 227     // For breaking into two non-shared copies, independently modifiable.
 228     TArraySizes& operator=(const TArraySizes& from)
 229     {
 230         implicitArraySize = from.implicitArraySize;
 231         variablyIndexed = from.variablyIndexed;
 232         sizes = from.sizes;
 233
 234         return *this;
 235     }
 236
 237     // translate from array-of-array semantics to container semantics
 238     int getNumDims() const { return sizes.size(); }
 239     int getDimSize(int dim) const { return sizes.getDimSize(dim); }
 240     TIntermTyped* getDimNode(int dim) const { return sizes.getDimNode(dim); }
 241     void setDimSize(int dim, int size) { sizes.setDimSize(dim, size); }
 242     int getOuterSize() const { return sizes.frontSize(); }
 243     TIntermTyped* getOuterNode() const { return sizes.frontNode(); }
 244     int getCumulativeSize() const
 245     {
 246         int size = 1;
 247         for (int d = 0; d < sizes.size(); ++d) {
 248             // this only makes sense in paths that have a known array size
 249             assert(sizes.getDimSize(d) != UnsizedArraySize);
 250             size *= sizes.getDimSize(d);
 251         }
 252         return size;
 253     }
 254     void addInnerSize() { addInnerSize((unsigned)UnsizedArraySize); }
 255     void addInnerSize(int s) { addInnerSize((unsigned)s, nullptr); }
 256     void addInnerSize(int s, TIntermTyped* n) { sizes.push_back((unsigned)s, n); }
 257     void addInnerSize(TArraySize pair) {
 258         sizes.push_back(pair.size, pair.node);
 259     }
 260     void addInnerSizes(const TArraySizes& s) { sizes.push_back(s.sizes); }
 261     void changeOuterSize(int s) { sizes.changeFront((unsigned)s); }
 262     int getImplicitSize() const { return implicitArraySize; }
 263     void updateImplicitSize(int s) { implicitArraySize = std::max(implicitArraySize, s); }
 264     bool isInnerUnsized() const
 265     {
 266         for (int d = 1; d < sizes.size(); ++d) {
 267             if (sizes.getDimSize(d) == (unsigned)UnsizedArraySize)
 268                 return true;
 269         }
 270
 271         return false;
 272     }
 273     bool clearInnerUnsized()
 274     {
 275         for (int d = 1; d < sizes.size(); ++d) {
 276             if (sizes.getDimSize(d) == (unsigned)UnsizedArraySize)
 277                 setDimSize(d, 1);
 278         }
 279
 280         return false;
 281     }
 282     bool isInnerSpecialization() const
 283     {
 284         for (int d = 1; d < sizes.size(); ++d) {
 285             if (sizes.getDimNode(d) != nullptr)
 286                 return true;
 287         }
 288
 289         return false;
 290     }
 291     bool isOuterSpecialization()
 292     {
 293         return sizes.getDimNode(0) != nullptr;
 294     }
 295
 296     bool hasUnsized() const { return getOuterSize() == UnsizedArraySize || isInnerUnsized(); }
 297     bool isSized() const { return getOuterSize() != UnsizedArraySize; }
 298     void dereference() { sizes.pop_front(); }
 299     void copyDereferenced(const TArraySizes& rhs)
 300     {
 301         assert(sizes.size() == 0);
 302         if (rhs.sizes.size() > 1)
 303             sizes.copyNonFront(rhs.sizes);
 304     }
 305
 306     bool sameInnerArrayness(const TArraySizes& rhs) const
 307     {
 308         if (sizes.size() != rhs.sizes.size())
 309             return false;
 310
 311         for (int d = 1; d < sizes.size(); ++d) {
 312             if (sizes.getDimSize(d) != rhs.sizes.getDimSize(d) ||
 313                 sizes.getDimNode(d) != rhs.sizes.getDimNode(d))
 314                 return false;
 315         }
 316
 317         return true;
 318     }
 319
 320     void setVariablyIndexed() { variablyIndexed = true; }
 321     bool isVariablyIndexed() const { return variablyIndexed; }
 322
 323     bool operator==(const TArraySizes& rhs) const { return sizes == rhs.sizes; }
 324     bool operator!=(const TArraySizes& rhs) const { return sizes != rhs.sizes; }
 325
 326 protected:
 327     TSmallArrayVector sizes;
 328
 329     TArraySizes(const TArraySizes&);
 330
 331     // For tracking maximum referenced compile-time constant index.
 332     // Applies only to the outer-most dimension. Potentially becomes
 333     // the implicit size of the array, if not variably indexed and
 334     // otherwise legal.
 335     int implicitArraySize;
 336     bool variablyIndexed;  // true if array is indexed with a non compile-time constant
 337 };
 338
 339 } // end namespace glslang
 340
 341 #endif // _ARRAYS_INCLUDED_