2
This code is derived from jgit (http://eclipse.org/jgit).
3
Copyright owners are documented in jgit's IP log.
5
This program and the accompanying materials are made available
6
under the terms of the Eclipse Distribution License v1.0 which
7
accompanies this distribution, is reproduced below, and is
8
available at http://www.eclipse.org/org/documents/edl-v10.php
12
Redistribution and use in source and binary forms, with or
13
without modification, are permitted provided that the following
16
- Redistributions of source code must retain the above copyright
17
notice, this list of conditions and the following disclaimer.
19
- Redistributions in binary form must reproduce the above
20
copyright notice, this list of conditions and the following
21
disclaimer in the documentation and/or other materials provided
22
with the distribution.
24
- Neither the name of the Eclipse Foundation, Inc. nor the
25
names of its contributors may be used to endorse or promote
26
products derived from this software without specific prior
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44
using System.Collections.Generic;
51
namespace NGit.Revwalk
53
/// <summary>Specialized subclass of RevWalk to include trees, blobs and tags.</summary>
55
/// Specialized subclass of RevWalk to include trees, blobs and tags.
57
/// Unlike RevWalk this subclass is able to remember starting roots that include
58
/// annotated tags, or arbitrary trees or blobs. Once commit generation is
59
/// complete and all commits have been popped by the application, individual
60
/// annotated tag, tree and blob objects can be popped through the additional
62
/// <see cref="NextObject()">NextObject()</see>
65
/// Tree and blob objects reachable from interesting commits are automatically
66
/// scheduled for inclusion in the results of
67
/// <see cref="NextObject()">NextObject()</see>
69
/// each object exactly once. Objects are sorted and returned according to the
70
/// the commits that reference them and the order they appear within a tree.
71
/// Ordering can be affected by changing the
72
/// <see cref="RevSort">RevSort</see>
74
/// commits that are returned first.
76
public class ObjectWalk : RevWalk
79
/// Indicates a non-RevCommit is in
80
/// <see cref="pendingObjects">pendingObjects</see>
83
/// We can safely reuse
84
/// <see cref="RevWalk.REWRITE">RevWalk.REWRITE</see>
85
/// here for the same value as it
86
/// is only set on RevCommit and
87
/// <see cref="pendingObjects">pendingObjects</see>
88
/// never has RevCommit
89
/// instances inserted into it.
91
private const int IN_PENDING = RevWalk.REWRITE;
93
private static readonly byte[] EMPTY_PATH = new byte[] { };
95
private CanonicalTreeParser treeWalk;
97
private IList<RevObject> rootObjects;
99
private BlockObjQueue pendingObjects;
101
private RevTree currentTree;
103
private RevObject last;
105
private RevCommit firstCommit;
107
private RevCommit lastCommit;
109
/// <summary>Create a new revision and object walker for a given repository.</summary>
110
/// <remarks>Create a new revision and object walker for a given repository.</remarks>
111
/// <param name="repo">the repository the walker will obtain data from.</param>
112
public ObjectWalk(Repository repo) : this(repo.NewObjectReader())
116
/// <summary>Create a new revision and object walker for a given repository.</summary>
117
/// <remarks>Create a new revision and object walker for a given repository.</remarks>
118
/// <param name="or">
119
/// the reader the walker will obtain data from. The reader should
120
/// be released by the caller when the walker is no longer
123
public ObjectWalk(ObjectReader or) : base(or)
125
rootObjects = new AList<RevObject>();
126
pendingObjects = new BlockObjQueue();
127
treeWalk = new CanonicalTreeParser();
130
/// <summary>Mark an object or commit to start graph traversal from.</summary>
132
/// Mark an object or commit to start graph traversal from.
134
/// Callers are encouraged to use
135
/// <see cref="RevWalk.ParseAny(NGit.AnyObjectId)">RevWalk.ParseAny(NGit.AnyObjectId)
138
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
141
/// requires the object to be parsed before it can be added as a root for the
144
/// The method will automatically parse an unparsed object, but error
145
/// handling may be more difficult for the application to explain why a
146
/// RevObject is not actually valid. The object pool of this walker would
147
/// also be 'poisoned' by the invalid RevObject.
149
/// This method will automatically call
150
/// <see cref="RevWalk.MarkStart(RevCommit)">RevWalk.MarkStart(RevCommit)</see>
151
/// if passed RevCommit instance, or a RevTag that directly (or indirectly)
152
/// references a RevCommit.
155
/// the object to start traversing from. The object passed must be
156
/// from this same revision walker.
158
/// <exception cref="NGit.Errors.MissingObjectException">
159
/// the object supplied is not available from the object
160
/// database. This usually indicates the supplied object is
161
/// invalid, but the reference was constructed during an earlier
163
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
167
/// <exception cref="NGit.Errors.IncorrectObjectTypeException">
168
/// the object was not parsed yet and it was discovered during
169
/// parsing that it is not actually the type of the instance
170
/// passed in. This usually indicates the caller used the wrong
172
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
176
/// <exception cref="System.IO.IOException">a pack file or loose object could not be read.
178
public virtual void MarkStart(RevObject o)
183
o = ((RevTag)o).GetObject();
188
base.MarkStart((RevCommit)o);
196
/// <summary>Mark an object to not produce in the output.</summary>
198
/// Mark an object to not produce in the output.
200
/// Uninteresting objects denote not just themselves but also their entire
201
/// reachable chain, back until the merge base of an uninteresting commit and
202
/// an otherwise interesting commit.
204
/// Callers are encouraged to use
205
/// <see cref="RevWalk.ParseAny(NGit.AnyObjectId)">RevWalk.ParseAny(NGit.AnyObjectId)
208
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
211
/// requires the object to be parsed before it can be added as a root for the
214
/// The method will automatically parse an unparsed object, but error
215
/// handling may be more difficult for the application to explain why a
216
/// RevObject is not actually valid. The object pool of this walker would
217
/// also be 'poisoned' by the invalid RevObject.
219
/// This method will automatically call
220
/// <see cref="RevWalk.MarkStart(RevCommit)">RevWalk.MarkStart(RevCommit)</see>
221
/// if passed RevCommit instance, or a RevTag that directly (or indirectly)
222
/// references a RevCommit.
224
/// <param name="o">the object to start traversing from. The object passed must be</param>
225
/// <exception cref="NGit.Errors.MissingObjectException">
226
/// the object supplied is not available from the object
227
/// database. This usually indicates the supplied object is
228
/// invalid, but the reference was constructed during an earlier
230
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
234
/// <exception cref="NGit.Errors.IncorrectObjectTypeException">
235
/// the object was not parsed yet and it was discovered during
236
/// parsing that it is not actually the type of the instance
237
/// passed in. This usually indicates the caller used the wrong
239
/// <see cref="RevWalk.LookupAny(NGit.AnyObjectId, int)">RevWalk.LookupAny(NGit.AnyObjectId, int)
243
/// <exception cref="System.IO.IOException">a pack file or loose object could not be read.
245
public virtual void MarkUninteresting(RevObject o)
249
o.flags |= UNINTERESTING;
250
if (HasRevSort(RevSort.BOUNDARY))
254
o = ((RevTag)o).GetObject();
259
base.MarkUninteresting((RevCommit)o);
265
MarkTreeUninteresting((RevTree)o);
269
o.flags |= UNINTERESTING;
272
if (o.Type != Constants.OBJ_COMMIT && HasRevSort(RevSort.BOUNDARY))
278
/// <exception cref="NGit.Errors.MissingObjectException"></exception>
279
/// <exception cref="NGit.Errors.IncorrectObjectTypeException"></exception>
280
/// <exception cref="System.IO.IOException"></exception>
281
public override RevCommit Next()
285
RevCommit r = base.Next();
290
if ((r.flags & UNINTERESTING) != 0)
292
MarkTreeUninteresting(r.Tree);
293
if (HasRevSort(RevSort.BOUNDARY))
299
if (firstCommit == null)
304
pendingObjects.Add(r.Tree);
309
/// <summary>Pop the next most recent object.</summary>
310
/// <remarks>Pop the next most recent object.</remarks>
311
/// <returns>next most recent object; null if traversal is over.</returns>
312
/// <exception cref="NGit.Errors.MissingObjectException">
313
/// one or or more of the next objects are not available from the
314
/// object database, but were thought to be candidates for
315
/// traversal. This usually indicates a broken link.
317
/// <exception cref="NGit.Errors.IncorrectObjectTypeException">
318
/// one or or more of the objects in a tree do not match the type
321
/// <exception cref="System.IO.IOException">a pack file or loose object could not be read.
323
public virtual RevObject NextObject()
327
treeWalk = last is RevTree ? Enter(last) : treeWalk.Next();
329
while (!treeWalk.Eof)
331
FileMode mode = treeWalk.EntryFileMode;
332
switch (mode.GetObjectType())
334
case Constants.OBJ_BLOB:
336
treeWalk.GetEntryObjectId(idBuffer);
337
RevBlob o = LookupBlob(idBuffer);
338
if ((o.flags & SEEN) != 0)
343
if (ShouldSkipObject(o))
351
case Constants.OBJ_TREE:
353
treeWalk.GetEntryObjectId(idBuffer);
354
RevTree o = LookupTree(idBuffer);
355
if ((o.flags & SEEN) != 0)
360
if (ShouldSkipObject(o))
370
if (FileMode.GITLINK.Equals(mode))
374
treeWalk.GetEntryObjectId(idBuffer);
375
throw new CorruptObjectException(MessageFormat.Format(JGitText.Get().corruptObjectInvalidMode3
376
, mode, idBuffer.Name, treeWalk.EntryPathString, currentTree.Name));
379
treeWalk = treeWalk.Next();
381
if (firstCommit != null)
383
reader.WalkAdviceBeginTrees(this, firstCommit, lastCommit);
390
RevObject o = pendingObjects.Next();
393
reader.WalkAdviceEnd();
396
if ((o.flags & SEEN) != 0)
401
if (ShouldSkipObject(o))
407
currentTree = (RevTree)o;
408
treeWalk = treeWalk.ResetRoot(reader, currentTree);
414
/// <exception cref="System.IO.IOException"></exception>
415
private CanonicalTreeParser Enter(RevObject tree)
417
CanonicalTreeParser p = treeWalk.CreateSubtreeIterator0(reader, tree);
420
// We can't tolerate the subtree being an empty tree, as
421
// that will break us out early before we visit all names.
422
// If it is, advance to the parent's next record.
424
return treeWalk.Next();
429
private bool ShouldSkipObject(RevObject o)
431
return (o.flags & UNINTERESTING) != 0 && !HasRevSort(RevSort.BOUNDARY);
434
/// <summary>Verify all interesting objects are available, and reachable.</summary>
436
/// Verify all interesting objects are available, and reachable.
438
/// Callers should populate starting points and ending points with
439
/// <see cref="MarkStart(RevObject)">MarkStart(RevObject)</see>
441
/// <see cref="MarkUninteresting(RevObject)">MarkUninteresting(RevObject)</see>
442
/// and then use this method to verify all objects between those two points
443
/// exist in the repository and are readable.
445
/// This method returns successfully if everything is connected; it throws an
446
/// exception if there is a connectivity problem. The exception message
447
/// provides some detail about the connectivity failure.
449
/// <exception cref="NGit.Errors.MissingObjectException">
450
/// one or or more of the next objects are not available from the
451
/// object database, but were thought to be candidates for
452
/// traversal. This usually indicates a broken link.
454
/// <exception cref="NGit.Errors.IncorrectObjectTypeException">
455
/// one or or more of the objects in a tree do not match the type
458
/// <exception cref="System.IO.IOException">a pack file or loose object could not be read.
460
public virtual void CheckConnectivity()
464
RevCommit c = Next();
472
RevObject o = NextObject();
477
if (o is RevBlob && !reader.Has(o))
479
throw new MissingObjectException(o, Constants.TYPE_BLOB);
484
/// <summary>Get the current object's complete path.</summary>
486
/// Get the current object's complete path.
488
/// This method is not very efficient and is primarily meant for debugging
489
/// and final output generation. Applications should try to avoid calling it,
490
/// and if invoked do so only once per interesting entry, where the name is
491
/// absolutely required for correct function.
494
/// complete path of the current entry, from the root of the
495
/// repository. If the current entry is in a subtree there will be at
496
/// least one '/' in the returned string. Null if the current entry
497
/// has no path, such as for annotated tags or root level trees.
499
public virtual string GetPathString()
501
return last != null ? treeWalk.EntryPathString : null;
504
/// <summary>Get the current object's path hash code.</summary>
506
/// Get the current object's path hash code.
508
/// This method computes a hash code on the fly for this path, the hash is
509
/// suitable to cluster objects that may have similar paths together.
511
/// <returns>path hash code; any integer may be returned.</returns>
512
public virtual int GetPathHashCode()
514
return last != null ? treeWalk.GetEntryPathHashCode() : 0;
517
/// <returns>the internal buffer holding the current path.</returns>
518
public virtual byte[] GetPathBuffer()
520
return last != null ? treeWalk.GetEntryPathBuffer() : EMPTY_PATH;
524
/// length of the path in
525
/// <see cref="GetPathBuffer()">GetPathBuffer()</see>
528
public virtual int GetPathLength()
530
return last != null ? treeWalk.GetEntryPathLength() : 0;
533
public override void Dispose()
536
pendingObjects = new BlockObjQueue();
537
treeWalk = new CanonicalTreeParser();
544
protected internal override void Reset(int retainFlags)
546
base.Reset(retainFlags);
547
foreach (RevObject obj in rootObjects)
549
obj.flags &= ~IN_PENDING;
551
rootObjects = new AList<RevObject>();
552
pendingObjects = new BlockObjQueue();
553
treeWalk = new CanonicalTreeParser();
560
private void AddObject(RevObject o)
562
if ((o.flags & IN_PENDING) == 0)
564
o.flags |= IN_PENDING;
565
rootObjects.AddItem(o);
566
pendingObjects.Add(o);
570
/// <exception cref="NGit.Errors.MissingObjectException"></exception>
571
/// <exception cref="NGit.Errors.IncorrectObjectTypeException"></exception>
572
/// <exception cref="System.IO.IOException"></exception>
573
private void MarkTreeUninteresting(RevTree tree)
575
if ((tree.flags & UNINTERESTING) != 0)
579
tree.flags |= UNINTERESTING;
580
treeWalk = treeWalk.ResetRoot(reader, tree);
581
while (!treeWalk.Eof)
583
FileMode mode = treeWalk.EntryFileMode;
584
int sType = mode.GetObjectType();
587
case Constants.OBJ_BLOB:
589
treeWalk.GetEntryObjectId(idBuffer);
590
LookupBlob(idBuffer).flags |= UNINTERESTING;
594
case Constants.OBJ_TREE:
596
treeWalk.GetEntryObjectId(idBuffer);
597
RevTree t = LookupTree(idBuffer);
598
if ((t.flags & UNINTERESTING) == 0)
600
t.flags |= UNINTERESTING;
601
treeWalk = treeWalk.CreateSubtreeIterator0(reader, t);
609
if (FileMode.GITLINK.Equals(mode))
613
treeWalk.GetEntryObjectId(idBuffer);
614
throw new CorruptObjectException(MessageFormat.Format(JGitText.Get().corruptObjectInvalidMode3
615
, mode, idBuffer.Name, treeWalk.EntryPathString, tree));
618
treeWalk = treeWalk.Next();
added
removed
contrib/NGit/NGit.Revwalk/ObjectWalk.cs
