JWZ email threading in Go: reconstructing conversation trees from Message-ID and References headers

Email threads aren't stored as threads by SMTP. They are individual messages that reference each other via headers. Reconstructing the conversation tree from a flat list of messages is the job of the JWZ algorithm, originally described by Jamie Zawinski for Netscape Mail. Here's how KaryoSpace implements it in Go.

The three headers

Three headers carry threading information. Message-ID is a unique identifier for the message, generated by the sender's mail client. In-Reply-To contains the Message-ID of the message being replied to. References contains the Message-ID of every message in the thread so far, in order. Together, these three headers let you reconstruct the full conversation tree.

type EmailHeaders struct {
    MessageID  string   // e.g. 
    InReplyTo  string   // Message-ID of parent
    References []string // All ancestors, oldest first
    Subject    string
    Date       time.Time
}

func parseThreadingHeaders(raw string) EmailHeaders {
    var h EmailHeaders
    for _, line := range strings.Split(raw, "
") {
        if strings.HasPrefix(line, "Message-ID:") {
            h.MessageID = extractID(line)
        } else if strings.HasPrefix(line, "In-Reply-To:") {
            h.InReplyTo = extractID(line)
        } else if strings.HasPrefix(line, "References:") {
            h.References = extractAllIDs(line)
        }
    }
    return h
}

Building the thread container tree

JWZ works in two passes. The first pass builds a flat map from Message-ID to a container struct. The second pass links containers into a parent-child tree. A container may exist before its message arrives (from a References header in a later message), in which case it's a "dummy" container that gets filled in when the message arrives.

type ThreadContainer struct {
    Message  *EmailMessage
    Children []*ThreadContainer
    Parent   *ThreadContainer
    MessageID string
}

func buildThreadMap(messages []*EmailMessage) map[string]*ThreadContainer {
    containers := map[string]*ThreadContainer{}

    for _, msg := range messages {
        // Ensure this message has a container
        c, ok := containers[msg.Headers.MessageID]
        if !ok {
            c = &ThreadContainer{MessageID: msg.Headers.MessageID}
            containers[msg.Headers.MessageID] = c
        }
        c.Message = msg

        // Link References chain: each reference is parent of next
        refs := msg.Headers.References
        if msg.Headers.InReplyTo != "" {
            // InReplyTo is authoritative if References is missing
            if len(refs) == 0 || refs[len(refs)-1] != msg.Headers.InReplyTo {
                refs = append(refs, msg.Headers.InReplyTo)
            }
        }
        for i, refID := range refs {
            if _, ok := containers[refID]; !ok {
                containers[refID] = &ThreadContainer{MessageID: refID}
            }
            if i > 0 {
                parent := containers[refs[i-1]]
                child := containers[refID]
                if child.Parent == nil && !wouldCycle(child, parent) {
                    child.Parent = parent
                    parent.Children = append(parent.Children, child)
                }
            }
        }
    }
    return containers
}

Finding thread roots

After the first pass, thread roots are containers with no parent. In a well-formed thread, there's one root (the first message). In practice, missing messages and malformed References headers create multiple roots. KaryoSpace groups multiple roots under a synthetic root keyed by the subject line (normalised by stripping Re:/Fwd: prefixes).

func findRoots(containers map[string]*ThreadContainer) []*ThreadContainer {
    var roots []*ThreadContainer
    for _, c := range containers {
        if c.Parent == nil {
            roots = append(roots, c)
        }
    }
    // Sort roots by date of earliest message in subtree
    sort.Slice(roots, func(i, j int) bool {
        return earliestDate(roots[i]).Before(earliestDate(roots[j]))
    })
    return roots
}

func normalizeSubject(subj string) string {
    subj = replyPrefixRe.ReplaceAllString(subj, "")
    return strings.TrimSpace(strings.ToLower(subj))
}

MongoDB storage

Rather than recomputing the thread tree on every page load, KaryoSpace stores a thread_id field on each email message. When a message arrives, the threading logic runs immediately and assigns it to an existing thread or creates a new one. The thread document stores the root message ID and the sorted list of participant IDs.

type EmailThread struct {
    ID           primitive.ObjectID `bson:"_id"`
    OrgID        string             `bson:"org_id"`
    UserID       string             `bson:"user_id"`
    Subject      string             `bson:"subject"`
    RootMsgID    string             `bson:"root_msg_id"`
    Participants []string           `bson:"participants"`
    MessageCount int                `bson:"message_count"`
    LastAt       time.Time          `bson:"last_at"`
    HasUnread    bool               `bson:"has_unread"`
}

The edge cases that matter