language/duchain/codemodel.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 "codemodel.h"
  20
  21 #include <QHash>
  22 #include <QVector>
  23
  24 #include "appendedlist.h"
  25 #include "repositories/itemrepository.h"
  26 #include "identifier.h"
  27 #include "indexedstring.h"
  28
  29 #define ifDebug(x)
  30
  31 namespace KDevelop {
  32
  33 DEFINE_LIST_MEMBER_HASH(CodeModelRepositoryItem, items, CodeModelItem)
  34
  35 class CodeModelRepositoryItem {
  36   public:
  37   CodeModelRepositoryItem() {
  38     initializeAppendedLists();
  39   }
  40   CodeModelRepositoryItem(const CodeModelRepositoryItem& rhs) : file(rhs.file) {
  41     initializeAppendedLists();
  42     copyListsFrom(rhs);
  43   }
  44
  45   ~CodeModelRepositoryItem() {
  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 file.index();
  53   }
  54
  55   unsigned short int itemSize() const {
  56     return dynamicSize();
  57   }
  58
  59   uint classSize() const {
  60     return sizeof(CodeModelRepositoryItem);
  61   }
  62
  63   IndexedString file;
  64
  65   START_APPENDED_LISTS(CodeModelRepositoryItem);
  66   APPENDED_LIST_FIRST(CodeModelRepositoryItem, CodeModelItem, items);
  67   END_APPENDED_LISTS(CodeModelRepositoryItem, items);
  68 };
  69
  70 class CodeModelRequestItem {
  71   public:
  72
  73   CodeModelRequestItem(const CodeModelRepositoryItem& 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(CodeModelRepositoryItem* item) const {
  88     item->initializeAppendedLists(false);
  89     item->file = m_item.file;
  90     item->copyListsFrom(m_item);
  91   }
  92
  93   bool equals(const CodeModelRepositoryItem* item) const {
  94     return m_item.file == item->file;
  95   }
  96
  97   const CodeModelRepositoryItem& m_item;
  98 };
  99
 100
 101 struct CodeModelPrivate {
 102   CodeModelPrivate() : m_repository("Code Model") {
 103   }
 104   //Maps declaration-ids to items
 105   ItemRepository<CodeModelRepositoryItem, CodeModelRequestItem> m_repository;
 106 };
 107
 108 CodeModel::CodeModel() : d(new CodeModelPrivate())
 109 {
 110 }
 111
 112 CodeModel::~CodeModel()
 113 {
 114   delete d;
 115 }
 116
 117 ///@todo Sorting in the items list, so searches can be faster
 118 void CodeModel::addItem(const IndexedString& file, const IndexedQualifiedIdentifier& id, CodeModelItem::Kind kind)
 119 {
 120   ifDebug( kDebug() << "addItem" << file.str() << id.identifier().toString(); )
 121
 122   if(!id.isValid())
 123     return;
 124   CodeModelRepositoryItem item;
 125   item.file = file;
 126   CodeModelRequestItem request(item);
 127
 128   uint index = d->m_repository.findIndex(item);
 129
 130   if(index) {
 131     //Check whether the item is already in the mapped list, else copy the list into the new created item
 132     const CodeModelRepositoryItem* oldItem = d->m_repository.itemFromIndex(index);
 133       ifDebug( kDebug() << "found index" << index << "count:" << oldItem->itemsSize(); )
 134     int freePlace = -1;
 135     uint itemsSize = oldItem->itemsSize();
 136     const KDevelop::CodeModelItem* items = oldItem->items();
 137
 138     for(uint a = 0; a < itemsSize; ++a) {
 139       ifDebug( kDebug() << "id at" << a << items[a].id.identifier().toString(); )
 140       if(items[a].id == id) {
 141         CodeModelRepositoryItem* editableItem = d->m_repository.dynamicItemFromIndex(index);
 142         ++const_cast<CodeModelItem*>(editableItem->items())[a].referenceCount;
 143         const_cast<CodeModelItem*>(editableItem->items())[a].kind = kind;
 144         return; //Already there
 145       }else if(freePlace == -1 && !items[a].id.isValid()) {
 146         freePlace = (int)a; //Remember an unused position where we can insert the item
 147         ifDebug( kDebug() << "found free place at" << freePlace; )
 148       }
 149     }
 150
 151     CodeModelItem newItem;
 152     newItem.referenceCount = 1;
 153     newItem.id = id;
 154     newItem.kind = kind;
 155
 156     if(freePlace != -1) {
 157       //We can insert the item at a currently unused position
 158       CodeModelRepositoryItem* editableItem = d->m_repository.dynamicItemFromIndex(index);
 159       const_cast<CodeModelItem*>(editableItem->items())[freePlace] = newItem;
 160       ifDebug( kDebug() << "using freePlace" << freePlace; )
 161       return;
 162     }
 163
 164     item.copyListsFrom(*oldItem);
 165     item.itemsList().append(newItem);
 166
 167     //Append a few additional items, so we don't need to re-create that often
 168     item.itemsList().append(CodeModelItem());
 169     item.itemsList().append(CodeModelItem());
 170     item.itemsList().append(CodeModelItem());
 171     item.itemsList().append(CodeModelItem());
 172
 173     ifDebug( kDebug() << "deleting list, and creating new with" << item.itemsSize() << "items"; )
 174     d->m_repository.deleteItem(index);
 175   }else{
 176     //We're creating a new index
 177     CodeModelItem newItem;
 178     newItem.referenceCount = 1;
 179     newItem.id = id;
 180     newItem.kind = kind;
 181     item.itemsList().append(newItem);
 182   }
 183   Q_ASSERT(!d->m_repository.findIndex(request));
 184
 185   //This inserts the changed item
 186   uint newIndex = d->m_repository.index(request);
 187   Q_UNUSED(newIndex);
 188   ifDebug( kDebug() << "new index" << newIndex; )
 189
 190   Q_ASSERT(d->m_repository.findIndex(request));
 191 }
 192
 193 void CodeModel::updateItem(const IndexedString& file, const IndexedQualifiedIdentifier& id, CodeModelItem::Kind kind)
 194 {
 195   ifDebug( kDebug() << file.str() << id.identifier().toString() << kind; )
 196
 197   if(!id.isValid())
 198     return;
 199   CodeModelRepositoryItem item;
 200   item.file = file;
 201   CodeModelRequestItem request(item);
 202
 203   uint index = d->m_repository.findIndex(item);
 204
 205   if(index) {
 206     //Check whether the item is already in the mapped list, else copy the list into the new created item
 207     const CodeModelRepositoryItem* oldItem = d->m_repository.itemFromIndex(index);
 208     uint itemsSize = oldItem->itemsSize();
 209     const KDevelop::CodeModelItem* items = oldItem->items();
 210
 211     for(uint a = 0; a < itemsSize; ++a) {
 212       if(items[a].id == id) {
 213         CodeModelRepositoryItem* editableItem = d->m_repository.dynamicItemFromIndex(index);
 214         const_cast<CodeModelItem*>(editableItem->items())[a].kind = kind;
 215         return; //Already there
 216       }
 217     }
 218   }
 219
 220   Q_ASSERT(0); //The updated item as not in the symbol table!
 221 }
 222
 223 void CodeModel::removeItem(const IndexedString& file, const IndexedQualifiedIdentifier& id)
 224 //void CodeModel::removeDeclaration(const QualifiedIdentifier& id, const IndexedDeclaration& declaration)
 225 {
 226   if(!id.isValid())
 227     return;
 228   ifDebug( kDebug() << "removeItem" << file.str() << id.identifier().toString(); )
 229   CodeModelRepositoryItem item;
 230   item.file = file;
 231   CodeModelRequestItem request(item);
 232
 233   uint index = d->m_repository.findIndex(item);
 234
 235   if(index) {
 236
 237     uint freeItemCount = 0;
 238
 239     CodeModelRepositoryItem* oldItem = d->m_repository.dynamicItemFromIndex(index);
 240     uint itemsSize = oldItem->itemsSize();
 241     KDevelop::CodeModelItem* items = const_cast<CodeModelItem*>(oldItem->items());
 242
 243     for(uint a = 0; a < itemsSize; ++a) {
 244       if(oldItem->items()[a].id == id) {
 245
 246         --items[a].referenceCount;
 247         ifDebug( kDebug() << "reduced reference-count for" << id.identifier().toString() << "to" << oldItem->items()[a].referenceCount; )
 248
 249         if(!items[a].referenceCount) {
 250           items[a].id = IndexedQualifiedIdentifier();
 251           ifDebug( kDebug() << "marking index" << a << "as free"; )
 252         }
 253       }
 254       if(!items[a].id.isValid()) {
 255         ++freeItemCount;
 256       }
 257     }
 258     if(freeItemCount == itemsSize) {
 259       ifDebug( kDebug() << "no items left, deleting"; )
 260       d->m_repository.deleteItem(index);
 261     }else if(freeItemCount > 10) {
 262         ifDebug( kDebug() << "resizing to make smaller"; )
 263
 264         for(uint a = 0; a < itemsSize; ++a)
 265           if(items[a].id.isValid())
 266             item.itemsList().append(items[a]);
 267
 268         d->m_repository.deleteItem(index);
 269         ifDebug( kDebug() << "creating new entry with" << item.itemsSize() << "entries"; )
 270         d->m_repository.index(request);
 271     }
 272   }
 273 }
 274
 275 void CodeModel::items(const IndexedString& file, uint& count, const CodeModelItem*& items) const
 276 {
 277   ifDebug( kDebug() << "items" << file.str(); )
 278
 279   CodeModelRepositoryItem item;
 280   item.file = file;
 281   CodeModelRequestItem request(item);
 282
 283   uint index = d->m_repository.findIndex(item);
 284
 285   if(index) {
 286     const CodeModelRepositoryItem* repositoryItem = d->m_repository.itemFromIndex(index);
 287     ifDebug( kDebug() << "found index" << index << repositoryItem->itemsSize(); )
 288     count = repositoryItem->itemsSize();
 289     items = repositoryItem->items();
 290   }else{
 291     ifDebug( kDebug() << "found no index"; )
 292     count = 0;
 293     items = 0;
 294   }
 295 }
 296
 297 CodeModel& CodeModel::self() {
 298   static CodeModel ret;
 299   return ret;
 300 }
 301
 302 }
 303