1 // Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to deal
5 // in the Software without restriction, including without limitation the rights
6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 // copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 // THE SOFTWARE.
20
21 #include "Scope.h"
22 #include "Symbols.h"
23 #include "Names.h"
24 #include "Literals.h"
25 #include "Templates.h"
26
27 #include "cppassert.h"
28
29 #include <cstring>
30
31 namespace CPlusPlus {
32
33 class SymbolTable
34 {
35 SymbolTable(const SymbolTable &other);
36 void operator =(const SymbolTable &other);
37
38 public:
39 typedef Symbol **iterator;
40
41 public:
42 /// Constructs an empty Scope.
43 SymbolTable(Scope *owner = nullptr);
44
45 /// Destroy this scope.
46 ~SymbolTable();
47
48 /// Returns this scope's owner Symbol.
49 Scope *owner() const;
50
51 /// Sets this scope's owner Symbol.
52 void setOwner(Scope *owner); // ### remove me
53
54 /// Adds a Symbol to this Scope.
55 void enterSymbol(Symbol *symbol);
56
57 /// Returns true if this Scope is empty; otherwise returns false.
58 bool isEmpty() const;
59
60 /// Returns the number of symbols is in the scope.
61 int symbolCount() const;
62
63 /// Returns the Symbol at the given position.
64 Symbol *symbolAt(int index) const;
65
66 /// Returns the first Symbol in the scope.
67 iterator firstSymbol() const;
68
69 /// Returns the last Symbol in the scope.
70 iterator lastSymbol() const;
71
72 Symbol *lookat(const Identifier *id) const;
73 Symbol *lookat(OperatorNameId::Kind operatorId) const;
74 Symbol *lookat(const ConversionNameId *convId) const;
75
76 private:
77 /// Returns the hash value for the given Symbol.
78 unsigned hashValue(Symbol *symbol) const;
79
80 /// Updates the hash table.
81 void rehash();
82
83 private:
84 enum { DefaultInitialSize = 4 };
85
86 Scope *_owner;
87 Symbol **_symbols;
88 Symbol **_hash;
89 int _allocatedSymbols;
90 int _symbolCount;
91 int _hashSize;
92 };
93
SymbolTable(Scope * owner)94 SymbolTable::SymbolTable(Scope *owner)
95 : _owner(owner),
96 _symbols(nullptr),
97 _hash(nullptr),
98 _allocatedSymbols(0),
99 _symbolCount(-1),
100 _hashSize(0)
101 { }
102
~SymbolTable()103 SymbolTable::~SymbolTable()
104 {
105 if (_symbols)
106 free(_symbols);
107 if (_hash)
108 free(_hash);
109 }
110
enterSymbol(Symbol * symbol)111 void SymbolTable::enterSymbol(Symbol *symbol)
112 {
113 CPP_ASSERT(! symbol->_enclosingScope || symbol->enclosingScope() == _owner, return);
114
115 if (++_symbolCount == _allocatedSymbols) {
116 _allocatedSymbols <<= 1;
117 if (! _allocatedSymbols)
118 _allocatedSymbols = DefaultInitialSize;
119
120 _symbols = reinterpret_cast<Symbol **>(realloc(_symbols, sizeof(Symbol *) * _allocatedSymbols));
121 memset(_symbols + _symbolCount, 0, sizeof(Symbol *) * (_allocatedSymbols - _symbolCount));
122 }
123
124 symbol->_index = _symbolCount;
125 symbol->_enclosingScope = _owner;
126 _symbols[_symbolCount] = symbol;
127
128 if (_symbolCount * 5 >= _hashSize * 3)
129 rehash();
130 else {
131 const unsigned h = hashValue(symbol);
132 symbol->_next = _hash[h];
133 _hash[h] = symbol;
134 }
135 }
136
lookat(const Identifier * id) const137 Symbol *SymbolTable::lookat(const Identifier *id) const
138 {
139 if (! _hash || ! id)
140 return nullptr;
141
142 const unsigned h = id->hashCode() % _hashSize;
143 Symbol *symbol = _hash[h];
144 for (; symbol; symbol = symbol->_next) {
145 const Name *identity = symbol->unqualifiedName();
146 if (! identity) {
147 continue;
148 } else if (const Identifier *nameId = identity->asNameId()) {
149 if (nameId->identifier()->match(id))
150 break;
151 } else if (const TemplateNameId *t = identity->asTemplateNameId()) {
152 if (t->identifier()->match(id))
153 break;
154 } else if (const DestructorNameId *d = identity->asDestructorNameId()) {
155 if (d->identifier()->match(id))
156 break;
157 } else if (identity->isQualifiedNameId()) {
158 return nullptr;
159 } else if (const SelectorNameId *selectorNameId = identity->asSelectorNameId()) {
160 if (selectorNameId->identifier()->match(id))
161 break;
162 }
163 }
164 return symbol;
165 }
166
lookat(OperatorNameId::Kind operatorId) const167 Symbol *SymbolTable::lookat(OperatorNameId::Kind operatorId) const
168 {
169 if (! _hash)
170 return nullptr;
171
172 const unsigned h = operatorId % _hashSize;
173 Symbol *symbol = _hash[h];
174 for (; symbol; symbol = symbol->_next) {
175 if (const Name *identity = symbol->unqualifiedName()) {
176 if (const OperatorNameId *op = identity->asOperatorNameId()) {
177 if (op->kind() == operatorId)
178 break;
179 }
180 }
181 }
182 return symbol;
183 }
184
lookat(const ConversionNameId * convId) const185 Symbol *SymbolTable::lookat(const ConversionNameId *convId) const
186 {
187 if (!_hash)
188 return nullptr;
189
190 Symbol *symbol = _hash[0]; // See Symbol::HashCode
191 for (; symbol; symbol = symbol->_next) {
192 if (const Name *identity = symbol->unqualifiedName()) {
193 if (const ConversionNameId * const id = identity->asConversionNameId()) {
194 if (id->type().match(convId->type()))
195 break;
196 }
197 }
198 }
199 return symbol;
200 }
201
rehash()202 void SymbolTable::rehash()
203 {
204 _hashSize <<= 1;
205
206 if (! _hashSize)
207 _hashSize = DefaultInitialSize;
208
209 _hash = reinterpret_cast<Symbol **>(realloc(_hash, sizeof(Symbol *) * _hashSize));
210 std::memset(_hash, 0, sizeof(Symbol *) * _hashSize);
211
212 for (int index = 0; index < _symbolCount + 1; ++index) {
213 Symbol *symbol = _symbols[index];
214 const unsigned h = hashValue(symbol);
215 symbol->_next = _hash[h];
216 _hash[h] = symbol;
217 }
218 }
219
hashValue(Symbol * symbol) const220 unsigned SymbolTable::hashValue(Symbol *symbol) const
221 {
222 if (! symbol)
223 return 0;
224
225 return symbol->hashCode() % _hashSize;
226 }
227
isEmpty() const228 bool SymbolTable::isEmpty() const
229 { return _symbolCount == -1; }
230
symbolCount() const231 int SymbolTable::symbolCount() const
232 { return _symbolCount + 1; }
233
symbolAt(int index) const234 Symbol *SymbolTable::symbolAt(int index) const
235 {
236 if (! _symbols)
237 return nullptr;
238 return _symbols[index];
239 }
240
firstSymbol() const241 SymbolTable::iterator SymbolTable::firstSymbol() const
242 { return _symbols; }
243
lastSymbol() const244 SymbolTable::iterator SymbolTable::lastSymbol() const
245 { return _symbols + _symbolCount + 1; }
246
Scope(TranslationUnit * translationUnit,int sourceLocation,const Name * name)247 Scope::Scope(TranslationUnit *translationUnit, int sourceLocation, const Name *name)
248 : Symbol(translationUnit, sourceLocation, name),
249 _members(nullptr),
250 _startOffset(0),
251 _endOffset(0)
252 { }
253
Scope(Clone * clone,Subst * subst,Scope * original)254 Scope::Scope(Clone *clone, Subst *subst, Scope *original)
255 : Symbol(clone, subst, original)
256 , _members(nullptr)
257 , _startOffset(original->_startOffset)
258 , _endOffset(original->_endOffset)
259 {
260 for (iterator it = original->memberBegin(), end = original->memberEnd(); it != end; ++it)
261 addMember(clone->symbol(*it, subst));
262 }
263
~Scope()264 Scope::~Scope()
265 { delete _members; }
266
267 /// Adds a Symbol to this Scope.
addMember(Symbol * symbol)268 void Scope::addMember(Symbol *symbol)
269 {
270 if (! _members)
271 _members = new SymbolTable(this);
272
273 _members->enterSymbol(symbol);
274 }
275
276 /// Returns true if this Scope is empty; otherwise returns false.
isEmpty() const277 bool Scope::isEmpty() const
278 { return _members ? _members->isEmpty() : true; }
279
280 /// Returns the number of symbols is in the scope.
memberCount() const281 int Scope::memberCount() const
282 { return _members ? _members->symbolCount() : 0; }
283
284 /// Returns the Symbol at the given position.
memberAt(int index) const285 Symbol *Scope::memberAt(int index) const
286 { return _members ? _members->symbolAt(index) : nullptr; }
287
288 /// Returns the first Symbol in the scope.
memberBegin() const289 Scope::iterator Scope::memberBegin() const
290 { return _members ? _members->firstSymbol() : nullptr; }
291
292 /// Returns the last Symbol in the scope.
memberEnd() const293 Scope::iterator Scope::memberEnd() const
294 { return _members ? _members->lastSymbol() : nullptr; }
295
find(const Identifier * id) const296 Symbol *Scope::find(const Identifier *id) const
297 { return _members ? _members->lookat(id) : nullptr; }
298
find(OperatorNameId::Kind operatorId) const299 Symbol *Scope::find(OperatorNameId::Kind operatorId) const
300 { return _members ? _members->lookat(operatorId) : nullptr; }
301
find(const ConversionNameId * conv) const302 Symbol *Scope::find(const ConversionNameId *conv) const
303 { return _members ? _members->lookat(conv) : nullptr; }
304
305 /// Set the start offset of the scope
startOffset() const306 int Scope::startOffset() const
307 { return _startOffset; }
308
setStartOffset(int offset)309 void Scope::setStartOffset(int offset)
310 { _startOffset = offset; }
311
312 /// Set the end offset of the scope
endOffset() const313 int Scope::endOffset() const
314 { return _endOffset; }
315
setEndOffset(int offset)316 void Scope::setEndOffset(int offset)
317 { _endOffset = offset; }
318
319 } // namespace CPlusPlus
320