language/duchain/persistentsymboltable.cpp

   1 /* This file is part of KDevelop
   2     Copyright 2008 David Nolden <david.nolden.kdevelop@art-master.de>
   3
   4    This library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Library General Public
   6    License version 2 as published by the Free Software Foundation.
   7
   8    This library is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11    Library General Public License for more details.
  12
  13    You should have received a copy of the GNU Library General Public License
  14    along with this library; see the file COPYING.LIB.  If not, write to
  15    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  16    Boston, MA 02110-1301, USA.
  17 */
  18
  19 #include "persistentsymboltable.h"
  20
  21 #include <QHash>
  22 #include <QVector>
  23
  24 #include "declarationid.h"
  25 #include "appendedlist.h"
  26 #include "repositories/itemrepository.h"
  27 #include "identifier.h"
  28 #include "ducontext.h"
  29 #include "topducontext.h"
  30
  31 namespace KDevelop {
  32
  33 DEFINE_LIST_MEMBER_HASH(PersistentSymbolTableItem, declarations, IndexedDeclaration)
  34
  35 class PersistentSymbolTableItem {
  36   public:
  37   PersistentSymbolTableItem() {
  38     initializeAppendedLists();
  39   }
  40   PersistentSymbolTableItem(const PersistentSymbolTableItem& rhs) : id(rhs.id) {
  41     initializeAppendedLists();
  42     copyListsFrom(rhs);
  43   }
  44
  45   ~PersistentSymbolTableItem() {
  46     freeAppendedLists();
  47   }
  48
  49   unsigned int hash() const {
  50     //We only compare the declaration. This allows us implementing a map, although the item-repository
  51     //originally represents a set.
  52     return id.index;
  53   }
  54
  55   unsigned short int itemSize() const {
  56     return dynamicSize();
  57   }
  58
  59   uint classSize() const {
  60     return sizeof(PersistentSymbolTableItem);
  61   }
  62
  63   IndexedQualifiedIdentifier id;
  64
  65   START_APPENDED_LISTS(PersistentSymbolTableItem);
  66   APPENDED_LIST_FIRST(PersistentSymbolTableItem, IndexedDeclaration, declarations);
  67   END_APPENDED_LISTS(PersistentSymbolTableItem, declarations);
  68 };
  69
  70 class PersistentSymbolTableRequestItem {
  71   public:
  72
  73   PersistentSymbolTableRequestItem(const PersistentSymbolTableItem& item) : m_item(item) {
  74   }
  75   enum {
  76     AverageSize = 30 //This should be the approximate average size of an Item
  77   };
  78
  79   unsigned int hash() const {
  80     return m_item.hash();
  81   }
  82
  83   size_t itemSize() const {
  84       return m_item.itemSize();
  85   }
  86
  87   void createItem(PersistentSymbolTableItem* item) const {
  88     item->initializeAppendedLists(false);
  89     item->id = m_item.id;
  90     item->copyListsFrom(m_item);
  91   }
  92
  93   bool equals(const PersistentSymbolTableItem* item) const {
  94     return m_item.id == item->id;
  95   }
  96
  97   const PersistentSymbolTableItem& m_item;
  98 };
  99
 100 DEFINE_LIST_MEMBER_HASH(PersistentContextTableItem, contexts, IndexedDUContext)
 101
 102 class PersistentContextTableItem {
 103   public:
 104   PersistentContextTableItem() {
 105     initializeAppendedLists();
 106   }
 107   PersistentContextTableItem(const PersistentContextTableItem& rhs) : id(rhs.id) {
 108     initializeAppendedLists();
 109     copyListsFrom(rhs);
 110   }
 111
 112   ~PersistentContextTableItem() {
 113     freeAppendedLists();
 114   }
 115
 116   unsigned int hash() const {
 117     //We only compare the context. This allows us implementing a map, although the item-repository
 118     //originally represents a set.
 119     return id.index;
 120   }
 121
 122   size_t itemSize() const {
 123     return dynamicSize();
 124   }
 125
 126   uint classSize() const {
 127     return sizeof(PersistentContextTableItem);
 128   }
 129
 130   IndexedQualifiedIdentifier id;
 131
 132   START_APPENDED_LISTS(PersistentContextTableItem);
 133   APPENDED_LIST_FIRST(PersistentContextTableItem, IndexedDUContext, contexts);
 134   END_APPENDED_LISTS(PersistentContextTableItem, contexts);
 135 };
 136
 137 class PersistentContextTableRequestItem {
 138   public:
 139
 140   PersistentContextTableRequestItem(const PersistentContextTableItem& item) : m_item(item) {
 141   }
 142   enum {
 143     AverageSize = 30 //This should be the approximate average size of an Item
 144   };
 145
 146   unsigned int hash() const {
 147     return m_item.hash();
 148   }
 149
 150   size_t itemSize() const {
 151       return m_item.itemSize();
 152   }
 153
 154   void createItem(PersistentContextTableItem* item) const {
 155     item->initializeAppendedLists(false);
 156     item->id = m_item.id;
 157     item->copyListsFrom(m_item);
 158   }
 159
 160   bool equals(const PersistentContextTableItem* item) const {
 161     return m_item.id == item->id;
 162   }
 163
 164   const PersistentContextTableItem& m_item;
 165 };
 166
 167
 168 struct PersistentSymbolTablePrivate {
 169   PersistentSymbolTablePrivate() : m_declarations("Persistent Declaration Table"), m_contexts("Persistent Context Table") {
 170   }
 171   //Maps declaration-ids to declarations
 172   ItemRepository<PersistentSymbolTableItem, PersistentSymbolTableRequestItem> m_declarations;
 173   ItemRepository<PersistentContextTableItem, PersistentContextTableRequestItem> m_contexts;
 174 };
 175
 176 PersistentSymbolTable::PersistentSymbolTable() : d(new PersistentSymbolTablePrivate())
 177 {
 178 }
 179
 180 PersistentSymbolTable::~PersistentSymbolTable()
 181 {
 182   delete d;
 183 }
 184
 185 void PersistentSymbolTable::addDeclaration(const IndexedQualifiedIdentifier& id, const IndexedDeclaration& declaration)
 186 {
 187   PersistentSymbolTableItem item;
 188   item.id = id;
 189   item.declarationsList().append(declaration);
 190   PersistentSymbolTableRequestItem request(item);
 191
 192   uint index = d->m_declarations.findIndex(item);
 193
 194   if(index) {
 195     //Check whether the item is already in the mapped list, else copy the list into the new created item
 196     const PersistentSymbolTableItem* oldItem = d->m_declarations.itemFromIndex(index);
 197     for(uint a = 0; a < oldItem->declarationsSize(); ++a) {
 198       if(oldItem->declarations()[a] == declaration)
 199         return; //Already there
 200       item.declarationsList().append(oldItem->declarations()[a]);
 201     }
 202
 203     if(request.itemSize() > (1<<15))
 204       kWarning() << "many many declarations for id" << id.identifier().toString() << item.declarationsSize();
 205
 206     d->m_declarations.deleteItem(index);
 207     uint stillExistingIndex = d->m_declarations.findIndex(request);
 208     Q_ASSERT(!stillExistingIndex);
 209   }
 210
 211   //This inserts the changed item
 212   d->m_declarations.index(request);
 213 }
 214
 215 void PersistentSymbolTable::removeDeclaration(const IndexedQualifiedIdentifier& id, const IndexedDeclaration& declaration)
 216 {
 217   PersistentSymbolTableItem item;
 218   item.id = id;
 219   PersistentSymbolTableRequestItem request(item);
 220
 221   uint index = d->m_declarations.findIndex(item);
 222
 223   if(index) {
 224     //Check whether the item is already in the mapped list, else copy the list into the new created item
 225     const PersistentSymbolTableItem* oldItem = d->m_declarations.itemFromIndex(index);
 226     uint oldSize = oldItem->declarationsSize();
 227
 228     bool found = false;
 229
 230     for(uint a = 0; a < oldSize; ++a)
 231       if(!(oldItem->declarations()[a] == declaration))
 232         item.declarationsList().append(oldItem->declarations()[a]);
 233       else
 234         found = true;
 235
 236     if(found) {
 237       d->m_declarations.deleteItem(index);
 238       Q_ASSERT(d->m_declarations.findIndex(item) == 0);
 239
 240       //This inserts the changed item
 241       if(item.declarationsSize() != 0) {
 242         uint newIndex = d->m_declarations.index(request);
 243         Q_ASSERT(oldSize == d->m_declarations.itemFromIndex(newIndex)->declarationsSize()+1);
 244       }
 245     }else{
 246       kDebug() << "tried to remove a declaration from the symbol-table that isn't there" << id.identifier().toString();
 247     }
 248   }
 249 }
 250
 251 void PersistentSymbolTable::declarations(const IndexedQualifiedIdentifier& id, uint& countTarget, const IndexedDeclaration*& declarationsTarget ) const
 252 {
 253   PersistentSymbolTableItem item;
 254   item.id = id;
 255   PersistentSymbolTableRequestItem request(item);
 256
 257   uint index = d->m_declarations.findIndex(item);
 258
 259   if(index) {
 260     const PersistentSymbolTableItem* repositoryItem = d->m_declarations.itemFromIndex(index);
 261     countTarget = repositoryItem->declarationsSize();
 262     declarationsTarget = repositoryItem->declarations();
 263   }else{
 264     countTarget = 0;
 265     declarationsTarget = 0;
 266   }
 267 }
 268
 269 void PersistentSymbolTable::addContext(const IndexedQualifiedIdentifier& id, const IndexedDUContext& context) {
 270   PersistentContextTableItem item;
 271   item.id = id;
 272   item.contextsList().append(context);
 273   PersistentContextTableRequestItem request(item);
 274
 275   uint index = d->m_contexts.findIndex(item);
 276
 277   if(index) {
 278     //Check whether the item is already in the mapped list, else copy the list into the new created item
 279     const PersistentContextTableItem* oldItem = d->m_contexts.itemFromIndex(index);
 280     for(uint a = 0; a < oldItem->contextsSize(); ++a) {
 281       if(oldItem->contexts()[a] == context)
 282         return; //Already there
 283       item.contextsList().append(oldItem->contexts()[a]);
 284     }
 285
 286     if(request.itemSize() > (1<<15))
 287       kWarning() << "too many contexts for id" << id.identifier().toString() << item.contextsSize();
 288
 289     d->m_contexts.deleteItem(index);
 290   }
 291
 292   //This inserts the changed item
 293   d->m_contexts.index(request);
 294 }
 295
 296 void PersistentSymbolTable::removeContext(const IndexedQualifiedIdentifier& id, const IndexedDUContext& context) {
 297   PersistentContextTableItem item;
 298   item.id = id;
 299   PersistentContextTableRequestItem request(item);
 300
 301   uint index = d->m_contexts.findIndex(item);
 302
 303   if(index) {
 304     //Check whether the item is already in the mapped list, else copy the list into the new created item
 305     const PersistentContextTableItem* oldItem = d->m_contexts.itemFromIndex(index);
 306     for(uint a = 0; a < oldItem->contextsSize(); ++a)
 307       if(!(oldItem->contexts()[a] == context))
 308         item.contextsList().append(oldItem->contexts()[a]);
 309
 310     d->m_contexts.deleteItem(index);
 311     Q_ASSERT(d->m_contexts.findIndex(item) == 0);
 312
 313     //This inserts the changed item
 314     if(item.contextsSize() != 0)
 315       d->m_contexts.index(request);
 316   }
 317 }
 318
 319 void PersistentSymbolTable::contexts(const IndexedQualifiedIdentifier& id, uint& countTarget, const IndexedDUContext*& contextsTarget) const {
 320   PersistentContextTableItem item;
 321   item.id = id;
 322   PersistentContextTableRequestItem request(item);
 323
 324   uint index = d->m_contexts.findIndex(item);
 325
 326   if(index) {
 327     const PersistentContextTableItem* repositoryItem = d->m_contexts.itemFromIndex(index);
 328     countTarget = repositoryItem->contextsSize();
 329     contextsTarget = repositoryItem->contexts();
 330   }else{
 331     countTarget = 0;
 332     contextsTarget = 0;
 333   }
 334 }
 335
 336 uint qHash(IndexedDeclaration decl) {
 337   return decl.hash();
 338 }
 339
 340 struct Visitor {
 341   bool operator() (const PersistentSymbolTableItem* item) {
 342     QualifiedIdentifier id(item->id.identifier());
 343     if(identifiers.contains(id))
 344       kDebug() << "identifier" << id.toString() << "appears for" << identifiers[id] << "th time";
 345
 346     ++identifiers[id];
 347
 348     for(uint a = 0; a < item->declarationsSize(); ++a) {
 349       IndexedDeclaration decl(item->declarations()[a]);
 350       if(declarations.contains(decl)) {
 351         kDebug() << "declaration found for multiple identifiers. Previous identifier:" << declarations[decl].toString() << "current identifier:" << id.toString();
 352       }else{
 353         declarations.insert(decl, id);
 354       }
 355       if(!decl.data()) {
 356         kDebug() << "Item in symbol-table is invalid:" << id.toString() << item->declarations()[a].localIndex() << IndexedTopDUContext(item->declarations()[a].topContextIndex()).url().str();
 357       }
 358     }
 359     return true;
 360   }
 361   QHash<QualifiedIdentifier, uint> identifiers;
 362   QHash<IndexedDeclaration, QualifiedIdentifier> declarations;
 363 };
 364
 365 struct ContextVisitor {
 366   bool operator() (const PersistentContextTableItem* item) {
 367     QualifiedIdentifier id(item->id.identifier());
 368     if(identifiers.contains(id))
 369       kDebug() << "identifier" << id.toString() << "appears for" << identifiers[id] << "th time";
 370
 371     ++identifiers[id];
 372
 373     for(uint a = 0; a < item->contextsSize(); ++a) {
 374       if(!item->contexts()[a].data()) {
 375         kDebug() << "Item in Context-table is invalid:" << id.toString() << item->contexts()[a].localIndex() << IndexedTopDUContext(item->contexts()[a].topContextIndex()).url().str();
 376       }
 377     }
 378     return true;
 379   }
 380   QHash<QualifiedIdentifier, uint> identifiers;
 381 };
 382
 383 void PersistentSymbolTable::selfAnalysis() {
 384   {
 385     Visitor v;
 386     kDebug() << d->m_declarations.statistics();
 387     d->m_declarations.visitAllItems(v);
 388     kDebug() << "visited" << v.identifiers.size() << "identifiers";
 389   }
 390
 391   {
 392     ContextVisitor v;
 393     kDebug() << d->m_contexts.statistics();
 394     d->m_contexts.visitAllItems(v);
 395     kDebug() << "visited" << v.identifiers.size() << "identifiers";
 396   }
 397 }
 398
 399 PersistentSymbolTable& PersistentSymbolTable::self() {
 400   static PersistentSymbolTable ret;
 401   return ret;
 402 }
 403
 404 }
 405