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

patch: support diff data loss detection and upgrade...

patch: support diff data loss detection and upgrade In worst case, generating diff in upgrade mode can be two times more expensive than generating it in git mode directly: we may have to regenerate the whole diff again whenever a git feature is detected. Also, the first diff attempt is completely buffered instead of being streamed. That said, even without having profiled it yet, I am convinced we can fast-path the upgrade mode if necessary were it to be used in regular diff commands, and not only in mq where avoiding data loss is worth the price.

Martin Geisler - - Load All Authors

File last commit:

r8225:46293a0c default


                r10189:e451e599

default

Download file

             bdiff.py
        
                    76 lines
            
             | 2.0 KiB
            
                | text/x-python
            
             |
                PythonLexer
            
             / mercurial / pure / bdiff.py
          
                    History
                
                 |
                  Annotation
                 | Raw
                 |Copy content
                 |Copy permalink

      # bdiff.py - Python implementation of bdiff.c

      #

      # Copyright 2009 Matt Mackall <mpm@selenic.com> and others

      #

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

      # GNU General Public License version 2, incorporated herein by reference.

      import struct, difflib

      def splitnewlines(text):

          '''like str.splitlines, but only split on newlines.'''

          lines = [l + '\n' for l in text.split('\n')]

          if lines:

              if lines[-1] == '\n':

                  lines.pop()

              else:

                  lines[-1] = lines[-1][:-1]

          return lines

      def _normalizeblocks(a, b, blocks):

          prev = None

          for curr in blocks:

              if prev is None:

                  prev = curr

                  continue

              shift = 0

              a1, b1, l1 = prev

              a1end = a1 + l1

              b1end = b1 + l1

              a2, b2, l2 = curr

              a2end = a2 + l2

              b2end = b2 + l2

              if a1end == a2:

                  while a1end+shift < a2end and a[a1end+shift] == b[b1end+shift]:

                      shift += 1

              elif b1end == b2:

                  while b1end+shift < b2end and a[a1end+shift] == b[b1end+shift]:

                      shift += 1

              yield a1, b1, l1+shift

              prev = a2+shift, b2+shift, l2-shift

          yield prev

      def bdiff(a, b):

          a = str(a).splitlines(True)

          b = str(b).splitlines(True)

          if not a:

              s = "".join(b)

              return s and (struct.pack(">lll", 0, 0, len(s)) + s)

          bin = []

          p = [0]

          for i in a: p.append(p[-1] + len(i))

          d = difflib.SequenceMatcher(None, a, b).get_matching_blocks()

          d = _normalizeblocks(a, b, d)

          la = 0

          lb = 0

          for am, bm, size in d:

              s = "".join(b[lb:bm])

              if am > la or s:

                  bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s)

              la = am + size

              lb = bm + size

          return "".join(bin)

      def blocks(a, b):

          an = splitnewlines(a)

          bn = splitnewlines(b)

          d = difflib.SequenceMatcher(None, an, bn).get_matching_blocks()

          d = _normalizeblocks(an, bn, d)

          return [(i, i + n, j, j + n) for (i, j, n) in d]

	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

				# bdiff.py - Python implementation of bdiff.c
				#
				# Copyright 2009 Matt Mackall <mpm@selenic.com> and others
				#
				# This software may be used and distributed according to the terms of the
				# GNU General Public License version 2, incorporated herein by reference.

				import struct, difflib

				def splitnewlines(text):
				'''like str.splitlines, but only split on newlines.'''
				lines = [l + '\n' for l in text.split('\n')]
				if lines:
				if lines[-1] == '\n':
				lines.pop()
				else:
				lines[-1] = lines[-1][:-1]
				return lines

				def _normalizeblocks(a, b, blocks):
				prev = None
				for curr in blocks:
				if prev is None:
				prev = curr
				continue
				shift = 0

				a1, b1, l1 = prev
				a1end = a1 + l1
				b1end = b1 + l1

				a2, b2, l2 = curr
				a2end = a2 + l2
				b2end = b2 + l2
				if a1end == a2:
				while a1end+shift < a2end and a[a1end+shift] == b[b1end+shift]:
				shift += 1
				elif b1end == b2:
				while b1end+shift < b2end and a[a1end+shift] == b[b1end+shift]:
				shift += 1
				yield a1, b1, l1+shift
				prev = a2+shift, b2+shift, l2-shift
				yield prev

				def bdiff(a, b):
				a = str(a).splitlines(True)
				b = str(b).splitlines(True)

				if not a:
				s = "".join(b)
				return s and (struct.pack(">lll", 0, 0, len(s)) + s)

				bin = []
				p = [0]
				for i in a: p.append(p[-1] + len(i))

				d = difflib.SequenceMatcher(None, a, b).get_matching_blocks()
				d = _normalizeblocks(a, b, d)
				la = 0
				lb = 0
				for am, bm, size in d:
				s = "".join(b[lb:bm])
				if am > la or s:
				bin.append(struct.pack(">lll", p[la], p[am], len(s)) + s)
				la = am + size
				lb = bm + size

				return "".join(bin)

				def blocks(a, b):
				an = splitnewlines(a)
				bn = splitnewlines(b)
				d = difflib.SequenceMatcher(None, an, bn).get_matching_blocks()
				d = _normalizeblocks(an, bn, d)
				return [(i, i + n, j, j + n) for (i, j, n) in d]