Scope.cpp 9.29 KB
Newer Older
1
/**************************************************************************
con's avatar
con committed
2
3
4
**
** This file is part of Qt Creator
**
hjk's avatar
hjk committed
5
** Copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).
con's avatar
con committed
6
**
7
** Contact: Nokia Corporation (qt-info@nokia.com)
con's avatar
con committed
8
**
9
** Commercial Usage
10
**
11
12
13
14
** Licensees holding valid Qt Commercial licenses may use this file in
** accordance with the Qt Commercial License Agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Nokia.
15
**
16
** GNU Lesser General Public License Usage
17
**
18
19
20
21
22
23
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24
**
25
** If you are unsure which license is appropriate for your use, please
hjk's avatar
hjk committed
26
** contact the sales department at http://qt.nokia.com/contact.
con's avatar
con committed
27
**
28
**************************************************************************/
con's avatar
con committed
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#include "Scope.h"
#include "Symbols.h"
#include "Names.h"
#include "Literals.h"
#include <cassert>
#include <cstring>
55

Roberto Raggi's avatar
Roberto Raggi committed
56
using namespace CPlusPlus;
con's avatar
con committed
57

Roberto Raggi's avatar
Roberto Raggi committed
58
class CPlusPlus::SymbolTable
con's avatar
con committed
59
{
Roberto Raggi's avatar
Roberto Raggi committed
60
61
    SymbolTable(const SymbolTable &other);
    void operator =(const SymbolTable &other);
con's avatar
con committed
62

Roberto Raggi's avatar
Roberto Raggi committed
63
64
public:
    typedef Symbol **iterator;
con's avatar
con committed
65

Roberto Raggi's avatar
Roberto Raggi committed
66
67
68
public:
    /// Constructs an empty Scope.
    SymbolTable(Scope *owner = 0);
con's avatar
con committed
69

Roberto Raggi's avatar
Roberto Raggi committed
70
71
    /// Destroy this scope.
    ~SymbolTable();
con's avatar
con committed
72

Roberto Raggi's avatar
Roberto Raggi committed
73
74
    /// Returns this scope's owner Symbol.
    Scope *owner() const;
con's avatar
con committed
75

Roberto Raggi's avatar
Roberto Raggi committed
76
77
    /// Sets this scope's owner Symbol.
    void setOwner(Scope *owner); // ### remove me
con's avatar
con committed
78

Roberto Raggi's avatar
Roberto Raggi committed
79
80
    /// Adds a Symbol to this Scope.
    void enterSymbol(Symbol *symbol);
con's avatar
con committed
81

Roberto Raggi's avatar
Roberto Raggi committed
82
83
    /// Returns true if this Scope is empty; otherwise returns false.
    bool isEmpty() const;
con's avatar
con committed
84

Roberto Raggi's avatar
Roberto Raggi committed
85
86
    /// Returns the number of symbols is in the scope.
    unsigned symbolCount() const;
con's avatar
con committed
87

Roberto Raggi's avatar
Roberto Raggi committed
88
89
    /// Returns the Symbol at the given position.
    Symbol *symbolAt(unsigned index) const;
con's avatar
con committed
90

Roberto Raggi's avatar
Roberto Raggi committed
91
92
    /// Returns the first Symbol in the scope.
    iterator firstSymbol() const;
con's avatar
con committed
93

Roberto Raggi's avatar
Roberto Raggi committed
94
95
    /// Returns the last Symbol in the scope.
    iterator lastSymbol() const;
con's avatar
con committed
96

Roberto Raggi's avatar
Roberto Raggi committed
97
98
99
    Symbol *lookat(const Name *name) const;
    Symbol *lookat(const Identifier *id) const;
    Symbol *lookat(int operatorId) const;
con's avatar
con committed
100

Roberto Raggi's avatar
Roberto Raggi committed
101
102
103
private:
    /// Returns the hash value for the given Symbol.
    unsigned hashValue(Symbol *symbol) const;
con's avatar
con committed
104

Roberto Raggi's avatar
Roberto Raggi committed
105
106
    /// Updates the hash table.
    void rehash();
107

Roberto Raggi's avatar
Roberto Raggi committed
108
109
private:
    enum { DefaultInitialSize = 11 };
110

Roberto Raggi's avatar
Roberto Raggi committed
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
    Scope *_owner;
    Symbol **_symbols;
    Symbol **_hash;
    int _allocatedSymbols;
    int _symbolCount;
    int _hashSize;
};

