storage: reuse deltas from packfiles

* plumbing: add DeltaObject interface for EncodedObjects that
  are deltas and hold additional information about them, such
  as the hash of the base object.

* plumbing/storer: add DeltaObjectStorer interface for object
  storers that can return DeltaObject. Note that calls to
  EncodedObject will never return instances of DeltaObject.
  That requires explicit calls to DeltaObject.

* storage/filesystem: implement DeltaObjectStorer interface.

* plumbing/packfile: packfile encoder now supports reusing
  deltas that are already computed (e.g. from an existing
  packfile) if the storage implements DeltaObjectStorer.
  Reusing deltas boosts performance of packfile generation
  (e.g. on push).

12 files changed, 491 insertions, 107 deletions

diff --git a/plumbing/format/packfile/delta_selector.go b/plumbing/format/packfile/delta_selector.go
index 20c8cea..4bee6d3 100644
--- a/plumbing/format/packfile/delta_selector.go
+++ b/plumbing/format/packfile/delta_selector.go
@@ -47,17 +47,127 @@ func (dw *deltaSelector) ObjectsToPack(hashes []plumbing.Hash) ([]*ObjectToPack,
 func (dw *deltaSelector) objectsToPack(hashes []plumbing.Hash) ([]*ObjectToPack, error) {
 	var objectsToPack []*ObjectToPack
 	for _, h := range hashes {
-		o, err := dw.storer.EncodedObject(plumbing.AnyObject, h)
+		o, err := dw.encodedDeltaObject(h)
 		if err != nil {
 			return nil, err
 		}
 
-		objectsToPack = append(objectsToPack, newObjectToPack(o))
+		otp := newObjectToPack(o)
+		if _, ok := o.(plumbing.DeltaObject); ok {
+			otp.Original = nil
+		}
+
+		objectsToPack = append(objectsToPack, otp)
+	}
+
+	if err := dw.fixAndBreakChains(objectsToPack); err != nil {
+		return nil, err
 	}
 
 	return objectsToPack, nil
 }
 
+func (dw *deltaSelector) encodedDeltaObject(h plumbing.Hash) (plumbing.EncodedObject, error) {
+	edos, ok := dw.storer.(storer.DeltaObjectStorer)
+	if !ok {
+		return dw.encodedObject(h)
+	}
+
+	return edos.DeltaObject(plumbing.AnyObject, h)
+}
+
+func (dw *deltaSelector) encodedObject(h plumbing.Hash) (plumbing.EncodedObject, error) {
+	return dw.storer.EncodedObject(plumbing.AnyObject, h)
+}
+
+func (dw *deltaSelector) fixAndBreakChains(objectsToPack []*ObjectToPack) error {
+	m := make(map[plumbing.Hash]*ObjectToPack, len(objectsToPack))
+	for _, otp := range objectsToPack {
+		m[otp.Hash()] = otp
+	}
+
+	for _, otp := range objectsToPack {
+		if err := dw.fixAndBreakChainsOne(m, otp); err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+func (dw *deltaSelector) fixAndBreakChainsOne(objectsToPack map[plumbing.Hash]*ObjectToPack, otp *ObjectToPack) error {
+	isDelta := otp.Object.Type() == plumbing.OFSDeltaObject ||
+		otp.Object.Type() == plumbing.REFDeltaObject
+	if !isDelta {
+		return nil
+	}
+
+	// Initial ObjectToPack instances might have a delta assigned to Object
+	// but no actual base initially. Once Base is assigned to a delta, it means
+	// we already fixed it.
+	if otp.Base != nil {
+		return nil
+	}
+
+	do, ok := otp.Object.(plumbing.DeltaObject)
+	if !ok {
+		// if this is not a DeltaObject, then we cannot retrieve its base,
+		// so we have to break the delta chain here.
+		return dw.undeltify(otp)
+	}
+
+	base, ok := objectsToPack[do.BaseHash()]
+	if !ok {
+		// The base of the delta is not in our list of objects to pack, so
+		// we break the chain.
+		return dw.undeltify(otp)
+	}
+
+	if base.Size() <= otp.Size() {
+		// Bases should be bigger
+		return dw.undeltify(otp)
+	}
+
+	if err := dw.fixAndBreakChainsOne(objectsToPack, base); err != nil {
+		return err
+	}
+
+	otp.SetDelta(base, otp.Object)
+	return nil
+}
+
+func (dw *deltaSelector) restoreOriginal(otp *ObjectToPack) error {
+	if otp.Original != nil {
+		return nil
+	}
+
+	isDelta := otp.Object.Type() == plumbing.OFSDeltaObject ||
+		otp.Object.Type() == plumbing.REFDeltaObject
+	if !isDelta {
+		return nil
+	}
+
+	obj, err := dw.encodedObject(otp.Hash())
+	if err != nil {
+		return err
+	}
+
+	otp.Original = obj
+	return nil
+}
+
+// undeltify undeltifies an *ObjectToPack by retrieving the original object from
+// the storer and resetting it.
+func (dw *deltaSelector) undeltify(otp *ObjectToPack) error {
+	if err := dw.restoreOriginal(otp); err != nil {
+		return err
+	}
+
+	otp.Object = otp.Original
+	otp.Depth = 0
+	return nil
+}
+
 func (dw *deltaSelector) sort(objectsToPack []*ObjectToPack) {
 	sort.Sort(byTypeAndSize(objectsToPack))
 }
@@ -66,15 +176,24 @@ func (dw *deltaSelector) walk(objectsToPack []*ObjectToPack) error {
 	for i := 0; i < len(objectsToPack); i++ {
 		target := objectsToPack[i]
 
-		// We only want to create deltas from specific types
-		if !applyDelta[target.Original.Type()] {
+		// If we already have a delta, we don't try to find a new one for this
+		// object. This happens when a delta is set to be reused from an existing
+		// packfile.
+		if target.IsDelta() {
+			continue
+		}
+
+		// We only want to create deltas from specific types.
+		if !applyDelta[target.Type()] {
 			continue
 		}
 
 		for j := i - 1; j >= 0; j-- {
 			base := objectsToPack[j]
 			// Objects must use only the same type as their delta base.
-			if base.Original.Type() != target.Original.Type() {
+			// Since objectsToPack is sorted by type and size, once we find
+			// a different type, we know we won't find more of them.
+			if base.Type() != target.Type() {
 				break
 			}
 
@@ -89,7 +208,7 @@ func (dw *deltaSelector) walk(objectsToPack []*ObjectToPack) error {
 
 func (dw *deltaSelector) tryToDeltify(base, target *ObjectToPack) error {
 	// If the sizes are radically different, this is a bad pairing.
-	if target.Original.Size() < base.Original.Size()>>4 {
+	if target.Size() < base.Size()>>4 {
 		return nil
 	}
 
@@ -106,10 +225,20 @@ func (dw *deltaSelector) tryToDeltify(base, target *ObjectToPack) error {
 	}
 
 	// If we have to insert a lot to make this work, find another.
-	if base.Original.Size()-target.Object.Size() > msz {
+	if base.Size()-target.Size() > msz {
 		return nil
 	}
 
+	// Original object might not be present if we're reusing a delta, so we
+	// ensure it is restored.
+	if err := dw.restoreOriginal(target); err != nil {
+		return err
+	}
+
+	if err := dw.restoreOriginal(base); err != nil {
+		return err
+	}
+
 	// Now we can generate the delta using originals
 	delta, err := GetDelta(base.Original, target.Original)
 	if err != nil {
@@ -162,13 +291,13 @@ func (a byTypeAndSize) Len() int { return len(a) }
 func (a byTypeAndSize) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
 
 func (a byTypeAndSize) Less(i, j int) bool {
-	if a[i].Object.Type() < a[j].Object.Type() {
+	if a[i].Type() < a[j].Type() {
 		return false
 	}
 
-	if a[i].Object.Type() > a[j].Object.Type() {
+	if a[i].Type() > a[j].Type() {
 		return true
 	}
 
-	return a[i].Object.Size() > a[j].Object.Size()
+	return a[i].Size() > a[j].Size()
 }
diff --git a/plumbing/format/packfile/encoder.go b/plumbing/format/packfile/encoder.go
index ae83752..1426559 100644
--- a/plumbing/format/packfile/encoder.go
+++ b/plumbing/format/packfile/encoder.go
@@ -18,6 +18,9 @@ type Encoder struct {
 	w            *offsetWriter
 	zw           *zlib.Writer
 	hasher       plumbing.Hasher
+	// offsets is a map of object hashes to corresponding offsets in the packfile.
+	// It is used to determine offset of the base of a delta when a OFS_DELTA is
+	// used.
 	offsets      map[plumbing.Hash]int64
 	useRefDeltas bool
 }
@@ -78,25 +81,24 @@ func (e *Encoder) head(numEntries int) error {
 
 func (e *Encoder) entry(o *ObjectToPack) error {
 	offset := e.w.Offset()
+	e.offsets[o.Hash()] = offset
 
 	if o.IsDelta() {
 		if err := e.writeDeltaHeader(o, offset); err != nil {
 			return err
 		}
 	} else {
-		if err := e.entryHead(o.Object.Type(), o.Object.Size()); err != nil {
+		if err := e.entryHead(o.Type(), o.Size()); err != nil {
 			return err
 		}
 	}
 
-	// Save the position using the original hash, maybe a delta will need it
-	e.offsets[o.Original.Hash()] = offset
-
 	e.zw.Reset(e.w)
 	or, err := o.Object.Reader()
 	if err != nil {
 		return err
 	}
+
 	_, err = io.Copy(e.zw, or)
 	if err != nil {
 		return err
@@ -117,9 +119,9 @@ func (e *Encoder) writeDeltaHeader(o *ObjectToPack, offset int64) error {
 	}
 
 	if e.useRefDeltas {
-		return e.writeRefDeltaHeader(o.Base.Original.Hash())
+		return e.writeRefDeltaHeader(o.Base.Hash())
 	} else {
-		return e.writeOfsDeltaHeader(offset, o.Base.Original.Hash())
+		return e.writeOfsDeltaHeader(offset, o.Base.Hash())
 	}
 }
 
@@ -128,14 +130,19 @@ func (e *Encoder) writeRefDeltaHeader(base plumbing.Hash) error {
 }
 
 func (e *Encoder) writeOfsDeltaHeader(deltaOffset int64, base plumbing.Hash) error {
-	// because it is an offset delta, we need the base
-	// object position
-	offset, ok := e.offsets[base]
+	baseOffset, ok := e.offsets[base]
 	if !ok {
-		return fmt.Errorf("delta base not found. Hash: %v", base)
+		return fmt.Errorf("base for delta not found, base hash: %v", base)
+	}
+
+	// for OFS_DELTA, offset of the base is interpreted as negative offset
+	// relative to the type-byte of the header of the ofs-delta entry.
+	relativeOffset := deltaOffset-baseOffset
+	if relativeOffset <= 0 {
+		return fmt.Errorf("bad offset for OFS_DELTA entry: %d", relativeOffset)
 	}
 
-	return binary.WriteVariableWidthInt(e.w, deltaOffset-offset)
+	return binary.WriteVariableWidthInt(e.w, relativeOffset)
 }
 
 func (e *Encoder) entryHead(typeNum plumbing.ObjectType, size int64) error {
diff --git a/plumbing/format/packfile/encoder_advanced_test.go b/plumbing/format/packfile/encoder_advanced_test.go
new file mode 100644
index 0000000..d92e2c4
--- /dev/null
+++ b/plumbing/format/packfile/encoder_advanced_test.go
@@ -0,0 +1,91 @@
+package packfile_test
+
+import (
+	"bytes"
+	"math/rand"
+
+	"gopkg.in/src-d/go-git.v4/plumbing"
+	. "gopkg.in/src-d/go-git.v4/plumbing/format/packfile"
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
+	"gopkg.in/src-d/go-git.v4/storage/filesystem"
+	"gopkg.in/src-d/go-git.v4/storage/memory"
+
+	"github.com/src-d/go-git-fixtures"
+	. "gopkg.in/check.v1"
+)
+
+type EncoderAdvancedSuite struct {
+	fixtures.Suite
+}
+
+var _ = Suite(&EncoderAdvancedSuite{})
+
+func (s *EncoderAdvancedSuite) TestEncodeDecode(c *C) {
+	fixs := fixtures.Basic().ByTag("packfile").ByTag(".git")
+	fixs = append(fixs, fixtures.ByURL("https://github.com/src-d/go-git.git").
+		ByTag("packfile").ByTag(".git").One())
+	fixs.Test(c, func(f *fixtures.Fixture) {
+		storage, err := filesystem.NewStorage(f.DotGit())
+		c.Assert(err, IsNil)
+		s.testEncodeDecode(c, storage)
+	})
+
+}
+
+func (s *EncoderAdvancedSuite) testEncodeDecode(c *C, storage storer.Storer) {
+
+	objIter, err := storage.IterEncodedObjects(plumbing.AnyObject)
+	c.Assert(err, IsNil)
+
+	expectedObjects := map[plumbing.Hash]bool{}
+	var hashes []plumbing.Hash
+	err = objIter.ForEach(func(o plumbing.EncodedObject) error {
+		expectedObjects[o.Hash()] = true
+		hashes = append(hashes, o.Hash())
+		return err
+
+	})
+	c.Assert(err, IsNil)
+
+	// Shuffle hashes to avoid delta selector getting order right just because
+	// the initial order is correct.
+	auxHashes := make([]plumbing.Hash, len(hashes))
+	for i, j := range rand.Perm(len(hashes)) {
+		auxHashes[j] = hashes[i]
+	}
+	hashes = auxHashes
+
+	buf := bytes.NewBuffer(nil)
+	enc := NewEncoder(buf, storage, false)
+	_, err = enc.Encode(hashes)
+	c.Assert(err, IsNil)
+
+	scanner := NewScanner(buf)
+	storage = memory.NewStorage()
+	d, err := NewDecoder(scanner, storage)
+	c.Assert(err, IsNil)
+	_, err = d.Decode()
+	c.Assert(err, IsNil)
+
+	objIter, err = storage.IterEncodedObjects(plumbing.AnyObject)
+	c.Assert(err, IsNil)
+	obtainedObjects := map[plumbing.Hash]bool{}
+	err = objIter.ForEach(func(o plumbing.EncodedObject) error {
+		obtainedObjects[o.Hash()] = true
+		return nil
+	})
+	c.Assert(err, IsNil)
+	c.Assert(obtainedObjects, DeepEquals, expectedObjects)
+
+	for h := range obtainedObjects {
+		if !expectedObjects[h] {
+			c.Errorf("obtained unexpected object: %s", h)
+		}
+	}
+
+	for h := range expectedObjects {
+		if !obtainedObjects[h] {
+			c.Errorf("missing object: %s", h)
+		}
+	}
+}
diff --git a/plumbing/format/packfile/encoder_test.go b/plumbing/format/packfile/encoder_test.go
index 551d7ec..b5b0c42 100644
--- a/plumbing/format/packfile/encoder_test.go
+++ b/plumbing/format/packfile/encoder_test.go
@@ -2,11 +2,9 @@ package packfile
 
 import (
 	"bytes"
-	"io"
 
 	"github.com/src-d/go-git-fixtures"
 	"gopkg.in/src-d/go-git.v4/plumbing"
-	"gopkg.in/src-d/go-git.v4/plumbing/storer"
 	"gopkg.in/src-d/go-git.v4/storage/memory"
 
 	. "gopkg.in/check.v1"
@@ -88,80 +86,6 @@ func (s *EncoderSuite) TestHashNotFound(c *C) {
 	c.Assert(err, Equals, plumbing.ErrObjectNotFound)
 }
 
-func (s *EncoderSuite) TestDecodeEncodeDecode(c *C) {
-	fixtures.Basic().ByTag("packfile").Test(c, func(f *fixtures.Fixture) {
-		pf := f.Packfile()
-		ph := f.PackfileHash
-		storage := memory.NewStorage()
-		s.testDecodeEncodeDecode(c, pf, ph, storage)
-	})
-}
-
-func (s *EncoderSuite) testDecodeEncodeDecode(c *C,
-	pf io.ReadCloser,
-	ph plumbing.Hash,
-	storage storer.Storer) {
-
-	defer func() {
-		c.Assert(pf.Close(), IsNil)
-	}()
-
-	scanner := NewScanner(pf)
-
-	d, err := NewDecoder(scanner, storage)
-	c.Assert(err, IsNil)
-
-	ch, err := d.Decode()
-	c.Assert(err, IsNil)
-	c.Assert(ch, Equals, ph)
-
-	objIter, err := storage.IterEncodedObjects(plumbing.AnyObject)
-	c.Assert(err, IsNil)
-
-	expectedObjects := map[plumbing.Hash]bool{}
-	var hashes []plumbing.Hash
-	err = objIter.ForEach(func(o plumbing.EncodedObject) error {
-		expectedObjects[o.Hash()] = true
-		hashes = append(hashes, o.Hash())
-		return err
-
-	})
-	c.Assert(err, IsNil)
-
-	enc := NewEncoder(s.buf, storage, false)
-	_, err = enc.Encode(hashes)
-	c.Assert(err, IsNil)
-
-	scanner = NewScanner(s.buf)
-	storage = memory.NewStorage()
-	d, err = NewDecoder(scanner, storage)
-	c.Assert(err, IsNil)
-	_, err = d.Decode()
-	c.Assert(err, IsNil)
-
-	objIter, err = storage.IterEncodedObjects(plumbing.AnyObject)
-	c.Assert(err, IsNil)
-	obtainedObjects := map[plumbing.Hash]bool{}
-	err = objIter.ForEach(func(o plumbing.EncodedObject) error {
-		obtainedObjects[o.Hash()] = true
-		return nil
-	})
-	c.Assert(err, IsNil)
-	c.Assert(obtainedObjects, DeepEquals, expectedObjects)
-
-	for h := range obtainedObjects {
-		if !expectedObjects[h] {
-			c.Errorf("obtained unexpected object: %s", h)
-		}
-	}
-
-	for h := range expectedObjects {
-		if !obtainedObjects[h] {
-			c.Errorf("missing object: %s", h)
-		}
-	}
-}
-
 func (s *EncoderSuite) TestDecodeEncodeWithDeltaDecodeREF(c *C) {
 	s.enc = NewEncoder(s.buf, s.store, true)
 	s.simpleDeltaTest(c)
diff --git a/plumbing/format/packfile/object_pack.go b/plumbing/format/packfile/object_pack.go
index a3e99c0..14337d1 100644
--- a/plumbing/format/packfile/object_pack.go
+++ b/plumbing/format/packfile/object_pack.go
@@ -1,6 +1,8 @@
 package packfile
 
-import "gopkg.in/src-d/go-git.v4/plumbing"
+import (
+	"gopkg.in/src-d/go-git.v4/plumbing"
+)
 
 // ObjectToPack is a representation of an object that is going to be into a
 // pack file.
@@ -39,6 +41,48 @@ func newDeltaObjectToPack(base *ObjectToPack, original, delta plumbing.EncodedOb
 	}
 }
 
+func (o *ObjectToPack) Type() plumbing.ObjectType {
+	if o.Original != nil {
+		return o.Original.Type()
+	}
+
+	if o.Base != nil {
+		return o.Base.Type()
+	}
+
+	if o.Object != nil {
+		return o.Object.Type()
+	}
+
+	panic("cannot get type")
+}
+
+func (o *ObjectToPack) Hash() plumbing.Hash {
+	if o.Original != nil {
+		return o.Original.Hash()
+	}
+
+	do, ok := o.Object.(plumbing.DeltaObject)
+	if ok {
+		return do.ActualHash()
+	}
+
+	panic("cannot get hash")
+}
+
+func (o *ObjectToPack) Size() int64 {
+	if o.Original != nil {
+		return o.Original.Size()
+	}
+
+	do, ok := o.Object.(plumbing.DeltaObject)
+	if ok {
+		return do.ActualSize()
+	}
+
+	panic("cannot get ObjectToPack size")
+}
+
 func (o *ObjectToPack) IsDelta() bool {
 	if o.Base != nil {
 		return true
diff --git a/plumbing/object.go b/plumbing/object.go
index 3304da2..63396f0 100644
--- a/plumbing/object.go
+++ b/plumbing/object.go
@@ -23,6 +23,17 @@ type EncodedObject interface {
 	Writer() (io.WriteCloser, error)
 }
 
+// DeltaObject is an EncodedObject representing a delta.
+type DeltaObject interface {
+	EncodedObject
+	// BaseHash returns the hash of the object used as base for this delta.
+	BaseHash() Hash
+	// ActualHash returns the hash of the object after applying the delta.
+	ActualHash() Hash
+	// Size returns the size of the object after applying the delta.
+	ActualSize() int64
+}
+
 // ObjectType internal object type
 // Integer values from 0 to 7 map to those exposed by git.
 // AnyObject is used to represent any from 0 to 7.
diff --git a/plumbing/storer/object.go b/plumbing/storer/object.go
index a733ee6..3f41468 100644
--- a/plumbing/storer/object.go
+++ b/plumbing/storer/object.go
@@ -38,6 +38,14 @@ type EncodedObjectStorer interface {
 	IterEncodedObjects(plumbing.ObjectType) (EncodedObjectIter, error)
 }
 
+// DeltaObjectStorer is an EncodedObjectStorer that can return delta
+// objects.
+type DeltaObjectStorer interface {
+	// DeltaObject is the same as EncodedObject but without resolving deltas.
+	// Deltas will be returned as plumbing.DeltaObject instances.
+	DeltaObject(plumbing.ObjectType, plumbing.Hash) (plumbing.EncodedObject, error)
+}
+
 // Transactioner is a optional method for ObjectStorer, it enable transaction
 // base write and read operations in the storage
 type Transactioner interface {
diff --git a/storage/filesystem/deltaobject.go b/storage/filesystem/deltaobject.go
new file mode 100644
index 0000000..66cfb71
--- /dev/null
+++ b/storage/filesystem/deltaobject.go
@@ -0,0 +1,37 @@
+package filesystem
+
+import (
+	"gopkg.in/src-d/go-git.v4/plumbing"
+)
+
+type deltaObject struct {
+	plumbing.EncodedObject
+	base plumbing.Hash
+	hash plumbing.Hash
+	size int64
+}
+
+func newDeltaObject(
+	obj plumbing.EncodedObject,
+	hash plumbing.Hash,
+	base plumbing.Hash,
+	size int64) plumbing.DeltaObject {
+	return &deltaObject{
+		EncodedObject: obj,
+		hash:          hash,
+		base:          base,
+		size:          size,
+	}
+}
+
+func (o *deltaObject) BaseHash() plumbing.Hash {
+	return o.base
+}
+
+func (o *deltaObject) ActualSize() int64 {
+	return o.size
+}
+
+func (o *deltaObject) ActualHash() plumbing.Hash {
+	return o.hash
+}
diff --git a/storage/filesystem/object.go b/storage/filesystem/object.go
index 6dd910b..bc2b121 100644
--- a/storage/filesystem/object.go
+++ b/storage/filesystem/object.go
@@ -130,7 +130,27 @@ func (s *ObjectStorage) SetEncodedObject(o plumbing.EncodedObject) (plumbing.Has
 func (s *ObjectStorage) EncodedObject(t plumbing.ObjectType, h plumbing.Hash) (plumbing.EncodedObject, error) {
 	obj, err := s.getFromUnpacked(h)
 	if err == plumbing.ErrObjectNotFound {
-		obj, err = s.getFromPackfile(h)
+		obj, err = s.getFromPackfile(h, false)
+	}
+
+	if err != nil {
+		return nil, err
+	}
+
+	if plumbing.AnyObject != t && obj.Type() != t {
+		return nil, plumbing.ErrObjectNotFound
+	}
+
+	return obj, nil
+}
+
+// DeltaObject returns the object with the given hash, by searching for
+// it in the packfile and the git object directories.
+func (s *ObjectStorage) DeltaObject(t plumbing.ObjectType,
+	h plumbing.Hash) (plumbing.EncodedObject, error) {
+	obj, err := s.getFromUnpacked(h)
+	if err == plumbing.ErrObjectNotFound {
+		obj, err = s.getFromPackfile(h, true)
 	}
 
 	if err != nil {
@@ -182,12 +202,14 @@ func (s *ObjectStorage) getFromUnpacked(h plumbing.Hash) (obj plumbing.EncodedOb
 
 // Get returns the object with the given hash, by searching for it in
 // the packfile.
-func (s *ObjectStorage) getFromPackfile(h plumbing.Hash) (plumbing.EncodedObject, error) {
+func (s *ObjectStorage) getFromPackfile(h plumbing.Hash, canBeDelta bool) (
+	plumbing.EncodedObject, error) {
+
 	if err := s.requireIndex(); err != nil {
 		return nil, err
 	}
 
-	pack, offset := s.findObjectInPackfile(h)
+	pack, hash, offset := s.findObjectInPackfile(h)
 	if offset == -1 {
 		return nil, plumbing.ErrObjectNotFound
 	}
@@ -199,26 +221,94 @@ func (s *ObjectStorage) getFromPackfile(h plumbing.Hash) (plumbing.EncodedObject
 
 	defer ioutil.CheckClose(f, &err)
 
+	idx := s.index[pack]
+	if canBeDelta {
+		return s.decodeDeltaObjectAt(f, idx, offset, hash)
+	}
+
+	return s.decodeObjectAt(f, idx, offset)
+}
+
+func (s *ObjectStorage) decodeObjectAt(
+	f billy.File,
+	idx *packfile.Index,
+	offset int64) (plumbing.EncodedObject, error) {
+	if _, err := f.Seek(0, io.SeekStart); err != nil {
+		return nil, err
+	}
+
 	p := packfile.NewScanner(f)
+
 	d, err := packfile.NewDecoder(p, memory.NewStorage())
 	if err != nil {
 		return nil, err
 	}
 
+	d.SetIndex(idx)
 	d.DeltaBaseCache = s.DeltaBaseCache
-	d.SetIndex(s.index[pack])
 	obj, err := d.DecodeObjectAt(offset)
 	return obj, err
 }
 
-func (s *ObjectStorage) findObjectInPackfile(h plumbing.Hash) (plumbing.Hash, int64) {
+func (s *ObjectStorage) decodeDeltaObjectAt(
+	f billy.File,
+	idx *packfile.Index,
+	offset int64,
+	hash plumbing.Hash) (plumbing.EncodedObject, error) {
+	if _, err := f.Seek(0, io.SeekStart); err != nil {
+		return nil, err
+	}
+
+	p := packfile.NewScanner(f)
+	if _, err := p.SeekFromStart(offset); err != nil {
+		return nil, err
+	}
+
+	header, err := p.NextObjectHeader()
+	if err != nil {
+		return nil, err
+	}
+
+	var (
+		base plumbing.Hash
+	)
+
+	switch header.Type {
+	case plumbing.REFDeltaObject:
+		base = header.Reference
+	case plumbing.OFSDeltaObject:
+		e, ok := idx.LookupOffset(uint64(header.OffsetReference))
+		if !ok {
+			return nil, plumbing.ErrObjectNotFound
+		}
+
+		base = e.Hash
+	default:
+		return s.decodeObjectAt(f, idx, offset)
+	}
+
+	obj := &plumbing.MemoryObject{}
+	obj.SetType(header.Type)
+	w, err := obj.Writer()
+	if err != nil {
+		return nil, err
+	}
+
+	if _, _, err := p.NextObject(w); err != nil {
+		return nil, err
+	}
+
+	return newDeltaObject(obj, hash, base, header.Length), nil
+}
+
+func (s *ObjectStorage) findObjectInPackfile(h plumbing.Hash) (plumbing.Hash, plumbing.Hash, int64) {
 	for packfile, index := range s.index {
 		if e, ok := index.LookupHash(h); ok {
-			return packfile, int64(e.Offset)
+			return packfile, e.Hash, int64(e.Offset)
 		}
 	}
 
-	return plumbing.ZeroHash, -1
+	return plumbing.ZeroHash, plumbing.ZeroHash, -1
 }
 
 // IterEncodedObjects returns an iterator for all the objects in the packfile
diff --git a/storage/filesystem/object_test.go b/storage/filesystem/object_test.go
index d741fa2..504bd45 100644
--- a/storage/filesystem/object_test.go
+++ b/storage/filesystem/object_test.go
@@ -52,12 +52,12 @@ func (s *FsSuite) TestGetFromPackfileMultiplePackfiles(c *C) {
 	c.Assert(err, IsNil)
 
 	expected := plumbing.NewHash("8d45a34641d73851e01d3754320b33bb5be3c4d3")
-	obj, err := o.getFromPackfile(expected)
+	obj, err := o.getFromPackfile(expected, false)
 	c.Assert(err, IsNil)
 	c.Assert(obj.Hash(), Equals, expected)
 
 	expected = plumbing.NewHash("e9cfa4c9ca160546efd7e8582ec77952a27b17db")
-	obj, err = o.getFromPackfile(expected)
+	obj, err = o.getFromPackfile(expected, false)
 	c.Assert(err, IsNil)
 	c.Assert(obj.Hash(), Equals, expected)
 }
diff --git a/storage/filesystem/storage_test.go b/storage/filesystem/storage_test.go
index 22709f5..b165c5e 100644
--- a/storage/filesystem/storage_test.go
+++ b/storage/filesystem/storage_test.go
@@ -4,6 +4,7 @@ import (
 	"io/ioutil"
 	"testing"
 
+	"gopkg.in/src-d/go-git.v4/plumbing/storer"
 	"gopkg.in/src-d/go-git.v4/storage/test"
 
 	. "gopkg.in/check.v1"
@@ -25,6 +26,14 @@ func (s *StorageSuite) SetUpTest(c *C) {
 	storage, err := NewStorage(osfs.New(s.dir))
 	c.Assert(err, IsNil)
 
+	// ensure that right interfaces are implemented
+	var _ storer.EncodedObjectStorer = storage
+	var _ storer.IndexStorer = storage
+	var _ storer.ReferenceStorer = storage
+	var _ storer.ShallowStorer = storage
+	var _ storer.DeltaObjectStorer = storage
+	var _ storer.PackfileWriter = storage
+
 	s.BaseStorageSuite = test.NewBaseStorageSuite(storage)
 	s.BaseStorageSuite.SetUpTest(c)
 }
diff --git a/storage/test/storage_suite.go b/storage/test/storage_suite.go
index 7cb0fe3..624dc57 100644
--- a/storage/test/storage_suite.go
+++ b/storage/test/storage_suite.go
@@ -403,6 +403,40 @@ func (s *BaseStorageSuite) TestModule(c *C) {
 	c.Assert(storer, NotNil)
 }
 
+func (s *BaseStorageSuite) TestDeltaObjectStorer(c *C) {
+	dos, ok := s.Storer.(storer.DeltaObjectStorer)
+	if !ok {
+		c.Skip("not an DeltaObjectStorer")
+	}
+
+	pwr, ok := s.Storer.(storer.PackfileWriter)
+	if !ok {
+		c.Skip("not a storer.PackWriter")
+	}
+
+	pw, err := pwr.PackfileWriter()
+	c.Assert(err, IsNil)
+
+	f := fixtures.Basic().One()
+	_, err = io.Copy(pw, f.Packfile())
+	c.Assert(err, IsNil)
+
+	err = pw.Close()
+	c.Assert(err, IsNil)
+
+	h := plumbing.NewHash("32858aad3c383ed1ff0a0f9bdf231d54a00c9e88")
+	obj, err := dos.DeltaObject(plumbing.AnyObject, h)
+	c.Assert(err, IsNil)
+	c.Assert(obj.Type(), Equals, plumbing.BlobObject)
+
+	h = plumbing.NewHash("aa9b383c260e1d05fbbf6b30a02914555e20c725")
+	obj, err = dos.DeltaObject(plumbing.AnyObject, h)
+	c.Assert(err, IsNil)
+	c.Assert(obj.Type(), Equals, plumbing.OFSDeltaObject)
+	_, ok = obj.(plumbing.DeltaObject)
+	c.Assert(ok, Equals, true)
+}
+
 func objectEquals(a plumbing.EncodedObject, b plumbing.EncodedObject) error {
 	ha := a.Hash()
 	hb := b.Hash()