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