dymokomi/luced-message
Source of release 0.5.0
0.5.0 / src / mail_threads.lucb
## Conversations: a folder's messages grouped the way Mail groups them. A reply joins
## the message its In-Reply-To names; replies to the same message missing from the
## folder join each other; and a reply whose original cannot be found by ID joins the
## message with the same subject once its Re:/Fwd: prefixes are stripped. Threads are
## ordered by their newest message, newest first, and so are the messages inside one.
import memory
from luce_std.collections import List
from mail_store import Row
## One key and the row it came from, for sorted lookup.
struct Keyed:
var digest: u64
var row: u32
## A folder's conversations.
pub struct Threads:
## Row positions, a thread's members together, threads newest first.
var order: List[u32]
## Where each thread starts in `order`, and one past the last thread's end.
var starts: List[u32]
## How many conversations there are.
pub func count() -> usize:
return self.starts.length() - 1 if self.starts.length() > 0 else 0
## How many messages conversation `nth` has.
pub func size(nth: usize) -> usize:
return (usize)(self.starts.at(nth + 1) - self.starts.at(nth))
## The row of the `member`-th newest message of conversation `nth`.
pub func member(nth: usize, member: usize) -> u32:
return self.order.at((usize)self.starts.at(nth) + member)
pub func close():
self.order.destroy()
self.starts.destroy()
## FNV-1a of `text`, for grouping by message ID or subject.
func digest_of(text: const u8[]) -> u64:
var value: u64 = 0xcbf29ce484222325
for byte in text:
value = (value ^ byte) *% 0x100000001b3
return value
## `subject` without its reply and forward prefixes (Re:, Fwd:, Fw:, AW:, SV:, WG:),
## repeated or nested, and without surrounding spaces.
pub func base_subject(subject: const u8[]) -> const u8[]:
var text = subject
while true:
var start: usize = 0
while start < text.length and text[start] == ' ':
start += 1
text = text[start..]
var stripped = false
for prefix in ["re:", "fwd:", "fw:", "aw:", "sv:", "wg:"]:
if text.length >= prefix.length:
var matches = true
for at in 0..<prefix.length:
let byte = text[at]
let lower = byte + 32 if byte >= 'A' and byte <= 'Z' else byte
if lower != prefix.bytes[at]:
matches = false
break
if matches:
text = text[prefix.length..]
stripped = true
break
if not stripped:
break
var end = text.length
while end > 0 and text[end - 1] == ' ':
end -= 1
return text[0..<end]
## Whether `subject` starts with a reply or forward prefix.
func is_reply(subject: const u8[]) -> bool:
return base_subject(subject).length != subject.length and base_subject(subject).length > 0
## Union-find over rows.
struct Groups:
var parent: u32[]
func find(row: u32) -> u32:
var current = row
while self.parent[current] != current:
self.parent[current] = self.parent[self.parent[current]]
current = self.parent[current]
return current
func join(a: u32, b: u32):
let root_a = self.find(a)
let root_b = self.find(b)
if root_a != root_b:
self.parent[root_b] = root_a
## Sort `keys` by digest (a merge sort into `scratch`).
func sort_keys(keys: Keyed[], scratch: Keyed[]):
var width: usize = 1
while width < keys.length:
var start: usize = 0
while start < keys.length:
let middle = start + width if start + width < keys.length else keys.length
let end = start + 2 * width if start + 2 * width < keys.length else keys.length
var left = start
var right = middle
for out in start..<end:
if right >= end or (left < middle and keys[left].digest <= keys[right].digest):
scratch[out] = keys[left]
left += 1
else:
scratch[out] = keys[right]
right += 1
start = end
for at in 0..<keys.length:
keys[at] = scratch[at]
width *= 2
## The first position in sorted `keys` with digest `digest`, or none.
func lower_bound(keys: const Keyed[], digest: u64) -> usize?:
var low: usize = 0
var high = keys.length
while low < high:
let middle = (low + high) // 2
if keys[middle].digest < digest:
low = middle + 1
else:
high = middle
if low < keys.length and keys[low].digest == digest:
return low
return none
## Whether row `a` is newer than row `b`: by date, then UID.
func newer(rows: const List[Row]*, a: u32, b: u32) -> bool:
let first = rows.at((usize)a)
let second = rows.at((usize)b)
if first.date != second.date:
return first.date > second.date
return first.uid > second.uid
## Group `rows` into conversations.
pub func thread(rows: const List[Row]*) -> Threads!:
var threads: Threads
errdefer threads.close()
let count = rows.length()
if count == 0:
try threads.starts.append(0)
return threads
var groups = Groups(parent = try new u32[count] --- in memory.heap)
defer free(groups.parent) in memory.heap
for at in 0..<count:
groups.parent[at] = (u32)at
let ids = try new Keyed[count] --- in memory.heap
defer free(ids) in memory.heap
let scratch = try new Keyed[count] --- in memory.heap
defer free(scratch) in memory.heap
for at in 0..<count:
ids[at] = Keyed(digest = digest_of(rows.at(at).message_id.bytes), row = (u32)at)
sort_keys(ids, scratch)
# A reply joins the message it answers.
for at in 0..<count:
let row = rows.at(at)
if row.in_reply_to.length == 0:
continue
if let first = lower_bound(ids, digest_of(row.in_reply_to.bytes)):
var probe = first
while probe < count and ids[probe].digest == ids[first].digest:
if rows.at((usize)ids[probe].row).message_id.bytes == row.in_reply_to.bytes:
groups.join(ids[probe].row, (u32)at)
probe += 1
# Replies to the same missing message join each other.
let replies = try new Keyed[count] --- in memory.heap
defer free(replies) in memory.heap
for at in 0..<count:
let row = rows.at(at)
replies[at] = Keyed(digest = digest_of(row.in_reply_to.bytes) if row.in_reply_to.length > 0 else 0, row = (u32)at)
sort_keys(replies, scratch)
for at in 1..<count:
if replies[at].digest != 0 and replies[at].digest == replies[at - 1].digest:
groups.join(replies[at - 1].row, replies[at].row)
# A reply still alone joins the thread of the same base subject.
let subjects = try new Keyed[count] --- in memory.heap
defer free(subjects) in memory.heap
for at in 0..<count:
let base = base_subject(rows.at(at).subject.bytes)
subjects[at] = Keyed(digest = digest_of(base) if base.length > 0 else 0, row = (u32)at)
sort_keys(subjects, scratch)
var start: usize = 0
while start < count:
var end = start + 1
while end < count and subjects[end].digest == subjects[start].digest:
end += 1
if subjects[start].digest != 0 and end - start > 1:
# Join only when a member is a reply: two unrelated "Hello"s stay apart.
var anchor: u32? = none
for at in start..<end:
let row = subjects[at].row
if is_reply(rows.at((usize)row).subject.bytes):
if let first = anchor:
groups.join(first, row)
else:
anchor = row
if let first = anchor:
for at in start..<end:
let row = subjects[at].row
if groups.find(row) == row and not is_reply(rows.at((usize)row).subject.bytes):
groups.join(first, row)
start = end
# Order rows: by their thread's newest message, then newest first inside it.
let newest = try new u32[count] --- in memory.heap
defer free(newest) in memory.heap
for at in 0..<count:
newest[at] = 0xFFFFFFFF
for at in 0..<count:
let root = groups.find((u32)at)
if newest[root] == 0xFFFFFFFF or newer(rows, (u32)at, newest[root]):
newest[root] = (u32)at
let ordered = try new u32[count] --- in memory.heap
defer free(ordered) in memory.heap
for at in 0..<count:
ordered[at] = (u32)at
let spare = try new u32[count] --- in memory.heap
defer free(spare) in memory.heap
var width: usize = 1
while width < count:
var begin: usize = 0
while begin < count:
let middle = begin + width if begin + width < count else count
let end = begin + 2 * width if begin + 2 * width < count else count
var left = begin
var right = middle
for out in begin..<end:
let take_left = right >= end or (left < middle and not before(rows, &groups, newest, ordered[right], ordered[left]))
if take_left:
spare[out] = ordered[left]
left += 1
else:
spare[out] = ordered[right]
right += 1
begin = end
for at in 0..<count:
ordered[at] = spare[at]
width *= 2
for at in 0..<count:
if at == 0 or groups.find(ordered[at]) != groups.find(ordered[at - 1]):
try threads.starts.append((u32)at)
try threads.order.append(ordered[at])
try threads.starts.append((u32)count)
return threads
## Whether row `a` goes before row `b`: its thread is newer, or, in one thread, it is.
func before(rows: const List[Row]*, groups: Groups*, newest: const u32[], a: u32, b: u32) -> bool:
let root_a = groups.find(a)
let root_b = groups.find(b)
if root_a != root_b:
return newer(rows, newest[root_a], newest[root_b])
return newer(rows, a, b)