mercurial/pvec.py
author Raphaël Gomès <rgomes@octobus.net>
Thu, 01 Sep 2022 16:51:26 +0200
changeset 49473 f59e49f6bee4
parent 49284 d44e3c45f0e4
child 50928 d718eddf01d9
permissions -rw-r--r--
branching: merge stable into default
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     1
# pvec.py - probabilistic vector clocks for Mercurial
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
46819
d4ba4d51f85f contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents: 44602
diff changeset
     3
# Copyright 2012 Olivia Mackall <olivia@selenic.com>
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     8
'''
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     9
A "pvec" is a changeset property based on the theory of vector clocks
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    10
that can be compared to discover relatedness without consulting a
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    11
graph. This can be useful for tasks like determining how a
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    12
disconnected patch relates to a repository.
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    13
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    14
Currently a pvec consist of 448 bits, of which 24 are 'depth' and the
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    15
remainder are a bit vector. It is represented as a 70-character base85
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    16
string.
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    17
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    18
Construction:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    19
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    20
- a root changeset has a depth of 0 and a bit vector based on its hash
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    21
- a normal commit has a changeset where depth is increased by one and
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    22
  one bit vector bit is flipped based on its hash
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    23
- a merge changeset pvec is constructed by copying changes from one pvec into
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    24
  the other to balance its depth
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    25
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    26
Properties:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    27
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    28
- for linear changes, difference in depth is always <= hamming distance
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    29
- otherwise, changes are probably divergent
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    30
- when hamming distance is < 200, we can reliably detect when pvecs are near
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    31
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    32
Issues:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    33
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    34
- hamming distance ceases to work over distances of ~ 200
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    35
- detecting divergence is less accurate when the common ancestor is very close
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    36
  to either revision or total distance is high
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    37
- this could probably be improved by modeling the relation between
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    38
  delta and hdist
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    39
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    40
Uses:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    41
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    42
- a patch pvec can be used to locate the nearest available common ancestor for
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    43
  resolving conflicts
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    44
- ordering of patches can be established without a DAG
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    45
- two head pvecs can be compared to determine whether push/pull/merge is needed
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    46
  and approximately how many changesets are involved
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    47
- can be used to find a heuristic divergence measure between changesets on
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    48
  different branches
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    49
'''
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    50
27501
983e93d88193 pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24339
diff changeset
    51
983e93d88193 pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24339
diff changeset
    52
from .node import nullrev
983e93d88193 pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24339
diff changeset
    53
from . import (
38783
e7aa113b14f7 global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents: 32201
diff changeset
    54
    pycompat,
27501
983e93d88193 pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24339
diff changeset
    55
    util,
983e93d88193 pvec: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 24339
diff changeset
    56
)
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    57
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    58
_size = 448  # 70 chars b85-encoded
43465
90aac60b6697 pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents: 43463
diff changeset
    59
_bytes = _size // 8
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    60
_depthbits = 24
43465
90aac60b6697 pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents: 43463
diff changeset
    61
_depthbytes = _depthbits // 8
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    62
_vecbytes = _bytes - _depthbytes
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    63
_vecbits = _vecbytes * 8
43465
90aac60b6697 pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents: 43463
diff changeset
    64
_radius = (_vecbits - 30) // 2  # high probability vectors are related
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    65
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    66
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    67
def _bin(bs):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    68
    '''convert a bytestring to a long'''
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    69
    v = 0
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    70
    for b in bs:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    71
        v = v * 256 + ord(b)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    72
    return v
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    73
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    74
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    75
def _str(v, l):
43479
8e89b6e1e0cd pvec: add an explicit type hint to help pytype
Augie Fackler <augie@google.com>
parents: 43465
diff changeset
    76
    # type: (int, int) -> bytes
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
    77
    bs = b""
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
    78
    for p in range(l):
