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