upstream/mercurial-mirror Files · mercurial/cffi/bdiff.py

phases: large rewrite on retract boundary...

phases: large rewrite on retract boundary The new code is still pure Python, so we still have room to going significantly faster. However its complexity of the complex part is `O(|[min_new_draft, tip]|)` instead of `O(|[min_draft, tip]|` which should help tremendously one repository with old draft (like mercurial-devel or mozilla-try). This is especially useful as the most common "retract boundary" operation happens when we commit/rewrite new drafts or when we push new draft to a non-publishing server. In this case, the smallest new_revs is very close to the tip and there is very few work to do. A few smaller optimisation could be done for these cases and will be introduced in later changesets. We still have iterate over large sets of roots, but this is already a great improvement for a very small amount of work. We gather information on the affected changeset as we go as we can put it to use in the next changesets. This extra data collection might slowdown the `register_new` case a bit, however for register_new, it should not really matters. The set of new nodes is either small, so the impact is negligible, or the set of new nodes is large, and the amount of work to do to had them will dominate the overhead the collecting information in `changed_revs`. As this new code compute the changes on the fly, it unlock other interesting improvement to be done in later changeset.

Matt Harbison - - Load All Authors

File last commit:

r50493:594fc56c default


                r52302:2f39c7ae

default

Download file

             bdiff.py
        
                    88 lines
            
             | 2.4 KiB
            
                | text/x-python
            
             |
                PythonLexer
            
             / mercurial / cffi / bdiff.py
          
                    History
                
                 |
                  Source
                 | Raw
                 |Copy content
                 |Copy permalink

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
      # bdiff.py - CFFI implementation of bdiff.c

      #

      # Copyright 2016 Maciej Fijalkowski <fijall@gmail.com>

      #

      # This software may be used and distributed according to the terms of the

      # GNU General Public License version 2 or any later version.

      import struct

        Matt Harbison
    
typing: add type hints to bdiff implementations...

              r50493
            
      from typing import (

          List,

          Tuple,

      )

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
      from ..pure.bdiff import *

        Matt Harbison
    
typing: disable import error warnings that are already handled...

              r47543
            
      from . import _bdiff  # pytype: disable=import-error

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
      ffi = _bdiff.ffi

      lib = _bdiff.lib

        Augie Fackler
    
formatting: blacken the codebase...

              r43346
            
        Matt Harbison
    
typing: add type hints to bdiff implementations...

              r50493
            
      def blocks(sa: bytes, sb: bytes) -> List[Tuple[int, int, int, int]]:

        Augie Fackler
    
formatting: byteify all mercurial/ and hgext/ string literals...

              r43347
            
          a = ffi.new(b"struct bdiff_line**")

          b = ffi.new(b"struct bdiff_line**")

          ac = ffi.new(b"char[]", str(sa))

          bc = ffi.new(b"char[]", str(sb))

          l = ffi.new(b"struct bdiff_hunk*")

        Yuya Nishihara
    
cffi: remove superfluous "if True" blocks

              r32513
            
          try:

              an = lib.bdiff_splitlines(ac, len(sa), a)

              bn = lib.bdiff_splitlines(bc, len(sb), b)

              if not a[0] or not b[0]:

                  raise MemoryError

              count = lib.bdiff_diff(a[0], an, b[0], bn, l)

              if count < 0:

                  raise MemoryError

        Matt Harbison
    
cffi: adjust the list returned by bdiff.blocks to never have a None entry...

              r50492
            
              rl = [(0, 0, 0, 0)] * count

        Yuya Nishihara
    
cffi: remove superfluous "if True" blocks

              r32513
            
              h = l.next

              i = 0

              while h:

                  rl[i] = (h.a1, h.a2, h.b1, h.b2)

                  h = h.next

                  i += 1

          finally:

              lib.free(a[0])

              lib.free(b[0])

              lib.bdiff_freehunks(l.next)

          return rl

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
        Augie Fackler
    
formatting: blacken the codebase...

              r43346
            
        Matt Harbison
    
typing: add type hints to bdiff implementations...

              r50493
            
      def bdiff(sa: bytes, sb: bytes) -> bytes:

        Augie Fackler
    
formatting: byteify all mercurial/ and hgext/ string literals...

              r43347
            
          a = ffi.new(b"struct bdiff_line**")

          b = ffi.new(b"struct bdiff_line**")

          ac = ffi.new(b"char[]", str(sa))

          bc = ffi.new(b"char[]", str(sb))

          l = ffi.new(b"struct bdiff_hunk*")

        Yuya Nishihara
    
cffi: remove superfluous "if True" blocks

              r32513
            
          try:

              an = lib.bdiff_splitlines(ac, len(sa), a)

              bn = lib.bdiff_splitlines(bc, len(sb), b)

              if not a[0] or not b[0]:

                  raise MemoryError

              count = lib.bdiff_diff(a[0], an, b[0], bn, l)

              if count < 0:

                  raise MemoryError

              rl = []

              h = l.next

              la = lb = 0

              while h:

                  if h.a1 != la or h.b1 != lb:

                      lgt = (b[0] + h.b1).l - (b[0] + lb).l

        Augie Fackler
    
