annotate mercurial/cffi/bdiff.py @ 45637:ad6ebb6f0dfe

copies: make two version of the changeset centric algorithm They are two main ways to run the changeset-centric copy-tracing algorithm. One fed from data stored in side-data and still in development, and one based on data stored in extra (with a "compatibility" mode). The `extra` based is used in production at Google, but still experimental in code. It is mostly unsuitable for other users because it affects the hash. The side-data based storage and algorithm have been evolving to store more data, cover more cases (mostly around merge, that Google do not really care about) and use lower level storage for efficiency. All this changes make is increasingly hard to maintain de common code base, without impacting code complexity and performance. For example, the compatibility mode requires to keep things at different level than what we need for side-data. So, I am duplicating the involved functions. The newly added `_extra` variants will be kept as today, while I will do some deeper rework of the side data versions. Long terms, the side-data version should be more featureful and performant than the extra based version, so I expect the duplicated `_extra` functions to eventually get dropped. Differential Revision: https://phab.mercurial-scm.org/D9114
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Fri, 25 Sep 2020 14:39:04 +0200
parents 687b865b95ad
children 521ac0d7047f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
32512
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
1 # bdiff.py - CFFI implementation of bdiff.c
7703
9044d3567f6d pure Python implementation of bdiff.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
2 #
32512
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
3 # Copyright 2016 Maciej Fijalkowski <fijall@gmail.com>
7703
9044d3567f6d pure Python implementation of bdiff.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
4 #
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7944
diff changeset
5 # This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8225
diff changeset
6 # GNU General Public License version 2 or any later version.
7703
9044d3567f6d pure Python implementation of bdiff.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
7
27335
c4e3ff497f89 bdiff: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 15530
diff changeset
8 from __future__ import absolute_import
c4e3ff497f89 bdiff: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 15530
diff changeset
9
c4e3ff497f89 bdiff: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 15530
diff changeset
10 import struct
7944
e9b48afd0e78 pure/bdiff: fix circular import
Matt Mackall <mpm@selenic.com>
parents: 7703
diff changeset
11
32512
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
12 from ..pure.bdiff import *
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
13 from . import _bdiff
7703
9044d3567f6d pure Python implementation of bdiff.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
14
32512
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
15 ffi = _bdiff.ffi
0e8b0b9a7acc cffi: split modules from pure
Yuya Nishihara <yuya@tcha.org>
parents: 32506
diff changeset
16 lib = _bdiff.lib
7703
9044d3567f6d pure Python implementation of bdiff.c
Martin Geisler <mg@daimi.au.dk>
parents:
diff changeset
17
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
18
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
19 def blocks(sa, sb):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
20 a = ffi.new(b"struct bdiff_line**")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
21 b = ffi.new(b"struct bdiff_line**")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
22 ac = ffi.new(b"char[]", str(sa))
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
23 bc = ffi.new(b"char[]", str(sb))
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
24 l = ffi.new(b"struct bdiff_hunk*")
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
25 try:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
26 an = lib.bdiff_splitlines(ac, len(sa), a)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
27 bn = lib.bdiff_splitlines(bc, len(sb), b)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
28 if not a[0] or not b[0]:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
29 raise MemoryError
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
30 count = lib.bdiff_diff(a[0], an, b[0], bn, l)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
31 if count < 0:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
32 raise MemoryError
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
33 rl = [None] * count
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
34 h = l.next
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
35 i = 0
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
36 while h:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
37 rl[i] = (h.a1, h.a2, h.b1, h.b2)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
38 h = h.next
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
39 i += 1
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
40 finally:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
41 lib.free(a[0])
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
42 lib.free(b[0])
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
43 lib.bdiff_freehunks(l.next)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
44 return rl
29834
1ea77b75d266 bdiff: implement cffi version of bdiff
Maciej Fijalkowski <fijall@gmail.com>
parents: 29833
diff changeset
45
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
46
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
47 def bdiff(sa, sb):
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
48 a = ffi.new(b"struct bdiff_line**")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
49 b = ffi.new(b"struct bdiff_line**")
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
50 ac = ffi.new(b"char[]", str(sa))
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
51 bc = ffi.new(b"char[]", str(sb))
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
52 l = ffi.new(b"struct bdiff_hunk*")
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
53 try:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
54 an = lib.bdiff_splitlines(ac, len(sa), a)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
55 bn = lib.bdiff_splitlines(bc, len(sb), b)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
56 if not a[0] or not b[0]:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
57 raise MemoryError
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
58 count = lib.bdiff_diff(a[0], an, b[0], bn, l)
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
59 if count < 0:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
60 raise MemoryError
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
61 rl = []
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
62 h = l.next
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
63 la = lb = 0
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
64 while h:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
65 if h.a1 != la or h.b1 != lb:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
66 lgt = (b[0] + h.b1).l - (b[0] + lb).l
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
67 rl.append(
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
68 struct.pack(
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
69 b">lll",
43076
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
70 (a[0] + la).l - a[0].l,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
71 (a[0] + h.a1).l - a[0].l,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
72 lgt,
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
73 )
2372284d9457 formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents: 33572
diff changeset
74 )
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
75 rl.append(str(ffi.buffer((b[0] + lb).l, lgt)))
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
76 la = h.a2
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
77 lb = h.b2
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
78 h = h.next
29834
1ea77b75d266 bdiff: implement cffi version of bdiff
Maciej Fijalkowski <fijall@gmail.com>
parents: 29833
diff changeset
79
32513
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
80 finally:
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
81 lib.free(a[0])
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
82 lib.free(b[0])
25b37900d6e0 cffi: remove superfluous "if True" blocks
Yuya Nishihara <yuya@tcha.org>
parents: 32512
diff changeset
83 lib.bdiff_freehunks(l.next)
43077
687b865b95ad formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents: 43076
diff changeset
84 return b"".join(rl)