1// Package revlist provides support to access the ancestors of commits, in a
  2// similar way as the git-rev-list command.
  3package revlist
  4
  5import (
  6	"fmt"
  7	"io"
  8
  9	"github.com/go-git/go-git/v5/plumbing"
 10	"github.com/go-git/go-git/v5/plumbing/filemode"
 11	"github.com/go-git/go-git/v5/plumbing/object"
 12	"github.com/go-git/go-git/v5/plumbing/storer"
 13)
 14
 15// Objects applies a complementary set. It gets all the hashes from all
 16// the reachable objects from the given objects. Ignore param are object hashes
 17// that we want to ignore on the result. All that objects must be accessible
 18// from the object storer.
 19func Objects(
 20	s storer.EncodedObjectStorer,
 21	objs,
 22	ignore []plumbing.Hash,
 23) ([]plumbing.Hash, error) {
 24	return ObjectsWithStorageForIgnores(s, s, objs, ignore)
 25}
 26
 27// ObjectsWithStorageForIgnores is the same as Objects, but a
 28// secondary storage layer can be provided, to be used to finding the
 29// full set of objects to be ignored while finding the reachable
 30// objects.  This is useful when the main `s` storage layer is slow
 31// and/or remote, while the ignore list is available somewhere local.
 32func ObjectsWithStorageForIgnores(
 33	s, ignoreStore storer.EncodedObjectStorer,
 34	objs,
 35	ignore []plumbing.Hash,
 36) ([]plumbing.Hash, error) {
 37	ignore, err := objects(ignoreStore, ignore, nil, true)
 38	if err != nil {
 39		return nil, err
 40	}
 41
 42	return objects(s, objs, ignore, false)
 43}
 44
 45func objects(
 46	s storer.EncodedObjectStorer,
 47	objects,
 48	ignore []plumbing.Hash,
 49	allowMissingObjects bool,
 50) ([]plumbing.Hash, error) {
 51	seen := hashListToSet(ignore)
 52	result := make(map[plumbing.Hash]bool)
 53	visited := make(map[plumbing.Hash]bool)
 54
 55	walkerFunc := func(h plumbing.Hash) {
 56		if !seen[h] {
 57			result[h] = true
 58			seen[h] = true
 59		}
 60	}
 61
 62	for _, h := range objects {
 63		if err := processObject(s, h, seen, visited, ignore, walkerFunc); err != nil {
 64			if allowMissingObjects && err == plumbing.ErrObjectNotFound {
 65				continue
 66			}
 67
 68			return nil, err
 69		}
 70	}
 71
 72	return hashSetToList(result), nil
 73}
 74
 75// processObject obtains the object using the hash an process it depending of its type
 76func processObject(
 77	s storer.EncodedObjectStorer,
 78	h plumbing.Hash,
 79	seen map[plumbing.Hash]bool,
 80	visited map[plumbing.Hash]bool,
 81	ignore []plumbing.Hash,
 82	walkerFunc func(h plumbing.Hash),
 83) error {
 84	if seen[h] {
 85		return nil
 86	}
 87
 88	o, err := s.EncodedObject(plumbing.AnyObject, h)
 89	if err != nil {
 90		return err
 91	}
 92
 93	do, err := object.DecodeObject(s, o)
 94	if err != nil {
 95		return err
 96	}
 97
 98	switch do := do.(type) {
 99	case *object.Commit:
100		return reachableObjects(do, seen, visited, ignore, walkerFunc)
101	case *object.Tree:
102		return iterateCommitTrees(seen, do, walkerFunc)
103	case *object.Tag:
104		walkerFunc(do.Hash)
105		return processObject(s, do.Target, seen, visited, ignore, walkerFunc)
106	case *object.Blob:
107		walkerFunc(do.Hash)
108	default:
109		return fmt.Errorf("object type not valid: %s. "+
110			"Object reference: %s", o.Type(), o.Hash())
111	}
112
113	return nil
114}
115
116// reachableObjects returns, using the callback function, all the reachable
117// objects from the specified commit. To avoid to iterate over seen commits,
118// if a commit hash is into the 'seen' set, we will not iterate all his trees
119// and blobs objects.
120func reachableObjects(
121	commit *object.Commit,
122	seen map[plumbing.Hash]bool,
123	visited map[plumbing.Hash]bool,
124	ignore []plumbing.Hash,
125	cb func(h plumbing.Hash),
126) error {
127	i := object.NewCommitPreorderIter(commit, seen, ignore)
128	pending := make(map[plumbing.Hash]bool)
129	addPendingParents(pending, visited, commit)
130	for {
131		commit, err := i.Next()
132		if err == io.EOF {
133			break
134		}
135
136		if err != nil {
137			return err
138		}
139
140		if pending[commit.Hash] {
141			delete(pending, commit.Hash)
142		}
143
144		addPendingParents(pending, visited, commit)
145
146		if visited[commit.Hash] && len(pending) == 0 {
147			break
148		}
149
150		if seen[commit.Hash] {
151			continue
152		}
153
154		cb(commit.Hash)
155
156		tree, err := commit.Tree()
157		if err != nil {
158			return err
159		}
160
161		if err := iterateCommitTrees(seen, tree, cb); err != nil {
162			return err
163		}
164	}
165
166	return nil
167}
168
169func addPendingParents(pending, visited map[plumbing.Hash]bool, commit *object.Commit) {
170	for _, p := range commit.ParentHashes {
171		if !visited[p] {
172			pending[p] = true
173		}
174	}
175}
176
177// iterateCommitTrees iterate all reachable trees from the given commit
178func iterateCommitTrees(
179	seen map[plumbing.Hash]bool,
180	tree *object.Tree,
181	cb func(h plumbing.Hash),
182) error {
183	if seen[tree.Hash] {
184		return nil
185	}
186
187	cb(tree.Hash)
188
189	treeWalker := object.NewTreeWalker(tree, true, seen)
190
191	for {
192		_, e, err := treeWalker.Next()
193		if err == io.EOF {
194			break
195		}
196		if err != nil {
197			return err
198		}
199
200		if e.Mode == filemode.Submodule {
201			continue
202		}
203
204		if seen[e.Hash] {
205			continue
206		}
207
208		cb(e.Hash)
209	}
210
211	return nil
212}
213
214func hashSetToList(hashes map[plumbing.Hash]bool) []plumbing.Hash {
215	var result []plumbing.Hash
216	for key := range hashes {
217		result = append(result, key)
218	}
219
220	return result
221}
222
223func hashListToSet(hashes []plumbing.Hash) map[plumbing.Hash]bool {
224	result := make(map[plumbing.Hash]bool)
225	for _, h := range hashes {
226		result[h] = true
227	}
228
229	return result
230}