EVOLUTION-NINJA

Edit File: thread-refs.txt

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) child_node.parent_link_refcount++ 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: // #1: a -> b (a.ref=1, b.ref=1) // #2: b -> a (a.ref=2, b.ref=2) // #3: c -> a -> b (a.ref=3, b.ref=3, c.ref=1) // 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 child_node.child_unref_rebuilds = true 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) if parent.child_unref_rebuilds return false child.parent_link_refcount-- 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 if node.expunge_rebuilds 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).