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