simplified sparse checkout

This is the initial logic to support a simple sparse checkout where
directories to be included can be specified in CheckoutOptions.
This change doesn't fully support the sparse patterns, nor does this
change include the optimization to collapse flie entries in ithe index
that are excluded via the sparse checkout directory patterns included
under the parent directory.

14 files changed, 160 insertions, 10 deletions

diff --git a/options.go b/options.go
index e54889f..4b18ec1 100644
--- a/options.go
+++ b/options.go
@@ -291,6 +291,8 @@ type CheckoutOptions struct {
 	// target branch. Force and Keep are mutually exclusive, should not be both
 	// set to true.
 	Keep bool
+	// SparseCheckoutDirectories
+	SparseCheckoutDirectories []string
 }
 
 // Validate validates the fields and sets the default values.
diff --git a/plumbing/format/index/index.go b/plumbing/format/index/index.go
index 649416a..f4c7647 100644
--- a/plumbing/format/index/index.go
+++ b/plumbing/format/index/index.go
@@ -5,6 +5,7 @@ import (
 	"errors"
 	"fmt"
 	"path/filepath"
+	"strings"
 	"time"
 
 	"github.com/go-git/go-git/v5/plumbing"
@@ -211,3 +212,20 @@ type EndOfIndexEntry struct {
 	//	their contents).
 	Hash plumbing.Hash
 }
+
+// SkipUnless applies patterns in the form of A, A/B, A/B/C
+// to the index to prevent the files from being checked out
+func (i *Index) SkipUnless(patterns []string) {
+	for _, e := range i.Entries {
+		var include bool
+		for _, pattern := range patterns {
+			if strings.HasPrefix(e.Name, pattern) {
+				include = true
+				break
+			}
+		}
+		if !include {
+			e.SkipWorktree = true
+		}
+	}
+}
diff --git a/plumbing/object/treenoder.go b/plumbing/object/treenoder.go
index b4891b9..6e7b334 100644
--- a/plumbing/object/treenoder.go
+++ b/plumbing/object/treenoder.go
@@ -38,6 +38,10 @@ func NewTreeRootNode(t *Tree) noder.Noder {
 	}
 }
 
+func (t *treeNoder) Skip() bool {
+	return false
+}
+
 func (t *treeNoder) isRoot() bool {
 	return t.name == ""
 }
diff --git a/repository_test.go b/repository_test.go
index 2bc5c90..668828e 100644
--- a/repository_test.go
+++ b/repository_test.go
@@ -210,6 +210,37 @@ func (s *RepositorySuite) TestCloneWithTags(c *C) {
 	c.Assert(count, Equals, 3)
 }
 
