[diffoscope] 02/03: Move side-by-side and linediff algorithms to difference.py
Ximin Luo
infinity0 at debian.org
Wed Jun 14 19:10:39 CEST 2017
This is an automated email from the git hooks/post-receive script.
infinity0 pushed a commit to branch WIP/humungous-diffs
in repository diffoscope.
commit 0b428dad6ae2ec26b95ee13aa4b79d268ca00ddf
Author: Ximin Luo <infinity0 at debian.org>
Date: Wed Jun 14 16:54:24 2017 +0200
Move side-by-side and linediff algorithms to difference.py
---
diffoscope/difference.py | 253 +++++++++++++++++++++++++++++++++
diffoscope/presenters/html/html.py | 169 +++-------------------
diffoscope/presenters/html/linediff.py | 94 ------------
3 files changed, 273 insertions(+), 243 deletions(-)
diff --git a/diffoscope/difference.py b/diffoscope/difference.py
index ca45041..5693726 100644
--- a/diffoscope/difference.py
+++ b/diffoscope/difference.py
@@ -17,6 +17,7 @@
# You should have received a copy of the GNU General Public License
# along with diffoscope. If not, see <https://www.gnu.org/licenses/>.
+import re
import signal
import hashlib
import logging
@@ -297,3 +298,255 @@ def empty_file_feeder():
def feeder(f):
return False
return feeder
+
+DIFFON = "\x01"
+DIFFOFF = "\x02"
+
+def _linediff_sane(x):
+ r = ""
+ for i in x:
+ j = ord(i)
+ if i not in ['\t', '\n'] and (j < 32):
+ r = r + "."
+ else:
+ r = r + i
+ return r
+
+def linediff(s, t, diffon, diffoff):
+ '''
+ Original line diff algorithm of diff2html. It's character based.
+ '''
+ if len(s):
+ s = ''.join([ _linediff_sane(c) for c in s ])
+ if len(t):
+ t = ''.join([ _linediff_sane(c) for c in t ])
+
+ m, n = len(s), len(t)
+ d = [[(0, 0) for i in range(n+1)] for i in range(m+1)]
+
+
+ d[0][0] = (0, (0, 0))
+ for i in range(m+1)[1:]:
+ d[i][0] = (i,(i-1, 0))
+ for j in range(n+1)[1:]:
+ d[0][j] = (j,(0, j-1))
+
+ for i in range(m+1)[1:]:
+ for j in range(n+1)[1:]:
+ if s[i-1] == t[j-1]:
+ cost = 0
+ else:
+ cost = 1
+ d[i][j] = min((d[i-1][j][0] + 1, (i-1, j)),
+ (d[i][j-1][0] + 1, (i, j-1)),
+ (d[i-1][j-1][0] + cost, (i-1, j-1)))
+
+ l = []
+ coord = (m, n)
+ while coord != (0, 0):
+ l.insert(0, coord)
+ x, y = coord
+ coord = d[x][y][1]
+
+ l1 = []
+ l2 = []
+
+ for coord in l:
+ cx, cy = coord
+ child_val = d[cx][cy][0]
+
+ father_coord = d[cx][cy][1]
+ fx, fy = father_coord
+ father_val = d[fx][fy][0]
+
+ diff = (cx-fx, cy-fy)
+
+ if diff == (0, 1):
+ l1.append("")
+ l2.append(diffon + t[fy] + diffoff)
+ elif diff == (1, 0):
+ l1.append(diffon + s[fx] + diffoff)
+ l2.append("")
+ elif child_val-father_val == 1:
+ l1.append(diffon + s[fx] + diffoff)
+ l2.append(diffon + t[fy] + diffoff)
+ else:
+ l1.append(s[fx])
+ l2.append(t[fy])
+
+ return ''.join(l1).replace(diffoff + diffon, ''), ''.join(l2).replace(diffoff + diffon, '')
+
+
+class SideBySideDiff(object):
+ """Calculates a side-by-side diff from a unified diff."""
+
+ def __init__(self, unified_diff, diffon=DIFFON, diffoff=DIFFOFF):
+ self.unified_diff = unified_diff
+ self.diffon = diffon
+ self.diffoff = diffoff
+ self.reset()
+
+ def reset(self):
+ self.buf = []
+ self.add_cpt = 0
+ self.del_cpt = 0
+ self.line1 = 0
+ self.line2 = 0
+ self.hunk_off1 = 0
+ self.hunk_size1 = 0
+ self.hunk_off2 = 0
+ self.hunk_size2 = 0
+ self._bytes_processed = 0
+
+ @property
+ def bytes_processed(self):
+ return self._bytes_processed
+
+ def empty_buffer(self):
+ if self.del_cpt == 0 or self.add_cpt == 0:
+ for l in self.buf:
+ yield from self.yield_line(l[0], l[1])
+
+ elif self.del_cpt != 0 and self.add_cpt != 0:
+ l0, l1 = [], []
+ for l in self.buf:
+ if l[0] != None:
+ l0.append(l[0])
+ if l[1] != None:
+ l1.append(l[1])
+ max_len = (len(l0) > len(l1)) and len(l0) or len(l1)
+ for i in range(max_len):
+ s0, s1 = "", ""
+ if i < len(l0):
+ s0 = l0[i]
+ if i < len(l1):
+ s1 = l1[i]
+ yield from self.yield_line(s0, s1)
+
+ def yield_line(self, s1, s2):
+ orig1 = s1
+ orig2 = s2
+
+ if s1 == None and s2 == None:
+ type_name = "unmodified"
+ elif s1 == "" and s2 == "":
+ type_name = "unmodified"
+ elif s1 == None or s1 == "":
+ type_name = "added"
+ elif s2 == None or s2 == "":
+ type_name = "deleted"
+ elif orig1 == orig2 and not s1.endswith('lines removed ]') and not s2.endswith('lines removed ]'):
+ type_name = "unmodified"
+ else:
+ type_name = "changed"
+ s1, s2 = linediff(s1, s2, self.diffon, self.diffoff)
+
+ yield "L", (type_name, s1, self.line1, s2, self.line2)
+
+ m = orig1 and re.match(r"^\[ (\d+) lines removed \]$", orig1)
+ if m:
+ self.line1 += int(m.group(1))
+ elif orig1:
+ self.line1 += 1
+ m = orig2 and re.match(r"^\[ (\d+) lines removed \]$", orig2)
+ if m:
+ self.line2 += int(m.group(1))
+ elif orig2:
+ self.line2 += 1
+
+ self.add_cpt = 0
+ self.del_cpt = 0
+ self.buf = []
+
+ def items(self):
+ """Yield the items that form the side-by-side diff.
+
+ Each item is a (type, value) tuple, as follows:
+
+ type == "H", value is a tuple representing a hunk header
+ hunk_offset1, hunk_size1, hunk_offset2, hunk_size2 = value
+ all ints
+
+ type == "L", value is a tuple representing a line of a hunk
+ mode, line1, lineno1, line2, lineno2 = value
+ where mode is one of {"unmodified", "added", "deleted", "changed"}
+ line* are strings
+ lineno* are ints
+
+ type == "C", value is a comment
+ comment = value
+ a string
+ """
+ self.reset()
+
+ for l in self.unified_diff.splitlines():
+ self._bytes_processed += len(l) + 1
+ m = re.match(r'^--- ([^\s]*)', l)
+ if m:
+ yield from self.empty_buffer()
+ continue
+ m = re.match(r'^\+\+\+ ([^\s]*)', l)
+ if m:
+ yield from self.empty_buffer()
+ continue
+
+ m = re.match(r"@@ -(\d+),?(\d*) \+(\d+),?(\d*)", l)
+ if m:
+ yield from self.empty_buffer()
+ hunk_data = map(lambda x:x=="" and 1 or int(x), m.groups())
+ self.hunk_off1, self.hunk_size1, self.hunk_off2, self.hunk_size2 = hunk_data
+ self.line1, self.line2 = self.hunk_off1, self.hunk_off2
+ yield "H", (self.hunk_off1, self.hunk_size1, self.hunk_off2, self.hunk_size2)
+ continue
+
+ if re.match(r'^\[', l):
+ yield from self.empty_buffer()
+ yield "C", l
+
+ if re.match(r"^\\ No newline", l):
+ if self.hunk_size2 == 0:
+ self.buf[-1] = (self.buf[-1][0], self.buf[-1][1] + '\n' + l[2:])
+ else:
+ self.buf[-1] = (buf[-1][0] + '\n' + l[2:], self.buf[-1][1])
+ continue
+
+ if self.hunk_size1 <= 0 and self.hunk_size2 <= 0:
+ yield from self.empty_buffer()
+ continue
+
+ m = re.match(r"^\+\[ (\d+) lines removed \]$", l)
+ if m:
+ self.add_cpt += int(m.group(1))
+ self.hunk_size2 -= int(m.group(1))
+ self.buf.append((None, l[1:]))
+ continue
+
+ if re.match(r"^\+", l):
+ self.add_cpt += 1
+ self.hunk_size2 -= 1
+ self.buf.append((None, l[1:]))
+ continue
+
+ m = re.match(r"^-\[ (\d+) lines removed \]$", l)
+ if m:
+ self.del_cpt += int(m.group(1))
+ self.hunk_size1 -= int(m.group(1))
+ self.buf.append((l[1:], None))
+ continue
+
+ if re.match(r"^-", l):
+ self.del_cpt += 1
+ self.hunk_size1 -= 1
+ self.buf.append((l[1:], None))
+ continue
+
+ if re.match(r"^ ", l) and self.hunk_size1 and self.hunk_size2:
+ yield from self.empty_buffer()
+ self.hunk_size1 -= 1
+ self.hunk_size2 -= 1
+ self.buf.append((l[1:], l[1:]))
+ continue
+
+ yield from self.empty_buffer()
+
+ yield from self.empty_buffer()
diff --git a/diffoscope/presenters/html/html.py b/diffoscope/presenters/html/html.py
index 3940de8..f86db3e 100644
--- a/diffoscope/presenters/html/html.py
+++ b/diffoscope/presenters/html/html.py
@@ -43,13 +43,13 @@ import contextlib
from diffoscope import VERSION
from diffoscope.config import Config
+from diffoscope.difference import SideBySideDiff, DIFFON, DIFFOFF
from ..icon import FAVICON_BASE64
from ..utils import PrintLimitReached, DiffBlockLimitReached, \
create_limited_print_func, Presenter, make_printer
from . import templates
-from .linediff import linediff
# minimum line size, we add a zero-sized breakable space every
# LINESIZE characters
@@ -60,9 +60,6 @@ TABSIZE = 8
# Characters we're willing to word wrap on
WORDBREAK = " \t;.,/):-"
-DIFFON = "\x01"
-DIFFOFF = "\x02"
-
JQUERY_SYSTEM_LOCATIONS = (
'/usr/share/javascript/jquery/jquery.js',
)
@@ -179,56 +176,29 @@ class HTMLPresenter(Presenter):
self.new_unified_diff()
def new_unified_diff(self):
- self.buf = []
- self.add_cpt = 0
- self.del_cpt = 0
- self.line1 = 0
- self.line2 = 0
- self.has_internal_linenos = True
- self.hunk_off1 = 0
- self.hunk_size1 = 0
- self.hunk_off2 = 0
- self.hunk_size2 = 0
self.spl_rows = 0
self.spl_current_page = 0
self.spl_print_func = None
self.spl_print_ctrl = None
- def output_hunk(self):
- self.spl_print_func(u'<tr class="diffhunk"><td colspan="2">Offset %d, %d lines modified</td>' % (self.hunk_off1, self.hunk_size1))
- self.spl_print_func(u'<td colspan="2">Offset %d, %d lines modified</td></tr>\n' % (self.hunk_off2, self.hunk_size2))
+ def output_hunk_header(self, hunk_off1, hunk_size1, hunk_off2, hunk_size2):
+ self.spl_print_func(u'<tr class="diffhunk"><td colspan="2">Offset %d, %d lines modified</td>' % (hunk_off1, hunk_size1))
+ self.spl_print_func(u'<td colspan="2">Offset %d, %d lines modified</td></tr>\n' % (hunk_off2, hunk_size2))
self.row_was_output()
- def output_line(self, s1, s2):
- orig1 = s1
- orig2 = s2
-
+ def output_line(self, has_internal_linenos, type_name, s1, line1, s2, line2):
if s1 and len(s1) > MAX_LINE_SIZE:
s1 = s1[:MAX_LINE_SIZE] + u" ✂"
if s2 and len(s2) > MAX_LINE_SIZE:
s2 = s2[:MAX_LINE_SIZE] + u" ✂"
- if s1 == None and s2 == None:
- type_name = "unmodified"
- elif s1 == "" and s2 == "":
- type_name = "unmodified"
- elif s1 == None or s1 == "":
- type_name = "added"
- elif s2 == None or s2 == "":
- type_name = "deleted"
- elif orig1 == orig2 and not s1.endswith('lines removed ]') and not s2.endswith('lines removed ]'):
- type_name = "unmodified"
- else:
- type_name = "changed"
- s1, s2 = linediff(s1, s2, DIFFON, DIFFOFF)
-
self.spl_print_func(u'<tr class="diff%s">' % type_name)
try:
if s1:
- if self.has_internal_linenos:
+ if has_internal_linenos:
self.spl_print_func(u'<td colspan="2" class="diffpresent">')
else:
- self.spl_print_func(u'<td class="diffline">%d </td>' % self.line1)
+ self.spl_print_func(u'<td class="diffline">%d </td>' % line1)
self.spl_print_func(u'<td class="diffpresent">')
self.spl_print_func(convert(s1, ponct=1, tag='del'))
self.spl_print_func(u'</td>')
@@ -236,10 +206,10 @@ class HTMLPresenter(Presenter):
self.spl_print_func(u'<td colspan="2">\xa0</td>')
if s2:
- if self.has_internal_linenos:
+ if has_internal_linenos:
self.spl_print_func(u'<td colspan="2" class="diffpresent">')
else:
- self.spl_print_func(u'<td class="diffline">%d </td>' % self.line2)
+ self.spl_print_func(u'<td class="diffline">%d </td>' % line2)
self.spl_print_func(u'<td class="diffpresent">')
self.spl_print_func(convert(s2, ponct=1, tag='ins'))
self.spl_print_func(u'</td>')
@@ -249,42 +219,6 @@ class HTMLPresenter(Presenter):
self.spl_print_func(u"</tr>\n", force=True)
self.row_was_output()
- m = orig1 and re.match(r"^\[ (\d+) lines removed \]$", orig1)
- if m:
- self.line1 += int(m.group(1))
- elif orig1:
- self.line1 += 1
- m = orig2 and re.match(r"^\[ (\d+) lines removed \]$", orig2)
- if m:
- self.line2 += int(m.group(1))
- elif orig2:
- self.line2 += 1
-
- def empty_buffer(self):
- if self.del_cpt == 0 or self.add_cpt == 0:
- for l in self.buf:
- self.output_line(l[0], l[1])
-
- elif self.del_cpt != 0 and self.add_cpt != 0:
- l0, l1 = [], []
- for l in self.buf:
- if l[0] != None:
- l0.append(l[0])
- if l[1] != None:
- l1.append(l[1])
- max_len = (len(l0) > len(l1)) and len(l0) or len(l1)
- for i in range(max_len):
- s0, s1 = "", ""
- if i < len(l0):
- s0 = l0[i]
- if i < len(l1):
- s1 = l1[i]
- self.output_line(s0, s1)
-
- self.add_cpt = 0
- self.del_cpt = 0
- self.buf = []
-
def spl_print_enter(self, print_context, rotation_params):
# Takes ownership of print_context
self.spl_print_ctrl = print_context.__exit__, rotation_params
@@ -345,85 +279,22 @@ class HTMLPresenter(Presenter):
self.spl_print_func(templates.UD_TABLE_HEADER)
def output_unified_diff_table(self, unified_diff, has_internal_linenos):
- self.has_internal_linenos = has_internal_linenos
self.spl_print_func(templates.UD_TABLE_HEADER)
try:
- bytes_processed = 0
- for l in unified_diff.splitlines():
- bytes_processed += len(l) + 1
- m = re.match(r'^--- ([^\s]*)', l)
- if m:
- self.empty_buffer()
- continue
- m = re.match(r'^\+\+\+ ([^\s]*)', l)
- if m:
- self.empty_buffer()
- continue
-
- m = re.match(r"@@ -(\d+),?(\d*) \+(\d+),?(\d*)", l)
- if m:
- self.empty_buffer()
- hunk_data = map(lambda x:x=="" and 1 or int(x), m.groups())
- self.hunk_off1, self.hunk_size1, self.hunk_off2, self.hunk_size2 = hunk_data
- self.line1, self.line2 = self.hunk_off1, self.hunk_off2
- self.output_hunk()
- continue
-
- if re.match(r'^\[', l):
- self.empty_buffer()
- self.spl_print_func(u'<td colspan="2">%s</td>\n' % l)
-
- if re.match(r"^\\ No newline", l):
- if self.hunk_size2 == 0:
- self.buf[-1] = (self.buf[-1][0], self.buf[-1][1] + '\n' + l[2:])
- else:
- self.buf[-1] = (buf[-1][0] + '\n' + l[2:], self.buf[-1][1])
- continue
-
- if self.hunk_size1 <= 0 and self.hunk_size2 <= 0:
- self.empty_buffer()
- continue
-
- m = re.match(r"^\+\[ (\d+) lines removed \]$", l)
- if m:
- self.add_cpt += int(m.group(1))
- self.hunk_size2 -= int(m.group(1))
- self.buf.append((None, l[1:]))
- continue
-
- if re.match(r"^\+", l):
- self.add_cpt += 1
- self.hunk_size2 -= 1
- self.buf.append((None, l[1:]))
- continue
-
- m = re.match(r"^-\[ (\d+) lines removed \]$", l)
- if m:
- self.del_cpt += int(m.group(1))
- self.hunk_size1 -= int(m.group(1))
- self.buf.append((l[1:], None))
- continue
-
- if re.match(r"^-", l):
- self.del_cpt += 1
- self.hunk_size1 -= 1
- self.buf.append((l[1:], None))
- continue
-
- if re.match(r"^ ", l) and self.hunk_size1 and self.hunk_size2:
- self.empty_buffer()
- self.hunk_size1 -= 1
- self.hunk_size2 -= 1
- self.buf.append((l[1:], l[1:]))
- continue
-
- self.empty_buffer()
-
- self.empty_buffer()
+ ydiff = SideBySideDiff(unified_diff)
+ for t, args in ydiff.items():
+ if t == "L":
+ self.output_line(has_internal_linenos, *args)
+ elif t == "H":
+ self.output_hunk_header(*args)
+ elif t == "C":
+ self.spl_print_func(u'<td colspan="2">%s</td>\n' % args)
+ else:
+ raise AssertionError()
return True
except DiffBlockLimitReached:
total = len(unified_diff)
- bytes_left = total - bytes_processed
+ bytes_left = total - ydiff.bytes_processed
frac = bytes_left / total
self.spl_print_func(
u'<tr class="error">'
diff --git a/diffoscope/presenters/html/linediff.py b/diffoscope/presenters/html/linediff.py
deleted file mode 100644
index 710ce36..0000000
--- a/diffoscope/presenters/html/linediff.py
+++ /dev/null
@@ -1,94 +0,0 @@
-# -*- coding: utf-8 -*-
-#
-# diffoscope: in-depth comparison of files, archives, and directories
-#
-# Copyright © 2016 Chris Lamb <lamby at debian.org>
-#
-# diffoscope is free software: you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation, either version 3 of the License, or
-# (at your option) any later version.
-#
-# diffoscope is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with diffoscope. If not, see <https://www.gnu.org/licenses/>.
-
-
-def sane(x):
- r = ""
- for i in x:
- j = ord(i)
- if i not in ['\t', '\n'] and (j < 32):
- r = r + "."
- else:
- r = r + i
- return r
-
-
-def linediff(s, t, diffon, diffoff):
- '''
- Original line diff algorithm of diff2html. It's character based.
- '''
- if len(s):
- s = ''.join([ sane(c) for c in s ])
- if len(t):
- t = ''.join([ sane(c) for c in t ])
-
- m, n = len(s), len(t)
- d = [[(0, 0) for i in range(n+1)] for i in range(m+1)]
-
-
- d[0][0] = (0, (0, 0))
- for i in range(m+1)[1:]:
- d[i][0] = (i,(i-1, 0))
- for j in range(n+1)[1:]:
- d[0][j] = (j,(0, j-1))
-
- for i in range(m+1)[1:]:
- for j in range(n+1)[1:]:
- if s[i-1] == t[j-1]:
- cost = 0
- else:
- cost = 1
- d[i][j] = min((d[i-1][j][0] + 1, (i-1, j)),
- (d[i][j-1][0] + 1, (i, j-1)),
- (d[i-1][j-1][0] + cost, (i-1, j-1)))
-
- l = []
- coord = (m, n)
- while coord != (0, 0):
- l.insert(0, coord)
- x, y = coord
- coord = d[x][y][1]
-
- l1 = []
- l2 = []
-
- for coord in l:
- cx, cy = coord
- child_val = d[cx][cy][0]
-
- father_coord = d[cx][cy][1]
- fx, fy = father_coord
- father_val = d[fx][fy][0]
-
- diff = (cx-fx, cy-fy)
-
- if diff == (0, 1):
- l1.append("")
- l2.append(diffon + t[fy] + diffoff)
- elif diff == (1, 0):
- l1.append(diffon + s[fx] + diffoff)
- l2.append("")
- elif child_val-father_val == 1:
- l1.append(diffon + s[fx] + diffoff)
- l2.append(diffon + t[fy] + diffoff)
- else:
- l1.append(s[fx])
- l2.append(t[fy])
-
- return ''.join(l1).replace(diffoff + diffon, ''), ''.join(l2).replace(diffoff + diffon, '')
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/reproducible/diffoscope.git
More information about the diffoscope
mailing list