mercurial-scm/hg: mercurial/pvec.py comparison

comparison mercurial/pvec.py @ 16249:0d175ac527c1

pvec: introduce pvecs

author	Matt Mackall <mpm@selenic.com>
date	Mon, 12 Mar 2012 13:37:39 -0500
parents
children	e7cfe3587ea4

comparison

equal deleted inserted replaced

-:51e6f318bdf1
+:0d175ac527c1
+# pvec.py - probabilistic vector clocks for Mercurial
+#
+# Copyright 2012 Matt Mackall <mpm@selenic.com>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+'''
+A "pvec" is a changeset property based on the theory of vector clocks
+that can be compared to discover relatedness without consulting a
+graph. This can be useful for tasks like determining how a
+disconnected patch relates to a repository.
+Currently a pvec consist of 448 bits, of which 24 are 'depth' and the
+remainder are a bit vector. It is represented as a 70-character base85
+string.
+Construction:
+- a root changeset has a depth of 0 and a bit vector based on its hash
+- a normal commit has a changeset where depth is increased by one and
+one bit vector bit is flipped based on its hash
+- a merge changeset pvec is constructed by copying changes from one pvec into
+the other to balance its depth
+Properties:
+- for linear changes, difference in depth is always <= hamming distance
+- otherwise, changes are probably divergent
+- when hamming distance is < 200, we can reliably detect when pvecs are near
+Issues:
+- hamming distance ceases to work over distances of ~ 200
+- detecting divergence is less accurate when the common ancestor is very close
+to either revision or total distance is high
+- this could probably be improved by modeling the relation between
+delta and hdist
+Uses:
+- a patch pvec can be used to locate the nearest available common ancestor for
+resolving conflicts
+- ordering of patches can be established without a DAG
+- two head pvecs can be compared to determine whether push/pull/merge is needed
+and approximately how many changesets are involved
+- can be used to find a heuristic divergence measure between changesets on
+different branches
+'''
+import base85, util
+from node import nullrev
+_size = 448 # 70 chars b85-encoded
+_bytes = _size / 8
+_depthbits = 24
+_depthbytes = _depthbits / 8
+_vecbytes = _bytes - _depthbytes
+_vecbits = _vecbytes * 8
+_radius = (_vecbits - 30) / 2 # high probability vecs are related
+def _bin(bs):
+'''convert a bytestring to a long'''
+v = 0
+for b in bs:
+v = v * 256 + ord(b)
+return v
+def _str(v, l):
+bs = ""
+for p in xrange(l):
+bs = chr(v & 255) + bs
+v >>= 8
+return bs
+def _split(b):
+'''depth and bitvec'''
+return _bin(b[:_depthbytes]), _bin(b[_depthbytes:])
+def _join(depth, bitvec):
+return _str(depth, _depthbytes) + _str(bitvec, _vecbytes)
+def _hweight(x):
+c = 0
+while x:
+if x & 1:
+c += 1
+x >>= 1
+return c
+_htab = [_hweight(x) for x in xrange(256)]
+def _hamming(a, b):
+'''find the hamming distance between two longs'''
+d = a ^ b
+c = 0
+while d:
+c += _htab[d & 0xff]
+d >>= 8
+return c
+def _mergevec(x, y, c):
+# Ideally, this function would be x ^ y ^ ancestor, but finding
+# ancestors is a nuisance. So instead we find the minimal number
+# of changes to balance the depth and hamming distance
+d1, v1 = x
+d2, v2 = y
+if d1 < d2:
+d1, d2, v1, v2 = d2, d1, v2, v1
+hdist = _hamming(v1, v2)
+ddist = d1 - d2
+v = v1
+m = v1 ^ v2 # mask of different bits
+i = 1
+if hdist > ddist:
+# if delta = 10 and hdist = 100, then we need to go up 55 steps
+# to the ancestor and down 45
+changes = (hdist - ddist + 1) / 2
+else:
+# must make at least one change
+changes = 1
+depth = d1 + changes
+# copy changes from v2
+if m:
+while changes:
+if m & i:
+v ^= i
+changes -= 1
+i <<= 1
+else:
+v = _flipbit(v, c)
+return depth, v
+def _flipbit(v, node):
+# converting bit strings to longs is slow
+bit = (hash(node) & 0xffffffff) % _vecbits
+return v ^ (1<<bit)
+def ctxpvec(ctx):
+'''construct a pvec for ctx while filling in the cache'''
+r = ctx._repo
+if not util.safehasattr(r, "_pveccache"):
+r._pveccache = {}
+pvc = r._pveccache
+if ctx.rev() not in pvc:
+cl = r.changelog
+for n in xrange(ctx.rev() + 1):
+if n not in pvc:
+node = cl.node(n)
+p1, p2 = cl.parentrevs(n)
+if p1 == nullrev:
+# start with a 'random' vector at root
+pvc[n] = (0, _bin((node * 3)[:_vecbytes]))
+elif p2 == nullrev:
+d, v = pvc[p1]
+pvc[n] = (d + 1, _flipbit(v, node))
+else:
+pvc[n] = _mergevec(pvc[p1], pvc[p2], node)
+bs = _join(*pvc[ctx.rev()])
+return pvec(base85.b85encode(bs))
+class pvec(object):
+def __init__(self, hashorctx):
+if isinstance(hashorctx, str):
+self._bs = hashorctx
+self._depth, self._vec = _split(base85.b85decode(hashorctx))
+else:
+self._vec = ctxpvec(ctx)
+def __str__(self):
+return self._bs
+def __eq__(self, b):
+return self._vec == b._vec and self._depth == b._depth
+def __lt__(self, b):
+delta = b._depth - self._depth
+if delta < 0:
+return False # always correct
+if _hamming(self._vec, b._vec) > delta:
+return False
+return True
+def __gt__(self, b):
+return b < self
+def __or__(self, b):
+delta = abs(b._depth - self._depth)
+if _hamming(self._vec, b._vec) <= delta:
+return False
+return True
+def __sub__(self, b):
+if self | b:
+raise ValueError("concurrent pvecs")
+return self._depth - b._depth
+def distance(self, b):
+d = abs(b._depth - self._depth)
+h = _hamming(self._vec, b._vec)
+return max(d, h)
+def near(self, b):
+dist = abs(b.depth - self._depth)
+if dist > _radius or _hamming(self._vec, b._vec) > _radius:
+return False

Mercurial > public > mercurial-scm > hg

comparison mercurial/pvec.py @ 16249:0d175ac527c1