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 public ObjectReachabilityChecker createObjectReachabilityChecker()
177 throws IOException {
178 if (reader.getBitmapIndex() != null) {
179 return new BitmappedObjectReachabilityChecker(this);
180 }
181
182 return new PedestrianObjectReachabilityChecker(this);
183 }
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223 public void markStart(RevObject o) throws MissingObjectException,
224 IncorrectObjectTypeException, IOException {
225 while (o instanceof RevTag) {
226 addObject(o);
227 o = ((RevTag) o).getObject();
228 parseHeaders(o);
229 }
230
231 if (o instanceof RevCommit)
232 super.markStart((RevCommit) o);
233 else
234 addObject(o);
235 }
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278 public void markUninteresting(RevObject o) throws MissingObjectException,
279 IncorrectObjectTypeException, IOException {
280 while (o instanceof RevTag) {
281 o.flags |= UNINTERESTING;
282 if (boundary)
283 addObject(o);
284 o = ((RevTag) o).getObject();
285 parseHeaders(o);
286 }
287
288 if (o instanceof RevCommit)
289 super.markUninteresting((RevCommit) o);
290 else if (o instanceof RevTree)
291 markTreeUninteresting((RevTree) o);
292 else
293 o.flags |= UNINTERESTING;
294
295 if (o.getType() != OBJ_COMMIT && boundary)
296 addObject(o);
297 }
298
299
300 @Override
301 public void sort(RevSort s) {
302 super.sort(s);
303 boundary = hasRevSort(RevSort.BOUNDARY);
304 }
305
306
307 @Override
308 public void sort(RevSort s, boolean use) {
309 super.sort(s, use);
310 boundary = hasRevSort(RevSort.BOUNDARY);
311 }
312
313
314
315
316
317
318
319 public ObjectFilter getObjectFilter() {
320 return objectFilter;
321 }
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339 public void setObjectFilter(ObjectFilter newFilter) {
340 assertNotStarted();
341 objectFilter = newFilter != null ? newFilter : ObjectFilter.ALL;
342 }
343
344
345
346
347
348
349
350
351 public void setVisitationPolicy(VisitationPolicy policy) {
352 assertNotStarted();
353 visitationPolicy = requireNonNull(policy);
354 }
355
356
357 @Override
358 public RevCommit next() throws MissingObjectException,
359 IncorrectObjectTypeException, IOException {
360 for (;;) {
361 final RevCommit r = super.next();
362 if (r == null) {
363 return null;
364 }
365 final RevTree t = r.getTree();
366 if ((r.flags & UNINTERESTING) != 0) {
367 if (objectFilter.include(this, t)) {
368 markTreeUninteresting(t);
369 }
370 if (boundary) {
371 return r;
372 }
373 continue;
374 }
375 if (objectFilter.include(this, t)) {
376 pendingObjects.add(t);
377 }
378 return r;
379 }
380 }
381
382
383
384
385
386
387
388
389 public void skipTree() {
390 if (currVisit != null) {
391 currVisit.ptr = currVisit.buf.length;
392 }
393 }
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409 public RevObject nextObject() throws MissingObjectException,
410 IncorrectObjectTypeException, IOException {
411 pathLen = 0;
412
413 TreeVisit tv = currVisit;
414 while (tv != null) {
415 byte[] buf = tv.buf;
416 for (int ptr = tv.ptr; ptr < buf.length;) {
417 int startPtr = ptr;
418 ptr = findObjectId(buf, ptr);
419 idBuffer.fromRaw(buf, ptr);
420 ptr += ID_SZ;
421
422 if (!objectFilter.include(this, idBuffer)) {
423 continue;
424 }
425
426 RevObject obj = objects.get(idBuffer);
427 if (obj != null && !visitationPolicy.shouldVisit(obj))
428 continue;
429
430 int mode = parseMode(buf, startPtr, ptr, tv);
431 switch (mode >>> TYPE_SHIFT) {
432 case TYPE_FILE:
433 case TYPE_SYMLINK:
434 if (obj == null) {
435 obj = new RevBlob(idBuffer);
436 visitationPolicy.visited(obj);
437 objects.add(obj);
438 return obj;
439 }
440 if (!(obj instanceof RevBlob))
441 throw new IncorrectObjectTypeException(obj, OBJ_BLOB);
442 visitationPolicy.visited(obj);
443 if ((obj.flags & UNINTERESTING) == 0)
444 return obj;
445 if (boundary)
446 return obj;
447 continue;
448
449 case TYPE_TREE:
450 if (obj == null) {
451 obj = new RevTree(idBuffer);
452 visitationPolicy.visited(obj);
453 objects.add(obj);
454 return pushTree(obj);
455 }
456 if (!(obj instanceof RevTree))
457 throw new IncorrectObjectTypeException(obj, OBJ_TREE);
458 visitationPolicy.visited(obj);
459 if ((obj.flags & UNINTERESTING) == 0)
460 return pushTree(obj);
461 if (boundary)
462 return pushTree(obj);
463 continue;
464
465 case TYPE_GITLINK:
466 continue;
467
468 default:
469 throw new CorruptObjectException(MessageFormat.format(
470 JGitText.get().corruptObjectInvalidMode3,
471 String.format("%o", Integer.valueOf(mode)),
472 idBuffer.name(),
473 RawParseUtils.decode(buf, tv.namePtr, tv.nameEnd),
474 tv.obj));
475 }
476 }
477
478 currVisit = tv.parent;
479 releaseTreeVisit(tv);
480 tv = currVisit;
481 }
482
483 for (;;) {
484 RevObject o = pendingObjects.next();
485 if (o == null) {
486 return null;
487 }
488 if (!visitationPolicy.shouldVisit(o)) {
489 continue;
490 }
491 visitationPolicy.visited(o);
492 if ((o.flags & UNINTERESTING) == 0 || boundary) {
493 if (o instanceof RevTree) {
494
495
496 assert currVisit == null;
497
498 pushTree(o);
499 }
500 return o;
501 }
502 }
503 }
504
505 private static int findObjectId(byte[] buf, int ptr) {
506
507
508 for (;;) {
509 if (buf[++ptr] == 0) return ++ptr;
510 if (buf[++ptr] == 0) return ++ptr;
511 if (buf[++ptr] == 0) return ++ptr;
512 if (buf[++ptr] == 0) return ++ptr;
513
514 if (buf[++ptr] == 0) return ++ptr;
515 if (buf[++ptr] == 0) return ++ptr;
516 if (buf[++ptr] == 0) return ++ptr;
517 if (buf[++ptr] == 0) return ++ptr;
518
519 if (buf[++ptr] == 0) return ++ptr;
520 if (buf[++ptr] == 0) return ++ptr;
521 if (buf[++ptr] == 0) return ++ptr;
522 if (buf[++ptr] == 0) return ++ptr;
523
524 if (buf[++ptr] == 0) return ++ptr;
525 if (buf[++ptr] == 0) return ++ptr;
526 if (buf[++ptr] == 0) return ++ptr;
527 if (buf[++ptr] == 0) return ++ptr;
528 }
529 }
530
531 private static int parseMode(byte[] buf, int startPtr, int recEndPtr, TreeVisit tv) {
532 int mode = buf[startPtr] - '0';
533 for (;;) {
534 byte c = buf[++startPtr];
535 if (' ' == c)
536 break;
537 mode <<= 3;
538 mode += c - '0';
539
540 c = buf[++startPtr];
541 if (' ' == c)
542 break;
543 mode <<= 3;
544 mode += c - '0';
545
546 c = buf[++startPtr];
547 if (' ' == c)
548 break;
549 mode <<= 3;
550 mode += c - '0';
551
552 c = buf[++startPtr];
553 if (' ' == c)
554 break;
555 mode <<= 3;
556 mode += c - '0';
557
558 c = buf[++startPtr];
559 if (' ' == c)
560 break;
561 mode <<= 3;
562 mode += c - '0';
563
564 c = buf[++startPtr];
565 if (' ' == c)
566 break;
567 mode <<= 3;
568 mode += c - '0';
569
570 c = buf[++startPtr];
571 if (' ' == c)
572 break;
573 mode <<= 3;
574 mode += c - '0';
575 }
576
577 tv.ptr = recEndPtr;
578 tv.namePtr = startPtr + 1;
579 tv.nameEnd = recEndPtr - (ID_SZ + 1);
580 return mode;
581 }
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605 public void checkConnectivity() throws MissingObjectException,
606 IncorrectObjectTypeException, IOException {
607 for (;;) {
608 final RevCommit c = next();
609 if (c == null)
610 break;
611 }
612 for (;;) {
613 final RevObject o = nextObject();
614 if (o == null)
615 break;
616 if (o instanceof RevBlob && !reader.has(o))
617 throw new MissingObjectException(o, OBJ_BLOB);
618 }
619 }
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634 public String getPathString() {
635 if (pathLen == 0) {
636 pathLen = updatePathBuf(currVisit);
637 if (pathLen == 0)
638 return null;
639 }
640 return RawParseUtils.decode(pathBuf, 0, pathLen);
641 }
642
643
644
645
646
647 public int getTreeDepth() {
648 if (currVisit == null) {
649 return 0;
650 }
651 return currVisit.depth;
652 }
653
654
655
656
657
658
659
660
661
662 public int getPathHashCode() {
663 TreeVisit tv = currVisit;
664 if (tv == null)
665 return 0;
666
667 int nameEnd = tv.nameEnd;
668 if (nameEnd == 0) {
669
670
671
672
673 tv = tv.parent;
674 if (tv == null)
675 return 0;
676 nameEnd = tv.nameEnd;
677 }
678
679 byte[] buf;
680 int ptr;
681
682 if (16 <= (nameEnd - tv.namePtr)) {
683 buf = tv.buf;
684 ptr = nameEnd - 16;
685 } else {
686 nameEnd = pathLen;
687 if (nameEnd == 0) {
688 nameEnd = updatePathBuf(currVisit);
689 pathLen = nameEnd;
690 }
691 buf = pathBuf;
692 ptr = Math.max(0, nameEnd - 16);
693 }
694
695 int hash = 0;
696 for (; ptr < nameEnd; ptr++) {
697 byte c = buf[ptr];
698 if (c != ' ')
699 hash = (hash >>> 2) + (c << 24);
700 }
701 return hash;
702 }
703
704
705
706
707
708
709 public byte[] getPathBuffer() {
710 if (pathLen == 0)
711 pathLen = updatePathBuf(currVisit);
712 return pathBuf;
713 }
714
715
716
717
718
719
720 public int getPathLength() {
721 if (pathLen == 0)
722 pathLen = updatePathBuf(currVisit);
723 return pathLen;
724 }
725
726 private int updatePathBuf(TreeVisit tv) {
727 if (tv == null)
728 return 0;
729
730
731
732 int nameEnd = tv.nameEnd;
733 if (nameEnd == 0)
734 return updatePathBuf(tv.parent);
735
736 int ptr = tv.pathLen;
737 if (ptr == 0) {
738 ptr = updatePathBuf(tv.parent);
739 if (ptr == pathBuf.length)
740 growPathBuf(ptr);
741 if (ptr != 0)
742 pathBuf[ptr++] = '/';
743 tv.pathLen = ptr;
744 }
745
746 int namePtr = tv.namePtr;
747 int nameLen = nameEnd - namePtr;
748 int end = ptr + nameLen;
749 while (pathBuf.length < end)
750 growPathBuf(ptr);
751 System.arraycopy(tv.buf, namePtr, pathBuf, ptr, nameLen);
752 return end;
753 }
754
755 private void growPathBuf(int ptr) {
756 byte[] newBuf = new byte[pathBuf.length << 1];
757 System.arraycopy(pathBuf, 0, newBuf, 0, ptr);
758 pathBuf = newBuf;
759 }
760
761
762 @Override
763 public void dispose() {
764 super.dispose();
765 pendingObjects = new BlockObjQueue();
766 currVisit = null;
767 freeVisit = null;
768 }
769
770
771 @Override
772 protected void reset(int retainFlags) {
773 super.reset(retainFlags);
774
775 for (RevObject obj : rootObjects)
776 obj.flags &= ~IN_PENDING;
777
778 rootObjects = new ArrayList<>();
779 pendingObjects = new BlockObjQueue();
780 currVisit = null;
781 freeVisit = null;
782 }
783
784 private void addObject(RevObject o) {
785 if ((o.flags & IN_PENDING) == 0) {
786 o.flags |= IN_PENDING;
787 rootObjects.add(o);
788 pendingObjects.add(o);
789 }
790 }
791
792 private void markTreeUninteresting(RevTree tree)
793 throws MissingObjectException, IncorrectObjectTypeException,
794 IOException {
795 if ((tree.flags & UNINTERESTING) != 0)
796 return;
797 tree.flags |= UNINTERESTING;
798
799 byte[] raw = reader.open(tree, OBJ_TREE).getCachedBytes();
800 for (int ptr = 0; ptr < raw.length;) {
801 byte c = raw[ptr];
802 int mode = c - '0';
803 for (;;) {
804 c = raw[++ptr];
805 if (' ' == c)
806 break;
807 mode <<= 3;
808 mode += c - '0';
809 }
810 while (raw[++ptr] != 0) {
811
812 }
813 ptr++;
814
815 switch (mode >>> TYPE_SHIFT) {
816 case TYPE_FILE:
817 case TYPE_SYMLINK:
818 idBuffer.fromRaw(raw, ptr);
819 lookupBlob(idBuffer).flags |= UNINTERESTING;
820 break;
821
822 case TYPE_TREE:
823 idBuffer.fromRaw(raw, ptr);
824 markTreeUninteresting(lookupTree(idBuffer));
825 break;
826
827 case TYPE_GITLINK:
828 break;
829
830 default:
831 idBuffer.fromRaw(raw, ptr);
832 throw new CorruptObjectException(MessageFormat.format(
833 JGitText.get().corruptObjectInvalidMode3,
834 String.format("%o", Integer.valueOf(mode)),
835 idBuffer.name(), "", tree));
836 }
837 ptr += ID_SZ;
838 }
839 }
840
841 private RevObject/../../../org/eclipse/jgit/revwalk/RevObject.html#RevObject">RevObject pushTree(RevObject obj) throws LargeObjectException,
842 MissingObjectException, IncorrectObjectTypeException, IOException {
843 TreeVisit tv = freeVisit;
844 if (tv != null) {
845 freeVisit = tv.parent;
846 tv.ptr = 0;
847 tv.namePtr = 0;
848 tv.nameEnd = 0;
849 tv.pathLen = 0;
850 } else {
851 tv = new TreeVisit();
852 }
853 tv.obj = obj;
854 tv.buf = reader.open(obj, OBJ_TREE).getCachedBytes();
855 tv.parent = currVisit;
856 currVisit = tv;
857 if (tv.parent == null) {
858 tv.depth = 1;
859 } else {
860 tv.depth = tv.parent.depth + 1;
861 }
862
863 return obj;
864 }
865
866 private void releaseTreeVisit(TreeVisit tv) {
867 tv.buf = null;
868 tv.parent = freeVisit;
869 freeVisit = tv;
870 }
871
872 private static class TreeVisit {
873
874 TreeVisit parent;
875
876
877 RevObject obj;
878
879
880 byte[] buf;
881
882
883 int ptr;
884
885
886 int namePtr;
887
888
889 int nameEnd;
890
891
892 int pathLen;
893
894
895 int depth;
896 }
897 }