[PATCH 1 of 4] obsolete: track node versions

[Jun Wu]

# HG changeset patch
# User Jun Wu <quark at fb.com>
# Date 1489385975 25200
#      Sun Mar 12 23:19:35 2017 -0700
# Node ID dec2b2328ef19c166f0ed1cb711b6c99dc9c590a
# Parent  8a17c541177f32348e248608b6a9dfd7fefdf517
# Available At https://bitbucket.org/quark-zju/hg-draft
#              hg pull https://bitbucket.org/quark-zju/hg-draft -r dec2b2328ef1
obsolete: track node versions

This is the first step to support obs cycle nicely.

The core idea is straightforward,

  A new marker "X -> Y" has the intention to make Y visible.

So if we know "X -> Y" is not older than another marker "Y -> ...", the
latter gets ignored. It's "not older than", not "newer", because then a
single changeset can be revived by "X -> X" (plus the "cancel out" property,
see below).

Then we just need to figure out how to sort the markers - i.e. defining
their "version"s. My very first idea is to use the offsets of markers stored
in obsstore, which is unambiguous. While marmoute suggested that the "date"
field makes more sense if markers are exchanged - the offsets are local
while the dates are global. And that's what this patch uses. If two markers
form a cycle and have a same date, they "cancel out" automatically, like
what darcs deals with conflicts - a reasonable behavior.

Note that sorting all markers naively by date works but is very slow. My
hg-committed has 11k markers. It takes nearly 1 second to sort them. Not to
mention sorting all markers will have difficulty with "mergemarkers" or
"addmarker", since they may require sorting all the markers again, which is
an unacceptable time complexity.

Therefore I came up with the dynamic filter idea. That's to make "node
versions" a separate state to track. And use it to filter "successors",
"precursors", etc. dynamically. Building nodeversions on my hg-committed
repo takes about 0.1 seconds, which looks pretty good. In theory it should
have similar time complexity to building "successors", which is acceptable.

diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -499,4 +499,11 @@ def _addchildren(children, markers):
                 children.setdefault(p, set()).add(mark)
 
+ at util.nogc
+def _bumpversions(nodeversions, markers):
+    for mark in markers:
+        date = mark[4][0]
+        for suc in mark[1]:
+            nodeversions[suc] = max(nodeversions.get(suc, -1), date)
+
 def _checkinvalidmarkers(markers):
     """search for marker with invalid data and raise error if needed
@@ -535,4 +542,11 @@ class obsstore(object):
         self._readonly = readonly
 
+        # the latest versions of possibly "revived" nodes. currently we use the
+        # creation date of markers as versions. so this is {node: date}
+        # A marker with successor=REVS will bump REVS to the version of the
+        # date of that marker.
+        # A marker with date <= nodeversions.get(precursor, -1) is invisible.
+        self._nodeversions = {}
+
     def __iter__(self):
         return iter(self._all)
@@ -643,4 +657,5 @@ class obsstore(object):
         self._version, markers = _readmarkers(data)
         markers = list(markers)
+        _bumpversions(self._nodeversions, markers)
         _checkinvalidmarkers(markers)
         return markers
@@ -676,4 +691,5 @@ class obsstore(object):
         if self._cached('children'):
             _addchildren(self.children, markers)
+        _bumpversions(self._nodeversions, markers)
         _checkinvalidmarkers(markers)