Threading algorithm

Summary:
Kavya, Charles

I've implemented a basic threading algorithm.  It's sort of complicated.

So, last week I wrote a spec for a threading algorithm. This is not the same algorithm. The algo I speced was about flattening graphs (DAGs) which is kind of complicated to code, so I tried out instead an algo which uses lists.

Here's how it works:

1. The first step is getting together all the the messages which share the same subject (this is debatable but you've got to start somewhere) and sorting them by "received_date"

2. After this, the algo starts from an empty list and inserts all the messages the one after the other using "insert_message_in_thread". insert_message_in_thread uses the in-reply-to and references: headers to insert the message at the correct position or to at least take an educated guess at it. It's quite complex, so I've made a flowchart: {F729}

I'm not sure I've been very clear. Tell me if you have questions.

Test Plan: Compare this threading algorithm with Yahoo and Gmail threading. Run it on a bigger dataset.

Reviewers: charles, kav-ya

Reviewed By: kav-ya

Subscribers: emfree, spang

Differential Revision: https://review.inboxapp.com/D267

[Note(emfree): relanding commit c093ac34903. Surprisingly, the thread_order
column does actually get added by the migration with a default value of 0. It's
just excruciatingly slow to run this on a large database. Added a default
Python value though, as there are places where we create a Message object but
don't set this (drafts and sending)]