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