michael@0: //
michael@0: // Copyright (c) 2002-2013 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #ifndef _SYMBOL_TABLE_INCLUDED_
michael@0: #define _SYMBOL_TABLE_INCLUDED_
michael@0: 
michael@0: //
michael@0: // Symbol table for parsing.  Has these design characteristics:
michael@0: //
michael@0: // * Same symbol table can be used to compile many shaders, to preserve
michael@0: //   effort of creating and loading with the large numbers of built-in
michael@0: //   symbols.
michael@0: //
michael@0: // * Name mangling will be used to give each function a unique name
michael@0: //   so that symbol table lookups are never ambiguous.  This allows
michael@0: //   a simpler symbol table structure.
michael@0: //
michael@0: // * Pushing and popping of scope, so symbol table will really be a stack 
michael@0: //   of symbol tables.  Searched from the top, with new inserts going into
michael@0: //   the top.
michael@0: //
michael@0: // * Constants:  Compile time constant symbols will keep their values
michael@0: //   in the symbol table.  The parser can substitute constants at parse
michael@0: //   time, including doing constant folding and constant propagation.
michael@0: //
michael@0: // * No temporaries:  Temporaries made from operations (+, --, .xy, etc.)
michael@0: //   are tracked in the intermediate representation, not the symbol table.
michael@0: //
michael@0: 
michael@0: #include <assert.h>
michael@0: 
michael@0: #include "common/angleutils.h"
michael@0: #include "compiler/InfoSink.h"
michael@0: #include "compiler/intermediate.h"
michael@0: 
michael@0: //
michael@0: // Symbol base class.  (Can build functions or variables out of these...)
michael@0: //
michael@0: class TSymbol {    
michael@0: public:
michael@0:     POOL_ALLOCATOR_NEW_DELETE();
michael@0:     TSymbol(const TString *n) :  name(n) { }
michael@0:     virtual ~TSymbol() { /* don't delete name, it's from the pool */ }
michael@0: 
michael@0:     const TString& getName() const { return *name; }
michael@0:     virtual const TString& getMangledName() const { return getName(); }
michael@0:     virtual bool isFunction() const { return false; }
michael@0:     virtual bool isVariable() const { return false; }
michael@0:     void setUniqueId(int id) { uniqueId = id; }
michael@0:     int getUniqueId() const { return uniqueId; }
michael@0:     virtual void dump(TInfoSink &infoSink) const = 0;
michael@0:     void relateToExtension(const TString& ext) { extension = ext; }
michael@0:     const TString& getExtension() const { return extension; }
michael@0: 
michael@0: private:
michael@0:     DISALLOW_COPY_AND_ASSIGN(TSymbol);
michael@0: 
michael@0:     const TString *name;
michael@0:     unsigned int uniqueId;      // For real comparing during code generation
michael@0:     TString extension;
michael@0: };
michael@0: 
michael@0: //
michael@0: // Variable class, meaning a symbol that's not a function.
michael@0: // 
michael@0: // There could be a separate class heirarchy for Constant variables;
michael@0: // Only one of int, bool, or float, (or none) is correct for
michael@0: // any particular use, but it's easy to do this way, and doesn't
michael@0: // seem worth having separate classes, and "getConst" can't simply return
michael@0: // different values for different types polymorphically, so this is 
michael@0: // just simple and pragmatic.
michael@0: //
michael@0: class TVariable : public TSymbol {
michael@0: public:
michael@0:     TVariable(const TString *name, const TType& t, bool uT = false ) : TSymbol(name), type(t), userType(uT), unionArray(0) { }
michael@0:     virtual ~TVariable() { }
michael@0:     virtual bool isVariable() const { return true; }    
michael@0:     TType& getType() { return type; }    
michael@0:     const TType& getType() const { return type; }
michael@0:     bool isUserType() const { return userType; }
michael@0:     void setQualifier(TQualifier qualifier) { type.setQualifier(qualifier); }
michael@0: 
michael@0:     virtual void dump(TInfoSink &infoSink) const;
michael@0: 
michael@0:     ConstantUnion* getConstPointer()
michael@0:     { 
michael@0:         if (!unionArray)
michael@0:             unionArray = new ConstantUnion[type.getObjectSize()];
michael@0: 
michael@0:         return unionArray;
michael@0:     }
michael@0: 
michael@0:     ConstantUnion* getConstPointer() const { return unionArray; }
michael@0: 
michael@0:     void shareConstPointer( ConstantUnion *constArray)
michael@0:     {
michael@0:         if (unionArray == constArray)
michael@0:             return;
michael@0: 
michael@0:         delete[] unionArray;
michael@0:         unionArray = constArray;  
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     DISALLOW_COPY_AND_ASSIGN(TVariable);
michael@0: 
michael@0:     TType type;
michael@0:     bool userType;
michael@0:     // we are assuming that Pool Allocator will free the memory allocated to unionArray
michael@0:     // when this object is destroyed
michael@0:     ConstantUnion *unionArray;
michael@0: };
michael@0: 
michael@0: //
michael@0: // The function sub-class of symbols and the parser will need to
michael@0: // share this definition of a function parameter.
michael@0: //
michael@0: struct TParameter {
michael@0:     TString *name;
michael@0:     TType* type;
michael@0: };
michael@0: 
michael@0: //
michael@0: // The function sub-class of a symbol.  
michael@0: //
michael@0: class TFunction : public TSymbol {
michael@0: public:
michael@0:     TFunction(TOperator o) :
michael@0:         TSymbol(0),
michael@0:         returnType(TType(EbtVoid, EbpUndefined)),
michael@0:         op(o),
michael@0:         defined(false) { }
michael@0:     TFunction(const TString *name, TType& retType, TOperator tOp = EOpNull) : 
michael@0:         TSymbol(name), 
michael@0:         returnType(retType),
michael@0:         mangledName(TFunction::mangleName(*name)),
michael@0:         op(tOp),
michael@0:         defined(false) { }
michael@0:     virtual ~TFunction();
michael@0:     virtual bool isFunction() const { return true; }    
michael@0: 
michael@0:     static TString mangleName(const TString& name) { return name + '('; }
michael@0:     static TString unmangleName(const TString& mangledName)
michael@0:     {
michael@0:         return TString(mangledName.c_str(), mangledName.find_first_of('('));
michael@0:     }
michael@0: 
michael@0:     void addParameter(TParameter& p) 
michael@0:     { 
michael@0:         parameters.push_back(p);
michael@0:         mangledName = mangledName + p.type->getMangledName();
michael@0:     }
michael@0: 
michael@0:     const TString& getMangledName() const { return mangledName; }
michael@0:     const TType& getReturnType() const { return returnType; }
michael@0: 
michael@0:     void relateToOperator(TOperator o) { op = o; }
michael@0:     TOperator getBuiltInOp() const { return op; }
michael@0: 
michael@0:     void setDefined() { defined = true; }
michael@0:     bool isDefined() { return defined; }
michael@0: 
michael@0:     size_t getParamCount() const { return parameters.size(); }  
michael@0:     const TParameter& getParam(size_t i) const { return parameters[i]; }
michael@0: 
michael@0:     virtual void dump(TInfoSink &infoSink) const;
michael@0: 
michael@0: private:
michael@0:     DISALLOW_COPY_AND_ASSIGN(TFunction);
michael@0: 
michael@0:     typedef TVector<TParameter> TParamList;
michael@0:     TParamList parameters;
michael@0:     TType returnType;
michael@0:     TString mangledName;
michael@0:     TOperator op;
michael@0:     bool defined;
michael@0: };
michael@0: 
michael@0: 
michael@0: class TSymbolTableLevel {
michael@0: public:
michael@0:     typedef TMap<TString, TSymbol*> tLevel;
michael@0:     typedef tLevel::const_iterator const_iterator;
michael@0:     typedef const tLevel::value_type tLevelPair;
michael@0:     typedef std::pair<tLevel::iterator, bool> tInsertResult;
michael@0: 
michael@0:     POOL_ALLOCATOR_NEW_DELETE();
michael@0:     TSymbolTableLevel() { }
michael@0:     ~TSymbolTableLevel();
michael@0: 
michael@0:     bool insert(const TString &name, TSymbol &symbol)
michael@0:     {
michael@0:         //
michael@0:         // returning true means symbol was added to the table
michael@0:         //
michael@0:         tInsertResult result;
michael@0:         result = level.insert(tLevelPair(name, &symbol));
michael@0: 
michael@0:         return result.second;
michael@0:     }
michael@0: 
michael@0:     bool insert(TSymbol &symbol)
michael@0:     {
michael@0:         return insert(symbol.getMangledName(), symbol);
michael@0:     }
michael@0: 
michael@0:     TSymbol* find(const TString& name) const
michael@0:     {
michael@0:         tLevel::const_iterator it = level.find(name);
michael@0:         if (it == level.end())
michael@0:             return 0;
michael@0:         else
michael@0:             return (*it).second;
michael@0:     }
michael@0: 
michael@0:     const_iterator begin() const
michael@0:     {
michael@0:         return level.begin();
michael@0:     }
michael@0: 
michael@0:     const_iterator end() const
michael@0:     {
michael@0:         return level.end();
michael@0:     }
michael@0: 
michael@0:     void relateToOperator(const char* name, TOperator op);
michael@0:     void relateToExtension(const char* name, const TString& ext);
michael@0:     void dump(TInfoSink &infoSink) const;
michael@0: 
michael@0: protected:
michael@0:     tLevel level;
michael@0: };
michael@0: 
michael@0: class TSymbolTable {
michael@0: public:
michael@0:     TSymbolTable() : uniqueId(0)
michael@0:     {
michael@0:         //
michael@0:         // The symbol table cannot be used until push() is called, but
michael@0:         // the lack of an initial call to push() can be used to detect
michael@0:         // that the symbol table has not been preloaded with built-ins.
michael@0:         //
michael@0:     }
michael@0: 
michael@0:     ~TSymbolTable()
michael@0:     {
michael@0:         // level 0 is always built In symbols, so we never pop that out
michael@0:         while (table.size() > 1)
michael@0:             pop();
michael@0:     }
michael@0: 
michael@0:     //
michael@0:     // When the symbol table is initialized with the built-ins, there should
michael@0:     // 'push' calls, so that built-ins are at level 0 and the shader
michael@0:     // globals are at level 1.
michael@0:     //
michael@0:     bool isEmpty() { return table.size() == 0; }
michael@0:     bool atBuiltInLevel() { return table.size() == 1; }
michael@0:     bool atGlobalLevel() { return table.size() <= 2; }
michael@0:     void push()
michael@0:     {
michael@0:         table.push_back(new TSymbolTableLevel);
michael@0:         precisionStack.push_back( PrecisionStackLevel() );
michael@0:     }
michael@0: 
michael@0:     void pop()
michael@0:     { 
michael@0:         delete table[currentLevel()]; 
michael@0:         table.pop_back(); 
michael@0:         precisionStack.pop_back();
michael@0:     }
michael@0: 
michael@0:     bool insert(TSymbol& symbol)
michael@0:     {
michael@0:         symbol.setUniqueId(++uniqueId);
michael@0:         return table[currentLevel()]->insert(symbol);
michael@0:     }
michael@0: 
michael@0:     bool insertConstInt(const char *name, int value)
michael@0:     {
michael@0:         TVariable *constant = new TVariable(NewPoolTString(name), TType(EbtInt, EbpUndefined, EvqConst, 1));
michael@0:         constant->getConstPointer()->setIConst(value);
michael@0:         return insert(*constant);
michael@0:     }
michael@0: 
michael@0:     bool insertBuiltIn(TType *rvalue, const char *name, TType *ptype1, TType *ptype2 = 0, TType *ptype3 = 0)
michael@0:     {
michael@0:         TFunction *function = new TFunction(NewPoolTString(name), *rvalue);
michael@0: 
michael@0:         TParameter param1 = {NULL, ptype1};
michael@0:         function->addParameter(param1);
michael@0: 
michael@0:         if(ptype2)
michael@0:         {
michael@0:             TParameter param2 = {NULL, ptype2};
michael@0:             function->addParameter(param2);
michael@0:         }
michael@0: 
michael@0:         if(ptype3)
michael@0:         {
michael@0:             TParameter param3 = {NULL, ptype3};
michael@0:             function->addParameter(param3);
michael@0:         }
michael@0: 
michael@0:         return insert(*function);
michael@0:     }
michael@0: 
michael@0:     TSymbol* find(const TString& name, bool* builtIn = 0, bool *sameScope = 0) 
michael@0:     {
michael@0:         int level = currentLevel();
michael@0:         TSymbol* symbol;
michael@0:         do {
michael@0:             symbol = table[level]->find(name);
michael@0:             --level;
michael@0:         } while (symbol == 0 && level >= 0);
michael@0:         level++;
michael@0:         if (builtIn)
michael@0:             *builtIn = level == 0;
michael@0:         if (sameScope)
michael@0:             *sameScope = level == currentLevel();
michael@0:         return symbol;
michael@0:     }
michael@0: 
michael@0:     TSymbol *findBuiltIn(const TString &name)
michael@0:     {
michael@0:         return table[0]->find(name);
michael@0:     }
michael@0: 
michael@0:     TSymbolTableLevel* getGlobalLevel() {
michael@0:         assert(table.size() >= 2);
michael@0:         return table[1];
michael@0:     }
michael@0: 
michael@0:     TSymbolTableLevel* getOuterLevel() {
michael@0:         assert(table.size() >= 2);
michael@0:         return table[currentLevel() - 1];
michael@0:     }
michael@0: 
michael@0:     void relateToOperator(const char* name, TOperator op) {
michael@0:         table[0]->relateToOperator(name, op);
michael@0:     }
michael@0:     void relateToExtension(const char* name, const TString& ext) {
michael@0:         table[0]->relateToExtension(name, ext);
michael@0:     }
michael@0:     int getMaxSymbolId() { return uniqueId; }
michael@0:     void dump(TInfoSink &infoSink) const;
michael@0: 
michael@0:     bool setDefaultPrecision( const TPublicType& type, TPrecision prec ){
michael@0:         if (IsSampler(type.type))
michael@0:             return true;  // Skip sampler types for the time being
michael@0:         if (type.type != EbtFloat && type.type != EbtInt)
michael@0:             return false; // Only set default precision for int/float
michael@0:         if (type.size != 1 || type.matrix || type.array)
michael@0:             return false; // Not allowed to set for aggregate types
michael@0:         int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1;
michael@0:         precisionStack[indexOfLastElement][type.type] = prec; // Uses map operator [], overwrites the current value
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Searches down the precisionStack for a precision qualifier for the specified TBasicType
michael@0:     TPrecision getDefaultPrecision( TBasicType type){
michael@0:         if( type != EbtFloat && type != EbtInt ) return EbpUndefined;
michael@0:         int level = static_cast<int>(precisionStack.size()) - 1;
michael@0:         assert( level >= 0); // Just to be safe. Should not happen.
michael@0:         PrecisionStackLevel::iterator it;
michael@0:         TPrecision prec = EbpUndefined; // If we dont find anything we return this. Should we error check this?
michael@0:         while( level >= 0 ){
michael@0:             it = precisionStack[level].find( type );
michael@0:             if( it != precisionStack[level].end() ){
michael@0:                 prec = (*it).second;
michael@0:                 break;
michael@0:             }
michael@0:             level--;
michael@0:         }
michael@0:         return prec;
michael@0:     }
michael@0: 
michael@0: protected:    
michael@0:     int currentLevel() const { return static_cast<int>(table.size()) - 1; }
michael@0: 
michael@0:     std::vector<TSymbolTableLevel*> table;
michael@0:     typedef std::map< TBasicType, TPrecision > PrecisionStackLevel;
michael@0:     std::vector< PrecisionStackLevel > precisionStack;
michael@0:     int uniqueId;     // for unique identification in code generation
michael@0: };
michael@0: 
michael@0: #endif // _SYMBOL_TABLE_INCLUDED_