From patchwork Thu May 18 18:23:57 2017
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [3,of,6] hidden: add rootset class
From: Durham Goode <durham@fb.com>
X-Patchwork-Id: 20678
Message-Id: <3c0381b4b5687dcd53d5.1495131837@dev111.prn1.facebook.com>
To: <mercurial-devel@mercurial-scm.org>
Date: Thu, 18 May 2017 11:23:57 -0700

# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1495129620 25200
#      Thu May 18 10:47:00 2017 -0700
# Node ID 3c0381b4b5687dcd53d5b05c94ffa989ff3133b2
# Parent  35235b1cefb101dad0672a4c4ee9486fba8b935b
hidden: add rootset class

Adds a rootset class that acts like a set of commits where a given commit being
in the set implies that all descendants are also in the set. It stores this data
in as a series of roots for the set and validates that the set is consistent
when anything is added or removed.

diff --git a/mercurial/hidden.py b/mercurial/hidden.py
new file mode 100644
--- /dev/null
+++ b/mercurial/hidden.py
@@ -0,0 +1,137 @@
+# hidden.py - hidden commit storage and maintenance logic
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+from __future__ import absolute_import
+
+from .i18n import _
+from .node import bin, hex
+from . import (
+    error,
+)
+
+class rootset(object):
+    """A commit set like object where a commit being in the set implies that all
+    descendants of that commit are also in the set.
+    """
+    def __init__(self, repo, opener, name):
+        self.repo = repo
+        self.opener = opener
+        self.name = name
+        self.filename = "%s.roots" % name
+        self.path = opener.join(self.filename)
+        self.dirty = False
+        self.roots = None
+        self._cache = None
+
+    def _deserialize(self, raw):
+        repo = self.repo
+        return set(bin(n) for n
+                   in raw.split(',')
+                   if n and bin(n) in repo.changelog.nodemap)
+
+    def _serialize(self):
+        return ','.join(hex(n) for n in sorted(self.roots))
+
+    def _write(self, fp):
+        fp.write(self._serialize())
+        self.dirty = False
+
+    def __nonzero__(self):
+        self._load()
+        return len(self.roots) != 0
+
+    def _load(self):
+        if self.roots is None:
+            if self.opener.exists(self.filename):
+                raw = self.opener.read(self.filename)
+                self.roots = self._deserialize(raw)
+            else:
+                self.roots = set()
+
+            self._fillcache()
+            self.dirty = False
+
+    def _fillcache(self):
+        cl = self.repo.changelog
+        realroots = list(cl.rev(n) for n in self.roots
+                         if n in cl.nodemap)
+        if not realroots:
+            self._cache = set()
+        else:
+            truerevs = cl.descendants(realroots)
+            self._cache = set(cl.node(r) for r in truerevs)
+            self._cache.update(self.roots)
+
+    def __contains__(self, node):
+        self._load()
+        if isinstance(node, int):
+            raise RuntimeError("%s should be a node", node)
+        return node in self._cache
+
+    def set(self, tr, node, value, childmap=None):
+        """Sets the given node to the given True/False value.
+
+        If setting to True, this function checks that the children are already
+        True and throws an exception if not.
+
+        If setting to False, ancestor commits that should now also be False are
+        automatically updated to be False as well.
+
+        The difference in behavior is for performance reasons. Ideally we would
+        automatically update the set when setting to True, but most updates come
+        in topological order (highest rev first), which means repeatedly setting
+        values to True is O(n^2) (since every set has to walk descendants).
+        """
+        if isinstance(node, int):
+            raise RuntimeError("%s should be a node", node)
+        self._load()
+        if value == (node in self._cache):
+            return
+
+        cl = self.repo.changelog
+        # If changing to true
+        if value:
+            # Make it a root and remove old roots
+            if childmap is not None:
+                children = childmap.get(cl.rev(node))
+                childrennodes = set(cl.node(r) for r in children)
+            else:
+                childrennodes = cl.children(node)
+            if any(c for c in childrennodes if c not in self._cache):
+                raise error.Abort(_("cannot make node hidden unless children "
+                                    "are already hidden"))
+            self.roots.difference_update(childrennodes)
+            self.roots.add(node)
+
+            # Update cache
+            self._cache.add(node)
+        else:
+            # If changing to false, move ancestor roots forward
+            newlyvisible = self.repo.revs('%ln::%n', self.roots, node)
+            newlyvisiblenodes = list(cl.node(r) for r in newlyvisible)
+            self._cache.difference_update(newlyvisiblenodes)
+            self.roots.difference_update(newlyvisiblenodes)
+
+            # Add new roots to maintain truthy-ness of revs unrelated to this
+            # change.
+            newroots = self.repo.revs(
+                '(children(%ld) - ancestors(%n)) - descendants(%ln)',
+                newlyvisible, node, self.roots
+            )
+            self.roots.update(cl.node(r) for r in newroots)
+
+        self.dirty = True
+        tr.addfilegenerator(self.name, (self.filename,), self._write,
+                            location='')
+        tr.hookargs['%s_changed' % self.name] = '1'
+
+    def __iter__(self):
+        self._load()
+        for node in self._cache:
+            yield node
+
+    def __len__(self):
+        self._load()
+        return len(self._cache)