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), extensions(0), 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 0; }
 101     virtual const TFunction* getAsFunction() const { return 0; }
 102     virtual TVariable* getAsVariable() { return 0; }
 103     virtual const TVariable* getAsVariable() const { return 0; }
 104     virtual const TAnonMember* getAsAnonMember() const { return 0; }
 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 == 0);
 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) && !defined(GLSLANG_ANGLE)
 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) && !defined(GLSLANG_ANGLE)
 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     void copyParam(const TParameter& param)
 228     {
 229         if (param.name)
 230             name = NewPoolTString(param.name->c_str());
 231         else
 232             name = 0;
 233         type = param.type->clone();
 234         defaultValue = param.defaultValue;
 235     }
 236     TBuiltInVariable getDeclaredBuiltIn() const { return type->getQualifier().declaredBuiltIn; }
 237 };
 238
 239 //
 240 // The function sub-class of a symbol.
 241 //
 242 class TFunction : public TSymbol {
 243 public:
 244     explicit TFunction(TOperator o) :
 245         TSymbol(0),
 246         op(o),
 247         defined(false), prototyped(false), implicitThis(false), illegalImplicitThis(false), defaultParamCount(0) { }
 248     TFunction(const TString *name, const TType& retType, TOperator tOp = EOpNull) :
 249         TSymbol(name),
 250         mangledName(*name + '('),
 251         op(tOp),
 252         defined(false), prototyped(false), implicitThis(false), illegalImplicitThis(false), defaultParamCount(0)
 253     {
 254         returnType.shallowCopy(retType);
 255         declaredBuiltIn = retType.getQualifier().builtIn;
 256     }
 257     virtual TFunction* clone() const override;
 258     virtual ~TFunction();
 259
 260     virtual TFunction* getAsFunction() override { return this; }
 261     virtual const TFunction* getAsFunction() const override { return this; }
 262
 263     // Install 'p' as the (non-'this') last parameter.
 264     // Non-'this' parameters are reflected in both the list of parameters and the
 265     // mangled name.
 266     virtual void addParameter(TParameter& p)
 267     {
 268         assert(writable);
 269         parameters.push_back(p);
 270         p.type->appendMangledName(mangledName);
 271
 272         if (p.defaultValue != nullptr)
 273             defaultParamCount++;
 274     }
 275
 276     // Install 'this' as the first parameter.
 277     // 'this' is reflected in the list of parameters, but not the mangled name.
 278     virtual void addThisParameter(TType& type, const char* name)
 279     {
 280         TParameter p = { NewPoolTString(name), new TType, nullptr };
 281         p.type->shallowCopy(type);
 282         parameters.insert(parameters.begin(), p);
 283     }
 284
 285     virtual void addPrefix(const char* prefix) override
 286     {
 287         TSymbol::addPrefix(prefix);
 288         mangledName.insert(0, prefix);
 289     }
 290
 291     virtual void removePrefix(const TString& prefix)
 292     {
 293         assert(mangledName.compare(0, prefix.size(), prefix) == 0);
 294         mangledName.erase(0, prefix.size());
 295     }
 296
 297     virtual const TString& getMangledName() const override { return mangledName; }
 298     virtual const TType& getType() const override { return returnType; }
 299     virtual TBuiltInVariable getDeclaredBuiltInType() const { return declaredBuiltIn; }
 300     virtual TType& getWritableType() override { return returnType; }
 301     virtual void relateToOperator(TOperator o) { assert(writable); op = o; }
 302     virtual TOperator getBuiltInOp() const { return op; }
 303     virtual void setDefined() { assert(writable); defined = true; }
 304     virtual bool isDefined() const { return defined; }
 305     virtual void setPrototyped() { assert(writable); prototyped = true; }
 306     virtual bool isPrototyped() const { return prototyped; }
 307     virtual void setImplicitThis() { assert(writable); implicitThis = true; }
 308     virtual bool hasImplicitThis() const { return implicitThis; }
 309     virtual void setIllegalImplicitThis() { assert(writable); illegalImplicitThis = true; }
 310     virtual bool hasIllegalImplicitThis() const { return illegalImplicitThis; }
 311
 312     // Return total number of parameters
 313     virtual int getParamCount() const { return static_cast<int>(parameters.size()); }
 314     // Return number of parameters with default values.
 315     virtual int getDefaultParamCount() const { return defaultParamCount; }
 316     // Return number of fixed parameters (without default values)
 317     virtual int getFixedParamCount() const { return getParamCount() - getDefaultParamCount(); }
 318
 319     virtual TParameter& operator[](int i) { assert(writable); return parameters[i]; }
 320     virtual const TParameter& operator[](int i) const { return parameters[i]; }
 321
 322 #ifndef GLSLANG_WEB
 323     virtual void setSpirvInstruction(const TSpirvInstruction& inst)
 324     {
 325         relateToOperator(EOpSpirvInst);
 326         spirvInst = inst;
 327     }
 328     virtual const TSpirvInstruction& getSpirvInstruction() const { return spirvInst; }
 329 #endif
 330
 331 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 332     virtual void dump(TInfoSink& infoSink, bool complete = false) const override;
 333 #endif
 334
 335 protected:
 336     explicit TFunction(const TFunction&);
 337     TFunction& operator=(const TFunction&);
 338
 339     typedef TVector<TParameter> TParamList;
 340     TParamList parameters;
 341     TType returnType;
 342     TBuiltInVariable declaredBuiltIn;
 343
 344     TString mangledName;
 345     TOperator op;
 346     bool defined;
 347     bool prototyped;
 348     bool implicitThis;         // True if this function is allowed to see all members of 'this'
 349     bool illegalImplicitThis;  // True if this function is not supposed to have access to dynamic members of 'this',
 350                                // even if it finds member variables in the symbol table.
 351                                // This is important for a static member function that has member variables in scope,
 352                                // but is not allowed to use them, or see hidden symbols instead.
 353     int  defaultParamCount;
 354
 355 #ifndef GLSLANG_WEB
 356     TSpirvInstruction spirvInst; // SPIR-V instruction qualifiers
 357 #endif
 358 };
 359
 360 //
 361 // Members of anonymous blocks are a kind of TSymbol.  They are not hidden in
 362 // the symbol table behind a container; rather they are visible and point to
 363 // their anonymous container.  (The anonymous container is found through the
 364 // member, not the other way around.)
 365 //
 366 class TAnonMember : public TSymbol {
 367 public:
 368     TAnonMember(const TString* n, unsigned int m, TVariable& a, int an) : TSymbol(n), anonContainer(a), memberNumber(m), anonId(an) { }
 369     virtual TAnonMember* clone() const override;
 370     virtual ~TAnonMember() { }
 371
 372     virtual const TAnonMember* getAsAnonMember() const override { return this; }
 373     virtual const TVariable& getAnonContainer() const { return anonContainer; }
 374     virtual unsigned int getMemberNumber() const { return memberNumber; }
 375
 376     virtual const TType& getType() const override
 377     {
 378         const TTypeList& types = *anonContainer.getType().getStruct();
 379         return *types[memberNumber].type;
 380     }
 381
 382     virtual TType& getWritableType() override
 383     {
 384         assert(writable);
 385         const TTypeList& types = *anonContainer.getType().getStruct();
 386         return *types[memberNumber].type;
 387     }
 388
 389     virtual void setExtensions(int numExts, const char* const exts[]) override
 390     {
 391         anonContainer.setMemberExtensions(memberNumber, numExts, exts);
 392     }
 393     virtual int getNumExtensions() const override { return anonContainer.getNumMemberExtensions(memberNumber); }
 394     virtual const char** getExtensions() const override { return anonContainer.getMemberExtensions(memberNumber); }
 395
 396     virtual int getAnonId() const { return anonId; }
 397 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 398     virtual void dump(TInfoSink& infoSink, bool complete = false) const override;
 399 #endif
 400
 401 protected:
 402     explicit TAnonMember(const TAnonMember&);
 403     TAnonMember& operator=(const TAnonMember&);
 404
 405     TVariable& anonContainer;
 406     unsigned int memberNumber;
 407     int anonId;
 408 };
 409
 410 class TSymbolTableLevel {
 411 public:
 412     POOL_ALLOCATOR_NEW_DELETE(GetThreadPoolAllocator())
 413     TSymbolTableLevel() : defaultPrecision(0), anonId(0), thisLevel(false) { }
 414     ~TSymbolTableLevel();
 415
 416     bool insert(const TString& name, TSymbol* symbol) {
 417         return level.insert(tLevelPair(name, symbol)).second;
 418     }
 419
 420     bool insert(TSymbol& symbol, bool separateNameSpaces, const TString& forcedKeyName = TString())
 421     {
 422         //
 423         // returning true means symbol was added to the table with no semantic errors
 424         //
 425         const TString& name = symbol.getName();
 426         if (forcedKeyName.length()) {
 427             return level.insert(tLevelPair(forcedKeyName, &symbol)).second;
 428         }
 429         else if (name == "") {
 430             symbol.getAsVariable()->setAnonId(anonId++);
 431             // An empty name means an anonymous container, exposing its members to the external scope.
 432             // Give it a name and insert its members in the symbol table, pointing to the container.
 433             char buf[20];
 434             snprintf(buf, 20, "%s%d", AnonymousPrefix, symbol.getAsVariable()->getAnonId());
 435             symbol.changeName(NewPoolTString(buf));
 436
 437             return insertAnonymousMembers(symbol, 0);
 438         } else {
 439             // Check for redefinition errors:
 440             // - STL itself will tell us if there is a direct name collision, with name mangling, at this level
 441             // - additionally, check for function-redefining-variable name collisions
 442             const TString& insertName = symbol.getMangledName();
 443             if (symbol.getAsFunction()) {
 444                 // make sure there isn't a variable of this name
 445                 if (! separateNameSpaces && level.find(name) != level.end())
 446                     return false;
 447
 448                 // insert, and whatever happens is okay
 449                 level.insert(tLevelPair(insertName, &symbol));
 450
 451                 return true;
 452             } else
 453                 return level.insert(tLevelPair(insertName, &symbol)).second;
 454         }
 455     }
 456
 457     // Add more members to an already inserted aggregate object
 458     bool amend(TSymbol& symbol, int firstNewMember)
 459     {
 460         // See insert() for comments on basic explanation of insert.
 461         // This operates similarly, but more simply.
 462         // Only supporting amend of anonymous blocks so far.
 463         if (IsAnonymous(symbol.getName()))
 464             return insertAnonymousMembers(symbol, firstNewMember);
 465         else
 466             return false;
 467     }
 468
 469     bool insertAnonymousMembers(TSymbol& symbol, int firstMember)
 470     {
 471         const TTypeList& types = *symbol.getAsVariable()->getType().getStruct();
 472         for (unsigned int m = firstMember; m < types.size(); ++m) {
 473             TAnonMember* member = new TAnonMember(&types[m].type->getFieldName(), m, *symbol.getAsVariable(), symbol.getAsVariable()->getAnonId());
 474             if (! level.insert(tLevelPair(member->getMangledName(), member)).second)
 475                 return false;
 476         }
 477
 478         return true;
 479     }
 480
 481     void retargetSymbol(const TString& from, const TString& to) {
 482         tLevel::const_iterator fromIt = level.find(from);
 483         tLevel::const_iterator toIt = level.find(to);
 484         if (fromIt == level.end() || toIt == level.end())
 485             return;
 486         delete fromIt->second;
 487         level[from] = toIt->second;
 488         retargetedSymbols.push_back({from, to});
 489     }
 490
 491     TSymbol* find(const TString& name) const
 492     {
 493         tLevel::const_iterator it = level.find(name);
 494         if (it == level.end())
 495             return 0;
 496         else
 497             return (*it).second;
 498     }
 499
 500     void findFunctionNameList(const TString& name, TVector<const TFunction*>& list)
 501     {
 502         size_t parenAt = name.find_first_of('(');
 503         TString base(name, 0, parenAt + 1);
 504
 505         tLevel::const_iterator begin = level.lower_bound(base);
 506         base[parenAt] = ')';  // assume ')' is lexically after '('
 507         tLevel::const_iterator end = level.upper_bound(base);
 508         for (tLevel::const_iterator it = begin; it != end; ++it)
 509             list.push_back(it->second->getAsFunction());
 510     }
 511
 512     // See if there is already a function in the table having the given non-function-style name.
 513     bool hasFunctionName(const TString& name) const
 514     {
 515         tLevel::const_iterator candidate = level.lower_bound(name);
 516         if (candidate != level.end()) {
 517             const TString& candidateName = (*candidate).first;
 518             TString::size_type parenAt = candidateName.find_first_of('(');
 519             if (parenAt != candidateName.npos && candidateName.compare(0, parenAt, name) == 0)
 520
 521                 return true;
 522         }
 523
 524         return false;
 525     }
 526
 527     // See if there is a variable at this level having the given non-function-style name.
 528     // Return true if name is found, and set variable to true if the name was a variable.
 529     bool findFunctionVariableName(const TString& name, bool& variable) const
 530     {
 531         tLevel::const_iterator candidate = level.lower_bound(name);
 532         if (candidate != level.end()) {
 533             const TString& candidateName = (*candidate).first;
 534             TString::size_type parenAt = candidateName.find_first_of('(');
 535             if (parenAt == candidateName.npos) {
 536                 // not a mangled name
 537                 if (candidateName == name) {
 538                     // found a variable name match
 539                     variable = true;
 540                     return true;
 541                 }
 542             } else {
 543                 // a mangled name
 544                 if (candidateName.compare(0, parenAt, name) == 0) {
 545                     // found a function name match
 546                     variable = false;
 547                     return true;
 548                 }
 549             }
 550         }
 551
 552         return false;
 553     }
 554
 555     // Use this to do a lazy 'push' of precision defaults the first time
 556     // a precision statement is seen in a new scope.  Leave it at 0 for
 557     // when no push was needed.  Thus, it is not the current defaults,
 558     // it is what to restore the defaults to when popping a level.
 559     void setPreviousDefaultPrecisions(const TPrecisionQualifier *p)
 560     {
 561         // can call multiple times at one scope, will only latch on first call,
 562         // as we're tracking the previous scope's values, not the current values
 563         if (defaultPrecision != 0)
 564             return;
 565
 566         defaultPrecision = new TPrecisionQualifier[EbtNumTypes];
 567         for (int t = 0; t < EbtNumTypes; ++t)
 568             defaultPrecision[t] = p[t];
 569     }
 570
 571     void getPreviousDefaultPrecisions(TPrecisionQualifier *p)
 572     {
 573         // can be called for table level pops that didn't set the
 574         // defaults
 575         if (defaultPrecision == 0 || p == 0)
 576             return;
 577
 578         for (int t = 0; t < EbtNumTypes; ++t)
 579             p[t] = defaultPrecision[t];
 580     }
 581
 582     void relateToOperator(const char* name, TOperator op);
 583     void setFunctionExtensions(const char* name, int num, const char* const extensions[]);
 584 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 585     void dump(TInfoSink& infoSink, bool complete = false) const;
 586 #endif
 587     TSymbolTableLevel* clone() const;
 588     void readOnly();
 589
 590     void setThisLevel() { thisLevel = true; }
 591     bool isThisLevel() const { return thisLevel; }
 592
 593 protected:
 594     explicit TSymbolTableLevel(TSymbolTableLevel&);
 595     TSymbolTableLevel& operator=(TSymbolTableLevel&);
 596
 597     typedef std::map<TString, TSymbol*, std::less<TString>, pool_allocator<std::pair<const TString, TSymbol*> > > tLevel;
 598     typedef const tLevel::value_type tLevelPair;
 599     typedef std::pair<tLevel::iterator, bool> tInsertResult;
 600
 601     tLevel level;  // named mappings
 602     TPrecisionQualifier *defaultPrecision;
 603     // pair<FromName, ToName>
 604     TVector<std::pair<TString, TString>> retargetedSymbols;
 605     int anonId;
 606     bool thisLevel;  // True if this level of the symbol table is a structure scope containing member function
 607                      // that are supposed to see anonymous access to member variables.
 608 };
 609
 610 class TSymbolTable {
 611 public:
 612     TSymbolTable() : uniqueId(0), noBuiltInRedeclarations(false), separateNameSpaces(false), adoptedLevels(0)
 613     {
 614         //
 615         // This symbol table cannot be used until push() is called.
 616         //
 617     }
 618     ~TSymbolTable()
 619     {
 620         // this can be called explicitly; safest to code it so it can be called multiple times
 621
 622         // don't deallocate levels passed in from elsewhere
 623         while (table.size() > adoptedLevels)
 624             pop(0);
 625     }
 626
 627     void adoptLevels(TSymbolTable& symTable)
 628     {
 629         for (unsigned int level = 0; level < symTable.table.size(); ++level) {
 630             table.push_back(symTable.table[level]);
 631             ++adoptedLevels;
 632         }
 633         uniqueId = symTable.uniqueId;
 634         noBuiltInRedeclarations = symTable.noBuiltInRedeclarations;
 635         separateNameSpaces = symTable.separateNameSpaces;
 636     }
 637
 638     //
 639     // While level adopting is generic, the methods below enact a the following
 640     // convention for levels:
 641     //   0: common built-ins shared across all stages, all compiles, only one copy for all symbol tables
 642     //   1: per-stage built-ins, shared across all compiles, but a different copy per stage
 643     //   2: built-ins specific to a compile, like resources that are context-dependent, or redeclared built-ins
 644     //   3: user-shader globals
 645     //
 646 protected:
 647     static const uint32_t LevelFlagBitOffset = 56;
 648     static const int globalLevel = 3;
 649     static bool isSharedLevel(int level)  { return level <= 1; }            // exclude all per-compile levels
 650     static bool isBuiltInLevel(int level) { return level <= 2; }            // exclude user globals
 651     static bool isGlobalLevel(int level)  { return level <= globalLevel; }  // include user globals
 652 public:
 653     bool isEmpty() { return table.size() == 0; }
 654     bool atBuiltInLevel() { return isBuiltInLevel(currentLevel()); }
 655     bool atGlobalLevel()  { return isGlobalLevel(currentLevel()); }
 656     static bool isBuiltInSymbol(long long uniqueId) {
 657         int level = static_cast<int>(uniqueId >> LevelFlagBitOffset);
 658         return isBuiltInLevel(level);
 659     }
 660     static constexpr uint64_t uniqueIdMask = (1LL << LevelFlagBitOffset) - 1;
 661     static const uint32_t MaxLevelInUniqueID = 127;
 662     void setNoBuiltInRedeclarations() { noBuiltInRedeclarations = true; }
 663     void setSeparateNameSpaces() { separateNameSpaces = true; }
 664
 665     void push()
 666     {
 667         table.push_back(new TSymbolTableLevel);
 668         updateUniqueIdLevelFlag();
 669     }
 670
 671     // Make a new symbol-table level to represent the scope introduced by a structure
 672     // containing member functions, such that the member functions can find anonymous
 673     // references to member variables.
 674     //
 675     // 'thisSymbol' should have a name of "" to trigger anonymous structure-member
 676     // symbol finds.
 677     void pushThis(TSymbol& thisSymbol)
 678     {
 679         assert(thisSymbol.getName().size() == 0);
 680         table.push_back(new TSymbolTableLevel);
 681         updateUniqueIdLevelFlag();
 682         table.back()->setThisLevel();
 683         insert(thisSymbol);
 684     }
 685
 686     void pop(TPrecisionQualifier *p)
 687     {
 688         table[currentLevel()]->getPreviousDefaultPrecisions(p);
 689         delete table.back();
 690         table.pop_back();
 691         updateUniqueIdLevelFlag();
 692     }
 693
 694     //
 695     // Insert a visible symbol into the symbol table so it can
 696     // be found later by name.
 697     //
 698     // Returns false if the was a name collision.
 699     //
 700     bool insert(TSymbol& symbol)
 701     {
 702         symbol.setUniqueId(++uniqueId);
 703
 704         // make sure there isn't a function of this variable name
 705         if (! separateNameSpaces && ! symbol.getAsFunction() && table[currentLevel()]->hasFunctionName(symbol.getName()))
 706             return false;
 707
 708         // check for not overloading or redefining a built-in function
 709         if (noBuiltInRedeclarations) {
 710             if (atGlobalLevel() && currentLevel() > 0) {
 711                 if (table[0]->hasFunctionName(symbol.getName()))
 712                     return false;
 713                 if (currentLevel() > 1 && table[1]->hasFunctionName(symbol.getName()))
 714                     return false;
 715             }
 716         }
 717
 718         return table[currentLevel()]->insert(symbol, separateNameSpaces);
 719     }
 720
 721     // Add more members to an already inserted aggregate object
 722     bool amend(TSymbol& symbol, int firstNewMember)
 723     {
 724         // See insert() for comments on basic explanation of insert.
 725         // This operates similarly, but more simply.
 726         return table[currentLevel()]->amend(symbol, firstNewMember);
 727     }
 728
 729     // Update the level info in symbol's unique ID to current level
 730     void amendSymbolIdLevel(TSymbol& symbol)
 731     {
 732         // clamp level to avoid overflow
 733         uint64_t level = (uint32_t)currentLevel() > MaxLevelInUniqueID ? MaxLevelInUniqueID : currentLevel();
 734         uint64_t symbolId = symbol.getUniqueId();
 735         symbolId &= uniqueIdMask;
 736         symbolId |= (level << LevelFlagBitOffset);
 737         symbol.setUniqueId(symbolId);
 738     }
 739     //
 740     // To allocate an internal temporary, which will need to be uniquely
 741     // identified by the consumer of the AST, but never need to
 742     // found by doing a symbol table search by name, hence allowed an
 743     // arbitrary name in the symbol with no worry of collision.
 744     //
 745     void makeInternalVariable(TSymbol& symbol)
 746     {
 747         symbol.setUniqueId(++uniqueId);
 748     }
 749
 750     //
 751     // Copy a variable or anonymous member's structure from a shared level so that
 752     // it can be added (soon after return) to the symbol table where it can be
 753     // modified without impacting other users of the shared table.
 754     //
 755     TSymbol* copyUpDeferredInsert(TSymbol* shared)
 756     {
 757         if (shared->getAsVariable()) {
 758             TSymbol* copy = shared->clone();
 759             copy->setUniqueId(shared->getUniqueId());
 760             return copy;
 761         } else {
 762             const TAnonMember* anon = shared->getAsAnonMember();
 763             assert(anon);
 764             TVariable* container = anon->getAnonContainer().clone();
 765             container->changeName(NewPoolTString(""));
 766             container->setUniqueId(anon->getAnonContainer().getUniqueId());
 767             return container;
 768         }
 769     }
 770
 771     TSymbol* copyUp(TSymbol* shared)
 772     {
 773         TSymbol* copy = copyUpDeferredInsert(shared);
 774         table[globalLevel]->insert(*copy, separateNameSpaces);
 775         if (shared->getAsVariable())
 776             return copy;
 777         else {
 778             // return the copy of the anonymous member
 779             return table[globalLevel]->find(shared->getName());
 780         }
 781     }
 782
 783     // Normal find of a symbol, that can optionally say whether the symbol was found
 784     // at a built-in level or the current top-scope level.
 785     TSymbol* find(const TString& name, bool* builtIn = 0, bool* currentScope = 0, int* thisDepthP = 0)
 786     {
 787         int level = currentLevel();
 788         TSymbol* symbol;
 789         int thisDepth = 0;
 790         do {
 791             if (table[level]->isThisLevel())
 792                 ++thisDepth;
 793             symbol = table[level]->find(name);
 794             --level;
 795         } while (symbol == nullptr && level >= 0);
 796         level++;
 797         if (builtIn)
 798             *builtIn = isBuiltInLevel(level);
 799         if (currentScope)
 800             *currentScope = isGlobalLevel(currentLevel()) || level == currentLevel();  // consider shared levels as "current scope" WRT user globals
 801         if (thisDepthP != nullptr) {
 802             if (! table[level]->isThisLevel())
 803                 thisDepth = 0;
 804             *thisDepthP = thisDepth;
 805         }
 806
 807         return symbol;
 808     }
 809
 810     void retargetSymbol(const TString& from, const TString& to) {
 811         int level = currentLevel();
 812         table[level]->retargetSymbol(from, to);
 813     }
 814
 815
 816     // Find of a symbol that returns how many layers deep of nested
 817     // structures-with-member-functions ('this' scopes) deep the symbol was
 818     // found in.
 819     TSymbol* find(const TString& name, int& thisDepth)
 820     {
 821         int level = currentLevel();
 822         TSymbol* symbol;
 823         thisDepth = 0;
 824         do {
 825             if (table[level]->isThisLevel())
 826                 ++thisDepth;
 827             symbol = table[level]->find(name);
 828             --level;
 829         } while (symbol == 0 && level >= 0);
 830
 831         if (! table[level + 1]->isThisLevel())
 832             thisDepth = 0;
 833
 834         return symbol;
 835     }
 836
 837     bool isFunctionNameVariable(const TString& name) const
 838     {
 839         if (separateNameSpaces)
 840             return false;
 841
 842         int level = currentLevel();
 843         do {
 844             bool variable;
 845             bool found = table[level]->findFunctionVariableName(name, variable);
 846             if (found)
 847                 return variable;
 848             --level;
 849         } while (level >= 0);
 850
 851         return false;
 852     }
 853
 854     void findFunctionNameList(const TString& name, TVector<const TFunction*>& list, bool& builtIn)
 855     {
 856         // For user levels, return the set found in the first scope with a match
 857         builtIn = false;
 858         int level = currentLevel();
 859         do {
 860             table[level]->findFunctionNameList(name, list);
 861             --level;
 862         } while (list.empty() && level >= globalLevel);
 863
 864         if (! list.empty())
 865             return;
 866
 867         // Gather across all built-in levels; they don't hide each other
 868         builtIn = true;
 869         do {
 870             table[level]->findFunctionNameList(name, list);
 871             --level;
 872         } while (level >= 0);
 873     }
 874
 875     void relateToOperator(const char* name, TOperator op)
 876     {
 877         for (unsigned int level = 0; level < table.size(); ++level)
 878             table[level]->relateToOperator(name, op);
 879     }
 880
 881     void setFunctionExtensions(const char* name, int num, const char* const extensions[])
 882     {
 883         for (unsigned int level = 0; level < table.size(); ++level)
 884             table[level]->setFunctionExtensions(name, num, extensions);
 885     }
 886
 887     void setVariableExtensions(const char* name, int numExts, const char* const extensions[])
 888     {
 889         TSymbol* symbol = find(TString(name));
 890         if (symbol == nullptr)
 891             return;
 892
 893         symbol->setExtensions(numExts, extensions);
 894     }
 895
 896     void setVariableExtensions(const char* blockName, const char* name, int numExts, const char* const extensions[])
 897     {
 898         TSymbol* symbol = find(TString(blockName));
 899         if (symbol == nullptr)
 900             return;
 901         TVariable* variable = symbol->getAsVariable();
 902         assert(variable != nullptr);
 903
 904         const TTypeList& structure = *variable->getAsVariable()->getType().getStruct();
 905         for (int member = 0; member < (int)structure.size(); ++member) {
 906             if (structure[member].type->getFieldName().compare(name) == 0) {
 907                 variable->setMemberExtensions(member, numExts, extensions);
 908                 return;
 909             }
 910         }
 911     }
 912
 913     long long getMaxSymbolId() { return uniqueId; }
 914 #if !defined(GLSLANG_WEB) && !defined(GLSLANG_ANGLE)
 915     void dump(TInfoSink& infoSink, bool complete = false) const;
 916 #endif
 917     void copyTable(const TSymbolTable& copyOf);
 918
 919     void setPreviousDefaultPrecisions(TPrecisionQualifier *p) { table[currentLevel()]->setPreviousDefaultPrecisions(p); }
 920
 921     void readOnly()
 922     {
 923         for (unsigned int level = 0; level < table.size(); ++level)
 924             table[level]->readOnly();
 925     }
 926
 927     // Add current level in the high-bits of unique id
 928     void updateUniqueIdLevelFlag() {
 929         // clamp level to avoid overflow
 930         uint64_t level = (uint32_t)currentLevel() > MaxLevelInUniqueID ? MaxLevelInUniqueID : currentLevel();
 931         uniqueId &= uniqueIdMask;
 932         uniqueId |= (level << LevelFlagBitOffset);
 933     }
 934
 935     void overwriteUniqueId(long long id)
 936     {
 937         uniqueId = id;
 938         updateUniqueIdLevelFlag();
 939     }
 940
 941 protected:
 942     TSymbolTable(TSymbolTable&);
 943     TSymbolTable& operator=(TSymbolTableLevel&);
 944
 945     int currentLevel() const { return static_cast<int>(table.size()) - 1; }
 946     std::vector<TSymbolTableLevel*> table;
 947     long long uniqueId;     // for unique identification in code generation
 948     bool noBuiltInRedeclarations;
 949     bool separateNameSpaces;
 950     unsigned int adoptedLevels;
 951 };
 952
 953 } // end namespace glslang
 954
 955 #endif // _SYMBOL_TABLE_INCLUDED_