+func (s *RepositorySuite) TestCloneSparse(c *C) {
+	fs := memfs.New()
+	r, err := Clone(memory.NewStorage(), fs, &CloneOptions{
+		URL: s.GetBasicLocalRepositoryURL(),
+	})
+	c.Assert(err, IsNil)
+
+	w, err := r.Worktree()
+	c.Assert(err, IsNil)
+
+	sparseCheckoutDirectories := []string{"go", "json", "php"}
+	c.Assert(w.Checkout(&CheckoutOptions{
+		Branch:                    "refs/heads/master",
+		SparseCheckoutDirectories: sparseCheckoutDirectories,
+	}), IsNil)
+
+	fis, err := fs.ReadDir(".")
+	c.Assert(err, IsNil)
+	for _, fi := range fis {
+		c.Assert(fi.IsDir(), Equals, true)
+		var oneOfSparseCheckoutDirs bool
+
+		for _, sparseCheckoutDirectory := range sparseCheckoutDirectories {
+			if strings.HasPrefix(fi.Name(), sparseCheckoutDirectory) {
+				oneOfSparseCheckoutDirs = true
+			}
+		}
+		c.Assert(oneOfSparseCheckoutDirs, Equals, true)
+	}
+}
+
 func (s *RepositorySuite) TestCreateRemoteAndRemote(c *C) {
 	r, _ := Init(memory.NewStorage(), nil)
 	remote, err := r.CreateRemote(&config.RemoteConfig{
diff --git a/utils/merkletrie/difftree.go b/utils/merkletrie/difftree.go
index bd084b2..9f5145a 100644
--- a/utils/merkletrie/difftree.go
+++ b/utils/merkletrie/difftree.go
@@ -304,13 +304,38 @@ func DiffTreeContext(ctx context.Context, fromTree, toTree noder.Noder,
 				return nil, err
 			}
 		case onlyToRemains:
-			if err = ret.AddRecursiveInsert(to); err != nil {
-				return nil, err
+			if to.Skip() {
+				if err = ret.AddRecursiveDelete(to); err != nil {
+					return nil, err
+				}
+			} else {
+				if err = ret.AddRecursiveInsert(to); err != nil {
+					return nil, err
+				}
 			}
 			if err = ii.nextTo(); err != nil {
 				return nil, err
 			}
 		case bothHaveNodes:
+			if from.Skip() {
+				if err = ret.AddRecursiveDelete(from); err != nil {
+					return nil, err
+				}
+				if err := ii.nextBoth(); err != nil {
+					return nil, err
+				}
+				break
+			}
+			if to.Skip() {
+				if err = ret.AddRecursiveDelete(to); err != nil {
+					return nil, err
+				}
+				if err := ii.nextBoth(); err != nil {
+					return nil, err
+				}
+				break
+			}
+
 			if err = diffNodes(&ret, ii); err != nil {
 				return nil, err
 			}
diff --git a/utils/merkletrie/filesystem/node.go b/utils/merkletrie/filesystem/node.go
index 2fc3d7a..ad169ff 100644
--- a/utils/merkletrie/filesystem/node.go
+++ b/utils/merkletrie/filesystem/node.go
@@ -61,6 +61,10 @@ func (n *node) IsDir() bool {
 	return n.isDir
 }
 
+func (n *node) Skip() bool {
+	return false
+}
+
 func (n *node) Children() ([]noder.Noder, error) {
 	if err := n.calculateChildren(); err != nil {
 		return nil, err
diff --git a/utils/merkletrie/index/node.go b/utils/merkletrie/index/node.go
index d05b0c6..c1809f7 100644
--- a/utils/merkletrie/index/node.go
+++ b/utils/merkletrie/index/node.go
@@ -19,6 +19,7 @@ type node struct {
 	entry    *index.Entry
 	children []noder.Noder
 	isDir    bool
+	skip     bool
 }
 
 // NewRootNode returns the root node of a computed tree from a index.Index,
@@ -39,7 +40,7 @@ func NewRootNode(idx *index.Index) noder.Noder {
 				continue
 			}
 
-			n := &node{path: fullpath}
+			n := &node{path: fullpath, skip: e.SkipWorktree}
 			if fullpath == e.Name {
 				n.entry = e
 			} else {
@@ -58,6 +59,10 @@ func (n *node) String() string {
 	return n.path
 }
 
+func (n *node) Skip() bool {
+	return n.skip
+}
+
 // Hash the hash of a filesystem is a 24-byte slice, is the result of
 // concatenating the computed plumbing.Hash of the file as a Blob and its
 // plumbing.FileMode; that way the difftree algorithm will detect changes in the
diff --git a/utils/merkletrie/internal/fsnoder/dir.go b/utils/merkletrie/internal/fsnoder/dir.go
index 20a2aee..3a4c242 100644
--- a/utils/merkletrie/internal/fsnoder/dir.go
+++ b/utils/merkletrie/internal/fsnoder/dir.go
@@ -112,6 +112,10 @@ func (d *dir) NumChildren() (int, error) {
 	return len(d.children), nil
 }
 
+func (d *dir) Skip() bool {
+	return false
+}
+
 const (
 	dirStartMark  = '('
 	dirEndMark    = ')'
diff --git a/utils/merkletrie/internal/fsnoder/file.go b/utils/merkletrie/internal/fsnoder/file.go
index d53643f..0bb908b 100644
--- a/utils/merkletrie/internal/fsnoder/file.go
+++ b/utils/merkletrie/internal/fsnoder/file.go
@@ -55,6 +55,10 @@ func (f *file) NumChildren() (int, error) {
 	return 0, nil
 }
 
+func (f *file) Skip() bool {
+	return false
+}
+
 const (
 	fileStartMark = '<'
 	fileEndMark   = '>'
diff --git a/utils/merkletrie/noder/noder.go b/utils/merkletrie/noder/noder.go
index d6b3de4..6d22b8c 100644
--- a/utils/merkletrie/noder/noder.go
+++ b/utils/merkletrie/noder/noder.go
@@ -53,6 +53,7 @@ type Noder interface {
 	// implement NumChildren in O(1) while Children is usually more
 	// complex.
 	NumChildren() (int, error)
+	Skip()	bool
 }
 
 // NoChildren represents the children of a noder without children.
diff --git a/utils/merkletrie/noder/noder_test.go b/utils/merkletrie/noder/noder_test.go
index 5e014fe..ccebdc9 100644
--- a/utils/merkletrie/noder/noder_test.go
+++ b/utils/merkletrie/noder/noder_test.go
@@ -25,6 +25,7 @@ func (n noderMock) Name() string               { return n.name }
 func (n noderMock) IsDir() bool                { return n.isDir }
 func (n noderMock) Children() ([]Noder, error) { return n.children, nil }
 func (n noderMock) NumChildren() (int, error)  { return len(n.children), nil }
+func (n noderMock) Skip() bool                 { return false }
 
 // Returns a sequence with the noders 3, 2, and 1 from the
 // following diagram:
diff --git a/utils/merkletrie/noder/path.go b/utils/merkletrie/noder/path.go
index 1c7ef54..6c1d363 100644
--- a/utils/merkletrie/noder/path.go
+++ b/utils/merkletrie/noder/path.go
@@ -15,6 +15,14 @@ import (
 // not be used.
 type Path []Noder
 
+func (p Path) Skip() bool {
+	if len(p) > 0 {
+		return p.Last().Skip()
+	}
+
+	return false
+}
+
 // String returns the full path of the final noder as a string, using
 // "/" as the separator.
 func (p Path) String() string {
diff --git a/worktree.go b/worktree.go
index 362d10e..c974aed 100644
--- a/worktree.go
+++ b/worktree.go
@@ -11,6 +11,8 @@ import (
 	"strings"
 	"sync"
 
+	"github.com/go-git/go-billy/v5"
+	"github.com/go-git/go-billy/v5/util"
 	"github.com/go-git/go-git/v5/config"
 	"github.com/go-git/go-git/v5/plumbing"
 	"github.com/go-git/go-git/v5/plumbing/filemode"
@@ -20,9 +22,6 @@ import (
 	"github.com/go-git/go-git/v5/plumbing/storer"
 	"github.com/go-git/go-git/v5/utils/ioutil"
 	"github.com/go-git/go-git/v5/utils/merkletrie"
-
-	"github.com/go-git/go-billy/v5"
-	"github.com/go-git/go-billy/v5/util"
 )
 
 var (
@@ -183,6 +182,10 @@ func (w *Worktree) Checkout(opts *CheckoutOptions) error {
 		return err
 	}
 
+	if len(opts.SparseCheckoutDirectories) > 0 {
+		return w.ResetSparsely(ro, opts.SparseCheckoutDirectories)
+	}
+
 	return w.Reset(ro)
 }
 func (w *Worktree) createBranch(opts *CheckoutOptions) error {
@@ -263,8 +266,7 @@ func (w *Worktree) setHEADToBranch(branch plumbing.ReferenceName, commit plumbin
 	return w.r.Storer.SetReference(head)
 }
 
-// Reset the worktree to a specified state.
-func (w *Worktree) Reset(opts *ResetOptions) error {
+func (w *Worktree) ResetSparsely(opts *ResetOptions, dirs []string) error {
 	if err := opts.Validate(w.r); err != nil {
 		return err
 	}
@@ -294,7 +296,7 @@ func (w *Worktree) Reset(opts *ResetOptions) error {
 	}
 
 	if opts.Mode == MixedReset || opts.Mode == MergeReset || opts.Mode == HardReset {
-		if err := w.resetIndex(t); err != nil {
+		if err := w.resetIndex(t, dirs); err != nil {
 			return err
 		}
 	}
@@ -308,8 +310,17 @@ func (w *Worktree) Reset(opts *ResetOptions) error {
 	return nil
 }
 
-func (w *Worktree) resetIndex(t *object.Tree) error {
+// Reset the worktree to a specified state.
+func (w *Worktree) Reset(opts *ResetOptions) error {
+	return w.ResetSparsely(opts, nil)
+}
+
+func (w *Worktree) resetIndex(t *object.Tree, dirs []string) error {
 	idx, err := w.r.Storer.Index()
+	if len(dirs) > 0 {
+		idx.SkipUnless(dirs)
+	}
+
 	if err != nil {
 		return err
 	}
diff --git a/worktree_test.go b/worktree_test.go
index 79cbefd..a8f3187 100644
--- a/worktree_test.go
+++ b/worktree_test.go
@@ -10,6 +10,7 @@ import (
 	"path/filepath"
 	"regexp"
 	"runtime"
+	"strings"
 	"testing"
 	"time"
 
@@ -417,6 +418,37 @@ func (s *WorktreeSuite) TestCheckoutSymlink(c *C) {
 	c.Assert(err, IsNil)
 }
 
+func (s *WorktreeSuite) TestCheckoutSparse(c *C) {
+	fs := memfs.New()
+	r, err := Clone(memory.NewStorage(), fs, &CloneOptions{
+		URL: s.GetBasicLocalRepositoryURL(),
+	})
+	c.Assert(err, IsNil)
+
+	w, err := r.Worktree()
+	c.Assert(err, IsNil)
+
+	sparseCheckoutDirectories := []string{"go", "json", "php"}
+	c.Assert(w.Checkout(&CheckoutOptions{
+		SparseCheckoutDirectories: sparseCheckoutDirectories,
+	}), IsNil)
+
+	fis, err := fs.ReadDir("/")
+	c.Assert(err, IsNil)
+
+	for _, fi := range fis {
+		c.Assert(fi.IsDir(), Equals, true)
+		var oneOfSparseCheckoutDirs bool
+
+		for _, sparseCheckoutDirectory := range sparseCheckoutDirectories {
+			if strings.HasPrefix(fi.Name(), sparseCheckoutDirectory) {
+				oneOfSparseCheckoutDirs = true
+			}
+		}
+		c.Assert(oneOfSparseCheckoutDirs, Equals, true)
+	}
+}
+
 func (s *WorktreeSuite) TestFilenameNormalization(c *C) {
 	if runtime.GOOS == "windows" {
 		c.Skip("windows paths may contain non utf-8 sequences")