glslang/MachineIndependent/SymbolTable.h

   1 //
   2 //Copyright (C) 2002-2005  3Dlabs Inc. Ltd.
   3 //Copyright (C) 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 #ifndef _SYMBOL_TABLE_INCLUDED_
  38 #define _SYMBOL_TABLE_INCLUDED_
  39
  40 //
  41 // Symbol table for parsing.  Has these design characteristics:
  42 //
  43 // * Same symbol table can be used to compile many shaders, to preserve
  44 //   effort of creating and loading with the large numbers of built-in
  45 //   symbols.
  46 //
  47 // -->  This requires a copy mechanism, so initial pools used to create
  48 //   the shared information can be popped.  So, care is taken with
  49 //   copying pointers to point to new copies.  Done through "clone"
  50 //   methods.
  51 //
  52 // * Name mangling will be used to give each function a unique name
  53 //   so that symbol table lookups are never ambiguous.  This allows
  54 //   a simpler symbol table structure.
  55 //
  56 // * Pushing and popping of scope, so symbol table will really be a stack
  57 //   of symbol tables.  Searched from the top, with new inserts going into
  58 //   the top.
  59 //
  60 // * Constants:  Compile time constant symbols will keep their values
  61 //   in the symbol table.  The parser can substitute constants at parse
  62 //   time, including doing constant folding and constant propagation.
  63 //
  64 // * No temporaries:  Temporaries made from operations (+, --, .xy, etc.)
  65 //   are tracked in the intermediate representation, not the symbol table.
  66 //
  67
  68 #include "../Include/Common.h"
  69 #include "../Include/intermediate.h"
  70 #include "../Include/InfoSink.h"
  71
  72 //
  73 // Symbol base class.  (Can build functions or variables out of these...)
  74 //
  75 class TVariable;
  76 class TFunction;
  77 class TAnonMember;
  78 class TSymbol {
  79 public:
  80     POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
  81     explicit TSymbol(const TString *n) :  name(n) { }
  82         virtual TSymbol* clone(TStructureMap& remapper) = 0;
  83     virtual ~TSymbol() { }
  84
  85     const TString& getName() const { return *name; }
  86     void changeName(const char* buf) { name = new TString(buf); }
  87     virtual const TString& getMangledName() const { return getName(); }
  88     virtual TFunction* getAsFunction() { return 0; }
  89     virtual TVariable* getAsVariable() { return 0; }
  90     virtual TAnonMember* getAsAnonMember() { return 0; }
  91     void setUniqueId(int id) { uniqueId = id; }
  92     int getUniqueId() const { return uniqueId; }
  93     virtual void dump(TInfoSink &infoSink) const = 0;
  94
  95 protected:
  96         explicit TSymbol(const TSymbol&);
  97     TSymbol& operator=(const TSymbol&);
  98
  99     const TString *name;
 100     unsigned int uniqueId;      // For cross-scope comparing during code generation
 101 };
 102
 103 //
 104 // Variable class, meaning a symbol that's not a function.
 105 //
 106 // There could be a separate class heirarchy for Constant variables;
 107 // Only one of int, bool, or float, (or none) is correct for
 108 // any particular use, but it's easy to do this way, and doesn't
 109 // seem worth having separate classes, and "getConst" can't simply return
 110 // different values for different types polymorphically, so this is
 111 // just simple and pragmatic.
 112 //
 113 class TVariable : public TSymbol {
 114 public:
 115     TVariable(const TString *name, const TType& t, bool uT = false ) : TSymbol(name), type(t), userType(uT), unionArray(0), arrayInformationType(0) { }
 116         virtual TVariable* clone(TStructureMap& remapper);
 117     virtual ~TVariable() { }
 118
 119     virtual TVariable* getAsVariable() { return this; }
 120     TType& getType() { return type; }
 121     const TType& getType() const { return type; }
 122     bool isUserType() const { return userType; }
 123     void setStorageQualifier(TStorageQualifier qualifier) { type.getQualifier().storage = qualifier; }
 124     void updateArrayInformationType(TType *t) { arrayInformationType = t; }
 125     TType* getArrayInformationType() { return arrayInformationType; }
 126
 127     virtual void dump(TInfoSink &infoSink) const;
 128
 129     constUnion* getConstUnionPointer() {
 130         if (!unionArray)
 131             unionArray = new constUnion[type.getObjectSize()];
 132
 133         return unionArray;
 134     }
 135
 136     constUnion* getConstUnionPointer() const { return unionArray; }
 137
 138     void shareConstPointer( constUnion *constArray)
 139     {
 140         delete unionArray;
 141         unionArray = constArray;
 142     }
 143
 144 protected:
 145         explicit TVariable(TVariable&);
 146         TVariable(const TVariable&, TStructureMap& remapper);
 147     TVariable& operator=(TVariable&);
 148
 149     TType type;
 150     bool userType;
 151     // we are assuming that Pool Allocator will free the memory allocated to unionArray
 152     // when this object is destroyed
 153     constUnion *unionArray;
 154     TType *arrayInformationType;  // this is used for updating maxArraySize in all the references to a given symbol
 155 };
 156
 157 //
 158 // The function sub-class of symbols and the parser will need to
 159 // share this definition of a function parameter.
 160 //
 161 struct TParameter {
 162     TString *name;
 163     TType* type;
 164         void copyParam(const TParameter& param, const TStructureMap& remapper)
 165     {
 166                 if (param.name)
 167             name = NewPoolTString(param.name->c_str());
 168         else
 169             name = 0;
 170                 type = param.type->clone(remapper);
 171         }
 172 };
 173
 174 //
 175 // The function sub-class of a symbol.
 176 //
 177 class TFunction : public TSymbol {
 178 public:
 179     explicit TFunction(TOperator o) :
 180         TSymbol(0),
 181         returnType(TType(EbtVoid)),
 182         op(o),
 183         defined(false) { }
 184     TFunction(const TString *name, const TType& retType, TOperator tOp = EOpNull) :
 185         TSymbol(name),
 186         returnType(retType),
 187         mangledName(*name + '('),
 188         op(tOp),
 189         defined(false) { }
 190         virtual TFunction* clone(TStructureMap& remapper);
 191         virtual ~TFunction();
 192
 193     virtual TFunction* getAsFunction() { return this; }
 194
 195     void addParameter(TParameter& p)
 196     {
 197         parameters.push_back(p);
 198         mangledName = mangledName + p.type->getMangledName();
 199     }
 200
 201     const TString& getMangledName() const { return mangledName; }
 202     const TType& getReturnType() const { return returnType; }
 203     void relateToOperator(TOperator o) { op = o; }
 204     TOperator getBuiltInOp() const { return op; }
 205     void setDefined() { defined = true; }
 206     bool isDefined() { return defined; }
 207
 208     int getParamCount() const { return static_cast<int>(parameters.size()); }
 209           TParameter& operator [](int i)       { return parameters[i]; }
 210     const TParameter& operator [](int i) const { return parameters[i]; }
 211
 212     virtual void dump(TInfoSink &infoSink) const;
 213
 214 protected:
 215     explicit TFunction(TFunction&);
 216         TFunction(const TFunction&, const TStructureMap& remapper);
 217     TFunction& operator=(TFunction&);
 218
 219     typedef TVector<TParameter> TParamList;
 220         TParamList parameters;
 221     TType returnType;
 222     TString mangledName;
 223     TOperator op;
 224     bool defined;
 225 };
 226
 227 class TAnonMember : public TSymbol {
 228 public:
 229     TAnonMember(const TString* n, unsigned int m, TSymbol& a) : TSymbol(n), anonContainer(a), memberNumber(m) { }
 230         virtual TAnonMember* clone(TStructureMap& remapper);
 231     virtual ~TAnonMember() { }
 232
 233     TAnonMember* getAsAnonMember() { return this; }
 234     TSymbol& getAnonContainer() const { return anonContainer; }
 235     unsigned int getMemberNumber() const { return memberNumber; }
 236     virtual void dump(TInfoSink &infoSink) const;
 237
 238 protected:
 239     explicit TAnonMember(TAnonMember&);
 240     TAnonMember& operator=(TAnonMember&);
 241
 242     TSymbol& anonContainer;
 243     unsigned int memberNumber;
 244 };
 245
 246 class TSymbolTableLevel {
 247 public:
 248     POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
 249     TSymbolTableLevel() : defaultPrecision (0), anonId(0) { }
 250         ~TSymbolTableLevel();
 251
 252     bool insert(TSymbol& symbol)
 253     {
 254         //
 255         // returning true means symbol was added to the table
 256         //
 257         tInsertResult result;
 258         if (symbol.getName() == "") {
 259             // An empty name means an anonymous container, exposing its members to the external scope.
 260             // Give it a name and insert its members in the symbol table, pointing to the container.
 261             char buf[20];
 262             snprintf(buf, 20, "__anon__%d", anonId++);
 263             symbol.changeName(buf);
 264
 265             bool isOkay = true;
 266             TTypeList& types = *symbol.getAsVariable()->getType().getStruct();
 267             for (unsigned int m = 0; m < types.size(); ++m) {
 268                 TAnonMember* member = new TAnonMember(&types[m].type->getFieldName(), m, symbol);
 269                 result = level.insert(tLevelPair(member->getMangledName(), member));
 270                 if (! result.second)
 271                     isOkay = false;
 272             }
 273
 274             return isOkay;
 275         } else {
 276             result = level.insert(tLevelPair(symbol.getMangledName(), &symbol));
 277
 278             return result.second;
 279         }
 280     }
 281
 282     TSymbol* find(const TString& name) const
 283     {
 284         tLevel::const_iterator it = level.find(name);
 285         if (it == level.end())
 286             return 0;
 287         else
 288             return (*it).second;
 289     }
 290
 291     // Use this to do a lazy 'push' of precision defaults the first time
 292     // a precision statement is seen in a new scope.  Leave it at 0 for
 293     // when no push was needed.  Thus, it is not the current defaults,
 294     // it is what to restore the defaults to when popping a level.
 295     void setPreviousDefaultPrecisions(const TPrecisionQualifier *p)
 296     {
 297         // can call multiple times at one scope, will only latch on first call,
 298         // as we're tracking the previous scope's values, not the current values
 299         if (defaultPrecision != 0)
 300             return;
 301
 302         defaultPrecision = new TPrecisionQualifier[EbtNumTypes];
 303         for (int t = 0; t < EbtNumTypes; ++t)
 304             defaultPrecision[t] = p[t];
 305     }
 306
 307     void getPreviousDefaultPrecisions(TPrecisionQualifier *p)
 308     {
 309         // can be called for table level pops that didn't set the
 310         // defaults
 311         if (defaultPrecision == 0 || p == 0)
 312             return;
 313
 314         for (int t = 0; t < EbtNumTypes; ++t)
 315             p[t] = defaultPrecision[t];
 316     }
 317
 318     void relateToOperator(const char* name, TOperator op);
 319     void dump(TInfoSink &infoSink) const;
 320         TSymbolTableLevel* clone(TStructureMap& remapper);
 321
 322 protected:
 323     explicit TSymbolTableLevel(TSymbolTableLevel&);
 324     TSymbolTableLevel& operator=(TSymbolTableLevel&);
 325
 326     typedef std::map<TString, TSymbol*, std::less<TString>, pool_allocator<std::pair<const TString, TSymbol*> > > tLevel;
 327     typedef const tLevel::value_type tLevelPair;
 328     typedef std::pair<tLevel::iterator, bool> tInsertResult;
 329
 330     tLevel level;  // named mappings
 331     TPrecisionQualifier *defaultPrecision;
 332     int anonId;
 333 };
 334
 335 class TSymbolTable {
 336 public:
 337     TSymbolTable() : uniqueId(0)
 338     {
 339         //
 340         // The symbol table cannot be used until push() is called, but
 341         // the lack of an initial call to push() can be used to detect
 342         // that the symbol table has not been preloaded with built-ins.
 343         //
 344     }
 345     explicit TSymbolTable(TSymbolTable& symTable)
 346     {
 347         table.push_back(symTable.table[0]);
 348         uniqueId = symTable.uniqueId;
 349     }
 350     ~TSymbolTable()
 351     {
 352         // level 0 is always built In symbols, so we never pop that out
 353         while (table.size() > 1)
 354             pop(0);
 355     }
 356
 357     //
 358     // When the symbol table is initialized with the built-ins, there should
 359     // 'push' calls, so that built-ins are at level 0 and the shader
 360     // globals are at level 1.
 361     //
 362     bool isEmpty() { return table.size() == 0; }
 363     bool atBuiltInLevel() { return atSharedBuiltInLevel() || atDynamicBuiltInLevel(); }
 364     bool atSharedBuiltInLevel() { return table.size() == 1; }
 365     bool atGlobalLevel() { return table.size() <= 3; }
 366
 367     void push()
 368     {
 369         table.push_back(new TSymbolTableLevel);
 370     }
 371
 372     void pop(TPrecisionQualifier *p)
 373     {
 374         table[currentLevel()]->getPreviousDefaultPrecisions(p);
 375         delete table[currentLevel()];
 376         table.pop_back();
 377     }
 378
 379     bool insert(TSymbol& symbol)
 380     {
 381         symbol.setUniqueId(++uniqueId);
 382         return table[currentLevel()]->insert(symbol);
 383     }
 384
 385     TSymbol* find(const TString& name, bool* builtIn = 0, bool *sameScope = 0)
 386     {
 387         int level = currentLevel();
 388         TSymbol* symbol;
 389         do {
 390             symbol = table[level]->find(name);
 391             --level;
 392         } while (symbol == 0 && level >= 0);
 393         level++;
 394         if (builtIn)
 395             *builtIn = level == 0;
 396         if (sameScope)
 397             *sameScope = level == currentLevel();
 398         return symbol;
 399     }
 400
 401     TSymbolTableLevel* getGlobalLevel() { assert(table.size() >= 3); return table[2]; }
 402     void relateToOperator(const char* name, TOperator op) { table[0]->relateToOperator(name, op); }
 403     int getMaxSymbolId() { return uniqueId; }
 404     void dump(TInfoSink &infoSink) const;
 405         void copyTable(const TSymbolTable& copyOf);
 406
 407     void setPreviousDefaultPrecisions(TPrecisionQualifier *p) { table[currentLevel()]->setPreviousDefaultPrecisions(p); }
 408
 409 protected:
 410     TSymbolTable& operator=(TSymbolTableLevel&);
 411
 412     int currentLevel() const { return static_cast<int>(table.size()) - 1; }
 413     bool atDynamicBuiltInLevel() { return table.size() == 2; }
 414
 415     std::vector<TSymbolTableLevel*> table;
 416     int uniqueId;     // for unique identification in code generation
 417 };
 418
 419 #endif // _SYMBOL_TABLE_INCLUDED_