• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1  //
2  // Copyright (c) 2002-2010 The ANGLE Project Authors. All rights reserved.
3  // Use of this source code is governed by a BSD-style license that can be
4  // found in the LICENSE file.
5  //
6  
7  #ifndef _SYMBOL_TABLE_INCLUDED_
8  #define _SYMBOL_TABLE_INCLUDED_
9  
10  //
11  // Symbol table for parsing.  Has these design characteristics:
12  //
13  // * Same symbol table can be used to compile many shaders, to preserve
14  //   effort of creating and loading with the large numbers of built-in
15  //   symbols.
16  //
17  // * Name mangling will be used to give each function a unique name
18  //   so that symbol table lookups are never ambiguous.  This allows
19  //   a simpler symbol table structure.
20  //
21  // * Pushing and popping of scope, so symbol table will really be a stack
22  //   of symbol tables.  Searched from the top, with new inserts going into
23  //   the top.
24  //
25  // * Constants:  Compile time constant symbols will keep their values
26  //   in the symbol table.  The parser can substitute constants at parse
27  //   time, including doing constant folding and constant propagation.
28  //
29  // * No temporaries:  Temporaries made from operations (+, --, .xy, etc.)
30  //   are tracked in the intermediate representation, not the symbol table.
31  //
32  
33  #include <assert.h>
34  
35  #include "compiler/InfoSink.h"
36  #include "compiler/intermediate.h"
37  
38  //
39  // Symbol base class.  (Can build functions or variables out of these...)
40  //
41  class TSymbol {
42  public:
POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)43      POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
44      TSymbol(const TString *n) :  name(n) { }
~TSymbol()45      virtual ~TSymbol() { /* don't delete name, it's from the pool */ }
getName()46      const TString& getName() const { return *name; }
getMangledName()47      virtual const TString& getMangledName() const { return getName(); }
isFunction()48      virtual bool isFunction() const { return false; }
isVariable()49      virtual bool isVariable() const { return false; }
setUniqueId(int id)50      void setUniqueId(int id) { uniqueId = id; }
getUniqueId()51      int getUniqueId() const { return uniqueId; }
52      virtual void dump(TInfoSink &infoSink) const = 0;
53      TSymbol(const TSymbol&);
54      virtual TSymbol* clone(TStructureMap& remapper) = 0;
55  
56  protected:
57      const TString *name;
58      unsigned int uniqueId;      // For real comparing during code generation
59  };
60  
61  //
62  // Variable class, meaning a symbol that's not a function.
63  //
64  // There could be a separate class heirarchy for Constant variables;
65  // Only one of int, bool, or float, (or none) is correct for
66  // any particular use, but it's easy to do this way, and doesn't
67  // seem worth having separate classes, and "getConst" can't simply return
68  // different values for different types polymorphically, so this is
69  // just simple and pragmatic.
70  //
71  class TVariable : public TSymbol {
72  public:
TSymbol(name)73      TVariable(const TString *name, const TType& t, bool uT = false ) : TSymbol(name), type(t), userType(uT), unionArray(0), arrayInformationType(0) { }
~TVariable()74      virtual ~TVariable() { }
isVariable()75      virtual bool isVariable() const { return true; }
getType()76      TType& getType() { return type; }
getType()77      const TType& getType() const { return type; }
isUserType()78      bool isUserType() const { return userType; }
setQualifier(TQualifier qualifier)79      void setQualifier(TQualifier qualifier) { type.setQualifier(qualifier); }
updateArrayInformationType(TType * t)80      void updateArrayInformationType(TType *t) { arrayInformationType = t; }
getArrayInformationType()81      TType* getArrayInformationType() { return arrayInformationType; }
82  
83      virtual void dump(TInfoSink &infoSink) const;
84  
getConstPointer()85      ConstantUnion* getConstPointer()
86      {
87          if (!unionArray)
88              unionArray = new ConstantUnion[type.getObjectSize()];
89  
90          return unionArray;
91      }
92  
getConstPointer()93      ConstantUnion* getConstPointer() const { return unionArray; }
94  
shareConstPointer(ConstantUnion * constArray)95      void shareConstPointer( ConstantUnion *constArray)
96      {
97          if (unionArray == constArray)
98              return;
99  
100          delete[] unionArray;
101          unionArray = constArray;
102      }
103      TVariable(const TVariable&, TStructureMap& remapper); // copy constructor
104      virtual TVariable* clone(TStructureMap& remapper);
105  
106  protected:
107      TType type;
108      bool userType;
109      // we are assuming that Pool Allocator will free the memory allocated to unionArray
110      // when this object is destroyed
111      ConstantUnion *unionArray;
112      TType *arrayInformationType;  // this is used for updating maxArraySize in all the references to a given symbol
113  };
114  
115  //
116  // The function sub-class of symbols and the parser will need to
117  // share this definition of a function parameter.
118  //
119  struct TParameter {
120      TString *name;
121      TType* type;
copyParamTParameter122      void copyParam(const TParameter& param, TStructureMap& remapper)
123      {
124          name = NewPoolTString(param.name->c_str());
125          type = param.type->clone(remapper);
126      }
127  };
128  
129  //
130  // The function sub-class of a symbol.
131  //
132  class TFunction : public TSymbol {
133  public:
TFunction(TOperator o)134      TFunction(TOperator o) :
135          TSymbol(0),
136          returnType(TType(EbtVoid, EbpUndefined)),
137          op(o),
138          defined(false) { }
139      TFunction(const TString *name, TType& retType, TOperator tOp = EOpNull) :
TSymbol(name)140          TSymbol(name),
141          returnType(retType),
142          mangledName(TFunction::mangleName(*name)),
143          op(tOp),
144          defined(false) { }
145      virtual ~TFunction();
isFunction()146      virtual bool isFunction() const { return true; }
147  
mangleName(const TString & name)148      static TString mangleName(const TString& name) { return name + '('; }
unmangleName(const TString & mangledName)149      static TString unmangleName(const TString& mangledName)
150      {
151          return TString(mangledName.c_str(), mangledName.find_first_of('('));
152      }
153  
addParameter(TParameter & p)154      void addParameter(TParameter& p)
155      {
156          parameters.push_back(p);
157          mangledName = mangledName + p.type->getMangledName();
158      }
159  
getMangledName()160      const TString& getMangledName() const { return mangledName; }
getReturnType()161      const TType& getReturnType() const { return returnType; }
162  
relateToOperator(TOperator o)163      void relateToOperator(TOperator o) { op = o; }
getBuiltInOp()164      TOperator getBuiltInOp() const { return op; }
165  
relateToExtension(const TString & ext)166      void relateToExtension(const TString& ext) { extension = ext; }
getExtension()167      const TString& getExtension() const { return extension; }
168  
setDefined()169      void setDefined() { defined = true; }
isDefined()170      bool isDefined() { return defined; }
171  
getParamCount()172      int getParamCount() const { return static_cast<int>(parameters.size()); }
getParam(int i)173      const TParameter& getParam(int i) const { return parameters[i]; }
174  
175      virtual void dump(TInfoSink &infoSink) const;
176      TFunction(const TFunction&, TStructureMap& remapper);
177      virtual TFunction* clone(TStructureMap& remapper);
178  
179  protected:
180      typedef TVector<TParameter> TParamList;
181      TParamList parameters;
182      TType returnType;
183      TString mangledName;
184      TOperator op;
185      TString extension;
186      bool defined;
187  };
188  
189  
190  class TSymbolTableLevel {
191  public:
192      typedef TMap<TString, TSymbol*> tLevel;
193      typedef tLevel::const_iterator const_iterator;
194      typedef const tLevel::value_type tLevelPair;
195      typedef std::pair<tLevel::iterator, bool> tInsertResult;
196  
197      POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
TSymbolTableLevel()198      TSymbolTableLevel() { }
199      ~TSymbolTableLevel();
200  
insert(TSymbol & symbol)201      bool insert(TSymbol& symbol)
202      {
203          //
204          // returning true means symbol was added to the table
205          //
206          tInsertResult result;
207          result = level.insert(tLevelPair(symbol.getMangledName(), &symbol));
208  
209          return result.second;
210      }
211  
find(const TString & name)212      TSymbol* find(const TString& name) const
213      {
214          tLevel::const_iterator it = level.find(name);
215          if (it == level.end())
216              return 0;
217          else
218              return (*it).second;
219      }
220  
begin()221      const_iterator begin() const
222      {
223          return level.begin();
224      }
225  
end()226      const_iterator end() const
227      {
228          return level.end();
229      }
230  
231      void relateToOperator(const char* name, TOperator op);
232      void relateToExtension(const char* name, const TString& ext);
233      void dump(TInfoSink &infoSink) const;
234      TSymbolTableLevel* clone(TStructureMap& remapper);
235  
236  protected:
237      tLevel level;
238  };
239  
240  class TSymbolTable {
241  public:
TSymbolTable()242      TSymbolTable() : uniqueId(0)
243      {
244          //
245          // The symbol table cannot be used until push() is called, but
246          // the lack of an initial call to push() can be used to detect
247          // that the symbol table has not been preloaded with built-ins.
248          //
249      }
250  
~TSymbolTable()251      ~TSymbolTable()
252      {
253          // level 0 is always built In symbols, so we never pop that out
254          while (table.size() > 1)
255              pop();
256      }
257  
258      //
259      // When the symbol table is initialized with the built-ins, there should
260      // 'push' calls, so that built-ins are at level 0 and the shader
261      // globals are at level 1.
262      //
isEmpty()263      bool isEmpty() { return table.size() == 0; }
atBuiltInLevel()264      bool atBuiltInLevel() { return table.size() == 1; }
atGlobalLevel()265      bool atGlobalLevel() { return table.size() <= 2; }
push()266      void push()
267      {
268          table.push_back(new TSymbolTableLevel);
269          precisionStack.push_back( PrecisionStackLevel() );
270      }
271  
pop()272      void pop()
273      {
274          delete table[currentLevel()];
275          table.pop_back();
276          precisionStack.pop_back();
277      }
278  
insert(TSymbol & symbol)279      bool insert(TSymbol& symbol)
280      {
281          symbol.setUniqueId(++uniqueId);
282          return table[currentLevel()]->insert(symbol);
283      }
284  
285      TSymbol* find(const TString& name, bool* builtIn = 0, bool *sameScope = 0)
286      {
287          int level = currentLevel();
288          TSymbol* symbol;
289          do {
290              symbol = table[level]->find(name);
291              --level;
292          } while (symbol == 0 && level >= 0);
293          level++;
294          if (builtIn)
295              *builtIn = level == 0;
296          if (sameScope)
297              *sameScope = level == currentLevel();
298          return symbol;
299      }
300  
getGlobalLevel()301      TSymbolTableLevel* getGlobalLevel() {
302          assert(table.size() >= 2);
303          return table[1];
304      }
relateToOperator(const char * name,TOperator op)305      void relateToOperator(const char* name, TOperator op) {
306          table[0]->relateToOperator(name, op);
307      }
relateToExtension(const char * name,const TString & ext)308      void relateToExtension(const char* name, const TString& ext) {
309          table[0]->relateToExtension(name, ext);
310      }
getMaxSymbolId()311      int getMaxSymbolId() { return uniqueId; }
312      void dump(TInfoSink &infoSink) const;
313      void copyTable(const TSymbolTable& copyOf);
314  
setDefaultPrecision(TBasicType type,TPrecision prec)315      void setDefaultPrecision( TBasicType type, TPrecision prec ){
316          if( type != EbtFloat && type != EbtInt ) return; // Only set default precision for int/float
317          int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1;
318          precisionStack[indexOfLastElement][type] = prec; // Uses map operator [], overwrites the current value
319      }
320  
321      // Searches down the precisionStack for a precision qualifier for the specified TBasicType
getDefaultPrecision(TBasicType type)322      TPrecision getDefaultPrecision( TBasicType type){
323          if( type != EbtFloat && type != EbtInt ) return EbpUndefined;
324          int level = static_cast<int>(precisionStack.size()) - 1;
325          assert( level >= 0); // Just to be safe. Should not happen.
326          PrecisionStackLevel::iterator it;
327          TPrecision prec = EbpUndefined; // If we dont find anything we return this. Should we error check this?
328          while( level >= 0 ){
329              it = precisionStack[level].find( type );
330              if( it != precisionStack[level].end() ){
331                  prec = (*it).second;
332                  break;
333              }
334              level--;
335          }
336          return prec;
337      }
338  
339  protected:
currentLevel()340      int currentLevel() const { return static_cast<int>(table.size()) - 1; }
341  
342      std::vector<TSymbolTableLevel*> table;
343      typedef std::map< TBasicType, TPrecision > PrecisionStackLevel;
344      std::vector< PrecisionStackLevel > precisionStack;
345      int uniqueId;     // for unique identification in code generation
346  };
347  
348  #endif // _SYMBOL_TABLE_INCLUDED_
349