2010-12-26 MORITA Hajime <morrita@google.com>
[WebKit.git] / Sources / ThirdParty / ANGLE / src / compiler / SymbolTable.h
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:
43     POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
44     TSymbol(const TString *n) :  name(n) { }
45     virtual ~TSymbol() { /* don't delete name, it's from the pool */ }
46     const TString& getName() const { return *name; }
47     virtual const TString& getMangledName() const { return getName(); }
48     virtual bool isFunction() const { return false; }
49     virtual bool isVariable() const { return false; }
50     void setUniqueId(int id) { uniqueId = id; }
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:
73     TVariable(const TString *name, const TType& t, bool uT = false ) : TSymbol(name), type(t), userType(uT), unionArray(0), arrayInformationType(0) { }
74     virtual ~TVariable() { }
75     virtual bool isVariable() const { return true; }    
76     TType& getType() { return type; }    
77     const TType& getType() const { return type; }
78     bool isUserType() const { return userType; }
79     void setQualifier(TQualifier qualifier) { type.setQualifier(qualifier); }
80     void updateArrayInformationType(TType *t) { arrayInformationType = t; }
81     TType* getArrayInformationType() { return arrayInformationType; }
82
83     virtual void dump(TInfoSink &infoSink) const;
84
85     ConstantUnion* getConstPointer()
86     { 
87         if (!unionArray)
88             unionArray = new ConstantUnion[type.getObjectSize()];
89
90         return unionArray;
91     }
92
93     ConstantUnion* getConstPointer() const { return unionArray; }
94
95     void shareConstPointer( ConstantUnion *constArray)
96     {
97         delete unionArray;
98         unionArray = constArray;  
99     }
100     TVariable(const TVariable&, TStructureMap& remapper); // copy constructor
101     virtual TVariable* clone(TStructureMap& remapper);
102
103 protected:
104     TType type;
105     bool userType;
106     // we are assuming that Pool Allocator will free the memory allocated to unionArray
107     // when this object is destroyed
108     ConstantUnion *unionArray;
109     TType *arrayInformationType;  // this is used for updating maxArraySize in all the references to a given symbol
110 };
111
112 //
113 // The function sub-class of symbols and the parser will need to
114 // share this definition of a function parameter.
115 //
116 struct TParameter {
117     TString *name;
118     TType* type;
119     void copyParam(const TParameter& param, TStructureMap& remapper)
120     {
121         name = NewPoolTString(param.name->c_str());
122         type = param.type->clone(remapper);
123     }
124 };
125
126 //
127 // The function sub-class of a symbol.  
128 //
129 class TFunction : public TSymbol {
130 public:
131     TFunction(TOperator o) :
132         TSymbol(0),
133         returnType(TType(EbtVoid, EbpUndefined)),
134         op(o),
135         defined(false) { }
136     TFunction(const TString *name, TType& retType, TOperator tOp = EOpNull) : 
137         TSymbol(name), 
138         returnType(retType),
139         mangledName(TFunction::mangleName(*name)),
140         op(tOp),
141         defined(false) { }
142     virtual ~TFunction();
143     virtual bool isFunction() const { return true; }    
144
145     static TString mangleName(const TString& name) { return name + '('; }
146     static TString unmangleName(const TString& mangledName)
147     {
148         return TString(mangledName.c_str(), mangledName.find_first_of('('));
149     }
150
151     void addParameter(TParameter& p) 
152     { 
153         parameters.push_back(p);
154         mangledName = mangledName + p.type->getMangledName();
155     }
156
157     const TString& getMangledName() const { return mangledName; }
158     const TType& getReturnType() const { return returnType; }
159     void relateToOperator(TOperator o) { op = o; }
160     TOperator getBuiltInOp() const { return op; }
161     void setDefined() { defined = true; }
162     bool isDefined() { return defined; }
163
164     int getParamCount() const { return static_cast<int>(parameters.size()); }    
165     TParameter& operator [](int i)       { return parameters[i]; }
166     const TParameter& operator [](int i) const { return parameters[i]; }
167
168     virtual void dump(TInfoSink &infoSink) const;
169     TFunction(const TFunction&, TStructureMap& remapper);
170     virtual TFunction* clone(TStructureMap& remapper);
171
172 protected:
173     typedef TVector<TParameter> TParamList;
174     TParamList parameters;
175     TType returnType;
176     TString mangledName;
177     TOperator op;
178     bool defined;
179 };
180
181
182 class TSymbolTableLevel {
183 public:
184     typedef TMap<TString, TSymbol*> tLevel;
185     typedef tLevel::const_iterator const_iterator;
186     typedef const tLevel::value_type tLevelPair;
187     typedef std::pair<tLevel::iterator, bool> tInsertResult;
188
189     POOL_ALLOCATOR_NEW_DELETE(GlobalPoolAllocator)
190     TSymbolTableLevel() { }
191     ~TSymbolTableLevel();
192
193     bool insert(TSymbol& symbol) 
194     {
195         //
196         // returning true means symbol was added to the table
197         //
198         tInsertResult result;
199         result = level.insert(tLevelPair(symbol.getMangledName(), &symbol));
200
201         return result.second;
202     }
203
204     TSymbol* find(const TString& name) const
205     {
206         tLevel::const_iterator it = level.find(name);
207         if (it == level.end())
208             return 0;
209         else
210             return (*it).second;
211     }
212
213     const_iterator begin() const
214     {
215         return level.begin();
216     }
217
218     const_iterator end() const
219     {
220         return level.end();
221     }
222
223     void relateToOperator(const char* name, TOperator op);
224     void dump(TInfoSink &infoSink) const;
225     TSymbolTableLevel* clone(TStructureMap& remapper);
226
227 protected:
228     tLevel level;
229 };
230
231 class TSymbolTable {
232 public:
233     TSymbolTable() : uniqueId(0)
234     {
235         //
236         // The symbol table cannot be used until push() is called, but
237         // the lack of an initial call to push() can be used to detect
238         // that the symbol table has not been preloaded with built-ins.
239         //
240     }
241
242     ~TSymbolTable()
243     {
244         // level 0 is always built In symbols, so we never pop that out
245         while (table.size() > 1)
246             pop();
247     }
248
249     //
250     // When the symbol table is initialized with the built-ins, there should
251     // 'push' calls, so that built-ins are at level 0 and the shader
252     // globals are at level 1.
253     //
254     bool isEmpty() { return table.size() == 0; }
255     bool atBuiltInLevel() { return table.size() == 1; }
256     bool atGlobalLevel() { return table.size() <= 2; }
257     void push()
258     {
259         table.push_back(new TSymbolTableLevel);
260         precisionStack.push_back( PrecisionStackLevel() );
261     }
262
263     void pop()
264     { 
265         delete table[currentLevel()]; 
266         table.pop_back(); 
267         precisionStack.pop_back();
268     }
269
270     bool insert(TSymbol& symbol)
271     {
272         symbol.setUniqueId(++uniqueId);
273         return table[currentLevel()]->insert(symbol);
274     }
275
276     TSymbol* find(const TString& name, bool* builtIn = 0, bool *sameScope = 0) 
277     {
278         int level = currentLevel();
279         TSymbol* symbol;
280         do {
281             symbol = table[level]->find(name);
282             --level;
283         } while (symbol == 0 && level >= 0);
284         level++;
285         if (builtIn)
286             *builtIn = level == 0;
287         if (sameScope)
288             *sameScope = level == currentLevel();
289         return symbol;
290     }
291
292     TSymbolTableLevel* getGlobalLevel() { assert(table.size() >= 2); return table[1]; }
293     void relateToOperator(const char* name, TOperator op) { table[0]->relateToOperator(name, op); }
294     int getMaxSymbolId() { return uniqueId; }
295     void dump(TInfoSink &infoSink) const;
296     void copyTable(const TSymbolTable& copyOf);
297
298     void setDefaultPrecision( TBasicType type, TPrecision prec ){
299         if( type != EbtFloat && type != EbtInt ) return; // Only set default precision for int/float
300         int indexOfLastElement = static_cast<int>(precisionStack.size()) - 1;
301         precisionStack[indexOfLastElement][type] = prec; // Uses map operator [], overwrites the current value
302     }
303
304     // Searches down the precisionStack for a precision qualifier for the specified TBasicType
305     TPrecision getDefaultPrecision( TBasicType type){
306         if( type != EbtFloat && type != EbtInt ) return EbpUndefined;
307         int level = static_cast<int>(precisionStack.size()) - 1;
308         assert( level >= 0); // Just to be safe. Should not happen.
309         PrecisionStackLevel::iterator it;
310         TPrecision prec = EbpUndefined; // If we dont find anything we return this. Should we error check this?
311         while( level >= 0 ){
312             it = precisionStack[level].find( type );
313             if( it != precisionStack[level].end() ){
314                 prec = (*it).second;
315                 break;
316             }
317             level--;
318         }
319         return prec;
320     }
321
322 protected:    
323     int currentLevel() const { return static_cast<int>(table.size()) - 1; }
324
325     std::vector<TSymbolTableLevel*> table;
326     typedef std::map< TBasicType, TPrecision > PrecisionStackLevel;
327     std::vector< PrecisionStackLevel > precisionStack;
328     int uniqueId;     // for unique identification in code generation
329 };
330
331 #endif // _SYMBOL_TABLE_INCLUDED_