1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.reftable;
12
13 import static org.eclipse.jgit.lib.Constants.HEAD;
14 import static org.eclipse.jgit.lib.Constants.MASTER;
15 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
16 import static org.eclipse.jgit.lib.Constants.R_HEADS;
17 import static org.eclipse.jgit.lib.Ref.Storage.NEW;
18 import static org.eclipse.jgit.lib.Ref.Storage.PACKED;
19 import static org.junit.Assert.assertEquals;
20 import static org.junit.Assert.assertFalse;
21 import static org.junit.Assert.assertNull;
22 import static org.junit.Assert.assertTrue;
23
24 import java.io.ByteArrayOutputStream;
25 import java.io.IOException;
26 import java.util.ArrayList;
27 import java.util.Arrays;
28 import java.util.Collection;
29 import java.util.Collections;
30 import java.util.HashMap;
31 import java.util.List;
32 import java.util.Map;
33
34 import org.eclipse.jgit.internal.storage.io.BlockSource;
35 import org.eclipse.jgit.lib.ObjectId;
36 import org.eclipse.jgit.lib.ObjectIdRef;
37 import org.eclipse.jgit.lib.Ref;
38 import org.eclipse.jgit.lib.RefComparator;
39 import org.eclipse.jgit.lib.SymbolicRef;
40 import org.junit.Test;
41
42 public class MergedReftableTest {
43 @Test
44 public void noTables() throws IOException {
45 MergedReftable mr = merge(new byte[0][]);
46 try (RefCursor rc = mr.allRefs()) {
47 assertFalse(rc.next());
48 }
49 try (RefCursor rc = mr.seekRef(HEAD)) {
50 assertFalse(rc.next());
51 }
52 try (RefCursor rc = mr.seekRefsWithPrefix(R_HEADS)) {
53 assertFalse(rc.next());
54 }
55 }
56
57 @Test
58 public void oneEmptyTable() throws IOException {
59 MergedReftable mr = merge(write());
60 try (RefCursor rc = mr.allRefs()) {
61 assertFalse(rc.next());
62 }
63 try (RefCursor rc = mr.seekRef(HEAD)) {
64 assertFalse(rc.next());
65 }
66 try (RefCursor rc = mr.seekRefsWithPrefix(R_HEADS)) {
67 assertFalse(rc.next());
68 }
69 }
70
71 @Test
72 public void twoEmptyTables() throws IOException {
73 MergedReftable mr = merge(write(), write());
74 try (RefCursor rc = mr.allRefs()) {
75 assertFalse(rc.next());
76 }
77 try (RefCursor rc = mr.seekRef(HEAD)) {
78 assertFalse(rc.next());
79 }
80 try (RefCursor rc = mr.seekRefsWithPrefix(R_HEADS)) {
81 assertFalse(rc.next());
82 }
83 }
84
85 @SuppressWarnings("boxing")
86 @Test
87 public void oneTableScan() throws IOException {
88 List<Ref> refs = new ArrayList<>();
89 for (int i = 1; i <= 567; i++) {
90 refs.add(ref(String.format("refs/heads/%03d", i), i));
91 }
92
93 MergedReftable mr = merge(write(refs));
94 try (RefCursor rc = mr.allRefs()) {
95 for (Ref exp : refs) {
96 assertTrue("has " + exp.getName(), rc.next());
97 Ref act = rc.getRef();
98 assertEquals(exp.getName(), act.getName());
99 assertEquals(exp.getObjectId(), act.getObjectId());
100 assertEquals(1, act.getUpdateIndex());
101 }
102 assertFalse(rc.next());
103 }
104 }
105
106 @Test
107 public void deleteIsHidden() throws IOException {
108 List<Ref> delta1 = Arrays.asList(
109 ref("refs/heads/apple", 1),
110 ref("refs/heads/master", 2));
111 List<Ref> delta2 = Arrays.asList(delete("refs/heads/apple"));
112
113 MergedReftable mr = merge(write(delta1), write(delta2));
114 try (RefCursor rc = mr.allRefs()) {
115 assertTrue(rc.next());
116 assertEquals("refs/heads/master", rc.getRef().getName());
117 assertEquals(id(2), rc.getRef().getObjectId());
118 assertEquals(1, rc.getRef().getUpdateIndex());
119 assertFalse(rc.next());
120 }
121 }
122
123 @Test
124 public void twoTableSeek() throws IOException {
125 List<Ref> delta1 = Arrays.asList(
126 ref("refs/heads/apple", 1),
127 ref("refs/heads/master", 2));
128 List<Ref> delta2 = Arrays.asList(ref("refs/heads/banana", 3));
129
130 MergedReftable mr = merge(write(delta1), write(delta2));
131 try (RefCursor rc = mr.seekRef("refs/heads/master")) {
132 assertTrue(rc.next());
133 assertEquals("refs/heads/master", rc.getRef().getName());
134 assertEquals(id(2), rc.getRef().getObjectId());
135 assertFalse(rc.next());
136 assertEquals(1, rc.getRef().getUpdateIndex());
137 }
138 }
139
140 @Test
141 public void twoTableById() throws IOException {
142 List<Ref> delta1 = Arrays.asList(
143 ref("refs/heads/apple", 1),
144 ref("refs/heads/master", 2));
145 List<Ref> delta2 = Arrays.asList(ref("refs/heads/banana", 3));
146
147 MergedReftable mr = merge(write(delta1), write(delta2));
148 try (RefCursor rc = mr.byObjectId(id(2))) {
149 assertTrue(rc.next());
150 assertEquals("refs/heads/master", rc.getRef().getName());
151 assertEquals(id(2), rc.getRef().getObjectId());
152 assertEquals(1, rc.getRef().getUpdateIndex());
153 assertFalse(rc.next());
154 }
155 }
156
157 @Test
158 public void tableByIDDeletion() throws IOException {
159 List<Ref> delta1 = Arrays.asList(
160 ref("refs/heads/apple", 1),
161 ref("refs/heads/master", 2));
162 List<Ref> delta2 = Arrays.asList(ref("refs/heads/master", 3));
163
164 MergedReftable mr = merge(write(delta1), write(delta2));
165 try (RefCursor rc = mr.byObjectId(id(2))) {
166 assertFalse(rc.next());
167 }
168 }
169
170 @SuppressWarnings("boxing")
171 @Test
172 public void fourTableScan() throws IOException {
173 List<Ref> base = new ArrayList<>();
174 for (int i = 1; i <= 567; i++) {
175 base.add(ref(String.format("refs/heads/%03d", i), i));
176 }
177
178 List<Ref> delta1 = Arrays.asList(
179 ref("refs/heads/next", 4),
180 ref(String.format("refs/heads/%03d", 55), 4096));
181 List<Ref> delta2 = Arrays.asList(
182 delete("refs/heads/next"),
183 ref(String.format("refs/heads/%03d", 55), 8192));
184 List<Ref> delta3 = Arrays.asList(
185 ref("refs/heads/master", 4242),
186 ref(String.format("refs/heads/%03d", 42), 5120),
187 ref(String.format("refs/heads/%03d", 98), 6120));
188
189 List<Ref> expected = merge(base, delta1, delta2, delta3);
190 MergedReftable mr = merge(
191 write(base),
192 write(delta1),
193 write(delta2),
194 write(delta3));
195 try (RefCursor rc = mr.allRefs()) {
196 for (Ref exp : expected) {
197 assertTrue("has " + exp.getName(), rc.next());
198 Ref act = rc.getRef();
199 assertEquals(exp.getName(), act.getName());
200 assertEquals(exp.getObjectId(), act.getObjectId());
201 assertEquals(1, rc.getRef().getUpdateIndex());
202 }
203 assertFalse(rc.next());
204 }
205 }
206
207 @Test
208 public void scanIncludeDeletes() throws IOException {
209 List<Ref> delta1 = Arrays.asList(ref("refs/heads/next", 4));
210 List<Ref> delta2 = Arrays.asList(delete("refs/heads/next"));
211 List<Ref> delta3 = Arrays.asList(ref("refs/heads/master", 8));
212
213 MergedReftable mr = merge(write(delta1), write(delta2), write(delta3));
214 mr.setIncludeDeletes(true);
215 try (RefCursor rc = mr.allRefs()) {
216 assertTrue(rc.next());
217 Ref r = rc.getRef();
218 assertEquals("refs/heads/master", r.getName());
219 assertEquals(id(8), r.getObjectId());
220 assertEquals(1, rc.getRef().getUpdateIndex());
221
222 assertTrue(rc.next());
223 r = rc.getRef();
224 assertEquals("refs/heads/next", r.getName());
225 assertEquals(NEW, r.getStorage());
226 assertNull(r.getObjectId());
227 assertEquals(1, rc.getRef().getUpdateIndex());
228
229 assertFalse(rc.next());
230 }
231 }
232
233 @SuppressWarnings("boxing")
234 @Test
235 public void oneTableSeek() throws IOException {
236 List<Ref> refs = new ArrayList<>();
237 for (int i = 1; i <= 567; i++) {
238 refs.add(ref(String.format("refs/heads/%03d", i), i));
239 }
240
241 MergedReftable mr = merge(write(refs));
242 for (Ref exp : refs) {
243 try (RefCursor rc = mr.seekRef(exp.getName())) {
244 assertTrue("has " + exp.getName(), rc.next());
245 Ref act = rc.getRef();
246 assertEquals(exp.getName(), act.getName());
247 assertEquals(exp.getObjectId(), act.getObjectId());
248 assertEquals(1, act.getUpdateIndex());
249 assertFalse(rc.next());
250 }
251 }
252 }
253
254 @Test
255 public void missedUpdate() throws IOException {
256 ByteArrayOutputStream buf = new ByteArrayOutputStream();
257 ReftableWriter writer = new ReftableWriter(buf)
258 .setMinUpdateIndex(1)
259 .setMaxUpdateIndex(3)
260 .begin();
261 writer.writeRef(ref("refs/heads/a", 1), 1);
262 writer.writeRef(ref("refs/heads/c", 3), 3);
263 writer.finish();
264 byte[] base = buf.toByteArray();
265
266 byte[] delta = write(Arrays.asList(
267 ref("refs/heads/b", 2),
268 ref("refs/heads/c", 4)),
269 2);
270 MergedReftable mr = merge(base, delta);
271 try (RefCursor rc = mr.allRefs()) {
272 assertTrue(rc.next());
273 assertEquals("refs/heads/a", rc.getRef().getName());
274 assertEquals(id(1), rc.getRef().getObjectId());
275 assertEquals(1, rc.getRef().getUpdateIndex());
276
277 assertTrue(rc.next());
278 assertEquals("refs/heads/b", rc.getRef().getName());
279 assertEquals(id(2), rc.getRef().getObjectId());
280 assertEquals(2, rc.getRef().getUpdateIndex());
281
282 assertTrue(rc.next());
283 assertEquals("refs/heads/c", rc.getRef().getName());
284 assertEquals(id(3), rc.getRef().getObjectId());
285 assertEquals(3, rc.getRef().getUpdateIndex());
286 }
287 }
288
289 @Test
290 public void nonOverlappedUpdateIndices() throws IOException {
291 ByteArrayOutputStream buf = new ByteArrayOutputStream();
292 ReftableWriter writer = new ReftableWriter(buf)
293 .setMinUpdateIndex(1)
294 .setMaxUpdateIndex(2)
295 .begin();
296 writer.writeRef(ref("refs/heads/a", 1), 1);
297 writer.writeRef(ref("refs/heads/b", 2), 2);
298 writer.finish();
299 byte[] base = buf.toByteArray();
300
301 buf = new ByteArrayOutputStream();
302 writer = new ReftableWriter(buf)
303 .setMinUpdateIndex(3)
304 .setMaxUpdateIndex(4)
305 .begin();
306 writer.writeRef(ref("refs/heads/a", 10), 3);
307 writer.writeRef(ref("refs/heads/b", 20), 4);
308 writer.finish();
309 byte[] delta = buf.toByteArray();
310
311 MergedReftable mr = merge(base, delta);
312 assertEquals(1, mr.minUpdateIndex());
313 assertEquals(4, mr.maxUpdateIndex());
314
315 try (RefCursor rc = mr.allRefs()) {
316 assertTrue(rc.next());
317 assertEquals("refs/heads/a", rc.getRef().getName());
318 assertEquals(id(10), rc.getRef().getObjectId());
319 assertEquals(3, rc.getRef().getUpdateIndex());
320
321 assertTrue(rc.next());
322 assertEquals("refs/heads/b", rc.getRef().getName());
323 assertEquals(id(20), rc.getRef().getObjectId());
324 assertEquals(4, rc.getRef().getUpdateIndex());
325 }
326 }
327
328 @Test
329 public void overlappedUpdateIndices() throws IOException {
330 ByteArrayOutputStream buf = new ByteArrayOutputStream();
331 ReftableWriter writer = new ReftableWriter(buf)
332 .setMinUpdateIndex(2)
333 .setMaxUpdateIndex(4)
334 .begin();
335 writer.writeRef(ref("refs/heads/a", 10), 2);
336 writer.writeRef(ref("refs/heads/b", 20), 4);
337 writer.finish();
338 byte[] base = buf.toByteArray();
339
340 buf = new ByteArrayOutputStream();
341 writer = new ReftableWriter(buf)
342 .setMinUpdateIndex(1)
343 .setMaxUpdateIndex(3)
344 .begin();
345 writer.writeRef(ref("refs/heads/a", 1), 1);
346 writer.writeRef(ref("refs/heads/b", 2), 3);
347 writer.finish();
348 byte[] delta = buf.toByteArray();
349
350 MergedReftable mr = merge(base, delta);
351 assertEquals(1, mr.minUpdateIndex());
352 assertEquals(4, mr.maxUpdateIndex());
353
354 try (RefCursor rc = mr.allRefs()) {
355 assertTrue(rc.next());
356 assertEquals("refs/heads/a", rc.getRef().getName());
357 assertEquals(id(10), rc.getRef().getObjectId());
358 assertEquals(2, rc.getRef().getUpdateIndex());
359
360 assertTrue(rc.next());
361 assertEquals("refs/heads/b", rc.getRef().getName());
362 assertEquals(id(20), rc.getRef().getObjectId());
363 assertEquals(4, rc.getRef().getUpdateIndex());
364 }
365 }
366
367 @Test
368 public void enclosedUpdateIndices() throws IOException {
369 ByteArrayOutputStream buf = new ByteArrayOutputStream();
370 ReftableWriter writer = new ReftableWriter(buf)
371 .setMinUpdateIndex(2)
372 .setMaxUpdateIndex(3)
373 .begin();
374 writer.writeRef(ref("refs/heads/a", 10), 2);
375 writer.writeRef(ref("refs/heads/b", 2), 3);
376 writer.finish();
377 byte[] base = buf.toByteArray();
378
379 buf = new ByteArrayOutputStream();
380 writer = new ReftableWriter(buf)
381 .setMinUpdateIndex(1)
382 .setMaxUpdateIndex(4)
383 .begin();
384 writer.writeRef(ref("refs/heads/a", 1), 1);
385 writer.writeRef(ref("refs/heads/b", 20), 4);
386 writer.finish();
387 byte[] delta = buf.toByteArray();
388
389 MergedReftable mr = merge(base, delta);
390 assertEquals(1, mr.minUpdateIndex());
391 assertEquals(4, mr.maxUpdateIndex());
392
393 try (RefCursor rc = mr.allRefs()) {
394 assertTrue(rc.next());
395 assertEquals("refs/heads/a", rc.getRef().getName());
396 assertEquals(id(10), rc.getRef().getObjectId());
397 assertEquals(2, rc.getRef().getUpdateIndex());
398
399 assertTrue(rc.next());
400 assertEquals("refs/heads/b", rc.getRef().getName());
401 assertEquals(id(20), rc.getRef().getObjectId());
402 assertEquals(4, rc.getRef().getUpdateIndex());
403 }
404 }
405
406 @Test
407 public void compaction() throws IOException {
408 List<Ref> delta1 = Arrays.asList(
409 ref("refs/heads/next", 4),
410 ref("refs/heads/master", 1));
411 List<Ref> delta2 = Arrays.asList(delete("refs/heads/next"));
412 List<Ref> delta3 = Arrays.asList(ref("refs/heads/master", 8));
413
414 ByteArrayOutputStream out = new ByteArrayOutputStream();
415 ReftableCompactor compactor = new ReftableCompactor(out);
416 compactor.addAll(Arrays.asList(
417 read(write(delta1)),
418 read(write(delta2)),
419 read(write(delta3))));
420 compactor.compact();
421 byte[] table = out.toByteArray();
422
423 ReftableReader reader = read(table);
424 try (RefCursor rc = reader.allRefs()) {
425 assertTrue(rc.next());
426 Ref r = rc.getRef();
427 assertEquals("refs/heads/master", r.getName());
428 assertEquals(id(8), r.getObjectId());
429 assertFalse(rc.next());
430 }
431 }
432
433 @Test
434 public void versioningSymbolicReftargetMoves() throws IOException {
435 Ref master = ref(MASTER, 100);
436
437 List<Ref> delta1 = Arrays.asList(master, sym(HEAD, MASTER));
438 List<Ref> delta2 = Arrays.asList(ref(MASTER, 200));
439
440 MergedReftable mr = merge(write(delta1, 1), write(delta2, 2));
441 Ref head = mr.exactRef(HEAD);
442 assertEquals(head.getUpdateIndex(), 1);
443
444 Ref masterRef = mr.exactRef(MASTER);
445 assertEquals(masterRef.getUpdateIndex(), 2);
446 }
447
448 @Test
449 public void versioningSymbolicRefMoves() throws IOException {
450 Ref branchX = ref("refs/heads/branchX", 200);
451
452 List<Ref> delta1 = Arrays.asList(ref(MASTER, 100), branchX,
453 sym(HEAD, MASTER));
454 List<Ref> delta2 = Arrays.asList(sym(HEAD, "refs/heads/branchX"));
455 List<Ref> delta3 = Arrays.asList(sym(HEAD, MASTER));
456
457 MergedReftable mr = merge(write(delta1, 1), write(delta2, 2),
458 write(delta3, 3));
459 Ref head = mr.exactRef(HEAD);
460 assertEquals(head.getUpdateIndex(), 3);
461
462 Ref masterRef = mr.exactRef(MASTER);
463 assertEquals(masterRef.getUpdateIndex(), 1);
464
465 Ref branchRef = mr.exactRef(MASTER);
466 assertEquals(branchRef.getUpdateIndex(), 1);
467 }
468
469 @Test
470 public void versioningResolveRef() throws IOException {
471 List<Ref> delta1 = Arrays.asList(sym(HEAD, "refs/heads/tmp"),
472 sym("refs/heads/tmp", MASTER), ref(MASTER, 100));
473 List<Ref> delta2 = Arrays.asList(ref(MASTER, 200));
474 List<Ref> delta3 = Arrays.asList(ref(MASTER, 300));
475
476 MergedReftable mr = merge(write(delta1, 1), write(delta2, 2),
477 write(delta3, 3));
478 Ref head = mr.exactRef(HEAD);
479 Ref resolvedHead = mr.resolve(head);
480 assertEquals(resolvedHead.getObjectId(), id(300));
481 assertEquals("HEAD has not moved", resolvedHead.getUpdateIndex(), 1);
482
483 Ref master = mr.exactRef(MASTER);
484 Ref resolvedMaster = mr.resolve(master);
485 assertEquals(resolvedMaster.getObjectId(), id(300));
486 assertEquals("master also has update index",
487 resolvedMaster.getUpdateIndex(), 3);
488 }
489
490 private static MergedReftable merge(byte[]... table) {
491 List<ReftableReader> stack = new ArrayList<>(table.length);
492 for (byte[] b : table) {
493 stack.add(read(b));
494 }
495 return new MergedReftable(stack);
496 }
497
498 private static ReftableReader read(byte[] table) {
499 return new ReftableReader(BlockSource.from(table));
500 }
501
502 private static Ref ref(String name, int id) {
503 return new ObjectIdRef.PeeledNonTag(PACKED, name, id(id));
504 }
505
506 private static Ref sym(String name, String target) {
507 return new SymbolicRef(name, newRef(target));
508 }
509
510 private static Ref newRef(String name) {
511 return new ObjectIdRef.Unpeeled(NEW, name, null);
512 }
513
514 private static Ref delete(String name) {
515 return new ObjectIdRef.Unpeeled(NEW, name, null);
516 }
517
518 private static ObjectId id(int i) {
519 byte[] buf = new byte[OBJECT_ID_LENGTH];
520 buf[0] = (byte) (i & 0xff);
521 buf[1] = (byte) ((i >>> 8) & 0xff);
522 buf[2] = (byte) ((i >>> 16) & 0xff);
523 buf[3] = (byte) (i >>> 24);
524 return ObjectId.fromRaw(buf);
525 }
526
527 private byte[] write(Ref... refs) throws IOException {
528 return write(Arrays.asList(refs));
529 }
530
531 private byte[] write(Collection<Ref> refs) throws IOException {
532 return write(refs, 1);
533 }
534
535 private byte[] write(Collection<Ref> refs, long updateIndex)
536 throws IOException {
537 ByteArrayOutputStream buffer = new ByteArrayOutputStream();
538 new ReftableWriter(buffer)
539 .setMinUpdateIndex(updateIndex)
540 .setMaxUpdateIndex(updateIndex)
541 .begin()
542 .sortAndWriteRefs(refs)
543 .finish();
544 return buffer.toByteArray();
545 }
546
547 @SafeVarargs
548 private static List<Ref> merge(List<Ref>... tables) {
549 Map<String, Ref> expect = new HashMap<>();
550 for (List<Ref> t : tables) {
551 for (Ref r : t) {
552 if (r.getStorage() == NEW && r.getObjectId() == null) {
553 expect.remove(r.getName());
554 } else {
555 expect.put(r.getName(), r);
556 }
557 }
558 }
559
560 List<Ref> expected = new ArrayList<>(expect.values());
561 Collections.sort(expected, RefComparator.INSTANCE);
562 return expected;
563 }
564 }