src/kitemviews/kfileitemmodel.cpp

   1 /*****************************************************************************
   2  *   Copyright (C) 2011 by Peter Penz <peter.penz19@gmail.com>               *
   3  *   Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com>      *
   4  *   Copyright (C) 2013 by Emmanuel Pescosta <emmanuelpescosta099@gmail.com> *
   5  *                                                                           *
   6  *   This program is free software; you can redistribute it and/or modify    *
   7  *   it under the terms of the GNU General Public License as published by    *
   8  *   the Free Software Foundation; either version 2 of the License, or       *
   9  *   (at your option) any later version.                                     *
  10  *                                                                           *
  11  *   This program is distributed in the hope that it will be useful,         *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
  14  *   GNU General Public License for more details.                            *
  15  *                                                                           *
  16  *   You should have received a copy of the GNU General Public License       *
  17  *   along with this program; if not, write to the                           *
  18  *   Free Software Foundation, Inc.,                                         *
  19  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA              *
  20  *****************************************************************************/
  21
  22 #include "kfileitemmodel.h"
  23
  24 #include <KDirModel>
  25 #include <KGlobalSettings>
  26 #include <KLocale>
  27 #include <KStringHandler>
  28 #include <KDebug>
  29
  30 #include "private/kfileitemmodelsortalgorithm.h"
  31 #include "private/kfileitemmodeldirlister.h"
  32
  33 #include <QApplication>
  34 #include <QMimeData>
  35 #include <QTimer>
  36 #include <QWidget>
  37
  38 #include <algorithm>
  39 #include <vector>
  40
  41 // #define KFILEITEMMODEL_DEBUG
  42
  43 KFileItemModel::KFileItemModel(QObject* parent) :
  44     KItemModelBase("text", parent),
  45     m_dirLister(0),
  46     m_naturalSorting(KGlobalSettings::naturalSorting()),
  47     m_sortDirsFirst(true),
  48     m_sortRole(NameRole),
  49     m_sortingProgressPercent(-1),
  50     m_roles(),
  51     m_caseSensitivity(Qt::CaseInsensitive),
  52     m_itemData(),
  53     m_items(),
  54     m_filter(),
  55     m_filteredItems(),
  56     m_requestRole(),
  57     m_maximumUpdateIntervalTimer(0),
  58     m_resortAllItemsTimer(0),
  59     m_pendingItemsToInsert(),
  60     m_groups(),
  61     m_expandedDirs(),
  62     m_urlsToExpand()
  63 {
  64     m_dirLister = new KFileItemModelDirLister(this);
  65     m_dirLister->setDelayedMimeTypes(true);
  66
  67     const QWidget* parentWidget = qobject_cast<QWidget*>(parent);
  68     if (parentWidget) {
  69         m_dirLister->setMainWindow(parentWidget->window());
  70     }
  71
  72     connect(m_dirLister, SIGNAL(started(KUrl)), this, SIGNAL(directoryLoadingStarted()));
  73     connect(m_dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  74     connect(m_dirLister, SIGNAL(completed(KUrl)), this, SLOT(slotCompleted()));
  75     connect(m_dirLister, SIGNAL(itemsAdded(KUrl,KFileItemList)), this, SLOT(slotItemsAdded(KUrl,KFileItemList)));
  76     connect(m_dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  77     connect(m_dirLister, SIGNAL(refreshItems(QList<QPair<KFileItem,KFileItem> >)), this, SLOT(slotRefreshItems(QList<QPair<KFileItem,KFileItem> >)));
  78     connect(m_dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  79     connect(m_dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  80     connect(m_dirLister, SIGNAL(infoMessage(QString)), this, SIGNAL(infoMessage(QString)));
  81     connect(m_dirLister, SIGNAL(errorMessage(QString)), this, SIGNAL(errorMessage(QString)));
  82     connect(m_dirLister, SIGNAL(redirection(KUrl,KUrl)), this, SIGNAL(directoryRedirection(KUrl,KUrl)));
  83     connect(m_dirLister, SIGNAL(urlIsFileError(KUrl)), this, SIGNAL(urlIsFileError(KUrl)));
  84
  85     // Apply default roles that should be determined
  86     resetRoles();
  87     m_requestRole[NameRole] = true;
  88     m_requestRole[IsDirRole] = true;
  89     m_requestRole[IsLinkRole] = true;
  90     m_roles.insert("text");
  91     m_roles.insert("isDir");
  92     m_roles.insert("isLink");
  93
  94     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  95     // before the completed() or canceled() signal has been emitted.
  96     m_maximumUpdateIntervalTimer = new QTimer(this);
  97     m_maximumUpdateIntervalTimer->setInterval(2000);
  98     m_maximumUpdateIntervalTimer->setSingleShot(true);
  99     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
 100
 101     // When changing the value of an item which represents the sort-role a resorting must be
 102     // triggered. Especially in combination with KFileItemModelRolesUpdater this might be done
 103     // for a lot of items within a quite small timeslot. To prevent expensive resortings the
 104     // resorting is postponed until the timer has been exceeded.
 105     m_resortAllItemsTimer = new QTimer(this);
 106     m_resortAllItemsTimer->setInterval(500);
 107     m_resortAllItemsTimer->setSingleShot(true);
 108     connect(m_resortAllItemsTimer, SIGNAL(timeout()), this, SLOT(resortAllItems()));
 109
 110     connect(KGlobalSettings::self(), SIGNAL(naturalSortingChanged()), this, SLOT(slotNaturalSortingChanged()));
 111 }
 112
 113 KFileItemModel::~KFileItemModel()
 114 {
 115     qDeleteAll(m_itemData);
 116     qDeleteAll(m_filteredItems.values());
 117     qDeleteAll(m_pendingItemsToInsert);
 118 }
 119
 120 void KFileItemModel::loadDirectory(const KUrl& url)
 121 {
 122     m_dirLister->openUrl(url);
 123 }
 124
 125 void KFileItemModel::refreshDirectory(const KUrl& url)
 126 {
 127     // Refresh all expanded directories first (Bug 295300)
 128     QHashIterator<KUrl, KUrl> expandedDirs(m_expandedDirs);
 129     while (expandedDirs.hasNext()) {
 130         expandedDirs.next();
 131         m_dirLister->openUrl(expandedDirs.value(), KDirLister::Reload);
 132     }
 133
 134     m_dirLister->openUrl(url, KDirLister::Reload);
 135 }
 136
 137 KUrl KFileItemModel::directory() const
 138 {
 139     return m_dirLister->url();
 140 }
 141
 142 void KFileItemModel::cancelDirectoryLoading()
 143 {
 144     m_dirLister->stop();
 145 }
 146
 147 int KFileItemModel::count() const
 148 {
 149     return m_itemData.count();
 150 }
 151
 152 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
 153 {
 154     if (index >= 0 && index < count()) {
 155         ItemData* data = m_itemData.at(index);
 156         if (data->values.isEmpty()) {
 157             data->values = retrieveData(data->item, data->parent);
 158         }
 159
 160         return data->values;
 161     }
 162     return QHash<QByteArray, QVariant>();
 163 }
 164
 165 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
 166 {
 167     if (index < 0 || index >= count()) {
 168         return false;
 169     }
 170
 171     QHash<QByteArray, QVariant> currentValues = data(index);
 172
 173     // Determine which roles have been changed
 174     QSet<QByteArray> changedRoles;
 175     QHashIterator<QByteArray, QVariant> it(values);
 176     while (it.hasNext()) {
 177         it.next();
 178         const QByteArray role = sharedValue(it.key());
 179         const QVariant value = it.value();
 180
 181         if (currentValues[role] != value) {
 182             currentValues[role] = value;
 183             changedRoles.insert(role);
 184         }
 185     }
 186
 187     if (changedRoles.isEmpty()) {
 188         return false;
 189     }
 190
 191     m_itemData[index]->values = currentValues;
 192     if (changedRoles.contains("text")) {
 193         KUrl url = m_itemData[index]->item.url();
 194         url.setFileName(currentValues["text"].toString());
 195         m_itemData[index]->item.setUrl(url);
 196     }
 197
 198     emitItemsChangedAndTriggerResorting(KItemRangeList() << KItemRange(index, 1), changedRoles);
 199
 200     return true;
 201 }
 202
 203 void KFileItemModel::setSortDirectoriesFirst(bool dirsFirst)
 204 {
 205     if (dirsFirst != m_sortDirsFirst) {
 206         m_sortDirsFirst = dirsFirst;
 207         resortAllItems();
 208     }
 209 }
 210
 211 bool KFileItemModel::sortDirectoriesFirst() const
 212 {
 213     return m_sortDirsFirst;
 214 }
 215
 216 void KFileItemModel::setShowHiddenFiles(bool show)
 217 {
 218     m_dirLister->setShowingDotFiles(show);
 219     m_dirLister->emitChanges();
 220     if (show) {
 221         slotCompleted();
 222     }
 223 }
 224
 225 bool KFileItemModel::showHiddenFiles() const
 226 {
 227     return m_dirLister->showingDotFiles();
 228 }
 229
 230 void KFileItemModel::setShowDirectoriesOnly(bool enabled)
 231 {
 232     m_dirLister->setDirOnlyMode(enabled);
 233 }
 234
 235 bool KFileItemModel::showDirectoriesOnly() const
 236 {
 237     return m_dirLister->dirOnlyMode();
 238 }
 239
 240 QMimeData* KFileItemModel::createMimeData(const KItemSet& indexes) const
 241 {
 242     QMimeData* data = new QMimeData();
 243
 244     // The following code has been taken from KDirModel::mimeData()
 245     // (kdelibs/kio/kio/kdirmodel.cpp)
 246     // Copyright (C) 2006 David Faure <faure@kde.org>
 247     KUrl::List urls;
 248     KUrl::List mostLocalUrls;
 249     bool canUseMostLocalUrls = true;
 250
 251     foreach (int index, indexes) {
 252         const KFileItem item = fileItem(index);
 253         if (!item.isNull()) {
 254             urls << item.targetUrl();
 255
 256             bool isLocal;
 257             mostLocalUrls << item.mostLocalUrl(isLocal);
 258             if (!isLocal) {
 259                 canUseMostLocalUrls = false;
 260             }
 261         }
 262     }
 263
 264     const bool different = canUseMostLocalUrls && mostLocalUrls != urls;
 265     urls = KDirModel::simplifiedUrlList(urls); // TODO: Check if we still need KDirModel for this in KDE 5.0
 266     if (different) {
 267         mostLocalUrls = KDirModel::simplifiedUrlList(mostLocalUrls);
 268         urls.populateMimeData(mostLocalUrls, data);
 269     } else {
 270         urls.populateMimeData(data);
 271     }
 272
 273     return data;
 274 }
 275
 276 int KFileItemModel::indexForKeyboardSearch(const QString& text, int startFromIndex) const
 277 {
 278     startFromIndex = qMax(0, startFromIndex);
 279     for (int i = startFromIndex; i < count(); ++i) {
 280         if (fileItem(i).text().startsWith(text, Qt::CaseInsensitive)) {
 281             return i;
 282         }
 283     }
 284     for (int i = 0; i < startFromIndex; ++i) {
 285         if (fileItem(i).text().startsWith(text, Qt::CaseInsensitive)) {
 286             return i;
 287         }
 288     }
 289     return -1;
 290 }
 291
 292 bool KFileItemModel::supportsDropping(int index) const
 293 {
 294     const KFileItem item = fileItem(index);
 295     return !item.isNull() && (item.isDir() || item.isDesktopFile());
 296 }
 297
 298 QString KFileItemModel::roleDescription(const QByteArray& role) const
 299 {
 300     static QHash<QByteArray, QString> description;
 301     if (description.isEmpty()) {
 302         int count = 0;
 303         const RoleInfoMap* map = rolesInfoMap(count);
 304         for (int i = 0; i < count; ++i) {
 305             description.insert(map[i].role, i18nc(map[i].roleTranslationContext, map[i].roleTranslation));
 306         }
 307     }
 308
 309     return description.value(role);
 310 }
 311
 312 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 313 {
 314     if (!m_itemData.isEmpty() && m_groups.isEmpty()) {
 315 #ifdef KFILEITEMMODEL_DEBUG
 316         QElapsedTimer timer;
 317         timer.start();
 318 #endif
 319         switch (typeForRole(sortRole())) {
 320         case NameRole:        m_groups = nameRoleGroups(); break;
 321         case SizeRole:        m_groups = sizeRoleGroups(); break;
 322         case DateRole:        m_groups = dateRoleGroups(); break;
 323         case PermissionsRole: m_groups = permissionRoleGroups(); break;
 324         case RatingRole:      m_groups = ratingRoleGroups(); break;
 325         default:              m_groups = genericStringRoleGroups(sortRole()); break;
 326         }
 327
 328 #ifdef KFILEITEMMODEL_DEBUG
 329         kDebug() << "[TIME] Calculating groups for" << count() << "items:" << timer.elapsed();
 330 #endif
 331     }
 332
 333     return m_groups;
 334 }
 335
 336 KFileItem KFileItemModel::fileItem(int index) const
 337 {
 338     if (index >= 0 && index < count()) {
 339         return m_itemData.at(index)->item;
 340     }
 341
 342     return KFileItem();
 343 }
 344
 345 KFileItem KFileItemModel::fileItem(const KUrl& url) const
 346 {
 347     const int index = m_items.value(url, -1);
 348     if (index >= 0) {
 349         return m_itemData.at(index)->item;
 350     }
 351     return KFileItem();
 352 }
 353
 354 int KFileItemModel::index(const KFileItem& item) const
 355 {
 356     if (item.isNull()) {
 357         return -1;
 358     }
 359
 360     return m_items.value(item.url(), -1);
 361 }
 362
 363 int KFileItemModel::index(const KUrl& url) const
 364 {
 365     KUrl urlToFind = url;
 366     urlToFind.adjustPath(KUrl::RemoveTrailingSlash);
 367     return m_items.value(urlToFind, -1);
 368 }
 369
 370 KFileItem KFileItemModel::rootItem() const
 371 {
 372     return m_dirLister->rootItem();
 373 }
 374
 375 void KFileItemModel::clear()
 376 {
 377     slotClear();
 378 }
 379
 380 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 381 {
 382     if (m_roles == roles) {
 383         return;
 384     }
 385     m_roles = roles;
 386
 387     if (count() > 0) {
 388         const bool supportedExpanding = m_requestRole[ExpandedParentsCountRole];
 389         const bool willSupportExpanding = roles.contains("expandedParentsCount");
 390         if (supportedExpanding && !willSupportExpanding) {
 391             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 392             // that is not 0 (and hence are part of an expanded item).
 393             removeExpandedItems();
 394         }
 395     }
 396
 397     m_groups.clear();
 398     resetRoles();
 399
 400     QSetIterator<QByteArray> it(roles);
 401     while (it.hasNext()) {
 402         const QByteArray& role = it.next();
 403         m_requestRole[typeForRole(role)] = true;
 404     }
 405
 406     if (count() > 0) {
 407         // Update m_data with the changed requested roles
 408         const int maxIndex = count() - 1;
 409         for (int i = 0; i <= maxIndex; ++i) {
 410             m_itemData[i]->values = retrieveData(m_itemData.at(i)->item, m_itemData.at(i)->parent);
 411         }
 412
 413         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 414         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 415     }
 416 }
 417
 418 QSet<QByteArray> KFileItemModel::roles() const
 419 {
 420     return m_roles;
 421 }
 422
 423 bool KFileItemModel::setExpanded(int index, bool expanded)
 424 {
 425     if (!isExpandable(index) || isExpanded(index) == expanded) {
 426         return false;
 427     }
 428
 429     QHash<QByteArray, QVariant> values;
 430     values.insert(sharedValue("isExpanded"), expanded);
 431     if (!setData(index, values)) {
 432         return false;
 433     }
 434
 435     const KFileItem item = m_itemData.at(index)->item;
 436     const KUrl url = item.url();
 437     const KUrl targetUrl = item.targetUrl();
 438     if (expanded) {
 439         m_expandedDirs.insert(targetUrl, url);
 440         m_dirLister->openUrl(url, KDirLister::Keep);
 441
 442         const KUrl::List previouslyExpandedChildren = m_itemData.at(index)->values.value("previouslyExpandedChildren").value<KUrl::List>();
 443         foreach (const KUrl& url, previouslyExpandedChildren) {
 444             m_urlsToExpand.insert(url);
 445         }
 446     } else {
 447         m_expandedDirs.remove(targetUrl);
 448         m_dirLister->stop(url);
 449
 450         const int parentLevel = expandedParentsCount(index);
 451         const int itemCount = m_itemData.count();
 452         const int firstChildIndex = index + 1;
 453
 454         KUrl::List expandedChildren;
 455
 456         int childIndex = firstChildIndex;
 457         while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
 458             ItemData* itemData = m_itemData.at(childIndex);
 459             if (itemData->values.value("isExpanded").toBool()) {
 460                 const KUrl targetUrl = itemData->item.targetUrl();
 461                 m_expandedDirs.remove(targetUrl);
 462                 expandedChildren.append(targetUrl);
 463             }
 464             ++childIndex;
 465         }
 466         const int childrenCount = childIndex - firstChildIndex;
 467
 468         removeFilteredChildren(KItemRangeList() << KItemRange(index, 1 + childrenCount));
 469         removeItems(KItemRangeList() << KItemRange(firstChildIndex, childrenCount), DeleteItemData);
 470
 471         m_itemData.at(index)->values.insert("previouslyExpandedChildren", expandedChildren);
 472     }
 473
 474     return true;
 475 }
 476
 477 bool KFileItemModel::isExpanded(int index) const
 478 {
 479     if (index >= 0 && index < count()) {
 480         return m_itemData.at(index)->values.value("isExpanded").toBool();
 481     }
 482     return false;
 483 }
 484
 485 bool KFileItemModel::isExpandable(int index) const
 486 {
 487     if (index >= 0 && index < count()) {
 488         // Call data (instead of accessing m_itemData directly)
 489         // to ensure that the value is initialized.
 490         return data(index).value("isExpandable").toBool();
 491     }
 492     return false;
 493 }
 494
 495 int KFileItemModel::expandedParentsCount(int index) const
 496 {
 497     if (index >= 0 && index < count()) {
 498         return expandedParentsCount(m_itemData.at(index));
 499     }
 500     return 0;
 501 }
 502
 503 QSet<KUrl> KFileItemModel::expandedDirectories() const
 504 {
 505     return m_expandedDirs.values().toSet();
 506 }
 507
 508 void KFileItemModel::restoreExpandedDirectories(const QSet<KUrl>& urls)
 509 {
 510     m_urlsToExpand = urls;
 511 }
 512
 513 void KFileItemModel::expandParentDirectories(const KUrl& url)
 514 {
 515     const int pos = m_dirLister->url().path().length();
 516
 517     // Assure that each sub-path of the URL that should be
 518     // expanded is added to m_urlsToExpand. KDirLister
 519     // does not care whether the parent-URL has already been
 520     // expanded.
 521     KUrl urlToExpand = m_dirLister->url();
 522     const QStringList subDirs = url.path().mid(pos).split(QDir::separator());
 523     for (int i = 0; i < subDirs.count() - 1; ++i) {
 524         urlToExpand.addPath(subDirs.at(i));
 525         m_urlsToExpand.insert(urlToExpand);
 526     }
 527
 528     // KDirLister::open() must called at least once to trigger an initial
 529     // loading. The pending URLs that must be restored are handled
 530     // in slotCompleted().
 531     QSetIterator<KUrl> it2(m_urlsToExpand);
 532     while (it2.hasNext()) {
 533         const int idx = index(it2.next());
 534         if (idx >= 0 && !isExpanded(idx)) {
 535             setExpanded(idx, true);
 536             break;
 537         }
 538     }
 539 }
 540
 541 void KFileItemModel::setNameFilter(const QString& nameFilter)
 542 {
 543     if (m_filter.pattern() != nameFilter) {
 544         dispatchPendingItemsToInsert();
 545         m_filter.setPattern(nameFilter);
 546         applyFilters();
 547     }
 548 }
 549
 550 QString KFileItemModel::nameFilter() const
 551 {
 552     return m_filter.pattern();
 553 }
 554
 555 void KFileItemModel::setMimeTypeFilters(const QStringList& filters)
 556 {
 557     if (m_filter.mimeTypes() != filters) {
 558         dispatchPendingItemsToInsert();
 559         m_filter.setMimeTypes(filters);
 560         applyFilters();
 561     }
 562 }
 563
 564 QStringList KFileItemModel::mimeTypeFilters() const
 565 {
 566     return m_filter.mimeTypes();
 567 }
 568
 569
 570 void KFileItemModel::applyFilters()
 571 {
 572     // Check which shown items from m_itemData must get
 573     // hidden and hence moved to m_filteredItems.
 574     QVector<int> newFilteredIndexes;
 575
 576     const int itemCount = m_itemData.count();
 577     for (int index = 0; index < itemCount; ++index) {
 578         ItemData* itemData = m_itemData.at(index);
 579
 580         // Only filter non-expanded items as child items may never
 581         // exist without a parent item
 582         if (!itemData->values.value("isExpanded").toBool()) {
 583             const KFileItem item = itemData->item;
 584             if (!m_filter.matches(item)) {
 585                 newFilteredIndexes.append(index);
 586                 m_filteredItems.insert(item, itemData);
 587             }
 588         }
 589     }
 590
 591     const KItemRangeList removedRanges = KItemRangeList::fromSortedContainer(newFilteredIndexes);
 592     removeItems(removedRanges, KeepItemData);
 593
 594     // Check which hidden items from m_filteredItems should
 595     // get visible again and hence removed from m_filteredItems.
 596     QList<ItemData*> newVisibleItems;
 597
 598     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
 599     while (it != m_filteredItems.end()) {
 600         if (m_filter.matches(it.key())) {
 601             newVisibleItems.append(it.value());
 602             it = m_filteredItems.erase(it);
 603         } else {
 604             ++it;
 605         }
 606     }
 607
 608     insertItems(newVisibleItems);
 609 }
 610
 611 void KFileItemModel::removeFilteredChildren(const KItemRangeList& itemRanges)
 612 {
 613     if (m_filteredItems.isEmpty() || !m_requestRole[ExpandedParentsCountRole]) {
 614         // There are either no filtered items, or it is not possible to expand
 615         // folders -> there cannot be any filtered children.
 616         return;
 617     }
 618
 619     QSet<ItemData*> parents;
 620     foreach (const KItemRange& range, itemRanges) {
 621         for (int index = range.index; index < range.index + range.count; ++index) {
 622             parents.insert(m_itemData.at(index));
 623         }
 624     }
 625
 626     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
 627     while (it != m_filteredItems.end()) {
 628         if (parents.contains(it.value()->parent)) {
 629             delete it.value();
 630             it = m_filteredItems.erase(it);
 631         } else {
 632             ++it;
 633         }
 634     }
 635 }
 636
 637 QList<KFileItemModel::RoleInfo> KFileItemModel::rolesInformation()
 638 {
 639     static QList<RoleInfo> rolesInfo;
 640     if (rolesInfo.isEmpty()) {
 641         int count = 0;
 642         const RoleInfoMap* map = rolesInfoMap(count);
 643         for (int i = 0; i < count; ++i) {
 644             if (map[i].roleType != NoRole) {
 645                 RoleInfo info;
 646                 info.role = map[i].role;
 647                 info.translation = i18nc(map[i].roleTranslationContext, map[i].roleTranslation);
 648                 if (map[i].groupTranslation) {
 649                     info.group = i18nc(map[i].groupTranslationContext, map[i].groupTranslation);
 650                 } else {
 651                     // For top level roles, groupTranslation is 0. We must make sure that
 652                     // info.group is an empty string then because the code that generates
 653                     // menus tries to put the actions into sub menus otherwise.
 654                     info.group = QString();
 655                 }
 656                 info.requiresNepomuk = map[i].requiresNepomuk;
 657                 info.requiresIndexer = map[i].requiresIndexer;
 658                 rolesInfo.append(info);
 659             }
 660         }
 661     }
 662
 663     return rolesInfo;
 664 }
 665
 666 void KFileItemModel::onGroupedSortingChanged(bool current)
 667 {
 668     Q_UNUSED(current);
 669     m_groups.clear();
 670 }
 671
 672 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 673 {
 674     Q_UNUSED(previous);
 675     m_sortRole = typeForRole(current);
 676
 677     if (!m_requestRole[m_sortRole]) {
 678         QSet<QByteArray> newRoles = m_roles;
 679         newRoles << current;
 680         setRoles(newRoles);
 681     }
 682
 683     resortAllItems();
 684 }
 685
 686 void KFileItemModel::onSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous)
 687 {
 688     Q_UNUSED(current);
 689     Q_UNUSED(previous);
 690     resortAllItems();
 691 }
 692
 693 void KFileItemModel::resortAllItems()
 694 {
 695     m_resortAllItemsTimer->stop();
 696
 697     const int itemCount = count();
 698     if (itemCount <= 0) {
 699         return;
 700     }
 701
 702 #ifdef KFILEITEMMODEL_DEBUG
 703     QElapsedTimer timer;
 704     timer.start();
 705     kDebug() << "===========================================================";
 706     kDebug() << "Resorting" << itemCount << "items";
 707 #endif
 708
 709     // Remember the order of the current URLs so
 710     // that it can be determined which indexes have
 711     // been moved because of the resorting.
 712     QList<KUrl> oldUrls;
 713     oldUrls.reserve(itemCount);
 714     foreach (const ItemData* itemData, m_itemData) {
 715         oldUrls.append(itemData->item.url());
 716     }
 717
 718     m_items.clear();
 719
 720     // Resort the items
 721     sort(m_itemData.begin(), m_itemData.end());
 722     for (int i = 0; i < itemCount; ++i) {
 723         m_items.insert(m_itemData.at(i)->item.url(), i);
 724     }
 725
 726     // Determine the first index that has been moved.
 727     int firstMovedIndex = 0;
 728     while (firstMovedIndex < itemCount
 729            && firstMovedIndex == m_items.value(oldUrls.at(firstMovedIndex))) {
 730         ++firstMovedIndex;
 731     }
 732
 733     const bool itemsHaveMoved = firstMovedIndex < itemCount;
 734     if (itemsHaveMoved) {
 735         m_groups.clear();
 736
 737         int lastMovedIndex = itemCount - 1;
 738         while (lastMovedIndex > firstMovedIndex
 739                && lastMovedIndex == m_items.value(oldUrls.at(lastMovedIndex))) {
 740             --lastMovedIndex;
 741         }
 742
 743         Q_ASSERT(firstMovedIndex <= lastMovedIndex);
 744
 745         // Create a list movedToIndexes, which has the property that
 746         // movedToIndexes[i] is the new index of the item with the old index
 747         // firstMovedIndex + i.
 748         const int movedItemsCount = lastMovedIndex - firstMovedIndex + 1;
 749         QList<int> movedToIndexes;
 750         movedToIndexes.reserve(movedItemsCount);
 751         for (int i = firstMovedIndex; i <= lastMovedIndex; ++i) {
 752             const int newIndex = m_items.value(oldUrls.at(i));
 753             movedToIndexes.append(newIndex);
 754         }
 755
 756         emit itemsMoved(KItemRange(firstMovedIndex, movedItemsCount), movedToIndexes);
 757     } else if (groupedSorting()) {
 758         // The groups might have changed even if the order of the items has not.
 759         const QList<QPair<int, QVariant> > oldGroups = m_groups;
 760         m_groups.clear();
 761         if (groups() != oldGroups) {
 762             emit groupsChanged();
 763         }
 764     }
 765
 766 #ifdef KFILEITEMMODEL_DEBUG
 767     kDebug() << "[TIME] Resorting of" << itemCount << "items:" << timer.elapsed();
 768 #endif
 769 }
 770
 771 void KFileItemModel::slotCompleted()
 772 {
 773     dispatchPendingItemsToInsert();
 774
 775     if (!m_urlsToExpand.isEmpty()) {
 776         // Try to find a URL that can be expanded.
 777         // Note that the parent folder must be expanded before any of its subfolders become visible.
 778         // Therefore, some URLs in m_restoredExpandedUrls might not be visible yet
 779         // -> we expand the first visible URL we find in m_restoredExpandedUrls.
 780         foreach (const KUrl& url, m_urlsToExpand) {
 781             const int index = m_items.value(url, -1);
 782             if (index >= 0) {
 783                 m_urlsToExpand.remove(url);
 784                 if (setExpanded(index, true)) {
 785                     // The dir lister has been triggered. This slot will be called
 786                     // again after the directory has been expanded.
 787                     return;
 788                 }
 789             }
 790         }
 791
 792         // None of the URLs in m_restoredExpandedUrls could be found in the model. This can happen
 793         // if these URLs have been deleted in the meantime.
 794         m_urlsToExpand.clear();
 795     }
 796
 797     emit directoryLoadingCompleted();
 798 }
 799
 800 void KFileItemModel::slotCanceled()
 801 {
 802     m_maximumUpdateIntervalTimer->stop();
 803     dispatchPendingItemsToInsert();
 804
 805     emit directoryLoadingCanceled();
 806 }
 807
 808 void KFileItemModel::slotItemsAdded(const KUrl& directoryUrl, const KFileItemList& items)
 809 {
 810     Q_ASSERT(!items.isEmpty());
 811
 812     KUrl parentUrl;
 813     if (m_expandedDirs.contains(directoryUrl)) {
 814         parentUrl = m_expandedDirs.value(directoryUrl);
 815     } else {
 816         parentUrl = directoryUrl;
 817         parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
 818     }
 819
 820     if (m_requestRole[ExpandedParentsCountRole]) {
 821         KFileItem item = items.first();
 822
 823         // If the expanding of items is enabled, the call
 824         // dirLister->openUrl(url, KDirLister::Keep) in KFileItemModel::setExpanded()
 825         // might result in emitting the same items twice due to the Keep-parameter.
 826         // This case happens if an item gets expanded, collapsed and expanded again
 827         // before the items could be loaded for the first expansion.
 828         const int index = m_items.value(item.url(), -1);
 829         if (index >= 0) {
 830             // The items are already part of the model.
 831             return;
 832         }
 833
 834         if (directoryUrl != directory()) {
 835             // To be able to compare whether the new items may be inserted as children
 836             // of a parent item the pending items must be added to the model first.
 837             dispatchPendingItemsToInsert();
 838         }
 839
 840         // KDirLister keeps the children of items that got expanded once even if
 841         // they got collapsed again with KFileItemModel::setExpanded(false). So it must be
 842         // checked whether the parent for new items is still expanded.
 843         const int parentIndex = m_items.value(parentUrl, -1);
 844         if (parentIndex >= 0 && !m_itemData[parentIndex]->values.value("isExpanded").toBool()) {
 845             // The parent is not expanded.
 846             return;
 847         }
 848     }
 849
 850     QList<ItemData*> itemDataList = createItemDataList(parentUrl, items);
 851
 852     if (!m_filter.hasSetFilters()) {
 853         m_pendingItemsToInsert.append(itemDataList);
 854     } else {
 855         // The name or type filter is active. Hide filtered items
 856         // before inserting them into the model and remember
 857         // the filtered items in m_filteredItems.
 858         foreach (ItemData* itemData, itemDataList) {
 859             if (m_filter.matches(itemData->item)) {
 860                 m_pendingItemsToInsert.append(itemData);
 861             } else {
 862                 m_filteredItems.insert(itemData->item, itemData);
 863             }
 864         }
 865     }
 866
 867     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 868         // Assure that items get dispatched if no completed() or canceled() signal is
 869         // emitted during the maximum update interval.
 870         m_maximumUpdateIntervalTimer->start();
 871     }
 872 }
 873
 874 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 875 {
 876     dispatchPendingItemsToInsert();
 877
 878     QVector<int> indexesToRemove;
 879     indexesToRemove.reserve(items.count());
 880
 881     foreach (const KFileItem& item, items) {
 882         const KUrl url = item.url();
 883         const int index = m_items.value(url, -1);
 884         if (index >= 0) {
 885             indexesToRemove.append(index);
 886         } else {
 887             // Probably the item has been filtered.
 888             QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.find(item);
 889             if (it != m_filteredItems.end()) {
 890                 delete it.value();
 891                 m_filteredItems.erase(it);
 892             }
 893         }
 894     }
 895
 896     std::sort(indexesToRemove.begin(), indexesToRemove.end());
 897
 898     if (m_requestRole[ExpandedParentsCountRole] && !m_expandedDirs.isEmpty()) {
 899         // Assure that removing a parent item also results in removing all children
 900         QVector<int> indexesToRemoveWithChildren;
 901         indexesToRemoveWithChildren.reserve(m_items.count());
 902
 903         const int itemCount = m_itemData.count();
 904         foreach (int index, indexesToRemove) {
 905             indexesToRemoveWithChildren.append(index);
 906
 907             const int parentLevel = expandedParentsCount(index);
 908             int childIndex = index + 1;
 909             while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
 910                 indexesToRemoveWithChildren.append(childIndex);
 911                 ++childIndex;
 912             }
 913         }
 914
 915         indexesToRemove = indexesToRemoveWithChildren;
 916     }
 917
 918     const KItemRangeList itemRanges = KItemRangeList::fromSortedContainer(indexesToRemove);
 919     removeFilteredChildren(itemRanges);
 920     removeItems(itemRanges, DeleteItemData);
 921 }
 922
 923 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 924 {
 925     Q_ASSERT(!items.isEmpty());
 926 #ifdef KFILEITEMMODEL_DEBUG
 927     kDebug() << "Refreshing" << items.count() << "items";
 928 #endif
 929
 930     // Get the indexes of all items that have been refreshed
 931     QList<int> indexes;
 932     indexes.reserve(items.count());
 933
 934     QSet<QByteArray> changedRoles;
 935
 936     QListIterator<QPair<KFileItem, KFileItem> > it(items);
 937     while (it.hasNext()) {
 938         const QPair<KFileItem, KFileItem>& itemPair = it.next();
 939         const KFileItem& oldItem = itemPair.first;
 940         const KFileItem& newItem = itemPair.second;
 941         const int index = m_items.value(oldItem.url(), -1);
 942         if (index >= 0) {
 943             m_itemData[index]->item = newItem;
 944
 945             // Keep old values as long as possible if they could not retrieved synchronously yet.
 946             // The update of the values will be done asynchronously by KFileItemModelRolesUpdater.
 947             QHashIterator<QByteArray, QVariant> it(retrieveData(newItem, m_itemData.at(index)->parent));
 948             QHash<QByteArray, QVariant>& values = m_itemData[index]->values;
 949             while (it.hasNext()) {
 950                 it.next();
 951                 const QByteArray& role = it.key();
 952                 if (values.value(role) != it.value()) {
 953                     values.insert(role, it.value());
 954                     changedRoles.insert(role);
 955                 }
 956             }
 957
 958             m_items.remove(oldItem.url());
 959             m_items.insert(newItem.url(), index);
 960             indexes.append(index);
 961         }
 962     }
 963
 964     // If the changed items have been created recently, they might not be in m_items yet.
 965     // In that case, the list 'indexes' might be empty.
 966     if (indexes.isEmpty()) {
 967         return;
 968     }
 969
 970     // Extract the item-ranges out of the changed indexes
 971     qSort(indexes);
 972     const KItemRangeList itemRangeList = KItemRangeList::fromSortedContainer(indexes);
 973     emitItemsChangedAndTriggerResorting(itemRangeList, changedRoles);
 974 }
 975
 976 void KFileItemModel::slotClear()
 977 {
 978 #ifdef KFILEITEMMODEL_DEBUG
 979     kDebug() << "Clearing all items";
 980 #endif
 981
 982     qDeleteAll(m_filteredItems.values());
 983     m_filteredItems.clear();
 984     m_groups.clear();
 985
 986     m_maximumUpdateIntervalTimer->stop();
 987     m_resortAllItemsTimer->stop();
 988
 989     qDeleteAll(m_pendingItemsToInsert);
 990     m_pendingItemsToInsert.clear();
 991
 992     const int removedCount = m_itemData.count();
 993     if (removedCount > 0) {
 994         qDeleteAll(m_itemData);
 995         m_itemData.clear();
 996         m_items.clear();
 997         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
 998     }
 999
1000     m_expandedDirs.clear();
1001 }
1002
1003 void KFileItemModel::slotClear(const KUrl& url)
1004 {
1005     Q_UNUSED(url);
1006 }
1007
1008 void KFileItemModel::slotNaturalSortingChanged()
1009 {
1010     m_naturalSorting = KGlobalSettings::naturalSorting();
1011     resortAllItems();
1012 }
1013
1014 void KFileItemModel::dispatchPendingItemsToInsert()
1015 {
1016     if (!m_pendingItemsToInsert.isEmpty()) {
1017         insertItems(m_pendingItemsToInsert);
1018         m_pendingItemsToInsert.clear();
1019     }
1020 }
1021
1022 void KFileItemModel::insertItems(QList<ItemData*>& newItems)
1023 {
1024     if (newItems.isEmpty()) {
1025         return;
1026     }
1027
1028 #ifdef KFILEITEMMODEL_DEBUG
1029     QElapsedTimer timer;
1030     timer.start();
1031     kDebug() << "===========================================================";
1032     kDebug() << "Inserting" << newItems.count() << "items";
1033 #endif
1034
1035     m_groups.clear();
1036
1037     if (m_sortRole == NameRole && m_naturalSorting) {
1038         // Natural sorting of items can be very slow. However, it becomes much
1039         // faster if the input sequence is already mostly sorted. Therefore, we
1040         // first sort 'newItems' according to the QStrings returned by
1041         // KFileItem::text() using QString::operator<(), which is quite fast.
1042         parallelMergeSort(newItems.begin(), newItems.end(), nameLessThan, QThread::idealThreadCount());
1043     }
1044
1045     sort(newItems.begin(), newItems.end());
1046
1047 #ifdef KFILEITEMMODEL_DEBUG
1048     kDebug() << "[TIME] Sorting:" << timer.elapsed();
1049 #endif
1050
1051     KItemRangeList itemRanges;
1052     const int existingItemCount = m_itemData.count();
1053     const int newItemCount = newItems.count();
1054     const int totalItemCount = existingItemCount + newItemCount;
1055
1056     if (existingItemCount == 0) {
1057         // Optimization for the common special case that there are no
1058         // items in the model yet. Happens, e.g., when entering a folder.
1059         m_itemData = newItems;
1060         itemRanges << KItemRange(0, newItemCount);
1061     } else {
1062         m_itemData.reserve(totalItemCount);
1063         for (int i = existingItemCount; i < totalItemCount; ++i) {
1064             m_itemData.append(0);
1065         }
1066
1067         // We build the new list m_items in reverse order to minimize
1068         // the number of moves and guarantee O(N) complexity.
1069         int targetIndex = totalItemCount - 1;
1070         int sourceIndexExistingItems = existingItemCount - 1;
1071         int sourceIndexNewItems = newItemCount - 1;
1072
1073         int rangeCount = 0;
1074
1075         while (sourceIndexNewItems >= 0) {
1076             ItemData* newItem = newItems.at(sourceIndexNewItems);
1077             if (sourceIndexExistingItems >= 0 && lessThan(newItem, m_itemData.at(sourceIndexExistingItems))) {
1078                 // Move an existing item to its new position. If any new items
1079                 // are behind it, push the item range to itemRanges.
1080                 if (rangeCount > 0) {
1081                     itemRanges << KItemRange(sourceIndexExistingItems + 1, rangeCount);
1082                     rangeCount = 0;
1083                 }
1084
1085                 m_itemData[targetIndex] = m_itemData.at(sourceIndexExistingItems);
1086                 --sourceIndexExistingItems;
1087             } else {
1088                 // Insert a new item into the list.
1089                 ++rangeCount;
1090                 m_itemData[targetIndex] = newItem;
1091                 --sourceIndexNewItems;
1092             }
1093             --targetIndex;
1094         }
1095
1096         // Push the final item range to itemRanges.
1097         if (rangeCount > 0) {
1098             itemRanges << KItemRange(sourceIndexExistingItems + 1, rangeCount);
1099         }
1100
1101         // Note that itemRanges is still sorted in reverse order.
1102         std::reverse(itemRanges.begin(), itemRanges.end());
1103     }
1104
1105     // The indexes starting from the first inserted item must be adjusted.
1106     m_items.reserve(totalItemCount);
1107     for (int i = itemRanges.front().index; i < totalItemCount; ++i) {
1108         m_items.insert(m_itemData.at(i)->item.url(), i);
1109     }
1110
1111     emit itemsInserted(itemRanges);
1112
1113 #ifdef KFILEITEMMODEL_DEBUG
1114     kDebug() << "[TIME] Inserting of" << newItems.count() << "items:" << timer.elapsed();
1115 #endif
1116 }
1117
1118 void KFileItemModel::removeItems(const KItemRangeList& itemRanges, RemoveItemsBehavior behavior)
1119 {
1120     if (itemRanges.isEmpty()) {
1121         return;
1122     }
1123
1124     m_groups.clear();
1125
1126     // Step 1: Remove the items from the hash m_items, and free the ItemData.
1127     int removedItemsCount = 0;
1128     foreach (const KItemRange& range, itemRanges) {
1129         removedItemsCount += range.count;
1130
1131         for (int index = range.index; index < range.index + range.count; ++index) {
1132             const KUrl url = m_itemData.at(index)->item.url();
1133
1134             // Prevent repeated expensive rehashing by using QHash::erase(),
1135             // rather than QHash::remove().
1136             QHash<KUrl, int>::iterator it = m_items.find(url);
1137             m_items.erase(it);
1138
1139             if (behavior == DeleteItemData) {
1140                 delete m_itemData.at(index);
1141             }
1142
1143             m_itemData[index] = 0;
1144         }
1145     }
1146
1147     // Step 2: Remove the ItemData pointers from the list m_itemData.
1148     int target = itemRanges.at(0).index;
1149     int source = itemRanges.at(0).index + itemRanges.at(0).count;
1150     int nextRange = 1;
1151
1152     const int oldItemDataCount = m_itemData.count();
1153     while (source < oldItemDataCount) {
1154         m_itemData[target] = m_itemData[source];
1155         ++target;
1156         ++source;
1157
1158         if (nextRange < itemRanges.count() && source == itemRanges.at(nextRange).index) {
1159             // Skip the items in the next removed range.
1160             source += itemRanges.at(nextRange).count;
1161             ++nextRange;
1162         }
1163     }
1164
1165     m_itemData.erase(m_itemData.end() - removedItemsCount, m_itemData.end());
1166
1167     // Step 3: Adjust indexes in the hash m_items, starting from the
1168     //         index of the first removed item.
1169     const int newItemDataCount = m_itemData.count();
1170     for (int i = itemRanges.front().index; i < newItemDataCount; ++i) {
1171         m_items.insert(m_itemData.at(i)->item.url(), i);
1172     }
1173
1174     emit itemsRemoved(itemRanges);
1175 }
1176
1177 QList<KFileItemModel::ItemData*> KFileItemModel::createItemDataList(const KUrl& parentUrl, const KFileItemList& items) const
1178 {
1179     if (m_sortRole == TypeRole) {
1180         // Try to resolve the MIME-types synchronously to prevent a reordering of
1181         // the items when sorting by type (per default MIME-types are resolved
1182         // asynchronously by KFileItemModelRolesUpdater).
1183         determineMimeTypes(items, 200);
1184     }
1185
1186     const int parentIndex = m_items.value(parentUrl, -1);
1187     ItemData* parentItem = parentIndex < 0 ? 0 : m_itemData.at(parentIndex);
1188
1189     QList<ItemData*> itemDataList;
1190     itemDataList.reserve(items.count());
1191
1192     foreach (const KFileItem& item, items) {
1193         ItemData* itemData = new ItemData();
1194         itemData->item = item;
1195         itemData->parent = parentItem;
1196         itemDataList.append(itemData);
1197     }
1198
1199     switch (m_sortRole) {
1200     case PermissionsRole:
1201     case OwnerRole:
1202     case GroupRole:
1203     case DestinationRole:
1204     case PathRole:
1205         // These roles can be determined with retrieveData, and they have to be stored
1206         // in the QHash "values" for the sorting.
1207         foreach (ItemData* itemData, itemDataList) {
1208             itemData->values = retrieveData(itemData->item, parentItem);
1209         }
1210         break;
1211
1212     case TypeRole:
1213         // At least store the data including the file type for items with known MIME type.
1214         foreach (ItemData* itemData, itemDataList) {
1215             const KFileItem item = itemData->item;
1216             if (item.isDir() || item.isMimeTypeKnown()) {
1217                 itemData->values = retrieveData(itemData->item, parentItem);
1218             }
1219         }
1220         break;
1221
1222     default:
1223         // The other roles are either resolved by KFileItemModelRolesUpdater
1224         // (this includes the SizeRole for directories), or they do not need
1225         // to be stored in the QHash "values" for sorting because the data can
1226         // be retrieved directly from the KFileItem (NameRole, SiezRole for files,
1227         // DateRole).
1228         break;
1229     }
1230
1231     return itemDataList;
1232 }
1233
1234 int KFileItemModel::expandedParentsCount(const ItemData* data)
1235 {
1236     // The hash 'values' is only guaranteed to contain the key "expandedParentsCount"
1237     // if the corresponding item is expanded, and it is not a top-level item.
1238     const ItemData* parent = data->parent;
1239     if (parent) {
1240         if (parent->parent) {
1241             Q_ASSERT(parent->values.contains("expandedParentsCount"));
1242             return parent->values.value("expandedParentsCount").toInt() + 1;
1243         } else {
1244             return 1;
1245         }
1246     } else {
1247         return 0;
1248     }
1249 }
1250
1251 void KFileItemModel::removeExpandedItems()
1252 {
1253     QVector<int> indexesToRemove;
1254
1255     const int maxIndex = m_itemData.count() - 1;
1256     for (int i = 0; i <= maxIndex; ++i) {
1257         const ItemData* itemData = m_itemData.at(i);
1258         if (itemData->parent) {
1259             indexesToRemove.append(i);
1260         }
1261     }
1262
1263     removeItems(KItemRangeList::fromSortedContainer(indexesToRemove), DeleteItemData);
1264     m_expandedDirs.clear();
1265
1266     // Also remove all filtered items which have a parent.
1267     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
1268     const QHash<KFileItem, ItemData*>::iterator end = m_filteredItems.end();
1269
1270     while (it != end) {
1271         if (it.value()->parent) {
1272             delete it.value();
1273             it = m_filteredItems.erase(it);
1274         } else {
1275             ++it;
1276         }
1277     }
1278 }
1279
1280 void KFileItemModel::emitItemsChangedAndTriggerResorting(const KItemRangeList& itemRanges, const QSet<QByteArray>& changedRoles)
1281 {
1282     emit itemsChanged(itemRanges, changedRoles);
1283
1284     // Trigger a resorting if necessary. Note that this can happen even if the sort
1285     // role has not changed at all because the file name can be used as a fallback.
1286     if (changedRoles.contains(sortRole()) || changedRoles.contains(roleForType(NameRole))) {
1287         foreach (const KItemRange& range, itemRanges) {
1288             bool needsResorting = false;
1289
1290             const int first = range.index;
1291             const int last = range.index + range.count - 1;
1292
1293             // Resorting the model is necessary if
1294             // (a)  The first item in the range is "lessThan" its predecessor,
1295             // (b)  the successor of the last item is "lessThan" the last item, or
1296             // (c)  the internal order of the items in the range is incorrect.
1297             if (first > 0
1298                 && lessThan(m_itemData.at(first), m_itemData.at(first - 1))) {
1299                 needsResorting = true;
1300             } else if (last < count() - 1
1301                 && lessThan(m_itemData.at(last + 1), m_itemData.at(last))) {
1302                 needsResorting = true;
1303             } else {
1304                 for (int index = first; index < last; ++index) {
1305                     if (lessThan(m_itemData.at(index + 1), m_itemData.at(index))) {
1306                         needsResorting = true;
1307                         break;
1308                     }
1309                 }
1310             }
1311
1312             if (needsResorting) {
1313                 m_resortAllItemsTimer->start();
1314                 return;
1315             }
1316         }
1317     }
1318
1319     if (groupedSorting() && changedRoles.contains(sortRole())) {
1320         // The position is still correct, but the groups might have changed
1321         // if the changed item is either the first or the last item in a
1322         // group.
1323         // In principle, we could try to find out if the item really is the
1324         // first or last one in its group and then update the groups
1325         // (possibly with a delayed timer to make sure that we don't
1326         // re-calculate the groups very often if items are updated one by
1327         // one), but starting m_resortAllItemsTimer is easier.
1328         m_resortAllItemsTimer->start();
1329     }
1330 }
1331
1332 void KFileItemModel::resetRoles()
1333 {
1334     for (int i = 0; i < RolesCount; ++i) {
1335         m_requestRole[i] = false;
1336     }
1337 }
1338
1339 KFileItemModel::RoleType KFileItemModel::typeForRole(const QByteArray& role) const
1340 {
1341     static QHash<QByteArray, RoleType> roles;
1342     if (roles.isEmpty()) {
1343         // Insert user visible roles that can be accessed with
1344         // KFileItemModel::roleInformation()
1345         int count = 0;
1346         const RoleInfoMap* map = rolesInfoMap(count);
1347         for (int i = 0; i < count; ++i) {
1348             roles.insert(map[i].role, map[i].roleType);
1349         }
1350
1351         // Insert internal roles (take care to synchronize the implementation
1352         // with KFileItemModel::roleForType() in case if a change is done).
1353         roles.insert("isDir", IsDirRole);
1354         roles.insert("isLink", IsLinkRole);
1355         roles.insert("isExpanded", IsExpandedRole);
1356         roles.insert("isExpandable", IsExpandableRole);
1357         roles.insert("expandedParentsCount", ExpandedParentsCountRole);
1358
1359         Q_ASSERT(roles.count() == RolesCount);
1360     }
1361
1362     return roles.value(role, NoRole);
1363 }
1364
1365 QByteArray KFileItemModel::roleForType(RoleType roleType) const
1366 {
1367     static QHash<RoleType, QByteArray> roles;
1368     if (roles.isEmpty()) {
1369         // Insert user visible roles that can be accessed with
1370         // KFileItemModel::roleInformation()
1371         int count = 0;
1372         const RoleInfoMap* map = rolesInfoMap(count);
1373         for (int i = 0; i < count; ++i) {
1374             roles.insert(map[i].roleType, map[i].role);
1375         }
1376
1377         // Insert internal roles (take care to synchronize the implementation
1378         // with KFileItemModel::typeForRole() in case if a change is done).
1379         roles.insert(IsDirRole, "isDir");
1380         roles.insert(IsLinkRole, "isLink");
1381         roles.insert(IsExpandedRole, "isExpanded");
1382         roles.insert(IsExpandableRole, "isExpandable");
1383         roles.insert(ExpandedParentsCountRole, "expandedParentsCount");
1384
1385         Q_ASSERT(roles.count() == RolesCount);
1386     };
1387
1388     return roles.value(roleType);
1389 }
1390
1391 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item, const ItemData* parent) const
1392 {
1393     // It is important to insert only roles that are fast to retrieve. E.g.
1394     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
1395     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
1396     QHash<QByteArray, QVariant> data;
1397     data.insert(sharedValue("url"), item.url());
1398
1399     const bool isDir = item.isDir();
1400     if (m_requestRole[IsDirRole] && isDir) {
1401         data.insert(sharedValue("isDir"), true);
1402     }
1403
1404     if (m_requestRole[IsLinkRole] && item.isLink()) {
1405         data.insert(sharedValue("isLink"), true);
1406     }
1407
1408     if (m_requestRole[NameRole]) {
1409         data.insert(sharedValue("text"), item.text());
1410     }
1411
1412     if (m_requestRole[SizeRole] && !isDir) {
1413         data.insert(sharedValue("size"), item.size());
1414     }
1415
1416     if (m_requestRole[DateRole]) {
1417         // Don't use KFileItem::timeString() as this is too expensive when
1418         // having several thousands of items. Instead the formatting of the
1419         // date-time will be done on-demand by the view when the date will be shown.
1420         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
1421         data.insert(sharedValue("date"), dateTime.dateTime());
1422     }
1423
1424     if (m_requestRole[PermissionsRole]) {
1425         data.insert(sharedValue("permissions"), item.permissionsString());
1426     }
1427
1428     if (m_requestRole[OwnerRole]) {
1429         data.insert(sharedValue("owner"), item.user());
1430     }
1431
1432     if (m_requestRole[GroupRole]) {
1433         data.insert(sharedValue("group"), item.group());
1434     }
1435
1436     if (m_requestRole[DestinationRole]) {
1437         QString destination = item.linkDest();
1438         if (destination.isEmpty()) {
1439             destination = QLatin1String("-");
1440         }
1441         data.insert(sharedValue("destination"), destination);
1442     }
1443
1444     if (m_requestRole[PathRole]) {
1445         QString path;
1446         if (item.url().protocol() == QLatin1String("trash")) {
1447             path = item.entry().stringValue(KIO::UDSEntry::UDS_EXTRA);
1448         } else {
1449             // For performance reasons cache the home-path in a static QString
1450             // (see QDir::homePath() for more details)
1451             static QString homePath;
1452             if (homePath.isEmpty()) {
1453                 homePath = QDir::homePath();
1454             }
1455
1456             path = item.localPath();
1457             if (path.startsWith(homePath)) {
1458                 path.replace(0, homePath.length(), QLatin1Char('~'));
1459             }
1460         }
1461
1462         const int index = path.lastIndexOf(item.text());
1463         path = path.mid(0, index - 1);
1464         data.insert(sharedValue("path"), path);
1465     }
1466
1467     if (m_requestRole[IsExpandableRole] && isDir) {
1468         data.insert(sharedValue("isExpandable"), true);
1469     }
1470
1471     if (m_requestRole[ExpandedParentsCountRole]) {
1472         if (parent) {
1473             const int level = expandedParentsCount(parent) + 1;
1474             data.insert(sharedValue("expandedParentsCount"), level);
1475         }
1476     }
1477
1478     if (item.isMimeTypeKnown()) {
1479         data.insert(sharedValue("iconName"), item.iconName());
1480
1481         if (m_requestRole[TypeRole]) {
1482             data.insert(sharedValue("type"), item.mimeComment());
1483         }
1484     } else if (m_requestRole[TypeRole] && isDir) {
1485         static const QString folderMimeType = item.mimeComment();
1486         data.insert(sharedValue("type"), folderMimeType);
1487     }
1488
1489     return data;
1490 }
1491
1492 bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const
1493 {
1494     int result = 0;
1495
1496     if (a->parent != b->parent) {
1497         const int expansionLevelA = expandedParentsCount(a);
1498         const int expansionLevelB = expandedParentsCount(b);
1499
1500         // If b has a higher expansion level than a, check if a is a parent
1501         // of b, and make sure that both expansion levels are equal otherwise.
1502         for (int i = expansionLevelB; i > expansionLevelA; --i) {
1503             if (b->parent == a) {
1504                 return true;
1505             }
1506             b = b->parent;
1507         }
1508
1509         // If a has a higher expansion level than a, check if b is a parent
1510         // of a, and make sure that both expansion levels are equal otherwise.
1511         for (int i = expansionLevelA; i > expansionLevelB; --i) {
1512             if (a->parent == b) {
1513                 return false;
1514             }
1515             a = a->parent;
1516         }
1517
1518         Q_ASSERT(expandedParentsCount(a) == expandedParentsCount(b));
1519
1520         // Compare the last parents of a and b which are different.
1521         while (a->parent != b->parent) {
1522             a = a->parent;
1523             b = b->parent;
1524         }
1525     }
1526
1527     if (m_sortDirsFirst || m_sortRole == SizeRole) {
1528         const bool isDirA = a->item.isDir();
1529         const bool isDirB = b->item.isDir();
1530         if (isDirA && !isDirB) {
1531             return true;
1532         } else if (!isDirA && isDirB) {
1533             return false;
1534         }
1535     }
1536
1537     result = sortRoleCompare(a, b);
1538
1539     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
1540 }
1541
1542 /**
1543  * Helper class for KFileItemModel::sort().
1544  */
1545 class KFileItemModelLessThan
1546 {
1547 public:
1548     KFileItemModelLessThan(const KFileItemModel* model) :
1549         m_model(model)
1550     {
1551     }
1552
1553     bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const
1554     {
1555         return m_model->lessThan(a, b);
1556     }
1557
1558 private:
1559     const KFileItemModel* m_model;
1560 };
1561
1562 void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin,
1563                           QList<KFileItemModel::ItemData*>::iterator end) const
1564 {
1565     KFileItemModelLessThan lessThan(this);
1566
1567     if (m_sortRole == NameRole) {
1568         // Sorting by name can be expensive, in particular if natural sorting is
1569         // enabled. Use all CPU cores to speed up the sorting process.
1570         static const int numberOfThreads = QThread::idealThreadCount();
1571         parallelMergeSort(begin, end, lessThan, numberOfThreads);
1572     } else {
1573         // Sorting by other roles is quite fast. Use only one thread to prevent
1574         // problems caused by non-reentrant comparison functions, see
1575         // https://bugs.kde.org/show_bug.cgi?id=312679
1576         mergeSort(begin, end, lessThan);
1577     }
1578 }
1579
1580 int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
1581 {
1582     const KFileItem& itemA = a->item;
1583     const KFileItem& itemB = b->item;
1584
1585     int result = 0;
1586
1587     switch (m_sortRole) {
1588     case NameRole:
1589         // The name role is handled as default fallback after the switch
1590         break;
1591
1592     case SizeRole: {
1593         if (itemA.isDir()) {
1594             // See "if (m_sortFoldersFirst || m_sortRole == SizeRole)" in KFileItemModel::lessThan():
1595             Q_ASSERT(itemB.isDir());
1596
1597             const QVariant valueA = a->values.value("size");
1598             const QVariant valueB = b->values.value("size");
1599             if (valueA.isNull() && valueB.isNull()) {
1600                 result = 0;
1601             } else if (valueA.isNull()) {
1602                 result = -1;
1603             } else if (valueB.isNull()) {
1604                 result = +1;
1605             } else {
1606                 result = valueA.toInt() - valueB.toInt();
1607             }
1608         } else {
1609             // See "if (m_sortFoldersFirst || m_sortRole == SizeRole)" in KFileItemModel::lessThan():
1610             Q_ASSERT(!itemB.isDir());
1611             const KIO::filesize_t sizeA = itemA.size();
1612             const KIO::filesize_t sizeB = itemB.size();
1613             if (sizeA > sizeB) {
1614                 result = +1;
1615             } else if (sizeA < sizeB) {
1616                 result = -1;
1617             } else {
1618                 result = 0;
1619             }
1620         }
1621         break;
1622     }
1623
1624     case DateRole: {
1625         const KDateTime dateTimeA = itemA.time(KFileItem::ModificationTime);
1626         const KDateTime dateTimeB = itemB.time(KFileItem::ModificationTime);
1627         if (dateTimeA < dateTimeB) {
1628             result = -1;
1629         } else if (dateTimeA > dateTimeB) {
1630             result = +1;
1631         }
1632         break;
1633     }
1634
1635     case RatingRole: {
1636         result = a->values.value("rating").toInt() - b->values.value("rating").toInt();
1637         break;
1638     }
1639
1640     case ImageSizeRole: {
1641         // Alway use a natural comparing to interpret the numbers of a string like
1642         // "1600 x 1200" for having a correct sorting.
1643         result = KStringHandler::naturalCompare(a->values.value("imageSize").toString(),
1644                                                 b->values.value("imageSize").toString(),
1645                                                 Qt::CaseSensitive);
1646         break;
1647     }
1648
1649     default: {
1650         const QByteArray role = roleForType(m_sortRole);
1651         result = QString::compare(a->values.value(role).toString(),
1652                                   b->values.value(role).toString());
1653         break;
1654     }
1655
1656     }
1657
1658     if (result != 0) {
1659         // The current sort role was sufficient to define an order
1660         return result;
1661     }
1662
1663     // Fallback #1: Compare the text of the items
1664     result = stringCompare(itemA.text(), itemB.text());
1665     if (result != 0) {
1666         return result;
1667     }
1668
1669     // Fallback #2: KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
1670     result = stringCompare(itemA.name(m_caseSensitivity == Qt::CaseInsensitive),
1671                            itemB.name(m_caseSensitivity == Qt::CaseInsensitive));
1672     if (result != 0) {
1673         return result;
1674     }
1675
1676     // Fallback #3: It must be assured that the sort order is always unique even if two values have been
1677     // equal. In this case a comparison of the URL is done which is unique in all cases
1678     // within KDirLister.
1679     return QString::compare(itemA.url().url(), itemB.url().url(), Qt::CaseSensitive);
1680 }
1681
1682 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
1683 {
1684     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
1685     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
1686     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
1687     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
1688
1689     if (m_caseSensitivity == Qt::CaseInsensitive) {
1690         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
1691                                             : QString::compare(a, b, Qt::CaseInsensitive);
1692         if (result != 0) {
1693             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
1694             // comparison, still a deterministic sort order is required. A case sensitive
1695             // comparison is done as fallback.
1696             return result;
1697         }
1698     }
1699
1700     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
1701                             : QString::compare(a, b, Qt::CaseSensitive);
1702 }
1703
1704 bool KFileItemModel::useMaximumUpdateInterval() const
1705 {
1706     return !m_dirLister->url().isLocalFile();
1707 }
1708
1709 static bool localeAwareLessThan(const QChar& c1, const QChar& c2)
1710 {
1711     return QString::localeAwareCompare(c1, c2) < 0;
1712 }
1713
1714 QList<QPair<int, QVariant> > KFileItemModel::nameRoleGroups() const
1715 {
1716     Q_ASSERT(!m_itemData.isEmpty());
1717
1718     const int maxIndex = count() - 1;
1719     QList<QPair<int, QVariant> > groups;
1720
1721     QString groupValue;
1722     QChar firstChar;
1723     for (int i = 0; i <= maxIndex; ++i) {
1724         if (isChildItem(i)) {
1725             continue;
1726         }
1727
1728         const QString name = m_itemData.at(i)->item.text();
1729
1730         // Use the first character of the name as group indication
1731         QChar newFirstChar = name.at(0).toUpper();
1732         if (newFirstChar == QLatin1Char('~') && name.length() > 1) {
1733             newFirstChar = name.at(1).toUpper();
1734         }
1735
1736         if (firstChar != newFirstChar) {
1737             QString newGroupValue;
1738             if (newFirstChar.isLetter()) {
1739                 // Try to find a matching group in the range 'A' to 'Z'.
1740                 static std::vector<QChar> lettersAtoZ;
1741                 if (lettersAtoZ.empty()) {
1742                     for (char c = 'A'; c <= 'Z'; ++c) {
1743                         lettersAtoZ.push_back(QLatin1Char(c));
1744                     }
1745                 }
1746
1747                 std::vector<QChar>::iterator it = std::lower_bound(lettersAtoZ.begin(), lettersAtoZ.end(), newFirstChar, localeAwareLessThan);
1748                 if (it != lettersAtoZ.end()) {
1749                     if (localeAwareLessThan(newFirstChar, *it) && it != lettersAtoZ.begin()) {
1750                         // newFirstChar belongs to the group preceding *it.
1751                         // Example: for an umlaut 'A' in the German locale, *it would be 'B' now.
1752                         --it;
1753                     }
1754                     newGroupValue = *it;
1755                 } else {
1756                     newGroupValue = newFirstChar;
1757                 }
1758             } else if (newFirstChar >= QLatin1Char('0') && newFirstChar <= QLatin1Char('9')) {
1759                 // Apply group '0 - 9' for any name that starts with a digit
1760                 newGroupValue = i18nc("@title:group Groups that start with a digit", "0 - 9");
1761             } else {
1762                 newGroupValue = i18nc("@title:group", "Others");
1763             }
1764
1765             if (newGroupValue != groupValue) {
1766                 groupValue = newGroupValue;
1767                 groups.append(QPair<int, QVariant>(i, newGroupValue));
1768             }
1769
1770             firstChar = newFirstChar;
1771         }
1772     }
1773     return groups;
1774 }
1775
1776 QList<QPair<int, QVariant> > KFileItemModel::sizeRoleGroups() const
1777 {
1778     Q_ASSERT(!m_itemData.isEmpty());
1779
1780     const int maxIndex = count() - 1;
1781     QList<QPair<int, QVariant> > groups;
1782
1783     QString groupValue;
1784     for (int i = 0; i <= maxIndex; ++i) {
1785         if (isChildItem(i)) {
1786             continue;
1787         }
1788
1789         const KFileItem& item = m_itemData.at(i)->item;
1790         const KIO::filesize_t fileSize = !item.isNull() ? item.size() : ~0U;
1791         QString newGroupValue;
1792         if (!item.isNull() && item.isDir()) {
1793             newGroupValue = i18nc("@title:group Size", "Folders");
1794         } else if (fileSize < 5 * 1024 * 1024) {
1795             newGroupValue = i18nc("@title:group Size", "Small");
1796         } else if (fileSize < 10 * 1024 * 1024) {
1797             newGroupValue = i18nc("@title:group Size", "Medium");
1798         } else {
1799             newGroupValue = i18nc("@title:group Size", "Big");
1800         }
1801
1802         if (newGroupValue != groupValue) {
1803             groupValue = newGroupValue;
1804             groups.append(QPair<int, QVariant>(i, newGroupValue));
1805         }
1806     }
1807
1808     return groups;
1809 }
1810
1811 QList<QPair<int, QVariant> > KFileItemModel::dateRoleGroups() const
1812 {
1813     Q_ASSERT(!m_itemData.isEmpty());
1814
1815     const int maxIndex = count() - 1;
1816     QList<QPair<int, QVariant> > groups;
1817
1818     const QDate currentDate = KDateTime::currentLocalDateTime().date();
1819
1820     QDate previousModifiedDate;
1821     QString groupValue;
1822     for (int i = 0; i <= maxIndex; ++i) {
1823         if (isChildItem(i)) {
1824             continue;
1825         }
1826
1827         const KDateTime modifiedTime = m_itemData.at(i)->item.time(KFileItem::ModificationTime);
1828         const QDate modifiedDate = modifiedTime.date();
1829         if (modifiedDate == previousModifiedDate) {
1830             // The current item is in the same group as the previous item
1831             continue;
1832         }
1833         previousModifiedDate = modifiedDate;
1834
1835         const int daysDistance = modifiedDate.daysTo(currentDate);
1836
1837         QString newGroupValue;
1838         if (currentDate.year() == modifiedDate.year() && currentDate.month() == modifiedDate.month()) {
1839             switch (daysDistance / 7) {
1840             case 0:
1841                 switch (daysDistance) {
1842                 case 0:  newGroupValue = i18nc("@title:group Date", "Today"); break;
1843                 case 1:  newGroupValue = i18nc("@title:group Date", "Yesterday"); break;
1844                 default: newGroupValue = modifiedTime.toString(i18nc("@title:group The week day name: %A", "%A"));
1845                 }
1846                 break;
1847             case 1:
1848                 newGroupValue = i18nc("@title:group Date", "One Week Ago");
1849                 break;
1850             case 2:
1851                 newGroupValue = i18nc("@title:group Date", "Two Weeks Ago");
1852                 break;
1853             case 3:
1854                 newGroupValue = i18nc("@title:group Date", "Three Weeks Ago");
1855                 break;
1856             case 4:
1857             case 5:
1858                 newGroupValue = i18nc("@title:group Date", "Earlier this Month");
1859                 break;
1860             default:
1861                 Q_ASSERT(false);
1862             }
1863         } else {
1864             const QDate lastMonthDate = currentDate.addMonths(-1);
1865             if  (lastMonthDate.year() == modifiedDate.year() && lastMonthDate.month() == modifiedDate.month()) {
1866                 if (daysDistance == 1) {
1867                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Yesterday (%B, %Y)"));
1868                 } else if (daysDistance <= 7) {
1869                     newGroupValue = modifiedTime.toString(i18nc("@title:group The week day name: %A, %B is full month name in current locale, and %Y is full year number", "%A (%B, %Y)"));
1870                 } else if (daysDistance <= 7 * 2) {
1871                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "One Week Ago (%B, %Y)"));
1872                 } else if (daysDistance <= 7 * 3) {
1873                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Two Weeks Ago (%B, %Y)"));
1874                 } else if (daysDistance <= 7 * 4) {
1875                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Three Weeks Ago (%B, %Y)"));
1876                 } else {
1877                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Earlier on %B, %Y"));
1878                 }
1879             } else {
1880                 newGroupValue = modifiedTime.toString(i18nc("@title:group The month and year: %B is full month name in current locale, and %Y is full year number", "%B, %Y"));
1881             }
1882         }
1883
1884         if (newGroupValue != groupValue) {
1885             groupValue = newGroupValue;
1886             groups.append(QPair<int, QVariant>(i, newGroupValue));
1887         }
1888     }
1889
1890     return groups;
1891 }
1892
1893 QList<QPair<int, QVariant> > KFileItemModel::permissionRoleGroups() const
1894 {
1895     Q_ASSERT(!m_itemData.isEmpty());
1896
1897     const int maxIndex = count() - 1;
1898     QList<QPair<int, QVariant> > groups;
1899
1900     QString permissionsString;
1901     QString groupValue;
1902     for (int i = 0; i <= maxIndex; ++i) {
1903         if (isChildItem(i)) {
1904             continue;
1905         }
1906
1907         const ItemData* itemData = m_itemData.at(i);
1908         const QString newPermissionsString = itemData->values.value("permissions").toString();
1909         if (newPermissionsString == permissionsString) {
1910             continue;
1911         }
1912         permissionsString = newPermissionsString;
1913
1914         const QFileInfo info(itemData->item.url().pathOrUrl());
1915
1916         // Set user string
1917         QString user;
1918         if (info.permission(QFile::ReadUser)) {
1919             user = i18nc("@item:intext Access permission, concatenated", "Read, ");
1920         }
1921         if (info.permission(QFile::WriteUser)) {
1922             user += i18nc("@item:intext Access permission, concatenated", "Write, ");
1923         }
1924         if (info.permission(QFile::ExeUser)) {
1925             user += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1926         }
1927         user = user.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : user.mid(0, user.count() - 2);
1928
1929         // Set group string
1930         QString group;
1931         if (info.permission(QFile::ReadGroup)) {
1932             group = i18nc("@item:intext Access permission, concatenated", "Read, ");
1933         }
1934         if (info.permission(QFile::WriteGroup)) {
1935             group += i18nc("@item:intext Access permission, concatenated", "Write, ");
1936         }
1937         if (info.permission(QFile::ExeGroup)) {
1938             group += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1939         }
1940         group = group.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : group.mid(0, group.count() - 2);
1941
1942         // Set others string
1943         QString others;
1944         if (info.permission(QFile::ReadOther)) {
1945             others = i18nc("@item:intext Access permission, concatenated", "Read, ");
1946         }
1947         if (info.permission(QFile::WriteOther)) {
1948             others += i18nc("@item:intext Access permission, concatenated", "Write, ");
1949         }
1950         if (info.permission(QFile::ExeOther)) {
1951             others += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1952         }
1953         others = others.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : others.mid(0, others.count() - 2);
1954
1955         const QString newGroupValue = i18nc("@title:group Files and folders by permissions", "User: %1 | Group: %2 | Others: %3", user, group, others);
1956         if (newGroupValue != groupValue) {
1957             groupValue = newGroupValue;
1958             groups.append(QPair<int, QVariant>(i, newGroupValue));
1959         }
1960     }
1961
1962     return groups;
1963 }
1964
1965 QList<QPair<int, QVariant> > KFileItemModel::ratingRoleGroups() const
1966 {
1967     Q_ASSERT(!m_itemData.isEmpty());
1968
1969     const int maxIndex = count() - 1;
1970     QList<QPair<int, QVariant> > groups;
1971
1972     int groupValue = -1;
1973     for (int i = 0; i <= maxIndex; ++i) {
1974         if (isChildItem(i)) {
1975             continue;
1976         }
1977         const int newGroupValue = m_itemData.at(i)->values.value("rating", 0).toInt();
1978         if (newGroupValue != groupValue) {
1979             groupValue = newGroupValue;
1980             groups.append(QPair<int, QVariant>(i, newGroupValue));
1981         }
1982     }
1983
1984     return groups;
1985 }
1986
1987 QList<QPair<int, QVariant> > KFileItemModel::genericStringRoleGroups(const QByteArray& role) const
1988 {
1989     Q_ASSERT(!m_itemData.isEmpty());
1990
1991     const int maxIndex = count() - 1;
1992     QList<QPair<int, QVariant> > groups;
1993
1994     bool isFirstGroupValue = true;
1995     QString groupValue;
1996     for (int i = 0; i <= maxIndex; ++i) {
1997         if (isChildItem(i)) {
1998             continue;
1999         }
2000         const QString newGroupValue = m_itemData.at(i)->values.value(role).toString();
2001         if (newGroupValue != groupValue || isFirstGroupValue) {
2002             groupValue = newGroupValue;
2003             groups.append(QPair<int, QVariant>(i, newGroupValue));
2004             isFirstGroupValue = false;
2005         }
2006     }
2007
2008     return groups;
2009 }
2010
2011 void KFileItemModel::emitSortProgress(int resolvedCount)
2012 {
2013     // Be tolerant against a resolvedCount with a wrong range.
2014     // Although there should not be a case where KFileItemModelRolesUpdater
2015     // (= caller) provides a wrong range, it is important to emit
2016     // a useful progress information even if there is an unexpected
2017     // implementation issue.
2018
2019     const int itemCount = count();
2020     if (resolvedCount >= itemCount) {
2021         m_sortingProgressPercent = -1;
2022         if (m_resortAllItemsTimer->isActive()) {
2023             m_resortAllItemsTimer->stop();
2024             resortAllItems();
2025         }
2026
2027         emit directorySortingProgress(100);
2028     } else if (itemCount > 0) {
2029         resolvedCount = qBound(0, resolvedCount, itemCount);
2030
2031         const int progress = resolvedCount * 100 / itemCount;
2032         if (m_sortingProgressPercent != progress) {
2033             m_sortingProgressPercent = progress;
2034             emit directorySortingProgress(progress);
2035         }
2036     }
2037 }
2038
2039 const KFileItemModel::RoleInfoMap* KFileItemModel::rolesInfoMap(int& count)
2040 {
2041     static const RoleInfoMap rolesInfoMap[] = {
2042     //  | role         | roleType       | role translation                                | group translation           | requires Nepomuk | requires indexer
2043         { 0,             NoRole,          0, 0,                                             0, 0,                                     false, false },
2044         { "text",        NameRole,        I18N_NOOP2_NOSTRIP("@label", "Name"),             0, 0,                                     false, false },
2045         { "size",        SizeRole,        I18N_NOOP2_NOSTRIP("@label", "Size"),             0, 0,                                     false, false },
2046         { "date",        DateRole,        I18N_NOOP2_NOSTRIP("@label", "Date"),             0, 0,                                     false, false },
2047         { "type",        TypeRole,        I18N_NOOP2_NOSTRIP("@label", "Type"),             0, 0,                                     false, false },
2048         { "rating",      RatingRole,      I18N_NOOP2_NOSTRIP("@label", "Rating"),           0, 0,                                     true,  false },
2049         { "tags",        TagsRole,        I18N_NOOP2_NOSTRIP("@label", "Tags"),             0, 0,                                     true,  false },
2050         { "comment",     CommentRole,     I18N_NOOP2_NOSTRIP("@label", "Comment"),          0, 0,                                     true,  false },
2051         { "wordCount",   WordCountRole,   I18N_NOOP2_NOSTRIP("@label", "Word Count"),       I18N_NOOP2_NOSTRIP("@label", "Document"), true,  true  },
2052         { "lineCount",   LineCountRole,   I18N_NOOP2_NOSTRIP("@label", "Line Count"),       I18N_NOOP2_NOSTRIP("@label", "Document"), true,  true  },
2053         { "imageSize",   ImageSizeRole,   I18N_NOOP2_NOSTRIP("@label", "Image Size"),       I18N_NOOP2_NOSTRIP("@label", "Image"),    true,  true  },
2054         { "orientation", OrientationRole, I18N_NOOP2_NOSTRIP("@label", "Orientation"),      I18N_NOOP2_NOSTRIP("@label", "Image"),    true,  true  },
2055         { "artist",      ArtistRole,      I18N_NOOP2_NOSTRIP("@label", "Artist"),           I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2056         { "album",       AlbumRole,       I18N_NOOP2_NOSTRIP("@label", "Album"),            I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2057         { "duration",    DurationRole,    I18N_NOOP2_NOSTRIP("@label", "Duration"),         I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2058         { "track",       TrackRole,       I18N_NOOP2_NOSTRIP("@label", "Track"),            I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2059         { "path",        PathRole,        I18N_NOOP2_NOSTRIP("@label", "Path"),             I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2060         { "destination", DestinationRole, I18N_NOOP2_NOSTRIP("@label", "Link Destination"), I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2061         { "copiedFrom",  CopiedFromRole,  I18N_NOOP2_NOSTRIP("@label", "Copied From"),      I18N_NOOP2_NOSTRIP("@label", "Other"),    true,  false },
2062         { "permissions", PermissionsRole, I18N_NOOP2_NOSTRIP("@label", "Permissions"),      I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2063         { "owner",       OwnerRole,       I18N_NOOP2_NOSTRIP("@label", "Owner"),            I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2064         { "group",       GroupRole,       I18N_NOOP2_NOSTRIP("@label", "User Group"),       I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2065     };
2066
2067     count = sizeof(rolesInfoMap) / sizeof(RoleInfoMap);
2068     return rolesInfoMap;
2069 }
2070
2071 void KFileItemModel::determineMimeTypes(const KFileItemList& items, int timeout)
2072 {
2073     QElapsedTimer timer;
2074     timer.start();
2075     foreach (const KFileItem& item, items) { // krazy:exclude=foreach
2076         // Only determine mime types for files here. For directories,
2077         // KFileItem::determineMimeType() reads the .directory file inside to
2078         // load the icon, but this is not necessary at all if we just need the
2079         // type. Some special code for setting the correct mime type for
2080         // directories is in retrieveData().
2081         if (!item.isDir()) {
2082             item.determineMimeType();
2083         }
2084
2085         if (timer.elapsed() > timeout) {
2086             // Don't block the user interface, let the remaining items
2087             // be resolved asynchronously.
2088             return;
2089         }
2090     }
2091 }
2092
2093 QByteArray KFileItemModel::sharedValue(const QByteArray& value)
2094 {
2095     static QSet<QByteArray> pool;
2096     const QSet<QByteArray>::const_iterator it = pool.constFind(value);
2097
2098     if (it != pool.constEnd()) {
2099         return *it;
2100     } else {
2101         pool.insert(value);
2102         return value;
2103     }
2104 }
2105
2106 bool KFileItemModel::isConsistent() const
2107 {
2108     if (m_items.count() != m_itemData.count()) {
2109         return false;
2110     }
2111
2112     for (int i = 0; i < count(); ++i) {
2113         // Check if m_items and m_itemData are consistent.
2114         const KFileItem item = fileItem(i);
2115         if (item.isNull()) {
2116             qWarning() << "Item" << i << "is null";
2117             return false;
2118         }
2119
2120         const int itemIndex = index(item);
2121         if (itemIndex != i) {
2122             qWarning() << "Item" << i << "has a wrong index:" << itemIndex;
2123             return false;
2124         }
2125
2126         // Check if the items are sorted correctly.
2127         if (i > 0 && !lessThan(m_itemData.at(i - 1), m_itemData.at(i))) {
2128             qWarning() << "The order of items" << i - 1 << "and" << i << "is wrong:"
2129                 << fileItem(i - 1) << fileItem(i);
2130             return false;
2131         }
2132
2133         // Check if all parent-child relationships are consistent.
2134         const ItemData* data = m_itemData.at(i);
2135         const ItemData* parent = data->parent;
2136         if (parent) {
2137             if (expandedParentsCount(data) != expandedParentsCount(parent) + 1) {
2138                 qWarning() << "expandedParentsCount is inconsistent for parent" << parent->item << "and child" << data->item;
2139                 return false;
2140             }
2141
2142             const int parentIndex = index(parent->item);
2143             if (parentIndex >= i) {
2144                 qWarning() << "Index" << parentIndex << "of parent" << parent->item << "is not smaller than index" << i << "of child" << data->item;
2145                 return false;
2146             }
2147         }
2148     }
2149
2150     return true;
2151 }
2152
2153 #include "kfileitemmodel.moc"