kleopatra/models/keylistmodel.cpp

   1 /* -*- mode: c++; c-basic-offset:4 -*-
   2     models/keylistmodel.cpp
   3
   4     This file is part of Kleopatra, the KDE keymanager
   5     Copyright (c) 2007 Klarälvdalens Datakonsult AB
   6
   7     Kleopatra is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     Kleopatra is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15     General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with this program; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21     In addition, as a special exception, the copyright holders give
  22     permission to link the code of this program with any edition of
  23     the Qt library by Trolltech AS, Norway (or with modified versions
  24     of Qt that use the same license as Qt), and distribute linked
  25     combinations including the two.  You must obey the GNU General
  26     Public License in all respects for all of the code used other than
  27     Qt.  If you modify this file, you may extend this exception to
  28     your version of the file, but you are not obligated to do so.  If
  29     you do not wish to do so, delete this exception statement from
  30     your version.
  31 */
  32
  33 #include <config-kleopatra.h>
  34
  35 #include "keylistmodel.h"
  36 #include "Libkleo/Predicates"
  37
  38 #ifdef KLEO_MODEL_TEST
  39 # include "modeltest.h"
  40 #endif
  41
  42 #include <utils/formatting.h>
  43
  44 #include <Libkleo/KeyFilterManager>
  45 #include <Libkleo/KeyFilter>
  46
  47 #include <KLocalizedString>
  48
  49 #include <QFont>
  50 #include <QColor>
  51 #include <QHash>
  52 #include <QIcon>
  53 #include <QDate>
  54 #include <gpgme++/key.h>
  55
  56 #ifndef Q_MOC_RUN // QTBUG-22829
  57 #include <boost/bind.hpp>
  58 #include <boost/graph/topological_sort.hpp>
  59 #include <boost/graph/adjacency_list.hpp>
  60 #endif
  61
  62 #include <algorithm>
  63 #include <vector>
  64 #include <map>
  65 #include <set>
  66 #include <iterator>
  67 #include <cassert>
  68
  69 #ifdef __GLIBCXX__
  70 #include <ext/algorithm> // for is_sorted
  71 #endif
  72
  73 using namespace GpgME;
  74 using namespace Kleo;
  75
  76 /****************************************************************************
  77 **
  78 ** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
  79 ** Contact: Qt Software Information (qt-info@nokia.com)
  80 **
  81 ** This file is part of the QtCore module of the Qt Toolkit.
  82 **
  83 ** Commercial Usage
  84 ** Licensees holding valid Qt Commercial licenses may use this file in
  85 ** accordance with the Qt Commercial License Agreement provided with the
  86 ** Software or, alternatively, in accordance with the terms contained in
  87 ** a written agreement between you and Nokia.
  88 **
  89 **
  90 ** GNU General Public License Usage
  91 ** Alternatively, this file may be used under the terms of the GNU
  92 ** General Public License versions 2.0 or 3.0 as published by the Free
  93 ** Software Foundation and appearing in the file LICENSE.GPL included in
  94 ** the packaging of this file.  Please review the following information
  95 ** to ensure GNU General Public Licensing requirements will be met:
  96 ** http://www.fsf.org/licensing/licenses/info/GPLv2.html and
  97 ** http://www.gnu.org/copyleft/gpl.html.  In addition, as a special
  98 ** exception, Nokia gives you certain additional rights. These rights
  99 ** are described in the Nokia Qt GPL Exception version 1.3, included in
 100 ** the file GPL_EXCEPTION.txt in this package.
 101 **
 102 ** Qt for Windows(R) Licensees
 103 ** As a special exception, Nokia, as the sole copyright holder for Qt
 104 ** Designer, grants users of the Qt/Eclipse Integration plug-in the
 105 ** right for the Qt/Eclipse Integration to link to functionality
 106 ** provided by Qt Designer and its related libraries.
 107 **
 108 ** If you are unsure which license is appropriate for your use, please
 109 ** contact the sales department at qt-sales@nokia.com.
 110 **
 111 ****************************************************************************/
 112
 113 /*
 114     These functions are based on Peter J. Weinberger's hash function
 115     (from the Dragon Book). The constant 24 in the original function
 116     was replaced with 23 to produce fewer collisions on input such as
 117     "a", "aa", "aaa", "aaaa", ...
 118 */
 119
 120 // adjustment to null-terminated strings
 121 // (c) 2008 Klarälvdalens Datakonsult AB
 122 static uint hash(const uchar *p)
 123 {
 124     uint h = 0;
 125     uint g;
 126
 127     while (*p) {
 128         h = (h << 4) + *p++;
 129         if ((g = (h & 0xf0000000)) != 0) {
 130             h ^= g >> 23;
 131         }
 132         h &= ~g;
 133     }
 134     return h;
 135 }
 136
 137 //
 138 // end Nokia-copyrighted code
 139 //
 140
 141 static inline uint qHash(const char *data)
 142 {
 143     if (!data) {
 144         return 1;    // something != 0
 145     }
 146     return ::hash(reinterpret_cast<const uchar *>(data));
 147 }
 148
 149 class AbstractKeyListModel::Private
 150 {
 151 public:
 152     Private() : m_toolTipOptions(Formatting::Validity) {}
 153     int m_toolTipOptions;
 154     mutable QHash<const char *, QVariant> prettyEMailCache;
 155 };
 156 AbstractKeyListModel::AbstractKeyListModel(QObject *p)
 157     : QAbstractItemModel(p), KeyListModelInterface(), d(new Private)
 158 {
 159
 160 }
 161
 162 AbstractKeyListModel::~AbstractKeyListModel() {}
 163
 164 void AbstractKeyListModel::setToolTipOptions(int opts)
 165 {
 166     d->m_toolTipOptions = opts;
 167 }
 168
 169 int AbstractKeyListModel::toolTipOptions() const
 170 {
 171     return d->m_toolTipOptions;
 172 }
 173
 174 Key AbstractKeyListModel::key(const QModelIndex &idx) const
 175 {
 176     if (idx.isValid()) {
 177         return doMapToKey(idx);
 178     } else {
 179         return Key::null;
 180     }
 181 }
 182
 183 std::vector<Key> AbstractKeyListModel::keys(const QList<QModelIndex> &indexes) const
 184 {
 185     std::vector<Key> result;
 186     result.reserve(indexes.size());
 187     std::transform(indexes.begin(), indexes.end(),
 188                    std::back_inserter(result),
 189                    boost::bind(&AbstractKeyListModel::key, this, _1));
 190     result.erase(std::unique(result.begin(), result.end(), _detail::ByFingerprint<std::equal_to>()), result.end());
 191     return result;
 192 }
 193
 194 QModelIndex AbstractKeyListModel::index(const Key &key, int col) const
 195 {
 196     if (key.isNull() || col < 0 || col >= NumColumns) {
 197         return QModelIndex();
 198     } else {
 199         return doMapFromKey(key, col);
 200     }
 201 }
 202
 203 QList<QModelIndex> AbstractKeyListModel::indexes(const std::vector<Key> &keys) const
 204 {
 205     QList<QModelIndex> result;
 206     std::transform(keys.begin(), keys.end(),
 207                    std::back_inserter(result),
 208                    // if some compilers are complaining about ambiguous overloads, use this line instead:
 209                    //bind( static_cast<QModelIndex(AbstractKeyListModel::*)(const Key&,int)const>( &AbstractKeyListModel::index ), this, _1, 0 ) );
 210                    boost::bind(&AbstractKeyListModel::index, this, _1, 0));
 211     return result;
 212 }
 213
 214 void AbstractKeyListModel::setKeys(const std::vector<Key> &keys)
 215 {
 216     clear();
 217     addKeys(keys);
 218 }
 219
 220 QModelIndex AbstractKeyListModel::addKey(const Key &key)
 221 {
 222     const std::vector<Key> vec(1, key);
 223     const QList<QModelIndex> l = doAddKeys(vec);
 224     return l.empty() ? QModelIndex() : l.front();
 225 }
 226
 227 void AbstractKeyListModel::removeKey(const Key &key)
 228 {
 229     if (key.isNull()) {
 230         return;
 231     }
 232     doRemoveKey(key);
 233     d->prettyEMailCache.remove(key.primaryFingerprint());
 234 }
 235
 236 QList<QModelIndex> AbstractKeyListModel::addKeys(const std::vector<Key> &keys)
 237 {
 238     std::vector<Key> sorted;
 239     sorted.reserve(keys.size());
 240     std::remove_copy_if(keys.begin(), keys.end(),
 241                         std::back_inserter(sorted),
 242                         boost::bind(&Key::isNull, _1));
 243     std::sort(sorted.begin(), sorted.end(), _detail::ByFingerprint<std::less>());
 244     return doAddKeys(sorted);
 245 }
 246
 247 void AbstractKeyListModel::clear()
 248 {
 249     doClear();
 250     d->prettyEMailCache.clear();
 251     reset();
 252 }
 253
 254 int AbstractKeyListModel::columnCount(const QModelIndex &) const
 255 {
 256     return NumColumns;
 257 }
 258
 259 QVariant AbstractKeyListModel::headerData(int section, Qt::Orientation o, int role) const
 260 {
 261     if (o == Qt::Horizontal)
 262         if (role == Qt::DisplayRole || role == Qt::EditRole || role == Qt::ToolTipRole)
 263             switch (section) {
 264             case PrettyName:       return i18n("Name");
 265             case PrettyEMail:      return i18n("E-Mail");
 266             case ValidFrom:        return i18n("Valid From");
 267             case ValidUntil:       return i18n("Valid Until");
 268             case TechnicalDetails: return i18n("Details");
 269             case ShortKeyID:       return i18n("Key-ID");
 270             case NumColumns:;
 271             }
 272     return QVariant();
 273 }
 274
 275 static QVariant returnIfValid(const QColor &t)
 276 {
 277     if (t.isValid()) {
 278         return t;
 279     } else {
 280         return QVariant();
 281     }
 282 }
 283
 284 static QVariant returnIfValid(const QIcon &t)
 285 {
 286     if (!t.isNull()) {
 287         return t;
 288     } else {
 289         return QVariant();
 290     }
 291 }
 292
 293 QVariant AbstractKeyListModel::data(const QModelIndex &index, int role) const
 294 {
 295     const Key key = this->key(index);
 296     if (key.isNull()) {
 297         return QVariant();
 298     }
 299
 300     const int column = index.column();
 301
 302     if (role == Qt::DisplayRole || role == Qt::EditRole)
 303         switch (column) {
 304         case PrettyName:
 305             return Formatting::prettyName(key);
 306         case PrettyEMail:
 307             if (const char *const fpr = key.primaryFingerprint()) {
 308                 const QHash<const char *, QVariant>::const_iterator it = d->prettyEMailCache.constFind(fpr);
 309                 if (it != d->prettyEMailCache.constEnd()) {
 310                     return *it;
 311                 } else {
 312                     return d->prettyEMailCache[fpr] = Formatting::prettyEMail(key);
 313                 }
 314             } else {
 315                 return QVariant();
 316             }
 317         case ValidFrom:
 318             if (role == Qt::EditRole) {
 319                 return Formatting::creationDate(key);
 320             } else {
 321                 return Formatting::creationDateString(key);
 322             }
 323         case ValidUntil:
 324             if (role == Qt::EditRole) {
 325                 return Formatting::expirationDate(key);
 326             } else {
 327                 return Formatting::expirationDateString(key);
 328             }
 329         case TechnicalDetails:
 330             return Formatting::type(key);
 331         case ShortKeyID:
 332             return QString::fromLatin1(key.shortKeyID());
 333         case NumColumns:
 334             break;
 335         }
 336     else if (role == Qt::ToolTipRole) {
 337         return Formatting::toolTip(key, toolTipOptions());
 338     } else if (role == Qt::FontRole) {
 339         return KeyFilterManager::instance()->font(key, (column == ShortKeyID) ? QFont(QStringLiteral("courier")) : QFont());
 340     } else if (role == Qt::DecorationRole) {
 341         return column == Icon ? returnIfValid(KeyFilterManager::instance()->icon(key)) : QVariant();
 342     } else if (role == Qt::BackgroundRole) {
 343         return returnIfValid(KeyFilterManager::instance()->bgColor(key));
 344     } else if (role == Qt::ForegroundRole) {
 345         return returnIfValid(KeyFilterManager::instance()->fgColor(key));
 346     } else if (role == FingerprintRole) {
 347         return QString::fromLatin1(key.primaryFingerprint());
 348     }
 349     return QVariant();
 350 }
 351
 352 namespace
 353 {
 354 template <typename Base>
 355 class TableModelMixin : public Base
 356 {
 357 public:
 358     explicit TableModelMixin(QObject *p = Q_NULLPTR) : Base(p) {}
 359     ~TableModelMixin() {}
 360
 361     using Base::index;
 362     QModelIndex index(int row, int column, const QModelIndex &pidx = QModelIndex()) const Q_DECL_OVERRIDE
 363     {
 364         return this->hasIndex(row, column, pidx) ? this->createIndex(row, column, Q_NULLPTR) : QModelIndex();
 365     }
 366
 367 private:
 368     QModelIndex parent(const QModelIndex &) const Q_DECL_OVERRIDE
 369     {
 370         return QModelIndex();
 371     }
 372     bool hasChildren(const QModelIndex &pidx) const Q_DECL_OVERRIDE
 373     {
 374         return (pidx.model() == this || !pidx.isValid()) && this->rowCount(pidx) > 0 && this->columnCount(pidx) > 0;
 375     }
 376 };
 377
 378 class FlatKeyListModel
 379 #ifndef Q_MOC_RUN
 380     : public TableModelMixin<AbstractKeyListModel>
 381 #else
 382     : public AbstractKeyListModel
 383 #endif
 384 {
 385     Q_OBJECT
 386 public:
 387     explicit FlatKeyListModel(QObject *parent = Q_NULLPTR);
 388     ~FlatKeyListModel();
 389
 390     int rowCount(const QModelIndex &pidx) const Q_DECL_OVERRIDE
 391     {
 392         return pidx.isValid() ? 0 : mKeysByFingerprint.size();
 393     }
 394
 395 private:
 396     Key doMapToKey(const QModelIndex &index) const Q_DECL_OVERRIDE;
 397     QModelIndex doMapFromKey(const Key &key, int col) const Q_DECL_OVERRIDE;
 398     QList<QModelIndex> doAddKeys(const std::vector<Key> &keys) Q_DECL_OVERRIDE;
 399     void doRemoveKey(const Key &key) Q_DECL_OVERRIDE;
 400     void doClear() Q_DECL_OVERRIDE {
 401         mKeysByFingerprint.clear();
 402     }
 403
 404 private:
 405     std::vector<Key> mKeysByFingerprint;
 406 };
 407
 408 class HierarchicalKeyListModel : public AbstractKeyListModel
 409 {
 410     Q_OBJECT
 411 public:
 412     explicit HierarchicalKeyListModel(QObject *parent = Q_NULLPTR);
 413     ~HierarchicalKeyListModel();
 414
 415     int rowCount(const QModelIndex &pidx) const Q_DECL_OVERRIDE;
 416     using AbstractKeyListModel::index;
 417     QModelIndex index(int row, int col, const QModelIndex &pidx) const Q_DECL_OVERRIDE;
 418     QModelIndex parent(const QModelIndex &idx) const Q_DECL_OVERRIDE;
 419
 420     bool hasChildren(const QModelIndex &pidx) const Q_DECL_OVERRIDE
 421     {
 422         return rowCount(pidx) > 0;
 423     }
 424
 425 private:
 426     Key doMapToKey(const QModelIndex &index) const Q_DECL_OVERRIDE;
 427     QModelIndex doMapFromKey(const Key &key, int col) const Q_DECL_OVERRIDE;
 428     QList<QModelIndex> doAddKeys(const std::vector<Key> &keys) Q_DECL_OVERRIDE;
 429     void doRemoveKey(const Key &key) Q_DECL_OVERRIDE;
 430     void doClear() Q_DECL_OVERRIDE {
 431         mTopLevels.clear();
 432         mKeysByFingerprint.clear();
 433         mKeysByExistingParent.clear();
 434         mKeysByNonExistingParent.clear();
 435     }
 436
 437 private:
 438     void addTopLevelKey(const Key &key);
 439     void addKeyWithParent(const char *issuer_fpr, const Key &key);
 440     void addKeyWithoutParent(const char *issuer_fpr, const Key &key);
 441
 442 private:
 443     typedef std::map< std::string, std::vector<Key> > Map;
 444     std::vector<Key> mKeysByFingerprint; // all keys
 445     Map mKeysByExistingParent, mKeysByNonExistingParent; // parent->child map
 446     std::vector<Key> mTopLevels; // all roots + parent-less
 447 };
 448
 449 static const char *cleanChainID(const Key &key)
 450 {
 451     if (key.isRoot()) {
 452         return "";
 453     }
 454     if (const char *chid = key.chainID()) {
 455         return chid;
 456     }
 457     return "";
 458 }
 459
 460 }
 461
 462 FlatKeyListModel::FlatKeyListModel(QObject *p)
 463     : TableModelMixin<AbstractKeyListModel>(p),
 464       mKeysByFingerprint()
 465 {
 466
 467 }
 468
 469 FlatKeyListModel::~FlatKeyListModel() {}
 470
 471 Key FlatKeyListModel::doMapToKey(const QModelIndex &idx) const
 472 {
 473     assert(idx.isValid());
 474     if (static_cast<unsigned>(idx.row()) < mKeysByFingerprint.size() && idx.column() < NumColumns) {
 475         return mKeysByFingerprint[ idx.row() ];
 476     } else {
 477         return Key::null;
 478     }
 479 }
 480
 481 QModelIndex FlatKeyListModel::doMapFromKey(const Key &key, int col) const
 482 {
 483     assert(!key.isNull());
 484     const std::vector<Key>::const_iterator it
 485         = std::lower_bound(mKeysByFingerprint.begin(), mKeysByFingerprint.end(),
 486                            key, _detail::ByFingerprint<std::less>());
 487     if (it == mKeysByFingerprint.end() || !_detail::ByFingerprint<std::equal_to>()(*it, key)) {
 488         return QModelIndex();
 489     } else {
 490         return createIndex(it - mKeysByFingerprint.begin(), col);
 491     }
 492 }
 493
 494 QList<QModelIndex> FlatKeyListModel::doAddKeys(const std::vector<Key> &keys)
 495 {
 496 #ifdef __GLIBCXX__
 497     assert(__gnu_cxx::is_sorted(keys.begin(), keys.end(), _detail::ByFingerprint<std::less>()));
 498 #endif
 499     if (keys.empty()) {
 500         return QList<QModelIndex>();
 501     }
 502
 503     for (std::vector<Key>::const_iterator it = keys.begin(), end = keys.end(); it != end; ++it) {
 504
 505         // find an insertion point:
 506         const std::vector<Key>::iterator pos = std::upper_bound(mKeysByFingerprint.begin(), mKeysByFingerprint.end(), *it, _detail::ByFingerprint<std::less>());
 507         const unsigned int idx = std::distance(mKeysByFingerprint.begin(), pos);
 508
 509         if (idx > 0 && qstrcmp(mKeysByFingerprint[idx - 1].primaryFingerprint(), it->primaryFingerprint()) == 0) {
 510             // key existed before - replace with new one:
 511             mKeysByFingerprint[idx - 1] = *it;
 512             Q_EMIT dataChanged(createIndex(idx - 1, 0), createIndex(idx - 1, NumColumns - 1));
 513         } else {
 514             // new key - insert:
 515             beginInsertRows(QModelIndex(), idx, idx);
 516             mKeysByFingerprint.insert(pos, *it);
 517             endInsertRows();
 518         }
 519     }
 520
 521     return indexes(keys);
 522 }
 523
 524 void FlatKeyListModel::doRemoveKey(const Key &key)
 525 {
 526     const std::vector<Key>::iterator it
 527         = qBinaryFind(mKeysByFingerprint.begin(), mKeysByFingerprint.end(),
 528                       key, _detail::ByFingerprint<std::less>());
 529     if (it == mKeysByFingerprint.end()) {
 530         return;
 531     }
 532
 533     const unsigned int row = std::distance(mKeysByFingerprint.begin(), it);
 534     beginRemoveRows(QModelIndex(), row, row);
 535     mKeysByFingerprint.erase(it);
 536     endRemoveRows();
 537 }
 538
 539 HierarchicalKeyListModel::HierarchicalKeyListModel(QObject *p)
 540     : AbstractKeyListModel(p),
 541       mKeysByFingerprint(),
 542       mKeysByExistingParent(),
 543       mKeysByNonExistingParent(),
 544       mTopLevels()
 545 {
 546
 547 }
 548
 549 HierarchicalKeyListModel::~HierarchicalKeyListModel() {}
 550
 551 int HierarchicalKeyListModel::rowCount(const QModelIndex &pidx) const
 552 {
 553
 554     // toplevel item:
 555     if (!pidx.isValid()) {
 556         return mTopLevels.size();
 557     }
 558
 559     if (pidx.column() != 0) {
 560         return 0;
 561     }
 562
 563     // non-toplevel item - find the number of subjects for this issuer:
 564     const Key issuer = this->key(pidx);
 565     const char *const fpr = issuer.primaryFingerprint();
 566     if (!fpr || !*fpr) {
 567         return 0;
 568     }
 569     const Map::const_iterator it = mKeysByExistingParent.find(fpr);
 570     if (it == mKeysByExistingParent.end()) {
 571         return 0;
 572     }
 573     return it->second.size();
 574 }
 575
 576 QModelIndex HierarchicalKeyListModel::index(int row, int col, const QModelIndex &pidx) const
 577 {
 578
 579     if (row < 0 || col < 0 || col >= NumColumns) {
 580         return QModelIndex();
 581     }
 582
 583     // toplevel item:
 584     if (!pidx.isValid()) {
 585         if (static_cast<unsigned>(row) < mTopLevels.size()) {
 586             return index(mTopLevels[row], col);
 587         } else {
 588             return QModelIndex();
 589         }
 590     }
 591
 592     // non-toplevel item - find the row'th subject of this key:
 593     const Key issuer = this->key(pidx);
 594     const char *const fpr = issuer.primaryFingerprint();
 595     if (!fpr || !*fpr) {
 596         return QModelIndex();
 597     }
 598     const Map::const_iterator it = mKeysByExistingParent.find(fpr);
 599     if (it == mKeysByExistingParent.end() || static_cast<unsigned>(row) >= it->second.size()) {
 600         return QModelIndex();
 601     }
 602     return index(it->second[row], col);
 603 }
 604
 605 QModelIndex HierarchicalKeyListModel::parent(const QModelIndex &idx) const
 606 {
 607     const Key key = this->key(idx);
 608     if (key.isNull() || key.isRoot()) {
 609         return QModelIndex();
 610     }
 611     const std::vector<Key>::const_iterator it
 612         = qBinaryFind(mKeysByFingerprint.begin(), mKeysByFingerprint.end(),
 613                       cleanChainID(key), _detail::ByFingerprint<std::less>());
 614     return it != mKeysByFingerprint.end() ? index(*it) : QModelIndex();
 615 }
 616
 617 Key HierarchicalKeyListModel::doMapToKey(const QModelIndex &idx) const
 618 {
 619
 620     if (!idx.isValid()) {
 621         return Key::null;
 622     }
 623
 624     const char *const issuer_fpr = static_cast<const char *>(idx.internalPointer());
 625     if (!issuer_fpr || !*issuer_fpr) {
 626         // top-level:
 627         if (static_cast<unsigned>(idx.row()) >= mTopLevels.size()) {
 628             return Key::null;
 629         } else {
 630             return mTopLevels[idx.row()];
 631         }
 632     }
 633
 634     // non-toplevel:
 635     const Map::const_iterator it
 636         = mKeysByExistingParent.find(issuer_fpr);
 637     if (it == mKeysByExistingParent.end() || static_cast<unsigned>(idx.row()) >= it->second.size()) {
 638         return Key::null;
 639     }
 640     return it->second[idx.row()];
 641 }
 642
 643 QModelIndex HierarchicalKeyListModel::doMapFromKey(const Key &key, int col) const
 644 {
 645
 646     if (key.isNull()) {
 647         return QModelIndex();
 648     }
 649
 650     const char *issuer_fpr = cleanChainID(key);
 651
 652     // we need to look in the toplevels list,...
 653     const std::vector<Key> *v = &mTopLevels;
 654     if (issuer_fpr && *issuer_fpr) {
 655         const std::map< std::string, std::vector<Key> >::const_iterator it
 656             = mKeysByExistingParent.find(issuer_fpr);
 657         // ...unless we find an existing parent:
 658         if (it != mKeysByExistingParent.end()) {
 659             v = &it->second;
 660         } else {
 661             issuer_fpr = 0;    // force internalPointer to zero for toplevels
 662         }
 663     }
 664
 665     const std::vector<Key>::const_iterator it
 666         = std::lower_bound(v->begin(), v->end(), key, _detail::ByFingerprint<std::less>());
 667     if (it == v->end() || !_detail::ByFingerprint<std::equal_to>()(*it, key)) {
 668         return QModelIndex();
 669     }
 670
 671     const unsigned int row = std::distance(v->begin(), it);
 672     return createIndex(row, col, const_cast<char * /* thanks, Trolls :/ */ >(issuer_fpr));
 673 }
 674
 675 void HierarchicalKeyListModel::addKeyWithParent(const char *issuer_fpr, const Key &key)
 676 {
 677
 678     assert(issuer_fpr); assert(*issuer_fpr); assert(!key.isNull());
 679
 680     std::vector<Key> &subjects = mKeysByExistingParent[issuer_fpr];
 681
 682     // find insertion point:
 683     const std::vector<Key>::iterator it = std::lower_bound(subjects.begin(), subjects.end(), key, _detail::ByFingerprint<std::less>());
 684     const int row = std::distance(subjects.begin(), it);
 685
 686     if (it != subjects.end() && qstricmp(it->primaryFingerprint(), key.primaryFingerprint()) == 0) {
 687         // exists -> replace
 688         *it = key;
 689         Q_EMIT dataChanged(createIndex(row, 0, const_cast<char *>(issuer_fpr)), createIndex(row, NumColumns - 1, const_cast<char *>(issuer_fpr)));
 690     } else {
 691         // doesn't exist -> insert
 692         const std::vector<Key>::const_iterator pos = qBinaryFind(mKeysByFingerprint.begin(), mKeysByFingerprint.end(), issuer_fpr, _detail::ByFingerprint<std::less>());
 693         assert(pos != mKeysByFingerprint.end());
 694         beginInsertRows(index(*pos), row, row);
 695         subjects.insert(it, key);
 696         endInsertRows();
 697     }
 698 }
 699
 700 void HierarchicalKeyListModel::addKeyWithoutParent(const char *issuer_fpr, const Key &key)
 701 {
 702
 703     assert(issuer_fpr); assert(*issuer_fpr); assert(!key.isNull());
 704
 705     std::vector<Key> &subjects = mKeysByNonExistingParent[issuer_fpr];
 706
 707     // find insertion point:
 708     const std::vector<Key>::iterator it = std::lower_bound(subjects.begin(), subjects.end(), key, _detail::ByFingerprint<std::less>());
 709
 710     if (it != subjects.end() && qstricmp(it->primaryFingerprint(), key.primaryFingerprint()) == 0)
 711         // exists -> replace
 712     {
 713         *it = key;
 714     } else
 715         // doesn't exist -> insert
 716     {
 717         subjects.insert(it, key);
 718     }
 719
 720     addTopLevelKey(key);
 721 }
 722
 723 void HierarchicalKeyListModel::addTopLevelKey(const Key &key)
 724 {
 725
 726     // find insertion point:
 727     const std::vector<Key>::iterator it = std::lower_bound(mTopLevels.begin(), mTopLevels.end(), key, _detail::ByFingerprint<std::less>());
 728     const int row = std::distance(mTopLevels.begin(), it);
 729
 730     if (it != mTopLevels.end() && qstricmp(it->primaryFingerprint(), key.primaryFingerprint()) == 0) {
 731         // exists -> replace
 732         *it = key;
 733         Q_EMIT dataChanged(createIndex(row, 0), createIndex(row, NumColumns - 1));
 734     } else {
 735         // doesn't exist -> insert
 736         beginInsertRows(QModelIndex(), row, row);
 737         mTopLevels.insert(it, key);
 738         endInsertRows();
 739     }
 740
 741 }
 742
 743 // sorts 'keys' such that parent always come before their children:
 744 static std::vector<Key> topological_sort(const std::vector<Key> &keys)
 745 {
 746
 747     boost::adjacency_list<> graph(keys.size());
 748
 749     // add edges from children to parents:
 750     for (unsigned int i = 0, end = keys.size(); i != end; ++i) {
 751         const char *const issuer_fpr = cleanChainID(keys[i]);
 752         if (!issuer_fpr || !*issuer_fpr) {
 753             continue;
 754         }
 755         const std::vector<Key>::const_iterator it
 756             = qBinaryFind(keys.begin(), keys.end(), issuer_fpr, _detail::ByFingerprint<std::less>());
 757         if (it == keys.end()) {
 758             continue;
 759         }
 760         add_edge(i, std::distance(keys.begin(), it), graph);
 761     }
 762
 763     std::vector<int> order;
 764     order.reserve(keys.size());
 765     topological_sort(graph, std::back_inserter(order));
 766
 767     assert(order.size() == keys.size());
 768
 769     std::vector<Key> result;
 770     result.reserve(keys.size());
 771     Q_FOREACH (int i, order) {
 772         result.push_back(keys[i]);
 773     }
 774     return result;
 775 }
 776
 777 QList<QModelIndex> HierarchicalKeyListModel::doAddKeys(const std::vector<Key> &keys)
 778 {
 779 #ifdef __GLIBCXX__
 780     assert(__gnu_cxx::is_sorted(keys.begin(), keys.end(), _detail::ByFingerprint<std::less>()));
 781 #endif
 782     if (keys.empty()) {
 783         return QList<QModelIndex>();
 784     }
 785
 786     const std::vector<Key> oldKeys = mKeysByFingerprint;
 787
 788     std::vector<Key> merged;
 789     merged.reserve(keys.size() + mKeysByFingerprint.size());
 790     std::set_union(keys.begin(), keys.end(),
 791                    mKeysByFingerprint.begin(), mKeysByFingerprint.end(),
 792                    std::back_inserter(merged), _detail::ByFingerprint<std::less>());
 793
 794     mKeysByFingerprint = merged;
 795
 796     std::set<Key, _detail::ByFingerprint<std::less> > changedParents;
 797
 798     Q_FOREACH (const Key &key, topological_sort(keys)) {
 799
 800         // check to see whether this key is a parent for a previously parent-less group:
 801         const char *const fpr = key.primaryFingerprint();
 802         if (!fpr || !*fpr) {
 803             continue;
 804         }
 805
 806         const bool keyAlreadyExisted = qBinaryFind(oldKeys.begin(), oldKeys.end(), key, _detail::ByFingerprint<std::less>()) != oldKeys.end();
 807
 808         const Map::iterator it = mKeysByNonExistingParent.find(fpr);
 809         const std::vector<Key> children = it != mKeysByNonExistingParent.end() ? it->second : std::vector<Key>();
 810         if (it != mKeysByNonExistingParent.end()) {
 811             mKeysByNonExistingParent.erase(it);
 812         }
 813
 814         // Step 1: For new keys, remove children from toplevel:
 815
 816         if (!keyAlreadyExisted) {
 817             std::vector<Key>::iterator last = mTopLevels.begin();
 818             std::vector<Key>::iterator lastFP = mKeysByFingerprint.begin();
 819
 820             Q_FOREACH (const Key &k, children) {
 821                 last = qBinaryFind(last, mTopLevels.end(), k, _detail::ByFingerprint<std::less>());
 822                 assert(last != mTopLevels.end());
 823                 const int row = std::distance(mTopLevels.begin(), last);
 824
 825                 lastFP = qBinaryFind(lastFP, mKeysByFingerprint.end(), k, _detail::ByFingerprint<std::less>());
 826                 assert(lastFP != mKeysByFingerprint.end());
 827
 828                 Q_EMIT rowAboutToBeMoved(QModelIndex(), row);
 829                 beginRemoveRows(QModelIndex(), row, row);
 830                 last = mTopLevels.erase(last);
 831                 lastFP = mKeysByFingerprint.erase(lastFP);
 832                 endRemoveRows();
 833             }
 834         }
 835         // Step 2: add/update key
 836
 837         const char *const issuer_fpr = cleanChainID(key);
 838         if (!issuer_fpr || !*issuer_fpr)
 839             // root or something...
 840         {
 841             addTopLevelKey(key);
 842         } else if (std::binary_search(mKeysByFingerprint.begin(), mKeysByFingerprint.end(), issuer_fpr, _detail::ByFingerprint<std::less>()))
 843             // parent exists...
 844         {
 845             addKeyWithParent(issuer_fpr, key);
 846         } else
 847             // parent does't exist yet...
 848         {
 849             addKeyWithoutParent(issuer_fpr, key);
 850         }
 851
 852         const QModelIndex key_idx = index(key);
 853         QModelIndex key_parent = key_idx.parent();
 854         while (key_parent.isValid()) {
 855             changedParents.insert(doMapToKey(key_parent));
 856             key_parent = key_parent.parent();
 857         }
 858
 859         // Step 3: Add children to new parent ( == key )
 860
 861         if (!keyAlreadyExisted && !children.empty()) {
 862             addKeys(children);
 863             const QModelIndex new_parent = index(key);
 864             // Q_EMIT the rowMoved() signals in reversed direction, so the
 865             // implementation can use a stack for mapping.
 866             for (int i = children.size() - 1; i >= 0; --i) {
 867                 Q_EMIT rowMoved(new_parent, i);
 868             }
 869         }
 870     }
 871     //Q_EMIT dataChanged for all parents with new children. This triggers KeyListSortFilterProxyModel to
 872     //show a parent node if it just got children matching the proxy's filter
 873     Q_FOREACH (const Key &i, changedParents) {
 874         const QModelIndex idx = index(i);
 875         if (idx.isValid()) {
 876             Q_EMIT dataChanged(idx.sibling(idx.row(), 0), idx.sibling(idx.row(), NumColumns - 1));
 877         }
 878     }
 879     return indexes(keys);
 880 }
 881
 882 void HierarchicalKeyListModel::doRemoveKey(const Key &key)
 883 {
 884     const QModelIndex idx = index(key);
 885     if (!idx.isValid()) {
 886         return;
 887     }
 888
 889     const char *const fpr = key.primaryFingerprint();
 890     if (mKeysByExistingParent.find(fpr) != mKeysByExistingParent.end()) {
 891         //handle non-leave nodes:
 892         std::vector<Key> keys = mKeysByFingerprint;
 893         const std::vector<Key>::iterator it = qBinaryFind(keys.begin(), keys.end(),
 894                                               key, _detail::ByFingerprint<std::less>());
 895         if (it == keys.end()) {
 896             return;
 897         }
 898         keys.erase(it);
 899         // FIXME for simplicity, we just clear the model and re-add all keys minus the removed one. This is suboptimal,
 900         // but acceptable given that deletion of non-leave nodes is rather rare.
 901         clear();
 902         addKeys(keys);
 903         return;
 904     }
 905
 906     //handle leave nodes:
 907
 908     const std::vector<Key>::iterator it = qBinaryFind(mKeysByFingerprint.begin(), mKeysByFingerprint.end(),
 909                                           key, _detail::ByFingerprint<std::less>());
 910
 911     assert(it != mKeysByFingerprint.end());
 912     assert(mKeysByNonExistingParent.find(fpr) == mKeysByNonExistingParent.end());
 913     assert(mKeysByExistingParent.find(fpr) == mKeysByExistingParent.end());
 914
 915     beginRemoveRows(parent(idx), idx.row(), idx.row());
 916     mKeysByFingerprint.erase(it);
 917
 918     const char *const issuer_fpr = cleanChainID(key);
 919
 920     const std::vector<Key>::iterator tlIt = qBinaryFind(mTopLevels.begin(), mTopLevels.end(), key, _detail::ByFingerprint<std::less>());
 921     if (tlIt != mTopLevels.end()) {
 922         mTopLevels.erase(tlIt);
 923     }
 924
 925     if (issuer_fpr && *issuer_fpr) {
 926         const Map::iterator nexIt = mKeysByNonExistingParent.find(issuer_fpr);
 927         if (nexIt != mKeysByNonExistingParent.end()) {
 928             const std::vector<Key>::iterator eit = qBinaryFind(nexIt->second.begin(), nexIt->second.end(), key, _detail::ByFingerprint<std::less>());
 929             if (eit != nexIt->second.end()) {
 930                 nexIt->second.erase(eit);
 931             }
 932             if (nexIt->second.empty()) {
 933                 mKeysByNonExistingParent.erase(nexIt);
 934             }
 935         }
 936
 937         const Map::iterator exIt = mKeysByExistingParent.find(issuer_fpr);
 938         if (exIt != mKeysByExistingParent.end()) {
 939             const std::vector<Key>::iterator eit = qBinaryFind(exIt->second.begin(), exIt->second.end(), key, _detail::ByFingerprint<std::less>());
 940             if (eit != exIt->second.end()) {
 941                 exIt->second.erase(eit);
 942             }
 943             if (exIt->second.empty()) {
 944                 mKeysByExistingParent.erase(exIt);
 945             }
 946         }
 947     }
 948     endRemoveRows();
 949 }
 950
 951 // static
 952 AbstractKeyListModel *AbstractKeyListModel::createFlatKeyListModel(QObject *p)
 953 {
 954     AbstractKeyListModel *const m = new FlatKeyListModel(p);
 955 #ifdef KLEO_MODEL_TEST
 956     new ModelTest(m, p);
 957 #endif
 958     return m;
 959 }
 960
 961 // static
 962 AbstractKeyListModel *AbstractKeyListModel::createHierarchicalKeyListModel(QObject *p)
 963 {
 964     AbstractKeyListModel *const m = new HierarchicalKeyListModel(p);
 965 #ifdef KLEO_MODEL_TEST
 966     new ModelTest(m, p);
 967 #endif
 968     return m;
 969 }
 970
 971 #include "keylistmodel.moc"
 972
 973 /*!
 974   \fn AbstractKeyListModel::rowAboutToBeMoved( const QModelIndex & old_parent, int old_row )
 975
 976   Emitted before the removal of a row from that model. It will later
 977   be added to the model again, in response to which rowMoved() will be
 978   emitted. If multiple rows are moved in one go, multiple
 979   rowAboutToBeMoved() signals are emitted before the corresponding
 980   number of rowMoved() signals is emitted - in reverse order.
 981
 982   This works around the absence of move semantics in
 983   QAbstractItemModel. Clients can maintain a stack to perform the
 984   QModelIndex-mapping themselves, or, e.g., to preserve the selection
 985   status of the row:
 986
 987   \code
 988   std::vector<bool> mMovingRowWasSelected; // transient, used when rows are moved
 989   // ...
 990   void slotRowAboutToBeMoved( const QModelIndex & p, int row ) {
 991       mMovingRowWasSelected.push_back( selectionModel()->isSelected( model()->index( row, 0, p ) ) );
 992   }
 993   void slotRowMoved( const QModelIndex & p, int row ) {
 994       const bool wasSelected = mMovingRowWasSelected.back();
 995       mMovingRowWasSelected.pop_back();
 996       if ( wasSelected )
 997           selectionModel()->select( model()->index( row, 0, p ), Select|Rows );
 998   }
 999   \endcode
1000
1001   A similar mechanism could be used to preserve the current item during moves.
1002 */
1003
1004 /*!
1005   \fn AbstractKeyListModel::rowMoved( const QModelIndex & new_parent, int new_parent )
1006
1007   See rowAboutToBeMoved()
1008 */