43463
271af23d01a9 pvec: fix overlooked chr() call
Augie Fackler <augie@google.com>
parents: 43115
diff changeset
    79
        bs = pycompat.bytechr(v & 255) + bs
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    80
        v >>= 8
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    81
    return bs
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    82
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    83
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    84
def _split(b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    85
    '''depth and bitvec'''
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    86
    return _bin(b[:_depthbytes]), _bin(b[_depthbytes:])
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    87
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    88
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    89
def _join(depth, bitvec):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    90
    return _str(depth, _depthbytes) + _str(bitvec, _vecbytes)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    91
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
    92
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    93
def _hweight(x):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    94
    c = 0
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    95
    while x:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    96
        if x & 1:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    97
            c += 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    98
        x >>= 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    99
    return c
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   100
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   101
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
   102
_htab = [_hweight(x) for x in range(256)]
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   103
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   104
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   105
def _hamming(a, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   106
    '''find the hamming distance between two longs'''
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   107
    d = a ^ b
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   108
    c = 0
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   109
    while d:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   110
        c += _htab[d & 0xFF]
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   111
        d >>= 8
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   112
    return c
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   113
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   114
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   115
def _mergevec(x, y, c):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   116
    # Ideally, this function would be x ^ y ^ ancestor, but finding
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   117
    # ancestors is a nuisance. So instead we find the minimal number
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   118
    # of changes to balance the depth and hamming distance
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   119
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   120
    d1, v1 = x
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   121
    d2, v2 = y
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   122
    if d1 < d2:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   123
        d1, d2, v1, v2 = d2, d1, v2, v1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   124
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   125
    hdist = _hamming(v1, v2)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   126
    ddist = d1 - d2
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   127
    v = v1
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   128
    m = v1 ^ v2  # mask of different bits
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   129
    i = 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   130
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   131
    if hdist > ddist:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   132
        # if delta = 10 and hdist = 100, then we need to go up 55 steps
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   133
        # to the ancestor and down 45
43465
90aac60b6697 pvec: migrate to modern integer division
Augie Fackler <augie@google.com>
parents: 43463
diff changeset
   134
        changes = (hdist - ddist + 1) // 2
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   135
    else:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   136
        # must make at least one change
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   137
        changes = 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   138
    depth = d1 + changes
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   139
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   140
    # copy changes from v2
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   141
    if m:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   142
        while changes:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   143
            if m & i:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   144
                v ^= i
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   145
                changes -= 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   146
            i <<= 1
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   147
    else:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   148
        v = _flipbit(v, c)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   149
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   150
    return depth, v
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   151
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   152
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   153
def _flipbit(v, node):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   154
    # converting bit strings to longs is slow
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   155
    bit = (hash(node) & 0xFFFFFFFF) % _vecbits
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   156
    return v ^ (1 << bit)
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   157
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   158
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   159
def ctxpvec(ctx):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   160
    '''construct a pvec for ctx while filling in the cache'''
24339
bcc319d936a3 pvec: replace 'ctx._repo' with 'ctx.repo()'
Matt Harbison <matt_harbison@yahoo.com>
parents: 18918
diff changeset
   161
    r = ctx.repo()
43115
4aa72cdf616f py3: delete b'' prefix from safehasattr arguments
Martin von Zweigbergk <martinvonz@google.com>
parents: 43077
diff changeset
   162
    if not util.safehasattr(r, "_pveccache"):
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   163
        r._pveccache = {}
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   164
    pvc = r._pveccache
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   165
    if ctx.rev() not in pvc:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   166
        cl = r.changelog
49284
d44e3c45f0e4 py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents: 48946
diff changeset
   167
        for n in range(ctx.rev() + 1):
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   168
            if n not in pvc:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   169
                node = cl.node(n)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   170
                p1, p2 = cl.parentrevs(n)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   171
                if p1 == nullrev:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   172
                    # start with a 'random' vector at root
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   173
                    pvc[n] = (0, _bin((node * 3)[:_vecbytes]))
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   174
                elif p2 == nullrev:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   175
                    d, v = pvc[p1]
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   176
                    pvc[n] = (d + 1, _flipbit(v, node))
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   177
                else:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   178
                    pvc[n] = _mergevec(pvc[p1], pvc[p2], node)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   179
    bs = _join(*pvc[ctx.rev()])
32201
4462a981e8df base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents: 27501
diff changeset
   180
    return pvec(util.b85encode(bs))
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   181
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   182
48946
642e31cb55f0 py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents: 48875
diff changeset
   183
class pvec:
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   184
    def __init__(self, hashorctx):
43746
10662ac7849e pvec: fix a `str` type conditional for py3
Matt Harbison <matt_harbison@yahoo.com>
parents: 43115
diff changeset
   185
        if isinstance(hashorctx, bytes):
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   186
            self._bs = hashorctx
32201
4462a981e8df base85: proxy through util module
Yuya Nishihara <yuya@tcha.org>
parents: 27501
diff changeset
   187
            self._depth, self._vec = _split(util.b85decode(hashorctx))
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   188
        else:
18918
5093d2a87ff6 pvec: use the correct name for an identifier
Bryan O'Sullivan <bryano@fb.com>
parents: 17424
diff changeset
   189
            self._vec = ctxpvec(hashorctx)
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   190
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   191
    def __str__(self):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   192
        return self._bs
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   193
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   194
    def __eq__(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   195
        return self._vec == b._vec and self._depth == b._depth
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   196
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   197
    def __lt__(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   198
        delta = b._depth - self._depth
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   199
        if delta < 0:
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 38783
diff changeset
   200
            return False  # always correct
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   201
        if _hamming(self._vec, b._vec) > delta:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   202
            return False
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   203
        return True
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   204
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   205
    def __gt__(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   206
        return b < self
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   207
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   208
    def __or__(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   209
        delta = abs(b._depth - self._depth)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   210
        if _hamming(self._vec, b._vec) <= delta:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   211
            return False
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   212
        return True
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   213
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   214
    def __sub__(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   215
        if self | b:
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
   216
            raise ValueError(b"concurrent pvecs")
16249
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   217
        return self._depth - b._depth
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   218
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   219
    def distance(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   220
        d = abs(b._depth - self._depth)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   221
        h = _hamming(self._vec, b._vec)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   222
        return max(d, h)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   223
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   224
    def near(self, b):
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   225
        dist = abs(b.depth - self._depth)
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   226
        if dist > _radius or _hamming(self._vec, b._vec) > _radius:
0d175ac527c1 pvec: introduce pvecs
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   227
            return False