1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.revwalk;
12
13 import static java.util.Objects.requireNonNull;
14 import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
15 import static org.eclipse.jgit.lib.Constants.OBJ_COMMIT;
16 import static org.eclipse.jgit.lib.Constants.OBJ_TREE;
17
18 import java.io.IOException;
19 import java.text.MessageFormat;
20 import java.util.ArrayList;
21 import java.util.List;
22
23 import org.eclipse.jgit.errors.CorruptObjectException;
24 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
25 import org.eclipse.jgit.errors.LargeObjectException;
26 import org.eclipse.jgit.errors.MissingObjectException;
27 import org.eclipse.jgit.internal.JGitText;
28 import org.eclipse.jgit.lib.AnyObjectId;
29 import org.eclipse.jgit.lib.ObjectReader;
30 import org.eclipse.jgit.lib.Repository;
31 import org.eclipse.jgit.revwalk.filter.ObjectFilter;
32 import org.eclipse.jgit.util.RawParseUtils;
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 public class ObjectWalk extends RevWalk {
52 private static final int ID_SZ = 20;
53 private static final int TYPE_SHIFT = 12;
54 private static final int TYPE_TREE = 0040000 >>> TYPE_SHIFT;
55 private static final int TYPE_SYMLINK = 0120000 >>> TYPE_SHIFT;
56 private static final int TYPE_FILE = 0100000 >>> TYPE_SHIFT;
57 private static final int TYPE_GITLINK = 0160000 >>> TYPE_SHIFT;
58
59
60
61
62
63
64
65
66 private static final int IN_PENDING = RevWalk.REWRITE;
67
68
69
70
71
72
73
74
75
76
77 public interface VisitationPolicy {
78
79
80
81
82
83
84
85
86
87 boolean shouldVisit(RevObject o);
88
89
90
91
92
93
94
95 void visited(RevObject o);
96 }
97
98
99
100
101
102
103
104 public static final VisitationPolicy SIMPLE_VISITATION_POLICY =
105 new VisitationPolicy() {
106 @Override
107 public boolean shouldVisit(RevObject o) {
108 return (o.flags & SEEN) == 0;
109 }
110
111 @Override
112 public void visited(RevObject o) {
113 o.flags |= SEEN;
114 }
115 };
116
117 private List<RevObject> rootObjects;
118
119 private BlockObjQueue pendingObjects;
120
121 private ObjectFilter objectFilter;
122
123 private TreeVisit freeVisit;
124
125 private TreeVisit currVisit;
126
127 private byte[] pathBuf;
128
129 private int pathLen;
130
131 private boolean boundary;
132
133 private VisitationPolicy visitationPolicy = SIMPLE_VISITATION_POLICY;
134
135
136
137
138
139
140
141 public ObjectWalk(Repository repo) {
142 this(repo.newObjectReader());
143 }
144
145
146
147
148
149
150
151
152
153 public ObjectWalk(ObjectReader or) {
154 super(or);
155 setRetainBody(false);
156 rootObjects = new ArrayList<>();
157 pendingObjects = new BlockObjQueue();
158 objectFilter = ObjectFilter.ALL;
159 pathBuf = new byte[256];
160 }
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200 public void markStart(RevObject o) throws MissingObjectException,
201 IncorrectObjectTypeException, IOException {
202 while (o instanceof RevTag) {
203 addObject(o);
204 o = ((RevTag) o).getObject();
205 parseHeaders(o);
206 }
207
208 if (o instanceof RevCommit)
209 super.markStart((RevCommit) o);
210 else
211 addObject(o);
212 }
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255 public void markUninteresting(RevObject o) throws MissingObjectException,
256 IncorrectObjectTypeException, IOException {
257 while (o instanceof RevTag) {
258 o.flags |= UNINTERESTING;
259 if (boundary)
260 addObject(o);
261 o = ((RevTag) o).getObject();
262 parseHeaders(o);
263 }
264
265 if (o instanceof RevCommit)
266 super.markUninteresting((RevCommit) o);
267 else if (o instanceof RevTree)
268 markTreeUninteresting((RevTree) o);
269 else
270 o.flags |= UNINTERESTING;
271
272 if (o.getType() != OBJ_COMMIT && boundary)
273 addObject(o);
274 }
275
276
277 @Override
278 public void sort(RevSort s) {
279 super.sort(s);
280 boundary = hasRevSort(RevSort.BOUNDARY);
281 }
282
283
284 @Override
285 public void sort(RevSort s, boolean use) {
286 super.sort(s, use);
287 boundary = hasRevSort(RevSort.BOUNDARY);
288 }
289
290
291
292
293
294
295
296 public ObjectFilter getObjectFilter() {
297 return objectFilter;
298 }
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316 public void setObjectFilter(ObjectFilter newFilter) {
317 assertNotStarted();
318 objectFilter = newFilter != null ? newFilter : ObjectFilter.ALL;
319 }
320
321
322
323
324
325
326
327
328 public void setVisitationPolicy(VisitationPolicy policy) {
329 assertNotStarted();
330 visitationPolicy = requireNonNull(policy);
331 }
332
333
334 @Override
335 public RevCommit next() throws MissingObjectException,
336 IncorrectObjectTypeException, IOException {
337 for (;;) {
338 final RevCommit r = super.next();
339 if (r == null) {
340 return null;
341 }
342 final RevTree t = r.getTree();
343 if ((r.flags & UNINTERESTING) != 0) {
344 if (objectFilter.include(this, t)) {
345 markTreeUninteresting(t);
346 }
347 if (boundary) {
348 return r;
349 }
350 continue;
351 }
352 if (objectFilter.include(this, t)) {
353 pendingObjects.add(t);
354 }
355 return r;
356 }
357 }
358
359
360
361
362
363
364
365
366 public void skipTree() {
367 if (currVisit != null) {
368 currVisit.ptr = currVisit.buf.length;
369 }
370 }
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386 public RevObject nextObject() throws MissingObjectException,
387 IncorrectObjectTypeException, IOException {
388 pathLen = 0;
389
390 TreeVisit tv = currVisit;
391 while (tv != null) {
392 byte[] buf = tv.buf;
393 for (int ptr = tv.ptr; ptr < buf.length;) {
394 int startPtr = ptr;
395 ptr = findObjectId(buf, ptr);
396 idBuffer.fromRaw(buf, ptr);
397 ptr += ID_SZ;
398
399 if (!objectFilter.include(this, idBuffer)) {
400 continue;
401 }
402
403 RevObject obj = objects.get(idBuffer);
404 if (obj != null && !visitationPolicy.shouldVisit(obj))
405 continue;
406
407 int mode = parseMode(buf, startPtr, ptr, tv);
408 switch (mode >>> TYPE_SHIFT) {
409 case TYPE_FILE:
410 case TYPE_SYMLINK:
411 if (obj == null) {
412 obj = new RevBlob(idBuffer);
413 visitationPolicy.visited(obj);
414 objects.add(obj);
415 return obj;
416 }
417 if (!(obj instanceof RevBlob))
418 throw new IncorrectObjectTypeException(obj, OBJ_BLOB);
419 visitationPolicy.visited(obj);
420 if ((obj.flags & UNINTERESTING) == 0)
421 return obj;
422 if (boundary)
423 return obj;
424 continue;
425
426 case TYPE_TREE:
427 if (obj == null) {
428 obj = new RevTree(idBuffer);
429 visitationPolicy.visited(obj);
430 objects.add(obj);
431 return pushTree(obj);
432 }
433 if (!(obj instanceof RevTree))
434 throw new IncorrectObjectTypeException(obj, OBJ_TREE);
435 visitationPolicy.visited(obj);
436 if ((obj.flags & UNINTERESTING) == 0)
437 return pushTree(obj);
438 if (boundary)
439 return pushTree(obj);
440 continue;
441
442 case TYPE_GITLINK:
443 continue;
444
445 default:
446 throw new CorruptObjectException(MessageFormat.format(
447 JGitText.get().corruptObjectInvalidMode3,
448 String.format("%o", Integer.valueOf(mode)),
449 idBuffer.name(),
450 RawParseUtils.decode(buf, tv.namePtr, tv.nameEnd),
451 tv.obj));
452 }
453 }
454
455 currVisit = tv.parent;
456 releaseTreeVisit(tv);
457 tv = currVisit;
458 }
459
460 for (;;) {
461 RevObject o = pendingObjects.next();
462 if (o == null) {
463 return null;
464 }
465 if (!visitationPolicy.shouldVisit(o)) {
466 continue;
467 }
468 visitationPolicy.visited(o);
469 if ((o.flags & UNINTERESTING) == 0 || boundary) {
470 if (o instanceof RevTree) {
471
472
473 assert currVisit == null;
474
475 pushTree(o);
476 }
477 return o;
478 }
479 }
480 }
481
482 private static int findObjectId(byte[] buf, int ptr) {
483
484
485 for (;;) {
486 if (buf[++ptr] == 0) return ++ptr;
487 if (buf[++ptr] == 0) return ++ptr;
488 if (buf[++ptr] == 0) return ++ptr;
489 if (buf[++ptr] == 0) return ++ptr;
490
491 if (buf[++ptr] == 0) return ++ptr;
492 if (buf[++ptr] == 0) return ++ptr;
493 if (buf[++ptr] == 0) return ++ptr;
494 if (buf[++ptr] == 0) return ++ptr;
495
496 if (buf[++ptr] == 0) return ++ptr;
497 if (buf[++ptr] == 0) return ++ptr;
498 if (buf[++ptr] == 0) return ++ptr;
499 if (buf[++ptr] == 0) return ++ptr;
500
501 if (buf[++ptr] == 0) return ++ptr;
502 if (buf[++ptr] == 0) return ++ptr;
503 if (buf[++ptr] == 0) return ++ptr;
504 if (buf[++ptr] == 0) return ++ptr;
505 }
506 }
507
508 private static int parseMode(byte[] buf, int startPtr, int recEndPtr, TreeVisit tv) {
509 int mode = buf[startPtr] - '0';
510 for (;;) {
511 byte c = buf[++startPtr];
512 if (' ' == c)
513 break;
514 mode <<= 3;
515 mode += c - '0';
516
517 c = buf[++startPtr];
518 if (' ' == c)
519 break;
520 mode <<= 3;
521 mode += c - '0';
522
523 c = buf[++startPtr];
524 if (' ' == c)
525 break;
526 mode <<= 3;
527 mode += c - '0';
528
529 c = buf[++startPtr];
530 if (' ' == c)
531 break;
532 mode <<= 3;
533 mode += c - '0';
534
535 c = buf[++startPtr];
536 if (' ' == c)
537 break;
538 mode <<= 3;
539 mode += c - '0';
540
541 c = buf[++startPtr];
542 if (' ' == c)
543 break;
544 mode <<= 3;
545 mode += c - '0';
546
547 c = buf[++startPtr];
548 if (' ' == c)
549 break;
550 mode <<= 3;
551 mode += c - '0';
552 }
553
554 tv.ptr = recEndPtr;
555 tv.namePtr = startPtr + 1;
556 tv.nameEnd = recEndPtr - (ID_SZ + 1);
557 return mode;
558 }
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582 public void checkConnectivity() throws MissingObjectException,
583 IncorrectObjectTypeException, IOException {
584 for (;;) {
585 final RevCommit c = next();
586 if (c == null)
587 break;
588 }
589 for (;;) {
590 final RevObject o = nextObject();
591 if (o == null)
592 break;
593 if (o instanceof RevBlob && !reader.has(o))
594 throw new MissingObjectException(o, OBJ_BLOB);
595 }
596 }
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611 public String getPathString() {
612 if (pathLen == 0) {
613 pathLen = updatePathBuf(currVisit);
614 if (pathLen == 0)
615 return null;
616 }
617 return RawParseUtils.decode(pathBuf, 0, pathLen);
618 }
619
620
621
622
623
624 public int getTreeDepth() {
625 if (currVisit == null) {
626 return 0;
627 }
628 return currVisit.depth;
629 }
630
631
632
633
634
635
636
637
638
639 public int getPathHashCode() {
640 TreeVisit tv = currVisit;
641 if (tv == null)
642 return 0;
643
644 int nameEnd = tv.nameEnd;
645 if (nameEnd == 0) {
646
647
648
649
650 tv = tv.parent;
651 if (tv == null)
652 return 0;
653 nameEnd = tv.nameEnd;
654 }
655
656 byte[] buf;
657 int ptr;
658
659 if (16 <= (nameEnd - tv.namePtr)) {
660 buf = tv.buf;
661 ptr = nameEnd - 16;
662 } else {
663 nameEnd = pathLen;
664 if (nameEnd == 0) {
665 nameEnd = updatePathBuf(currVisit);
666 pathLen = nameEnd;
667 }
668 buf = pathBuf;
669 ptr = Math.max(0, nameEnd - 16);
670 }
671
672 int hash = 0;
673 for (; ptr < nameEnd; ptr++) {
674 byte c = buf[ptr];
675 if (c != ' ')
676 hash = (hash >>> 2) + (c << 24);
677 }
678 return hash;
679 }
680
681
682
683
684
685
686 public byte[] getPathBuffer() {
687 if (pathLen == 0)
688 pathLen = updatePathBuf(currVisit);
689 return pathBuf;
690 }
691
692
693
694
695
696
697 public int getPathLength() {
698 if (pathLen == 0)
699 pathLen = updatePathBuf(currVisit);
700 return pathLen;
701 }
702
703 private int updatePathBuf(TreeVisit tv) {
704 if (tv == null)
705 return 0;
706
707
708
709 int nameEnd = tv.nameEnd;
710 if (nameEnd == 0)
711 return updatePathBuf(tv.parent);
712
713 int ptr = tv.pathLen;
714 if (ptr == 0) {
715 ptr = updatePathBuf(tv.parent);
716 if (ptr == pathBuf.length)
717 growPathBuf(ptr);
718 if (ptr != 0)
719 pathBuf[ptr++] = '/';
720 tv.pathLen = ptr;
721 }
722
723 int namePtr = tv.namePtr;
724 int nameLen = nameEnd - namePtr;
725 int end = ptr + nameLen;
726 while (pathBuf.length < end)
727 growPathBuf(ptr);
728 System.arraycopy(tv.buf, namePtr, pathBuf, ptr, nameLen);
729 return end;
730 }
731
732 private void growPathBuf(int ptr) {
733 byte[] newBuf = new byte[pathBuf.length << 1];
734 System.arraycopy(pathBuf, 0, newBuf, 0, ptr);
735 pathBuf = newBuf;
736 }
737
738
739 @Override
740 public void dispose() {
741 super.dispose();
742 pendingObjects = new BlockObjQueue();
743 currVisit = null;
744 freeVisit = null;
745 }
746
747
748 @Override
749 protected void reset(int retainFlags) {
750 super.reset(retainFlags);
751
752 for (RevObject obj : rootObjects)
753 obj.flags &= ~IN_PENDING;
754
755 rootObjects = new ArrayList<>();
756 pendingObjects = new BlockObjQueue();
757 currVisit = null;
758 freeVisit = null;
759 }
760
761 private void addObject(RevObject o) {
762 if ((o.flags & IN_PENDING) == 0) {
763 o.flags |= IN_PENDING;
764 rootObjects.add(o);
765 pendingObjects.add(o);
766 }
767 }
768
769 private void markTreeUninteresting(RevTree tree)
770 throws MissingObjectException, IncorrectObjectTypeException,
771 IOException {
772 if ((tree.flags & UNINTERESTING) != 0)
773 return;
774 tree.flags |= UNINTERESTING;
775
776 byte[] raw = reader.open(tree, OBJ_TREE).getCachedBytes();
777 for (int ptr = 0; ptr < raw.length;) {
778 byte c = raw[ptr];
779 int mode = c - '0';
780 for (;;) {
781 c = raw[++ptr];
782 if (' ' == c)
783 break;
784 mode <<= 3;
785 mode += c - '0';
786 }
787 while (raw[++ptr] != 0) {
788
789 }
790 ptr++;
791
792 switch (mode >>> TYPE_SHIFT) {
793 case TYPE_FILE:
794 case TYPE_SYMLINK:
795 idBuffer.fromRaw(raw, ptr);
796 lookupBlob(idBuffer).flags |= UNINTERESTING;
797 break;
798
799 case TYPE_TREE:
800 idBuffer.fromRaw(raw, ptr);
801 markTreeUninteresting(lookupTree(idBuffer));
802 break;
803
804 case TYPE_GITLINK:
805 break;
806
807 default:
808 idBuffer.fromRaw(raw, ptr);
809 throw new CorruptObjectException(MessageFormat.format(
810 JGitText.get().corruptObjectInvalidMode3,
811 String.format("%o", Integer.valueOf(mode)),
812 idBuffer.name(), "", tree));
813 }
814 ptr += ID_SZ;
815 }
816 }
817
818 private RevObject/../../../org/eclipse/jgit/revwalk/RevObject.html#RevObject">RevObject pushTree(RevObject obj) throws LargeObjectException,
819 MissingObjectException, IncorrectObjectTypeException, IOException {
820 TreeVisit tv = freeVisit;
821 if (tv != null) {
822 freeVisit = tv.parent;
823 tv.ptr = 0;
824 tv.namePtr = 0;
825 tv.nameEnd = 0;
826 tv.pathLen = 0;
827 } else {
828 tv = new TreeVisit();
829 }
830 tv.obj = obj;
831 tv.buf = reader.open(obj, OBJ_TREE).getCachedBytes();
832 tv.parent = currVisit;
833 currVisit = tv;
834 if (tv.parent == null) {
835 tv.depth = 1;
836 } else {
837 tv.depth = tv.parent.depth + 1;
838 }
839
840 return obj;
841 }
842
843 private void releaseTreeVisit(TreeVisit tv) {
844 tv.buf = null;
845 tv.parent = freeVisit;
846 freeVisit = tv;
847 }
848
849 private static class TreeVisit {
850
851 TreeVisit parent;
852
853
854 RevObject obj;
855
856
857 byte[] buf;
858
859
860 int ptr;
861
862
863 int namePtr;
864
865
866 int nameEnd;
867
868
869 int pathLen;
870
871
872 int depth;
873 }
874 }