Fix high memory usage during thread building

If only messages with threading info are loaded we can significantly
reduce the amount of memory consumed to build threads. This is because
many messages are not part of a thread. And if they are, the references
and in-reply-to headers are enough information to know that there was a
previous message. So we build the threads out of existance of the thread
roots. As long as the threading result is the same, this doesn't matter.

Signed-off-by: Christoph Wurst <christoph@winzerhof-wurst.at>

5 files changed, 47 insertions, 7 deletions

diff --git a/lib/Db/MessageMapper.php b/lib/Db/MessageMapper.php
index 011c7d7b5..9d2c14f16 100644
--- a/lib/Db/MessageMapper.php
+++ b/lib/Db/MessageMapper.php
@@ -202,7 +202,13 @@ class MessageMapper extends QBMapper {
 		$messagesQuery->select('id', 'subject', 'message_id', 'in_reply_to', 'references', 'thread_root_id')
 			->from($this->getTableName())
 			->where($messagesQuery->expr()->in('mailbox_id', $messagesQuery->createFunction($mailboxesQuery->getSQL()), IQueryBuilder::PARAM_INT_ARRAY))
-			->andWhere($messagesQuery->expr()->isNotNull('message_id'));
+			->andWhere(
+				$messagesQuery->expr()->isNotNull('message_id'),
+				$messagesQuery->expr()->orX(
+					$messagesQuery->expr()->isNotNull('in_reply_to'),
+					$messagesQuery->expr()->neq('references', $messagesQuery->createNamedParameter('[]'))
+				),
+			);
 
 		$result = $messagesQuery->execute();
 		$messages = [];
diff --git a/lib/IMAP/Threading/Container.php b/lib/IMAP/Threading/Container.php
index 71a6a1275..e57e390ac 100644
--- a/lib/IMAP/Threading/Container.php
+++ b/lib/IMAP/Threading/Container.php
@@ -33,6 +33,9 @@ class Container {
 	/** @var Message|null */
 	private $message;
 
+	/** @var string|null */
+	private $id;
+
 	/** @var bool */
 	private $root;
 
@@ -43,21 +46,25 @@ class Container {
 	private $children = [];
 
 	private function __construct(?Message $message,
+								 ?string $id = null,
 								 bool $root = false) {
 		$this->message = $message;
+		$this->id = $id;
 		$this->root = $root;
 	}
 
 	public static function root(): self {
 		return new self(
 			null,
+			null,
 			true
 		);
 	}
 
-	public static function empty(): self {
+	public static function empty(?string $id = null): self {
 		return new self(
-			null
+			null,
+			$id,
 		);
 	}
 
@@ -79,6 +86,10 @@ class Container {
 		return $this->message;
 	}
 
+	public function getId(): ?string {
+		return $this->id;
+	}
+
 	public function isRoot(): bool {
 		return $this->root;
 	}
diff --git a/lib/IMAP/Threading/ThreadBuilder.php b/lib/IMAP/Threading/ThreadBuilder.php
index a5fc3a264..5f4e25fdd 100644
--- a/lib/IMAP/Threading/ThreadBuilder.php
+++ b/lib/IMAP/Threading/ThreadBuilder.php
@@ -98,7 +98,7 @@ class ThreadBuilder {
 			foreach ($message->getReferences() as $reference) {
 				$refContainer = $idTable[$reference] ?? null;
 				if ($refContainer === null) {
-					$refContainer = $idTable[$reference] = Container::empty();
+					$refContainer = $idTable[$reference] = Container::empty($reference);
 				}
 				if (!$refContainer->hasParent()
 					&& !($parent !== null && !$parent->hasAncestor($refContainer))
@@ -149,7 +149,7 @@ class ThreadBuilder {
 
 			// Step 4.B
 			if (!$container->hasMessage() && $container->hasChildren()) {
-				if (!$container->getParent()->isRoot() && count($container->getChildren()) > 1) {
+				if (!$container->getParent()->isRoot() && count($container->getChildren()) > 0) {
 					// Do not promote
 					continue;
 				}
diff --git a/lib/Listener/AccountSynchronizedThreadUpdaterListener.php b/lib/Listener/AccountSynchronizedThreadUpdaterListener.php
index 4a9635b95..6758ac378 100644
--- a/lib/Listener/AccountSynchronizedThreadUpdaterListener.php
+++ b/lib/Listener/AccountSynchronizedThreadUpdaterListener.php
@@ -65,7 +65,7 @@ class AccountSynchronizedThreadUpdaterListener implements IEventListener {
 		$accountId = $event->getAccount()->getId();
 		$logger->debug("Building threads for account $accountId");
 		$messages = $this->mapper->findThreadingData($event->getAccount());
-		$logger->debug("Account $accountId has " . count($messages) . " messages for threading");
+		$logger->debug("Account $accountId has " . count($messages) . " messages with threading information");
 		$threads = $this->builder->build($messages, $logger);
 		$logger->debug("Account $accountId has " . count($threads) . " threads");
 		/** @var DatabaseMessage[] $flattened */
@@ -102,7 +102,7 @@ class AccountSynchronizedThreadUpdaterListener implements IEventListener {
 
 			yield from $this->flattenThreads(
 				$thread->getChildren(),
-				$threadId ?? ($message === null ? null : $message->getId())
+				$threadId ?? ($message === null ? $thread->getId() : $message->getId())
 			);
 		}
 	}
diff --git a/tests/Unit/IMAP/Threading/ThreadBuilderTest.php b/tests/Unit/IMAP/Threading/ThreadBuilderTest.php
index 99fb073bd..48074d2e1 100644
--- a/tests/Unit/IMAP/Threading/ThreadBuilderTest.php
+++ b/tests/Unit/IMAP/Threading/ThreadBuilderTest.php
@@ -475,6 +475,29 @@ class ThreadBuilderTest extends TestCase {
 		);
 	}
 
+	public function testWithVirtualParent(): void {
+		$messages = [
+			new Message('AW: s1', 'id2', ['id1']),
+		];
+
+		$result = $this->builder->build($messages, $this->logger);
+
+		$this->assertEquals(
+			[
+				[
+					'id' => null,
+					'children' => [
+						[
+							'id' => 'id2',
+							'children' => [],
+						],
+					],
+				],
+			],
+			$this->abstract($result)
+		);
+	}
+
 	/**
 	 * This is a test case from real-world data, compared to how Evolution renders the thread
 	 *