Mark Sapiro writes:
There is an article on threading at <https://www.jwz.org/doc/threading.html> and an RFC <https://www.rfc-editor.org/rfc/rfc5256.html>. These describe algorithms which are fairly complex, but if someone wanted to try to implement them in HyperKitty, we would certainly consider the implementation.
Ouch. I didn't realize we didn't use Jamie's algorithm. It's not that hard to implement[1], and it's robust and extremely efficient[2], modulo the cost of accessing message-id, in-reply-to, and references.
A robust, tested, and documented implementation sounds like a GSoC project to me. And a PyPI package, though that would be somewhat harder.
Footnotes: [1] It took me about a day to get it mostly working in Elisp, and most of the difficulty and the remaining issues were due to working around bugs in the MUA that caused uncaught exceptions in the MUA.
[2] It's multipass, but it's worst-case and average-case linear. Worst-case is linear because the line-length restriction keeps the length of references down to about 15 at most.