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.

8 files changed, 55 insertions, 3 deletions

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 {