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