D2288: pvec: delete module
pulkit abandoned this revision. pulkit added a comment. This is not required as @durin42 will like to use pvec. REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D2288 To: pulkit, #hg-reviewers, martinvonz Cc: durin42, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D2288: pvec: delete module
martinvonz updated this revision to Diff 5789. REPOSITORY rHG Mercurial CHANGES SINCE LAST UPDATE https://phab.mercurial-scm.org/D2288?vs=5781&id=5789 REVISION DETAIL https://phab.mercurial-scm.org/D2288 AFFECTED FILES mercurial/debugcommands.py mercurial/pvec.py tests/test-completion.t tests/test-help.t CHANGE DETAILS diff --git a/tests/test-help.t b/tests/test-help.t --- a/tests/test-help.t +++ b/tests/test-help.t @@ -953,7 +953,6 @@ debugpickmergetool examine which merge tool is chosen for specified file debugpushkey access the pushkey key/value protocol - debugpvec (no help text available) debugrebuilddirstate rebuild the dirstate as it would look like for the given revision diff --git a/tests/test-completion.t b/tests/test-completion.t --- a/tests/test-completion.t +++ b/tests/test-completion.t @@ -105,7 +105,6 @@ debugpeer debugpickmergetool debugpushkey - debugpvec debugrebuilddirstate debugrebuildfncache debugrename @@ -285,7 +284,6 @@ debugpeer: debugpickmergetool: rev, changedelete, include, exclude, tool debugpushkey: - debugpvec: debugrebuilddirstate: rev, minimal debugrebuildfncache: debugrename: rev diff --git a/mercurial/pvec.py b/mercurial/pvec.py deleted file mode 100644 --- a/mercurial/pvec.py +++ /dev/null @@ -1,214 +0,0 @@ -# pvec.py - probabilistic vector clocks for Mercurial -# -# Copyright 2012 Matt Mackall -# -# 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 -''' - -from __future__ import absolute_import - -from .node import nullrev -from . import ( -util, -) - -_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 vectors 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
D2288: pvec: delete module
martinvonz added a comment. In https://phab.mercurial-scm.org/D2288#37819, @durin42 wrote: > SoI actually have an idea involving pvec and obsmarker metadata in `hg export` output. I'll work on fixing any problems in pvec, can we keep it around a little longer? Definitely. It hasn't bothered me at all personally. I just saw it in the list of files and wondered what it was. The first two patches in this series should still make sense. REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D2288 To: martinvonz, #hg-reviewers Cc: durin42, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D2288: pvec: delete module
durin42 added a comment. SoI actually have an idea involving pvec and obsmarker metadata in `hg export` output. I'll work on fixing any problems in pvec, can we keep it around a little longer? REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D2288 To: martinvonz, #hg-reviewers Cc: durin42, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D2288: pvec: delete module
martinvonz created this revision. Herald added a subscriber: mercurial-devel. Herald added a reviewer: hg-reviewers. REVISION SUMMARY The pvec module was introduced in https://phab.mercurial-scm.org/rHG0d175ac527c1d1b51b1de6dff25907ae377b9280 (pvec: introduce pvecs, 2012-03-12), but it seems it was never used. Let's delete it to avoid wasting time cleaning it up in the future. REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D2288 AFFECTED FILES mercurial/debugcommands.py mercurial/pvec.py tests/test-completion.t tests/test-help.t CHANGE DETAILS diff --git a/tests/test-help.t b/tests/test-help.t --- a/tests/test-help.t +++ b/tests/test-help.t @@ -953,7 +953,6 @@ debugpickmergetool examine which merge tool is chosen for specified file debugpushkey access the pushkey key/value protocol - debugpvec (no help text available) debugrebuilddirstate rebuild the dirstate as it would look like for the given revision diff --git a/tests/test-completion.t b/tests/test-completion.t --- a/tests/test-completion.t +++ b/tests/test-completion.t @@ -105,7 +105,6 @@ debugpeer debugpickmergetool debugpushkey - debugpvec debugrebuilddirstate debugrebuildfncache debugrename @@ -285,7 +284,6 @@ debugpeer: debugpickmergetool: rev, changedelete, include, exclude, tool debugpushkey: - debugpvec: debugrebuilddirstate: rev, minimal debugrebuildfncache: debugrename: rev diff --git a/mercurial/pvec.py b/mercurial/pvec.py deleted file mode 100644 --- a/mercurial/pvec.py +++ /dev/null @@ -1,214 +0,0 @@ -# pvec.py - probabilistic vector clocks for Mercurial -# -# Copyright 2012 Matt Mackall -# -# 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 -''' - -from __future__ import absolute_import - -from .node import nullrev -from . import ( -util, -) - -_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 vectors 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)
