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.notes;
45
46 import java.io.IOException;
47
48 import org.eclipse.jgit.errors.MissingObjectException;
49 import org.eclipse.jgit.lib.AbbreviatedObjectId;
50 import org.eclipse.jgit.lib.AnyObjectId;
51 import org.eclipse.jgit.lib.MutableObjectId;
52 import org.eclipse.jgit.lib.ObjectId;
53 import org.eclipse.jgit.lib.ObjectInserter;
54 import org.eclipse.jgit.lib.ObjectReader;
55 import org.eclipse.jgit.lib.Repository;
56 import org.eclipse.jgit.merge.MergeStrategy;
57 import org.eclipse.jgit.merge.Merger;
58 import org.eclipse.jgit.merge.ThreeWayMerger;
59
60
61
62
63
64
65
66
67 public class NoteMapMerger {
68 private static final FanoutBucket EMPTY_FANOUT = new FanoutBucket(0);
69
70 private static final LeafBucket EMPTY_LEAF = new LeafBucket(0);
71
72 private final Repository db;
73
74 private final NoteMerger noteMerger;
75
76 private final MergeStrategy nonNotesMergeStrategy;
77
78 private final ObjectReader reader;
79
80 private final ObjectInserter inserter;
81
82 private final MutableObjectId objectIdPrefix;
83
84
85
86
87
88
89
90
91
92
93
94
95
96 public NoteMapMerger(Repository db, NoteMerger noteMerger,
97 MergeStrategy nonNotesMergeStrategy) {
98 this.db = db;
99 this.reader = db.newObjectReader();
100 this.inserter = db.newObjectInserter();
101 this.noteMerger = noteMerger;
102 this.nonNotesMergeStrategy = nonNotesMergeStrategy;
103 this.objectIdPrefix = new MutableObjectId();
104 }
105
106
107
108
109
110
111
112
113
114
115 public NoteMapMerger(Repository db) {
116 this(db, new DefaultNoteMerger(), MergeStrategy.RESOLVE);
117 }
118
119
120
121
122
123
124
125
126
127
128
129
130
131 public NoteMap merge(NoteMap base, NoteMap ours, NoteMap theirs)
132 throws IOException {
133 try {
134 InMemoryNoteBucket mergedBucket = merge(0, base.getRoot(),
135 ours.getRoot(), theirs.getRoot());
136 inserter.flush();
137 return NoteMap.newMap(mergedBucket, reader);
138 } finally {
139 reader.close();
140 inserter.close();
141 }
142 }
143
144
145
146
147
148
149
150
151
152
153
154
155 private InMemoryNoteBucket merge(int treeDepth, InMemoryNoteBucket base,
156 InMemoryNoteBucket ours, InMemoryNoteBucket theirs)
157 throws IOException {
158 InMemoryNoteBucket result;
159
160 if (base instanceof FanoutBucket || ours instanceof FanoutBucket
161 || theirs instanceof FanoutBucket) {
162 result = mergeFanoutBucket(treeDepth, asFanout(base),
163 asFanout(ours), asFanout(theirs));
164
165 } else {
166 result = mergeLeafBucket(treeDepth, (LeafBucket) base,
167 (LeafBucket) ours, (LeafBucket) theirs);
168 }
169
170 result.nonNotes = mergeNonNotes(nonNotes(base), nonNotes(ours),
171 nonNotes(theirs));
172 return result;
173 }
174
175 private FanoutBucket asFanout(InMemoryNoteBucket bucket) {
176 if (bucket == null)
177 return EMPTY_FANOUT;
178 if (bucket instanceof FanoutBucket)
179 return (FanoutBucket) bucket;
180 return ((LeafBucket) bucket).split();
181 }
182
183 private static NonNoteEntry nonNotes(InMemoryNoteBucket b) {
184 return b == null ? null : b.nonNotes;
185 }
186
187 private InMemoryNoteBucket mergeFanoutBucket(int treeDepth,
188 FanoutBucket base,
189 FanoutBucket ours, FanoutBucket theirs) throws IOException {
190 FanoutBucket result = new FanoutBucket(treeDepth * 2);
191
192 for (int i = 0; i < 256; i++) {
193 NoteBucket b = base.getBucket(i);
194 NoteBucket o = ours.getBucket(i);
195 NoteBucket t = theirs.getBucket(i);
196
197 if (equals(o, t))
198 addIfNotNull(result, i, o);
199
200 else if (equals(b, o))
201 addIfNotNull(result, i, t);
202
203 else if (equals(b, t))
204 addIfNotNull(result, i, o);
205
206 else {
207 objectIdPrefix.setByte(treeDepth, i);
208 InMemoryNoteBucket mergedBucket = merge(treeDepth + 1,
209 FanoutBucket.loadIfLazy(b, objectIdPrefix, reader),
210 FanoutBucket.loadIfLazy(o, objectIdPrefix, reader),
211 FanoutBucket.loadIfLazy(t, objectIdPrefix, reader));
212 result.setBucket(i, mergedBucket);
213 }
214 }
215 return result.contractIfTooSmall(objectIdPrefix, reader);
216 }
217
218 private static boolean equals(NoteBucket a, NoteBucket b) {
219 if (a == null && b == null)
220 return true;
221 return a != null && b != null && a.getTreeId().equals(b.getTreeId());
222 }
223
224 private void addIfNotNull(FanoutBucket b, int cell, NoteBucket child)
225 throws IOException {
226 if (child == null)
227 return;
228 if (child instanceof InMemoryNoteBucket)
229 b.setBucket(cell, ((InMemoryNoteBucket) child).writeTree(inserter));
230 else
231 b.setBucket(cell, child.getTreeId());
232 }
233
234 private InMemoryNoteBucket mergeLeafBucket(int treeDepth, LeafBucket bb,
235 LeafBucket ob, LeafBucket tb) throws MissingObjectException,
236 IOException {
237 bb = notNullOrEmpty(bb);
238 ob = notNullOrEmpty(ob);
239 tb = notNullOrEmpty(tb);
240
241 InMemoryNoteBucket result = new LeafBucket(treeDepth * 2);
242 int bi = 0, oi = 0, ti = 0;
243 while (bi < bb.size() || oi < ob.size() || ti < tb.size()) {
244 Note b = get(bb, bi), o = get(ob, oi), t = get(tb, ti);
245 Note min = min(b, o, t);
246
247 b = sameNoteOrNull(min, b);
248 o = sameNoteOrNull(min, o);
249 t = sameNoteOrNull(min, t);
250
251 if (sameContent(o, t))
252 result = addIfNotNull(result, o);
253
254 else if (sameContent(b, o))
255 result = addIfNotNull(result, t);
256
257 else if (sameContent(b, t))
258 result = addIfNotNull(result, o);
259
260 else
261 result = addIfNotNull(result,
262 noteMerger.merge(b, o, t, reader, inserter));
263
264 if (b != null)
265 bi++;
266 if (o != null)
267 oi++;
268 if (t != null)
269 ti++;
270 }
271 return result;
272 }
273
274 private static LeafBucket notNullOrEmpty(LeafBucket b) {
275 return b != null ? b : EMPTY_LEAF;
276 }
277
278 private static Note get(LeafBucket b, int i) {
279 return i < b.size() ? b.get(i) : null;
280 }
281
282 private static Note min(Note b, Note o, Note t) {
283 Note min = b;
284 if (min == null || (o != null && o.compareTo(min) < 0))
285 min = o;
286 if (min == null || (t != null && t.compareTo(min) < 0))
287 min = t;
288 return min;
289 }
290
291 private static Note sameNoteOrNull(Note min, Note other) {
292 return sameNote(min, other) ? other : null;
293 }
294
295 private static boolean sameNote(Note a, Note b) {
296 if (a == null && b == null)
297 return true;
298 return a != null && b != null && AnyObjectId.equals(a, b);
299 }
300
301 private static boolean sameContent(Note a, Note b) {
302 if (a == null && b == null)
303 return true;
304 return a != null && b != null
305 && AnyObjectId.equals(a.getData(), b.getData());
306 }
307
308 private static InMemoryNoteBucket addIfNotNull(InMemoryNoteBucket result,
309 Note note) {
310 if (note != null)
311 return result.append(note);
312 else
313 return result;
314 }
315
316 private NonNoteEntry mergeNonNotes(NonNoteEntry baseList,
317 NonNoteEntry oursList, NonNoteEntry theirsList) throws IOException {
318 if (baseList == null && oursList == null && theirsList == null)
319 return null;
320
321 ObjectId baseId = write(baseList);
322 ObjectId oursId = write(oursList);
323 ObjectId theirsId = write(theirsList);
324 inserter.flush();
325
326 Merger m = nonNotesMergeStrategy.newMerger(db, true);
327 if (m instanceof ThreeWayMerger)
328 ((ThreeWayMerger) m).setBase(baseId);
329 if (!m.merge(oursId, theirsId))
330 throw new NotesMergeConflictException(baseList, oursList,
331 theirsList);
332 ObjectId resultTreeId = m.getResultTreeId();
333 AbbreviatedObjectId none = AbbreviatedObjectId.fromString("");
334 return NoteParser.parse(none, resultTreeId, reader).nonNotes;
335 }
336
337 private ObjectId write(NonNoteEntry list)
338 throws IOException {
339 LeafBucket b = new LeafBucket(0);
340 b.nonNotes = list;
341 return b.writeTree(inserter);
342 }
343 }