format/packfile: implement delta encoding (#172)

* format/packfile: implement delta encoding

- Added all the logic to the encoder to be able to encode ref-delta and offset-delta objects
- Created plumbing.ObjectToPack to handle deltas and standard objects when we are writting them into a packfile
- Added specific encoder delta tests, one standard object and one delta, and one standard object and two deltas

* Requested changes.

* Requested changes

1 files changed, 78 insertions, 14 deletions

diff --git a/plumbing/format/packfile/encoder.go b/plumbing/format/packfile/encoder.go
index 1404dbe..eb1c532 100644
--- a/plumbing/format/packfile/encoder.go
+++ b/plumbing/format/packfile/encoder.go
@@ -15,9 +15,10 @@ import (
 // format
 type Encoder struct {
 	storage storer.ObjectStorer
-	w       io.Writer
+	w       *offsetWriter
 	zw      *zlib.Writer
 	hasher  plumbing.Hasher
+	offsets map[plumbing.Hash]int64
 }
 
 // NewEncoder creates a new packfile encoder using a specific Writer and
@@ -27,28 +28,38 @@ func NewEncoder(w io.Writer, s storer.ObjectStorer) *Encoder {
 		Hash: sha1.New(),
 	}
 	mw := io.MultiWriter(w, h)
+	ow := newOffsetWriter(mw)
 	zw := zlib.NewWriter(mw)
 	return &Encoder{
 		storage: s,
-		w:       mw,
+		w:       ow,
 		zw:      zw,
 		hasher:  h,
+		offsets: make(map[plumbing.Hash]int64),
 	}
 }
 
 // Encode creates a packfile containing all the objects referenced in hashes
 // and writes it to the writer in the Encoder.
 func (e *Encoder) Encode(hashes []plumbing.Hash) (plumbing.Hash, error) {
-	if err := e.head(len(hashes)); err != nil {
-		return plumbing.ZeroHash, err
-	}
-
+	var objects []*ObjectToPack
 	for _, h := range hashes {
 		o, err := e.storage.Object(plumbing.AnyObject, h)
 		if err != nil {
 			return plumbing.ZeroHash, err
 		}
+		// TODO delta selection logic
+		objects = append(objects, newObjectToPack(o))
+	}
+
+	return e.encode(objects)
+}
+func (e *Encoder) encode(objects []*ObjectToPack) (plumbing.Hash, error) {
+	if err := e.head(len(objects)); err != nil {
+		return plumbing.ZeroHash, err
+	}
 
+	for _, o := range objects {
 		if err := e.entry(o); err != nil {
 			return plumbing.ZeroHash, err
 		}
@@ -56,7 +67,6 @@ func (e *Encoder) Encode(hashes []plumbing.Hash) (plumbing.Hash, error) {
 
 	return e.footer()
 }
-
 func (e *Encoder) head(numEntries int) error {
 	return binary.Write(
 		e.w,
@@ -66,19 +76,22 @@ func (e *Encoder) head(numEntries int) error {
 	)
 }
 
-func (e *Encoder) entry(o plumbing.Object) error {
-	t := o.Type()
-	if t == plumbing.OFSDeltaObject || t == plumbing.REFDeltaObject {
-		// TODO implements delta objects
-		return fmt.Errorf("delta object not supported: %v", t)
+func (e *Encoder) entry(o *ObjectToPack) error {
+	offset := e.w.Offset()
+
+	if err := e.entryHead(o.Object.Type(), o.Object.Size()); err != nil {
+		return err
 	}
 
-	if err := e.entryHead(t, o.Size()); err != nil {
+	// Save the position using the original hash, maybe a delta will need it
+	e.offsets[o.Original.Hash()] = offset
+
+	if err := e.writeDeltaHeaderIfAny(o, offset); err != nil {
 		return err
 	}
 
 	e.zw.Reset(e.w)
-	or, err := o.Reader()
+	or, err := o.Object.Reader()
 	if err != nil {
 		return err
 	}
@@ -90,6 +103,38 @@ func (e *Encoder) entry(o plumbing.Object) error {
 	return e.zw.Close()
 }
 
+func (e *Encoder) writeDeltaHeaderIfAny(o *ObjectToPack, offset int64) error {
+	if o.IsDelta() {
+		switch o.Object.Type() {
+		case plumbing.OFSDeltaObject:
+			if err := e.writeOfsDeltaHeader(offset, o.Base.Original.Hash()); err != nil {
+				return err
+			}
+		case plumbing.REFDeltaObject:
+			if err := e.writeRefDeltaHeader(o.Base.Original.Hash()); err != nil {
+				return err
+			}
+		}
+	}
+
+	return nil
+}
+
+func (e *Encoder) writeRefDeltaHeader(source plumbing.Hash) error {
+	return binary.Write(e.w, source)
+}
+
+func (e *Encoder) writeOfsDeltaHeader(deltaOffset int64, source plumbing.Hash) error {
+	// because it is an offset delta, we need the source
+	// object position
+	offset, ok := e.offsets[source]
+	if !ok {
+		return fmt.Errorf("delta source not found. Hash: %v", source)
+	}
+
+	return binary.WriteVariableWidthInt(e.w, deltaOffset-offset)
+}
+
 func (e *Encoder) entryHead(typeNum plumbing.ObjectType, size int64) error {
 	t := int64(typeNum)
 	header := []byte{}
@@ -114,3 +159,22 @@ func (e *Encoder) footer() (plumbing.Hash, error) {
 	h := e.hasher.Sum()
 	return h, binary.Write(e.w, h)
 }
+
+type offsetWriter struct {
+	w      io.Writer
+	offset int64
+}
+
+func newOffsetWriter(w io.Writer) *offsetWriter {
+	return &offsetWriter{w: w}
+}
+
+func (ow *offsetWriter) Write(p []byte) (n int, err error) {
+	n, err = ow.w.Write(p)
+	ow.offset += int64(n)
+	return n, err
+}
+
+func (ow *offsetWriter) Offset() int64 {
+	return ow.offset
+}