SymbolTable::SymbolTable(Scope *owner)
    : _owner(owner),
      _symbols(0),
      _hash(0),
      _allocatedSymbols(0),
      _symbolCount(-1),
      _hashSize(0)
{ }
con's avatar
con committed
127

Roberto Raggi's avatar
Roberto Raggi committed
128
SymbolTable::~SymbolTable()
129
{
Roberto Raggi's avatar
Roberto Raggi committed
130
131
132
133
    if (_symbols)
        free(_symbols);
    if (_hash)
        free(_hash);
134
135
}

Roberto Raggi's avatar
Roberto Raggi committed
136
void SymbolTable::enterSymbol(Symbol *symbol)
con's avatar
con committed
137
138
139
140
141
142
143
144
145
{
    if (++_symbolCount == _allocatedSymbols) {
        _allocatedSymbols <<= 1;
        if (! _allocatedSymbols)
            _allocatedSymbols = DefaultInitialSize;

        _symbols = reinterpret_cast<Symbol **>(realloc(_symbols, sizeof(Symbol *) * _allocatedSymbols));
    }

146
    assert(! symbol->_scope || symbol->scope() == _owner);
con's avatar
con committed
147
    symbol->_index = _symbolCount;
Roberto Raggi's avatar
Roberto Raggi committed
148
    symbol->_scope = _owner;
con's avatar
con committed
149
150
151
152
153
154
155
156
157
158
159
    _symbols[_symbolCount] = symbol;

    if (_symbolCount >= _hashSize * 0.6)
        rehash();
    else {
        const unsigned h = hashValue(symbol);
        symbol->_next = _hash[h];
        _hash[h] = symbol;
    }
}

Roberto Raggi's avatar
Roberto Raggi committed
160
Symbol *SymbolTable::lookat(const Name *name) const
161
162
163
164
{
    if (! name)
        return 0;

Roberto Raggi's avatar
Roberto Raggi committed
165
    else if (const OperatorNameId *opId = name->asOperatorNameId())
166
167
        return lookat(opId->kind());

Roberto Raggi's avatar
Roberto Raggi committed
168
    else if (const Identifier *id = name->identifier())
169
170
171
172
173
174
        return lookat(id);

    else
        return 0;
}

Roberto Raggi's avatar
Roberto Raggi committed
175
Symbol *SymbolTable::lookat(const Identifier *id) const
con's avatar
con committed
176
{
177
    if (! _hash || ! id)
con's avatar
con committed
178
179
180
181
182
        return 0;

    const unsigned h = id->hashCode() % _hashSize;
    Symbol *symbol = _hash[h];
    for (; symbol; symbol = symbol->_next) {
Roberto Raggi's avatar
Roberto Raggi committed
183
        const Name *identity = symbol->identity();
184
185
        if (! identity) {
            continue;
Roberto Raggi's avatar
Roberto Raggi committed
186
        } else if (const NameId *nameId = identity->asNameId()) {
con's avatar
con committed
187
188
            if (nameId->identifier()->isEqualTo(id))
                break;
Roberto Raggi's avatar
Roberto Raggi committed
189
        } else if (const TemplateNameId *t = identity->asTemplateNameId()) {
con's avatar
con committed
190
191
            if (t->identifier()->isEqualTo(id))
                break;
Roberto Raggi's avatar
Roberto Raggi committed
192
        } else if (const DestructorNameId *d = identity->asDestructorNameId()) {
con's avatar
con committed
193
194
195
            if (d->identifier()->isEqualTo(id))
                break;
        } else if (identity->isQualifiedNameId()) {
Roberto Raggi's avatar
Roberto Raggi committed
196
197
            return 0;
        } else if (const SelectorNameId *selectorNameId = identity->asSelectorNameId()) {
198
199
            if (selectorNameId->identifier()->isEqualTo(id))
                break;
con's avatar
con committed
200
201
202
203
204
        }
    }
    return symbol;
}

Roberto Raggi's avatar
Roberto Raggi committed
205
Symbol *SymbolTable::lookat(int operatorId) const
con's avatar
con committed
206
207
208
209
210
211
212
{
    if (! _hash)
        return 0;

    const unsigned h = operatorId % _hashSize;
    Symbol *symbol = _hash[h];
    for (; symbol; symbol = symbol->_next) {
Roberto Raggi's avatar
Roberto Raggi committed
213
214
        const Name *identity = symbol->identity();
        if (const OperatorNameId *op = identity->asOperatorNameId()) {
con's avatar
con committed
215
216
217
218
219
220
221
            if (op->kind() == operatorId)
                break;
        }
    }
    return symbol;
}

