Optimistic incremental THREAD=REFERENCES
Step (1) is the slowest stage for building a THREAD=REFERENCES tree. If its
result tree is permanently saved, the following thread builds can be based
on it by updating the tree incrementally.
Adding new messages to the tree is simple: simply follow the normal rules
as when building a new tree from scratch. Expunging messages gets more
problematic though.
Each node in the tree keeps a "link reference count" which specifies how
many messages contain a "this message" -> "parent message" reference
(number of links to parent node). The first reference is usually added by
the message's own References: or In-Reply-To: header and the latter
references are added by References: headers. This link refcount must be
updated when adding and expunging messages. When the link refcount drops to
zero, the message becomes a root. The link refcount doesn't tell much about
the number of children the node has, because References: headers may
reference any number of its ancestors.
The optimistic approach assumes that usually there are no problematic
links. In such case expunging a message simply updates the link refcounts
and marks the message's node as expunged. Expunged messages may still act
as dummy nodes. The node may be removed only after there are no nodes which
point to it.
Problematic links are handled by marking nodes affected by them. If such a
node is expunged or its link is unreferenced, the thread tree must be
rebuilt. This is assumed to be a rarely occurring event. The problematic
cases are:
1) Duplicate Message-ID: headers. If the first message having it is
expunged, the thread tree must be rebuilt.
2) Message-ID loops. If a message referencing the looping path gets
expunged, the loop may break and the thread tree must be rebuilt. Because
it can't be determined easily which loops get broken by which expunges,
this case can be handled in a bit easier way: When detecting a loop between
parent and child, rebuild the tree if any link between the parent and child
gets unreferenced.
3) A message changes its parent because an earlier message's References:
header contained a different link. If the message gets expunged, the thread
tree must be rebuilt to get the original parent back.
4) A link in a message's References: header is ignored, because the
referenced child already specified a different parent to itself. If the
message gets expunged, the thread tree must be rebuilt to determine its new
parent.
5) A link in a message's References: header is ignored, because an earlier
message's References: header already specified a different link. If the
earlier message gets expunged, the parent may change. The earlier message
could be found out quickly by keeping some extra state (or with a slow
scan), but since this is assumed to be a rare problem, there's an easier
(but less specific) way to handle this: Rebuild the tree if a link to the
child node is unreferenced (or alternatively if a link to the original
parent node is unreferenced, but it probably happens more often).
Pseudocode:
node {
parent: Pointer to parent node. Children pointers aren't required.
uid: Message's UID (0 = expunged or never even existed)
parent_link_refcount: Number of messages containing "this message" -> "parent
message" link, i.e. "number of links to parent node". However since parents
can change, not all of these references might be from our current child
nodes. When this refcount reaches 0, it means we must detach from our
parent.
expunge_rebuilds: If this message gets expunged, rebuild the thread tree.
child_unref_rebuilds: If a link between this node and its child gets
unreferenced, rebuild the thread tree.
}
link_reference(parent_node, child_node)
if is_ancestor(child_node, parent_node)
// child_node is an ancestor of parent_node. Adding child_node ->
// parent_node would introduce a loop. If any messages referencing the
// path between parent_node's parent and child_node get expunged, we
// have to rebuild the tree because the loop might break. For example:
// Expunging #3 wouldn't break the loop, but expunging #1 would.
for node in nodes[parent_node.parent .. child_node]
node.child_unref_rebuilds = true
else if child_node.parent == parent_node
// The same link already exists
else
// Set parent_node as child_node's parent
if child_node.parent == NIL
child_node.parent = parent_node
else
// Conflicting parent already exists, keep the original.
// We get here only when handling References: header.
if child_node.uid != 0
// We've already seen this message. It specifies its own parent and
// it doesn't matter what any other reference says. The only way its
// parent can change is if the message itself gets expunged.
child_node.expunge_rebuilds = true
else
// Message doesn't exist, so it was one of the node's children
// that created the original reference. If that reference gets
// dropped, the parent is changed. We could catch this in one of
// several ways:
// a) Link to original parent node gets unreferenced
// b) Link to this node gets unreferenced
// c) Any of the child nodes gets expunged
// b) is probably the least likely to happen, so use it
thread_add_msg(uid)
// get the Message-IDs as specified by the thread spec
(msgid, parent_msgid, references) = message_get_thread_headers(uid)
if msgid != NIL
if nodes[msgid].uid == 0
nodes[msgid].uid = uid
else
// duplicate Message-ID. if the original ever gets expunged,
// rebuild the thread tree
nodes[msgid].expunge_rebuilds = true
msgid = NIL
if msgid == NIL
msgid = get_unique_msg_id()
node = nodes[msgid]
if node.parent != NIL and
(parent_msgid == NIL or node.parent.msgid != parent_msgid)
// Conflicting parent, remove it. If this message gets expunged, we have
// to revert back to the original parent.
node.parent = NIL
node.expunge_rebuilds = true
if parent_msgid != NIL
link_reference(nodes[parent_msgid], node)
// go through References (skipping the last one)
for (ref_parent, ref_child) in references
link_reference(nodes[ref_parent], nodes[ref_child])
unref_link(parent, child)
return false
if child.parent_link_refcount == 0
child.parent = NIL
return true
// returns false if thread tree needs to be rebuilt
thread_expunge_msg(uid)
// get the Message-IDs as specified by the thread spec
(msgid, in_reply_to_msgid, references) = message_get_thread_headers(uid)
node = nodes[msgid]
if node.uid != uid
// Removing a duplicate Message-ID
return false
return false
if parent_msgid != NIL and
not unref_link(nodes[parent_msgid], nodes[child_msgid])
return false
if references != NIL
// go through References
for (parent_msgid, child_msgid) in references
if not unref_link(nodes[parent_msgid], nodes[child_msgid])
return false
last_parent_msgid = references.last
else if in_reply_to_msgid != NIL
last_parent_msgid = in_reply_to_msgid
if last_parent_msgid != NIL and
not unref_link(nodes[last_parent_msgid], node)
return false
// mark this node as expunged
node.uid = 0
return true
thread_iterate()
root_nodes = []
referenced = []
children = [][]
// Steps (2) and (3)
for node in nodes
if node.parent != NIL
root_nodes[] = node
else
referenced[node.parent] = true
if node.uid != 0
// Find the node's first non-dummy parent and add the node as its child.
// If there are no non-dummy parents, add it as the highest dummy's
// child.
nondummy_parent = node.parent
while nondummy_parent.uid == 0 and nondummy_parent.parent != NIL
nondummy_parent = nondummy_parent.parent
children[nondummy_parent][] = node
for node in root_nodes
if node.uid == 0
if children[node] == NIL
// remove dummy roots that have no children.
delete(node)
else if count(children[node]) == 1
// dummy root has a single child, replace the root with its child
node = children[node]
for node in nodes
if node.uid == 0 and !referenced[node]
free(node)
// root_nodes and children now contain a tree equivalent to a tree built by
// THREAD=REFERENCES specification steps (1)-(3). The rest of the steps
// can be performed using them. Note that node.parent should not (and need
// not) be used because it points its parent before steps (2) and (3).