formatting: blacken the codebase...

              r43346
            
                      rl.append(

                          struct.pack(

        Augie Fackler
    
formatting: byteify all mercurial/ and hgext/ string literals...

              r43347
            
                              b">lll",

        Augie Fackler
    
formatting: blacken the codebase...

              r43346
            
                              (a[0] + la).l - a[0].l,

                              (a[0] + h.a1).l - a[0].l,

                              lgt,

                          )

                      )

        Yuya Nishihara
    
cffi: remove superfluous "if True" blocks

              r32513
            
                      rl.append(str(ffi.buffer((b[0] + lb).l, lgt)))

                  la = h.a2

                  lb = h.b2

                  h = h.next

        Yuya Nishihara
    
cffi: split modules from pure...

              r32512
            
        Yuya Nishihara
    
cffi: remove superfluous "if True" blocks

              r32513
            
          finally:

              lib.free(a[0])

              lib.free(b[0])

              lib.bdiff_freehunks(l.next)

        Augie Fackler
    
formatting: byteify all mercurial/ and hgext/ string literals...

              r43347
            
          return b"".join(rl)

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

Yuya Nishihara cffi: split modules from pure...	r32512	# bdiff.py - CFFI implementation of bdiff.c
		#
		# Copyright 2016 Maciej Fijalkowski <fijall@gmail.com>
		#
		# This software may be used and distributed according to the terms of the
		# GNU General Public License version 2 or any later version.


		import struct

Matt Harbison typing: add type hints to bdiff implementations...	r50493	from typing import (
		List,
		Tuple,
		)

Yuya Nishihara cffi: split modules from pure...	r32512	from ..pure.bdiff import *
Matt Harbison typing: disable import error warnings that are already handled...	r47543	from . import _bdiff # pytype: disable=import-error
Yuya Nishihara cffi: split modules from pure...	r32512
		ffi = _bdiff.ffi
		lib = _bdiff.lib

Augie Fackler formatting: blacken the codebase...	r43346
Matt Harbison typing: add type hints to bdiff implementations...	r50493	def blocks(sa: bytes, sb: bytes) -> List[Tuple[int, int, int, int]]:
Augie Fackler formatting: byteify all mercurial/ and hgext/ string literals...	r43347	a = ffi.new(b"struct bdiff_line**")
		b = ffi.new(b"struct bdiff_line**")
		ac = ffi.new(b"char[]", str(sa))
		bc = ffi.new(b"char[]", str(sb))
		l = ffi.new(b"struct bdiff_hunk*")
Yuya Nishihara cffi: remove superfluous "if True" blocks	r32513	try:
		an = lib.bdiff_splitlines(ac, len(sa), a)
		bn = lib.bdiff_splitlines(bc, len(sb), b)
		if not a[0] or not b[0]:
		raise MemoryError
		count = lib.bdiff_diff(a[0], an, b[0], bn, l)
		if count < 0:
		raise MemoryError
Matt Harbison cffi: adjust the list returned by bdiff.blocks to never have a None entry...	r50492	rl = [(0, 0, 0, 0)] * count
Yuya Nishihara cffi: remove superfluous "if True" blocks	r32513	h = l.next
		i = 0
		while h:
		rl[i] = (h.a1, h.a2, h.b1, h.b2)
		h = h.next
		i += 1
		finally:
		lib.free(a[0])
		lib.free(b[0])
		lib.bdiff_freehunks(l.next)
		return rl
Yuya Nishihara cffi: split modules from pure...	r32512
Augie Fackler formatting: blacken the codebase...	r43346
Matt Harbison typing: add type hints to bdiff implementations...	r50493	def bdiff(sa: bytes, sb: bytes) -> bytes:
Augie Fackler formatting: byteify all mercurial/ and hgext/ string literals...	r43347	a = ffi.new(b"struct bdiff_line**")
		b = ffi.new(b"struct bdiff_line**")
		ac = ffi.new(b"char[]", str(sa))
		bc = ffi.new(b"char[]", str(sb))
		l = ffi.new(b"struct bdiff_hunk*")
Yuya Nishihara cffi: remove superfluous "if True" blocks	r32513	try:
		an = lib.bdiff_splitlines(ac, len(sa), a)
		bn = lib.bdiff_splitlines(bc, len(sb), b)
		if not a[0] or not b[0]:
		raise MemoryError
		count = lib.bdiff_diff(a[0], an, b[0], bn, l)
		if count < 0:
		raise MemoryError
		rl = []
		h = l.next
		la = lb = 0
		while h:
		if h.a1 != la or h.b1 != lb:
		lgt = (b[0] + h.b1).l - (b[0] + lb).l
Augie Fackler formatting: blacken the codebase...	r43346	rl.append(
		struct.pack(
Augie Fackler formatting: byteify all mercurial/ and hgext/ string literals...	r43347	b">lll",
Augie Fackler formatting: blacken the codebase...	r43346	(a[0] + la).l - a[0].l,
		(a[0] + h.a1).l - a[0].l,
		lgt,
		)
		)
Yuya Nishihara cffi: remove superfluous "if True" blocks	r32513	rl.append(str(ffi.buffer((b[0] + lb).l, lgt)))
		la = h.a2
		lb = h.b2
		h = h.next
Yuya Nishihara cffi: split modules from pure...	r32512
Yuya Nishihara cffi: remove superfluous "if True" blocks	r32513	finally:
		lib.free(a[0])
		lib.free(b[0])
		lib.bdiff_freehunks(l.next)
Augie Fackler formatting: byteify all mercurial/ and hgext/ string literals...	r43347	return b"".join(rl)