packfile: delta diff implementation (#159)

* packfile: delta diff implementation

- Renamed delta.go to patch_delta.go
- Added diff_delta.go file
- Added tests that creates a diff and then tries to patch it

* Requested changes

4 files changed, 637 insertions, 0 deletions

diff --git a/plumbing/format/packfile/delta_test.go b/plumbing/format/packfile/delta_test.go
new file mode 100644
index 0000000..4ef9b70
--- /dev/null
+++ b/plumbing/format/packfile/delta_test.go
@@ -0,0 +1,93 @@
+package packfile
+
+import (
+	"fmt"
+
+	. "gopkg.in/check.v1"
+)
+
+type DeltaSuite struct {
+	testCases []deltaTest
+}
+
+var _ = Suite(&DeltaSuite{})
+
+type piece struct {
+	val   string
+	times int
+}
+
+type deltaTest struct {
+	description string
+	base        []piece
+	target      []piece
+}
+
+func (s *DeltaSuite) SetUpSuite(c *C) {
+	s.testCases = []deltaTest{{
+		description: "distinct file",
+		base:        []piece{{"0", 300}},
+		target:      []piece{{"2", 200}},
+	}, {
+		description: "same file",
+		base:        []piece{{"1", 3000}},
+		target:      []piece{{"1", 3000}},
+	}, {
+		description: "small file",
+		base:        []piece{{"1", 3}},
+		target:      []piece{{"1", 3}, {"0", 1}},
+	}, {
+		description: "big file",
+		base:        []piece{{"1", 300000}},
+		target:      []piece{{"1", 30000}, {"0", 1000000}},
+	}, {
+		description: "add elements before",
+		base:        []piece{{"0", 200}},
+		target:      []piece{{"1", 300}, {"0", 200}},
+	}, {
+		description: "add 10 times more elements at the end",
+		base:        []piece{{"1", 300}, {"0", 200}},
+		target:      []piece{{"0", 2000}},
+	}, {
+		description: "add elements between",
+		base:        []piece{{"0", 400}},
+		target:      []piece{{"0", 200}, {"1", 200}, {"0", 200}},
+	}, {
+		description: "add elements after",
+		base:        []piece{{"0", 200}},
+		target:      []piece{{"0", 200}, {"1", 200}},
+	}, {
+		description: "modify elements at the end",
+		base:        []piece{{"1", 300}, {"0", 200}},
+		target:      []piece{{"0", 100}},
+	}, {
+		description: "complex modification",
+		base: []piece{{"0", 3}, {"1", 40}, {"2", 30}, {"3", 2},
+			{"4", 400}, {"5", 23}},
+		target: []piece{{"1", 30}, {"2", 20}, {"7", 40}, {"4", 400},
+			{"5", 10}},
+	}}
+}
+
+func (s *DeltaSuite) TestAddDelta(c *C) {
+	for _, t := range s.testCases {
+		baseBuf := genBytes(t.base)
+		targetBuf := genBytes(t.target)
+		delta := DiffDelta(baseBuf, targetBuf)
+		result := PatchDelta(baseBuf, delta)
+
+		c.Log(fmt.Printf("Executing test case: %s\n", t.description))
+		c.Assert(result, DeepEquals, targetBuf)
+	}
+}
+
+func genBytes(elements []piece) []byte {
+	var result []byte
+	for _, e := range elements {
+		for i := 0; i < e.times; i++ {
+			result = append(result, e.val...)
+		}
+	}
+
+	return result
+}
diff --git a/plumbing/format/packfile/diff.go b/plumbing/format/packfile/diff.go
new file mode 100644
index 0000000..ff34329
--- /dev/null
+++ b/plumbing/format/packfile/diff.go
@@ -0,0 +1,397 @@
+package packfile
+
+/*
+
+Copyright (c) 2013, Patrick Mezard
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+    Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+    The names of its contributors may not be used to endorse or promote
+products derived from this software without specific prior written
+permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+*/
+
+// Code based on https://github.com/pmezard/go-difflib
+// Removed unnecessary code for this use case and changed string inputs to byte
+
+type match struct {
+	A    int
+	B    int
+	Size int
+}
+
+type opCode struct {
+	Tag byte
+	I1  int
+	I2  int
+	J1  int
+	J2  int
+}
+
+// SequenceMatcher compares sequence of bytes. The basic
+// algorithm predates, and is a little fancier than, an algorithm
+// published in the late 1980's by Ratcliff and Obershelp under the
+// hyperbolic name "gestalt pattern matching".  The basic idea is to find
+// the longest contiguous matching subsequence that contains no "junk"
+// elements (R-O doesn't address junk).  The same idea is then applied
+// recursively to the pieces of the sequences to the left and to the right
+// of the matching subsequence.  This does not yield minimal edit
+// sequences, but does tend to yield matches that "look right" to people.
+//
+// SequenceMatcher tries to compute a "human-friendly diff" between two
+// sequences.  Unlike e.g. UNIX(tm) diff, the fundamental notion is the
+// longest *contiguous* & junk-free matching subsequence.  That's what
+// catches peoples' eyes.  The Windows(tm) windiff has another interesting
+// notion, pairing up elements that appear uniquely in each sequence.
+// That, and the method here, appear to yield more intuitive difference
+// reports than does diff.  This method appears to be the least vulnerable
+// to synching up on blocks of "junk lines", though (like blank lines in
+// ordinary text files, or maybe "<P>" lines in HTML files).  That may be
+// because this is the only method of the 3 that has a *concept* of
+// "junk" <wink>.
+//
+// Timing:  Basic R-O is cubic time worst case and quadratic time expected
+// case.  SequenceMatcher is quadratic time for the worst case and has
+// expected-case behavior dependent in a complicated way on how many
+// elements the sequences have in common; best case time is linear.
+type sequenceMatcher struct {
+	a              []byte
+	b              []byte
+	b2j            map[byte][]int
+	IsJunk         func(byte) bool
+	autoJunk       bool
+	bJunk          map[byte]struct{}
+	matchingBlocks []match
+	fullBCount     map[byte]int
+	bPopular       map[byte]struct{}
+	opCodes        []opCode
+}
+
+func newMatcher(a, b []byte) *sequenceMatcher {
+	m := sequenceMatcher{autoJunk: true}
+	m.SetSeqs(a, b)
+	return &m
+}
+
+// Set two sequences to be compared.
+func (m *sequenceMatcher) SetSeqs(a, b []byte) {
+	m.SetSeq1(a)
+	m.SetSeq2(b)
+}
+
+// Set the first sequence to be compared. The second sequence to be compared is
+// not changed.
+//
+// SequenceMatcher computes and caches detailed information about the second
+// sequence, so if you want to compare one sequence S against many sequences,
+// use .SetSeq2(s) once and call .SetSeq1(x) repeatedly for each of the other
+// sequences.
+//
+// See also SetSeqs() and SetSeq2().
+func (m *sequenceMatcher) SetSeq1(a []byte) {
+	if &a == &m.a {
+		return
+	}
+	m.a = a
+	m.matchingBlocks = nil
+	m.opCodes = nil
+}
+
+// Set the second sequence to be compared. The first sequence to be compared is
+// not changed.
+func (m *sequenceMatcher) SetSeq2(b []byte) {
+	if &b == &m.b {
+		return
+	}
+	m.b = b
+	m.matchingBlocks = nil
+	m.opCodes = nil
+	m.fullBCount = nil
+	m.chainB()
+}
+
+func (m *sequenceMatcher) chainB() {
+	// Populate line -> index mapping
+	b2j := map[byte][]int{}
+	for i, s := range m.b {
+		indices := b2j[s]
+		indices = append(indices, i)
+		b2j[s] = indices
+	}
+
+	// Purge junk elements
+	m.bJunk = map[byte]struct{}{}
+	if m.IsJunk != nil {
+		junk := m.bJunk
+		for s := range b2j {
+			if m.IsJunk(s) {
+				junk[s] = struct{}{}
+			}
+		}
+		for s := range junk {
+			delete(b2j, s)
+		}
+	}
+
+	// Purge remaining popular elements
+	popular := map[byte]struct{}{}
+	n := len(m.b)
+	if m.autoJunk && n >= 200 {
+		ntest := n/100 + 1
+		for s, indices := range b2j {
+			if len(indices) > ntest {
+				popular[s] = struct{}{}
+			}
+		}
+		for s := range popular {
+			delete(b2j, s)
+		}
+	}
+	m.bPopular = popular
+	m.b2j = b2j
+}
+
+func (m *sequenceMatcher) isBJunk(s byte) bool {
+	_, ok := m.bJunk[s]
+	return ok
+}
+
+// Find longest matching block in a[alo:ahi] and b[blo:bhi].
+//
+// If IsJunk is not defined:
+//
+// Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
+//     alo <= i <= i+k <= ahi
+//     blo <= j <= j+k <= bhi
+// and for all (i',j',k') meeting those conditions,
+//     k >= k'
+//     i <= i'
+//     and if i == i', j <= j'
+//
+// In other words, of all maximal matching blocks, return one that
+// starts earliest in a, and of all those maximal matching blocks that
+// start earliest in a, return the one that starts earliest in b.
+//
+// If IsJunk is defined, first the longest matching block is
+// determined as above, but with the additional restriction that no
+// junk element appears in the block.  Then that block is extended as
+// far as possible by matching (only) junk elements on both sides.  So
+// the resulting block never matches on junk except as identical junk
+// happens to be adjacent to an "interesting" match.
+//
+// If no blocks match, return (alo, blo, 0).
+func (m *sequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) match {
+	// CAUTION:  stripping common prefix or suffix would be incorrect.
+	// E.g.,
+	//    ab
+	//    acab
+	// Longest matching block is "ab", but if common prefix is
+	// stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
+	// strip, so ends up claiming that ab is changed to acab by
+	// inserting "ca" in the middle.  That's minimal but unintuitive:
+	// "it's obvious" that someone inserted "ac" at the front.
+	// Windiff ends up at the same place as diff, but by pairing up
+	// the unique 'b's and then matching the first two 'a's.
+	besti, bestj, bestsize := alo, blo, 0
+
+	// find longest junk-free match
+	// during an iteration of the loop, j2len[j] = length of longest
+	// junk-free match ending with a[i-1] and b[j]
+	j2len := map[int]int{}
+	for i := alo; i != ahi; i++ {
+		// look at all instances of a[i] in b; note that because
+		// b2j has no junk keys, the loop is skipped if a[i] is junk
+		newj2len := map[int]int{}
+		for _, j := range m.b2j[m.a[i]] {
+			// a[i] matches b[j]
+			if j < blo {
+				continue
+			}
+			if j >= bhi {
+				break
+			}
+			k := j2len[j-1] + 1
+			newj2len[j] = k
+			if k > bestsize {
+				besti, bestj, bestsize = i-k+1, j-k+1, k
+			}
+		}
+		j2len = newj2len
+	}
+
+	// Extend the best by non-junk elements on each end.  In particular,
+	// "popular" non-junk elements aren't in b2j, which greatly speeds
+	// the inner loop above, but also means "the best" match so far
+	// doesn't contain any junk *or* popular non-junk elements.
+	for besti > alo && bestj > blo && !m.isBJunk(m.b[bestj-1]) &&
+		m.a[besti-1] == m.b[bestj-1] {
+		besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
+	}
+	for besti+bestsize < ahi && bestj+bestsize < bhi &&
+		!m.isBJunk(m.b[bestj+bestsize]) &&
+		m.a[besti+bestsize] == m.b[bestj+bestsize] {
+		bestsize += 1
+	}
+
+	// Now that we have a wholly interesting match (albeit possibly
+	// empty!), we may as well suck up the matching junk on each
+	// side of it too.  Can't think of a good reason not to, and it
+	// saves post-processing the (possibly considerable) expense of
+	// figuring out what to do with it.  In the case of an empty
+	// interesting match, this is clearly the right thing to do,
+	// because no other kind of match is possible in the regions.
+	for besti > alo && bestj > blo && m.isBJunk(m.b[bestj-1]) &&
+		m.a[besti-1] == m.b[bestj-1] {
+		besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
+	}
+	for besti+bestsize < ahi && bestj+bestsize < bhi &&
+		m.isBJunk(m.b[bestj+bestsize]) &&
+		m.a[besti+bestsize] == m.b[bestj+bestsize] {
+		bestsize += 1
+	}
+
+	return match{A: besti, B: bestj, Size: bestsize}
+}
+
+// Return list of triples describing matching subsequences.
+//
+// Each triple is of the form (i, j, n), and means that
+// a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
+// i and in j. It's also guaranteed that if (i, j, n) and (i', j', n') are
+// adjacent triples in the list, and the second is not the last triple in the
+// list, then i+n != i' or j+n != j'. IOW, adjacent triples never describe
+// adjacent equal blocks.
+//
+// The last triple is a dummy, (len(a), len(b), 0), and is the only
+// triple with n==0.
+func (m *sequenceMatcher) GetMatchingBlocks() []match {
+	if m.matchingBlocks != nil {
+		return m.matchingBlocks
+	}
+
+	var matchBlocks func(alo, ahi, blo, bhi int, matched []match) []match
+	matchBlocks = func(alo, ahi, blo, bhi int, matched []match) []match {
+		match := m.findLongestMatch(alo, ahi, blo, bhi)
+		i, j, k := match.A, match.B, match.Size
+		if match.Size > 0 {
+			if alo < i && blo < j {
+				matched = matchBlocks(alo, i, blo, j, matched)
+			}
+			matched = append(matched, match)
+			if i+k < ahi && j+k < bhi {
+				matched = matchBlocks(i+k, ahi, j+k, bhi, matched)
+			}
+		}
+		return matched
+	}
+	matched := matchBlocks(0, len(m.a), 0, len(m.b), nil)
+
+	// It's possible that we have adjacent equal blocks in the
+	// matching_blocks list now.
+	nonAdjacent := []match{}
+	i1, j1, k1 := 0, 0, 0
+	for _, b := range matched {
+		// Is this block adjacent to i1, j1, k1?
+		i2, j2, k2 := b.A, b.B, b.Size
+		if i1+k1 == i2 && j1+k1 == j2 {
+			// Yes, so collapse them -- this just increases the length of
+			// the first block by the length of the second, and the first
+			// block so lengthened remains the block to compare against.
+			k1 += k2
+		} else {
+			// Not adjacent.  Remember the first block (k1==0 means it's
+			// the dummy we started with), and make the second block the
+			// new block to compare against.
+			if k1 > 0 {
+				nonAdjacent = append(nonAdjacent, match{i1, j1, k1})
+			}
+			i1, j1, k1 = i2, j2, k2
+		}
+	}
+	if k1 > 0 {
+		nonAdjacent = append(nonAdjacent, match{i1, j1, k1})
+	}
+
+	nonAdjacent = append(nonAdjacent, match{len(m.a), len(m.b), 0})
+	m.matchingBlocks = nonAdjacent
+	return m.matchingBlocks
+}
+
+const (
+	tagReplace = 'r'
+	tagDelete  = 'd'
+	tagInsert  = 'i'
+	tagEqual   = 'e'
+)
+
+// Return list of 5-tuples describing how to turn a into b.
+//
+// Each tuple is of the form (tag, i1, i2, j1, j2).  The first tuple
+// has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
+// tuple preceding it, and likewise for j1 == the previous j2.
+//
+// The tags are characters, with these meanings:
+//
+// 'r' (replace):  a[i1:i2] should be replaced by b[j1:j2]
+//
+// 'd' (delete):   a[i1:i2] should be deleted, j1==j2 in this case.
+//
+// 'i' (insert):   b[j1:j2] should be inserted at a[i1:i1], i1==i2 in this case.
+//
+// 'e' (equal):    a[i1:i2] == b[j1:j2]
+func (m *sequenceMatcher) GetOpCodes() []opCode {
+	if m.opCodes != nil {
+		return m.opCodes
+	}
+	i, j := 0, 0
+	matching := m.GetMatchingBlocks()
+	opCodes := make([]opCode, 0, len(matching))
+	for _, m := range matching {
+		//  invariant:  we've pumped out correct diffs to change
+		//  a[:i] into b[:j], and the next matching block is
+		//  a[ai:ai+size] == b[bj:bj+size]. So we need to pump
+		//  out a diff to change a[i:ai] into b[j:bj], pump out
+		//  the matching block, and move (i,j) beyond the match
+		ai, bj, size := m.A, m.B, m.Size
+		tag := byte(0)
+		if i < ai && j < bj {
+			tag = tagReplace
+		} else if i < ai {
+			tag = tagDelete
+		} else if j < bj {
+			tag = tagInsert
+		}
+		if tag > 0 {
+			opCodes = append(opCodes, opCode{tag, i, ai, j, bj})
+		}
+		i, j = ai+size, bj+size
+		// the list of matching blocks is terminated by a
+		// sentinel with size 0
+		if size > 0 {
+			opCodes = append(opCodes, opCode{tagEqual, ai, i, bj, j})
+		}
+	}
+	m.opCodes = opCodes
+	return m.opCodes
+}
diff --git a/plumbing/format/packfile/diff_delta.go b/plumbing/format/packfile/diff_delta.go
new file mode 100644
index 0000000..eaed377
--- /dev/null
+++ b/plumbing/format/packfile/diff_delta.go
@@ -0,0 +1,147 @@
+package packfile
+
+import (
+	"io/ioutil"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+)
+
+// See https://github.com/jelmer/dulwich/blob/master/dulwich/pack.py and
+// https://github.com/tarruda/node-git-core/blob/master/src/js/delta.js
+// for more info
+
+const (
+	maxCopyLen = 0xffff
+)
+
+// GetDelta returns the way of how to transform base object to target object
+func GetDelta(base, target plumbing.Object) ([]byte, error) {
+	baseReader, err := base.Reader()
+	if err != nil {
+		return nil, err
+	}
+	targetReader, err := target.Reader()
+	if err != nil {
+		return nil, err
+	}
+
+	baseBuf, err := ioutil.ReadAll(baseReader)
+	if err != nil {
+		return nil, err
+	}
+
+	targetBuf, err := ioutil.ReadAll(targetReader)
+	if err != nil {
+		return nil, err
+	}
+
+	return DiffDelta(baseBuf, targetBuf), nil
+}
+
+// DiffDelta returns the way of how to transform baseBuf to targetBuf
+func DiffDelta(baseBuf []byte, targetBuf []byte) []byte {
+	var outBuff []byte
+
+	outBuff = append(outBuff, deltaEncodeSize(len(baseBuf))...)
+	outBuff = append(outBuff, deltaEncodeSize(len(targetBuf))...)
+
+	sm := newMatcher(baseBuf, targetBuf)
+	for _, op := range sm.GetOpCodes() {
+		switch {
+		case op.Tag == tagEqual:
+			copyStart := op.I1
+			copyLen := op.I2 - op.I1
+			for {
+				if copyLen <= 0 {
+					break
+				}
+				var toCopy int
+				if copyLen < maxCopyLen {
+					toCopy = copyLen
+				} else {
+					toCopy = maxCopyLen
+				}
+
+				outBuff = append(outBuff, encodeCopyOperation(copyStart, toCopy)...)
+				copyStart += toCopy
+				copyLen -= toCopy
+			}
+		case op.Tag == tagReplace || op.Tag == tagInsert:
+			s := op.J2 - op.J1
+			o := op.J1
+			for {
+				if s <= 127 {
+					break
+				}
+				outBuff = append(outBuff, byte(127))
+				outBuff = append(outBuff, targetBuf[o:o+127]...)
+				s -= 127
+				o += 127
+			}
+			outBuff = append(outBuff, byte(s))
+			outBuff = append(outBuff, targetBuf[o:o+s]...)
+		}
+	}
+
+	return outBuff
+}
+
+func deltaEncodeSize(size int) []byte {
+	var ret []byte
+	c := size & 0x7f
+	size >>= 7
+	for {
+		if size == 0 {
+			break
+		}
+
+		ret = append(ret, byte(c|0x80))
+		c = size & 0x7f
+		size >>= 7
+	}
+	ret = append(ret, byte(c))
+
+	return ret
+}
+
+func encodeCopyOperation(offset, length int) []byte {
+	code := 0x80
+	var opcodes []byte
+
+	if offset&0xff != 0 {
+		opcodes = append(opcodes, byte(offset&0xff))
+		code |= 0x01
+	}
+
+	if offset&0xff00 != 0 {
+		opcodes = append(opcodes, byte((offset&0xff00)>>8))
+		code |= 0x02
+	}
+
+	if offset&0xff0000 != 0 {
+		opcodes = append(opcodes, byte((offset&0xff0000)>>16))
+		code |= 0x04
+	}
+
+	if offset&0xff000000 != 0 {
+		opcodes = append(opcodes, byte((offset&0xff000000)>>24))
+		code |= 0x08
+	}
+
+	if length&0xff != 0 {
+		opcodes = append(opcodes, byte(length&0xff))
+		code |= 0x10
+	}
+
+	if length&0xff00 != 0 {
+		opcodes = append(opcodes, byte((length&0xff00)>>8))
+		code |= 0x20
+	}
+
+	if length&0xff0000 != 0 {
+		opcodes = append(opcodes, byte((length&0xff0000)>>16))
+		code |= 0x40
+	}
+
+	return append([]byte{byte(code)}, opcodes...)
+}
diff --git a/plumbing/format/packfile/delta.go b/plumbing/format/packfile/patch_delta.go
index 2493a39..2493a39 100644
--- a/plumbing/format/packfile/delta.go
+++ b/plumbing/format/packfile/patch_delta.go