glslang/MachineIndependent/SymbolTable.h

   1 //
   2 // Copyright (C) 2002-2005  3Dlabs Inc. Ltd.
   3 // Copyright (C) 2013 LunarG, Inc.
   4 // Copyright (C) 2015-2018 Google, Inc.
   5 //
   6 // All rights reserved.
   7 //
   8 // Redistribution and use in source and binary forms, with or without
   9 // modification, are permitted provided that the following conditions
  10 // are met:
  11 //
  12 //    Redistributions of source code must retain the above copyright
  13 //    notice, this list of conditions and the following disclaimer.
  14 //
  15 //    Redistributions in binary form must reproduce the above
  16 //    copyright notice, this list of conditions and the following
  17 //    disclaimer in the documentation and/or other materials provided
  18 //    with the distribution.
  19 //
  20 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  21 //    contributors may be used to endorse or promote products derived
  22 //    from this software without specific prior written permission.
  23 //
  24 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  25 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  26 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  27 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  28 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  30 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  34 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  35 // POSSIBILITY OF SUCH DAMAGE.
  36 //
  37
  38 #ifndef _SYMBOL_TABLE_INCLUDED_
  39 #define _SYMBOL_TABLE_INCLUDED_
  40
  41 //
  42 // Symbol table for parsing.  Has these design characteristics:
  43 //
  44 // * Same symbol table can be used to compile many shaders, to preserve
  45 //   effort of creating and loading with the large numbers of built-in
  46 //   symbols.
  47 //
  48 // -->  This requires a copy mechanism, so initial pools used to create
  49 //   the shared information can be popped.  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 namespace glslang {
  73
  74 //
  75 // Symbol base class.  (Can build functions or variables out of these...)
  76 //
  77
  78 class TVariable;
  79 class TFunction;
  80 class TAnonMember;
  81
  82 typedef TVector<const char*> TExtensionList;
  83
  84 class TSymbol {
  85 public:
  86     POOL_ALLOCATOR_NEW_DELETE(GetThreadPoolAllocator())
  87     explicit TSymbol(const TString *n) :  name(n), uniqueId(0), extensions(nullptr), writable(true) { }
  88     virtual TSymbol* clone() const = 0;
  89     virtual ~TSymbol() { }  // rely on all symbol owned memory coming from the pool
  90
  91     virtual const TString& getName() const { return *name; }
  92     virtual void changeName(const TString* newName) { name = newName; }
  93     virtual void addPrefix(const char* prefix)
  94     {
  95         TString newName(prefix);
  96         newName.append(*name);
  97         changeName(NewPoolTString(newName.c_str()));
  98     }
  99     virtual const TString& getMangledName() const { return getName(); }
 100     virtual TFunction* getAsFunction() { return nullptr; }
 101     virtual const TFunction* getAsFunction() const { return nullptr; }
 102     virtual TVariable* getAsVariable() { return nullptr; }
 103     virtual const TVariable* getAsVariable() const { return nullptr; }
 104     virtual const TAnonMember* getAsAnonMember() const { return nullptr; }
 105     virtual const TType& getType() const = 0;
 106     virtual TType& getWritableType() = 0;
 107     virtual void setUniqueId(long long id) { uniqueId = id; }
 108     virtual long long getUniqueId() const { return uniqueId; }
 109     virtual void setExtensions(int numExts, const char* const exts[])
 110     {
 111         assert(extensions == nullptr);
 112         assert(numExts > 0);
 113         extensions = NewPoolObject(extensions);
 114         for (int e = 0; e < numExts; ++e)
 115             extensions->push_back(exts[e]);
 116     }
 117     virtual int getNumExtensions() const { return extensions == nullptr ? 0 : (int)extensions->size(); }
 118     virtual const char** getExtensions() const { return extensions->data(); }
 119
 120 #if !defined(GLSLANG_WEB)
 121     virtual void dump(TInfoSink& infoSink, bool complete = false) const = 0;
 122     void dumpExtensions(TInfoSink& infoSink) const;
 123 #endif
 124
 125     virtual bool isReadOnly() const { return ! writable; }
 126     virtual void makeReadOnly() { writable = false; }
 127
 128 protected:
 129     explicit TSymbol(const TSymbol&);
 130     TSymbol& operator=(const TSymbol&);
 131
 132     const TString *name;
 133     unsigned long long uniqueId;      // For cross-scope comparing during code generation
 134
 135     // For tracking what extensions must be present
 136     // (don't use if correct version/profile is present).
 137     TExtensionList* extensions; // an array of pointers to existing constant char strings
 138
 139     //
 140     // N.B.: Non-const functions that will be generally used should assert on this,
 141     // to avoid overwriting shared symbol-table information.
 142     //
 143     bool writable;
 144 };
 145
 146 //
 147 // Variable class, meaning a symbol that's not a function.
 148 //
 149 // There could be a separate class hierarchy for Constant variables;
 150 // Only one of int, bool, or float, (or none) is correct for
 151 // any particular use, but it's easy to do this way, and doesn't
 152 // seem worth having separate classes, and "getConst" can't simply return
 153 // different values for different types polymorphically, so this is
 154 // just simple and pragmatic.
 155 //
 156 class TVariable : public TSymbol {
 157 public:
 158     TVariable(const TString *name, const TType& t, bool uT = false )
 159         : TSymbol(name),
 160           userType(uT),
 161           constSubtree(nullptr),
 162           memberExtensions(nullptr),
 163           anonId(-1)
 164         { type.shallowCopy(t); }
 165     virtual TVariable* clone() const;
 166     virtual ~TVariable() { }
 167
 168     virtual TVariable* getAsVariable() { return this; }
 169     virtual const TVariable* getAsVariable() const { return this; }
 170     virtual const TType& getType() const { return type; }
 171     virtual TType& getWritableType() { assert(writable); return type; }
 172     virtual bool isUserType() const { return userType; }
 173     virtual const TConstUnionArray& getConstArray() const { return constArray; }
 174     virtual TConstUnionArray& getWritableConstArray() { assert(writable); return constArray; }
 175     virtual void setConstArray(const TConstUnionArray& array) { constArray = array; }
 176     virtual void setConstSubtree(TIntermTyped* subtree) { constSubtree = subtree; }
 177     virtual TIntermTyped* getConstSubtree() const { return constSubtree; }
 178     virtual void setAnonId(int i) { anonId = i; }
 179     virtual int getAnonId() const { return anonId; }
 180
 181     virtual void setMemberExtensions(int member, int numExts, const char* const exts[])
 182     {
 183         assert(type.isStruct());
 184         assert(numExts > 0);
 185         if (memberExtensions == nullptr) {
 186             memberExtensions = NewPoolObject(memberExtensions);
 187             memberExtensions->resize(type.getStruct()->size());
 188         }
 189         for (int e = 0; e < numExts; ++e)
 190             (*memberExtensions)[member].push_back(exts[e]);
 191     }
 192     virtual bool hasMemberExtensions() const { return memberExtensions != nullptr; }
 193     virtual int getNumMemberExtensions(int member) const
 194     {
 195         return memberExtensions == nullptr ? 0 : (int)(*memberExtensions)[member].size();
 196     }
 197     virtual const char** getMemberExtensions(int member) const { return (*memberExtensions)[member].data(); }
 198
 199 #if !defined(GLSLANG_WEB)
 200     virtual void dump(TInfoSink& infoSink, bool complete = false) const;
 201 #endif
 202
 203 protected:
 204     explicit TVariable(const TVariable&);
 205     TVariable& operator=(const TVariable&);
 206
 207     TType type;
 208     bool userType;
 209
 210     // we are assuming that Pool Allocator will free the memory allocated to unionArray
 211     // when this object is destroyed
 212
 213     TConstUnionArray constArray;               // for compile-time constant value
 214     TIntermTyped* constSubtree;                // for specialization constant computation
 215     TVector<TExtensionList>* memberExtensions; // per-member extension list, allocated only when needed
 216     int anonId; // the ID used for anonymous blocks: TODO: see if uniqueId could serve a dual purpose
 217 };
 218
 219 //
 220 // The function sub-class of symbols and the parser will need to
 221 // share this definition of a function parameter.
 222 //
 223 struct TParameter {
 224     TString *name;
 225     TType* type;
 226     TIntermTyped* defaultValue;
 227     TParameter& copyParam(const TParameter& param)
 228     {
 229         if (param.name)
 230             name = NewPoolTString(param.name->c_str());
 231         else
 232             name = nullptr;
 233         type = param.type->clone();
 234         defaultValue = param.defaultValue;
 235         return *this;
 236     }
 237     TBuiltInVariable getDeclaredBuiltIn() const { return type->getQualifier().declaredBuiltIn; }
 238 };
 239
 240 //
 241 // The function sub-class of a symbol.
 242 //
 243 class TFunction : public TSymbol {
 244 public:
 245     explicit TFunction(TOperator o) :
 246         TSymbol(nullptr),
 247         op(o),
 248         defined(false), prototyped(false), implicitThis(false), illegalImplicitThis(false), defaultParamCount(0) { }
 249     TFunction(const TString *name, const TType& retType, TOperator tOp = EOpNull) :
 250         TSymbol(name),
 251         mangledName(*name + '('),
 252         op(tOp),
 253         defined(false), prototyped(false), implicitThis(false), illegalImplicitThis(false), defaultParamCount(0)
 254     {
 255         returnType.shallowCopy(retType);
 256         declaredBuiltIn = retType.getQualifier().builtIn;
 257     }
 258     virtual TFunction* clone() const override;
 259     virtual ~TFunction();
 260
 261     virtual TFunction* getAsFunction() override { return this; }
 262     virtual const TFunction* getAsFunction() const override { return this; }
 263
 264     // Install 'p' as the (non-'this') last parameter.
 265     // Non-'this' parameters are reflected in both the list of parameters and the
 266     // mangled name.
 267     virtual void addParameter(TParameter& p)
 268     {
 269         assert(writable);
 270         parameters.push_back(p);
 271         p.type->appendMangledName(mangledName);
 272
 273         if (p.defaultValue != nullptr)
 274             defaultParamCount++;
 275     }
 276
 277     // Install 'this' as the first parameter.
 278     // 'this' is reflected in the list of parameters, but not the mangled name.
 279     virtual void addThisParameter(TType& type, const char* name)
 280     {
 281         TParameter p = { NewPoolTString(name), new TType, nullptr };
 282         p.type->shallowCopy(type);
 283         parameters.insert(parameters.begin(), p);
 284     }
 285
 286     virtual void addPrefix(const char* prefix) override
 287     {
 288         TSymbol::addPrefix(prefix);
 289         mangledName.insert(0, prefix);
 290     }
 291
 292     virtual void removePrefix(const TString& prefix)
 293     {
 294         assert(mangledName.compare(0, prefix.size(), prefix) == 0);
 295         mangledName.erase(0, prefix.size());
 296     }
 297
 298     virtual const TString& getMangledName() const override { return mangledName; }
 299     virtual const TType& getType() const override { return returnType; }
 300     virtual TBuiltInVariable getDeclaredBuiltInType() const { return declaredBuiltIn; }
 301     virtual TType& getWritableType() override { return returnType; }
 302     virtual void relateToOperator(TOperator o) { assert(writable); op = o; }
 303     virtual TOperator getBuiltInOp() const { return op; }
 304     virtual void setDefined() { assert(writable); defined = true; }
 305     virtual bool isDefined() const { return defined; }
 306     virtual void setPrototyped() { assert(writable); prototyped = true; }
 307     virtual bool isPrototyped() const { return prototyped; }
 308     virtual void setImplicitThis() { assert(writable); implicitThis = true; }
 309     virtual bool hasImplicitThis() const { return implicitThis; }
 310     virtual void setIllegalImplicitThis() { assert(writable); illegalImplicitThis = true; }
 311     virtual bool hasIllegalImplicitThis() const { return illegalImplicitThis; }
 312
 313     // Return total number of parameters
 314     virtual int getParamCount() const { return static_cast<int>(parameters.size()); }
 315     // Return number of parameters with default values.
 316     virtual int getDefaultParamCount() const { return defaultParamCount; }
 317     // Return number of fixed parameters (without default values)
 318     virtual int getFixedParamCount() const { return getParamCount() - getDefaultParamCount(); }
 319
 320     virtual TParameter& operator[](int i) { assert(writable); return parameters[i]; }
 321     virtual const TParameter& operator[](int i) const { return parameters[i]; }
 322     const TQualifier& getQualifier() const { return returnType.getQualifier(); }
 323
 324 #ifndef GLSLANG_WEB
 325     virtual void setSpirvInstruction(const TSpirvInstruction& inst)
 326     {
 327         relateToOperator(EOpSpirvInst);
 328         spirvInst = inst;
 329     }
 330     virtual const TSpirvInstruction& getSpirvInstruction() const { return spirvInst; }
 331 #endif
 332
 333 #if !defined(GLSLANG_WEB)
 334     virtual void dump(TInfoSink& infoSink, bool complete = false) const override;
 335 #endif
 336
 337 protected:
 338     explicit TFunction(const TFunction&);
 339     TFunction& operator=(const TFunction&);
 340
 341     typedef TVector<TParameter> TParamList;
 342     TParamList parameters;
 343     TType returnType;
 344     TBuiltInVariable declaredBuiltIn;
 345
 346     TString mangledName;
 347     TOperator op;
 348     bool defined;
 349     bool prototyped;
 350     bool implicitThis;         // True if this function is allowed to see all members of 'this'
 351     bool illegalImplicitThis;  // True if this function is not supposed to have access to dynamic members of 'this',
 352                                // even if it finds member variables in the symbol table.
 353                                // This is important for a static member function that has member variables in scope,
 354                                // but is not allowed to use them, or see hidden symbols instead.
 355     int  defaultParamCount;
 356
 357 #ifndef GLSLANG_WEB
 358     TSpirvInstruction spirvInst; // SPIR-V instruction qualifiers
 359 #endif
 360 };
 361
 362 //
 363 // Members of anonymous blocks are a kind of TSymbol.  They are not hidden in
 364 // the symbol table behind a container; rather they are visible and point to
 365 // their anonymous container.  (The anonymous container is found through the
 366 // member, not the other way around.)
 367 //
 368 class TAnonMember : public TSymbol {
 369 public:
 370     TAnonMember(const TString* n, unsigned int m, TVariable& a, int an) : TSymbol(n), anonContainer(a), memberNumber(m), anonId(an) { }
 371     virtual TAnonMember* clone() const override;
 372     virtual ~TAnonMember() { }
 373
 374     virtual const TAnonMember* getAsAnonMember() const override { return this; }
 375     virtual const TVariable& getAnonContainer() const { return anonContainer; }
 376     virtual unsigned int getMemberNumber() const { return memberNumber; }
 377
 378     virtual const TType& getType() const override
 379     {
 380         const TTypeList& types = *anonContainer.getType().getStruct();
 381         return *types[memberNumber].type;
 382     }
 383
 384     virtual TType& getWritableType() override
 385     {
 386         assert(writable);
 387         const TTypeList& types = *anonContainer.getType().getStruct();
 388         return *types[memberNumber].type;
 389     }
 390
 391     virtual void setExtensions(int numExts, const char* const exts[]) override
 392     {
 393         anonContainer.setMemberExtensions(memberNumber, numExts, exts);
 394     }
 395     virtual int getNumExtensions() const override { return anonContainer.getNumMemberExtensions(memberNumber); }
 396     virtual const char** getExtensions() const override { return anonContainer.getMemberExtensions(memberNumber); }
 397
 398     virtual int getAnonId() const { return anonId; }
 399 #if !defined(GLSLANG_WEB)
 400     virtual void dump(TInfoSink& infoSink, bool complete = false) const override;
 401 #endif
 402
 403 protected:
 404     explicit TAnonMember(const TAnonMember&);
 405     TAnonMember& operator=(const TAnonMember&);
 406
 407     TVariable& anonContainer;
 408     unsigned int memberNumber;
 409     int anonId;
 410 };
 411
 412 class TSymbolTableLevel {
 413 public:
 414     POOL_ALLOCATOR_NEW_DELETE(GetThreadPoolAllocator())
 415     TSymbolTableLevel() : defaultPrecision(nullptr), anonId(0), thisLevel(false) { }
 416     ~TSymbolTableLevel();
 417
 418     bool insert(const TString& name, TSymbol* symbol) {
 419         return level.insert(tLevelPair(name, symbol)).second;
 420     }
 421
 422     bool insert(TSymbol& symbol, bool separateNameSpaces, const TString& forcedKeyName = TString())
 423     {
 424         //
 425         // returning true means symbol was added to the table with no semantic errors
 426         //
 427         const TString& name = symbol.getName();
 428         if (forcedKeyName.length()) {
 429             return level.insert(tLevelPair(forcedKeyName, &symbol)).second;
 430         }
 431         else if (name == "") {
 432             symbol.getAsVariable()->setAnonId(anonId++);
 433             // An empty name means an anonymous container, exposing its members to the external scope.
 434             // Give it a name and insert its members in the symbol table, pointing to the container.
 435             char buf[20];
 436             snprintf(buf, 20, "%s%d", AnonymousPrefix, symbol.getAsVariable()->getAnonId());
 437             symbol.changeName(NewPoolTString(buf));
 438
 439             return insertAnonymousMembers(symbol, 0);
 440         } else {
 441             // Check for redefinition errors:
 442             // - STL itself will tell us if there is a direct name collision, with name mangling, at this level
 443             // - additionally, check for function-redefining-variable name collisions
 444             const TString& insertName = symbol.getMangledName();
 445             if (symbol.getAsFunction()) {
 446                 // make sure there isn't a variable of this name
 447                 if (! separateNameSpaces && level.find(name) != level.end())
 448                     return false;
 449
 450                 // insert, and whatever happens is okay
 451                 level.insert(tLevelPair(insertName, &symbol));
 452
 453                 return true;
 454             } else
 455                 return level.insert(tLevelPair(insertName, &symbol)).second;
 456         }
 457     }
 458
 459     // Add more members to an already inserted aggregate object
 460     bool amend(TSymbol& symbol, int firstNewMember)
 461     {
 462         // See insert() for comments on basic explanation of insert.
 463         // This operates similarly, but more simply.
 464         // Only supporting amend of anonymous blocks so far.
 465         if (IsAnonymous(symbol.getName()))
 466             return insertAnonymousMembers(symbol, firstNewMember);
 467         else
 468             return false;
 469     }
 470
 471     bool insertAnonymousMembers(TSymbol& symbol, int firstMember)
 472     {
 473         const TTypeList& types = *symbol.getAsVariable()->getType().getStruct();
 474         for (unsigned int m = firstMember; m < types.size(); ++m) {
 475             TAnonMember* member = new TAnonMember(&types[m].type->getFieldName(), m, *symbol.getAsVariable(), symbol.getAsVariable()->getAnonId());
 476             if (! level.insert(tLevelPair(member->getMangledName(), member)).second)
 477                 return false;
 478         }
 479
 480         return true;
 481     }
 482
 483     void retargetSymbol(const TString& from, const TString& to) {
 484         tLevel::const_iterator fromIt = level.find(from);
 485         tLevel::const_iterator toIt = level.find(to);
 486         if (fromIt == level.end() || toIt == level.end())
 487             return;
 488         delete fromIt->second;
 489         level[from] = toIt->second;
 490         retargetedSymbols.push_back({from, to});
 491     }
 492
 493     TSymbol* find(const TString& name) const
 494     {
 495         tLevel::const_iterator it = level.find(name);
 496         if (it == level.end())
 497             return nullptr;
 498         else
 499             return (*it).second;
 500     }
 501
 502     void findFunctionNameList(const TString& name, TVector<const TFunction*>& list)
 503     {
 504         size_t parenAt = name.find_first_of('(');
 505         TString base(name, 0, parenAt + 1);
 506
 507         tLevel::const_iterator begin = level.lower_bound(base);
 508         base[parenAt] = ')';  // assume ')' is lexically after '('
 509         tLevel::const_iterator end = level.upper_bound(base);
 510         for (tLevel::const_iterator it = begin; it != end; ++it)
 511             list.push_back(it->second->getAsFunction());
 512     }
 513
 514     // See if there is already a function in the table having the given non-function-style name.
 515     bool hasFunctionName(const TString& name) const
 516     {
 517         tLevel::const_iterator candidate = level.lower_bound(name);
 518         if (candidate != level.end()) {
 519             const TString& candidateName = (*candidate).first;
 520             TString::size_type parenAt = candidateName.find_first_of('(');
 521             if (parenAt != candidateName.npos && candidateName.compare(0, parenAt, name) == 0)
 522
 523                 return true;
 524         }
 525
 526         return false;
 527     }
 528
 529     // See if there is a variable at this level having the given non-function-style name.
 530     // Return true if name is found, and set variable to true if the name was a variable.
 531     bool findFunctionVariableName(const TString& name, bool& variable) const
 532     {
 533         tLevel::const_iterator candidate = level.lower_bound(name);
 534         if (candidate != level.end()) {
 535             const TString& candidateName = (*candidate).first;
 536             TString::size_type parenAt = candidateName.find_first_of('(');
 537             if (parenAt == candidateName.npos) {
 538                 // not a mangled name
 539                 if (candidateName == name) {
 540                     // found a variable name match
 541                     variable = true;
 542                     return true;
 543                 }
 544             } else {
 545                 // a mangled name
 546                 if (candidateName.compare(0, parenAt, name) == 0) {
 547                     // found a function name match
 548                     variable = false;
 549                     return true;
 550                 }
 551             }
 552         }
 553
 554         return false;
 555     }
 556
 557     // Use this to do a lazy 'push' of precision defaults the first time
 558     // a precision statement is seen in a new scope.  Leave it at 0 for
 559     // when no push was needed.  Thus, it is not the current defaults,
 560     // it is what to restore the defaults to when popping a level.
 561     void setPreviousDefaultPrecisions(const TPrecisionQualifier *p)
 562     {
 563         // can call multiple times at one scope, will only latch on first call,
 564         // as we're tracking the previous scope's values, not the current values
 565         if (defaultPrecision != nullptr)
 566             return;
 567
 568         defaultPrecision = new TPrecisionQualifier[EbtNumTypes];
 569         for (int t = 0; t < EbtNumTypes; ++t)
 570             defaultPrecision[t] = p[t];
 571     }
 572
 573     void getPreviousDefaultPrecisions(TPrecisionQualifier *p)
 574     {
 575         // can be called for table level pops that didn't set the
 576         // defaults
 577         if (defaultPrecision == nullptr || p == nullptr)
 578             return;
 579
 580         for (int t = 0; t < EbtNumTypes; ++t)
 581             p[t] = defaultPrecision[t];
 582     }
 583
 584     void relateToOperator(const char* name, TOperator op);
 585     void setFunctionExtensions(const char* name, int num, const char* const extensions[]);
 586 #if !defined(GLSLANG_WEB)
 587     void dump(TInfoSink& infoSink, bool complete = false) const;
 588 #endif
 589     TSymbolTableLevel* clone() const;
 590     void readOnly();
 591
 592     void setThisLevel() { thisLevel = true; }
 593     bool isThisLevel() const { return thisLevel; }
 594
 595 protected:
 596     explicit TSymbolTableLevel(TSymbolTableLevel&);
 597     TSymbolTableLevel& operator=(TSymbolTableLevel&);
 598
 599     typedef std::map<TString, TSymbol*, std::less<TString>, pool_allocator<std::pair<const TString, TSymbol*> > > tLevel;
 600     typedef const tLevel::value_type tLevelPair;
 601     typedef std::pair<tLevel::iterator, bool> tInsertResult;
 602
 603     tLevel level;  // named mappings
 604     TPrecisionQualifier *defaultPrecision;
 605     // pair<FromName, ToName>
 606     TVector<std::pair<TString, TString>> retargetedSymbols;
 607     int anonId;
 608     bool thisLevel;  // True if this level of the symbol table is a structure scope containing member function
 609                      // that are supposed to see anonymous access to member variables.
 610 };
 611
 612 class TSymbolTable {
 613 public:
 614     TSymbolTable() : uniqueId(0), noBuiltInRedeclarations(false), separateNameSpaces(false), adoptedLevels(0)
 615     {
 616         //
 617         // This symbol table cannot be used until push() is called.
 618         //
 619     }
 620     ~TSymbolTable()
 621     {
 622         // this can be called explicitly; safest to code it so it can be called multiple times
 623
 624         // don't deallocate levels passed in from elsewhere
 625         while (table.size() > adoptedLevels)
 626             pop(nullptr);
 627     }
 628
 629     void adoptLevels(TSymbolTable& symTable)
 630     {
 631         for (unsigned int level = 0; level < symTable.table.size(); ++level) {
 632             table.push_back(symTable.table[level]);
 633             ++adoptedLevels;
 634         }
 635         uniqueId = symTable.uniqueId;
 636         noBuiltInRedeclarations = symTable.noBuiltInRedeclarations;
 637         separateNameSpaces = symTable.separateNameSpaces;
 638     }
 639
 640     //
 641     // While level adopting is generic, the methods below enact a the following
 642     // convention for levels:
 643     //   0: common built-ins shared across all stages, all compiles, only one copy for all symbol tables
 644     //   1: per-stage built-ins, shared across all compiles, but a different copy per stage
 645     //   2: built-ins specific to a compile, like resources that are context-dependent, or redeclared built-ins
 646     //   3: user-shader globals
 647     //
 648 protected:
 649     static const uint32_t LevelFlagBitOffset = 56;
 650     static const int globalLevel = 3;
 651     static bool isSharedLevel(int level)  { return level <= 1; }            // exclude all per-compile levels
 652     static bool isBuiltInLevel(int level) { return level <= 2; }            // exclude user globals
 653     static bool isGlobalLevel(int level)  { return level <= globalLevel; }  // include user globals
 654 public:
 655     bool isEmpty() { return table.size() == 0; }
 656     bool atBuiltInLevel() { return isBuiltInLevel(currentLevel()); }
 657     bool atGlobalLevel()  { return isGlobalLevel(currentLevel()); }
 658     static bool isBuiltInSymbol(long long uniqueId) {
 659         int level = static_cast<int>(uniqueId >> LevelFlagBitOffset);
 660         return isBuiltInLevel(level);
 661     }
 662     static constexpr uint64_t uniqueIdMask = (1LL << LevelFlagBitOffset) - 1;
 663     static const uint32_t MaxLevelInUniqueID = 127;
 664     void setNoBuiltInRedeclarations() { noBuiltInRedeclarations = true; }
 665     void setSeparateNameSpaces() { separateNameSpaces = true; }
 666
 667     void push()
 668     {
 669         table.push_back(new TSymbolTableLevel);
 670         updateUniqueIdLevelFlag();
 671     }
 672
 673     // Make a new symbol-table level to represent the scope introduced by a structure
 674     // containing member functions, such that the member functions can find anonymous
 675     // references to member variables.
 676     //
 677     // 'thisSymbol' should have a name of "" to trigger anonymous structure-member
 678     // symbol finds.
 679     void pushThis(TSymbol& thisSymbol)
 680     {
 681         assert(thisSymbol.getName().size() == 0);
 682         table.push_back(new TSymbolTableLevel);
 683         updateUniqueIdLevelFlag();
 684         table.back()->setThisLevel();
 685         insert(thisSymbol);
 686     }
 687
 688     void pop(TPrecisionQualifier *p)
 689     {
 690         table[currentLevel()]->getPreviousDefaultPrecisions(p);
 691         delete table.back();
 692         table.pop_back();
 693         updateUniqueIdLevelFlag();
 694     }
 695
 696     //
 697     // Insert a visible symbol into the symbol table so it can
 698     // be found later by name.
 699     //
 700     // Returns false if the was a name collision.
 701     //
 702     bool insert(TSymbol& symbol)
 703     {
 704         symbol.setUniqueId(++uniqueId);
 705
 706         // make sure there isn't a function of this variable name
 707         if (! separateNameSpaces && ! symbol.getAsFunction() && table[currentLevel()]->hasFunctionName(symbol.getName()))
 708             return false;
 709
 710         // check for not overloading or redefining a built-in function
 711         if (noBuiltInRedeclarations) {
 712             if (atGlobalLevel() && currentLevel() > 0) {
 713                 if (table[0]->hasFunctionName(symbol.getName()))
 714                     return false;
 715                 if (currentLevel() > 1 && table[1]->hasFunctionName(symbol.getName()))
 716                     return false;
 717             }
 718         }
 719
 720         return table[currentLevel()]->insert(symbol, separateNameSpaces);
 721     }
 722
 723     // Add more members to an already inserted aggregate object
 724     bool amend(TSymbol& symbol, int firstNewMember)
 725     {
 726         // See insert() for comments on basic explanation of insert.
 727         // This operates similarly, but more simply.
 728         return table[currentLevel()]->amend(symbol, firstNewMember);
 729     }
 730
 731     // Update the level info in symbol's unique ID to current level
 732     void amendSymbolIdLevel(TSymbol& symbol)
 733     {
 734         // clamp level to avoid overflow
 735         uint64_t level = (uint32_t)currentLevel() > MaxLevelInUniqueID ? MaxLevelInUniqueID : currentLevel();
 736         uint64_t symbolId = symbol.getUniqueId();
 737         symbolId &= uniqueIdMask;
 738         symbolId |= (level << LevelFlagBitOffset);
 739         symbol.setUniqueId(symbolId);
 740     }
 741     //
 742     // To allocate an internal temporary, which will need to be uniquely
 743     // identified by the consumer of the AST, but never need to
 744     // found by doing a symbol table search by name, hence allowed an
 745     // arbitrary name in the symbol with no worry of collision.
 746     //
 747     void makeInternalVariable(TSymbol& symbol)
 748     {
 749         symbol.setUniqueId(++uniqueId);
 750     }
 751
 752     //
 753     // Copy a variable or anonymous member's structure from a shared level so that
 754     // it can be added (soon after return) to the symbol table where it can be
 755     // modified without impacting other users of the shared table.
 756     //
 757     TSymbol* copyUpDeferredInsert(TSymbol* shared)
 758     {
 759         if (shared->getAsVariable()) {
 760             TSymbol* copy = shared->clone();
 761             copy->setUniqueId(shared->getUniqueId());
 762             return copy;
 763         } else {
 764             const TAnonMember* anon = shared->getAsAnonMember();
 765             assert(anon);
 766             TVariable* container = anon->getAnonContainer().clone();
 767             container->changeName(NewPoolTString(""));
 768             container->setUniqueId(anon->getAnonContainer().getUniqueId());
 769             return container;
 770         }
 771     }
 772
 773     TSymbol* copyUp(TSymbol* shared)
 774     {
 775         TSymbol* copy = copyUpDeferredInsert(shared);
 776         table[globalLevel]->insert(*copy, separateNameSpaces);
 777         if (shared->getAsVariable())
 778             return copy;
 779         else {
 780             // return the copy of the anonymous member
 781             return table[globalLevel]->find(shared->getName());
 782         }
 783     }
 784
 785     // Normal find of a symbol, that can optionally say whether the symbol was found
 786     // at a built-in level or the current top-scope level.
 787     TSymbol* find(const TString& name, bool* builtIn = nullptr, bool* currentScope = nullptr, int* thisDepthP = nullptr)
 788     {
 789         int level = currentLevel();
 790         TSymbol* symbol;
 791         int thisDepth = 0;
 792         do {
 793             if (table[level]->isThisLevel())
 794                 ++thisDepth;
 795             symbol = table[level]->find(name);
 796             --level;
 797         } while (symbol == nullptr && level >= 0);
 798         level++;
 799         if (builtIn)
 800             *builtIn = isBuiltInLevel(level);
 801         if (currentScope)
 802             *currentScope = isGlobalLevel(currentLevel()) || level == currentLevel();  // consider shared levels as "current scope" WRT user globals
 803         if (thisDepthP != nullptr) {
 804             if (! table[level]->isThisLevel())
 805                 thisDepth = 0;
 806             *thisDepthP = thisDepth;
 807         }
 808
 809         return symbol;
 810     }
 811
 812     void retargetSymbol(const TString& from, const TString& to) {
 813         int level = currentLevel();
 814         table[level]->retargetSymbol(from, to);
 815     }
 816
 817
 818     // Find of a symbol that returns how many layers deep of nested
 819     // structures-with-member-functions ('this' scopes) deep the symbol was
 820     // found in.
 821     TSymbol* find(const TString& name, int& thisDepth)
 822     {
 823         int level = currentLevel();
 824         TSymbol* symbol;
 825         thisDepth = 0;
 826         do {
 827             if (table[level]->isThisLevel())
 828                 ++thisDepth;
 829             symbol = table[level]->find(name);
 830             --level;
 831         } while (symbol == nullptr && level >= 0);
 832
 833         if (! table[level + 1]->isThisLevel())
 834             thisDepth = 0;
 835
 836         return symbol;
 837     }
 838
 839     bool isFunctionNameVariable(const TString& name) const
 840     {
 841         if (separateNameSpaces)
 842             return false;
 843
 844         int level = currentLevel();
 845         do {
 846             bool variable;
 847             bool found = table[level]->findFunctionVariableName(name, variable);
 848             if (found)
 849                 return variable;
 850             --level;
 851         } while (level >= 0);
 852
 853         return false;
 854     }
 855
 856     void findFunctionNameList(const TString& name, TVector<const TFunction*>& list, bool& builtIn)
 857     {
 858         // For user levels, return the set found in the first scope with a match
 859         builtIn = false;
 860         int level = currentLevel();
 861         do {
 862             table[level]->findFunctionNameList(name, list);
 863             --level;
 864         } while (list.empty() && level >= globalLevel);
 865
 866         if (! list.empty())
 867             return;
 868
 869         // Gather across all built-in levels; they don't hide each other
 870         builtIn = true;
 871         do {
 872             table[level]->findFunctionNameList(name, list);
 873             --level;
 874         } while (level >= 0);
 875     }
 876
 877     void relateToOperator(const char* name, TOperator op)
 878     {
 879         for (unsigned int level = 0; level < table.size(); ++level)
 880             table[level]->relateToOperator(name, op);
 881     }
 882
 883     void setFunctionExtensions(const char* name, int num, const char* const extensions[])
 884     {
 885         for (unsigned int level = 0; level < table.size(); ++level)
 886             table[level]->setFunctionExtensions(name, num, extensions);
 887     }
 888
 889     void setVariableExtensions(const char* name, int numExts, const char* const extensions[])
 890     {
 891         TSymbol* symbol = find(TString(name));
 892         if (symbol == nullptr)
 893             return;
 894
 895         symbol->setExtensions(numExts, extensions);
 896     }
 897
 898     void setVariableExtensions(const char* blockName, const char* name, int numExts, const char* const extensions[])
 899     {
 900         TSymbol* symbol = find(TString(blockName));
 901         if (symbol == nullptr)
 902             return;
 903         TVariable* variable = symbol->getAsVariable();
 904         assert(variable != nullptr);
 905
 906         const TTypeList& structure = *variable->getAsVariable()->getType().getStruct();
 907         for (int member = 0; member < (int)structure.size(); ++member) {
 908             if (structure[member].type->getFieldName().compare(name) == 0) {
 909                 variable->setMemberExtensions(member, numExts, extensions);
 910                 return;
 911             }
 912         }
 913     }
 914
 915     long long getMaxSymbolId() { return uniqueId; }
 916 #if !defined(GLSLANG_WEB)
 917     void dump(TInfoSink& infoSink, bool complete = false) const;
 918 #endif
 919     void copyTable(const TSymbolTable& copyOf);
 920
 921     void setPreviousDefaultPrecisions(TPrecisionQualifier *p) { table[currentLevel()]->setPreviousDefaultPrecisions(p); }
 922
 923     void readOnly()
 924     {
 925         for (unsigned int level = 0; level < table.size(); ++level)
 926             table[level]->readOnly();
 927     }
 928
 929     // Add current level in the high-bits of unique id
 930     void updateUniqueIdLevelFlag() {
 931         // clamp level to avoid overflow
 932         uint64_t level = (uint32_t)currentLevel() > MaxLevelInUniqueID ? MaxLevelInUniqueID : currentLevel();
 933         uniqueId &= uniqueIdMask;
 934         uniqueId |= (level << LevelFlagBitOffset);
 935     }
 936
 937     void overwriteUniqueId(long long id)
 938     {
 939         uniqueId = id;
 940         updateUniqueIdLevelFlag();
 941     }
 942
 943 protected:
 944     TSymbolTable(TSymbolTable&);
 945     TSymbolTable& operator=(TSymbolTableLevel&);
 946
 947     int currentLevel() const { return static_cast<int>(table.size()) - 1; }
 948     std::vector<TSymbolTableLevel*> table;
 949     long long uniqueId;     // for unique identification in code generation
 950     bool noBuiltInRedeclarations;
 951     bool separateNameSpaces;
 952     unsigned int adoptedLevels;
 953 };
 954
 955 } // end namespace glslang
 956
 957 #endif // _SYMBOL_TABLE_INCLUDED_