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//
41class TSymbol {
42public:
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
56protected:
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//
71class TVariable : public TSymbol {
72public:
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        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
106protected:
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//
119struct TParameter {
120    TString *name;
121    TType* type;
122    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//
132class TFunction : public TSymbol {
133public:
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) :
140        TSymbol(name),
141        returnType(retType),
142        mangledName(TFunction::mangleName(*name)),
143        op(tOp),
144        defined(false) { }
145    virtual ~TFunction();
146    virtual bool isFunction() const { return true; }
147
148    static TString mangleName(const TString& name) { return name + '('; }
149    static TString unmangleName(const TString& mangledName)
150    {
151        return TString(mangledName.c_str(), mangledName.find_first_of('('));
152    }
153
154    void addParameter(TParameter& p)
155    {
156        parameters.push_back(p);
157        mangledName = mangledName + p.type->getMangledName();
158    }
159
160    const TString& getMangledName() const { return mangledName; }
161    const TType& getReturnType() const { return returnType; }
162
163    void relateToOperator(TOperator o) { op = o; }
164    TOperator getBuiltInOp() const { return op; }
165
166    void relateToExtension(const TString& ext) { extension = ext; }
167    const TString& getExtension() const { return extension; }
168
169    void setDefined() { defined = true; }
170    bool isDefined() { return defined; }
171
172    int getParamCount() const { return static_cast<int>(parameters.size()); }
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
179protected:
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
190class TSymbolTableLevel {
191public:
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)
198    TSymbolTableLevel() { }
199    ~TSymbolTableLevel();
200
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
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
221    const_iterator begin() const
222    {
223        return level.begin();
224    }
225
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
236protected:
237    tLevel level;
238};
239
240class TSymbolTable {
241public:
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
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    //
263    bool isEmpty() { return table.size() == 0; }
264    bool atBuiltInLevel() { return table.size() == 1; }
265    bool atGlobalLevel() { return table.size() <= 2; }
266    void push()
267    {
268        table.push_back(new TSymbolTableLevel);
269        precisionStack.push_back( PrecisionStackLevel() );
270    }
271
272    void pop()
273    {
274        delete table[currentLevel()];
275        table.pop_back();
276        precisionStack.pop_back();
277    }
278
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
301    TSymbolTableLevel* getGlobalLevel() {
302        assert(table.size() >= 2);
303        return table[1];
304    }
305    void relateToOperator(const char* name, TOperator op) {
306        table[0]->relateToOperator(name, op);
307    }
308    void relateToExtension(const char* name, const TString& ext) {
309        table[0]->relateToExtension(name, ext);
310    }
311    int getMaxSymbolId() { return uniqueId; }
312    void dump(TInfoSink &infoSink) const;
313    void copyTable(const TSymbolTable& copyOf);
314
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
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
339protected:
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