IMAP: Handle missing UIDNEXT gracefully

Some ancient IMAP servers (I'm looking at you, Courier) do not report
UIDNEXT during SELECTs. This is of course suboptimal as it forces
Trojita to use a very inefficient syncing algorithm, but we should at
least prevent expensive trashing of the whole mailbox content, including
caches and the in-memory structure.

Luke-jr on IRC reported that when this happens on a big mailbox, the
ThreadingMsgListModel performs an extremely costly operation in its
pruneTree(). This is related to the way how we handle deletions at that
layer, by setting the internal ptr to 0. These messages are then pruned
one-by-one, and each of these deletes leads to a subsequent fixup of all
its siblings. An actual reported runtime was on the order of 45s with a
pretty beefy CPU. This patch does not fix the root cause of that
slowness (inefficient handleRowsDeleted/pruneTree), but it actually
prevents it from happening during the initial sync. It would be still
good to have an optimized threading model, but that is a topic for some
future patch.

I'm a little bit worried because this code doesn't raise any error if
the UID list changes in an incompatible way. It would be cool if it
checked the list of previously known UIDs and scream out loudly on
"impossible" changes, such as when a random UID gets inserted in the
middle or at the beginning.

Change-Id: I0501a8a9df969cef78b9f1bd12974fa2288b9129
CCBUG: 340241
Measure performance of mass deletes on the threading model

Change-Id: If79107083c9377610762ca535e608c9fbdbc53c1
CCBUG: 340241
Use QVector for passing lists of UIDs

OK, this is a big patch. Stuff started when I was profiling quite a slow
operation of mass expunges which was reported by Luke-jr on IRC. Some
profiling indicated that quite a lot of time was spent within
QListData::append. Adding a call to QList::reserve didn't help that
much, while replacing this with a QVector led to interesting results.
The cache format stays the same -- QDataStream uses the same
serialization format for both, which is cool.

Unfortunately, this change propagated into quite a few places. As I was
modifying the code anyway, I decoded to do it properly, with typedefs
and what not. Of course, QVector and QList have slightly different APIs,
especially the removeOne/removeAll/removeAt vs. just remove (until Qt
5.4 which actually added compatibility API, but we cannot depend on 5.4
yet).

The speed improvements suggest going from 2.5 to 1.5s on a synthetic
benchmark, Looking at callgrind's output, the total time spent in
Imap::Mailbox::Model::saveUidMap went from 34% to ~17%, which is IMHO a
pretty cool improvement.

Majority of time is now spent in comparing strings when determining
unread status of flags -- that's the next item on my list, because this
test exercises that code path a lot, again in an O(n^2) manner.

Change-Id: Ifb86903118b996c4bf5764965c06f4145eda6e07
Speed up rechecking of message flags

The old code was calling QString's operator==, which in the end leads to
comparing stuff byte-by-byte just to see if they happen to be the same
(with, I hope, a quick path for comparing identical objects). However,
we have an architecture which guarantees that the system flags are
always implicitly shared, and hence their D-pointers are the same.

This change speeds up things at least by a factor of two by comparing
the D-pointers directly. As a bonus, it also adds an optimization for a
special case of TreeItemMsgList::recalcVariousMessageCounts by looking
for the two flags which are needed at once.

Change-Id: Ie240307550b3c11f8c782493194bbe7ac0c5fed8
Do not consult all messages for flags when just a single one got deleted

This cuts the time spent in handleExpunge to about a 1/3 compared to
HEAD~1. The total savings compared to the state before we switched to
QVector amount to a speedup by a factor of eight (16e9 callgrind
instructions -> 2e9 instructions).

Change-Id: I6b45e15ab689accf458c421e29161e010aad4e91
Use iterators instead of operator[] for iterating a QVector

Both of these should be essentially free, but it happens that the debug
builds of Qt use boundary checking in the operator[], but not when using
iterators. Since there's absolutely no reason to use boundary checking
with this already-checked iteration, let's make sure it isn't needlessly
slow even in debug builds.

Change-Id: I9787c05f6489789bb1dad7bd2ea762436fc87fd4
Do not build and save the UID map twice in a row

All tests pass, so this appears to be a safe change. I'm actually
surprised that this too-eager saving wasn't causing any trouble except
performance issues.

Change-Id: Id6fe19f346c24a1351d64f71018583b1b3e5abe9
Test expunge performance on a bigger number of messages

The code is better now, so let's test it with something more noticeable
than mere 10k deletions -- that is nothing. At the same time, we aren't
there just yet, so 100k is out of question for now, at least until
expunges are batched prior to that UID map rebuild.

Change-Id: I7d233b164f49fa60dbca677e5215a8627cbe8c6d
Defer UID map saving when there's heavy incoming traffic

Previously, the seq->UID map would get rebuilt and saved into the DB
upon every EXPUNGE. That was quite expensive, as the test which deletes
15k out of 30k messages quite clearly indicates. This code makes sure
that the rate in which the data are saved is limited.

Originally, this was implemented by maintaining a pretty short time
window. The goal was to prevent excessive actions while the responses
still continue to flow, but at the same time to avoid excessive delays
in case the burst stops. I wanted the time window to be reasonable small
so as not to require adding multiple qWait()s into other tests. A single
EXPUNGE is typically less than 18 bytes ("* 1234567 EXPUNGE\r\n"), so in
order to send 100+ of them in a 10ms, it could require a 180 kBps, i.e.
about 1.44 Mbps bandwidth (at least as a burst). That might indeed be a
bit too high for a cell phone connection :(, as Thomas pointed out.
That's why the time window is a bit longer now.

Also make sure that no events get lost when the KeepMailboxOpenTask dies
prior to a timer firing, such as when switching mailboxes.

Change-Id: I77e638b3278918961d316cf4a615b5c78d15a79d
Test tree node promoting while pruning the threading tree

This adds an explicit test which makes sure that the
ThreadingMsgListModel::pruneTree will do the right thing when it decides
to visit a three node whose preceding sibling was already pruned from
the tree. There might be some lurking asserts in there which would get
invalidated by that move of node offset fixup to happen for all nodes at
once.

Change-Id: I26027e1a79a8dcece7c4e23ece1959152a594b3a
Speed up pruning of the threading tree

Previously, a lot of time was spent on looking up many items in an
internal hash table, and additional time was wasted by renumbering the
siblings all the time in case multiple removals took place at the same
time.

While each EXPUNGE is still being processed on its own, the actual
removal of each of these items now happens much faster (roughly 30% on a
synthetic benchmark based upon the callgrind's instruction fetch
counts).

Change-Id: I4fa6e0a884859d0105fc535c70ca1d0fb3c57d5b
Merge topic 'threading-expunges'

* changes:
  Speed up pruning of the threading tree
  Test tree node promoting while pruning the threading tree
  Defer UID map saving when there's heavy incoming traffic
  Test expunge performance on a bigger number of messages
  Do not build and save the UID map twice in a row
  Use iterators instead of operator[] for iterating a QVector
  Do not consult all messages for flags when just a single one got deleted
  Speed up rechecking of message flags
  Use QVector for passing lists of UIDs
  Measure performance of mass deletes on the threading model
  IMAP: Handle missing UIDNEXT gracefully