src/shared/cplusplus/Scope.cpp

   1 /**************************************************************************
   2 **
   3 ** This file is part of Qt Creator
   4 **
   5 ** Copyright (c) 2011 Nokia Corporation and/or its subsidiary(-ies).
   6 **
   7 ** Contact: Nokia Corporation (qt-info@nokia.com)
   8 **
   9 ** No Commercial Usage
  10 **
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 **
  18 ** Alternatively, this file may be used under the terms of the GNU Lesser
  19 ** General Public License version 2.1 as published by the Free Software
  20 ** Foundation and appearing in the file LICENSE.LGPL included in the
  21 ** packaging of this file.  Please review the following information to
  22 ** ensure the GNU Lesser General Public License version 2.1 requirements
  23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  24 **
  25 ** In addition, as a special exception, Nokia gives you certain additional
  26 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  28 **
  29 ** If you have questions regarding the use of this file, please contact
  30 ** Nokia at qt-info@nokia.com.
  31 **
  32 **************************************************************************/
  33 // Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>
  34 //
  35 // Permission is hereby granted, free of charge, to any person obtaining a copy
  36 // of this software and associated documentation files (the "Software"), to deal
  37 // in the Software without restriction, including without limitation the rights
  38 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  39 // copies of the Software, and to permit persons to whom the Software is
  40 // furnished to do so, subject to the following conditions:
  41 //
  42 // The above copyright notice and this permission notice shall be included in
  43 // all copies or substantial portions of the Software.
  44 //
  45 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  46 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  47 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  48 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  49 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  50 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  51 // THE SOFTWARE.
  52
  53 #include "Scope.h"
  54 #include "Symbols.h"
  55 #include "Names.h"
  56 #include "Literals.h"
  57 #include <cassert>
  58 #include <cstring>
  59
  60 using namespace CPlusPlus;
  61
  62 class CPlusPlus::SymbolTable
  63 {
  64     SymbolTable(const SymbolTable &other);
  65     void operator =(const SymbolTable &other);
  66
  67 public:
  68     typedef Symbol **iterator;
  69
  70 public:
  71     /// Constructs an empty Scope.
  72     SymbolTable(Scope *owner = 0);
  73
  74     /// Destroy this scope.
  75     ~SymbolTable();
  76
  77     /// Returns this scope's owner Symbol.
  78     Scope *owner() const;
  79
  80     /// Sets this scope's owner Symbol.
  81     void setOwner(Scope *owner); // ### remove me
  82
  83     /// Adds a Symbol to this Scope.
  84     void enterSymbol(Symbol *symbol);
  85
  86     /// Returns true if this Scope is empty; otherwise returns false.
  87     bool isEmpty() const;
  88
  89     /// Returns the number of symbols is in the scope.
  90     unsigned symbolCount() const;
  91
  92     /// Returns the Symbol at the given position.
  93     Symbol *symbolAt(unsigned index) const;
  94
  95     /// Returns the first Symbol in the scope.
  96     iterator firstSymbol() const;
  97
  98     /// Returns the last Symbol in the scope.
  99     iterator lastSymbol() const;
 100
 101     Symbol *lookat(const Identifier *id) const;
 102     Symbol *lookat(OperatorNameId::Kind operatorId) const;
 103
 104 private:
 105     /// Returns the hash value for the given Symbol.
 106     unsigned hashValue(Symbol *symbol) const;
 107
 108     /// Updates the hash table.
 109     void rehash();
 110
 111 private:
 112     enum { DefaultInitialSize = 4 };
 113
 114     Scope *_owner;
 115     Symbol **_symbols;
 116     Symbol **_hash;
 117     int _allocatedSymbols;
 118     int _symbolCount;
 119     int _hashSize;
 120 };
 121
 122 SymbolTable::SymbolTable(Scope *owner)
 123     : _owner(owner),
 124       _symbols(0),
 125       _hash(0),
 126       _allocatedSymbols(0),
 127       _symbolCount(-1),
 128       _hashSize(0)
 129 { }
 130
 131 SymbolTable::~SymbolTable()
 132 {
 133     if (_symbols)
 134         free(_symbols);
 135     if (_hash)
 136         free(_hash);
 137 }
 138
 139 void SymbolTable::enterSymbol(Symbol *symbol)
 140 {
 141     if (++_symbolCount == _allocatedSymbols) {
 142         _allocatedSymbols <<= 1;
 143         if (! _allocatedSymbols)
 144             _allocatedSymbols = DefaultInitialSize;
 145
 146         _symbols = reinterpret_cast<Symbol **>(realloc(_symbols, sizeof(Symbol *) * _allocatedSymbols));
 147     }
 148
 149     assert(! symbol->_scope || symbol->enclosingScope() == _owner);
 150     symbol->_index = _symbolCount;
 151     symbol->_scope = _owner;
 152     _symbols[_symbolCount] = symbol;
 153
 154     if (_symbolCount * 5 >= _hashSize * 3)
 155         rehash();
 156     else {
 157         const unsigned h = hashValue(symbol);
 158         symbol->_next = _hash[h];
 159         _hash[h] = symbol;
 160     }
 161 }
 162
 163 Symbol *SymbolTable::lookat(const Identifier *id) const
 164 {
 165     if (! _hash || ! id)
 166         return 0;
 167
 168     const unsigned h = id->hashCode() % _hashSize;
 169     Symbol *symbol = _hash[h];
 170     for (; symbol; symbol = symbol->_next) {
 171         const Name *identity = symbol->unqualifiedName();
 172         if (! identity) {
 173             continue;
 174         } else if (const Identifier *nameId = identity->asNameId()) {
 175             if (nameId->identifier()->isEqualTo(id))
 176                 break;
 177         } else if (const TemplateNameId *t = identity->asTemplateNameId()) {
 178             if (t->identifier()->isEqualTo(id))
 179                 break;
 180         } else if (const DestructorNameId *d = identity->asDestructorNameId()) {
 181             if (d->identifier()->isEqualTo(id))
 182                 break;
 183         } else if (identity->isQualifiedNameId()) {
 184             return 0;
 185         } else if (const SelectorNameId *selectorNameId = identity->asSelectorNameId()) {
 186             if (selectorNameId->identifier()->isEqualTo(id))
 187                 break;
 188         }
 189     }
 190     return symbol;
 191 }
 192
 193 Symbol *SymbolTable::lookat(OperatorNameId::Kind operatorId) const
 194 {
 195     if (! _hash)
 196         return 0;
 197
 198     const unsigned h = operatorId % _hashSize;
 199     Symbol *symbol = _hash[h];
 200     for (; symbol; symbol = symbol->_next) {
 201         if (const Name *identity = symbol->unqualifiedName()) {
 202             if (const OperatorNameId *op = identity->asOperatorNameId()) {
 203                 if (op->kind() == operatorId)
 204                     break;
 205             }
 206         }
 207     }
 208     return symbol;
 209 }
 210
 211 void SymbolTable::rehash()
 212 {
 213     _hashSize <<= 1;
 214
 215     if (! _hashSize)
 216         _hashSize = DefaultInitialSize;
 217
 218     _hash = reinterpret_cast<Symbol **>(realloc(_hash, sizeof(Symbol *) * _hashSize));
 219     std::memset(_hash, 0, sizeof(Symbol *) * _hashSize);
 220
 221     for (int index = 0; index < _symbolCount + 1; ++index) {
 222         Symbol *symbol = _symbols[index];
 223         const unsigned h = hashValue(symbol);
 224         symbol->_next = _hash[h];
 225         _hash[h] = symbol;
 226     }
 227 }
 228
 229 unsigned SymbolTable::hashValue(Symbol *symbol) const
 230 {
 231     if (! symbol)
 232         return 0;
 233
 234     return symbol->hashCode() % _hashSize;
 235 }
 236
 237 bool SymbolTable::isEmpty() const
 238 { return _symbolCount == -1; }
 239
 240 unsigned SymbolTable::symbolCount() const
 241 { return _symbolCount + 1; }
 242
 243 Symbol *SymbolTable::symbolAt(unsigned index) const
 244 {
 245     if (! _symbols)
 246         return 0;
 247     return _symbols[index];
 248 }
 249
 250 SymbolTable::iterator SymbolTable::firstSymbol() const
 251 { return _symbols; }
 252
 253 SymbolTable::iterator SymbolTable::lastSymbol() const
 254 { return _symbols + _symbolCount + 1; }
 255
 256 Scope::Scope(TranslationUnit *translationUnit, unsigned sourceLocation, const Name *name)
 257     : Symbol(translationUnit, sourceLocation, name),
 258       _members(0),
 259       _startOffset(0),
 260       _endOffset(0)
 261 { }
 262
 263 Scope::~Scope()
 264 { delete _members; }
 265
 266 /// Adds a Symbol to this Scope.
 267 void Scope::addMember(Symbol *symbol)
 268 {
 269     if (! _members)
 270         _members = new SymbolTable(this);
 271
 272     _members->enterSymbol(symbol);
 273 }
 274
 275 /// Returns true if this Scope is empty; otherwise returns false.
 276 bool Scope::isEmpty() const
 277 { return _members ? _members->isEmpty() : true; }
 278
 279 /// Returns the number of symbols is in the scope.
 280 unsigned Scope::memberCount() const
 281 { return _members ? _members->symbolCount() : 0; }
 282
 283 /// Returns the Symbol at the given position.
 284 Symbol *Scope::memberAt(unsigned index) const
 285 { return _members ? _members->symbolAt(index) : 0; }
 286
 287 /// Returns the first Symbol in the scope.
 288 Scope::iterator Scope::firstMember() const
 289 { return _members ? _members->firstSymbol() : 0; }
 290
 291 /// Returns the last Symbol in the scope.
 292 Scope::iterator Scope::lastMember() const
 293 { return _members ? _members->lastSymbol() : 0; }
 294
 295 Symbol *Scope::find(const Identifier *id) const
 296 { return _members ? _members->lookat(id) : 0; }
 297
 298 Symbol *Scope::find(OperatorNameId::Kind operatorId) const
 299 { return _members ? _members->lookat(operatorId) : 0; }
 300
 301 /// Set the start offset of the scope
 302 unsigned Scope::startOffset() const
 303 { return _startOffset; }
 304
 305 void Scope::setStartOffset(unsigned offset)
 306 { _startOffset = offset; }
 307
 308 /// Set the end offset of the scope
 309 unsigned Scope::endOffset() const
 310 { return _endOffset; }
 311
 312 void Scope::setEndOffset(unsigned offset)
 313 { _endOffset = offset; }