Roberto Raggi's avatar
Roberto Raggi committed
222
void SymbolTable::rehash()
con's avatar
con committed
223
224
225
226
227
228
229
{
    _hashSize <<= 1;

    if (! _hashSize)
        _hashSize = DefaultInitialSize;

    _hash = reinterpret_cast<Symbol **>(realloc(_hash, sizeof(Symbol *) * _hashSize));
Roberto Raggi's avatar
Roberto Raggi committed
230
    std::memset(_hash, 0, sizeof(Symbol *) * _hashSize);
con's avatar
con committed
231
232
233
234
235
236
237
238
239

    for (int index = 0; index < _symbolCount + 1; ++index) {
        Symbol *symbol = _symbols[index];
        const unsigned h = hashValue(symbol);
        symbol->_next = _hash[h];
        _hash[h] = symbol;
    }
}

Roberto Raggi's avatar
Roberto Raggi committed
240
unsigned SymbolTable::hashValue(Symbol *symbol) const
con's avatar
con committed
241
242
243
244
245
246
247
{
    if (! symbol)
        return 0;

    return symbol->hashCode() % _hashSize;
}

Roberto Raggi's avatar
Roberto Raggi committed
248
bool SymbolTable::isEmpty() const
con's avatar
con committed
249
250
{ return _symbolCount == -1; }

Roberto Raggi's avatar
Roberto Raggi committed
251
unsigned SymbolTable::symbolCount() const
con's avatar
con committed
252
253
{ return _symbolCount + 1; }

Roberto Raggi's avatar
Roberto Raggi committed
254
Symbol *SymbolTable::symbolAt(unsigned index) const
con's avatar
con committed
255
256
257
258
259
260
{
    if (! _symbols)
        return 0;
    return _symbols[index];
}

Roberto Raggi's avatar
Roberto Raggi committed
261
SymbolTable::iterator SymbolTable::firstSymbol() const
con's avatar
con committed
262
263
{ return _symbols; }

Roberto Raggi's avatar
Roberto Raggi committed
264
SymbolTable::iterator SymbolTable::lastSymbol() const
con's avatar
con committed
265
266
{ return _symbols + _symbolCount + 1; }

Roberto Raggi's avatar
Roberto Raggi committed
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
Scope::Scope(TranslationUnit *translationUnit, unsigned sourceLocation, const Name *name)
    : Symbol(translationUnit, sourceLocation, name),
      _members(0),
      _startOffset(0),
      _endOffset(0)
{ }

Scope::~Scope()
{ delete _members; }

/// Adds a Symbol to this Scope.
void Scope::addMember(Symbol *symbol)
{
    if (! _members)
        _members = new SymbolTable(this);

    _members->enterSymbol(symbol);
}

/// Returns true if this Scope is empty; otherwise returns false.
bool Scope::isEmpty() const
{ return _members ? _members->isEmpty() : true; }

/// Returns the number of symbols is in the scope.
unsigned Scope::memberCount() const
{ return _members ? _members->symbolCount() : 0; }

/// Returns the Symbol at the given position.
Symbol *Scope::memberAt(unsigned index) const
{ return _members ? _members->symbolAt(index) : 0; }

/// Returns the first Symbol in the scope.
Scope::iterator Scope::firstMember() const
{ return _members ? _members->firstSymbol() : 0; }

/// Returns the last Symbol in the scope.
Scope::iterator Scope::lastMember() const
{ return _members ? _members->lastSymbol() : 0; }

Symbol *Scope::find(const Name *name) const
{ return _members ? _members->lookat(name) : 0; }

Symbol *Scope::find(const Identifier *id) const
{ return _members ? _members->lookat(id) : 0; }

Symbol *Scope::find(int operatorId) const
{ return _members ? _members->lookat(operatorId) : 0; }

/// Set the start offset of the scope
316
317
318
319
320
321
unsigned Scope::startOffset() const
{ return _startOffset; }

void Scope::setStartOffset(unsigned offset)
{ _startOffset = offset; }

Roberto Raggi's avatar
Roberto Raggi committed
322
/// Set the end offset of the scope
323
324
325
326
327
unsigned Scope::endOffset() const
{ return _endOffset; }

void Scope::setEndOffset(unsigned offset)
{ _endOffset = offset; }